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

Direct link
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.
Internet Protocol, OSPF, combining SP-graphs, valid cycle, subpath consistency
National Category
Mathematics Computational Mathematics
URN: urn:nbn:se:liu:diva-12401ISRN: LITH-MAT-EX--2008/07--SEOAI: diva2:112
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)870 downloads
File information
File name FULLTEXT01.pdfFile size 654 kBChecksum SHA-512
Type fulltextMimetype application/pdf

By organisation
Department of Mathematics
MathematicsComputational Mathematics

Search outside of DiVA

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

Total: 339 hits
ReferencesLink to record
Permanent link

Direct link