Computing path-tables of quickest paths under different routing mechanisms

Several recent transport methods employ routing at a level such as the datagram, TCP stream, or application level in order to address quality of service in wide-area networks. The quickest path problem deals with the transmission of a message from a source to a destination with the minimum end-to-end delay over a network with delay and bandwidth constraints on the links. The minimum end-to-end delay path depends on the routing mechanism used for transport in addition to the message size and the link bandwidths and delays. We present algorithms for computing the path-table that specifies the minimum end-to-end delay path as a function of message size for six routing modes reflecting mechanisms such as circuit switching, Internet Protocol, and their combinations. These algorithms have polynomial time complexity in some cases, and in others achieve polynomial time complexity when the set of link bandwidths is suitably bounded.