NDLI: Multi-constrained optimal path selection

Content Provider	IEEE Xplore Digital Library
Author	Korkmaz, T. Krunz, M.
Copyright Year	2001
Description	Author affiliation: Dept. of Electr. & Comput. Eng., Arizona Univ., Tucson, AZ, USA (Korkmaz, T.)
Abstract	Providing quality-of-service (QoS) guarantees in packet networks gives rise to several challenging issues. One of them is how to determine a feasible path that satisfies a set of constraints while maintaining high utilization of network resources. The latter objective implies the need to impose an additional optimality requirement on the feasibility problem. This can be done through a primary cost function (e.g., administrative weight, hop count) according to which the selected feasible path is optimal. In general, multi-constrained path selection, with or without optimization, is an NP-complete problem that cannot be exactly solved in polynomial-time. Heuristics and approximation algorithms with polynomial and pseudo-polynomial-time complexities are often used to deal with this problem. However, existing solutions suffer either from excessive computational complexities that cannot be used for online network operation or from low performance. Moreover, they only deal with special cases of the problem (e.g., two constraints without optimization, one constraint with optimization, etc.). For the feasibility problem under multiple constraints, some researchers have proposed a nonlinear cost function whose minimization provides a continuous spectrum of solutions ranging from a generalized linear approximation (GLA) to an asymptotically exact solution. We propose an efficient heuristic algorithm for the most general form of the problem. We first formalize the theoretical properties of the above nonlinear cost function. We then introduce our heuristic algorithm (H MCOP), which attempts to minimize both the nonlinear cost function (for the feasibility part) and the primary cost function (for the optimality part). We prove that H MCOP guarantees at least the performance of GLA and often improves upon it. H MCOP has the same order of complexity as Dijkstra's algorithm. Using extensive simulations on random graphs with correlated and uncorrelated link weights, we show that under the same level of computational complexity, H MCOP outperforms its (less general) contenders in its success rate in finding feasible paths and in the cost of such paths.
Sponsorship	IEEE Comput. Soc. IEEE Commun. Soc
Starting Page	834
Ending Page	843
File Size	276893
Page Count	10
File Format	PDF
ISBN	0780370163
ISSN	0743166X
DOI	10.1109/INFCOM.2001.916274
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2001-04-22
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Cost function Heuristic algorithms Polynomials Computational complexity Constraint optimization Quality of service NP-complete problem Approximation algorithms Linear approximation Computational modeling
Content Type	Text
Resource Type	Article
Subject	Electrical and Electronic Engineering Computer Science

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	Mr. Siddhartha Mukherjee siddhartha@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	ndl-support@iitkgp.ac.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Libarray 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

Routing multimedia traffic with QoS guarantees

An overview of constraint-based path selection algorithms for QoS routing

Multi-constrained optimal path selection (2001).

Korkmaz and krunz: multi-constrained optimal path selection 1 multi-constrained optimal path selection.

Multi-Constrained Optimal Path Selection (2001)

Enhancing /spl epsiv/-approximation algorithms with the optimal linear scaling factor

Exact and heuristic algorithms for multi-constrained path selection problem.

Optimal and Heuristic Algorithms for Quality-of-Service Routing with Multiple Constraints (2004)

Inapproximability Results for Sparsest Cut, Optimal Linear Arrangement, and Precedence Constrained Scheduling

Multi-constrained optimal path selection

Similar Documents

Routing multimedia traffic with QoS guarantees

An overview of constraint-based path selection algorithms for QoS routing

Multi-constrained optimal path selection (2001).

Korkmaz and krunz: multi-constrained optimal path selection 1 multi-constrained optimal path selection.

Multi-Constrained Optimal Path Selection (2001)

Enhancing /spl epsiv/-approximation algorithms with the optimal linear scaling factor

Exact and heuristic algorithms for multi-constrained path selection problem.

Optimal and Heuristic Algorithms for Quality-of-Service Routing with Multiple Constraints (2004)

Inapproximability Results for Sparsest Cut, Optimal Linear Arrangement, and Precedence Constrained Scheduling

Multi-constrained optimal path selection