Routing algorithms and protocols
Routing decides the paths packets take. Inside a network, routers compute least-cost paths; between networks, policy and business relationships matter as much as distance.
Routing as a graph problem
A network can be modelled as a graph whose nodes are routers and whose edges are links with costs, which might reflect delay, capacity, or administrative preference. A routing algorithm finds least-cost paths from each router to every destination. Algorithms are either centralised, with global knowledge of the topology, or decentralised, with each router knowing only its neighbours.
Link-state routing
In link-state routing, each router floods information about its own links to all routers, so every router builds a complete map of the network and runs Dijkstra's algorithm to compute shortest paths. OSPF (Open Shortest Path First) and IS-IS are link-state protocols, widely used inside ISPs and large enterprises. They converge quickly after changes because every router recomputes from full information.
Distance-vector routing
In distance-vector routing, each router keeps its estimated distance to every destination and shares that vector with its neighbours, updating its own estimates using the Bellman-Ford equation: my cost to D is the minimum over neighbours of the link cost to the neighbour plus the neighbour's cost to D. RIP is a classic example. It is simple but can converge slowly and suffer the count-to-infinity problem after failures.
Autonomous systems
The internet is divided into autonomous systems (ASes), each a network under one administration, such as an ISP, university, or cloud provider, identified by an AS number. There are over 100,000 assigned AS numbers, with tens of thousands active in global routing. Intra-AS routing (OSPF, IS-IS) chooses paths inside an AS; inter-AS routing connects them.
BGP
The Border Gateway Protocol (BGP) is the internet's inter-AS routing protocol; its current version, BGP-4, dates from 1994 and is specified in RFC 4271. ASes advertise reachable prefixes to neighbours along with the AS path, the list of ASes a route passes through. BGP is a path-vector protocol: AS paths let routers reject loops and apply policies.
Policy routing
BGP route selection is driven by policy, not just distance. An AS typically prefers routes learned from customers (who pay it), then from peers (exchanging traffic for free), then from providers (whom it pays). It usually does not carry traffic between two of its providers for free. Among equal preferences, shorter AS paths win. This business logic shapes how traffic actually flows.
Routing security
BGP originally trusted what neighbours announced. Misconfigurations or attacks can 'hijack' prefixes by announcing them falsely, diverting traffic, as in a 2008 incident when Pakistan Telecom's announcement for YouTube's addresses spread worldwide and took YouTube offline for hours. Resource Public Key Infrastructure (RPKI) lets networks cryptographically validate which AS may originate a prefix, and adoption has grown steadily.
Worked example
Distance vector: router A has links to B (cost 1) and C (cost 4). B reports cost 2 to destination D; C reports cost 1 to D. A computes min(1 + 2, 4 + 1) = 3 via B. If the B-to-D route fails and B, before hearing the news, receives A's old advertisement of cost 3, B may wrongly set cost 4 via A, and the two routers count upwards slowly: count to infinity. Split horizon with poisoned reverse reduces the problem.
Key takeaways
Routing finds least-cost paths in a graph of routers and links. Link-state protocols such as OSPF and IS-IS flood link information and run Dijkstra's algorithm, converging quickly. Distance-vector protocols such as RIP exchange distance estimates using Bellman-Ford and can count to infinity. The internet consists of autonomous systems; intra-AS protocols route inside them. BGP-4 (1994, RFC 4271) is the path-vector protocol between ASes, advertising prefixes with AS paths. BGP choices follow business policy: customers, then peers, then providers. Prefix hijacks, such as the 2008 YouTube outage, motivate RPKI validation.
Flashcard
Weight assigned to a link
Check your understanding
Why might a BGP router choose a longer AS path over a shorter one?