Nick Feamster, Ramesh Johari, Hari Balakrishnan
ACM SIGCOMM, Philadelphia, PA, August 2005
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
certain rankings that are 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 essentially requires ASes to rank
routes based on AS-path lengths. We discuss the implications of these
results for the future of interdomain routing.
[PDF (200KB)] [PostScript (394KB)] [Gzipped PostScript (137KB)]
Bibtex Entry:
@inproceedings{feamster2005implications,
author = "Nick Feamster and Ramesh Johari and Hari Balakrishnan",
title = "{Implications of Autonomy for the Expressiveness of Policy Routing}",
booktitle = {ACM SIGCOMM},
year = {2005},
month = {August},
address = {Philadelphia, PA}
}