867
Comment: missing edit-log entry for this revision
|
1542
|
Deletions are marked like this. | Additions are marked like this. |
Line 21: | 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 || |
Back to ComputerTerms
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