Contact at or 8097636691
Responsive Ads Here

Tuesday, 6 February 2018

Cost-Effective Resource Allocation of Overlay Routing Relay Nodes(2015)

Cost-Effective Resource Allocation of

 Overlay Routing Relay Nodes(2015)

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.
KEYWORDS: Overlay network, resource allocation.

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. Note that if 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.
  1. Overlay placement is small.
  2. Assignment possible in between one source and one destination.
  3. Less trivial.
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. The second scenario we consider is the TPC improvement example discussed above. In this case, we test the 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. The third scenario addresses overlay Voice-over-IP (VoIP) applications such as Skype (, Google Talk (, and others. Such applications are becoming more and more popular offering IP telephone services for free, but they need abounded 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.
  1. Increase the service quality.
  2. Improve the performance for many users.
  3. Provides the best available topology.
System Requirements Specification:
Software Requirements:
Language                    :           Java (JDK1.7.0)
Operating System       :           Microsoft Windows Xp Service Pack 3
IDE                             :           my eclipse IDE 8.6
Front End                   :           JAVA (Swings)
Backend                     :           no database
Hardware Requirements:
Processor                     :           Intel Pentium 4
RAM                           :           256 MB
Hard Disk                   :           40 GB        
  1. System Model
  2. On the complexity of the ORRA problem
  3. Finding overlay vertex cut
  4. Performance analysis
System Model:
Given a G(V,E) graph describing a network, let Pu be the set of routing paths that is derived from the underlying routing scheme, and let Po be the set of routing paths that is derived from the overlaying routing scheme (we refer to each path Pu in and in Po as the underlying and overlaying path sets, respectively). Note that both Pu and Po can be defined explicitly as a set of paths, or implicitly, e.g., as the set of shortest paths with respect to a weight function W-> E->R over the edges. Given a pair of vertices s, t €v, denote by P o (s, t) the set of overlay paths between s and t.
On the complexity of the ORRA problem:
In this section, we study the complexity of the ORRA problem. In particular, we show that the -ORRA problem is NP-hard, and it cannot be approximated within a factor of O(log(n)) (where n is the minimum between the number of pairs and the number of vertices), using an approximation preserving reduction from the Set Cover (SC) problem. We also present an -approximation algorithm where m is the number of vertices required to separate each pair with respect to the set of overlay paths (a formal definition will be given later in this section). While the reduction and the hardness result hold even for the simple case where all nodes have an equal cost (i.e., the cost associated with a relay node deployment on each node is equal), the approximation algorithm can be applied for an arbitrary weight function, capturing the fact that the cost of deploying a relay node may be different from one node to another.
Finding overlay vertex cut:
While finding a minimal Overlay Vertex Cut required by the algorithm presented above seems like a nontrivial task in the general case, in turns out that when the overlay routing is given explicitly, it is simple as finding a minimal vertex cut. This is done by building a graph G’= (V’,E’) such that a vertex cut in G’ represents an Overlay Vertex Cut in the original graph .
Performance analysis:
Using overlay routing to improve TCP performance has been studied in several works in recent years. In particular, the TCP protocol is sensitive to delay, and there is a strict correlation between TCP throughput and the RTT. Thus, it may be beneficial to break high-latency TCP connections into a few concatenated low-latency sub connections. In this case, the set of relay nodes is used as sub connection endpoints, and the objective is to bound the RTT of each one of these sub connections. For instance, assuming that each link in the network depicted in has a similar latency, the TCP connection between and can be broken using the relay node located in into two sub connections reducing the maximum RTT of the connection.

No comments:

Post a Comment