Paper Info
Title
A survey on multi-constrained optimal path computation: Exact and approximate algorithms
Abstract
The paper presents a survey on the techniques to solve the multi-constrained optimal path (MCOP) problem. Computing the MCOP is a task shared by many research areas, from transportation systems to telecommunication networks. In the latter, the MCOP is often related to the issue of Quality of Service (QoS) routing, which consists in finding a route between a couple of nodes that meets a series of QoS requirements such as bounded delay, packet loss, and other parameters. The MCOP problem has been faced by several authors and a plethora of solving methods is now available. In the present work, we draw the state of the art of exact and approximate MCOP computation algorithms, with particular attention to the networking area. We describe and analyse the most representative methods, and for each of them we derive the worst case computational complexity. In addition, we provide the reader with a uniform notation and with the detailed pseudo-code of various algorithms, so that the paper can indeed serve as a workable starting point for further studies on the MCOP problem.
Year
DOI
Venue
2010
10.1016/j.comnet.2010.05.017
Computer Networks
Keywords
DocType
Volume
Multi-Constrained Optimal Path (MCOP),Multi-Objective Optimal Path (MOOP),Multi-Constrained Path (MCP),Restricted Shortest Path (RSP),Quality of Service (QoS) Routing,Exact algorithms,Approximate algorithms
Journal
54
Issue
ISSN
Citations 
17
Computer Networks
35
PageRank 
References 
Authors
1.18
37
3
Name
Order
Citations
PageRank
Rosario G. Garroppo111311.32
Stefano Giordano2583.28
Luca Tavanti314314.31