RouteSeer: Topological Placement of Nodes in Service Overlays

Abstract

Overlay networks are being increasingly used to deploy new services on the Internet. As opposed to peer-to-peer overlays, these infrastructure or service overlays offer the opportunity of placing the overlay nodes and selecting the links between them. There has been very little work done in the area of node placement in overlay network design. In this work, our objective is to study the overlay node placement problem based on a specific performance objective, namely, overlay link resiliency. An overlay link is called resilient if there exists an intermediate overlay node through which a connection can be established even if there is a failure in the underlying network links between the overlay nodes. In this paper, we propose an algorithm, called RouteSeer, to solve the overlay node placement problem. We split the problem into two parts, placing some overlay nodes called client proxies “close” to the clients of the overlay service and placing intermediate nodes to provide resilient paths between the client proxies. RouteSeer heuristically places the intermediate overlay nodes by only examining the routing tables at the client proxies and does not require global topology information. In our simulations and experiments on the Internet, we show that RouteSeer can improve on previous schemes by 50-100%.