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
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.