Koster A., Munoz X. Graphs and Algorithms in Communication Networks

Подождите немного. Документ загружается.

8 Optimization of OSPF Routing in IP Networks 229

8.7 Selected Extensions

In this section we brieﬂy extend the presentation of the previous sections to cover

several important issues not discussed so far. In particular, we present a full mixed-

integer programming formulation of STEP (Section 8.7.1), discuss additional rout-

ing constraints and various objective functions (Section 8.7.2), show how resource

dimensioning can be taken into account (Section 8.7.3), and show how optimization

of resilient weight systems can be approached (Section 8.7.4). Finally, in Section

8.8, we give historical remarks.

8.7.1 General MIP Formulation

For completeness, a full mixed-integer programming formulation of the basic SPR

problem (STEP) considered earlier in this chapter is given below. The formulation

is explained in detail, so the knowledge of Section 8.2 is sufﬁcient for its under-

standing.

General ECMP Trafﬁc Engineering Problem

ﬁnd

ECMP ﬂow destined to node t induced by system w on link e

common value of the ECMP ﬂow destined to node t, assigned to the links

outgoing from node v and belonging to the shortest paths from v to t

variable indicating whether link e is on a shortest path to node t

length of the w-shortest path from s to t

weight assigned to link e

Z maximum over link utilization factors

minimize

Z (8.18a)

subject to

230 A. Bley et al.

∑

e∈

−

(t)

= D

t ∈ V (8.18b)

∑

e∈

(v)

−

∑

e∈

−

(v)

= d

t ∈ V , v ∈ V \{t} (8.18c)

∑

t∈V \{a(e)}

≤ Zc

e ∈ E (8.18d)

0 ≤ x

≤ D

e ∈ E , t ∈ V \{a(e)} (8.18e)

0 ≤ z

a(e)t

−x

≤ D

(1−u

) e ∈ E , t ∈ V \{a(e)} (8.18f)

1−u

≤ w

+ r

b(e)t

−r

a(e)t

e ∈ E , t ∈ V \{a(e)} (8.18g)

+ r

b(e)t

−r

a(e)t

≤ M(1−u

) e ∈ E , t ∈V \{a(e)} (8.18h)

≥ 1 (s,t) ∈ V

|2|

(8.18i)

= 0 v ∈ V (8.18j)

∈{0,1} e ∈ E , t ∈ V \{a(e)} (8.18k)

∈{1,2,...,K} e ∈ E (8.18l)

x,z, r,Z ≥ 0 (8.18m)

x,z, r,Z ∈ R (8.18n)

Above, M is a constant (”big-M”) not less than the difference in length of any two

paths in the network graph. For example, M = K ·|E | would sufﬁce. Still, for com-

puting lower bounds in the linear relaxations of problem (8.18) it is advantageous to

use an M as small as possible, so this constant can be made dependent on the pairs

of nodes (s,t), and thus potentially reduced for some node pairs.

Subproblem (8.18a)–(8.18d) minimizes the maximum link utilization factor Z

and is an aggregated node-link formulation of a capacitated multi-commodity ﬂow

allocation problem with aggregated ﬂows x, where x

denotes the total trafﬁc des-

tined to node t carried on link e. The next two constraints express the ECMP rule of

trafﬁc routing by means of binary routing variables u. Each variable u

is supposed

to be equal to 1 if, and only if, link e belongs to at least one shortest path (with

respect to weight system w) from its originating node a(e) to node t. Constraint

(8.18e) forces trafﬁc destined to node t to use only the links allowed by the rout-

ing conﬁguration u (i.e., links e ∈ E with u

= 1), while constraint (8.18f) ensures

that in each node the trafﬁc to destination node t is split equally among the links

assigned to that destination. For node v ∈ V and destination t ∈ V this common

value of equal split is expressed by variable z

. Finally, the shortest path routing

constraints (8.18g)–(8.18j) ensure that the routing vector u deﬁnes shortest paths

consistent with the weight system w. Each variable r

is supposed to express the

distance (length of the shortest path with respect to w) from node v to node t.The

quantity q

:= w

+ r

b(e)t

−r

a(e)t

measures the difference between the length of the

shortest path which starts in node a(e), goes over link e, and ends in node t, and the

distance from the starting node of e to t. Thus, link e is on a shortest path to node t

if, and only if, w

+ r

b(e)t

−r

a(e)t

= 0.

The correctness of formulation (8.18) follows easily from the discussion of the

independent STEP master and ISP client models in Section 8.3.

8 Optimization of OSPF Routing in IP Networks 231

Note that in formulation (8.18) the link weights can be either integer (as assumed)

or continuous in interval [1,K]. In the latter case the regularity of the weight system

resulting from (8.18) is assured by constraint (8.18g).

We would like to ﬁnally recall what has already been stated on several occasions,

that because of the intrinsic difﬁculty of STEP, such formulations as (8.18) are virtu-

ally impossible to solve to optimality by contemporary integer programming solvers

for medium-size network instances.

8.7.2 Additional Routing Constraints and Other Objective

Functions

The general STEP formulation (8.18) can be adjusted to a version with a limited

split of ﬂows at the nodes, which can be useful in practice. This is done by adding

the following constraint to formulation (8.18):

∑

e∈

(v)

≤ nv∈ V , t ∈ V \{v}. (8.19)

This constraint forces at most n nonzero ﬂows allowed to each destination t at each

node v ∈ V . Certainly, if we put n = 1, then we will force unsplittable shortest path

routing, admitting only single shortest paths.

The same adjustment can be applied to the STEP formulation (8.3) introduced

in Section 8.3.1. Adding constraint (8.19) with n = 1 and removing variables z and

constraints (8.3e) from formulation (8.3) will result in an integer progamming for-

mulation for the STEP master problem for unsplittable shortest path routing.

There can also be other objective functions used in formulation (8.18). A sim-

ple variant of such a function is the maximization of the minimum unused link

capacity, denoted by Z, with the following constraint in place of constraint (8.18d):

∑

t∈V \{a(e)}

+Z ≤c

, for all links e ∈E . Note that with this objective the problem

is always feasible, provided we allow solutions with Z < 0. However, a true feasible

routing solution is obtained when the resulting objective value is nonnegative.

Another important objective is obtained by using the Kleinrock delay func-

tion [47], to be minimized: F =

∑

e∈E

−y

, where y

denotes the load of link e,

∑

t∈V \{a(e)}

. As with the previous objectives, the Kleinrock function helps

us avoid congestion by penalizing heavily loaded links. Observe that this objec-

tive function is convex, and hence can be approximated with a piecewise linear

function. This leads to linear relaxations of the corresponding convex problem, as

demonstrated in [45] (see also [68]).

As discussed in [43], an issue in these cost function formulations is that they

do not provide a universal measure of congestion. It is natural to require that the

maximum utilization remain below 1, independently of the network topology and

demand matrix. Similarly, we would like a universal cutoff value for the cost func-

tion, independently of the network topology and demand matrix. Fortz and Thorup

deﬁned in [43] a normalized version of the cost function, for which it is natural to

say that a routing solution congests a network if the cost is greater than 1.

232 A. Bley et al.

A comparison between problems with several objective functions can be found

in [50].

8.7.3 Resource Dimensioning

So far we have been investigating versions of STEP with ﬁxed link capacities c

e ∈ E . Still, it can be also important to combine SPR routing optimization with

simultaneous dimensioning of the network resources, such as link and node capaci-

ties. For example, design of an overlay IP network can typically consist in designing

IP link capacities (which will be then leased from the carrier network) and an SPR

weight system to be used to route packets in the network of leased links. The objec-

tive of such a design problem, in addition to keeping link loads reasonable, can be

minimizing the capacity, and hence the cost of the leased links.

Certainly, STEP formulation (8.18) can be extended to cover the new situation.

For that, link capacities c

, e ∈ E , are made variable, and denoted by y

, e ∈ E ,

objective Z can be moved to constraints (Z ≤ 0.8, for example), and the total link

cost

∑

e∈E

can be used in (8.18a) as the objective to be minimized (assuming

certain link unit costs

, e ∈ E , for example, the costs of leasing the link capacity

from the carrier).

Moreover, modularity of link capacity can be taken into account assuming in-

teger values for variables y

, e ∈ E , and the resulting link capacity equal to m ·y

for some ﬁxed module m expressed in Mbit/s. As usual, considering modularity

adds difﬁculty to the problem. Network design problems for SPR of this kind are

discussed in [9, 13, 16, 18, 48, 68].

8.7.4 Resilient Routing

Network elements such as links and nodes are subject to failures, and hence the

resilience issue should be taken into account when designing a weight system w.

In principle, the weight system used in an autonomous system (domain) could be

re-optimized when a failure occurs and then sent out to the routers in order to mod-

ify the packet forwarding tables so that at least the failed links are excluded from

the routing pattern. In practice, such dynamic weight updates are difﬁcult and even

risky to implement. Therefore, another approach to weight resiliency is usually con-

sidered, where the link weights are only modiﬁed by assuming inﬁnite weight for

the failing links. This idea and resulting optimization issues are summarized below.

Let s ∈S denote a failure state, where S is the family of all the considered fail-

ure states (for example, all single link failures), and each failure state is determined

by the set of failing links, i.e., s ⊂E . Now, if failure s occurs, the routers are notiﬁed

about the set s of failing links, and they locally modify the current weight system

8 Optimization of OSPF Routing in IP Networks 233

w to obtain a new system w



, where w



= w

, e ∈ E \s, and w



=+∞, e ∈ s, and

recompute the forwarding tables accordingly.

This weight modiﬁcation strategy can be taken into account at the weight system

design stage, for example by an appropriate modiﬁcation of STEP and its reso-

lution methods. In fact, it is a straightforward exercise to write down a modiﬁca-

tion of problem (8.18) that, for example, minimizes objective Z over all non-failing

links in the normal state and in all the failure states from the assumed failure sce-

nario S [72]. Additionally, in such a formulation we can directly take into account

that demand volumes can be made different in different failure states. Certainly,

these modiﬁcations add difﬁculty to the considered problem (which already in its

basic version is very difﬁcult) and to possible integer programming and heuristic

approaches.

In heuristic approaches the need of computing values of the objective function

for each failure state s ∈ S makes the evaluation of a single weight system very

expensive. To cope with this issue, Fortz and Thorup [44] adapted their local search

heuristic (see Section 8.5.1) by considering only a critical set of failure states, repre-

sentative for the whole failure scenario S . This allows us to achieve resilient weight

systems while keeping the problem manageable in size.

Certainly, resilient routing design can be combined with resource (link) dimen-

sioning; see, for example, [48]. More on design of resilient SPR routing can be

found in [13, 16, 18, 25, 35, 59, 64].

8.8 Historical and Literature Notes

Practical relevance of STEP and related shortest path routing optimization problems

has attracted attention of many researchers in operations research and telecommu-

nications during the last decade. Below, we give a historical survey of the work on

the SPR optimization issues.

Ben-Ameur and Gourdin [5, 6], Brostr

om and Holmberg [21, 22, 27, 28], and

Bley [13] studied the properties of path sets that correspond to (undirected) shortest

path routing patterns, i.e., systems that are generated by weight systems. In partic-

ular, they revealed different necessary conditions for such sets to have a compatible

weight system. Brostr

om and Holmberg considered path sets arising from the ECMP

shortest multi-path routing, while Ben-Ameur, Gourdin, and Bley were focusing on

the unsplittable shortest path routing case. Analyzing the linear model (in partic-

ular its dual) for ﬁnding a weight system inducing a given set of paths, Brostr

and Holmberg [23, 24] have proposed strong compatibility conditions and polyno-

mial algorithms to check whether these conditions are satisﬁed or not. Recently, also

Tomaszewski, Pi

oro et al. studied these issues in [78, 79]. A complete combinatorial

description of all valid paths sets, however, is not known. Bley [13] proved that the

inclusion-wise minimal invalid path sets for unsplittable shortest path routing can

become arbitrarily large and that it is NP-hard to ﬁnd the smallest conﬂict in a given

path set.

234 A. Bley et al.

The inverse shortest paths problem (ISP) was considered by Ben-Ameur and

Gourdin [5, 6], who devised linear and integer programming models for ﬁnding

a weight system that induces a prescribed set of shortest paths (or proves that no

such weights exist). Also Brostr

om and Holmberg [22, 28] considered mixed-integer

linear programming formulations to address the ISP problem. Farago et al. [38, 39]

studied a special case of ISP where the given paths are to be the shortest paths with

respect to the number of links (hops), and the task is to ﬁnd the link weights so that

all these paths are unique shortest paths. Bley [12] showed that ﬁnding a compatible

integer weight system is computationally hard if the range of admissible weights is

bounded.

Several groups studied problems similar to ISP in the context of data reengineer-

ing, where the task is to ﬁnd weights that resemble (as closely as possible) the known

distances or the presumed shortest paths and deviate as little as possible from a given

set of reference link weights. Typically, it is not necessary to exactly match the pre-

sumed shortest paths or distances, and the integrality of the weights is also not an

issue in this context. Burton and Toint [32, 33] solved this problem as a continu-

ous convex quadratic programming problem, while Tong and Lam [80] proposed

a conjugate gradient method for its solution. The computational complexity of this

variant of the inverse shortest paths problem was analyzed by Fekete et al. [40].

As far as the complexity of STEP is concerned, J

uttner et al. [54] showed that it

is NP-hard to ﬁnd a shortest multi-path routing pattern that splits trafﬁc according

to the ECMP rule and whose induced trafﬁc ﬂows do not exceed some given ﬁxed

link capacities. Fortz and Thorup [45] proved that the minimum congestion that

can be obtained with such a routing pattern cannot be polynomially approximated

within a factor less than 3/2, unless P = NP. Bley [11] proved that, for unsplittable

shortest path routing, the problem is inapproximable within a factor of

(|V |

1−

)

for any

> 0. In [15], Bley also proposed several polynomial-time approximation

algorithms for the unsplittable shortest path routing version of STEP and studied

the approximability of the ﬁxed charge and capacitated network design problem

with unsplittable shortest path routing.

One of the ﬁrst mixed-integer programming formulations of the shortest path

routing problem was presented by Bley et al. [16], who considered a (survivable)

network design problem with unsplittable shortest path routing. This formulation

contains binary link routing variables for end-to-end routing paths, integer variables

for the link weights, and continuous variables for the distances between the node

pairs induced by the weights. The interdependencies between the routing path vari-

ables, weights, and the distance variables are expressed analogously as in formula-

tion (8.18), using a quadratic number of linear constraints with big-M coefﬁcients

for the binary arc routing variables. The uniqueness of the shortest paths is guaran-

teed in a quite speciﬁc way by adding a predetermined perturbation to the integer

arc length variables.

Formulation (8.18) for the ECMP version (which works for unique shortest paths

as well) of STEP is due to Tomaszewski and was ﬁrst published in [69] (see also

[70], and Chapter 7 in monograph [68] by Pi

oro and Medhi). Another mixed-integer

programming formulation of this kind was independently proposed by Holmberg

8 Optimization of OSPF Routing in IP Networks 235

and Yuan [52]. Recently, Parmar et al. [67] presented an integer programming ap-

proach for STEP using a formulation analogous to (8.18).

Among the ﬁrst attempts to formulate shortest path routing problems as inte-

ger linear programs without variables for the routing weights were those made by

Staehle et al. [77] and Milbrandt [60]. They proposed mixed-integer programming

models with binary link-ﬂow variables for ﬁnding an unsplittable shortest path rout-

ing pattern that minimizes a linear combination of the maximum and the average

link congestion. These models ensure that the computed routing paths satisfy the

subpath consistency, but they still admit invalid routing patterns as integer solutions.

To our knowledge, the ﬁrst mathematically correct mixed-integer programming

approach without additional variables for the routing weights was presented by Bley

and Koch [18] for a survivable network design problem with unsplittable shortest

path routing. In their model the only binary variables, besides the link capacity vari-

ables, are link routing variables. In order to ensure that a valid unsplittable shortest

path routing pattern is obtained, they separate inequalities of type (8.3f) to cutoff

invalid routing patterns, using the basic approach presented in Section 8.3.

Since then, numerous solution approaches based on the decomposition idea dis-

cussed in Section 8.3 have been presented for different variants of shortest path rout-

ing problems by Bley [13], Bourquia et al. [20], Brostr

om and Holmberg [23, 26]

(network design problem with ECMP based on SP graphs modeled with binary vari-

ables and with subpath consistency ensured by binary variables indicating whether

or not a node is reachable from another node in an SP graph; it is solved with a

Lagrangean heuristic, where feasible solutions are generated using a tabu search

method), Giovanni et al. [48] (minimum cost resilient ﬁxed-charge network design

problem with ECMP; ﬁxed link weights), Pi

oro et al. [69, 70] (unique shortest paths,

meta-heuristics assuring subpath consistency applied in the ﬁrst phase), Eremin

et al. [36] (k-splittable routing), and Tomaszewski et al. [78, 79]. Holmberg and

Yuan [52] generalized the decomposition approach to solve a network design prob-

lem with unsplittable shortest path routing and multicast commodities. This case

was also considered by Prytz [73].

In fact, shortest path routing problems have been more frequently tackled with

heuristic methods than with integer programming methods. This is understandable,

since STEP, as discussed in this chapter, is very difﬁcult to solve with mixed-integer

programming techniques.

A speciﬁc simple approach to ﬁnding a reasonable weight system was proposed

by Pi

oro et al. [69, 70, 76] and independently by Wang et al. [82]. It considers

a linear fractional multi-commodity ﬂow allocation problem (with minimizing the

cost of routing as the objective), and uses the resulting optimal dual variables as the

link weights. A similar approach was also used by Fortz and

Umit [81] as a good

starting solution for a local search approach.

Lagrangian relaxation techniques, local search algorithms, and meta-heuristics,

such as simulated annealing, genetic algorithms, and tabu search, which all use the

link administrative weights as primary decision variables, are conceptually much

easier, and have become quite common to approximately solve shortest path routing

optimization problems. It seems that the ﬁrst successful method to solve the problem

236 A. Bley et al.

using meta-heuristics was proposed by Fortz and Thorup [42, 45]. It was able to ﬁnd

efﬁcient weight systems for large-size networks in reasonable computing time (see

Section 8.5 for details). Other relevant heuristic methods are described in [8, 9, 16,

23, 30, 34, 37, 44, 46, 49, 51, 55, 58, 62, 68, 69].

8.9 Concluding Remarks

The chapter summarizes over a decade research in optimizing weight systems in

the Internet Protocol networks. We have concentrated on a representative problem

referred to as STEP – an optimization problem related to intra-domain trafﬁc en-

gineering in networks based on shortest path routing protocols like OSPF or IS-IS.

Due to great practical relevance, problems of this type have been intensively stud-

ied in the literature. The presented chapter is an attempt to summarize the existing

knowledge with emphasis on the developments achieved by the chapter authors in

their previous work.

We have discussed modeling and resolutions issues of STEP, using the language

and methods of multi-commodity networks, eventually based on integer program-

ming. We have described up-to-date exact and heuristic approaches to STEP, and

summarized the theoretical results underlying the approaches.

We hope that the presented material forms a solid base for both experienced and

less-experienced researchers for getting familiar with the ﬁeld and for adding their

own contributions to it.

Acknowledgements This chapter has been written as a result of a collaboration of its authors

within the EU COST action 293 – Graphs and Algorithms in Communication Networks (GRAAL).

The contribution of Andreas Bley has been partially supported by the DFG Research Center

ATHEON “Mathematics for Key Technologies” and based on a series of research projects on IP

network optimization funded by the German national education and research network DFN and the

German Ministry of Science and Education.

The contribution of Bernard Fortz and Hakan

Umit has been partially supported by the Walloon

Region (DGTRE) in the framework of the TOTEM project. Bernard Fortz is supported by the

Communaut

e franc¸aise de Belgique – Actions de Recherche Concert

ees (ARC). Hakan

Umit is

supported by the FNRS – Bourse de S

ejour Scientiﬁque.

The contribution of K. Holmberg is based on the results of the research projects “Design of

Survivable Communication Networks with Distributed Routing” (Swedish Research Council, grant

2003-5345) and “Directing, Controlling and Modeling IP Network Trafﬁc” (Swedish Research

Council, grant 2006-3227).

The contribution of M. Pi

oro and A. Tomaszewski is based on the results of research projects

“Optimization Models for NGI Core Network” (Polish Ministry of Science and Higher Educa-

tion, grant N517 397334), “Modeling and Design of Core Internet Networks” (Swedish Research

Council, grant 621-2006-5509), and “Global Internet Intra-domain Routing Management” (France

Telecom R&D). Participation of M. Dzida, M. Mycek, M. Zago

zon and M.

Zotkiewicz in this

research is kindly acknowledged.

8 Optimization of OSPF Routing in IP Networks 237

Finally, the authors wish to express their gratitude to the anonymous reviewer whose remarks

based on deep understanding of the shortest path routing helped to improve the ﬁnal version of this

chapter.

References

1. Algorithmic Solutions Software GmbH, Schuetzenstrasse 3–5, D-66123 Saarbruecken, Ger-

many: LEDA—Library of Efﬁcient Data types and Algorithms (2000–2007). URL

http://www.algorithmic-solutions.com/leda

2. atesio GmbH, Sophie-Taeuber-Arp-Weg 27, D-12205 Berlin, Germany: DISCNET – Network

optimization software library (2000–2007). URL http://www.atesio.de

3. Awduche, D.: MPLS and trafﬁc engineering in IP networks. IEEE Communications Magazine

37, 42–47 (1999)

4. Bean, J.: Genetic algorithms and random keys for sequencing and optimization. ORSA J. on

Computing 6, 154–160 (1994)

5. Ben-Ameur, W.: Multi-hour design of survivable classical IP networks. International Journal

of Communication Systems 15, 553–572 (2002)

6. Ben-Ameur, W., Gourdin, E.: Internet routing and related topology issues. SIAM Journal on

Discrete Mathematics 17(1), 18–49 (2003)

7. Ben-Ameur, W., Gourdin, E., Liau, B., Michel, N.: Dimensioning of Internet networks. In:

Proceedings of the 2nd International Workshop on the Design of Reliable Communication

Networks (DRCN 2000), Munich, Germany (2000)

8. Ben-Ameur, W., Gourdin, E., Liau, B., Michel, N.: Optimizing administrative weights for

efﬁcient single-path routing. In: Proceedings of Networks 2000 (2000)

9. Bley, A.: A Lagrangian approach for integrated network design and routing in IP networks. In:

Proceedings of the 1st International Network Optimization Conference (INOC 2003), Paris,

France, pp. 107–113 (2003)

10. Bley, A.: Finding small administrative lengths for shortest path routing. In: Proceedings of the

2nd International Network Optimization Conference (INOC 2005), Lisbon, Portugal, vol. 1,

pp. 121–128 (2005)

11. Bley, A.: On the approximability of the minimum congestion unsplittable shortest path routing

problem. In: Proceedings of the 11th Conference on Integer Programming and Combinatorial

Optimization (IPCO 2005), Berlin, Germany, pp. 97–110 (2005)

12. Bley, A.: Inapproximability results for the inverse shortest paths problem with integer lengths

and unique shortest paths. Networks 50(1), 29–36 (2007)

13. Bley, A.: Routing and capacity optimization for IP networks. Ph.D. thesis, Technische Uni-

vertit

at Berlin (2007)

14. Bley, A.: An integer programming algorithm for routing optimization in IP networks. In:

Proceedings of the 16th Annual European Symposium on Algorithms (ESA 2008), Karlsruhe,

Germany, pp. 198–209 (2008)

15. Bley, A.: Approximability of unsplittable shortest path routing problems. Networks 54(1),

23–46 (2009)

16. Bley, A., Gr

otschel, M., Wess

aly, R.: Design of broadband virtual private networks: Model

and heuristics for the B-WiN. In: N. Dean, D. Hsu, R. Ravi (eds.) Robust Communication

Networks: Interconnection and Survivability, DIMACS Series in Discrete Mathematics and

Theoretical Computer Science, vol. 53, pp. 1–16. American Mathematical Society (1998)

17. Bley, A., Koch, T.: Optimierung des G-WiN. DFN-Mitteilungen 54, 13–15 (2000)

18. Bley, A., Koch, T.: Integer programming approaches to access and backbone IP-network plan-

ning. In: Modeling, Simulation and Optimization of Complex Processes: Proceedings of the

3rd International Conference on High Performance Scientiﬁc Computing, pp. 87–110. Hanoi,

Vietnam (2006)

238 A. Bley et al.

19. Bley, A., Pattloch, M.: Modellierung und Optimierung der X-WiN Plattform. DFN-

Mitteilungen 67, 4–7 (2005)

20. Bourquia, N., Ben-Ameur, W., Gourdin, E., Tolla, P.: Optimal shortest path routing for Internet

networks. In: Proceedings of the 1st International Network Optimization Conference (INOC

2003), Paris, France, pp. 119–125 (2003)

21. Brostr

om, P.: Optimization models and methods for telecommunication networks using OSPF.

PhD dissertation, Link

oping University, Sweden (2006). Link

oping Studies in Science and

Technology. Dissertation no. 1032

22. Brostr

om, P., Holmberg, K.: Determining the non-existence of compatibel OSPF weights. In:

D. Yuan (ed.) Nordic MPS 2004, no. 14 in Link

oping Electronic Conference Proceedings, pp.

7–21. Link

oping University Electronic Press (2004)

23. Brostr

om, P., Holmberg, K.: Design of IP/OSPF networks using a Lagrangean heuristic on an

in-graph based model. In: L. Gouveia, C. Mourao (eds.) INOC 2005, pp. 702–709. University

of Lisbon, Lisbon, Portugal (2005)

24. Brostr

om, P., Holmberg, K.: Determining the non-existance of a compatible OSPF metric.

In: L. Gouveia, C. Mourao (eds.) INOC 2005, pp. 702–709. University of Lisbon, Lisbon,

Portugal (2005)

25. Brostr

om, P., Holmberg, K.: Multiobjective design of survivable IP networks. Annals of Op-

erations Research 147 (2006)

26. Brostr

om, P., Holmberg, K.: Design of OSPF networks using subpath consistent routing pat-

terns. Research Report LiTH-MAT-R-2007-05, Department of Mathematics, Link

oping Insti-

tute of Technology, Sweden (2007). Under revision for publication.

27. Brostr

om, P., Holmberg, K.: On the extremal structure of an OSPF related cone. Vietnam

Journal on Mathematics 35(4), 507–522 (2007)

28. Brostr

om, P., Holmberg, K.: Valid cycles: A source of infeasibility in OSPF routing. Networks

52(4), 206–215 (2008)

29. Brostr

om, P., Holmberg, K.: Compatible weights and valid cycles in non-spanning OSPF rout-

ing patterns. Algorithmic Operations Research 4, 19–35 (2009)

30. Buriol, L. S., Resende, M. G. C., Ribeiro, C. C., Thorup, M.: A hybrid genetic algorithm for

the weight setting problem in OSPF/IS-IS routing. Networks 46(1), 36–56 (2005)

31. Buriol, L. S., Resende, M. G. C., Thorup, M.: Speeding Up Dynamic Shortest-Path Algo-

rithms. INFORMS Journal On Computing 20(2), 191–204 (2008)

32. Burton, D.: On the inverse shortest path problem. Ph.D. thesis, Department of Mathematics,

Facult

es Universitaires ND de la Paix, Namur, Belgium (1993)

33. Burton, D., Toint, P.: On an instance of the inverse shortest paths problem. Mathematical

Programming 53, 45–61 (1992)

34. Dzida, M., Petterson, M., Duelli, M., Zago

zon, M., Pi

oro, M., Menth, M.,

Zotkiewicz, M.:

Three methods for optimizing single-shortest path routing. In: NGI 2008 Conference on Next

Generation Internet Networks, Cracow, Poland (2008)

35. Dzida, M., Zago

zon, M., Pi

oro, M.: Optimization of resilient weight systems for shortest-

path routing in IP networks. In: 6th International Workshop on Design and Reliable Commu-

nication Networks. La Rochelle, France (2007)

36. Eremin, A., Ajili, F., Rodosek, R.: A set-based approach to the optimal IGP weight setting

problem. In: Proceedings of the 2nd International Network Optimization Conference (INOC

2005), Lisbon, Portugal, vol. 1, pp. 386–392 (2005)

37. Ericsson, M., Resende, M. G. C., P. M., P.: A genetic algorithm for the weight setting problem

in OSPF routing. J. of Combinatorial Optimization 6, 299–333 (2002)

38. Farago, A., Szentesi, A., Szviatovszki, B.: Allocation of administrative weights in PNNI. In:

Proceedings of Networks ’98, Sorrento, Italy, pp. 621–625 (1998)

39. Farago, A., Szentesi, A., Szviatovszki, B.: Inverse optimization in high-speed networks. Dis-

crete Applied Mathematics 129, 83–98 (2003)

40. Fekete, S., Hochst

attler, W., Kromberg, S., Moll, C.: The complexity of an inverse shortest

path problem. In: R. Graham, J. Kratochv

ıl, J. Nesetril, F. Roberts (eds.) Contemporary Trends

in Discrete Mathematics: From DIMACS and DIMATIA to the Future, vol. 49, pp. 113–127.

AMS (1999)