Evaluating the impact of stale link state on quality-of-service routing
- 1 April 2001
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Networking
- Vol. 9 (2) , 162-176
- https://doi.org/10.1109/90.917073
Abstract
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.Keywords
This publication has 22 references indexed in Scilit:
- Dynamic routing of real-time virtual circuitsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- On path selection for traffic with bandwidth guaranteesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Packing and least-loaded based routing in multi-rate loss networksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- QoS routing mechanisms and OSPF extensionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Load-sensitive routing of long-lived IP flowsACM SIGCOMM Computer Communication Review, 1999
- Quality of service based routingACM SIGCOMM Computer Communication Review, 1998
- Algorithm for efficient generation of link-state updates in ATM networksComputer Networks and ISDN Systems, 1997
- On-line routing for permanent virtual circuitsComputer Communications, 1996
- Routing and admission control algorithms for multimedia trafficComputer Communications, 1995
- The revised ARPANET routing metricPublished by Association for Computing Machinery (ACM) ,1989