Creating and sharing knowledge for telecommunications

A Theory for the Connectivity Discovered by Routing Protocols

Sobrinho, J. L. S. ; Quelhas, T.

IEEE/ACM Transactions on Networking Vol. 20, Nº 3, pp. 677 - 689, June, 2012.

ISSN (print): 1063-6692
ISSN (online):

Journal Impact Factor: 2,576 (in 2008)

Digital Object Identifier: 10.1109/TNET.2011.2165080

Download Full text PDF ( 2 MBs)

Route-vector protocols, such as the Border Gateway Protocol (BGP), have nodes elect and exchange routes in order to discover paths over which to send traffic. We ask the following: What is the minimum number of links whose failure prevents a route-vector protocol from finding such paths? The answer is not obvious because routing policies prohibit some paths from carrying traffic,
and because, on top of that, a route-vector protocol may hide paths the routing policies would allow.

We develop an algebraic theory to address the above and related questions. In particular,
we characterize a broad class of routing policies for which we can compute in polynomial-time
the minimum number of links whose failure leaves
a route-vector protocol without a communication path from one given node to another.

The theory is applied to a publicly available description of the
Internet topology to quantify how much of its intrinsic connectivity is
lost due to the traditional customer-provider, peer-peer routing policies and how much can be regained
with simple alternative policies.