Abstrait

Multi-hop overlay Transport for High Throughput transfers in the Internet

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. so, deploying overlay routing needs the placement and maintenance of overlay infrastructure, which gives the following optimization problem: Find a minimal set of overlay nodes such that the required routing properties are satisfied. Here, we rigorously study this optimization problem and it is NP-hard and derive a nontrivial approximation algorithm for which the approximation ratio depends on specific properties of the problem. 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, using up-to-date data reflecting the current BGP routing policy in the Internet, a relative small number of less than 110 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 50%. 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.