User:David MacQuigg/Sandbox/Hierarchical routing

Figure 1. A three-level network hierarchy

Figure 2. A more complex hierarchy

When networks grow beyond a few thousand routers, it becomes impractical for every router to compute a specific path to evey other router. The solution to this problem is to cluster the routers into independent routing areas or "subnets", and treat these subnets as single nodes in a larger network. All traffic to any address in a subnet is routed through one or two "border" routers.

Figure 1 shows a three-level hierarchy. Here, the regional networks appear as nodes within the top-level network. With 1000 routers in each subnet, a network like this could have four billion routers serving an entire planet. Changes in network topology propagate only within one subnet, so the whole system can be as stable as one subnet. The routing tables in each subnet could be as small as the number of routers, if addresses were assigned in contiguous blocks within each subnet. Each local network would get 1024 contiguous addresses (a /22 CIDR block. Each regional network would get 1024 local networks (a /12 CIDR block), and the global backbone could have as many as 4096 regional networks (the 12 high-order bits in a /12 address).

The real Internet is a bit more complex than this ideal hierarchy. There are more than three levels in many areas. There are many overlapping networks serving the same set of subnets, and many that don't have a clearly-defined regional or local level. There are many links directly between subnets, avoiding the cost of routing up and down a hierarchy. Routing is often more complex than just computing the shortest path. See Shortest path routing and Routing protocols for further discussion. In spite of these complications, the simple hierarchy is a good starting point to understand the Internet.

Realistic example

Let's look at the path of a packet from Barcelona Spain to Tucson Arizona address 69.9.57.232. The routing tables in the Barceloa subnet are simple. If the address doesn't match any of 200 local address ranges, the packet goes to a border router, where it will be forwarded to the "Spain" subnet which includes most of Spain and part of Southern France.

The routers in the Spain subnet see that any address starting with 69. is no match for anything in their area, so the packet is forwarded through a border router to a global backbone operated by AT&T. There is a less costly route through two overlapping regional networks, but it doesn't appear in the routing table for the Spain subnet, due to a "competitive situation" between two of the carriers along that path. The AT&T global backbone will accept packets going anywhere, so that is the chosen route.

Routers in a global backbone have huge routing tables, currently 300,000 address ranges. Ideally, this could be done with less than a thousand entries by allocating contiguous address ranges to each subnet, but the real Internet is a compromise between ideality and the need to not change allocations that were made many years ago. Also, the fact that there are mutliple backbones with different local connections means that optimizing for one will make difficulties for others.

Continuing with our example, the backbone router in Toulouse France which received the packet from the Spain subnet, looks in its global routing table and finds a match with the block 69.9.0.0/16 (see CIDR notation). This gets the packet routed to Denver Colorado, where there is a connection to a level-two subnet in the Southwest USA, also operated by AT&T. Routers in this subnet have much more detail on address blocks in this area. The matching entry here is 69.9.32.0/19, a block of 8192 addresses allocated to Dakota Communications in Tucson Arizona. Dakota receives the packet through a link to a second-level router in Phoenix.

The routing table in Dakota's Tucson network has about 500 entries, including 69.9.57.224/27 a block of 32 allocated to customers using DSL lines from Qwest. Anything in this block gets forwarded through a fiber-optic cable to a router in a Qwest central office in downtown Tucson, then to a router in a switching office in East Tucson, then over a DSL line to to a Linksys router in the author's home, and finally to his desktop computer. We have not shown anything below the "local" level in Figure 2, but it can be quite complex. Qwest has its own multi-level network of DSL subscribers, most of whom are not Dakota customers, but to Dakota, the /27 block looks just like any of its own small subnets.

Note that Dakotacom in Tucson has its own connection to Phoenix, a line leased from Qwest, but the AT&T network knows nothing about this. Dakotacom uses it for outgoing communications, and for anything coming in from Qwest's second-level network. This would actually be a less costly path for the packet from Barcelona, but Qwest and AT&T are competitors, so they prefer to use their own lines when possible.