Implications of Autonomy for the Expressiveness of Policy Routing

26 December 2007

journal article
Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Networking

Vol. 15 (6) , 1266-1279
https://doi.org/10.1109/tnet.2007.896531

Abstract

Thousands of competing autonomous systems must cooperate with each other to provide global Internet connectivity. Each autonomous system (AS) encodes various economic, business, and performance decisions in its routing policy. The current interdomain routing system enables each AS to express policy using rankings that determine how each router in the AS chooses among different routes to a destination, and filters that determine which routes are hidden from each neighboring AS. Because the Internet is composed of many independent, competing networks, the interdomain routing system should provide autonomy, allowing network operators to set their rankings independently, and to have no constraints on allowed filters. This paper studies routing protocol stability under these conditions. We first demonstrate that ldquonext-hop rankings,rdquo commonly used in practice, may not ensure routing stability. We then prove that, when providers can set rankings and filters autonomously, guaranteeing that the routing system will converge to a stable path assignment imposes strong restrictions on the rankings ASes are allowed to choose. We discuss the implications of these results for the future of interdomain routing.

Keywords

This publication has 17 references indexed in Scilit:

Metarouting
ACM SIGCOMM Computer Communication Review, 2005
Robustness of class-based path-vector systems
Published by Institute of Electrical and Electronics Engineers (IEEE) ,2004
Guidelines for interdomain traffic engineering
ACM SIGCOMM Computer Communication Review, 2003
Maximizable routing metrics
IEEE/ACM Transactions on Networking, 2003
Design principles of policy languages for path vector protocols
Published by Association for Computing Machinery (ACM) ,2003
A safe path vector protocol
Published by Institute of Electrical and Electronics Engineers (IEEE) ,2002
The stable paths problem and interdomain routing
IEEE/ACM Transactions on Networking, 2002
On the correctness of IBGP configuration
Published by Association for Computing Machinery (ACM) ,2002
An architecture for stable, analyzable Internet routing
IEEE Network, 1999
Route servers for inter-domain routing
Computer Networks and ISDN Systems, 1998