Toward Valley-Free Inter-domain Routing

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.