On the Placement of Infrastructure Overlay Nodes

Overlay routing has emerged as a promising approach to improving performance and reliability of Internet paths. To fully realize the potential of overlay routing under the constraints of deployment costs in terms of hardware, network connectivity and human effort, it is critical to carefully place i...

Full description

Saved in:
Bibliographic Details
Published in:IEEE/ACM transactions on networking 2009-08, Vol.17 (4), p.1298-1311
Main Authors: Roy, S., Pucha, H., Zheng Zhang, Hu, Y.C., Lili Qiu
Format: Article
Language:English
Subjects:
Algorithms
Computational modeling
Computer networks
Costs
Hardware
Humans
Infrastructure
Internet
Mathematical analysis
Network servers
NP-completeness
overlay networks
Peer to peer computing
Placement
reliability
Routing
Routing (telecommunications)
Studies
TCP
TCP (protocol)
Telecommunication traffic
Topology
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Overlay routing has emerged as a promising approach to improving performance and reliability of Internet paths. To fully realize the potential of overlay routing under the constraints of deployment costs in terms of hardware, network connectivity and human effort, it is critical to carefully place infrastructure overlay nodes to balance the tradeoff between performance and resource constraints. In this paper, we investigate approaches to perform intelligent placement of overlay nodes to facilitate (i) resilient routing and (ii) TCP performance improvement. We formulate objective functions to capture application behavior: reliability and TCP performance, and develop several placement algorithms, which offer a wide range of tradeoffs in complexity and required knowledge of the client-server location and traffic load. Using simulations on synthetic and real Internet topologies, and PlanetLab experiments, we demonstrate the effectiveness of the placement algorithms and objective functions developed, respectively. We conclude that a hybrid approach combining greedy and random approaches provides the best tradeoff between computational efficiency and accuracy. We also uncover the fundamental challenge in simultaneously optimizing for reliability and TCP performance, and propose a simple unified algorithm to achieve both.
ISSN:1063-6692
1558-2566
DOI:10.1109/TNET.2008.2007433