Distance vector and link state routing

Routing goal and graph model

Definition. Routing selects paths through a network graph. Routers are vertices, links are edges, and edge weights represent a chosen cost such as delay, hop count, or administrative metric. A routing algorithm computes next hops or paths using local or distributed information. Example. A router chooses a path of cost 3 through B rather than a direct link of cost 8. Exam point. Routing metric is not automatically physical distance or hop count.

Forwarding versus routing

Definition. Routing computes or maintains paths and populates forwarding information. Forwarding examines a packet’s destination and sends it to the next hop selected by a forwarding table. Routing is a control-plane process; forwarding is a per-packet data-plane action. Example. A routing update changes the table; a later packet lookup uses the new next hop. Exam point. A forwarding table normally maps destination prefixes to next hops and output interfaces.

Routing table and longest-prefix match

Definition. An IP forwarding table can contain destination prefixes, next-hop addresses, and output interfaces. When multiple prefixes match a destination, the router selects the most specific prefix, meaning the one with the greatest prefix length. A default route is used if no more-specific route matches. Example. Destination 10.4.2.9 matches 10.4.0.0/16 and 10.4.2.0/24; the /24 route wins. Exam point. Longest-prefix match is based on prefix length, not lowest numeric next-hop address.

Destination prefix	Next hop	Interface
10.4.2.0/24	192.0.2.6	eth1
10.4.0.0/16	192.0.2.2	eth0
0.0.0.0/0	198.51.100.1	eth2

Distance-vector routing principle

Definition. Each router maintains a distance estimate to destinations and shares its vector with neighbors. Bellman–Ford updates cost to destination y through neighbor v as $c(x,v)+D_v(y)$, taking the minimum over neighbors. Routers need not know the complete topology. Example. If link x–a costs 2 and a’s estimate to y is 5, x can estimate a path of cost 7 through a. Exam point. Neighbor advertisement contains its distance estimate, not the path cost including x’s own link.

Bellman–Ford update example

Definition. A synchronous distance-vector round uses the neighbor vectors from the previous round. Each node keeps cost zero to itself and infinity to unreachable nodes, then relaxes each destination through every neighbor. Asynchronous protocols may update at different times but follow the same minimum-cost recurrence. Example. Links A-B=2, B-C=1, A-C=7. Determine A’s cost to C after B’s vector is known. Exam point. A direct route may lose to a cheaper multi-hop path.

Candidate from A to C	Cost
Direct A-C	7
Via B: A-B + B-C	2+1=3

So A records cost 3 and next hop B. B’s cost to C is 1; it advertises that value to A. A adds its own link cost 2.

Distance-vector iteration table

Definition. A distance-vector trace should show each node’s current costs after each exchange. For a line topology, information about a far destination may advance one hop per synchronous round. A node changes its next hop when a strictly lower candidate becomes available. Example. A-B-C-D with each link cost 1; initially each router knows direct neighbors only. Exam point. State whether the problem assumes synchronous rounds or event-driven updates.

Round	A’s estimate to D	B’s estimate to D	C’s estimate to D
0	∞	∞	1
1	∞	2	1
2	3	2	1
3	3	2	1

The destination D itself starts at cost 0. In round 1, C advertises cost 1 to B, so B learns cost 2. In round 2, B advertises 2 to A, so A learns 3.