liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Icke-triviala billigaste väg-ruttningskonflikter - klassificering och sökmetoder
Linköping University, Department of Mathematics, Optimization . Linköping University.
2010 (Swedish)Independent thesis Basic level (degree of Bachelor), 15 credits / 22,5 HE creditsStudent thesisAlternative title
Non-triivial shortest path routing conflicts - classification and search methods (English)
Abstract [en]

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.

Abstract [sv]

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.

Place, publisher, year, edition, pages
2010. , 31 p.
Keyword [en]
OSPF, SPR-conflicts, SPRD, ISPR, classification, search methods
Keyword [sv]
OSPF, BVR-konflikter, design av BVR, inversa billigaste väg- problem, klassificering, sökmetoder.
National Category
Computational Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-58617ISRN: LiTH-MAT-EX--2010/19--SEOAI: oai:DiVA.org:liu-58617DiVA: diva2:345479
Presentation
2010-06-08, Kompakta rummet, Linköping, 10:00 (Swedish)
Uppsok
Physics, Chemistry, Mathematics
Supervisors
Examiners
Available from: 2010-08-31 Created: 2010-08-18 Last updated: 2010-08-31Bibliographically approved

Open Access in DiVA

fulltext(319 kB)479 downloads
File information
File name FULLTEXT01.pdfFile size 319 kBChecksum SHA-512
18e5ee088b7e195cb99b776ab029364f94b4cfbba811abbba10514860c1b2c2d51633e63bd430ee9d68f642e01c92bba09d5889e3df4350295f4166d12c6b9a4
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Morén, Björn
By organisation
Optimization Linköping University
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 479 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 319 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf