Tier-2 reachability and multihoming

Thu Mar 24 08:25:38 UTC 2005

G Pavan Kumar wrote:

>         I have been working on characterizing the internet hierarchy.
> I noticed that 27% of the total possible tier-2 provider node pairs are
> unreachable i.e., they dont have any tier-1 node connecting them nor a
> direct peering link between them.
> 
>      Multihoming can be used as a predominant reason for the
> reachability of tier-3 nodes which are customers of these nodes, but what 
> about the reachability of tier-2 nodes themselves and its customers which 
> cannot afford to multihoming? How does BGP solve this reachability problem 
> when it gets a request to a prefix unreachable?
>
>       1        tier-1
>     /
>   2      4     tier-2
>  / \    / \
> 5   6  7   8  tier-3
>
> here, nodes 2 and 4 have no reachability,
>       1
>     / |
>   2   3  4
>  / \   \/ \
> 5   6  7   8
>
> now, node 7 is reachable from 2 and its lower level nodes, but what
> about
> node 4 and 8, and as a typical case, suppose nodes 4 and 8 have no
> multihoming whatsoever, what then?

I suspect there are many cases (ok, I know from experience, but couldn't 
tell you off the top of my head which ones) of networks that can't reach 
other networks, but it's probably a tiny fraction of a percent, not the 
27% you came up with.

It looks like the flaws in your methodology are to assume a far more rigid 
hierarchy than is actually there, and to ignore peering.

If we assume the strict tiered hierarchy that you show in this example:

>       1        tier-1
>     /
>   2      4     tier-2
>  / \    / \
> 5   6  7   8  tier-3

It's unlikely that network 4 would lack a transit provider.  Network 4 
might not be buying transit from the same tier 1 as network 2, but they 
would be buying from a different tier 1, who would peer with network 1. 
It would look something like this:

    1------9     tier-1
    |      |
    2      4     tier-2
   / \    / \
  5   6  7   8   tier-3

These do show up in the route-views data.  To see some networks that are 
reachable from one tier 1 through another tier 1, you can use the command 
"show ip bgp regex ^2914_701$".

In the real world, the tier structure isn't nearly as clearly defined. 
There are also lots of interconnections ("peering") in places other than 
the top of the hierarchy, to the point where it isn't quite clear what the 
hierarchy is.  So, taking the above example, it could also look something 
like this:

    1------9     tier-1
    |      |
    |      4
    |     / \
    2----7 __8
   / \    /
  5   6---

In this case, 2 has gotten tired of paying 1 to reach 7, and 7 has gotten 
tired of paying 9 and 4 to reach 2, so they've peered directly.  A lot of 
these arrangements won't show up in route-views, since the routes learned 
from peers are generally only announced to customers, not to upstreams or 
other peers.  So, if route-views had a feed from 2, 5, or 7, but not from 
6 or 8, route-views would see the adjacency between 2 and 7, but not the 
adjacency between 6 and 8.

To answer your question about what BGP does when it doesn't find any 
reachability data for a network, it declares the network to be unreachable 
and drops the packets.  In the real world, you generally see this only 
when somebody is trying to send data to a network that doesn't exist, or 
when something is broken.

We've got some different routing data at http://lg.pch.net/, which shows 
what some networks are announcing to their peers, which might be useful to 
you.  However, our data doesn't tell you anything about our peers other 
peering or transit relationships, and there are a lot of networks we don't 
have peering data from (and it assumes they announce the same set of 
routes to all peers, which is a bad assumption in some cases).  I don't 
know if that's useful to you or not.

If this and the other replies you've gotten don't make sense, and you've 
still got a pair of networks you think don't talk to eachother, I'd be 
happy to look at the specific case and explain what's happening there.

-Steve