Assignment 5 is due at 2pm (before start of class) on Tuesday 4/13. Please see grading policy on course homepage for additional details regarding early/late submissions.

Please submit your answers in plain text (with any images as attachments) to i250hw@ischool.berkeley.edu.

---

1. Shortest Path Routing

(a) (3 points) Using Dijkstra's Shortest Path First algorithm, find the shortest-path routes from node C to all other nodes in the network.  Show the intermediate results after each iteration step of the algorithm.

(b) (1 point) What is the final routing table for node C?

Note: answers for intermediate steps may vary slightly if next closest node is a tie, but the final answer should be the same.

2. Policy Based Routing

Consider an internetwork that consists of three transit Autonomous Systems, AS1, AS2, and AS3. AS1 has a peering relationship with AS2, and AS2 has a peering relationship with AS3.

In addition, there are four stub ASs, AS44, AS55, AS66, and AS77. AS44 is a customer of AS1. AS55 is a customer of AS2. AS66 is a customer of AS3. Finally, AS77 is a customer of both AS1 and AS3.

(a) (2 points) Following the notation in slides 24-25 of the lecture on routing, draw a graph representing the internetwork and the relationships between the seven AS's.

(b) (1 point) A host in AS44 wishes to send a message to a host in AS66. Identify all possible AS-level paths that may be taken by the message.

(c) (1 point) A host in AS55 wishes to send a message to a host in AS77. Identify all possible AS-level paths that may be taken by the message.

(d) (1 point) If there are multiple AS-level paths to a given destination, how is the actual packet forwarding path selected?

(e) (1 point) Explain why the presence of a path at the physical layer or data link layer does not imply the presence of an AS-level path at the network layer.

3. TCP Reliable Data Transport

Host A and Host B are communicating over a TCP connection. Host B has already received from Host A all bytes up to and including byte 5000.

Next, Host A sends two more segments to Host B. The first segment contains 100 bytes of data, has a sequence number of 5001, with source and destination port numbers of 6200 and 7300 respectively. The second segment contains 200 bytes of data.

Host B sends an acknowledgement whenever it receives a segment from Host A.

(a) (1 point) What are the values for the sequence number, source port, and destination port for the second segment?

(b) (1 point) If the first segment has just arrived, and the second segment has not yet arrived, what values should Host B use for the acknowledgement number, source port, and destination port when constructing the acknowledgment message?

(c) (1 point) If the second segment arrives first, and the first segment has not yet arrived, what values should Host B use for the acknowledgement number, source port, and destination port when constructing the acknowledgment message?

(d) (3 points) Suppose that the first segment arrives, followed by the second segment. The first acknowledgment is lost, and the second acknowledgment arrives at Host A after the first timeout period. Draw a timing diagram, showing these messages and all subsequent segments and acknowledgements sent, assuming that no additional messages are lost. For each message, provide the sequence number or the acknowledgement number, where appropriate.

4. UDP and Addressing

(2 points) A process running on Host A has a UDP socket with port number 20000. Suppose both Host B and Host C both send a UDP datagram to Host A with destination port number 20000. Will both datagrams be delivered to the same process on Host A? If so, how will the process at Host A know that the two datagrams orginated from two different hosts?