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
4Dijkstra'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
LinkState is fast statble and takes a log of space.
- It is founded upon reliable flooding.
Back to ComputerTerms