Effective multicasting algorithm for dynamic membership with delay constraint

This paper proposes an effective heuristic algorithm The tree constructed by DDMR has the following characteristics： for dynamic multicast routing with delay-constrained DDMR. （1） multicast tree changes with the dynamic memberships; （2） the cost of the tree is as small as possible at each node addition/removal event; （3） all of the path delay meet a fixed delay constraint; （4） minimal perturbation to an existing tree. The proposed algorithm is based on “damage” and “usefulness” concepts proposed in previous work, and has a new parameter bf（Balancing Factor） for judging whether or not to rearrange a tree region when membership changes. Mutation operation in Genetic Algorithm （GA） is also employed to find an attached node for a new adding node. Simulation showed that our algorithm performs well and is better than static heuristic algorithms, in term of cost especially.

The Distributed Network Monitoring Model with Bounded Delay Constraints

We address the problem of optimizing a distributed monitoring system and the goal of the optimization is to reduce the cost of deployment of the monitoring infrastructure by identifying a minimum aggregating set subject to delay constraint on the aggregating path. We show that this problem is NP-hard and propose approximation algorithm proving the approximation ratio with lnm+1, where is the number of monitoring nodes. At last we extend our modal with more constraint of bounded delay variation. Key words network - distributed monitoring - delay constraint - NP-hard CLC number TP 393 Foundation item: Supported by the National Natural Science Foundation of China (60373023)Biography: LIU Xiang-hui(1973-), male, Ph. D. candidate, research direction: algorithm complexity analysis, QoS in Internet.

QoS Guarantees of Multiuser Video Streaming over Wireless Links: Delay Constraint and Packet Priority Drop

To provide a certain level of Quality of Service (QoS) guarantees for multiuser wireless downlink video streaming transmissions, we propose a multiuser scheduling scheme for QoS guarantees. It is based on the classic Queue-Length-Based (QLB)-rate maximum scheduling algorithm and integrated with the delay constraint and the packet priority drop. We use the large deviation principle and the effective capacity theory to construct a new analysis model to find each user's queue length threshold (delay constraint) violation probability. This probability corresponds to the upper bound of the packet drop probability, which indicates a certain level of statistical QoS guarantees. Then, we utilize the priority information of video packets and introduce the packet priority drop to further improve the quality perceived by each user. The simulation results show that the average Peak Signal to Noise Ratio (PSNR) value of the priority drop is 0.8 higher than that of the non-priority drop and the PSNR value of the most badly damaged video frame in the priority drop is on an average 4 higher than that of the non-priority drop.

A delay-constrained energy-efficient component carrier adjusting scheme for LTE-Advanced systems

The energy efficiency and packet delay tradeoffs in long term evolution-advanced(LTE-A) systems are investigated.Analytical expressions are derived to explain the relation of energy efficiency to mean packet delay,arrival rate and component carrier(CC) configurations,from the theoretical respective which reveals that the energy efficiency of multiple CC systems is closely related to the frequency of CCs and the number of active CCs.Based on the theoretical analysis,a CC adjusting scheme for LTE-A systems is proposed to maximize energy efficiency subject to delay constraint by dynamically altering the on/off state of CCs according to traffic variations.Numerical and simulation results show that for CCs in different frequency bands with equal transmit power,the proposed scheme could significantly improve the energy efficiency of users in all aggregation levels within the constraint of mean packet delay.

A Heuristic Algorithm on QoS Routing

This paper focuses on solving the delay constrained least cost routing problem, and propose a simple, distributed heuristic solution, called distributed recursive delay constrained least cost (DR DCLC) unicast routing algorithm. DR DCLC only requires local information to find the near optimal solution. The correctness of DR DCLC is proued by showing that it is always capable of constructing a loop free delay constrained path within finite time, if such a path exists. Simulation is also used to compare DR DCLC to the optimal DCLC algorithm and other algorithms.

Modified Shifting Bottleneck Heuristic for Scheduling Problems of Large-Scale Job Shops

A modified shifting bottleneck algorithm was proposed to solve scheduling problems of a large-scale job shop.Firstly,a new structured algorithm was employed for sub-problems so as to reduce the computational burden and suit for large-scale instances more effectively.The modified cycle avoidance method,incorporating with the disjunctive graph model and topological sort algorithm,was applied to guaranteeing the feasibility of solutions with considering delayed precedence constraints.Finally,simulation experiments were carried out to verify the feasibility and effectiveness of the modified method.The results demonstrate that the proposed algorithm can solve the large-scale job shop scheduling problems(JSSPs) within a reasonable period of time and obtaining satisfactory solutions simultaneously.

Hybrid Routing by Joint Optimization of Per-Flow Routing and Tag-Based Routing in Software-Defined Networks

In recent years, Software-Defined Networks （SDNs） have become a promising technology to improve network utilization. However, limited flow table size and long deployment delays may result in low network performance in large-scale networks and a poor user experience. While a typical solution to this issue is routing aggregation （i.e., wildcard routing）, the aggregation feasibility problem and reduced network performance may be encountered. To address this dilemma, we first design a novel wildcard routing scheme, called the Tag-based Rule Placement Scheme （TRPS）. We then formulate a Hybrid Routing by Joint optimization of Per-flow routing and Tag- based routing （HR-JPT） problem, and prove its NP-hardness. An algorithm with a bounded approximation factor is designed for this problem, and the proposed methods are implemented on a Mininet platform. Extensive simulation results show that our methods are efficient for wildcard/hybrid routing. For example, our proposed tag-based wildcard rule placement scheme can reduce the number of required rules by about 65% on average compared with previous wildcard routing methods. Our proposed hybrid routing algorithm can increase network throughput by about 43% compared with existing hybrid routing solutions.

Effective capacity of cognitive radio systems in asymmetric fading channels

As known that the effective capacity theory offers a methodology for exploring the performance limits in delay constrained wireless networks, this article considered a spectrum sharing cognitive radio （CR） system in which CR users may access the spectrum allocated to primary users （PUs）. Particularly, the channel between the CR transmitter （CR-T） and the primary receiver and the channel between the CR-T and the CR receiver （CR-R） may undergo different fading types and arbitrary link power gains. This is referred to as asymmetric fading. The authors investigated the capacity gains achievable under a given delay quality-of-service （QoS） constraint in asymmetric fading channels. The closed-form expression for the effective capacity under an average received interference power constraint is obtained. The main results indicate that the effective capacity is sensitive to the fading types and link power gains. The fading parameters of the interference channel play a vital role in effective capacity for the looser delay constraints. However, the fading parameters of the CR channel play a decisive role in effective capacity for the more stringent delay constraints. Also, the impact of multiple PUs on the capacity gains under delay constraints has also been explored.