On selection of candidate paths for proportional routing

Srihari Nelakuditi, Zhi Li Zhang, David H.C. Du

Research output: Contribution to journalArticlepeer-review

45 Scopus citations

Abstract

QoS routing involves selection of paths for flows based on the knowledge at network nodes about the availability of resources along paths, and the QoS requirements of flows. Several QoS routing schemes have been proposed that differ in the way they gather information about the network state and select paths using this information. Most of these schemes can be categorized as best path routing where a source node selects the "best" path for each incoming flow based on its current view of the global network state. It has been shown that best path routing schemes require frequent exchange of network state, imposing both communication overhead on the network and processing overheads on the core routers. On the other hand, proportional routing schemes proportion incoming flows among a set of candidate paths. Two key questions that arise under proportional routing are how to select candidate paths and how to proportion flows among candidate paths. We propose a scheme that selects a few widest disjoint paths as candidates and equalizes the blocking probabilities of the candidate paths. We show that our proportional routing approach yields higher throughput with lower overhead than best path routing approach. Furthermore, we present a method for aggregating the state of an area and extend the proportional routing approach to provide hierarchical routing across multiple areas in a large network.

Original languageEnglish (US)
Pages (from-to)79-102
Number of pages24
JournalComputer Networks
Volume44
Issue number1
DOIs
StatePublished - Jan 15 2004

Bibliographical note

Funding Information:
This work is partly supported by National Science Foundation Grants CAREER Award ANI-9734428, ANI-0073819, and ITR ANI-0085824. Any opinions, findings, and conclusions or recommendations expressed in this paper are those of the authors and do not necessarily reflect the views of the National Science Foundation.

Funding Information:
Zhi-Li Zhang received the B.S. degree in Computer Science from Nanjing University, China, in 1986 and his M.S. and Ph.D. degrees in Computer Science from the University of Massachusetts in 1992 and 1997. In 1997 he joined the Computer Science and Engineering faculty at the University of Minnesota, where he is currently an Associate Professor. From 1987 to 1990, he conducted research in Computer Science Department at Aarhus University, Denmark, under a fellowship from the Chinese National Committee for Education. His research interests are in computer networks and multimedia systems. He received the National Science Foundation CAREER Award in 1997. He has also awarded the prestigious McKnight Land-Grant Professorship at the University of Minnesota. He is a co-recipient of an ACM SIGMETRICS best paper award. He currently serves on the Editorial Boards of IEEE/ACM Transactions on Networking and Computer Networks. He is a member of IEEE, ACM and INFORMS Telecommunication Section.

Keywords

  • Proportional routing
  • QoS routing
  • Widest disjoint paths

Fingerprint

Dive into the research topics of 'On selection of candidate paths for proportional routing'. Together they form a unique fingerprint.

Cite this