Homework 4

Due May 7, 2009 5:30 pm (Leave homework in the box outside instructor's office door).

Email submissions are unacceptable. You will need to have a hard copy submission. You can always submit early if not on campus on the deadline date. Some of the problems refer to the papers in the reading list and may not have been discussed directly in class. Be precise in your answers. Usually a few 1-3 short paras (with examples when appropriate) are sufficient for the answer. Lengthy convoluted response where the grader has to fish for the answer could lose points.

  1. Distance Vector Protocol: Show using an example that the Poisoned Reverse technique cannot solve the counting-to-infinity problem using three or more nodes. Showing just a three node example is sufficient.

  2. Multicast: In class we learnt that the union of the least cost paths from the source to all destinations can be thought of as forming a least cost path tree. (We used the terminology shortest path to mean the least cost path.) By constructing a counterexample, show that the least cost path tree is not always the same as a minimum spanning tree.

  3. More Multicast: Consider the two basic approaches identified for achieving broadcast: unicast emulation (i.e., using multiple unicast)  and true network layer broadcast, and suppose broadcast over a spanning tree is used to achieve network layer broadcast. Consider a single sender and 32 receivers. Suppose the sender is connected to the receivers by a binary tree of routers. What is the cost of sending a broadcast packet, in that cases of unique emulation and network layer broadcast, for this topology? Here, each time a packet (or a copy of the packet) is sent over a single link, it incurs a unit of cost. What topology for interconnecting the sender, receivers, and routers will bring the cost of unicast emulation and true network layer broadcast as far apart as possible? You can choose as many routers as you like.

  4. BGP: The AS paths in BGP adhere to specific patterns due to specific nature of export policies. What are these patterns? What is the valley-free property of AS-paths? If there is no valley, where is the "top-of-the-hill"? [The BGP readings should be sufficient to answer this question, particularly the one on reverse engineering BGP.]

  5. Overlay/Miltihoming: Explain how overlay networks and multihoming can improve routing performance. [The first three papers in the overlay part of the readings should be sufficient to answer this question.]