Cost Effective Resource Allocation of Overlay Routing Relay Nodes (2014)

Note: Please Scroll Down to See the Download Link.

Cost-Effective Resource Allocation of Overlay Routing Relay Nodes



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.




In the existing system, the system is using overlay routing to improve network performance is

motivated by many works that studied the inefficiency of varieties of networking architectures and applications. Analyzing a large set of data, Savage et al. explore the question: How “good” is Internet routing from a user’s perspective considering round-trip time, packet loss rate, and bandwidth? They showed that in 30%–80% of the cases, there is an alternate routing path with better quality compared to the default routing path. In the current system and later in existing system, the authors show that TCP performance is strictly affected by the RTT. Thus, breaking a TCP connection into low-latency sub connections improves the overall connection performance. In the existing system, the authors show that in many cases, routing paths in the Internet are inflated, and the actual length (in hops) of routing paths between clients is longer than the minimum hop distance between them. Using overlay routing to improve routing and network performance has been studied before in several works.


 In the existing system, 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 in the current system. 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.




In the proposed system, The system concentrates on this point and study the minimum number of infrastructure nodes that need to be added in order to maintain a specific property in the overlay routing. In the shortest-path routing over the Internet BGP-based routing example, this question is mapped to: What is the minimum number of relay nodes that are needed in order to make the routing between a groups of autonomous systems (ASs) use the underlying shortest path between them? In the TCP performance example, this may translate to: What is the minimal number of relay nodes needed in order to make sure that for each TCP connection, there is a path between the connection endpoints for which every predefined round-trip time (RTT), there is an overlay node capable of TCP Piping?


Regardless of the specific implication in mind, we define a general optimization problem called the Overlay Routing Resource Allocation (ORRA) problem and study its complexity. It turns out that the problem is NP-hard, and we present a nontrivial approximation algorithm for it.



Hardware Requirements:


•         System                                    :   Pentium IV 3.5 GHz.

•         Hard Disk                   :   40 GB.

•         Floppy Drive               :   1.44 Mb.

•         Monitor                       :   14’ Colour Monitor.

•         Mouse                        :   Optical Mouse.

•         Ram                            :   1 GB.


Software Requirements:


•         Operating system        :   Windows XP or Windows 7, Windows 8.

•         Coding Language       :   Java – AWT,Swings,Networking

•         Data Base                    :   My Sql / MS Access.

•         Documentation           :  MS Office

•         IDE                             : Eclipse Galileo

•         Development Kit        : JDK 1.6



While using overlay routing to improve network performance was studied in the past by many works both practical and theoretical, very few of them consider the cost associated with the deployment of overlay infrastructure. In this paper, we addressed this fundamental problem developing an approximation algorithm to the problem. Rather than considering a customized algorithm for a specific application or scenario, we suggested a general framework that fits a large set of overlay applications. Considering three different practical scenarios, we evaluated the performance of the algorithm, showing that in practice the algorithm provides close-to-optimal results. Many issues are left for further research. One interesting direction is an analytical study of the vertex cut used in the algorithm. It would be interesting to find properties of the underlay and overlay routing that assure a bound on the size of the cut. It would be also interesting to study the performance of our framework for other routing scenarios and to study issues related to actual implementation of the scheme.


In particular, the connection between the cost in terms of establishing overlay nodes and the benefit in terms of performance gain achieved due to the improved routing is not trivial, and it is interesting to investigate it. The business relationship between the different players in the various use cases is complex, and thus it is important to study the economical aspects of the scheme as well. For example, the one-to-many BGP routing scheme can be used by a large content provider in order to improve the user experience of its customers. The VoIP scheme

can be used by VoIP services (such as Skype) to improve call quality of their customers. In both these cases, the exact translation of the service performance gain into actual revenue is not clear and can benefit from further research.

Click here to download Cost Effective Resource Allocation of Overlay Routing Relay Nodes (2014) documents