Quality of service routing on wide area networks.

Abstract

Moore [20] introduced the quickest path problem and it has been studied extensively in recent times. The quickest path problem is to determine a routing path to minimize end-to-end delay from the source to the destination node taking into account message size, and propagation delay and bandwidth on the links of the network. Thus the quickest path is a path with minimum end-to-end delay time required to send sigma units of message from a source node to the destination node.

The main theme of this dissertation is to investigate unicast and multicast routing algorithms in wide area networks. Towards this end, first we present a unifying quickest path algorithm for different message transfer modes at intermediate nodes. The source to destination path varies with message sizes. Quickest path algorithms build a table called the Path-Table that when searched with message size gives the minimum end-to-end delay path for that message size. Our second result deals with efficient construction of the Path-Table when a link or path bandwidth changes, where path bandwidth is defined as the minimum of the bandwidths on the links of the path. Third, we present efficient algorithms for all-to-all quickest path problems in the presence of unreliable links in the network. By assigning probability of link failure to each link we can cast two problems namely, quickest most reliable path and most reliable quickest path.

Routing is the process of sending a message from a source node to the destination node and the routing algorithm is a method to determine links that a message should be transmitted in order to reach the destination. The routing algorithm can be classified into the following three categories: unicast, multicast, and broadcast. Unicast involves sending a message from a given source to a destination; multicasting is a mechanism to send a message from a given source to a chosen set of destinations; broadcasting is sending a message from a given source to all the nodes in the network. Clearly, unicast and broadcast are special cases of multicast. The path selected by a routing algorithm depends on the application's Quality-of-Service (QoS) demands such as, end-to-end delay time, cost, delay jitter, and other factors.

Our fourth result deals with multicast routing in wide area networks. We have developed several heuristics for the construction of a multicast tree that minimizes end-to-end delay time taking into account message size, and propagation delay and bandwidths on links. We consider different modes of message transfers at intermediate nodes and for each type of intermediate node architecture we present heuristics for the multicast tree construction. The heuristics are simulated on large networks that are generated using different network generation models including Waxman I and II, Locality, and Transit-Stub. Our heuristics are shown to outperform existing heuristics that are based on shortest path and minimum spanning tree for multicast tree construction. Finally, we introduce a novel heuristic for the construction of a multicast tree with minimum cost in Internet like topologies. Our algorithm on directed asymmetric networks is shown to have a performance gain in terms of tree costs over existing algorithms.