Diff for "LinkState"

Differences between revisions 1 and 10 (spanning 9 versions)

Link State Protocol

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

ID of the node that created the LSP
List of directly connected neighbors, cost of link
A sequence number
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

-  ⇤ ← Revision 1 as of 2003-09-12 17:57:20 → 
  Size: 261
  Editor: pcp025745pcs
  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 1:
+Back to ComputerTerms
-Line 4:
+Line 6:
-   * What: Send Link stata packet about dirrect connected links
+   * What: Send Link state packet (LSP) about direct connected links
-Line 6:
+Line 8:
+   * How: Reliable flooding
-Line 7:
+Line 10:
-Local information globally
+The point is that Local information is distributed globally.
-Line 9:
+Line 12:
-Uses OpenShortestPathFirst OSPF algorithm
+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