Home

Schedule/Notes

Readings

Assignments

TA info

Policies

Homework #1: Networking Review
Assigned: Wednesday 9/30
Due Wednesday 10/7 4:30 pm (main CS office)

1. Packet-switching versus circuit-siwtching. Suppose users share a 155 Mbps link. Suppose that this line is being shared by two populations of users. The first are watching high resolution videos that each require 6Mbps at a constant bit rate. The second population of users are intermittent users. When each user has data to send, it wants to send data at 20Mbps. Each of these users only wants to send data 10% of the time, and all users are mutually independent.

• Suppose that there are ten video watchers. Assuming circuit switching is being used. How many additional simultaneous intermittent users can be supported?
• Suppose now that we use packet switching, and that there is only a minimal amount of packet buffering (That is, if the aggregate transmission rates of the active users exceeds the link capacity, the traffic beyond the link capacity will be dropped, with these drops being spread evenly among users). Consider again the case of ten video users and ten intermittent users. What is the probability that at any given point in time, an intermiitent user that is transmitting will experience packet loss due to congestion?
• Let us return to the circuit switching setting. Plot a curve describing the maximum number of intermittent users that can be supported as a function of the number of video watchers.
• Answer the above question for the case of packet switching. under the constraint that the probability that an intermittent user experiences loss is always less than one percent.

2. Error control and TCP.

(2a) Consider the simple stop and wait protocol (rdt 3.0) in note set #1.Suppose the path connecting the sender and receiver is a 100Mbps connection, with an end-end propagation delay of 50 ms. A data packet is 1512 bytes long. Given the simple stop and wait protocol, what is the throughput (in terms of bits/sec) delivered from sender to receiver?

(2b) We've seen that TCP overcomes the low throughput of a stop-and-wait protocol by allowing a window of W packets to be sent and waiting for acknowledgements.Recall that if all of those W packets are successfully acknowledged, TCP will increase the window size to W+1.Recall also that we characterized TCP as "probing" for available network bandwidth, increasing its window size until loss occurs and then cutting the window size in half (in the case of TCP Reno). So let us consider an idealized TCP protocol in which the window size starts at W/2. In this idealized model, the TCP sender sends out W/2 packets and has them all acknowledged 1 round trip time (RTT) later, and increases the window size to W/2+1. These packets are then acknowledged 1 RTT later and the window size is again incremented. Suppose the amount of available bandwidth is such that when the window size reaches W, exactly one packet is lost out of this W, and the TCP sender then resets the window size to W/2, and this process repeats. This gives rise to the behavior shown below:

Given the basic behavior described above, show that the fraction of packets lost in this scenario is p = 1/ ( (3/8)W**2 + (3/4)W).Given this result and assuming that W is large enough so that W**2 >> W, show that the throughput of the TCP connection is 1.22/(RTT * sqrt(p)).

Last, suppose that the TCP protocol is run over a channel with capacity C. Assume that, as soon as the TCP sender sends at a rate W/RTT that exceeds C, a loss occurs and the sender is notified one RTT later. What is the maximum, minimum, and average window sizes for the TCP sender? What is p, the packet loss probability. Give your results in terms of C.

3.Traceroute. Perform a Traceroute (see pages 40 and 41 in K&R) between source and destination on the same continent at three different hours of the day.

1. Find the average and standard deviation of the round-trip delays at each of
   the three hours.
2. Find the number of routers in the path at each of the three hours. Did the
   paths change during any of the hours?
3. Try to identify the number of ISP networks that the Traceroute packets
   pass through from source to destination. Routers with similar names
   and/or similar IP addresses should be considered as part of the same ISP.
   In your experiments, do the largest delays occur at the peering interfaces
   between adjacent ISPs?
4. Repeat the above for a destination that is on a different continent than your source. Compare the intra-continent (above) and these inter-continent results.

4. Distance Vector Algorithm. (see section 4.5 in K&R). Consider the network below.

• What are A, B, C, D, E, and F’s distance vectors? Note: you do not have to run the distance vector algorithm; you should be able to compute distance vectors by inspection. Recall that a nodes distance vector is vector of the least cost paths from itself to each of the other nodes in the network.
• Now let us consider node D.  From which other nodes does D receive its distance vector?
•  Consider node D again.  Through which neighbor will D route it packets destined to E.  Explain how you arrived at this answer, given the distance vectors that D has received from its neighbors.

5.Q.2931, RSVP, SIP. Read the specification of  SIP (Session Initiation Protocol) RFC 3261). (BE CAREFUL! It's a long document; you can skim or ignore many parts.  But read carefully enough so that you have an idea how SIP works.  If you are interested in a tutorial overview of SIP, you can try the SIP webpage).  Answer the following questions.

• What are the similarities and differences between SIP and Q.2931?
• What are the similarities and differences between SIP and RSVP?
• What state is stored by SIP endpoints and proxies for a session?
• Would you say that SIP provides for separation of control and data?  Why or why not?

6. Hard state. Given our discussions in class, we would probably classify TCP as a hard state protocol, since it has explicit setup and teardown. What are the mechanisms that TCP uses that allows it to recover when there is a failure "on the other side" of the connection?  To answer this question, you will need to use sources outside of our class reading (e.g., Steven's TCP IP Illustrated V1.)