14:332:423            Telecommunication Networks

Homework #3
(to be discussed in the recitations on October 14 & 21, 2005)

1. [10 points]   Suppose an application running at host B wants to send a packet of 2000 bytes to an application at host C. Assume that IP header is 20 bytes long and that the packet is assigned ID = 12345. Show all the fragments created on the path from B to C and specify the values of all relevant parameters in each fragment header.



2. [10 points]   The following is a routing table of a router using CIDR. Note that the last three entries cover every address and thus serve in lieu of a default route.

   Subnet Mask	Next Hop
   223.92.32.0 / 20	A
   223.81.196.0 / 12	B
   223.112.0.0 / 12	C
   223.120.0.0 / 14	D
   128.0.0.0 / 1	E
   64.0.0.0 / 2	F
   32.0.0.0 / 3	G

   State to what next hop the packets with the following destination addresses will be delivered:
   1. 195.145.34.2
   2. 223.95.19.135
   3. 223.95.34.9
   4. 63.67.145.18
   5. 223.123.59.47
   6. 223.125.49.47
   (The default matches should be reported only if no other match is found.)



3. [10 points]   For the network given in the figure below, show how a distance-vector routing algorithm converges from the initial to the stable state.
4. Consider the simple network in the following figure, in which A and B exchange distance-vector routing information. All links have cost 1.
   Here we assume that the nodes send distance vectors to other nodes under two circumstances: (1) periodic clock-driven updates (say, every 15 sec), regardless of whether or not there were changes in the routing table; and, (2) updates triggered by routing table changes, when some of the table entries get modified, e.g., due to the link failure to an adjacent neighbor.
   We also need to know how a node detects a failure, which can be done is several ways. One way is to continuously test the adjacent links by sending probe packets and receiving acknowledgements. Another way is to surmise the link failure from the absence of periodic updates from that neighbor.
   Suppose now that the A-E link fails.
   1. [10 points]   Give a sequence of routing table updates that leads to a routing loop between A and B ("count-to-infinity" problem).
   2. [10 points]   Estimate the probability of the scenario in (a), assuming A and B send out routing updates at random times, each at the same average rate.
      HINT: Consider what happens if A receives a (periodic) update from B "simultaneously" as it learns about the failure of A-E. (Almost simultaneously, i.e., A receives B's packet before it sends the new distance vector to B.)
   



5. Suppose host A is sending to a multicast group; the recipients are leaf nodes of a tree rooted at A with depth N and with each nonleaf node having k children.
   1. [3 points]   What is the total number of recipients?
   2. [5 points]   How many individual link transmissions are involved if A sends a multicast message to all recipients?
   3. [5 points]   How many individual link transmissions are involved if A sends unicast messages to each individual recipient?
   4. [7 points]   Suppose A sends to all recipients, but some messages are lost and retransmission is necessary. Unicast retransmissions to what fraction of the recipients is equivalent, in terms of individual link transmissions, to a multicast retransmission to all recipients?

Note 2: Please bring your own printed copy of the homework assignment, so the TA doesn't need to write the problem statement on the board.