CMSC 417-F02
|
EXAM 1 SOLUTION
|
Fall 2002
|
1 [15 pts]. Solution
Since each packet carries 1 Kbyte,
the file consists of packet chunks 0..25.
The protocol evolves as follows, where
window send identifies the instance of sending the window,
chunks sent identifies the packets sent
with "*" identifying a packet dropped at router,
cw is the congestion window size,
sst is the slow start threshold,
router is the number of packets at the router just after the send,
tns is the time to next send (in ms)
and is tagged with rtt or rto,
and send time is the time when the current window is sent (in ms).
window send chunks sent cw sst router tns send time
1 0 1 8 1 10 (rtt) 0
2 1,2 2 8 2 20 (rtt) 10
3 3,4,5,6* 4 8 3 40 (rto) 30
4 6 1 2 1 10 (rtt) 70
5 7,8 2 2 2 20 (rtt) 80
6 9,10,11 3 2 3 30 (rtt) 100
7 12,13,14,15* 4 2 3 40 (rto) 130
8 15 1 2 1 10 (rtt) 170
9 16,17 2 2 2 20 (rtt) 180
10 18,19,20 3 2 3 30 (rtt) 200
11 21,22,23,24* 4 2 3 40 (rto) 230
12 24 1 2 1 10 (rtt) 270
13 25 2 2 2 20 (rtt) 280
The file transfer is complete when packet 25 is acked.
From above, this happens at time 290 ms.
Also, 13 windows are sent.
GRADING:
-
8 for window evolution (cw, sst, packets sent);
7 for timing (3 for rtts, 2 for rto).
-
Incorrect cw, sst evolution: -3 to -6,
depending on extent of cluelessness.
-
Serious errors (no packet lost, no retransmission of lost packet,
timeout without packet loss, not waiting for ack to be received):
-3 to -4
2 [10 pts]. Solution
When a SACK message is received, the source should
see if the message acknowledges any outstanding data,
and if so, it should mark that data as acked.
What if the (SACK,cj,len) acknowledges na?
That is, what if the unbounded sequence number j corresponding to cj
equals na, or, more generally, [j..j+len-1] contains na.
An obvious answer is that the source should update na (easy to do),
and as a consequence update sw (but how to do this is not clear).
In fact, this situation never arises, as the following argument shows.
-
Consider any (ACK,k,w) message and any (SACK,j,len) message
sent by the sink,
where we let j and k be unbounded sequence numbers
(for clarity and without loss of generality).
-
If the ACK message was sent before the SACK message,
then k is less than j and is not contained in [j..j+len-1],
otherwise data j would not have been out-of-sequence at the sink
when the SACK was sent.
-
If the ACK message was sent after the SACK message,
then k is not contained in [j..j+len-1],
otherwise data j would not have been the next in-sequence
expected at the sink when the ACK was sent.
-
Because na is always the k in some ACK message,
na will never be contained in the segment acked by a SACK message
This leads us to the following event handler for SACK reception:
Receive(SACK,cj,len) {
// if (cj in outstanding packets)
int tmp := mod(N, cj-na);
if (1 ≤ tmp ≤ mod(N, ns-na)) { | 4 points
// mark data[j..k] as acked, where |
// j is unbounded seq number corresponding to cj |
// and k is the smaller of cj+len-1 and ns-1. | 6 points
for i := tmp to tmp + min(len,ns-na)-1 { |
sbuff[i].ackd := true; |
} |
}
}
GRADING:
-
The points distribution is as indicated above next to the code.
-
Mistakes in the modulo-N arithmetic and buffer handling: -2 to -8 points,
depending on extent of cluelessness.
Here are some common mistakes:
-
No modulo-N arithmetic at all: -7 pts.
-
Using cj rather than Mod(N,cj-na) in test: -4
-
Using Mod(N,cj-ns) rather than Mod(N,cj-na) in test: -3
-
Comparing tmp or cj vs ns or na (rather than ns-na): -4
-
Treating sbuff as indexed starting from na rather than 0: -3
-
Not checking for min(ns-na,len): -2 points
-
Updating na and sw when tmp not equal to 0 : -4 points
3 [5 pts]. Solution
The very high bandwidth and compute resources at the end points
means that the propagation times are the only causes of delay;
e.g., transmitting a message takes zero time,
processing a received message takes zero time.
user 1 ----------- SYN -----------> user 2 T1,2
user 1 <--------- SYN-ACK --------- user 2 T2,1
user 1 ---- ACK-DATA(optional) ---> user 2 T1,2
user 1 <--- DATA(user 3 addr) ----- user 2 T2,1
user 1 ----------- SYN -----------> user 3 T1,3
user 1 <--------- SYN-ACK --------- user 2 T3,1
user 1 --- ACK-DATA(few octets) --> user 2 T1,3
user 1 <-------- ACK ------------- user 2 T3,1
Total time taken is
2T1,2 + 2T2,1 + 2T1,3 + 2T3,1
If you close the connection between user 1 and user 2
before connecting to user 3
and you use separate FIN handshake for this,
then there can be an additional delays
(e.g., additional T1,2 + T2,1).
Many of you had user 1 send data to user 3 (or optional data to user 2)
in a separate message (i.e., not in the ACK of the connection establishment).
This does not affect the total time taken because this message
is sent as soon as it becomes open
(and transmitting a message takes zero time).
GRADING:
-
Correct handshake chart but inconsistent formula: -1 to -2
-
Incorrect but sensible handshake chart and consistent formula: -1 to -2.
-
Not using 3-way handshake in TCP connection establishment: -3
-
Common mistake:
Having transmission of data (usually in separate message)
contribute additional propagation delay: -3