General quickest paths and path-tables

We consider the transmission of a message of size r from a source to adestination over a computer network with n nodes and m links. There are three sources of delays for a message transmitted over the network: (a) propagation delays along the links, (b) delays due to the bandwidth availability on the links, and (c) queuing delays at the intermediate nodes. If the delay in (b) is a non-increasing function of the bandwidth, we propose an O(m² + mn log n) time algorithm to compute a path with the minimum end-to-end delay for a given message. For the general case, we show the size of path-table to be infinite. Under the condition that the delay curves are continuous and intersect with each other in no more than τ connected regions, we show that path-table size has as an upper bound the Davenport-Schinzelnumber λ_s(ρ*), where ρ* is the dominant path number of G. We also discuss special cases where the path-table is of significantly smaller size.