Hierarchical Routing in Large Networks
As networks expand in size and complexity, traditional flat routing methods become increasingly impractical. The growth of routing tables in routers leads to higher memory consumption, increased CPU processing time, and greater bandwidth usage for status updates. To address these challenges, hierarchical routing emerges as a viable solution, allowing for more efficient management of routing information.
Concept of Hierarchical Routing
In hierarchical routing, routers are organized into distinct regions. Each router maintains detailed knowledge of routing within its own region but has limited awareness of the internal structure of other regions. This division allows routers to focus on local routing decisions while abstracting the complexities of the entire network. When different networks are interconnected, treating each as a separate region further simplifies the routing process, freeing routers from the burden of knowing the topological details of other networks.
Multi-Level Hierarchies
For particularly large networks, a two-level hierarchy may not suffice. In such cases, regions can be grouped into clusters, which can then be organized into zones, groups, and so on. This multi-level hierarchy allows for a more granular approach to routing. For example, consider a packet traveling from Berkeley, California, to Malindi, Kenya. The routing process might unfold as follows:
1.The Berkeley router routes packets within California.
2.For out-of-state traffic, it forwards packets to the Los Angeles router.
3.The Los Angeles router handles domestic routing but sends foreign traffic to the New York router.
4.The New York router directs packets to the appropriate router in the destination country, such as Nairobi.
5.Finally, the packet is routed through the Kenyan network until it reaches Malindi.
This hierarchical approach streamlines routing by reducing the number of entries in each router’s routing table.
Efficiency Gains
Hierarchical routing significantly reduces the size of routing tables. For instance, in a two-level hierarchy with five regions, a router that originally had 17 entries can be reduced to just 7 entries. This reduction is particularly beneficial as the ratio of the number of regions to the number of routers per region increases, leading to substantial savings in table space.
However, these efficiency gains come with trade-offs. One notable drawback is the potential increase in path length. For example, while the optimal route from one region to another may be direct, hierarchical routing may necessitate routing through intermediary regions, which can lead to longer paths.
Determining the Optimal Hierarchy Levels
When designing a hierarchical routing structure, a key consideration is the number of levels in the hierarchy. For instance, in a network with 720 routers, a flat structure would require each router to maintain 720 entries. By partitioning the network into 24 regions of 30 routers each, the number of required entries per router drops to 53. If a three-level hierarchy is implemented, with 8 clusters containing 9 regions of 10 routers each, the number of entries per router can be further reduced to 25.
Research by Kamoun and Kleinrock (1979) suggests that the optimal number of levels for a network with N routers is approximately ln(N), resulting in an average of e ln(N) entries per router. Their findings indicate that the increase in effective mean path length due to hierarchical routing is typically small enough to be acceptable in most scenarios.
Conclusion
Hierarchical routing is a powerful strategy for managing routing in large networks. By organizing routers into regions and clusters, it reduces the complexity of routing tables and enhances the efficiency of routing processes. While there are trade-offs, such as increased path lengths, the benefits of reduced memory usage and processing requirements often outweigh the drawbacks. As networks continue to grow, hierarchical routing will remain a critical component in ensuring effective and scalable communication.