基于遗传算法的实时组播通信路由算法

组播通信路由技术是视频广播、计算机会议、CSCW()等新型分布式计算的关键技术.提出了基于分布式遗传算法的共享树组播路由算法,包括包交换的网络组播树的建立、组播树的动态维护和计算满足特定时延和时延抖动限制的近似斯坦利最小树算法等.利用它可以实现在给定网络和组播需求的情况下,在组成员间寻找动态的组播树,并使该树覆盖所有的成员,并约束网络费用达到最小.进而解决树状路由的建立以及树状路由的动态维护等问题.     

Improved Approximation Algorithms for the Quality of Service Multicast Tree Problem

The Quality of Service Multicast Tree Problem is a generalization of the Steiner tree problem which appears in the context of multimedia multicast and network design. In this generalization, each node possesses a rate and the cost of an edge with length l in a Steiner tree T connecting the source to non-zero rate nodes is l · r_e, where r_e is the maximum node rate in the component of T-{e} that does not contain the source. The best previously known approximation ratios for this problem (based on the best known approximation factor of 1.549 for the Steiner tree problem in networks) are 2.066 for the case of two non-zero rates and 4.212 for the case of an unbounded number of rates. In this paper we give improved approximation algorithms with ratios of 1.960 and 3.802, respectively. When the minimum spanning tree heuristic is used for finding approximate Steiner trees, then the previously best known approximation ratios of 2.667 for two non-zero rates and 5.542 for an unbounded number of rates are reduced to 2.414 and 4.311, respectively.     

On fair and optimal multi-source IP-multicast

We investigate the problem of maximizing multicast throughput under a fairness constraint. Multiple server nodes wish to communicate to their intended set of client nodes over a shared network infrastructure. Our goal is to devise distributed algorithms to construct multicast sessions, one for each server node, such that (a) the network infrastructure is optimally utilized and (b) the network resources are fairly distributed between multicast sessions, i.e., no individual session claims more than a prescribed share of the network bandwidth resources. We are particularly interested in multi-tree multicast strategies in which every multicast session may contain many multicast trees. We show how the use of multiple trees increases network throughput and the load distribution in the network. We propose a class of round-robin algorithms that are based on successive selection of multicast trees for each multicast session, in a loosely cooperative, yet distributed fashion. Our best algorithm, the Cooperative Shortest Path Tree Packing (CSPTP) algorithm, performs well in a variety of scenarios, ranging from very sparse to dense applications. Through extensive simulations on random networks, we compare the performance of our algorithms with those commonly used in IP-multicast as well as theoretical upper bounds derived from network coding formulations. We show that the CSPTP can improve the throughput, and often achieves about 90% of the theoretical upper bound.     

A novel ring-tree-based routing and wavelength assignment algorithm for multicasting in DWDM optical mesh networks

Multicast session communications, such as video-conferencing and video-broadcasting, in DWDM mesh networks require the efficient multipoint-to-multipoint multicast algorithms. Several heuristics have approximate solutions using lightpath or light-tree for one-to-multipoint multicast communications, but few papers have discussed the multipoint-to-multipoint multicast problems in DWDM mesh networks. This paper proposes a ring-tree-based routing and wavelength assignment (RTRWA) solution in DWDM mesh networks. It proceeds to multipoint-to-multipoint multicast transmission by reserving links and wavelengths assigned by the Least Converter Count algorithm. The RTRWA algorithm tries to find an optimal ring path that connects all multicast session members with unidirectional links and connects the remaining nodes to the ring path with the light-tree. The RTRWA algorithm outperforms the Steiner minimal tree (SMT) algorithm in terms of the call blocking probability, difference in user capacity and the mean maximum transmission time.     

Efficient Multicast Algorithms for Multichannel Wireless Mesh Networks

The wireless mesh network is an emerging technology that provides high quality service to end users as the "last mile” of the Internet. Furthermore, multicast communication is a key technology for wireless mesh networks. Multicast provides efficient data distribution among a group of nodes. However, unlike other wireless networks, such as sensor networks and MANETs, where multicast algorithms are designed to be energy efficient and to achieve optimal route discovery among mobile nodes, wireless mesh networks need to maximize throughput. This paper proposes two multicast algorithms: the Level Channel Assignment (LCA) algorithm and the Multichannel Multicast (MCM) to improve the throughput for multichannel and multi-interface mesh networks. The algorithms build efficient multicast trees by minimizing the number of relay nodes and total hop count distances of the trees. The algorithms use dedicated channel assignment strategies to reduce the interference to improve the network capacity. We also demonstrate that using partially overlapping channels can further diminish the interference. Furthermore, additional interfaces help to increase the bandwidth, and multiple gateways can further shorten the total hop count distance. Simulations show that those algorithms greatly outperform the single-channel multicast algorithm. We also observe that MCM achieves better throughput and shorter delay while LCA can be realized in distributed manner.     

多媒体通信中带度约束的多播路由算法

随着多媒体业务的发展,多播技术应用日益广泛,多播路由是要寻找连接源节点和一组目的节点的一棵多播树,这个问题在数学上归结为Steiner树问题,它是一个NPC问题。在实际网络中,网络节点具备不同的多播能力,有些节点不支持多播,有些节点支持多播,但为了保证网络速度和节点负载平衡,支持多播的节点要限制其复制信息的数量,即节点的多播能力受限。在这种情况下,寻找多播树变得更加困难,该文用节点的约束来表示敏个节点具备的多播能力,节点多播能力受限情况下的多播路由问题被称为带度约束的多播路由问题,其仍是一个NPC问题。该文提出了一种求解带度的约束多播路由问题的双层遗传算法。算法的基本思想是最优多播树应是一棵满足度约束的最小生成树,因此问题的关键在于如何找到包括在最优生成树中的Steiner节点。遗传算法 采用二进制编码方式,内层算法用于求解满足度约束的最小生成树;外层算法进行全局搜索。该文将算法在稀疏图上进行实验,为了更好地模拟真实网络,稀疏图中每个节点具有不同的多播能力,并且多播目的节点数目相比于网络节点数要小。实验对算法进行了三方面比较：（1）解的质量;（2）计算时间;（3）算法的收敛性。实验结果表明,文中提出的遗传算法能够找到费用较小的多播树,但是当网络规模增大时,算法的求解时间也较长。     

A note on distributed multicast routing in point-to-point networks

The distributed algorithm for a multicast connection set-up, based on the ‘cheapest insertion’ heuristic, is reviewed. The multicast routing problem is translated into a Steiner tree problem in point-to-point networks where nodes have only a limited knowledge about the network. A solution is proposed in which the time complexity and the amount of information exchanged between network nodes are proportional to the number of members of the multicast group. The Steiner tree is constructed by means of a distributed table-passing algorithm. The analysis of the algorithm presented, backed up by simulation results, confirms its superiority over the algorithm based on ‘waving technique’.Scope and purposeMulticasting is a mechanism used in communication networks that allows distribution of information from a single source to multiple destinations. The problem of finding a multicast connection for a static group of communicating entities in connection-oriented point-to-point network can be formulated in graph theory as a minimum Steiner tree problem. Due to NP-completeness of the Steiner tree problem multicast, routing algorithms are based on heuristics. The diversity of network environments and the lack of centralised information about network topology require an effective distribution of the multicast routing algorithms among the network nodes. This article presents an alternative to the distributed algorithm proposed by Rugelj and Klavzar that implements the same heuristics for the construction of a minimum cost multicast connection in point-to-point networks. The present algorithm constitutes a substantial improvement over that previously proposed with regard to running time and the amount of the information exchanged between network nodes.     

Algorithms for delay-constrained low-cost multicast tree construction

With the proliferation of multimedia group applications, the construction of multicast trees satisfying quality of service (QoS) requirements is becoming a problem of prime importance. Multicast groups are usually classified as sparse or pervasive groups depending on the physical distribution of group members. They are also classified based on the temporal characteristics of group membership into static and dynamic groups. In this paper, we propose two algorithms for constructing multicast trees for multimedia group communication in which the members are sparse and static. The proposed algorithms use a constrained distributed unicast routing algorithm for generating low-cost, bandwidth and delay constrained multicast trees. These algorithms have lower message complexity and call setup time due to their nature of iteratively adding paths, rather than edges, to partially constructed trees. We study the performance (in terms of call acceptance rate, call setup time and multicast tree cost) of these algorithms through simulation by comparing them with that of a recently proposed algorithm (V. Kompella, J.C. Pasquale, G.C. Polyzos, Two distributed algorithms for the constrained Steiner tree problem, in: Proc. Comp. Comm. Networking, San Diego, CA, June 1993) for the same problem. The simulation results indicate that the proposed algorithms provide larger call acceptance rates, lower setup times and comparable tree costs.     

一种在Ad Hoc网络中基于地理位置的节约能量的组播路由算法

在移动adhoc网络中,设计节约能量的组播路由算法是非常重要的,这是由于网络中的节点运行时所需要的能量来自于电池的有限供给。由于节点是可以移动的,这就要求节约能量的路由协议在本质上是分布式的,对于当前的节点状态是自适应的。论文提出一种基于地理位置的节约能量的组播路由算法,使得在满足带宽的同时,组播的能量消耗尽可能的少。其基本思想是:先由基本的组播算法生成一棵组播树,然后由组播树的每个非叶子节点根据其邻居节点的地理位置,动态地选择一些转发点,通过这些点以较小功率转发时可节约能量,以此优化组播树。     

Nonblocking k-fold multicast networks

Multicast communication involves transmitting information from a single source to multiple destinations and is a requirement in high-performance networks. Current trends in networking applications indicate an increasing demand in future networks for multicast capability. Many multicast applications require not only multicast capability, but also predictable communication performance such as guaranteed multicast latency and bandwidth. In this paper, we present a design for a nonblocking k-fold multicast network, in which any destination node can be involved in up to k simultaneous multicast connections in a nonblocking manner. We also develop an efficient routing algorithm for the network. As can be seen, a k-fold multicast network has significantly lower network cost than that of k copies of ordinary 1-fold multicast networks and is a cost effective choice for supporting arbitrary multicast communication.     

Suboptimal network coding subgraph algorithms for 5G minimum-cost multicast networks

To reduce the transmission cost in 5G multicast networks that have separate control and data planes, we focus on the minimum-power-cost network-coding subgraph problem for the coexistence of two multicasts in wireless networks. We propose two suboptimal algorithms as extensions of the Steiner tree multicast. The critical 1-cut path eliminating (C1CPE) algorithm attempts to find the minimum-cost solution for the coexistence of two multicast trees with the same throughput by reusing the links in the topology, and keeps the solution decodable by a coloring process. For the special case in which the two multicast trees share the same source and destinations, we propose the extended selective closest terminal first (E-SCTF) algorithm out of the C1CPE algorithm. Theoretically the complexity of the E-SCTF algorithm is lower than that of the C1CPE algorithm. Simulation results show that both algorithms have superior performance in terms of power cost and that the advantage is more evident in networks with ultra-densification.     

无线Mesh网络中的骨干网络部署的优化

在满足用户需求情况下,优化无线Mesh网络中接入点(TAPs)放置以及布线线路以减小布线成本.首先,把该问题中的布线问题模型化为欧氏空间中准组Steiner树问题.解决传统的组Steiner树问题的算法在该问题上并不适用.其次,针对该问题特有的特征给出了一种近似算法.最后,为了达到最小化网络布线的成本的目的,在布线的基础上使用线性规划达到最小化TAPs数目.模拟实验的结果表明,该方法能够显著降低布线成本.优化方法对于无线Mesh网络的骨干网络的部署具有重要指导意义.     

新的群播路由算法

考虑了费用非对称通信网络上的群播路由问题。首先提出了一种满足带宽约束接近最小成本的启发式算法NEW1-GM算法。该算法以FMPH算法(FastMinimumPathCostHeuristicAlgorithm)为基础,可以有效地降低成本。数值实验表明,这种算法是有效的,且所获得解的总费用几乎总是小于或等于由GTM算法所获得的解的总费用。然后,提出了一种满足延迟约束的DFMPH算法(Delay-ConstrainedFastMinimumPathCostHeuristicAlgorithm)。最后,在NEW1-GM算法和DFMPH算法的基础上提出了一种不仅满足延迟和带宽要求且接近最小成本的启发式算法DGM1算法。NEW1-GM算法和DGM1算法的时间复杂度均与GTM算法相同,为O(p3n2)。     

GLBM: A new QoS aware multicast scheme for wireless mesh networks

Wireless mesh networks (WMNs) have been attracting significant attention due to their promising technology. The WMN technology is becoming a major avenue for the fourth generation of wireless mobility. Communication in large-scale wireless networks can create bottlenecks for scalable implementations of computationally intensive applications. A class of crucially important communication patterns that have already received considerable attention in this regard are group communication operations, since these inevitably place a high demand on network bandwidth and have a consequent impact on algorithm execution times. Multicast communication has been among the most primitive group capabilities of any message passing in networks. It is central to many important distributed applications in science and engineering and fundamental to the implementation of higher-level communication operations such as gossip, gather, and barrier synchronisation. Existing solutions offered for providing multicast communications in WMN have severe restriction in terms of almost all performance characteristics. Consequently, there is a need for the design and analysis of new efficient multicast communication schemes for this promising network technology. Hence, the aim of this study is to tackle the challenges posed by the continuously growing need for delivering efficient multicast communication over WMN. In particular, this study presents a new load balancing aware multicast algorithm with the aim of enhancing the QoS in the multicast communication over WMNs. Our simulations experiments show that our proposed multicast algorithm exhibits superior performance in terms of delay, jitter and throughput, compared to the most well known multicast algorithms.     

在线多点广播路由的动态方法探讨

多点广播是网络支持多媒体业务的关键技术之一。在线多点广播问题是指组中的成员加入或离开后多点广播路由树的更新问题。本文以服务质量（QoS)指标中的带宽和时延为优化选路准则，提出了一种受限的动态多点广播路由算法，仿真结果证明了该算法比传统算法更简洁。     

A novel optimization-based bandwidth-aware minimum power multicast routing algorithm in green wireless networks

Multicast routing in wireless networks that possess the wireless multicast advantage could significantly reduce the power and energy consumption. However, this kind of multicast routing that only addresses the transmission radius coverage might not be able to meet the bandwidth requirement of the users. As a result, additional transmissions are required to incur more energy consumption and carbon dioxide emissions that make existing algorithms not applicable to bandwidth constrained applications. In this paper, for the first time, we address the bandwidth aware minimum power multicast routing problem in wireless networks where the objective function is to minimize the total power consumption subject to the users?? bandwidth requirements. This problem is a challenging cross-layer design problem that requires seamless and sophisticated integrated design in the network layer (multicast routing) and physical layer (bandwidth-aware wireless transmission and power control). We first formulate this problem as a mixed integer linear programming problem and then propose a Lagrangian relaxation based algorithm to solve this problem. Numerical results demonstrate that the proposed approach is a sound green networking algorithm that outperforms the existing power efficient multicast routing approaches under all tested cases, especially in large bandwidth request, fine radius granularity, large group size and sparse network.     

A distributed multicast routing protocol for real-time multicast applications

Multicast routing is establishing a tree which is rooted from the source node and contains all the multicast destinations. A delay bounded routing tree is a tree in which the accumulated delay from the source node to any destination along the tree does not exceed a pre-specified bound. This paper presents a distributed routing protocol which constructs delay bounded routing trees for real-time multicast connections. A constructed routing tree has a near optimal network cost under the delay bound constraint. The proposed algorithm is fully distributed, efficient in terms of the number of messages required, and flexible in multicast membership changes. A large number of simulations have been done to show the network cost of the routing trees generated by our method is better than the other major existing algorithms.     

Demand-scalable geographic multicasting in wireless sensor networks

In this paper, we focus on the challenge of demand-scalable multicast routing in wireless sensor networks. Due to the ad-hoc nature of the placement of the sensor nodes as well as the variations in the available power of the nodes, centralized or stateful routing schemes are not applicable. Thus, in this paper, we first introduce a Geographic Multicast routing Protocol (GMP) for wireless sensor networks.¹ The protocol is fully distributed and stateless. Given a set of the destinations, the transmitting node first constructs a virtual Euclidean Steiner tree rooted at itself and including the destinations, using a novel and highly efficient reduction ratio heuristic (called rrSTR). The simulation results on NS2 show that GMP requires 25% less hops and energy than the existing Position Based Multicasting, PBM, Location-Guided Steiner trees, LGS, approaches. The GMP algorithm as well as LGS and PBM all assume that each recipient receives the same copy of the multicast message. In reality, however, especially when the transmission includes streamed media, different recipients have different demands (in terms of the frequency of packets or the quality of media). Thus, in this paper, we investigate the suitability of the geographic multicasting schemes for situations where scalable transmission paths can save power. In particular, we propose intuitive mechanisms to extend the three schemes to cases where the data transmission can scale based on the demand. This leads to three new weighted multicast routing algorithms: wGMP, wLGS, and wPBM. The results show that the wGMP algorithm provides the best opportunities for scalability due to its flexible self-correcting decision making process, while other schemes, such as wLGS and wPBM are not directly suitable for scalable multicasting, due to their naively greedy structures.     

Energy efficient multicast routing in ad hoc wireless networks

In this paper, we discuss the energy efficient multicast problem in ad hoc wireless networks. Each node in the network is assumed to have a fixed level of transmission power. The problem of our concern is: given an ad hoc wireless network and a multicast request, how to find a multicast tree such that the total energy cost of the multicast tree is minimized. We first prove this problem is NP-hard and it is unlikely to have an approximation algorithm with a constant performance ratio of the number of nodes in the network. We then propose an algorithm based on the directed Steiner tree method that has a theoretically guaranteed approximation performance ratio. We also propose two efficient heuristics, node-join-tree (NJT) and tree-join-tree (TJT) algorithms. The NJT algorithm can be easily implemented in a distributed fashion. Extensive simulations have been conducted to compare with other methods and the results have shown significant improvement on energy efficiency of the proposed algorithms.