Share Email Print

Proceedings Paper

Reserved delivery subnetwork configuration algorithm with the maximum sharing shortest path tree
Author(s): Ruibiao Qiu
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper Abstract

The reserved delivery service can help the information service providers to provide more consistent performance to their customers by the provisioning of reserved bandwidth on a delivery subnetwork. However, the configuration problem of a reserved delivery subnetwork is a hard optimization problem with no efficient exact algorithm besides exhaust searches. In this paper, we introduce a reserved delivery subnetwork configuration algorithm based on an idea of the maximum sharing shortest path tree (MSSPT). The proposed algorithm is motivated by the observation that the path sharing of multiple flows reduce the cost in reserved delivery subnetworks. Thus, a solution close to the optimal could occur in a subnetwork with the maximum degree of flow sharing. The maximum sharing shortest path tree problem can be categorized as a multicriteria shortest path problem. Using an algorithm based on the shortest path network (SPN, a unique subnetwork in which every path s → u is a shortest path in the original graph), we develop an efficient algorithm for the maximum sharing shortest path problem. The proposed algorithm is an approximation algorithm in nature because it takes the MSSPT as the approximation solution to the reserved delivery subnetwork configuration problem. Our experimental results show that the proposed algorithm has good performance against an easily computed lower bound, but has time complexity comparable to a single source shortest path algorithm.

Paper Details

Date Published: 8 August 2003
PDF: 8 pages
Proc. SPIE 5244, Performance and Control of Next-Generation Communications Networks, (8 August 2003); doi: 10.1117/12.511309
Show Author Affiliations
Ruibiao Qiu, Washington Univ. (United States)

Published in SPIE Proceedings Vol. 5244:
Performance and Control of Next-Generation Communications Networks
Robert D. van der Mei; Frank Huebner, Editor(s)

© SPIE. Terms of Use
Back to Top
Sign in to read the full article
Create a free SPIE account to get access to
premium articles and original research
Forgot your username?