Experimental Study on Diversity and Novelty of Interdomain Paths

Exploiting Internet path diversity to en- hance communication reliability and performance is an im- portant research field. Although the Internet has enor- mous physical diversity in the underlaying infrastructure, inter-domain routing protocol and routing policies highly limit this path diversity in the Internet. In order to inves- tigate the effects of routing policies on inter-domain paths, we develop a measurement study framework to character- ize and classify inter-domain paths. In this framework, we define the concepts of the transit strategy and the valley and valley-free paths, and give a formal model of strategy- labeled inter-domain paths. Then we develop three asso- ciated algorithms: Topology extraction (TE), Multi-path computation algorithm (MCA) and Classification of path pattern (CPP), which are used to compute and classify inter-domain paths. Experimental results show two useful and important observations that valley paths have aver- agely more than 73% in all inter-domain paths, and Class 1 paths account for 64.6% of all valley paths. The observa- tions may guide the design of inter-domain routing proto- col, especially the design of multi-path routing, to achieve higher performance and reliability.