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?

**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….**

*OSPF (Open Shortest Path First)**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

4.1 Menu

4.2 Arguments

4.3 Information

Chapter 5: Computational tests and results

5.1 Generating modified SP-graphs

5.2 Information about the examples used

5.3 Introduction to running the program

5.4 Results from running the program

Erik Haraldsson, 2008 – vii -5.5 About *Valid Cycles*

5.6 Conclusions…

Source: Linköping University

Download URL 2: Visit Now