N-hub Shortest-Path: A New Routing Paradigm for the Internet

Gabi Nakibly, Ph.D. Thesis Seminar
Wednesday, 25.7.2007, 15:00
Taub 601
Assoc. Prof. Reuven Cohen

We study the computational complexity and effectiveness of a concept we term "N-hub Shortest-Path Routing" in IP networks. N-hub Shortest-Path Routing allows the ingress node of a routing domain to determine up to N intermediate nodes ("hubs") through which a packet will pass before reaching its final destination. This facilitates better utilization of the network resources, while allowing the network routers to continue to employ the simple and well-known shortest-path routing paradigm. Our results show that N-hub Shortest-Path Routing can increase network utilization significantly even for N=1. Hence, it should be considered as a powerful mechanism for future datagram routing in the Internet. We further present an application of N-hub Shortest-Path Routing that leverages network service gateways (e.g. web proxies and caches) as hubs. Traffic flows are directed through these gateways in order to be serviced. We propose a novel approach for service gateways placement and selection, which takes into account traffic engineering considerations. Rather than trying to minimize the length of the traffic flow routes, we take advantage of these routes in order to enhance the overall network performance. We show that placement and selection of network services can be used as effective tools for traffic engineering.

Back to the index of events