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

Constraint-based path selection aims at identifying a path that satisfies a set of quality of service (QoS) constraints. In general, this problem is known to be NP-complete, leading to the proposal of many heuristic algorithms. We provide an overview of these algorithms, focusing on restricted shortest path and multi-constrained path algorithms.

Introduction

In recent years, there has been an increasing demand for Internet-based multimedia applications. In response to this demand, the research community has been extensively investigating several quality of service (QoS)-based networking frameworks, such as integrated services (IntServ), differentiated services (DiffServ), and multiprotocol label switching (MPLS). One of the key issues in all of these frameworks is how to identify efficient paths that can satisfy the given QoS constraints, commonly known as the QoS-based routing problem.