Routing algorithms

Routing is a top 10 networking challenge.

The goal of a routing algorithm is to find good paths (or routes) for data to travel from senders to receivers through a network of routers.

A good path is the one with the lowest cost, although real-world constraints (like policy rules) can also affect the choice.

Modeling the network

Routing problems are represented using graphs where:

• nodes = routers
  • two nodes are neighbors if they share a direct link
• edges or links = physical links between routers
  • edges are undirected (traffic can go both ways)

The cost of an edge between two nodes x and y is:

\[ c(x, y) \]

The cost may represent:

• distance
• speed of the link
• financial cost

Paths

A path is a sequence of nodes connected by links:

\[ (x_{1}, x_{2}, …, x_{p}) \]

The cost of a path is the sum of all edge costs along it:

\[ c(x_{1}, x_{2}) + c(x_{2}, x_{3}) + … + c(x_{p - 1}, x_{p}) \]

Between any two nodes, there may be many possible paths. The least-cost path is the one with the smallest total cost.

If all links have equal cost, the least-cost path is simply the shortest path (fewest hops).

Types of routing algorithms

Routing algorithms are classified in several ways:

Classification	Type	Description
Centralized vs. decentralized	Centralized (link-state)	has full knowledge of the entire network: takes the connectivity between all nodes and all link costs as inputs computes routes using global information
	Decentralized (distance-vector)	no node has complete information about the costs of all network links each router shares information only with its neighbors routes are built step by step in an iterative, distributed manner by the routers
Static vs. dynamic	Static routing	routes change very slowly over time
	Dynamic routing	routes change as the network traffic loads or topology change can react to failures or congestion may cause issues like routing loops and route oscillation
Load-sensitive vs. load-insensitive	Load-sensitive	link costs vary dynamically based on congestion tries to avoid congested links but may be unstable used in early ARPAnet routing algorithms
	Load-insensitive	link costs do not explicitly reflect their current level of congestion used by today's Internet routing algorithms (e.g., RIP, OSPF, BGP)

Fundamental routing algorithms

Two main classes of routing protocols are used to compute least-cost paths in a network:

• link-state (LS) routing protocols
• distance-vector (DV) routing protocols

Neither algorithm is an obvious winner over the other:

• LS converges faster and avoids some DV pathologies, but it requires more memory, computation, and flooding overhead
• DV generally requires less information exchange per update but can suffer from slower convergence and problems such as count-to-infinity

Both are used in the Internet. For example, OSPF is a link-state protocol, while RIP is a distance-vector protocol.

They are used in both traditional per-router control and SDN architectures.