Mulitcast routing for real-time communication in wide-area high-speed networks

This thesis focuses on the algorithmic and design issues related to the development of multicast trees between a source node and a group of destination nodes.; The first part of this work considers single-cost communication networks and focuses on developing a multicast tree to deliver data from a source to a set of destinations. The objective is to reduce the cost of the multicast tree. Two heuristics, Normalized Average Distance Heuristic (NADH) and Shared Average Distance Heuristic (SADH), are proposed. Both heuristics use a new centrality measure to incrementally build the multicast tree. NADH avoids biases toward the closest tree and extends the centrality to include more subtrees. SADH finds the edge with the smallest centrality measure and uses the selected edge to combine the two closest subtrees to produce a new subtree. The simulation results show, on average, NADH outperforms other known heuristics in dense graphs, whereas SADH outperforms these heuristics for all types of graphs.; The second part of this work considers dual-cost communication networks and focuses on developing low-cost, delay-bounded multicast trees. The offline case, where the multicast group is semi-permanent, as well as the online case, where the multicast group is dynamic, are considered. Three new heuristics are proposed for the offline problem. The heuristics decouple the cost optimization from bounding the delay by first building a low-cost tree and then handling any delay violations that may occur in the tree. The first two heuristics, delay-constrained, Low-cost, Inexpensive, Multicasting (SLIM) and SLIM+, use the least-cost path between-the multicast nodes to incrementally build the multicast tree. Their complexity is O(n3), where n is the number of nodes in the network. The third heuristic uses the $k$-shortest-path algorithm to find the set of low-cost, delay-bounded paths. Its time complexity is O($k$ n3 log(n )), where $k$ is a user-defined parameter. Our simulation results show that K-SLIM on average outperforms other well-known heuristics. The results also show that SLIM+ produces low-cost trees with average cost close to the average cost of trees produced by K-SLIM but with much lower processing overhead.; To address the online problem, a new Simple and Efficient Low-cost Delay-bounded Online Multicasting (SELDOM) heuristic is proposed. SELDOM is particularly tailored to networks in which group membership changes frequently. SELDOM supports two modes: non-rearrangeable and rearrangeable. The scheme handles join requests dynamically by determining the least-cost path which satisfies the required delaybounds to which the new group member is to be attached. To handle a leave request, the scheme seeks to limit the number of rearrangements required in order to reduce the disturbance such a request may cause to current group members. The worst case time complexity of SELDOM is O(n2). An important research contribution of this work shows that if any non-rearrangeable multicast heuristics use a path other than the least-delay path to add a node to the multicast tree, then the multicast tree can have cycles or nodes with two incoming paths. (Abstract shortened by UMI.)...