# Combining unobtainable shortest path graphs for OSPF

The well-known Dijkstra’s algorithm utilizes weights to look for the shortest path. The target here’s rather on the opposite problem, does there exist weights for a certain set of shortest paths? OSPF (Open Shortest Path First) is among several feasible protocols which establishes how routers will be sending data in a network such as internet. Network operators would however like to get some control of how the traffic is sent, and having the ability to determine the weights, which may lead to the desired shortest paths to be used, would be a aid in this task. The beginning of this dissertation is a mathematical explanation of the challenge with a lot of cases to make it simpler to understand. The main objective here is on attempting to combine several routing patterns into one, to ensure the result will be fewer, but more fully spanned, routing patterns, and it can e.g. be shown that there cannot exist a common set of weights if 2 routing patterns cannot be combined. The next portion is a program which you can utilize to create many tests and changes to a set of routing patterns….

Contents

Chapter 1: Introduction
1.1 Background
1.2 Problem/Purpose
1.3 Outline
Chapter 2: Theoretical Description
2.1 Definitions
2.2 Mathematical model
2.3 Valid cycle
2.4 Subpath consistency
2.5 Restrictions to combining SP-graphs
2.6 Summary
Chapter 3: Mechanisms of the Program
3.1 Introduction
3.2 Running Times
3.3 The structure of my program
3.4 Storage
3.5 Startup
3.6 The use of DFS
3.7 How to divide SP-graphs
3.8 How to check in order to combine SP-graphs
3.9 How to combine SP-graphs
3.10 Remove extra SP-graphs
3.11 Check for subpath consistency
3.12 Changing SP-graphs
3.13 Check valid cycles
3.14 Summary
3.15 List of complexities
Chapter 4: Mechanisms of the Program