QoS multicast routing algorithm based on GA

The multicast routing problem with multiple QoS constraints in networks with uncertain parameters is discussed, and a network model that is suitable to research such QoS multicast routing problem is described. The QMRGA, a multicast routing policy for Internet, mobile network or other highperformance networks is mainly presented, which is based on the genetic algorithm(GA), and can provide QoSsensitive paths in a scalable and flexible way in the network environment with uncertain parameters. The QMRGA can also optimize the network resources such as bandwidth and delay, and can converge to the optimal or nearoptimal solution within few iterations, even for the network environment with uncertain parameters. The incremental rate of computational cost can be close to a polynomial and is less than exponential rate. The performance measures of the QMRGA are evaluated by using simulations. The results show that QMRGA provides an available approach to QoS multicast routing in network environment with uncertain parameters.

A Novel Genetic Algorithm for Stable Multicast Routing in Mobile Ad Hoc Networks

Data transmission among multicast trees is an efficient routing method in mobile ad hoc networks(MANETs). Genetic algorithms(GAs) have found widespread applications in designing multicast trees. This paper proposes a stable quality-of-service(QoS) multicast model for MANETs. The new model ensures the duration time of a link in a multicast tree is always longer than the delay time from the source node. A novel GA is designed to solve our QoS multicast model by introducing a new crossover mechanism called leaf crossover(LC), which outperforms the existing crossover mechanisms in requiring neither global network link information, additional encoding/decoding nor repair procedures. Experimental results confirm the effectiveness of the proposed model and the efficiency of the involved GA. Specifically, the simulation study indicates that our algorithm can obtain a better QoS route with a considerable reduction of execution time as compared with existing GAs.

Multiple constraints-based QoS multicast routing: model and algorithms

Constraint-based multicast routing, which aims at identifying a path that satisfies a set of quality of service (QoS) constraints, has became a very important research issue in the areas of networks and distributed systems. In general, multi-constrained path selection with or without optimization is a NP-complete problem that can not be exactly solved in polynomial time. Hence, accurate constraints-based routing algorithms with a fast running time are scarce, perhaps even non-existent. The expected impact of such a constrained-based routing algorithm has resulted in the proposal of numerous heuristics and a few exact QoS algorithms. This paper aims to give a thorough, concise and fair evaluation of the most important multiple constraint-based QoS multicast routing algorithms known today, and it provides a descriptive overview and simulation results of these multi-constrained routing algorithms.

Multicast Routing Based on Hybrid Genetic Algorithm

A new multicast routing algorithm based on the hybrid genetic algorithm (HGA) is proposed. The coding pattern based on the number of routing paths is used. A fitness function that is computed easily and makes algorithm quickly convergent is proposed. A new approach that defines the HGA's parameters is provided. The simulation shows that the approach can increase largely the convergent ratio, and the fitting values of the parameters of this algorithm are different from that of the original algorithms. The optimal mutation probability of HGA equals 0.50 in HGA in the experiment, but that equals 0.07 in SGA. It has been concluded that the population size has a significant influence on the HGA's convergent ratio when it's mutation probability is bigger. The algorithm with a small population size has a high average convergent rate. The population size has little influence on HGA with the lower mutation probability.

A multicast routing algorithm with multiple trees

Quality of service (QoS) multicast routing has continued to be a very important research topic in the Internet. A method of multicast routing is proposed to simultaneously optimize several parameters based on multiobjective genetic algorithm, after the related work is reviewed. The contribution lies on that the selection process of such routing is treated with multiobjective optimization. Different quality criterions in IP network are taken into account for multicast communications. A set of routing trees is generated to approximate the Pareto front of multicast problem. Multiple trees can be selected from the final set of nondominated solutions, and applied to obtain a good overall link cost and balance traffic distribution according to some simulation results.

Constructing Multicast Routing Tree for Inter-cloud Data Transmission：An Approximation Algorithmic Perspective

Networking plays a crucial role in cloud computing especially in an inter-cloud environment, where data communications among data centers located at different geographical sites form the foundation of inter-cloud federation. Data transmissions required for inter-cloud federation in the complex inter-cloud networking system are often point-to-multi points, which calls for a more effective and efficient multicast routing algorithm in complex networking systems. In this paper, we investigate the multicast routing problem in the inter-cloud context with K constraints where K ≥ 2. Unlike most of existing algorithms that are too complex to be applied in practical scenarios, a novel and fast algorithm for establishing multicast routing tree for interclouds is proposed. The proposed algorithm leverages an entropybased process to aggregate all weights into a comprehensive metric, and then uses it to search a multicast tree(MT) on the basis of the shortest path tree(SPT). We conduct complexity analysis and extensive simulations for the proposed algorithm from the approximation perspective. Both analytical and experimental results demonstrate that the algorithm is more efficient than a representative multi-constrained multicast routing algorithm in terms of both speed and accuracy, and thus we believe that the proposed algorithm is applicable to the inter-cloud environment.

A New Delay-Constrained Multicast Routing Algorithm Based on Shared Edges

In this paper, we made a detail analysis for the ESAMPH algorithm, and proposed ESAMPH_D algorithm according to the insufficient of ESAMPH algorithm. The ESAMPH_D algorithm does not consider those paths that do not satisfy the delay constraint, so we can ensure that all paths be taken into account will meet the limit of delay constraint, then we find the least costly path in order to build a minimum cost multicast tree. Simulation results show that the algorithm is better than ESAMPH algorithm in performance.

Two-stage evolutionary algorithm for dynamic multicast routing in mesh network

In order to share multimedia transmissions in mesh networks and optimize the utilization of network resources, this paper presents a Two-stage Evolutionary Algorithm (TEA), i.e., unicast routing evolution and multicast path composition, for dynamic multicast routing. The TEA uses a novel link-duplicate-degree encoding, which can encode a multicast path in the link-duplicate-degree and decode the path as a link vector easily. A dynamic algorithm for adding nodes to or removing nodes from a multicast group and a repairing algorithm are also covered in this paper. As the TEA is based on global evaluation, the quality of the multicast path remains stabilized without degradation when multicast members change over time. Therefore, it is not necessary to rearrange the multicast path during the life cycle of the multicast sessions. Simulation results show that the TEA is efficient and convergent.

QOS-BASED MULTICAST ROUTING OPTIMIZATION ALGORITHMS FOR INTERNET

Most of the multimedia applications require strict Quality-of-Service (QoS) guarantee during the communication between a single source and multiple destinations. The paper mainly presents a QoS Multicast Routing algorithms based on Genetic Algorithm (QMRGA). Simulation results demonstrate that the algorithm is capable of discovering a set of QoS-based near optimized, non-dominated multicast routes within a few iterations, even for the networks environment with uncertain parameters.

Distributed multicast routing algorithm with dynamic performance in multimedia networks

The delay and DVBMT problem is known to be NP-complete. In this paper,an efficient distributed dynamic multicast routing algorithm was proposed to produce routing trees with delay and delay variation constraints. The proposed algorithm is fully distributed,and supports the dynamic reorganizing of the multicast tree in response to changes for the destination. Simulations demonstrate that our algorithm is better in terms of tree delay and routing success ratio as compared with other existing algorithms,and performs excellently in delay variation performance under lower time complexity,which ensures it to support the requirements of real-time multimedia communications more effectively.

满足QoS约束的加速加权分布式动态Multicast算法

在计算机网络中高效实现具有延迟等ＱｏＳ约束的Ｍｕｌｔｉｃａｓｔ功能，是计算机网络应该提供的一种基本功能，是保证视频会议系统、多媒体教学系统、视频点播系统（ＶＯＤ）、网上拍卖等应用得以实现的基础．针对这一问题，提出了一种加速加权方法，根据已经经过的部分路径的延迟和剩余延迟，将成本加速加权，利用加权成本构造Ｍｕｌｔｉｃａｓｔ树．利用该算法，可以在计算机网络中以分布式方式建立接近最小成本、满足延迟约束条件、适于实时通信的动态Ｍｕｌｔｉｃａｓｔ连接，避免了传统方法将成本和延迟分别考虑、大量回溯的弊端．

多级互连网络中的multicast通信

ＭＰＰ系统中的并行通信是目前并行处理研究的热点，改善并行通信性能、提高网络吞吐率是促进ＭＰＰ性能发挥的关键问题．ｍｕｌｔｉｃａｓｔ通信是区别于点到点通信的一对多通信方式，因而功能更强大，使用起来更灵活方便，在并行处理中应用十分广泛．文中以基于开关元件实现结点间动态互连的多级互连网络为背景，研究了ｍｕｌｔｉｃａｓｔ通信路由算法的效率．针对现有路由算法的不足，提出了基于功能扩展的交换开关的ＳＢＭＴ路由算法，并进一步作出了性能分析和比较．

分层自治的Multicast地址管理和连接控制

Multicast动态地址管理和连接控制是多点会话中的重要问题．基于分层自治结构，文章提出了Multicast地址分配管理机制、主从结构连接管理体系和一种简单的多点连接建立算法，简述了它们的工作过程，并通过模拟实验比较了3种地址分配方式，即集中管理方式、分布方式（由Eleftheri-adis提出）与分层自治方式．分层自治结构与Internet自组织拓扑结构一致，分层自治地址分配机制结合了集中方式和分布方式的优点，具有较高的整体效率，主从结构连接管理体系也具有较高的控制效率，它们都具有较高的鲁棒性、柔韧性和伸缩性．

满足延迟约束的加速加权分布式动态Multicast算法

在计算机网络中高效实现具有延迟约束的Multicast功能,是计算机网络应该提供的一种基本功能,是保证视频会议系统、多媒体教学系统、视频点播系统(VOD)等应用得以实现的基础。该文针对这一问题,提出了一种加速加权方法,根据已经经过的部分路径的延迟和剩余延迟,将成本加速加权,利用加权成本构造Multicast树。利用该算法,可以在计算机网络中以分布式方式建立接近最小成本、满足延迟约束条件、适于实时通信的动态Multicast连接,避免了传统方法将成本和延迟分别考虑、大量回溯的弊端。

A Low-Complexity Resource Allocation Scheme for OFDMA Multicast Systems with Proportional Fairness

A low-complexity optimization scheme is proposed to balance the tradeoff between system capacity and proportional fairness in orthogonal frequency division multiple access(OFDMA) based multicast systems. The major challenge is to solve the non-convexity optimization problem with strict proportional fairness. Constrained team progress algorithm(CTPA) solves this non-convexity problem by allocating sub-channels to each group based on sub-channel gains and proportional fairness constraint. Mapping power algorithm(MPA) guarantees strict proportional fairness with efficient power allocation which utilizes the mapping relation between power and throughput. CTPA-MPA is analyzed in three aspects: complexity, fairness and efficiency. We numerically show that when the system capacity is slightly increased in lower power region compared with several previous approaches, CTPA-MPA improves the proportional fairness in a typical scenario with 4 groups over 16 sub-channels, while reducing the complexity from exponential to linear in the number of sub-channels. It is also proved available in a more complicated system.

Resource allocation with minimum transmit power in multicast OFDM systems

To minimize the total transmit power for multicast service in an orthogonal frequency division multiplexing（OFDM） downlink system,resource allocation algorithms that adaptively allocate subcarriers and bits are proposed.The proposed algorithms select users with good channel conditions for each subcarrier to reduce the transmit power,while guaranteeing each user＇s instantaneous minimum rate requirement.The resource allocation problem is first formulated as an integer programming（IP） problem,and then,a full search algorithm that achieves an optimal solution is presented.To reduce the computation load,a suboptimal algorithm is proposed.This suboptimal algorithm decouples the joint resource allocation problem by separating subcarrier and bit allocation.Greedy-like algorithms are employed in both procedures.Simulation results illustrate that the proposed algorithms can significantly reduce the transmit power compared with the conventional multicast approach and the performance of the suboptimal algorithm is close to the optimum.

IP MULTICAST GROUP MANAGEMENT FOR BROADCAST LANS DISTRIBUTION

Problems of the current IGMP mechanism were identified, such as unnecessary periodic probing of hosts and leave latency, which wastes bandwidth and cause more traffic and overhead. Alternative mechanism that preserve the IP multicast model but employ join/leave messages to track local group membership for broadcast LANs (shared medium LANs) was proposed in this paper. We describe the implementation requirements of the new mechanism and compare it to existing one, demonstrating that join/leave approach is uniformly superior for the environment of broadcast LANs.

Coded Multicasting for Content Delivery over Predictable Time-Varying Satellite Communication Networks

With the development of astronautic technology, communication satellites now have a tremendous gain in both quantity and quality, and have already shown their capability on multi-functional converged communication other than telecommunication. Under this circumstance, increasing the transmission efficiency of satellite communication network becomes a top priority. In this paper, we focus on content delivery service on satellite networks, where each ground station may have prefetched some file fragments. We cast this problem into a coded caching framework so as to exploit the coded multicast gain for minimizing the satellite communication load. We first propose an optimization-based coded multicast scheme by considering the special property that the satellite network topology is predictable and timevariant. Then, a greedy based fast algorithm is proposed, which can tremendously reduce the computation complexity with a small loss in optimality. Simulation experiments conducted on two Walker constellation satellite networks show that our proposed coded multicast method can efficiently reduce the communication load of satellite networks.

A Cooperative Evolution of Multiple Operators Based Adaptive Quantum Genetic Algorithm for Network Coding Resources Optimization

In order to optimize the network coding resources in a multicast network, an improved adaptive quantum genetic algorithm (AM-QEA) was proposed. Firstly, the optimization problem was translated into a graph decomposition problem. Then the graph decomposition problem was represented by the binary coding, which can be processed by quantum genetic algorithm. At last, a multiple-operators based adaptive quantum genetic algorithm was proposed to optimize the network coding resources. In the algorithm, the individual fitness evaluation operator and population mutation adjustment operator were employed to solve the shortcomings of common quantum genetic algorithm, such as high convergence rate, easy to fall into local optimal solution and low diversity of the population in later stage. The experimental results under various topologies show that the proposed algorithm has the advantages of high multicast success rate, fast convergence speed and strong global search ability in resolving the network coding resource optimization problems.