Document Type

Technical Report

Publication Date

2002-01-31

Filename

wucse-2002-5.pdf

DOI:

10.7936/K7PK0DGJ

Technical Report Number

WUCSE-2002-5

Abstract

Overlay networks are becoming a popular vehicle for deploying advanced network services in the Internet. Overlay networks are implemented by deploying service nodes at suitably chosen sites in the network. Service nodes communicate with users through the commodity Internet, while among themselves, they may use either the commodity Internet or dedicated channels. The number of distinct service nodes has a big influence on the operational cost of an overlay network; meanwhile, the distance between service nodes and end users has a big influence on the quality of the service. In this paper, we study the problem of how to optimally place service nodes in a network, balancing the need to minimize the number of nodes, while limiting the distance between users and service nodes. We show that the design problem is NP-hard and study the performance of heuristic algorithms using simulation. For single domain, our algorithms produce results that are within a few percent of an easily computed lower bound. For multi-domain networks, the performance ranges from close to the optimal to roughly twice the optimal.

Comments

Permanent URL: http://dx.doi.org/10.7936/K7PK0DGJ

Download

Share

COinS