Distance-vector routing
Let routers learn routes by trading their distance tables with neighbours, and see how bad news travels slowly. About 15 minutes.
What does split horizon do?
- AA router doesn't advertise a route back out of the interface it learned it from
- BIt splits the routing table in half
- CIt splits traffic across two links
Show the answer
A router doesn't advertise a route back out of the interface it learned it from. That prevents two neighbours from feeding each other's stale information.
Distance-vector routing
A network has n routers numbered 0 to n − 1. Router me has direct links described by linkCosts: linkCosts[j] is the cost of its link to router j, or −1 if j is not a direct neighbour (the entry for me is ignored). vectors[j] is the vector last advertised by router j: vectors[j][d] is j's cost to destination d, or −1 if unreachable. Return me's new vector: for d = me the cost is 0, otherwise the minimum over neighbours j of linkCosts[j] + vectors[j][d] using only neighbours that can reach d, or −1 if there is none.
me = 0, linkCosts = [0, 2, 5, -1], vectors = [[0, -1, -1, -1], [2, 0, 1, 4], [5, 1, 0, 1], [-1, -1, -1, 0]] → [0, 2, 3, 6]
1 ≤ n ≤ 8 · link costs 1 to 100 or −1 · vector entries 0 to 1000 or −1