We study the NP-hard delay-constrained least cost (DCLC) path problem. A solution to this problem is needed to provide real-time communication service to connection-oriented applications, such as video and voice. We propose a simple, distributed heuristic solution, called the delay-constrained unicast routing (DCUR) algorithm, DCUR requires limited network state information to be kept at each node: a cost vector and a delay vector. We prove DCUR's correctness by showing that it is always capable of constructing a loop-free delay-constrained path within finite time, if such a path exists. The worst case message complexity of DCUR is O(|V|/sup 2/) messages, where |V| is the number of nodes. However, simulation results show that, on the average, DCUR requires much fewer messages. Therefore, DCUR scales well to large networks. We also use simulation to compare DCUR to the optimal algorithm, and to the least delay path algorithm. Our results show that DCUR's path costs are within 10% of those of the optimal solution.

We study the NP-hard delay-constrained least-cost path problem, and propose a simple, distributed heuristic solution: the delay-constrained unicast routing (DCUR) algorithm. The DCUR requires limited network state information to be kept at each node: a cost vector and a delay vector. We prove the DCUR's correctness by showing that it is always capable of constructing a loop-free delay-constrained path within finite time, if such a path exists. The worst case message complexity of the DCUR is O(|V|/sup 3/) messages, where |V| is the number of nodes. However simulation results show that, on average, the DCUR requires much fewer messages. Therefore, the DCUR scales well to large networks. We also use simulation to compare the DCUR to the optimal algorithm, and to the least-delay path algorithm. Our results show that the DCUR's path costs are within 10% from those of the optimal solution.

We formulate the problem of constructing broadcast trees for real-time traffic with delay constraints in networks with asymmetric link loads as a delay-constrained minimum spanning tree (DCMST) problem in directed networks. Then, we prove that this problem is NP-complete, and we propose an efficient heuristic to solve the problem based on Prim's algorithm for the unconstrained minimum spanning tree problem. Simulation results under realistic networking conditions show that our heuristic performance is close to optimal. Delay-constrained minimum Steiner tree heuristics can be used to solve the DCMST problem. Simulation results indicate that the fastest delay-constrained minimum Steiner tree heuristic, DMCT is not as efficient as the heuristic we propose, while the most efficient delay-constrained minimum Steiner tree heuristic, BSMA, is much slower than our proposed heuristic and does not construct delay-constrained broadcast trees of lower cost.

Multicast (MC) routing algorithms capable of satisfying the quality of service (QoS) requirements of real-time applications will be essential for future high-speed networks. We compare the performance of all of the important MC routing algorithms when applied to networks with asymmetric link loads. Each algorithm is judged based on the quality of the MC trees it generates and its efficiency in managing the network resources. Simulation results over random networks show that unconstrained algorithms are not capable of fulfilling the QoS requirements of real-time applications in wide-area networks. Simulations also reveal that one of the unconstrained algorithms, reverse path multicasting (RPM), is quite inefficient when applied to asymmetric networks. We study how combining routing with resource reservation and admission control improves the RPM's efficiency in managing the network resources. The performance of one semiconstrained heuristic, MSC, three constrained Steiner tree (CST) heuristics, Kompella, Pasquale, and Polyzos (1992), constrained adaptive ordering (CAO), and bounded shortest multicast algorithm (BSMA), and one constrained shortest path tree (CSPT) heuristic, the constrained Dijkstra heuristic (CDKS) are also studied. Simulations show that the semiconstrained and constrained heuristics are capable of successfully constructing MC trees which satisfy the QoS requirements of real-time traffic. However, the cost performance of the heuristics varies. The BSMA's MC trees are lower in cost than all other constrained heuristics. Finally, we compare the execution times of all algorithms, unconstrained, semiconstrained, and constrained.