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