Authors: Jennifer Rexford and Anees Shaikh Title: Performance Evaluation of Quality-of-Service Routing with Inaccurate Link-State Information Abstract: The migration to integrated backbone networks for voice, data, and multimedia applications introduces new challenges in supporting predictable communication performance. Quality-of-service routing can provide low latency and guaranteed throughput to emerging applications, while also improving network utilization. However, quality-of-service routing requires recent information about network load to compute new routes, which can impose a significant burden on bandwidth and processing resources in the network. We investigate this fundamental tension between network overheads and the quality of the routing decisions in the context of source-directed, link-state routing algorithms. In contrast to previous performance studies that compare different routing algorithms under specific network configurations, we attempt to characterize how stale load information interacts with the underlying network topology, traffic load, and link-state update policies. A broad set of simulation experiments suggests ways to tune the frequency of link-state update messages to strike a careful balance between high accuracy and low complexity. Drawing on these results, we propose several enhancements to routing and signalling policies for high-speed networks.