The Internet topological connectivity becomes denser over time. However the de facto routing protocol of the global Internet, BGP, lets each BGP router select and propagate only a single best path to each destination network. This leads to a common concern that the rich connectivity is not fully utilized and the lack of alternative paths can reduce a network's robustness to failures as well as flexibility in traffic engineering, and can lead to slow adaptation to topological changes. Yet there have been few quantitative measurement studies on path diversity in today's operational Internet. In this paper we use iBGP routing data collected from a Tier1 ISP, ISPA, over a 2-year time period to quantify BGP next-hop diversity for all destinations. Our results show that ISPA reaches the majority of prefixes through multiple next-hop routers. We use several case studies of prefixes with different diversity degrees to identify two major factors that impact the number of observed next-hops: the ISP's path preference and the number of peering routers between large ISPs. This observation provides operational input to the current efforts on augmenting BGP to increase path diversity.
Financed by the National Centre for Research and Development under grant No. SP/I/1/77065/10 by the strategic scientific research and experimental development program:
SYNAT - “Interdisciplinary System for Interactive Scientific and Scientific-Technical Information”.