Computing Path Tables for Quickest Multipaths In Computer Networks Metadata

Metadata describes a digital item, providing (if known) such information as creator, publisher, contents, size, relationship to other resources, and more. Metadata may also contain "preservation" components that help us to maintain the integrity of digital files over time.


  • Main Title Computing Path Tables for Quickest Multipaths In Computer Networks


  • Author: Grimmell, W.C.
    Creator Type: Personal


  • Sponsor: United States. Department of Energy.
    Contributor Type: Organization


  • Name: Oak Ridge National Laboratory
    Place of Publication: [Tennessee]
    Additional Info: ORNL


  • Creation: 2004-12-21


  • English


  • Content Description: We consider the transmission of a message from a source node to a terminal node in a network with n nodes and m links where the message is divided into parts and each part is transmitted over a different path in a set of paths from the source node to the terminal node. Here each link is characterized by a bandwidth and delay. The set of paths together with their transmission rates used for the message is referred to as a multipath. We present two algorithms that produce a minimum-end-to-end message delay multipath path table that, for every message length, specifies a multipath that will achieve the minimum end-to-end delay. The algorithms also generate a function that maps the minimum end-to-end message delay to the message length. The time complexities of the algorithms are O(n{sup 2}((n{sup 2}/logn) + m)min(D{sub max}, C{sub max})) and O(nm(C{sub max} + nmin(D{sub max}, C{sub max}))) when the link delays and bandwidths are non-negative integers. Here D{sub max} and C{sub max} are respectively the maximum link delay and maximum link bandwidth and C{sub max} and D{sub max} are greater than zero.


  • Keyword: Time Dependence
  • Keyword: Computer Networks
  • Keyword: Algorithms
  • Keyword: Data Transmission
  • STI Subject Categories: 99 General And Miscellaneous//Mathematics, Computing, And Information Science


  • Name: Office of Scientific & Technical Information Technical Reports
    Code: OSTI


  • Name: UNT Libraries Government Documents Department
    Code: UNTGD

Resource Type

  • Report


  • Text


  • Report No.: ORNL/TM-2004/3
  • Grant Number: DE-AC05-00OR22725
  • DOI: 10.2172/885861
  • Office of Scientific & Technical Information Report Number: 885861
  • Archival Resource Key: ark:/67531/metadc892224