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.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:liu-58617 |
| Date | January 2010 |
| Creators | Morén, Björn |
| Publisher | Linköpings universitet, Optimeringslära, Linköpings universitet |
| Source Sets | DiVA Archive at Upsalla University |
| Language | Swedish |
| Detected Language | Swedish |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0022 seconds