How do distance-vector and link-state routing protocols differ in what each router learns and how it computes its routes?

## Two ways to build a routing table Every dynamic routing protocol solves the same problem: each router must find, for every destination prefix, the neighbour that leads there most cheaply, and keep that answer right as links fail and recover. RFC 1812, the IPv4 router requirements, notes that interior routing protocols are characterised as based on either a **distance-vector** or a **link-state** algorithm. The difference is what a router is told, and therefore what it can compute. ## Distance-vector: trust what the neighbours say A distance-vector router knows its own links and what its neighbours claim, nothing more. The cycle is: 1. Each router starts with its directly connected networks at a small distance. 2. Periodically, or when something changes, each router sends its neighbours a **vector** of (destination, distance) pairs: its whole view of the network. 3. On receiving a neighbour's vector, a router computes, for each destination, `neighbour's distance + cost of the link to that neighbour`, and keeps the neighbour giving the minimum. 4. If its own table changed, it advertises the new vector, and the change ripples outward one router at a time. This is the **Bellman-Ford** shortest-path computation, spread across the routers; RFC 1812 uses 'distance vector' and 'Bellman-Ford' as names for the same technology. It is often summarised as routing by rumour: a router believes a distance without knowing the path behind it. ## The cost of rumours: counting to infinity Take three routers in a line, A, B and C, with network N attached to C. C reaches N at distance 1, B at 2 through C, and A at 3 through B. Now C's link to N fails. If, before C's news reaches B, C hears B's vector still claiming N at distance 2, C concludes it can reach N at 3 through B, although B's path runs through C. B then hears 3 from C, its next hop, and moves to 4; each exchange raises the number by one. Packets for N loop between B and C while the distances count upward until they reach the protocol's 'unreachable' value. Distance-vector protocols therefore add loop-prevention rules such as **split horizon** (never advertise a route back to the neighbour it was learned from; RFC 1812 requires it of RIP), **poisoned reverse** and **holddown** timers. Each protocol's own timers and limits are a subject of their own. ## Link-state: everyone holds the map A link-state router describes itself instead of repeating what it heard: 1. Each router discovers its neighbours and the cost of each of its links. 2. It packages that description into a **link-state advertisement** and **floods** it: every router passes it on unchanged to its neighbours, so it reaches every router in the area. 3. Every router therefore holds an identical **link-state database**, a full map of routers, links and costs. 4. Each router runs **Dijkstra's shortest-path-first (SPF)** algorithm over that map, rooted at itself, and derives its routing table. RFC 1812 describes exactly this for OSPF: each router 'obtains the entire topology database through a process known as flooding' and then runs the SPF algorithm on it. IS-IS works the same way. Because a failure is flooded as a fact rather than relayed as a recalculated distance, every router hears of it quickly and recomputes from the same facts, so the long counting loops of distance-vector do not occur, although routers can briefly disagree, and loop packets, while a flood is still in flight. ## Side by side | | Distance-vector | Link-state | |---|---|---| | What a router learns | Neighbours' distances to each destination | Every router's own links, flooded | | Computation | Bellman-Ford, spread across routers | Dijkstra SPF, run by every router | | View of the network | Next hop and distance only | Whole topology of the area | | After a failure | Slow, exchange by exchange; can count to infinity | Fast: flood, then recompute | | Resource cost | Low memory and CPU | Database memory, SPF CPU, areas to scale | | Examples | RIP | OSPF, IS-IS | ## Protocols that do not fit neatly - **EIGRP** is usually described as an advanced distance-vector protocol: it still learns neighbours' distances, but adds a loop-free condition for accepting a path and keeps backup paths ready, which avoids counting to infinity. - **BGP** is neither. For each prefix it carries the complete list of autonomous systems a route has crossed, as RFC 1812 describes, and rejects any route that already contains its own; it is commonly called a **path-vector** protocol. ## Where answers go wrong - Saying link-state routers exchange routing tables. They exchange link descriptions, and each builds its own table. - Saying distance-vector routers run Dijkstra. They combine neighbours' claims; no router sees the whole graph. - Claiming link-state is always the better choice. On a small stub network a distance-vector protocol, or simply a static route, can be simpler and adequate.