Reserved delivery subnetwork configuration algorithm with the maximum sharing shortest path tree

Ruibiao Qiu

doi:10.1117/12.511309

8 August 2003 Reserved delivery subnetwork configuration algorithm with the maximum sharing shortest path tree

Ruibiao Qiu

Proceedings Volume 5244, Performance and Control of Next-Generation Communications Networks; (2003) https://doi.org/10.1117/12.511309
Event: ITCom 2003, 2003, Orlando, Florida, United States

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.

Citation Download Citation

Ruibiao Qiu "Reserved delivery subnetwork configuration algorithm with the maximum sharing shortest path tree", Proc. SPIE 5244, Performance and Control of Next-Generation Communications Networks, (8 August 2003); https://doi.org/10.1117/12.511309

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available