Back to ComputerTerms

The point is that Local information is distributed globally.

The LSP information recieved is used to create a graph of the network. Then routing is easy because we use DijkstrasAlgorithm, to find the shortest path. See cse952lec03.pdf. The LSP contains the following information

  1. ID of the node that created the LSP
  2. List of directly connected neighbors, cost of link
  3. A sequence number
  4. TTL

OpenShortestPathFirst OSPF is an example protocol

Given a network that looks like

         2
    A---------C
    |\       / \
    | \5    /2  \1
    |  \   /     \
   3|    D        F
    |  /   \     /
    | /1    \3  /2
    |/       \ /
    B---------E
         4

Dijkstra's Algorithm goes through the following steps:

Step

Confirmed

Tentative

1

(A,0,-)

(C,2,C),(B,3,B),(D,5,D)

2

(A,0,-),(C,2,C)

(B,3,B),(D,4,C),(F,3,C)

3

(A,0,-),(C,2,C),(B,3,B)

(D,4,C),(F,3,C),(E,7,B)

4

(A,0,-),(C,2,C),(B,3,B),(F,3,C)

(D,4,C),(E,5,C)

5

(A,0,-),(C,2,C),(B,3,B),(F,3,C),(D,4,C)

(E,5,C)

6

(A,0,-),(C,2,C),(B,3,B),(F,3,C),(D,4,C),(E,5,C)

None

This produces the following routing tables

Destination

Next Hop

Cost

A

-

0

C

C

2

B

B

3

F

C

3

D

C

4

E

C

5

Alternately we could have just written line 6.

Plus

Back to ComputerTerms

LinkState (last edited 2004-03-17 21:32:02 by yakko)