Adaptive and non-adaptive routing algorithms

Routing is the process by which a node (router or packet switch) decides the outgoing link for a packet so it reaches its destination. Routing algorithms are of two kinds: non-adaptive (static) and adaptive (dynamic).

Non-adaptive (static) routing

Routes are computed in advance (off-line) and loaded into the routers; they do not change with current traffic or topology, unless an administrator changes them.

Examples

1. Shortest path routing: the network is a graph with link costs (distance, delay); Dijkstra's algorithm finds the least-cost path from each source, and the tables are fixed.
2. Flooding: every incoming packet is sent on every outgoing line except the one it came on; hop counters or sequence numbers stop endless copies. Very robust, used in military networks and for broadcasting link-state updates.
3. Flow-based routing: uses known average traffic between node pairs and link capacities to choose routes that minimise mean delay.
4. Fixed/static routes configured by hand (e.g. default route).

Features: simple, low processing and no routing traffic, predictable; but cannot react to failures or congestion.

Adaptive (dynamic) routing

Routes are changed automatically in response to changes in topology and traffic load. Routers exchange information and recompute paths periodically or when a change occurs.

Types by where decisions are made

• Centralised: a routing control centre collects information and sends tables to all nodes.
• Isolated: each node decides from local information only, e.g. hot-potato routing (send on the shortest queue) or backward learning.
• Distributed: nodes exchange information with neighbours.

Main distributed algorithms

1. Distance vector routing (Bellman–Ford): each router keeps a table of the best known distance to every destination and the next hop, and periodically sends it to neighbours. Used in RIP. Simple but suffers from the count-to-infinity problem and slow convergence.
2. Link state routing: each router learns its neighbours and link costs, floods link state packets to all routers, builds the full topology and runs Dijkstra. Used in OSPF and IS-IS. Converges fast, larger memory and CPU.

   A --2-- B --1-- D
   |       |       |
   5       2       1
   |       |       |
   C --3-- E ------+
 If link B-D fails, adaptive routing
 finds A-B-E-D; static routing keeps
 using B-D and the packets are lost.

Comparison