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.
DISADVANTAGES
OF EXISTING 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.
PROPOSED
SYSTEM:
In this paper, 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:
Ø We
are only interested in improving routing properties between a single source
node and a single destination, then the problem is not complicated, and finding
the optimal number of nodes becomes trivial since the potential candidate for
overlay placement is small, and in general any assignment would be good.
Ø However,
when we consider one-to-many or many-to-many scenarios, then a single overlay
node may affect the path property of many paths, and thus choosing the best
locations becomes much less trivial.
MODULES:
1. AS-level
BGP routing
2. TPC
improvement level
3. Voice-over-IP
MODULES
DESCRIPTION:
AS-level
BGP routing:
We consider is AS-level BGP routing, where the goal
is to find a minimal number of relay node locations that can allow
shortest-path routing between the source–destination pairs. Recall that routing
in BGP is policy-based and depends on the business relationship between peering
ASs, and as a result, a considerable fraction of the paths in the Internet do
not go along a shortest path. This phenomenon, called path inflation, is the
motivation for this scenario. We consider a one-to-many setting where we
want
to improve routing between a single source and many destinations. This is the
case where the algorithm power is most significant since, in the many-to-many
setting, there is very little overlap between shortest paths, and thus not much
improvement can be made over a basic greedy approach. We demonstrate, using
real up-to-date Internet data, that the algorithm can suggest a relatively
small set of relay nodes that can significantly reduce latency in current BGP
routing.
TPC
level improvement:
We consider is the TPC level improvement in the
wireless networks as explained in the above module. In this case, we test our
proposed algorithm on a synthetic random graph, and we show that the general framework
can be applied also to this case, resulting in very close-to-optimal results.
Voice-over-IP:
Voice-Over-IP type of applications are becoming more
and more popular offering IP telephone services for free, but they need a
bounded end-to-end delay (or latency) between any pair of users to maintain a
reasonable service quality. We show that our scheme can be very useful also in
this case, allowing applications to choose a smaller number of hubs, yet improving
performance for many users.
SYSTEM CONFIGURATION:-
HARDWARE CONFIGURATION:-
ü Processor - Pentium –IV
ü Speed - 1.1
Ghz
ü RAM - 256
MB(min)
ü Hard Disk -
20 GB
ü Key Board -
Standard Windows Keyboard
ü Mouse - Two
or Three Button Mouse
ü Monitor - SVGA
SOFTWARE CONFIGURATION:-
ü Operating System : Windows 7
ü Programming Language :
JAVA
ü Java Version :
JDK 1.6 & above.
REFERENCE:
Rami Cohen and Danny Raz, Member, IEEE “Cost-Effective
Resource Allocation of Overlay Routing Relay Nodes”- IEEE/ACM TRANSACTIONS ON
NETWORKING, VOL. 22, NO. 2, APRIL 2014
No comments:
Post a Comment