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 pack et 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 (C) 2010 Elsevier B V All rights reserved
A survey on multi-constrained optimal path computation: Exact and approximate algorithms
GARROPPO, ROSARIO GIUSEPPE;GIORDANO, STEFANO;TAVANTI, LUCA
2010-01-01
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 pack et 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 (C) 2010 Elsevier B V All rights reservedI documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
