An Algorithmic Approach to Topological Design of Service Overlay Networks

Report
Authors:Vieira, Sibelius, Department of Computer ScienceUniversity of Virginia Liebeherr, Jorg, Department of Computer ScienceUniversity of Virginia
Abstract:

The Internet still lacks adequate support for QoS applications with real-time re- quirements. In great part, this is due to the fact that provisioning of end-to-end QoS to traffic that traverses multiple autonomous systems (ASs) requires a level of cooperation between ASs that is difficult to achieve in the current architecture. Recently, service overlay networks have been considered as an approach to QoS deployment that avoids these difficulties. In this study, we address the problem of the topological synthesis of a service overlay network, where endsystems and nodes of the overlay network (provider nodes) are connected through ISPs that supports bandwidth reservations. We express the topology design problem as an optimization problem. Even though the design problem is related to the (in general NP-hard) quadratic assignment problem, we are able to show that relatively simple heuristic algorithms can deliver results that are sometimes close to the optimal solution.

Rights:
All rights reserved (no additional license for public reuse)
Language:
English
Source Citation:

Vieira, Sibelius, and Jorg Liebeherr. "An Algorithmic Approach to Topological Design of Service Overlay Networks." University of Virginia Dept. of Computer Science Tech Report (2004).

Publisher:
University of Virginia, Department of Computer Science
Published Date:
2004