DocumentCode :
1317261
Title :
A Theory for the Connectivity Discovered by Routing Protocols
Author :
Sobrinho, João Luís ; Quelhas, Tiago
Author_Institution :
Inst. de Telecomun., Inst. Super. Tecnico, Lisbon, Portugal
Volume :
20
Issue :
3
fYear :
2012
fDate :
6/1/2012 12:00:00 AM
Firstpage :
677
Lastpage :
689
Abstract :
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.
Keywords :
Internet; algebra; computational complexity; peer-to-peer computing; routing protocols; telecommunication network topology; BGP; Internet topology; algebraic theory; border gateway protocol; customer-provider; intrinsic connectivity; peer-peer routing policies; polynomial time; route-vector protocols; Internet; Logic gates; Peer to peer computing; Polynomials; Routing; Routing protocols; Algebraic routing; Internet routing; Menger´s theorems; connectivity; routing; routing policies; routing protocols; theory of routing;
fLanguage :
English
Journal_Title :
Networking, IEEE/ACM Transactions on
Publisher :
ieee
ISSN :
1063-6692
Type :
jour
DOI :
10.1109/TNET.2011.2165080
Filename :
6015505
Link To Document :
بازگشت