On topological design of service overlay networks

Arunabha Sen, Ling Zhou, Bin Hao, Bao Hong Shen, Samrat Ganguly

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations


The notion of service overlay network (SON) was proposed recently to alleviate difficulties encountered in providing end-to-end quality of service (QoS) guarantees in the current Internet architecture. The SONs are able to provide QoS guarantees by purchasing bandwidth from individual network domains and building a logical end-to-end data delivery infrastructure on top of existing Internet. In this paper, we consider a generalized framework for SON, which is categorized based on three different characteristics: a) single-homed/multi-homed end-system b) usage-based/leased cost model and c) capacitated/uncapacitated network. We focus on the algorithmic analysis of the topology design problem for the above generalized SON. We prove that for certain case, polynomial-time optimal algorithm exists, while for other cases, the topology design problem is NP-complete. For the NP-complete cases, we provide approximation algorithms and experimental results.

Original languageEnglish (US)
Title of host publicationLecture Notes in Computer Science
EditorsH. Meer, N. Bhatti
Number of pages15
StatePublished - 2005
Event13th International Workshop on Qualityof Service - IWQoS 2005 - Passau, Germany
Duration: Jun 21 2005Jun 23 2005


Other13th International Workshop on Qualityof Service - IWQoS 2005

ASJC Scopus subject areas

  • Computer Science (miscellaneous)


Dive into the research topics of 'On topological design of service overlay networks'. Together they form a unique fingerprint.

Cite this