Development of a Nontrivial Approximation Algorithm to resolve Optimization Problem of Overlay Routing Resource Allocation

Abstract

In this research 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 group 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.
Keywords: Overlay Routing Resource Allocation; Round trip time; Autonomous Systems; TCP Piping; Voice over IP; Resilient Overlay Network