1

Computer Network - Homework II
Due: 2007/6/11 24:00
1. Consider the GBN protocol with a sender window size of 3 and a sequence
number of 1024. Suppose that at time t, the next in-order packet that
the receiver is expecting has a sequence number of k. Assume that the
medium does not reorder messages. Answer the following questions:
a) What are the possible sets of sequence numbers inside the sender's
window at time t? Justify your answer.
b) What are all possible values of the ACK field in all possible
messages currently propagating back to the sender at time t? Justify
your answer. 2. Consider the following plot of TCP window size as a function of time.
[pic] Assuming TCP Reno is the protocol experiencing the behavior shown above,
answer the following questions. In all cases, you should provide a short
discussion justifying your answer.
a) Identify the intervals of time when TCP slow start is operating.
b) Identify the intervals of time when TCP congestion avoidance is
operating.
c) After 16th transmission round, is segment loss detected by a triple
duplicate ACK or by a timeout?
d) After the 22nd transmission round, is segment loss detected by a
triple duplicate ACK or by a timeout?
e) What is the initial value of Threshold at the first transmission
round?
f) What is the value of Threshold at the 18th transmission round?
g) What is the value of Threshold at the 24th transmission round?
h) During what transmission round in the 70th segment sent?
i) Assuming a packet loss is detected after the 26th round by the
receipt of a triple duplicate ACK, what will be the values of the
congestion window size of Threshold? 3. Recall the idealized model for the steady-state dynamics of TCP. In the
period of time from when the connection's rate varies from W/(2RTT) to
W/RTT, only one packets is lost (at the very end of the period).
a) Show that the loss rate (fraction of packets lost) is equal to
[pic]
b) Use the result above to show that if a connections has loss rate L,
then its average rate is approximately given by
[pic] 4. Consider sending an object of size O=100 Kbytes from server to client.
Let S=536 bytes and RTT=100 msec. Suppose the transport protocol uses
static windows with window size W.
a) For a transmission rate of 28 kbps, determine the minimum possible
latency. Determine the minimum window size that achieves this
latency.
b) Repeat (a) for 1 Mbps.
5. Consider a VC network with a 2-bit field for the VC number. Suppose
that the network wants to set up a virtual circuit over four links: link
A, link B, link C, and link D. Suppose that each of these links is
currently carrying two other virtual circuits, and the VC numbers of
these other VCs are as follows:
|Link A |Link B |Link C |Link D |
|00 |01 |10 |11 |
|01 |10 |11 |00 |
In answering the following questions, keep in mind that each of the
existing VCs may only be traversing one of the four links.
a) If each VC is required to use the same VC number on all links along
its path, what VC number could be assigned to the new VC?
b) If each VC is permitted to have a different VC numbers in the
different links along its path (so that forwarding tables must
perform VC number translation), how many different combinations of
four VC numbers (one for each of the four links) could be used?
6. Consider the topology shown in Figure 1. Denote the three subnets with
hosts (starting clockwise at 12:00) as Networks A, B, and C. Denote the
subnets without hosts as Networks D, E, and F.
a) Assign network addresses to each of these six subnets, with the
following constraints: All addresses must be allocated from
214.97.254/17; Subnet A should have enough addresses to support 250
interfaces; Subnet B should have enough addresses to support 120
interfaces; and Subnet C should have enough addresses to support 120
interfaces. Of course, subnets D, E and F should each be able to
support two interfaces. For each subnet, the assignment should take
the form a.b.c.d/x or a.b.c.d/x - e.f.g.h/y.
b) Using your answer to part (a), provide the forwarding tables (using
longest prefix matching) for each of the three routers.
[pic]
Figure 1
7. Consider the network shown in figure 2. Using Dijkstra's algorithm, and
showing your work using a table similar to table 3, do the following:
a) Computer the shortest path from s to all network nodes.
b) Computer the shortest path from v to all network nodes.
c) Computer the shortest path from x to all network nodes.
[pic]
Figure 2.
|step |
Table 3.
8. Consider the following network. ISP B provides national backbone
services to regional ISP A. ISP C provides national backbone services to
regional ISP D. B and C peer with each other in two places using BGP.
Consider traffic going from A to D. B would prefer to hand that traffic
over to C on the West Coast (so that C would have to absorb the cost of
carrying the traffic cross-country), while C would prefer to get the
traffic via its East Coast peering point with B (so that B would have
carried the traffic across the country). What BGP mechanism might C use,
so that B would hand over A-to-D traffic at their East Coast peering
point?
[pic]
-----------------------
Transmission round
Congestion window size (segments)