CSE 588 Problem Set #2
Due Date: Friday, May 7
1. For (i) link state, (ii) traditional distance vector, and (iii) path-based distance vector:
(a) Under what circumstances, if any, is it possible for router A to forward packets for router B through router C, even though routers A and B are neighbors.
(b) Suppose that A and B are neighbors, but A thinks the cost of the link to B is x, and B thinks the cost to the link to A is y.Will this cause any problems?Explain in terms of an example.
(c) Give a topology in which, due to an inconsistency in the information about a single link, many routes are disrupted.Give a topology in which, despite an inconsistency in the information about a single link, no routes are disrupted.
2. Consider an arbitrarily large network in the form of a fully balanced binary tree of L levels.There are 2^k nodes at level k (for k = 0 ... L - 1) and there are 2^L - 1 nodes altogether.Each leaf at the bottom of the tree represents a host and each internal node represents a router.Your task is to devise a scheme for assigning addresses to nodes that is optimal in the sense of minimizing the maximum size of the routing tables across all routers, assuming each entry in the routing tables store only prefixes with unique routes (in other words, the routers are CIDR-based).Indicate what it stored in each router's forwarding table.
3. Consider the following proposal for hierarchical source routing based on the Internet's "loose source routing".With loose source routing, a host specifies a list of routers to visit on the way to the destination; the network is free to use any means of getting between the routers in the loose source route.A hierarchical source routing scheme could be built on top of this, by saying that when a packet is delivered to a router specified in the loose source route list, it can in turn "push on the stack" a loose source route to the next router in the original list.Explain why this might be better or worse than the way hierarchical routing is done in the Internet today.Where appropriate, give concrete examples.
4. Draw a timing diagram illustrating all the packets that are sent using TCP between a client and server, when the client requests a 10KB web page, and the previously determined maximum transfer unit without fragmentation is 512 bytes.Include connection setup and teardown, slow start, delayed acks, etc. Roughly how many round trips does it take?What happens if the third data packet from the server is dropped?How many round trips in this case?
5. Suppose we modified TCP to use the DECbit constant for multiplicative decrease (0.875 instead of 0.5).Assuming packets are lost periodically at the tip of the sawtooth, how would this change the formula in Mathis et al.?Is there any downside?
Document converted from word 8 by
MSWordView (mswordview 0.5.6)
MSWordView written by Caolan McNamara