The Internet's unexploited path diversity

The connectivity of the Internet at the Autonomous System level is influenced by the network operator policies implemented. These in turn impose a direction to the announcement of address advertisements and, consequently, to the paths that can be used to reach back such destinations. We propose to use directed graphs to properly represent how destinations propagate through the Internet and the number of arc-disjoint paths to quantify this network's path diversity. Moreover, in order to understand the effects that policies have on the connectivity of the Internet, numerical analyses of the resulting directed graphs were conducted. Results demonstrate that, even after policies have been applied, there is still path diversity which the Border Gateway Protocol cannot currently exploit.

Chain routing:a new routing framework for the Internet based on complete orders

A new framework to perform routing at the autonomous system (AS) level is proposed here. This mechanism, called chain routing framework (CRF), uses complete orders as its main topological unit. Since complete orders are acyclic digraphs that possess a known topology, it is possible to use these acyclic structures to route consistently packets between a group of ASs. The adoption of complete orders also allows easy identification and avoidance of persistent route oscillations, eliminates the possibility of developing transient loops in paths and provides a structure that facilitates the implementation of traffic engineering. Moreover, by combining CRF with other mechanisms that implement complete orders in time, the authors propose that it is possible to design a new routing protocol, which can be more reliable and stable than the border gateway protocol. © 2011 The Institution of Engineering and Technology.