CSE 461
Homework 2 Solution
1a.
Latency = Propogation Delay + Transmit Time
= 2ms + 8*8192 bits / 10 Mbs
= 8.55 ms
1b.
Latency = Latency from A to B + Latency from B to C
= 8.55 ms (from above)+ 10 ms + 8*8192 bits /1.5 Mbs
= 62.2 ms
1c.
Number of packets sent from A to B as a function
of time (t) is:
Num packets = (t - 2ms) * (10 Mbs / 8192*8 bits/packet)
= (t - .002) * 152.58 packets/second
Number of packets leaving B to C as a function
of time is:
Num packets = (t - 8.55ms) * (1.5 Mbs / 8192*8 bits/packet)
= (t - .00855) * 22.89 packets/second
Subtract packets departing from packets arriving and
solve for when the difference equals 10:
((t - .002)*152.58) - ((t-.00855)*22.89) = 10
t = (10 + (.002*152.58) - (.00855*22.89)) /
(152.58 - 22.89)
t = .07795
= 77.95 ms
Correct analytical solutions will continue with the following
analysis:
Number of packets sent to B in 77.95 ms =
10 Mb/s * 77.95 ms / 8*8192 bits/packet
= 11.89 packets
Since last 0.89 packets can't be received (i.e. must either
receive the whole packet into a buffer or drop it completely),
12th packet is dropped on arrival.
Time at which 12th packet arrives:
= 11 * 8 * 8192 / 10 Mb/s + 2ms propogation delay
= 74.1 ms
How often will B drop packets?
The answer to this question is simply the difference in
the transmission rates between A/B and B/C expressed as
packets per second:
= (10Mb/s - 1.5Mb/s) / 8*8192 bits/packet
= B will drop 129.70 packets / second
If B's queue is increased to 20, B will still drop packets
at the same rate after the queue is filled.
1d.
Assuming that the acknowledgement takes no transmission time
(i.e., only propogation time), the acknowledgement will arrive
back at A in:
Time for first packet to get from A to C +
Time for acknowldgement to get from C back to A
62.2 ms (calculated in 1b) +
12 ms
74.2 ms.
Number of packets A transmitted in this time:
(10 Mb/s / 8*8192 bits/packet) * 74.2 ms
11.3 packets
Does B's queue overflow?
Yes
NOTE: if you assumed that the queue size for 1d was 20 (the
wording of the problem was unclear) the answer is no.
2a.
Propagation delay for 20Km fiber link with speed of light
being 2x10^8 m/s =
20 Km / 2*10e8 = 0.0001 s = .1 ms = 100 us
2b.
A suitable ARQ timeout value should be at least bigger than
round trip time, so at least 200 us.
2c.
Acknowledgement and/or packet may be corrupted or lost due
to transmission errors, thus we still may have to retransmit.
3.
Once RWS equals SWS, the receiver can buffer any frame that
the sender sends, so no need for a larger RWS.
4.
Under different assumptions there are two different answers
for this question. If you state that you assume that
the receiver can not receive out of order and that packets
are strictly FIFO, then the answer is enough bits to encode
a sequence number 1 larger than the desired window size, which
is:
ceiling (log base 2 ((Round Trip Time * Transfer Rate / Packet Size)+1))
ceiling (log base 2 ((1.25 sec. * 2 * 1 Mb/s / 1024*8 bits/packet) + 1))
ceiling (log base 2 (306.17))
ceiling (8.26)
9 bits
Without these assumptions, the answer should be twice the
window size which is:
ceiling (log base 2 ((Round Trip Time * Transfer Rate / Packet Size)*2))
ceiling (log base 2 ((1.25 sec * 2 * 1 Mb/s / 1024*8 bits/packet)*2))
ceiling (log base 2 (610.35))
ceiling (9.25)
10 bits
5.
The reciever would need an extra timer if the sender did not
probe because once the advertised window falls to zero, the
sender will cease sending packets and since the advertised window
is set in an acknowledgement packet, the sender will never discover
when the window is no longer zero. The extra timer on the receiver's
end would be needed to discover when the window was no longer zero
and to signal the sender of this fact.
ANDY'S ANSWER:
The receiver can recognize when there is space because it will
happen when the receiving application reads from the buffer. This
should be a fairly easy check to add. The problem is that the packet
telling the sender to restart might get lost, and that would have to
be resent. The algorithm of the receiver continually waking up and
sending a message if there is space is sufficient, but in reality you
only need to do this between when space was made available and when
you start getting data again.
6.
For the sequence number, you need enough bits such that you
don't reuse a sequence number within the maximum segment lifetime.
We can find this by computing how many sequence numbers the
network could possibly use within the specified segment lifetime
and make sure that the number of bits used in sequence number
can encode at least this number. So the solution is:
ceiling (log base 2 ( Transfer Rate * Max. Seg. Life.))
ceiling (log base 2 ( 100 Mb/s * 60 sec / 8 bits/byte))
ceiling (log base 2 (7.5e+08))
ceiling (29.48)
30 bits
For the advertised window, we want to be able to encode a value
large enough to allow the sender to completely fill the pipeline
as long as the receiver has the buffer space. To calculate this
number we find the number of bytes that can be sent within a
round trip time and make sure that the advertised window can encode
at least this number. So the solution is:
ceiling (log base 2 ( Transfer Rate * Round Trip Time));
ceiling (log base 2 ( 100 Mb/s * 100 ms / 8 bits/byte))
ceiling (log base 2 (1250000))
ceiling (20.25)
21 bits