Portal de Periódicos da CAPES

A Theory for the Connectivity Discovered by Routing Protocols

2011; Institute of Electrical and Electronics Engineers; Volume: 20; Issue: 3 Linguagem: Inglês

10.1109/tnet.2011.2165080

1558-2566

J.L. Sobrinho, Tiago Quelhas,

Cooperative Communication and Network Coding

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.