Federico Mengozzi

Network Layer

Routing Algorithms

Every host in a network is usually attached to the default router also called the first-hop router for the host. A packet need to travel from the source default router to the destination default router.

A graph is used to model the problem of finding a path from source to destination. In the graph the nodes represent each router and the edges represent the physical link between them (whose value represent the length/speed/monetary cost of the link).

A routing algorithms, simply put, finds the shortest path between source and destination. There are two different kind of routing algorithm:

  • Global Routing Algorithms: those that operate with a complete, global knowledge of the network. They are also referred as link-state algorithms because they must be aware of the state of each link
  • Decentralized Routing Algorithms: those in which each node begins with the only knowledge of its neighbors and gradually they calculate the shortest path to a set of destinations.

Another way to classify routing algorithms is wether they are static or dynamic. In static routing algorithms routes change very slowly (usually as a result of human intervention) while dynamic routing algorithms change the routing path as the network traffic loads or topology change.

Go to top