On the Computational Complexity and Effectiveness of N-Hub Shortest-Path Routing

In this paper, the authors study the computational complexity and effectiveness of a concept they 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. Although this concept has been proposed in the past, this paper is the first to investigate it in depth.