Ruttningen av trafik i IP-nätverk sker ofta med hjälp av bågvikter som bestämmer vilken väg trafiken tar (kortastevägruttning). Problemet här är att avgöra ifall det existerar en uppsättning vikter givet ett önskat ruttningsschema. Den hör rapporten undersöker prestandan hos ett antal modeller och optimeringsprogram avsedda att lösa denna typ av problem som ofta kallas inversa kortastevägruttningsproblemet. Undersökningen visar att det existerar en stor skillnad mellan modellerna och optimeringsprogrammen och att modellen baserad på cykelbaser löst med CPLEXdualopt lösaren är snabbast. / The routing of traffic in IP networks is often done with a set of weights that determinewhich way the traffic will go (shortest path routing). The problem here is todetermine if there exists a set of weights for a desired routing pattern. This thesis willinvestigate the performance of a number of different models and solvers for solvingthis type of problem which is usually called the inverse shortest path routing (ISPR)problem. The models tested are the same as described in [1]. The different solversused are mainly the linear CPLEX solvers but also a few multi commodity networksolvers. The tests showed that there is a big performance difference between the models andsolvers and that the cycle bases model solved with the CPLEX dualopt solver wasthe fastest overall.

<p>Within telecommunication and routing of traffic in IP-networks a protocol named“Open Shortest Path First” (OSPF) is widely used. This means that a server dealswith the routing over a network with given weights by calculating shortest paths touse for routing. If we assume that a desired traffic pattern is given the problem isto find out if it is possible to set the weights so that the desired traffic pattern is apart of a shortest path graph. In this thesis we assume that it is a unique shortestpath. To search for weights that solve the problem leads to a complex LP-model. Analternative is to search in the LP-dual under certain restrictions. These solutions tothe LP-dual are called conflicts and a conflict means that there exists no weights sothat the desired traffic pattern is obtained. The goal of this thesis is to study, classifyand search for conflicts. An algorithm has been developed that finds some kind ofconflicts in polynomial time with respect to the size of the graph.</p> / <p>Inom telekommunikation och ruttning av datatrafik i IP-nätverk så används oftaett protokoll som kallas “Open Shortest Path First” (OSPF). Det innebär att enserver sköter ruttningen över ett nätverk genom att utifrån givna bågkostnaderberäkna billigaste vägar som används för ruttningen. Frågeställningen utgårfrån att vi har ett önskat ruttningsschema och vi vill ta reda på om det gåratt sätta bågkostnader så att det önskade ruttningsschemat ingår i en billigasteväg-graf. I det här examensarbetet splittas inte trafik utan varje billigaste vägär unik mellan två noder. Att söka efter bågkostnader som löser problemet geren krävande LP-modell och ett alternativ är att utgå från LP-dualen undervissa restriktioner. Dessa lösningar till LP-dualen benämns konflikter och enkonflikt motsvarar att det inte finns några bågkostnader så att det önskaderuttningsschemat fås. Målet med examensarbetet är att studera, klassificeraoch söka efter konflikter. En algoritm har tagits fram som hittar vissa typer avsådana konflikter i polynomiell tid, sett till storleken på grafen.</p>

Within telecommunication and routing of traffic in IP-networks a protocol named“Open Shortest Path First” (OSPF) is widely used. This means that a server dealswith the routing over a network with given weights by calculating shortest paths touse for routing. If we assume that a desired traffic pattern is given the problem isto find out if it is possible to set the weights so that the desired traffic pattern is apart of a shortest path graph. In this thesis we assume that it is a unique shortestpath. To search for weights that solve the problem leads to a complex LP-model. Analternative is to search in the LP-dual under certain restrictions. These solutions tothe LP-dual are called conflicts and a conflict means that there exists no weights sothat the desired traffic pattern is obtained. The goal of this thesis is to study, classifyand search for conflicts. An algorithm has been developed that finds some kind ofconflicts in polynomial time with respect to the size of the graph. / Inom telekommunikation och ruttning av datatrafik i IP-nätverk så används oftaett protokoll som kallas “Open Shortest Path First” (OSPF). Det innebär att enserver sköter ruttningen över ett nätverk genom att utifrån givna bågkostnaderberäkna billigaste vägar som används för ruttningen. Frågeställningen utgårfrån att vi har ett önskat ruttningsschema och vi vill ta reda på om det gåratt sätta bågkostnader så att det önskade ruttningsschemat ingår i en billigasteväg-graf. I det här examensarbetet splittas inte trafik utan varje billigaste vägär unik mellan två noder. Att söka efter bågkostnader som löser problemet geren krävande LP-modell och ett alternativ är att utgå från LP-dualen undervissa restriktioner. Dessa lösningar till LP-dualen benämns konflikter och enkonflikt motsvarar att det inte finns några bågkostnader så att det önskaderuttningsschemat fås. Målet med examensarbetet är att studera, klassificeraoch söka efter konflikter. En algoritm har tagits fram som hittar vissa typer avsådana konflikter i polynomiell tid, sett till storleken på grafen.