Learning Objectives

After successfully completing this section, you should be able to

  1. explain routing principles.
  2. describe some important routing algorithms and protocols.
  3. show how these routing algorithms and protocols work.
  4. describe the structure of routers.
  5. explain how routers work.

Learning Tasks

Required

  1. Watch the slideshow for this section.
  2. Study Section 5.2, Routing Algorithms, in the textbook.

Suggested:

  1. Search the Internet for tutorials on network routing and routing algorithms. Choose two tutorials to study and post the links to the course forum with your comments.

Terms and Topics

Section 2 – Routing Algorithms

Routing algorithms
Important and well-known routing algorithms
Default router
First-hope router
Source router
Destination router
Graph
A neighbor of a node (in a graph)
Path in a graph
Least cost path in a graph
Shortest path in a graph
Global routing algorithm
Global state information
Link-state (LS) algorithm
Decentralized routing algorithm
Static routing algorithms
Dynamic routing algorithms
Load-sensitive routing algorithms
Link state broadcasting algorithm

Distance vector (DV)
The distance-vector (DV) routing algorithm
Link cost changes and link failure
Routing loop
Count to infinity problem in DV routing
Adding poisoned reverse to the distance-vector algorithm
Comparing DV with LS routing algorithms
Circuit-switched routing algorithms
Hierarchical routing
Problems with LS and DV routing 

Leading Questions

  1. What are the goals of a routing algorithm?
  2. What is the role of the network layer routing protocol?
  3. What is the least cost path between two hosts in a network? What condition does such a path have to meet?
  4. What is the shortest path between two hosts in a network?
  5. When can the shortest path and the least cost path be identical?
  6. What are routing algorithms used for?
  7. How is a graph used to formulate routing problems?
  8. What is a centralized routing algorithm?
  9. What is a decentralized routing algorithm?
  10. What is a static routing algorithm?
  11. What is a dynamic routing algorithm?
  12. What is a load-sensitive routing algorithm?
  13. What is a global routing algorithm for a network?
  14. Why is a global routing algorithm referred to as a link-state algorithm?
  15. What are the differences between distance-vector algorithms and link-state algorithms?
  16. How are link cost changes and link failures handled in the distance-vector algorithm?
  17. What is hot potato routing?
  18. What is shortest path first routing?
  19. What is least loaded path routing?
  20. What is maximum free circuit routing?
  21. What are gateway routers?
  22. What is the intra-autonomous routing protocol?
  23. Based on the IPv4 addressing scheme, what is the maximum number of hosts that can be addressed?
  24. What is a network address? What is a network mask?
  25. What is classful addressing? What are the differences between class A, B, C, and D addresses?
  26. Why are the four address classes no longer formally part of the IP addressing architecture?
  27. What is Classless Interdomain Routing (CIDR)?
  28. What is subnetting?
  29. What is the Dynamic Host Configuration Protocol (DHCP)?
  30. What is route aggregation or route summarization and how does it work?
  31. How does an ISP get a block of addresses?
  32. Which organization is responsible for the management of IP addresses?
  33. How is an IP datagram formatted?
  34. How is an IP datagram transported from source to destination?
  35. What is the maximum transfer unit (MTU)?
  36. What is the Internet Control Message Protocol (ICMP) used for?