NDLI: Bandwidth-delay constrained path selection under inaccurate state information

Content Provider	ACM Digital Library
Author	Krunz, Marwan Korkmaz, Turgay
Abstract	One of the key issues in any quality-of-service (QoS) routing framework is how to compute a path that satisfies given QoS constraints. In this paper, we focus on the path computation problem subject to the bandwidth and delay constraints. This problem can be easily solved if the exact state information is available to the node performing the path computation function. In practice, however, nodes have only imprecise knowledge of the network state. The reliance on outdated information and treating this information as exact can significantly degrade the effectiveness of the path selection algorithm. To address this problem, we adopt a probabilistic approach in which the state parameters (available bandwidth and delay) are characterized by random variables. The goal is then to find the most-probable bandwidth-delay-constrained path (MP-BDCP). We provide efficient solutions for the MP-BDCP problem by decomposing it into two subproblems: the most-probable delay-constrained path (MP-DCP) problem and the most-probable bandwidth-constrained path (MP-BCP) problem. MP-DCP by itself is known to be NP-hard, necessitating the use of approximate solutions. By employing the central limit theorem and Lagrange relaxation techniques, we provide two complementary solutions for MP-DCP. These solutions are found to be highly efficient, requiring on average a few iterations of Dijkstra's shortest path algorithm. As for MP-BCP, it can be easily transformed into a variant of the shortest path problem. Our solutions for MP-DCP and MP-BCP are then combined to address the MP-BDCP problem by obtaining a set of $\textit{near-nondominated}$ paths. Decision makers can then select one or more of these paths based on a specific utility function. Extensive simulations are used to demonstrate the efficiency of the proposed algorithmic solutions and, more generally, to contrast the probabilistic path selection approach with the standard threshold-based triggered approach.
Starting Page	384
Ending Page	398
Page Count	15
File Format	PDF
ISSN	10636692
DOI	10.1109/TNET.2003.813047
Volume Number	11
Issue Number	3
Journal	IEEE/ACM Transactions on Networking (TON)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2003-06-01
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Lagrange relaxation Multiobjective optimization Quality-of-service (QoS) routing Stochastic shortest path
Content Type	Text
Resource Type	Article
Subject	Electrical and Electronic Engineering Computer Networks and Communications Software Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Bandwidth-delay constrained path selection under inaccurate state information

Bandwidth-Delay Constrained Path Selection Under Inaccurate State Information (2003)

Heuristic methods for delay constrained least cost routing using /spl kappa/-shortest-paths

Algorithms for computing QoS paths with restoration

QoS routing in networks with inaccurate information: theory and algorithms

QoS routing in networks with inaccurate information: theory and algorithms

QoS Routing Algorithms under Inaccurate Routing Information for Bandwidth Constrained Applications (2003)

Quality-of-service provisioning via stochastic path selection under Weibullian link delays

A Simple and Fast Algorithm for Restricted Shortest Path Problem

Bandwidth-delay constrained path selection under inaccurate state information

Similar Documents

Bandwidth-delay constrained path selection under inaccurate state information

Bandwidth-Delay Constrained Path Selection Under Inaccurate State Information (2003)

Heuristic methods for delay constrained least cost routing using /spl kappa/-shortest-paths

Algorithms for computing QoS paths with restoration

QoS routing in networks with inaccurate information: theory and algorithms

QoS routing in networks with inaccurate information: theory and algorithms

QoS Routing Algorithms under Inaccurate Routing Information for Bandwidth Constrained Applications (2003)

Quality-of-service provisioning via stochastic path selection under Weibullian link delays

A Simple and Fast Algorithm for Restricted Shortest Path Problem

Bandwidth-delay constrained path selection under inaccurate state information