• DocumentCode
    858710
  • Title

    Network routing capacity

  • Author

    Cannons, Jillian ; Dougherty, Randall ; Freiling, Chris ; Zeger, Kenneth

  • Author_Institution
    Dept. of Electr. & Comput. Eng., Univ. of California, La Jolla, CA
  • Volume
    52
  • Issue
    3
  • fYear
    2006
  • fDate
    3/1/2006 12:00:00 AM
  • Firstpage
    777
  • Lastpage
    788
  • Abstract
    We define the routing capacity of a network to be the supremum of all possible fractional message throughputs achievable by routing. We prove that the routing capacity of every network is achievable and rational, we present an algorithm for its computation, and we prove that every rational number in (0, 1] is the routing capacity of some solvable network. We also determine the routing capacity for various example networks. Finally, we discuss the extension of routing capacity to fractional coding solutions and show that the coding capacity of a network is independent of the alphabet used
  • Keywords
    encoding; telecommunication network routing; telecommunication switching; fractional coding solution; network routing capacity; switching; Communication networks; Communication switching; Computer networks; Galois fields; Instruction sets; Linearity; Network coding; Routing; Throughput; Vectors; Network coding; capacity; flow; switching;
  • fLanguage
    English
  • Journal_Title
    Information Theory, IEEE Transactions on
  • Publisher
    ieee
  • ISSN
    0018-9448
  • Type

    jour

  • DOI
    10.1109/TIT.2005.864474
  • Filename
    1603753