Home Announcements Schedule Assignments

## IS250 Computer Based Communications Networks and Systems

Spring 2010

Assignment 5

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.

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.