Cost-Effective Resource Allocation of Overlay Routing Relay Nodes

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:

 Overlay routing has been proposed in recent years as an effective way to achieve certain routing properties, without going into the long and tedious process of standardization and global deployment of a new routing protocol. For example, in overlay routing was used to improve TCP performance over the Internet, where the main idea is to break the end-to-end feedback loop into smaller loops. This requires that nodes capable of performing TCP Piping would be present along the route at relatively small distances. Other examples for the use of overlay routing are projects like RON and Detour, where overlay routing is used to improve reliability. Yet another example is the concept of the “Global-ISP” paradigm introduced, where an overlay node is used to reduce latency in BGP routing. 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.

DISADVANTAGES OF EXISTING SYSTEM:

·       It comes with a non negligible cost both in terms of capital and operating costs.

·       It gives rise to optimization problem.

PROPOSED SYSTEM:

We concentrate 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.

ADVANTAGES OF PROPOSED SYSTEM:

·       It provides general algorithmic framework that can be used in order to deal with efficient resource allocation in overlay routing.

·       It develops a nontrivial approximation algorithm and prove its properties.

SYSTEM CONFIGURATION:-

HARDWARE REQUIREMENTS:-

ü Processor                  -        Pentium –IV

ü Speed                        -        1.1 Ghz

ü RAM                         -        512 MB(min)

ü Hard Disk                 -        40 GB

ü Key Board                -        Standard Windows Keyboard

ü Mouse                       -        Two or Three Button Mouse

ü Monitor                     -        LCD/LED

SOFTWARE REQUIREMENTS:

•         Operating system :         Windows XP

•         Coding Language :         Java

•         Data Base             :         MySQL

•         Tool                     :         Net Beans IDE

REFERENCE:

Rami Cohen and Danny Raz, “Cost-Effective Resource Allocation of Overlay Routing Relay Nodes” IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 22, NO. 2, APRIL 2014.