Multicast routing, load balancing, and wavelength assignment ontree of rings

There are two steps to establish a multicast connection in WDM networks: routing and wavelength assignment. The shortest path tree (SPT) and minimum spanning tree (MST) are the two widely used multicast routing methods. The SPT method minimizes the delay from the source to every destination along a routing tree, and the MST method is often used to minimize the network cost of the tree. Load balancing is an important objective in multicast routing, which minimizes the maximal link load in the system. The objective of wavelength assignment is to minimize the number of wavelengths used in the system. This paper analyzes the performance of the shortest path tree (SPT) and minimum spanning tree (MST) methods in the tree of ring networks, regarding the performance criteria such as the delay and network cost of the generated routing trees, load balancing, and the number of wavelengths required in the system. We prove that SPT and MST methods can not only produce routing trees with low network costs and short delays, but also have good competitive ratios for the load balancing problem (LBP) and wavelength assignment problem (WAP), respectively     

Forwarding state scalability for multicast provisioning in IP networks

Forwarding state scalability is one of the critical issues that delay the multicast deployment in IP networks. With traditional multicast routing protocols, a forwarding tree is built for each multicast session, and each router is required to maintain a forwarding entry for each multicast session whose distribution tree passes through the router. This poses the multicast forwarding state scalability issue when the number of concurrent multicast sessions is very large. We first present a survey of existing work addressing this scalability issue for providing scalable IP multicast. Then we extend an existing multicast routing protocol, Multicast Extension to OSPF (MOSPF), to scale well with respect to the number of concurrent multicast sessions by introducing tunnel support. This extension aims to reduce the protocol overhead associated with MOSPF. Simulation results show that the extension can significantly reduce multicast forwarding state and computational overhead at routers without affecting the per-destination shortest path characteristic of a resulting tree or introducing extra control overhead.     

An integrated routing and admission control mechanism for real‐time multicast connection establishment

There are two major difficulties in real‐time multicast connection setup. One is the design of an efficient distributed routing algorithm which optimizes the network cost of routing trees under the real‐time constraints. The other is the integration of routing with admission control into one single phase of operations. This paper presents a real‐time multicast connection setup mechanism, which integrates multicast routing with real‐time admission control. The proposed mechanism performs the real‐time admission tests on a cost optimal tree (COT) and a shortest path tree (SPT) in parallel, aiming at optimizing network cost of the routing tree under real‐time constraints. It has the following important features: (1) it is fully distributed; (2) it achieves sub‐optimal network cost of routing trees; (3) it takes less time and less network messages for a connection setup. Copyright © 2001 John Wiley & Sons, Ltd.     

QoS multicast routing by using multiple paths/trees in wireless ad hoc networks

In this paper, we investigate the issues of QoS multicast routing in wireless ad hoc networks. Due to limited bandwidth of a wireless node, a QoS multicast call could often be blocked if there does not exist a single multicast tree that has the requested bandwidth, even though there is enough bandwidth in the system to support the call. In this paper, we propose a new multicast routing scheme by using multiple paths or multiple trees to meet the bandwidth requirement of a call. Three multicast routing strategies are studied, SPT (shortest path tree) based multiple-paths (SPTM), least cost tree based multiple-paths (LCTM) and multiple least cost trees (MLCT). The final routing tree(s) can meet the user’s QoS requirements such that the delay from the source to any destination node shall not exceed the required bound and the aggregate bandwidth of the paths or trees shall meet the bandwidth requirement of the call. Extensive simulations have been conducted to evaluate the performance of our three multicast routing strategies. The simulation results show that the new scheme improves the call success ratio and makes a better use of network resources.     

Alternate path routing for multicast

Current network-layer multicast routing protocols build multicast trees based only on hop count and policy. If a tree cannot meet application requirements, the receivers have no alternative. In this paper, we propose a general and modular architecture that integrates alternate path routing with the network's multicast services. This enables individual multicast receivers to reroute a multicast tree according to their needs, subject to policy restrictions. Our design focuses on the two primary components of this architecture - a loop-free path installation protocol and a scalable, distributed path computation algorithm. Based on a simulation study, we demonstrate that using alternate path routing enables receivers to find acceptable paths nearly as well as a link-state protocol, with much lower overhead. We also show that our approach scales to large networks and that performance improves as a multicast group grows in size.     

A QoS-aware multicast routing protocol

The future Internet is expected to support multicast applications with quality of service (QoS) requirements. To facilitate this, QoS multicast routing protocols are pivotal in enabling new receivers to join a multicast group. However, current routing protocols are either too restrictive in their search for a feasible path between a new receiver and the multicast tree, or burden the network with excessive overhead. We propose QMRP, a new QoS-aware multicast routing protocol. QMRP achieves scalability by significantly reducing the communication overhead of constructing a multicast tree, yet it retains a high chance of success. This is achieved by switching between single-path routing and multiple-path routing according to the current network conditions. The high level design of QMRP makes it operable on top of any unicast routing algorithm in both intradomain and interdomain. Its responsiveness is improved by using a termination mechanism which detects the failure as well as the success of routing without the use of timeout. In addition, QMRP always constructs loop-free multicast trees     

Comparison of routing methods in optical multicast WDM ring networks

Multicast routing and wavelength assignment (MC-RWA) is an important issue when designing multicast WDM ring networks. Two heuristic multicast routing methods, minimum spanning tree (MST) and shortest path routing (SPT), have been studied extensively. However, the comparison of those two heuristics in terms of the number of required wavelengths is still an open issue because of the lack of efficient optimization methods for MC-RWA. In this paper, using a recently developed optimization algorithm, we compare the two multicast routing methods and optimal MC-RWA. The results show that SPT requires about 1–12% more wavelengths than MST. Moreover, the number of required wavelengths under MST routing is shown to be very close to that of the optimal solution.     

Restricted dynamic Steiner trees for scalable multicast in datagramnetworks

The paper addresses the issue of minimizing the number of nodes involved in routing over a multicast tree and in the maintenance of such a tree in a datagram network. It presents a scheme where the tree routing and maintenance burden is laid only upon the source node and the destination nodes associated with the multicast tree. The main concept behind this scheme is to view each multicast tree as a collection of unicast paths and to locate only the multicast source and destination nodes on the junctions of their multicast tree. The paper shows that despite this restriction, the cost of the created multicast trees is not necessarily higher than the cost of the trees created by other algorithms that do not impose the restriction and therefore require all nodes along the data path of a tree to participate in routing over the tree and in the maintenance of the tree     

Multicast Routing in Wireless Mesh Networks: Minimum Cost Trees or Shortest Path Trees?

There exist two fundamental approaches to multicast routing: shortest path trees (SPTs) and minimum cost trees (MCTs). The SPT algorithms minimize the distance (or cost) from the sender to each receiver, whereas the MCT algorithms minimize the overall cost of the multicast tree. Due to the very large scale and unknown topology of the Internet, computing MCTs for multicast routing in the Internet is a very complex problem. As a result, the SPT approach is the more commonly used method for multicast routing in the Internet, because it is easy to implement and gives minimum delay from the sender to each receiver, a property favored by many real-life applications. Unlike the Internet, a wireless mesh network (WMN) has a much smaller size, and its topology can be made known to all nodes in the network. This makes the MCT approach an equally viable candidate for multicast routing in WMNs. However, it is not clear how the two types of trees compare when used in WMNs. In this article we present a simulation-based performance comparison of SPTs and MCTs in WMNs, using performance metrics, such as packet delivery ratio, end-to-end delay, and traffic impacts on unicast flows in the same network.     

基于共享路径和网络编码的光组播容量优化

为了降低光组播路由 的光域网络编码代价和提高达到理论最大光组播容量的 概率,提出一种基于共享链路和网络编 码的优化光组播容量方法。首先设计一种从多条源－ 宿最短路径中选择能达到最大光组播容量的最短路径簇,然后在 最短路径簇中计算路径的共享度,选择共享度高的组播路径传输网络编码信息,构造网络编 码次数最少的光组播编码子图, 解决传统的网络编码组 播路由和最大共享度链路组播路由中存在的网络编码次数过多和达到最大光组播容量概率过 低的问 题。仿真结果表明:本文提出的方法具有最低的网络编码代价,能以最大的概率达到光组播 理论最大容量。     

A learning automata and clustering-based routing protocol for named data networking

Named data networking (NDN) is a new information-centric networking architecture in which data or content is identified by a unique name and saved pieces of the content are used in the cache of routers. Certainly, routing is one of the major challenges in these networks. In NDN, to achieve the required data for users, interest messages containing the names of data are sent. Because the source and destination addresses are not included in this package, routers forward them using the names that carried in packages. This forward will continue until the interest package is served. In this paper, we propose a routing algorithm for NDN. The purpose of this protocol is to choose a path with the minimum cost in order to enhance the quality of internet services. This is done using learning automata with multi-level clustering and the cache is placed in each cluster head. Since the purpose of this paper is to provide a routing protocol and one of the main rules of routing protocol in NDN is that alternative paths should be found in each path request, so, we use multicast trees to observe this rule. One way of making multicast trees is by using algorithms of the Steiner tree construction in the graph. According to the proposed algorithm, the content requester and content owners are the Steiner tree root and terminal nodes, respectively. Dijkstra’s algorithm is one of the proper algorithms in routing which is used for automata convergence. The proposed algorithm has been simulated in NS2 environment and proved by mathematical rules. Experimental results show the excellence of the proposed method over the one of the most common routing protocols in terms of the throughput, control message overhead, packet delivery ratio and end-to-end delay.     

Morphing distribution trees—On the evolution of multicast states under mobility and an adaptive routing scheme for mobile SSM sources

Source Specific Multicast (SSM) promises a wider dissemination of group distribution services than Any Source Multicast, as it relies on simpler routing strategies with reduced demands on the infrastructure. However, SSM is designed for á priori known and changeless addresses of multicast sources and thus withstands any easy extension to mobility. Up until now only few approaches arose from the Internet research community, leaving SSM source mobility as a major open problem. The purpose of this paper is twofold. At first we analyze characteristic properties of multicast shortest path trees evolving under source mobility. Analytically and by stochastic simulations we derive measures on the complexity of SSM routing under source mobility. At second we introduce a straightforward extension to multicast routing for transforming (morphing) source specific delivery trees into optimal trees rooted at a relocated source. All packet forwarding is done free of tunneling. Multicast service disruption and signaling overhead for the algorithms remain close to minimal. Further on we evaluate the proposed scheme using both, analytical estimates and stochastic simulations based on a variety of real-world Internet topology data. Detailed comparisons are drawn to bi-directional tunneling, as well as to proposals on concurrent distribution trees.     

Avoidance of multicast incapable branching nodes for multicast routing in WDM networks

In this article we study the multicast routing problem in all-optical WDM networks under the spare light splitting constraint. To implement a multicast session, several light-trees may have to be used due to the limited fanouts of network nodes. Although many multicast routing algorithms have been proposed in order to reduce the total number of wavelength channels used (total cost) for a multicast session, the maximum number of wavelengths required in one fiber link (link stress) and the end-to-end delay are two parameters which are not always taken into consideration. It is known that the shortest path tree (SPT) results in the optimal end-to-end delay, but it can not be employed directly for multicast routing in sparse light splitting WDM networks. Hence, we propose a novel wavelength routing algorithm which tries to avoid the multicast incapable branching nodes (MIBs, branching nodes without splitting capability) in the shortest-path-based multicast tree to diminish the link stress. Good parts of the shortest-path-tree are retained by the algorithm to reduce the end-to-end delay. The algorithm consists of tree steps: (1) a DijkstraPro algorithm with priority assignment and node adoption is introduced to produce a SPT with up to 38% fewer MIB nodes in the NSF topology and 46% fewer MIB nodes in the USA Longhaul topology, (2) critical articulation and deepest branch heuristics are used to process the MIB nodes, (3) a distance-based light-tree reconnection algorithm is proposed to create the multicast light-trees. Extensive simulations demonstrate the algorithm’s efficiency in terms of link stress and end-to-end delay.     

无线Mesh网络可靠多播路由

无线Mesh网络多播路由是无线路由必须解决的关键技术。部分研究者对网络资源和服务质量（QoS）进行研究,提出了建立最短路径树、最小开销树、负载感知、信道分配多播等多播算法;有的算法考虑链路可靠性,建立备用路径。将结合网络资源和可靠性对多播路由算法进行研究,提出了建立可靠多播树（RT,Reliable Tree）的多播路由算法：可靠多播树是一个多树结构,由一棵首选多播树和一棵多径树构成,多径树提供可靠多路径,以提高网络吞吐量。     

A location prediction based routing protocol and its extensions for multicast and multi-path routing in mobile ad hoc networks

This paper discusses a new location prediction based routing (LPBR) protocol for mobile ad hoc networks (MANETs) and its extensions for multicast and multi-path routing. The objective of the LPBR protocol is to simultaneously minimize the number of flooding-based route discoveries as well as the hop count of the paths for a source–destination (s–d) session. During a regular flooding-based route discovery, LPBR collects the location and mobility information of nodes in the network and stores the collected information at the destination node of the route search process. When the minimum-hop route discovered through flooding fails, the destination node locally predicts a global topology based on the location and mobility information collected during the latest flooding-based route discovery and runs a minimum-hop path algorithm. If the predicted minimum-hop route exists in reality, no expensive flooding-based route discovery is needed and the source continues to send data packets on the discovered route. Similarly, we propose multicast extensions of LPBR (referred to as NR-MLPBR and R-MLPBR) to simultaneously reduce the number of tree discoveries and the hop count per path from the source to each multicast group receiver. Nodes running NR-MLPBR are not aware of the receivers of the multicast group. R-MLPBR assumes that each receiver node also knows the identity of the other receiver nodes of the multicast group. Finally, we also propose a node-disjoint multi-path extension of LPBR (referred to as LPBR-M) to simultaneously minimize the number of multi-path route discoveries as well as the hop count of the paths.     

光组播路由代价与波长使用量的联合优化方法

为解决光组播路由中组播中路由代价和波长资源消耗单一化造成的组播路树路由的代价过高问题,在分光节点约束条件下,提出了光组播路由代价与波长使用量联合优化的长路优先(LPF)方法和短路优先(SPF)方法。算法通过检查最小光组播树是否存在节点分光约束的问题,根据设置的波长使用代价控制因子,使LPF或SPF的路由代价和波长使用量最小。LPF方法首先选择组播树最长路径或新波长通道重路由受分光约束的目的节点,SPF方法先选择组播树中最短路径或新波长通道重路由受分光约束的目的节点,仿真结果表明,本文提出的两种联合优化方法都能实现路由代价较低和波长需求较少的目的。     

Improved heuristics for multicast routing in wireless mesh networks

Multicast is a communication technique that allows a source to transmit data to a set of recipients in an efficient manner. Therefore, the primary objective of a multicast routing protocol would be to minimize number of transmissions to conserve bandwidth. The problem of computing multicast trees with minimal bandwidth consumption is similar to Steiner tree problem and has shown to be NP-complete. So, heuristic based algorithms are suitable to approximate such bandwidth optimal trees. This paper proposes a multicast routing protocol based on minimum number of transmission trees using an heuristic approach. The simulation results show that the proposed algorithm offers better performance over existing protocols, even in the worst-case scenario when the set of multicast receivers are sparsely distributed across the network.     

A dynamic multicast routing satisfying multiple QoS constraints

In this paper we propose a QoS‐based routing algorithm for dynamic multicasting. The complexity of the problem can be reduced to a simple shortest path problem by applying a Weighted Fair Queuing (WFQ) service discipline. Using a modified Bellman–Ford algorithm, the proposed routing builds a multicast tree, where a node is added to the existing multicast tree without re‐routing and satisfying QoS constraints. With user defined life‐time of connection this heuristic algorthm builds multicast tree which is near optimum over the whole duration of session. Simulation results show that tree costs are nearly as good as other dynamic multicast routings that does not consider QoS. Copyright © 2003 John Wiley & Sons, Ltd.     

New dynamic algorithms for shortest path tree computation

The open shortest path first (OSPF) and IS-IS routing protocols widely used in today's Internet compute a shortest path tree (SPT) from each router to other routers in a routing area. Many existing commercial routers recompute an SPT from scratch following changes in the link states of the network. Such recomputation of an entire SPT is inefficient and may consume a considerable amount of CPU time. Moreover, as there may coexist multiple SPTs in a network with a set of given link states, recomputation from scratch causes frequent unnecessary changes in the topology of an existing SPT and may lead to routing instability. We present new dynamic SPT algorithms that make use of the structure of the previously computed SPT. Besides efficiency, our algorithm design objective is to achieve routing stability by making minimum changes to the topology of an existing SPT (while maintaining shortest path property) when some link states in the network have changed. We establish an algorithmic framework that allows us to characterize a variety of dynamic SPT algorithms including dynamic versions of the well-known Dijkstra, Bellman-Ford, D'Esopo-Pape algorithms, and to establish proofs of correctness for these algorithms in a unified way. The theoretical asymptotic complexity of our new dynamic algorithms matches the best known results in the literature     

Bandwidth-satisfied multicast trees in large-scale ad-hoc networks

The purpose of this paper is to construct bandwidth-satisfied multicast trees for QoS applications in large-scale ad-hoc networks (MANETs). Recent routing protocols and multicast protocols in large-scale MANETs adopt two-tier infrastructures to avoid the inefficiency of the flooding. Hosts with a maximal number of neighbors are often chosen as backbone hosts (BHs) to forward packets. Most likely, these BHs will be traffic concentrations/bottlenecks of the network. In addition, since host mobility is not taken into consideration in BH selection, these two-tier schemes will suffer from more lost packets if highly mobile hosts are selected as BHs. In this paper, a new multicast protocol is proposed for partitioning large-scale MANET into two-tier infrastructures. In the proposed two-tier multicast protocol, hosts with fewer hops and longer remaining connection time to the other hosts will be selected as BHs. The objective is not only to obtain short and stable multicast routes, but also to construct a stable two-tier infrastructure with fewer lost packets. Further, previous MANET quality-of-service (QoS) routing/multicasting protocols determined bandwidth-satisfied routes for QoS applications. Some are implemented as a probing scheme, but the scheme is inefficient due to high overhead and slow response. On the contrary, the others are implemented by taking advantage of routing and link information to reduce the inefficiency. However, the latter scheme suffers from two bandwidth-violation problems. In this paper, a novel algorithm is proposed to avoid the two problems, and it is integrated with the proposed two-tier multicast protocol to construct bandwidth-satisfied multicast trees for QoS applications in large-scale MANETs. The proposed algorithm aims to achieve better network performance by minimizing the number of forwarders in a tree.