Routing Algorithms
| Distance Vector | Link State | |
|---|---|---|
| Algorithm | Bellman-Ford | Dijkstra |
| Knowledge | Each router knows only its neighbours' tables | Each router knows the full topology |
| Updates | Periodic, whole table to neighbours | Link-state packets flooded to all routers when a link changes |
| Problem | Count-to-infinity (fixed by split horizon, poison reverse) | More memory and CPU |
| Protocol | RIP (max 15 hops) | OSPF |
Distance Vector Update
D_x(y) = min over neighbours v { c(x, v) + D_v(y) }
Router A, neighbours B (cost 2) and C (cost 5)
B says: dist to D = 4 C says: dist to D = 1
D_A(D) = min(2 + 4, 5 + 1) = 6 (tie; either next hop works)Inter-domain Routing
BGP (Border Gateway Protocol) is a path-vector protocol used between autonomous systems on the Internet.
Track your progress through the Computer Networks course