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 ASes 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 end points for which every predefined Round-Trip-Time, 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 Re- source Allocation (ORRA) problem and study its complexity. It turns out that the problem is NP-hard, and we present a non-trivial approximation algorithm for it. 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 are sufficient to enable routing over shorter paths from a single source to all ASes, reducing the average path length of inflated paths by 40%. We also demonstrate that using the scheme for TCP performance improvement, results in an almost optimal placement of overlay nodes. We develop a general algorithmic framework that can be used in order to deal with efficient resource allocation in overlay routing. We develop a non-trivial approximation algorithm and prove its properties. We demonstrate the actual benefit one can gain from using our scheme in two practical scenarios, namely BPG routing, and TCP improvement.