Routing Algorithms

Algorithms that aim to determine good paths from senders to receivers, through a network of Routers.

Graph

They are performed on an Undirected Graph $G=(N,E)$, where $N$ is a set of nodes and $E$ a set of edges defined by the pair of nodes connected. The nodes represent Routers and the edges the physical links between them.

The edges are assigned costs denoted by $c(x,y)$, for any edge $(x,y)$. Since the graph is undirected we have $c(x,y)=c(y,x)$.

If $(x,y)\notin E$ then $c(x,y)=\infty$. A node $y$ is said to be a neighbour of node $x$ if $(x,y)\in E$.

The cost of a Path are simply the sum of all the edge costs. The path(s) with the lowest such cost are the least-cost path(s).

Categorisations

• Centralised Routing Algorithms vs Decentralised Routing Algorithms
• Static Routing Algorithms vs Dynamic Routing Algorithms
• Load-sensitive Routing Algorithms vs Load-insensitive Routing Algorithms