Valley-free violation in Internet routing — Analysis based on BGP Community data
- 1 June 2012
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 15503607,p. 1193-1197
Abstract
The valley-free rule defines patterns of routing paths that allow the Internet Autonomous Systems (AS) to minimize their routing costs through selective announcement of BGP routes. The valley-free rule has been widely perceived as a universal property of the Internet BGP routing that is only violated due to transient configuration errors. Analysing the valley-free violations is important for a better understanding of BGP behaviour and inter-domain routing. This requires knowledge of the business relationships between ASes. The ground-truth data of AS relationships are not publicly available. Previous algorithms have inferred AS relationships based on the assumption that AS paths should be valley-free. Such inference results are biased and can not provide an objective assessment of the valley-free rule. Instead we extract the AS relationships directly from routing polices encoded in the BGP Community attribute. We are able to extract the business relationship of more than 30% of AS links based on BGP data collected from the RouteViews and RIPE RIS repositories in June 2011. We use our inferred AS relationships to analyse the valley-free violations in BGP routing. We reveal that the non valley-free paths are significantly more frequent than previously reported. As many as one fifth of AS paths in IPv6 BGP updates are valley paths. A substantial portion of these valley paths are persistent during the whole month of measurement. These observations strongly indicate that the valley paths are not merely a result of BGP misconfigurations. Instead they are the outcome of complex business relationships and deliberate policies by ASes using distinct unconventional models.Keywords
This publication has 11 references indexed in Scilit:
- Detecting and assessing the hybrid IPv4/IPv6 as relationships2011
- The (In)Completeness of the Observed Internet AS-level StructureIEEE/ACM Transactions on Networking, 2009
- Near-Deterministic Inference of AS Relationships2009
- On BGP communitiesACM SIGCOMM Computer Communication Review, 2008
- Study on Traffic Characteristics of BGP Misconfiguration2008
- AS relationshipsACM SIGCOMM Computer Communication Review, 2007
- On the evaluation of AS relationship inferences2005
- Analyzing BGP policies: methodology and tool2004
- Understanding BGP misconfiguration2002
- On inferring autonomous system relationships in the InternetIEEE/ACM Transactions on Networking, 2001