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.