Evaluating the impact of stale link state on quality-of-service routing

Anees Shaikh, Jennifer L. Rexford, Kang G. Shin

Research output: Contribution to journalArticlepeer-review

152 Scopus citations


Quality-of-service (QoS) routing satisfies application performance requirements and optimizes network resource usage by selecting paths based on connection traffic parameters and link load information. However, distributing link state imposes significant bandwidth and processing overhead on the network. This paper investigates the performance tradeoff between protocol overhead and the quality of the routing decisions in the context of the source-directed link-state routing protocols proposed for IP and ATM networks. We construct a detailed model of QoS routing that parameterizes the path-selection algorithm, link-cost function, and link-state update policy. Through extensive simulation experiments with several network topologies and traffic patterns, we uncover the effects of stale link-state information and random fluctuations in traffic load on the routing and setup overheads. We then investigate how inaccuracy of link-state information interacts with the size and connectivity of the underlying topology. Finally, we show that tuning the coarseness of the link-cost metric to the inaccuracy of underlying link-state information reduces the computational complexity of the path-selection algorithm without significantly degrading performance. This work confirms and extends earlier studies, and offers new insights for designing efficient quality-of-service routing policies in large networks.

Original languageEnglish (US)
Pages (from-to)162-176
Number of pages15
JournalIEEE/ACM Transactions on Networking
Issue number2
StatePublished - Apr 2001

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Science Applications
  • Computer Networks and Communications
  • Electrical and Electronic Engineering


  • Explicit routing
  • Link-state
  • Modeling
  • Quality-of-service
  • Signaling
  • Source-directed routing


Dive into the research topics of 'Evaluating the impact of stale link state on quality-of-service routing'. Together they form a unique fingerprint.

Cite this