On the computation of fast data transmissions in networks with capacities and delays

We examine the problem of transmitting in minimum time a given amount of data between a source and a destination in a network with flnite channel capacities and non{zero propagation delays. In the absence of delays, the problem has been shown to be solvable in polyno- mial time. In this paper, we show that the general problem is NP{hard. In addition, we examine transmissions along a single path, called the quickest path, and present algorithms for general and sparse networks that outperform previous approaches. The flrst dynamic algorithm for the quickest path problem is also given.