## 3 Applications to Communication Network Design
### Overview of Selected Papers
#### 3.2.1 Models That Use Straightforwardly Algorithm(s) Dedicated to MOPPs
Finally, the problem of finding (if they exist) a set of \(k\) (edge-)disjoint paths for a source-destination pair, such that each path is the shortest concerning each of the multiple criteria, is tackled and an algorithm is proposed to solve it. In [160], the description of an application to an Internet stochastic packet routing method of the \(k\)-quickest path algorithm in [161] is included. The objective function of the corresponding path optimization problem is the expected total transmission time given by the sum of total average delay (an additive metric) and the expected packet transmission time associated with the path bottleneck bandwidth (a non-additive metric) and is solved exactly by that deviation algorithm. The efficiency of the routing method is shown with a stochastic packet traffic simulator using a truncated Pareto distribution. Note that this type of path ranking calculation method can be very useful in applications to single objective multipath routing and to multicriteria routing models where the path bottleneck bandwidth is a central optimization objective. Concerning non-lexicographic MOPP formulations, which are the main focus of this work, we will begin by referring to [162]. It is, as far as we know, a first approach to an explicitly multiobjective routing model for telecommunication networks solved with an exact combinatorial algorithm. It presents a biobjective routing model seeking paths with minimal cost and average delay which corresponds to the formulation of a biobjective shortest path problem. This model can be adapted to different additive objective functions associated with different types of end-to-end services in multiservice networks. An exact resolution method was developed which computes efficient paths based on the optimization of weighted sums of the OFs by recurring to the very efficient \(k\)-shortest path algorithm [71]. Furthermore, QoS requirements are represented in the model through'soft constraints' (which are not directly included in the BOSPP mathematical formulation) concerning 'acceptable' and'requested' values for each of those metrics. These values enable the definition of priority regions in the OF space where nondominated solutions can be searched for and can be used in the context of an automatic search procedure of a final routing solution. Paper [18] addresses a multiobjective routing model with two additive objective functions (routing cost in terms of the number of arcs and a 'load cost' associated with the available bandwidth in the arcs) and three QoS constraints concerning average delay, delay jitter and bottleneck bandwidth. This corresponds to the formulation of a biobjective constrained shortest path problem previously tackled in a telecom network routing design context by [163] using a rule-based heuristic based on the Dijkstra shortest path algorithm, a heuristic which does not guarantee that the obtained solutions are Pareto optimal. The authors in [18] present an exact resolution approach for calculating the whole set of efficient solutions for this problem by recurring to the biobjective shortest path algorithm in [11] and to the MPS algorithm in [71], for calculating \(k\)-shortest paths having as objective function the convex combination of the two OFs of the problem. The use of a ranking algorithm in this context was shown to be the more efficient resolution approach (even in networks with up to a few thousand nodes) due to the explicit consideration of the mentioned QoS constraints of the biobjective problem. Note that this type of routing model, although originally formulated for video type traffic in the discontinued Asynchronous Transfer Mode (ATM) based networks, can be applied straightforwardly to current networks with packet-switch-based technologies (such as MPLS-Transport Profile, MPLS-TP) by simple adaptation of the pertinent QoS constraints.