On algorithms for minimum-cost quickest paths with multiple delay-bounds

The quickest path problem deals with the transmission of a message of size σ from a source to a destination with the minimum end-to-end delay over a network with bandwidth and delay constraints on the links. We adapt properties of the quickest path to solve the delay-bounded minimum-cost (DBMC) path problem that is known to be the NP-hard. In this paper, we propose two efficient and simple algorithms, DBMCQP and DBMCQRT. DBMCQP computes a DBMC quickest path for a given message size σ with O(rm + rnlogn), and DBMCQRT construct DBMC routing tables taking into account multiple delay-bounds for any size of message with O(kr2), where r, n, m, and k are the number of distinct link-bandwidths, nodes, links of the network, and the number of delay-bounds, respectively.