Routing

Objectives

• Understand the basic types of routing algorithms.
• Know about the different possible routing metrics.
• Know how distance-vector routing algorithms work.
• Know how link-state routing algorithms work.

Inquiry

• How do you select the best path for a connection or datagram to take in a network?
• What are the measures that you might use to make routing decisions?
• What are the advantages and disadvantages of centralized and decentralized routing?
• What are the advantages and disadvantages of dynamic and static routing?

Preparation

Read section 4.2 in the book and the notes.

Knowledge, Comprehension and Problem Solving

Term

• Centralized routing
• Decentralized routing
• Distance-vector routing
• Dynamic routing
• Link-state routing
• Open Shortest Path First (OSPF) Protocol
• Route Information Protocol (RIP)
• Slow convergence
• Static routing

Questions

Given the following network:

1. Show the initial distance-vector routing tables where all nodes know only about their neighbors.
2. Show the routing tables after there is one exchange with all of their neighbors, and then when there is one more exchange.
3. Show the adjacency matrix for a router if link-state routing is used.
4. What happens at R3 if router R4 crashes?
5. Give an example of slow convergence.

Analysis, Synthesis and Evaluation

1. For the network show above, compare the network capacity used for distance-vector versus link-state routing. Assume that all distances are two-byte integers and that all addresses are four-byte integers. Also, assume that every router advertises its routes at 60 second intervals.
2. Given a router with a router table, write the algorithm that it would use to route and switch and incoming packet.