Toward valley-free inter-domain routing

Sophie Y. Qiu, Patrick D. McDaniel, Fabian Monrose

Research output: Chapter in Book/Report/Conference proceedingConference contribution

33 Scopus citations


ASes in inter-domain routing receive little information about the quality of the routes they receive. This lack of information can lead to inefficient and even incorrect routing. In this paper, we quantitatively characterize BGP announcements that violate the so-called valley-free property-an indicator that universal best practices are not being preserved in the propagation of routes. Our analysis indicates that valley announcements are more pervasive than expected. Approximately ten thousand valley announcements appear every day and involve a substantial number of prefixes. 11 % of provider ASes propagate valley announcements, with a majority of violations happening at intermediate providers. We find that large surges of violating announcements can be attributed to transient configuration errors. We further propose a dynamic mechanism that provides route propagation information as transitive attributes of BGP. This information implicitly reflects the policies of the ASes along the path, without revealing the relationship of each AS pair. BGP-speaking routers use this information to identify (and presumably avoid) routes that violate the valley-free property.

Original languageEnglish (US)
Title of host publication2007 IEEE International Conference on Communications, ICC'07
Number of pages8
StatePublished - 2007
Event2007 IEEE International Conference on Communications, ICC'07 - Glasgow, Scotland, United Kingdom
Duration: Jun 24 2007Jun 28 2007

Publication series

NameIEEE International Conference on Communications
ISSN (Print)0536-1486


Other2007 IEEE International Conference on Communications, ICC'07
Country/TerritoryUnited Kingdom
CityGlasgow, Scotland

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Electrical and Electronic Engineering


Dive into the research topics of 'Toward valley-free inter-domain routing'. Together they form a unique fingerprint.

Cite this