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.     

Dynamic Multicast Session Provisioning in WDM Optical Networks with Sparse Splitting Capability

In this work, we study dynamic provisioning of multicast sessions in a wavelength-routed sparse splitting capable WDM network with an arbitrary mesh topology where the network consists of nodes with full, partial, or no wavelength conversion capabilities and a node can be a tap-and-continue (TaC) node or a splitting and delivery (SaD) node. The objectives are to minimize the network resources in terms of wavelength-links used by each session and to reduce the multicast session blocking probability. The problem is to route the multicast session from each source to the members of every multicast session, and to assign an appropriate wavelength to each link used by the session. We propose an efficient online algorithm for dynamic multicast session provisioning. To evaluate the proposed algorithm, we apply the integer linear programming (ILP) optimization tool on a per multicast session basis to solve off-line the optimal routing and wavelength assignment given a multicast session and the current network topology as well as its residual network resource information. We formulate the per session multicast routing and wavelength assignment problem as an ILP. With this ILP formulation, the multicast session blocking probability or success probability can then be estimated based on solving a series of ILPs off-line. We have evaluated the effectiveness of the proposed online algorithm via simulation in terms of session blocking probability and network resources used by a session. Simulation results indicate that our proposed computationally efficient online algorithm performs well even when a fraction of the nodes are SaD nodes.     

Efficient solutions to multicast routing in communication networks

An important problem in both wireless and wired communication networks is to be able to efficiently multicst information to a group of network sites. Multicasting reduces the transmission overhead of both wireless and wired networks and the time it takes for all the nodes in the subset to receive the information. Since transmission bandwidth is a scarce commodity especially in wireless networks, efficient and near minimum-cost multicast algorithms are particularly useful in the wireless context. In this paper, we discuss methods of establishing efficient and near minimum-cost multicast routing in communication networks. In particular, we discuss an efficient implementation of a widely used multicast routing method which can construct a multicast tree with a cost no greater than twice the cost of an optimal tree. We also present two efficient multicast tree constructions for a general version of the multicast routing problem in which a network consists of different classes of nodes, where each class can have one or more nodes of the same characteristic which is different from the characteristics of nodes from other classes. Because of their efficient running times, these multicast routing methods are particularly useful in the mobile communication environments where topology changes will imply recomputation of the multicast trees. Furthermore, the proposed efficient and near minimum-cost multicast routing methods are particularly suited to the wireless communication environments, where transmission bandwidth is more scarce than wired communication environments.Partially supported by NSF/LaSER under grant number EHR-9108765, by LEQSF grant number 94-RD-A-39, by NASA under grant number NAG 5-2842.     

动态QoS多播路由协议

本文主要研讨了具有QoS约束的动态多播路由问题.文中描述了一种适用于QoS多播路由的网络模型,提出了一种动态QoS多播路由协议(DQMRP),该协议能操作在单播路由协议的顶层,它只要求网络链路(或节点)的局部状态信息,不需要维护全局状态信息.DQMRP可有效地减少构造一棵多播树的开销,多播组成员可动态地加入／退出多播会晤.该协议可搜索多条可行树枝,并能选择一条最优(或近优)树枝将新成员连接到多播树.文中给出了DQMRP的正确性证明和复杂性分析,并通过仿真实验验证了该协议的可用性和有效性.     

Tracetree: a scalable mechanism to discover multicast tree topologies in the Internet

The successful deployment of multicast in the Internet requires the availability of good network management solutions. Discovering multicast tree topologies is an important component of this task. Network managers can use topology information to monitor and debug potential multicast forwarding problems. In addition, the collected topology has several other uses, for example, in reliable multicast transport protocols, in multicast congestion control protocols, and in discovering network characteristics. We present a mechanism for discovering multicast tree topologies using the forwarding state in the network. We call our approach tracetree. First, we present the basic operation of tracetree. Then, we explore various issues related to its functionality (e.g., scalability, security, etc.). Next, we provide a detailed evaluation by comparing it to the currently available alternatives. Finally, we discuss a number of deployment issues. We believe that tracetree provides an efficient and scalable mechanism for discovering multicast tree topologies and therefore fills an important void in the area of multicast network management.     

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.     

An Efficient Multicast Routing Protocol in Wireless Mobile Networks

Providing multicast service to mobile hosts in wireless mobile networking environments is difficult due to frequent changes of mobile host location and group membership. If a conventional multicast routing protocol is used in wireless mobile networks, several problems may be experienced since existing multicast routing protocols assume static hosts when they construct the multicast delivery tree. To overcome the problems, several multicast routing protocols for mobile hosts have been proposed. Although the protocols solve several problems inherent in multicast routing proposals for static hosts, they still have problems such as non-optimal delivery path, datagram duplication, overheads resulting from frequent reconstruction of a multicast tree, etc. In this paper, we summarize these problems of multicast routing protocols and propose an efficient multicast routing protocol based on IEFT mobile IP in wireless mobile networks. The proposed protocol introduces a multicast agent, where a mobile host receives a tunneled multicast datagram from a multicast agent located in a network close to it or directly from the multicast router in the current network. While receiving a tunneled multicast datagram from a remote multicast agent, the local multicast agent may start multicast join process, which makes the multicast delivery route optimal. The proposed protocol reduces data delivery path length and decreases the amount of duplicate copies of multicast datagrams. We examined and compared the performance of the proposed protocol and existing protocols by simulation under various environments and we got an improved performance over the existing proposals.     

Minimizing Intermediate Multicast routing for dynamic multi-hop ad hoc networks

A Minimizing Intermediate Multicast Routing protocol （MIMR） is proposed for dynamic multi-hop ad hoc networks. In MIMR, multicast sessions are created and released only by source nodes. In each multicast session process, the source node keeps a list of intermediate nodes and destinations, which is encapsulated into the packet header when the source node sends a multicast packet. Nodes receiving multicast packets decide to accept or forward the packet according to the list. Depending on topology matrix maintained by unicast routing, the shortest virtual hierarchy routing tree is constructed by improved Dijkstra algorithm. MIMR can achieve the minimum number of intermediate nodes, which are computed through the tree. No control packet is transmitted in the process of multicast session. Load of the network is largely decreased. Experimental result shows that MIMR is flexible and robust for dynamic ad hoc networks.     

On Multicast Routing for Wavelength-Routed WDM Networks with Dynamic Membership

Future broadband networks must support integrated services and offer flexible bandwidth usage. In our previous work in [1], we explored the optical link control (OLC) layer on the top of optical layer that enables the possibility of bandwidth on-demand (BoD) service directly over wavelength division multiplexed (WDM) networks. Today, more and more applications and services such as video-conferencing software and Virtual LAN service require multicast support over the underlying networks. Currently, it is difficult to provide wavelength multicast over optical switches without optical/electronic conversions although the conversion takes extra cost. In this paper, based on the proposed wavelength router architecture (equipped with ATM switches to offer O/E and E/O conversions when necessary), a dynamic multicast routing algorithm is proposed to furnish multicast services over WDM networks. The goal is to join a new group member into the multicast tree so that the cost, including the link cost and the optical/electronic conversion cost, is kept as low as possible. The same algorithm can be applied to other wavelength routing architectures with redefinition of electronic copy cost. The effectiveness of the proposed wavelength router architecture as well as the dynamic multicast algorithm is evaluated by simulation.     

A ring-based multicast routing topology with QoS support in wireless mesh networks

Wireless mesh networking (WMN) is an emerging technology for future broadband wireless access. The proliferation of the mobile computing devices that are equipped with cameras and ad hoc communication mode creates the possibility of exchanging real-time data between mobile users in wireless mesh networks. In this paper, we argue for a ring-based multicast routing topology with support from infrastructure nodes for group communications in WMNs. We study the performance of multicast communication over a ring routing topology when 802.11 with RTS/CTS scheme is used at the MAC layer to enable reliable multicast services in WMNs. We propose an algorithm to enhance the IP multicast routing on the ring topology. We show that when mesh routers on a ring topology support group communications by employing our proposed algorithms, a significant performance enhancement is realized. We analytically compute the end-to-end delay on a ring multicast routing topology. Our results show that the end-to-end delay is reduced about 33 %, and the capacity of multicast network (i.e., maximum group size that the ring can serve with QoS guarantees) is increased about 50 % as compared to conventional schemes. We also use our analytical results to develop heuristic algorithms for constructing an efficient ring-based multicast routing topology with QoS guarantees. The proposed algorithms take into account all possible traffic interference when constructing the multicast ring topology. Thus, the constructed ring topology provides QoS guarantees for the multicast traffic and minimizes the cost of group communications in WMNs.     

Domain Constrained Multicast: A New Approach for IP Multicast Routing

One of major reasons why IP multicast has not been well deployed is the complexity of IP multicast routing. Since existing IP multicast routing protocols have been designed independently of IP unicast routing protocols, a router must maintain routing tables for both IP mutlicast and unicast routing. This is, in particular, a big burden for an inter-domain router. In addition, by using existing IP multicast routing protocols, we cannot realize an application that a sending host outside the designated domain sends IP multicast packets only towards the designated domain. To resolve above issues, we propose a new architecture for IP multicast, which is called Domain Constrained Multicast (DCM). In this architecture, IP multicast packets are forwarded to a border router of the designated domain using IP unicast routing. And then, IP multicast packets are delivered inside the designated domain using IP multicast. We propose an address format when realizing the DCM architecture using IPv6. We describe the extension of the DCM architecture for applying it to inter-domain IP multicast routing. Finally, we have compared the DCM architecture for inter-domain routing, with existing inter-domain IP multicast routing protocols such as MSDP and BGMP.     

High-throughput multicast routing metrics in wireless mesh networks

The stationary nature of nodes in a mesh network has shifted the main design goal of routing protocols from maintaining connectivity between source and destination nodes to finding high-throughput paths between them. Numerous link-quality-based routing metrics have been proposed for choosing high-throughput routing paths in recent years. In this paper, we study routing metrics for high-throughput tree or mesh construction in multicast protocols. We show that there is a fundamental difference between unicast and multicast routing in how data packets are transmitted at the link layer, and accordingly how the routing metrics for unicast routing should be adapted for high-throughput multicast routing. We propose a low-overhead adaptive online algorithm to incorporate link-quality metrics to a representative multicast routing protocol. We then study the performance improvement achieved by using different link-quality-based routing metrics via extensive simulation and experiments on a mesh-network testbed, using ODMRP as a representative multicast protocol.Our extensive simulation studies show that: (1) ODMRP equipped with any of the link-quality-based routing metrics can achieve higher throughput than the original ODMRP. In particular, under a tree topology, on average, ODMRP enhanced with link-quality routing metrics achieve up to 34% higher throughput than the original ODMRP under low multicast sending rate; (2) the improvement reduces to 21% under high multicast sending rate due to higher interference experienced by the data packets from the probe packets; (3) heavily penalizing lossy links is an effective way in the link-quality metric design to avoid low-throughput paths; and (4) the path redundancy from a mesh data dissemination topology in mesh-based multicast protocols provides another degree of robustness to link characteristics and reduces the additional throughput gain achieved by using link-quality-based routing metrics. Finally, our experiments on an eight-node testbed show that on average, ODMRP using SPP and PP achieves 14% and 17% higher throughput over ODMRP, respectively, validating the simulation results.     

Stateless overlay multicast with in-packet bloom filters

Due to the difficulty of deploying Internet protocol (IP) multicast on the Internet on a large scale, overlay multicast has been considered as a promising alternative to develop the multicast communication in recent years. However, the existing overlay multicast solutions suffer from high costs to maintain the state information of nodes in the multicast forwarding tree. A stateless overlay multicast scheme is proposed, in which the multicast routing information is encoded by a bloom filter (BF) and encapsulated into the packet header without any need for maintaining the multicast forwarding tree. Our scheme leverages the node heterogeneity and proximity information in the physical topology and hierarchically constructs the transit-stub overlay topology by assigning geometric coordinates to all overlay nodes. More importantly, the scheme uses BF technology to identify the nodes and links of the multicast forwarding tree, which improves the forwarding efficiency and decreases the false-positive forwarding loop. The analytical and simulation results show that the proposal can achieve high forwarding efficiency and good scalability.     

基于灰狼算法的无线网络组播路由优化

针对无线网络中资源受限的组播路由问题,考虑网络节点的节点度限制和网络链路的带宽约束,以最小化组播路由开销为目标,提出了一种二进制编码方式的基于灰狼优化算法的组播路由策略.在给定的网络拓扑下,基于灰狼优化算法的组播路由策略可以迅速找到一棵包含源和目的节点的最小开销组播树.仿真结果表明,相比于遗传算法,所提出的基于灰狼优化...     

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.     

Protecting multicast sessions in WDM optical mesh networks

Recent advances in wavelength-division-multiplexing (WDM) technology are expected to facilitate bandwidth-intensive multicast applications. However, a single fiber (bundle) cut on such a network can disrupt the transmission of information to several destination nodes on a "light tree"-based multicast session. Thus, it is imperative to protect multicast sessions e.g., by reserving resources along backup trees. We show that, if a backup tree is directed-link-disjoint to its primary counterpart, then data loss can be prevented in the event of any single link failure. We provide mathematical formulations for efficient routing and wavelength assignment (RWA) of several multicast sessions (including their backup trees for dedicated protection) at a globally optimum cost. We present these formulations for networks equipped with two kinds of multicast-capable switch architectures: one using the opaque (O-E-O) approach and the other using transparent (all-optical) approach. We expand our formulations to accommodate sparse splitting constraints in a network, in which an optical splitter has limited splitting fanout and each node has a limited number of such splitters. We develop a profit-maximizing model that would enable a network operator to be judicious in selecting sessions and simultaneously routing the chosen ones optimally. We illustrate the solutions obtained from solving these optimization problem formulations for a representative-size network.     

Internet multicast routing and transport control protocols

Multicasting is a mechanism to send data to multiple receivers in an efficient way. We give a comprehensive survey on network and transport layer issues of Internet multicast. We begin with an introduction to the current Internet protocol multicast model-the "host group" model and the current Internet multicast architecture, then discuss in depth the following three research areas: (1) scalable multicast routing; (2) reliable multicast; and (3) multicast flow and congestion control. Our goal is to summarize the state of the art in Internet multicast and to stimulate further research in this area     

A scalable multicast routing protocol for building shortest path trees

Scalability is a great concern in the design of multicast routing protocols for the global Internet. Building shortest path trees (SPT) is currently one of the most widely used approaches to supporting multicast routing because of the simplicity and low per‐destination cost of such trees. However, the construction of an SPT typically involves high protocol overhead, which leads to the scalability problem as the number of concurrent multicast sessions increases. In this paper, we present a destination‐initiated shortest path tree (DSPT) routing protocol. The design objective is to effectively reduce the protocol overhead associated with SPT constructions for providing scalable multicast. To achieve this objective, we introduce destination‐initiated joining operations in constructing SPTs. With DSPT, each router receiving a request to join a specific multicast group makes a local decision on selecting its parent node through which it connects to the existing tree. A source‐rooted SPT is built as a result of such collaborative operations at nodes. DSPT requires only limited routing information at routers. Analytical results demonstrate that DSPT scales well with respect to computation, storage and communication overhead when the number of concurrent multicast requests is large. Simulation experiments are also conducted to verify the correctness of the theoretically deduced analytical results. Copyright © 2006 John Wiley & Sons, Ltd.     

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.