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.     

Enabling scalable multicast protocols using dynamic overlap tree path

The scalability of a multicast protocol is a very critical issue when it is implemented on a global scale. The number of forwarding states that are maintained at each multicast router explodes when the number of multicast groups grows exponentially as in the case of global Internet. In this paper we describe a technique, called dynamic overlap tree path (DOTP), to reduce the forwarding states that need to be maintained in multicast routers and hence improve the scalability of existing multicast protocols. This technique, which can be incorporated in both the dense and sparse modes of multicast protocols, dynamically finds overlapped unbranched tree paths and merges their corresponding forwarding states to reduce the storage requirement in multicast routers. It does not introduce any additional control‐message overheads through the reduction process. OPNET simulation results show that the overall average forwarding‐state table size of the simulated networks can be reduced by about 30 per cent on the average. Copyright © 2001 John Wiley & Sons, Ltd.     

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.     

Performance evaluation of the MoM mobile multicast protocol

This paper presents a performance study of a mobile multicast protocol called MoM, which is designed to support IP multicast for mobile hosts in an IP internetwork. The protocol uses the basic unicast routing capability of IETF Mobile IP, and leverages existing IP multicast to provide multicast services for mobile hosts as well. A key feature of the MoM protocol is the use of designated multicast service providers (DMSPs) to improve the scalability of mobile multicast. Discrete-event simulation is used in the performance evaluation of the protocol. The performance study focuses on the scalability, routing efficiency, fairness, and overhead of the MoM protocol, as well as on DMSP selection policies and the deliverability of multicast messages. The simulation results suggest distinct performance advantages for the MoM protocol over other approaches for mobile multicast, such as bi-directional tunnelling, particularly as the number of mobile group members increases. Furthermore, even simple policies for choosing a DMSP from possible candidates provide reasonable tradeoffs between handoff rates, routing efficiency, deliverability of messages, and protocol overhead. This revised version was published online in June 2006 with corrections to the Cover Date.     

A router-assisted session tree configuration mechanism for reliablemulticast

A session tree based mechanism provides an efficient method to avoid well-known feedback implosion. However, it is not easy to configure an efficient session tree for IP multicast because it does not provide any explicit membership and routing topology information to the upper layer protocol. Incongruity between a session tree built on the transport layer and the corresponding routing tree on the network layer would incur large cost to handle control messages. This problem can be solved if a router that knows the information of routing topology can support the configuration of a session tree. Thus this letter proposed a router-assistant mechanism which minimizes the change of router functions and allows the routers to assist in providing a reliable multicast transport service     

An ant colony optimisation algorithm for aggregated multicast based on minimum grouping model

The tree‐based delivery structure of the traditional Internet protocol multicast requires each on‐tree router to maintain a forwarding state for a group. This leads to a state scalability problem when large numbers of concurrent groups exist in a network. To address this state scalability problem, a novel scheme called aggregated multicast has recently been proposed, in which multiple groups are forced to share one delivery tree. In this paper, we define the aggregated multicast problem based on the minimum grouping model, and propose an ant colony optimisation algorithm. The relative fullness of the tree is defined according to the characteristics of the minimum grouping problem and is introduced as an important component in identifying the aggregation fitness function between two multicast groups. New pheromone update rules are designed based on the aggregation fitness function. To improve the convergence time of the algorithm, we use the changes (brought by each group) in the relative fullness of the current tree as the selection heuristic information. The impact of the relative fullness of the tree is analysed using the hypothesis test, and simulation results indicate that introducing relative fullness to the fitness function can significantly improve the optimisation performance of the algorithm. Compared with other heuristic algorithms, our algorithm has better optimisation performance and is more suitable for scenarios with larger bandwidth waste rates. Copyright © 2011 John Wiley & Sons, Ltd.     

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.     

动态QoS多播路由协议

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

Scalable Multicast Provisioning in DiffServ with MPLS Labeling

The phenomenal growth of multimedia applications imposes scalable and efficient network support. The DiffServ and MPLS architectures were developed to provide QoS. The combination of both architectures presents a very attractive strategy to backbone network providers. However, integrating native IP multicasting with MPLS supports DiffServ is a quite comple issue. Major problems are: the lack of labels in MPLS networks, the core routers simplicity in DiffServ and the multicast state scalability problems, since it requires routers to keep a forwarding state for every multicast tree passing through it. In addition, the number of states grows with the number of groups. Under such circumstance, we propose an hybrid label aggregation algorithm in order to solve multicast scalability problem and provide a solution for multicast in MPLS support DiffServ. In the proposed scheme, one label is assigned per multicast groups (logical aggregation) and different multicast groups sharing the same output interface in a router are aggregated locally (physical aggregation). Also, in order to support the proposed algorithm, we propose a separate treatment and labels space (prime numbers range) for multicast traffic. The proposed solution allows consuming fewer labels, reducing the forwarding table and consequently the total packet processing 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.     

Exploring Performance of Hypercube Structure for Multicast in Mobile Ad Hoc Networks

Performance of multicast routing protocol in mobile ad hoc networks is mostly characterized by underlying forwarding structure. Currently, general structures based on tree/mesh based scheme cannot handle with transmission efficiency, robustness to dynamic topology, scalability, and load balancing functionalities at the same time. To handle above key performance factors concurrently, we propose a new virtual backbone architecture for multicast, which is based on hierarchical hypercube structure. Due to the natural properties of hypercube structure, we can achieve efficiency, robustness and load balance in mobile ad hoc networks where links are frequently broken owing to nodes’ free immigration. Furthermore, scalability problem is naturally resolved by hierarchical structure. Finally, through simulation results, we have proven good scalability by demonstrating that our structure can provide higher packet delivery ratio with low control overhead and better scalability than tree/mesh based scheme without regard to the number of group members.     

Scalable Multicasting: The Core-Assisted Mesh Protocol

Most of the multicast routing protocols for ad hoc networks today are based on shared or source-based trees; however, keeping a routing tree connected for the purpose of data forwarding may lead to a substantial network overhead. A different approach to multicast routing consists of building a shared mesh for each multicast group. In multicast meshes, data packets can be accepted from any router, as opposed to trees where data packets are only accepted from routers with whom a tree branch has been established. The difference among multicast routing protocols based on meshes is in the method used to build these structures. Some mesh-based protocols require the flooding of sender or receiver announcements over the whole network. This paper presents the Core-Assisted Mesh Protocol, which uses meshes for data forwarding, and avoids flooding by generalizing the notion of core-based trees introduced for internet multicasting. Group members form the mesh of a group by sending join requests to a set of cores. Simulation experiments show that meshes can be used effectively as multicast routing structures without the need for flooding control packets.     

Routing with a clue

We suggest a new simple forwarding technique to speed up IP destination address lookup. The technique is a natural extension of IP, requires 5 bits in the IP header (IPv4, 7 in IPv6), and performs IP lookup nearly as fast as IP/Tag switching but with a smaller memory requirement and a much simpler protocol. The basic idea is that each router adds a "clue" to each packet, telling its downstream router where it ended the IP lookup. Since the forwarding tables of neighboring routers are similar, the clue either directly determines the best prefix match for the downstream router, or provides the downstream router with a good point to start its IP lookup. The new scheme thus prevents repeated computations and distributes the lookup process across the routers along the packet path. Each router starts the lookup computation at the point its upstream neighbor has finished. Furthermore, the new scheme is easily assimilated into heterogeneous IP networks, does not require routers coordination, and requires no setup time. Even a flow of one packet enjoys the benefits of the scheme without any additional overhead. The speedup we achieve is about 10 times faster than current standard techniques. In a sense, this paper shows that the current routers employed in the Internet are clue-less; namely, it is possible to speed up the IP lookup by an order of magnitude without any major changes to the existing protocols     

Fast adaptive routing supporting mobile senders in Source Specific Multicast

IP multicast deployment recently progresses, but group services often remain restricted to limited domains and fail to comply with route-optimizing mobility management of the next generation Internet. Source Specific Multicast (SSM) facilitates transparent inter-domain routing and is expected to globally disseminate to many users and services. However, mobility support for Source Specific Multicast is still known to be a major open problem. In this paper, we propose the Enhanced Tree Morphing (ETM) protocol for extending SSM routing to mobile multicast sources. The scheme dynamically adapts SSM forwarding states to sender mobility, and transforms (morphs) source specific distribution trees into new, optimal trees rooted at a relocated source. ETM is simple, robust and secure, while it admits superior performance in packet forwarding at a low signaling overhead. Extensive evaluations based on a full protocol implementation, and simulations based on real-world topology data are performed, granting full insight into the properties of packet loss and delay stretch, protocol convergence times and router state evolution during single and rapidly repeated handovers. In a constant bit rate scenario, an ETM source handover typically leads to a slightly increasing delay of the first data packet, only. When operating on realistic network topologies, the protocol uniformly converges within less than 50 ms, thereby sustaining robustness under rapid source movement at all speeds common to our mobile world. Further optimizations are identified for FMIPv6 and for multihomed nodes.     

A Domain-Based Routing Protocol for SSM Source Mobility in Mobile IPv6 Networks

In Mobile IP, the signaling traffic overhead will be too high since the new Care-of-Address (CoA) of the mobile node (MN) is registered all the way with the home agent (HA) whenever the MN has moved into a new foreign network. To complement Mobile IP in better handling local movement, several IP micro protocols have been proposed. These protocols introduce a hierarchical mobility management scheme, which divides the mobility into micro mobility and macro mobility according to whether the host's movement is intra-domain or inter-domain. Thus, the requirements on performance and flexibility are achieved, especially for frequently moving hosts. This paper introduces a routing protocol for multicast source mobility on the basis of the hierarchical mobile management scheme, which provides a unified global architecture for both uni- and multicast routing in mobile networks. The implementation of multicast services adopts an improved SSM (Source Specific Multicast) model, which combines the advantages of the existing protocols in scalability and mobility transparency. Simulation results show that the proposed protocol has better performance than the existing routing protocols for SSM source mobility.     

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     

Hierarchical geographic multicast routing for wireless sensor networks

Wireless sensor networks comprise typically dense deployments of large networks of small wireless capable sensor devices. In such networks, multicast is a fundamental routing service for efficient data dissemination required for activities such as code updates, task assignment and targeted queries. In particular, efficient multicast for sensor networks is critical due to the limited energy availability in such networks. Multicast protocols that exploit location information available from GPS or localization algorithms are more efficient and robust than other stateful protocols as they avoid the difficulty of maintaining distributed state (multicast tree). Since localization is typically already required for sensing applications, this location information can simply be reused for optimizing multicast performance at no extra cost. Recently, two protocols were proposed to optimize two orthogonal aspects of location-based multicast protocols: GMR (Sanchez et al. GMR: Geographic multicast routing for wireless sensor networks. In Proceedings of the IEEE SECON, 2006) improves the forwarding efficiency by exploiting the wireless multicast advantage but it suffers from scalability issues when dealing with large sensor networks. On the other hand, HRPM (Das et al. Distributed hashing for scalable multicast in wireless ad hoc networks. IEEE TPDS 47(4):445–487, 2007) reduces the encoding overhead by constructing a hierarchy at virtually no maintenance cost via the use of geographic hashing but it is energy-inefficient due to inefficacies in forwarding data packets. In this paper, we present HGMR (hierarchical geographic multicast routing), a new location-based multicast protocol that seamlessly incorporates the key design concepts of GMR and HRPM and optimizes them for wireless sensor networks by providing both forwarding efficiency (energy efficiency) as well as scalability to large networks. Our simulation studies show that: (i) In an ideal environment, HGMR incurs a number of transmissions either very close to or lower than GMR, and, at the same time, an encoding overhead very close to HRPM, as the group size or the network size increases. (ii) In a realistic environment, HGMR, like HRPM, achieves a Packet Delivery Ratio (PDR) that is close to perfect and much higher than GMR. Further, HGMR has the lowest packet delivery latency among the three protocols, while incurring much fewer packet transmissions than HRPM. (iii) HGMR is equally efficient with both uniform and non-uniform group member distributions.     

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.     

Mapper:一种基于组播的Peer-to-Peer文件 匿名访问协议

Peer-to-Peer(P2P)文件系统的一个基本问题是如何在保护节点隐私的基础上为数据访问提供高效服务.Mapper将IP组播技术和多级代理转发技术相结合,解决了P2P文件访问的相互匿名问题.协议还通过MRFC算法将组成员筛选和缓存位置选择有机统一,在减少组播开销的同时保证了文件布局对用户访问模式的动态自适应性.实验表明,Mapper能有效缓解网络负载,提高数据的易获取性,具有良好的伸缩性和自适应性.     

Explicit Multicasting for Mobile Ad Hoc Networks

In this paper we propose an explicit multicast routing protocol for mobile ad hoc networks (MANETs). Explicit multicasting differs from common approaches by listing destination addresses in data packet headers. Using the explicit destination information, the multicast routing protocol can avoid the overhead of employing its own route construction and maintenance mechanisms by taking advantage of unicast routing table. Our protocol – termed Differential Destination Multicast (DDM) – is an explicit multicast routing protocol specifically designed for MANET environment. Unlike other MANET multicasting protocols, instead of distributing membership control throughout the network, DDM concentrates this authority at the data sources (i.e. senders) thereby giving sources knowledge of group membership. In addition, differentially-encoded, variable-length destination headers are inserted in data packets which are used in combination with unicast routing tables to forward multicast packets towards multicast receivers. Instead of requiring that multicast forwarding state to be stored in all participating nodes, this approach also provides the option of stateless multicasting. Each node independently has the choice of caching forwarding state or having its upstream neighbor to insert this state into self-routed data packets, or some combination thereof. The protocol is best suited for use with small multicast groups operating in dynamic MANET environment.