Static and dynamic routing algorithms

A routing algorithm decides the output line on which a router forwards each packet so that it reaches its destination. Routing algorithms are of two main kinds: static (non-adaptive) and dynamic (adaptive).

Static (non-adaptive) routing

Routes are computed in advance and loaded into the routers (by the administrator or an offline program). They do not change with traffic or topology until changed manually.

• Shortest path routing: the network is drawn as a graph with link weights (distance, delay, cost); Dijkstra's algorithm finds the least-cost path, which is stored in the table.
• Flooding: each packet is sent on all output lines except the input one; a hop counter limits copies. Very robust, used where reliability is vital or for broadcasting.
• Flow-based routing: uses known average traffic between nodes and link capacities to pick routes with least average delay.

Advantages: simple, no routing overhead, predictable, secure. Disadvantages: cannot react to failures or congestion; unsuitable for large changing networks.

Dynamic (adaptive) routing

Routers exchange information and change routes automatically when topology or load changes.

• Centralized: one Routing Control Centre computes all tables.
• Isolated: each node uses only local data (e.g. hot potato: shortest queue).
• Distributed:
  • Distance vector (Bellman-Ford): each router sends its distance table to its neighbours periodically and updates using $D_x(y)=\min_v\{c(x,v)+D_v(y)\}$. Simple but slow convergence and count-to-infinity. Example: RIP.
  • Link state (Dijkstra): each router floods its link costs to all routers, builds the full map and computes shortest paths. Fast convergence. Example: OSPF.

Example: if link B–C fails, a static router keeps sending packets over link B–C and they are lost; a dynamic router learns of the failure and shifts the traffic to another path.

Comparison