Quantifying Path Exploration in the Internet

Abstract — The Internet’s BGP routing protocol is known to suffer from path exploration and slow convergence. This paper presents the first systematic measurement study that quantifies the extent and severity of path exploration and slow convergence. Our results show that origin ASes at different tier levels experience slow convergence with different degrees, with tier-1 ASes seeing little path exploration but lower tier ASes experiencing significantly more. Roughly 17.63 % of updates belong to events during which there is no AS path change, 37.85 % are updates belonging to events during which there are path changes but the starting path and the ending path are the same, and 44.51% are updates belonging to events that lead to path changes. For those path change events, less than 30 % are route failures or route announcement events. 96 % of the Path Change events are shorter than 3 minutes and route failure (Tdown) events suffer the worst path exploration and slow converence. Deploying routing convergence improvement mechanisms such as [19] we could potentially reduce the number of Tdown updates by up to 85 % and all Path Change updates up to 63%. Unlike previous conjectures, our results show that route fail-over (Tlong) events have short duration in general that are comparable to events that end in more preferred routes (Tup and Tshort). Overall, the results illustrate how, why, and where path exploration and slow convergence problems occur in the Internet. I