## Abstract

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^{2} + 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.

Original language | English |
---|---|

Pages (from-to) | 253-257 |

Number of pages | 5 |

Journal | Computer Systems Science and Engineering |

Volume | 17 |

Issue number | 4-5 |

State | Published - Jul 2002 |

## Keywords

- End-to-end delay
- Path-table
- Quickest path problem