## 3 Applications to Communication Network Design
### Overview of Selected Papers
The shortest path problems associated with QoS routing models formally are not MOPPs and the number of papers in this area is very large. Nevertheless, we will refer to some relevant works on this type of routing models noting that most exact resolution approaches in this domain were based on shortest path and \(k\)-shortest path algorithms, and also a number of proposed heuristics/metaheuristics were often based on those types of auxiliary exact algorithms. One of the earliest works in this area is the report [147] which presented an exact algorithm (referred to as constrained Bellman-Ford algorithm) for a constrained shortest path problem in QoS routing design, for calculating minimal cost paths with a delay constraint. It enables the obtainment of successive shortest paths for different values of the right-hand-side constraint on the delay, leading to efficient solutions. Bearing in mind the implicit bicriteria nature of this approach, we could remark that the bicriteria shortest path problem method in [11] could obtain a similar result by using a more efficient procedure. An early state-of-the-art report on QoS routing up to 1999 is given in [148]. The author of [149] describes a unified treatment of several path calculation problem formulations in QoS routing models (including linear and non-linear objective functions such as in shortest path, widest path, widest-shortest path, most-reliable path and most-reliable shortest path problems) by proposing an 'algebra of weights', also enabling us to consider a specific requirement for the implementation of the corresponding hop-by-hop routing procedure on the Internet. For this purpose, it constructs a variant of the Dijkstra algorithm. A review on constrain-based QoS routing models can be seen in [150]. In [151], a formal analysis of complexity issues of the multiconstrained path problem, shows that this problem is NP-complete but not strong NP-complete and also explains reasons why in most practical instances of this problem, in communication network routing, exact resolution methods can be used. A study concerning the comparison of exact algorithms and specific heuristics (\(\epsilon\)-approximation algorithms) for the multiconstrained optimal path problem in QoS routing is shown in [152]. An analysis of the relation between QoS routing problem resolution approaches based on Lagrangean decomposition and the optimization of linear combinations of the OFs (for example, average path delay and path cost) used in multicriteria analysis can be seen in [1] (Section 4.1.2.1). It is also important to note that, in the context of packet-switched networks and IP-based networks, adequate versions of classical shortest path algorithms have been extensively used as the basis of routing algorithms associated with two classes of routing protocols. These classes are defined in terms of the type of information and information exchange that a node needs (and may need to pass to its neighbors) to compute the shortestpaths. The first type comprises link state routing protocols such as Open Shortest Path First (OSPF) and Intermediate System to Intermediate System (IS-IS) which have been commonly used as Internet intra-domain routing protocols and typically use a distributed version of the Dijkstra algorithm. In this case, the current link metric values (arc costs) are to be known by the nodes, and nodes are informed about its changes in a distributed manner (link-state advertisement mechanism). The second type comprises distance-vector routing protocols--where a node needs to know the cost (or 'distance') from each of its neighbors to all destination nodes, so that a shortest path may be computed and typically use a distributed version of the Bellman-Ford algorithm. An important example is the Routing Information Protocol (RIP). Extensive analysis of the application of shortest path-based routing algorithms and related protocols can be seen in [143] (Chapter 7) and in [144] (Chapters 2 and 7).