Cost Effective Resource Allocation of Overlay Routing Relay Nodes

Abstract

Overlay routing is a very attractive scheme that allows improving certain properties of the routing (such as delay or TCP throughput) without the need to change the standards of the current underlying routing. However, deploying overlay routing requires the placement and maintenance of overlay infrastructure. This gives rise to the following optimization problem: Find a minimal set of overlay nodes such that the required routing properties are satisfied. In this paper, we rigorously study this optimization problem. We show that it is NP-hard and derive a nontrivial approximation algorithm for it, where the approximation ratio depends on specific properties of the problem at hand. We examine the practical aspects of the scheme by evaluating the gain one can get over several real scenarios. The first one is BGP routing, and we show, using up-to-date data reflecting the current BGP routing policy in the Internet, that a relative small number of less than 100 relay servers is sufficient to enable routing over shortest paths from a single source to all autonomous systems (ASs), reducing the average path length of inflated paths by 40%. We also demonstrate that the scheme is very useful for TCP performance improvement (results in an almost optimal placement of overlay nodes) and for Voice-over-IP (VoIP) applications where a small number of overlay nodes can significantly reduce the maximal peer-to-peer delay.

Existing System

Using overlay routing to improve routing and network performance has been studied before in several works. The authors studied the routing inefficiency in the Internet and used an overlay routing in order to evaluate and study experimental techniques improving the network over the real environment. While the concept of using overlay routing to improve routing scheme was presented in this work, it did not deal with the deployment aspects and the optimization aspect of such infrastructure. A resilient overlay network (RON), which is architecture for application-layer overlay routing to be used on top of the existing Internet routing infrastructure, has been presented. Similar to our work, the main goal of this architecture is to replace the existing routing scheme, if necessary, using the overlay infrastructure. This work mainly focuses on the overlay infrastructure (monitoring and detecting routing problems, and maintaining the overlay system), and it does not consider the cost associated with the deployment of such system.

Proposed System

 In order to deploy overlay routing over the actual physical infrastructure, one needs to deploy and manage overlay nodes that will have the new extra functionality. This comes with a non negligible cost both in terms of capital and operating costs.  Our proposed algorithmic framework that can be used in order to deal with efficient resource allocation in overlay routing.

Architecture