E6998-02 Homework 3

Out: 1 October 2002


Due: 10 October 2002 at 3am EDT. You have more than a week. Start tonight, ask questions if you have problems.


The purpose of this homework is to convince yourself (and me!) that you understand the essential elements of DV and LS protocols. For a change, you'll have no real programming to do (but short scripts might help). You answers should be short and concise; don't write a dissertation!

Consider this network:

It is the same as the network on slide 20 of Lecture 8. The numbers next to each router indicate the metrics to the corresponding router on the other side of the link. For example, to get from A to E the cost is 4, but to get from E back to A the cost is 5.

  1. Assume that the network is running a DV routing protocol, with all link costs being 1. After routing stabilizes, what is A's forwarding table? E's? H's?
  2. Repeat 1, but with each link cost being the smaller of the two costs given for each link (e.g., link AE has cost 4 in both directions. What differences do you observe, if any?
  3. Repeat 2, but with each link cost being the larger of the two costs given for each link (e.g., link AE has cost 5 in both directions. What differences do you observe, if any?
  4. Does it make sense to run a DV protocol with unequal costs in each direction? Does the protocol converge with this network? If so, what are the forwarding tables of A, E, and H? If it does not converge, what do you observe?
  5. The network is now running a LS protocol, with all link costs being 1. After routing stabilizes, what are the forwarding tables of A, E, and H? Are they different from what you got with the DV protocol in question 1? Explain.
  6. Repeat 5, but with each link cost being the smaller of the two costs given for each link. How do the results differ from the results in 2 and the results in 5?
  7. Repeat 5, but with the link costs as given. Again, how do the results differ from the results in 4 (if you got convergence), 5, and 6?

For extra credit:


Submit the homework via email to ji+hw3@cs.columbia.edu. Do not send anything other than plain ascii text of a .pdf file. Do not send to any other address, or your submission will be ignored.


$Id: index.html,v 1.2 2002/09/29 22:56:31 ji Exp ji $