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

In this paper, we study the computational complexity and effectiveness of a concept we term ldquoN-hub shortest-path routingrdquo in IP networks. N-hub shortest-path routing allows the ingress node of a routing domain to determine up to N intermediate nodes (ldquohubsrdquo) 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. We apply N-hub shortest-path routing to the problem of minimizing the maximum load in the network. We show that the resulting routing problem is NP-complete and hard to approximate. However, we propose efficient algorithms for solving it both in the online and the offline contexts. Our results show that N-hub shortest-path routing can increase network utilization significantly even for N = 1. Hence, this routing paradigm should be considered as a powerful mechanism for future datagram routing in the Internet.