Lecture 15: Routing Algorithms
Routing is one of the big components of the Network Layer. The last lecture talked about how individual packets are addressed and how they are forwarded at each router based on the forwarding table. The routing algorithms described today are the basis for filling the forwarding table.
There are two main types of routing algorithms — Distance-Vector and Link-State. Distance Vector algorithms are decentralized and don't require the routing nodes to have global information about the network. Link-state algorithms require global knowledge, but are very stable.
Lesson Objectives
By the end of this lesson, the student will be able to:
- describe the differences between global / decentralized and static / dynamic routing algorithms. Students should be able to describe different message complexity, convergence speeds, robustness and algorithm complexity.
- calculate a forwarding table using Dijkstra's algorithm (which may include identifying and using proper variables and terms). Intermediate results may be required, such as an SPT or table of variable values.
- use Bellman-Ford equations to calculate a forwarding table for a DV routing algorithm. Intermediate values may be required, which may require knowing variable names and terms.
- describe how DV algorithms operate to pass updates.
- describe DV instability problems, such as “Count to Infinity” and the associated stabilization techniques.
- analyze DV instability examples.
Reading
- KR Ch 5.1 - 5.2