Multicast routing in computer networks
Jose Joaquin Garcia-Luna-Aceves, Mehrdad Parsa · 1998
Multicast routing is a network-layer function that constructs paths along which data packets from a source are distributed to reach many, but not all, destinations in a communication network. Multicast routing sends a single copy of a data packet simultaneously to multiple receivers over a communication link that is shared by the paths to the receivers. The sharing of links in the collection of the paths to receivers implicitly defines a tree used to distribute multicast packets. This thesis addresses three aspects of multicast routing in computer networks. We first consider centralized algorithms for finding low-cost multicast trees under end-to-end delay constraints, where each link in the network has both a cost and a delay associated with it in order to capture distinct properties of the link. The bounded shortest multicast algorithm (BSMA) is presented for constructing minimum-cost multicast trees with delay constraints. BSMA can handle asymmetric link characteristics and variable real-valued delay bounds on destinations, and minimizes the total cost of a multicast routing tree. Instead of the single-pass tree construction approach used in most previous heuristics, the new algorithm is based on a feasible-search optimization strategy that starts with the minimum-delay multicast tree and monotonically decreases the cost by iterative improvement of the delay-bounded multicast tree. The expected time complexity of BSMA is analyzed, and simulation results are provided showing that BSMA can achieve near-optimal cost reduction with fast execution. We next consider distributed algorithms for constructing group-shared and shortest-path multicast trees. We present and verify a new multicast routing protocol, called the multicast internet protocol (MIP), which offers a simple and flexible approach based on diffusing computations to construct both group-shared and shortest-paths multicast trees. MIP can be sender-initiated or receiver-initiated or both in constructing a multicast tree. MIP is independent of the underlying unicast routing algorithms used. MIP is robust and adapts under dynamic network conditions (topology or link cost changes) to maintain loop-free multicast routing. Under stable network conditions, MIP has no maintenance or control message overhead. We prove that MIP is loop-free at every instant, and that it is deadlock-free and obtains multicast routing trees within a finite time after the occurrence of an arbitrary sequence of topology or unicast changes. Finally, we consider the problem of distributed construction of a low-cost multicast tree with end-to-end path constraints that represent quality-of-service requirements. We present a new distributed algorithm, called distributed constrained multicast algorithm (DCMA), to construct and maintain minimum-cost multicast trees with QoS guarantees. DCMA operates efficiently in an asynchronous communication network by using diffusing computations. DCMA conserves network resources by minimizing the unnecessary participation of all the routers in the network during the construction and maintenance of a multicast tree; therefore, DCMA is scalable to larger networks. DCMA permits heterogeneity in the network by allowing different QoS parameters to be specified by the receivers. DCMA handles the asymmetric nature of link parameters, such as delay, by setting up the multicast tree such that the data flow is over the minimum delay path from the source. In addition, DCMA is robust to group membership changes, i.e., joins and leaves, and network dynamics, such as router failures and recoveries. The worst-case cost performance of DCMA is comparable to other proposed heuristics for the static directed Steiner problem.