Differences between revisions 9 and 10
⇤ ← Revision 9 as of 2003-09-25 17:54:30 →
Size: 706
Editor: yakko
Comment:
← Revision 10 as of 2004-03-17 21:08:41 → ⇥
Size: 1542
Editor: yakko
Comment:
Deletions are marked like this. Additions are marked like this.
Line 8: Line 8:
   * How: Reliable flooding
Line 13: Line 14:
1. ID of the node that created the LSP
2. List of directly connected neighbors, cost of link
3. A sequence number
4. TTL		    1. ID of the node that created the LSP
   2. List of directly connected neighbors, cost of link
   3. A sequence number
   4. TTL
Line 20: Line 21:
Given a network that looks like

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

Dijkstra's Algorithm produces:

||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 ||

=== Plus ===

   * LinkState is fast statble and takes a log of space.
   * It is founded upon reliable flooding.

Back to ComputerTerms

  • Who: Send to all nodes
  • What: Send Link state packet (LSP) about direct connected links
  • When: Periodically or when a change occurs (triggered)
  • How: Reliable flooding

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 produces:

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

Plus

  • LinkState is fast statble and takes a log of space.

  • It is founded upon reliable flooding.

Back to ComputerTerms

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