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
Combining unobtainable shortest path graphs for OSPF
Linköping University, Department of Mathematics.
2008 (English)Independent thesis Advanced level (degree of Master), 25 points / 37,5 hpStudent thesis
Abstract [en]

The well-known Dijkstra's algorithm uses weights to determine the shortest path. The focus here is instead on the opposite problem, does there exist weights for a certain set of shortest paths? OSPF (Open Shortest Path First) is one of several possible protocols that determines how routers will send data in a network like the internet. Network operators would however like to have some control of how the traffic is routed, and being able to determine the weights, which would lead to the desired shortest paths to be used, would be a help in this task.The first part of this thesis is a mathematical explanation of the problem with a lot of examples to make it easier to understand. The focus here is on trying to combine several routing patterns into one, so that the result will be fewer, but more fully spanned, routing patterns, and it can e.g. be shown that there can't exist a common set of weights if two routing patterns can't be combined.The second part is a program that can be used to make several tests and changes to a set of routing patterns. It has a polynomial implementation of a function that can combine routing patterns. The examples that I used to combine routing patterns, showed that this will increase the likelihood of finding and significantly speed up the computation of a “valid cycle”.

Place, publisher, year, edition, pages
2008. , 81 p.
Keyword
Internet Protocol, OSPF, combining SP-graphs, valid cycle, subpath consistency
National Category
Mathematics Computational Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-12401ISRN: LITH-MAT-EX--2008/07--SEOAI: oai:DiVA.org:liu-12401DiVA: diva2:112
Presentation
(English)
Uppsok
fysik/kemi/matematik
Supervisors
Examiners
Note
Egentligen 30p/45hp, men det fanns inte som alternativ.Available from: 2008-10-15 Created: 2008-09-03 Last updated: 2008-10-15Bibliographically approved

Open Access in DiVA

fulltext(654 kB)947 downloads
File information
File name FULLTEXT01.pdfFile size 654 kBChecksum SHA-512
a781a6f5cd2e3e480e966fcfb67626473df106c541c1c5d8f08610e875ff62d9922b13d92b19cbf54834b84a5f20d0bed288489b097a303aeacc3236e6add3ce
Type fulltextMimetype application/pdf

By organisation
Department of Mathematics
MathematicsComputational Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 947 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: 355 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