User:David MacQuigg/Sandbox/Hierarchical routing
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 indepependent routing areas or "subnets", and treat these subnets as single nodes in a higher-level 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 second-level networks appear as subnets within the top-level network. With 1000 routers in each subnet, a network like this could have a billion routers. Changes in network topology propagate only within one subnet, and each subnet computes its own internal routing table, so the whole system can be as stable and efficient as one subnet.
The real Internet is a bit more complex than this ideal hierarchy. There are many higher level networks serving the same set of subnets, and there are many links directly between subnets, avoiding the cost of routing up and down the hierarchy. Routing at the higher levels is more complex than just computing the shortest path. Network owners may want to provide special routing for preferred customers, or block other customers entirely. In spite of these complications, the simple hierarchy is a good starting point to understand the Internet.
Routing 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 500 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. 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 1, 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 Communications, 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.