# Computer Network HW3

## R14

* a
* False. Host B will send the acknowledgments to Host A.
* b
* False. The `rwnd` will change due to congestion control.
* c
* True.
* d
* False. If the size of the segment is k, then the subsequent sequence number will be m + k.
* e
* True.
* f
* False. Sample RTT is 1 sec, but the value of Estimated RTT and DevRTT could be quite small. It is possible that the TimeoutInterval is less than 1 sec.
* g
* False. The acknowledgment number of packet which corresponds to the segment from Host B to Host A is 42.

## R15

* a
* 110 - 90 = 20 byte
* b
* ack number = 90

## R16

* 3 segments
* First segment : seq = 43, ack = 80
* Second segment : seq = 80, ack = 44
* Third segment : seq = 44, ack = 81

## R19

$\because 4\cdot RTT_{FE} + RTT_{BE} + ProcessTime < 4\cdot RTT + ProcessTime$

$\therefore 4\cdot RTT_{FE} < 3.5\cdot RTT$

$\therefore RTT_{FE} < 0.875 \cdot RTT$

## P1

* a
* source port = 33000, destination port = 80
* b
* source port = 80, destination port = 33000
* c
* One of the following answers
* No, HTTP use TCP protocol.
* Possible, HTTP/3 use QUIC protocol which is implemented in UDP
* d
* Yes, if supported by the server

## P2

| | source port | destination port | source ip address | destination ip address |
| --- | --- | --- | --- | --- |
| B -> C | 80 | 7532 | B | C |
| B -> C | 80 | 26145 | B | C |
| B -> A | 80 | 26145 | B | A |

## P3

* one's complement = 11010001
* To detect errors, the receiver adds the four words (the three original words and the
checksum). If the sum contains a zero, the receiver knows there has been an error. All
one-bit errors will be detected, but two-bit errors can be undetected.

## P4

* Because the sum is 10001111 11111111 which contains zero, the received seqment has corrupted.
* It can either discard the segment or notify the application layer that
a corrupted segment has been received

## P9


## P15

* Transmission rate = 1Gbps
* RTT = 30 millisecond

$\frac{1500 bytes \cdot 8\ bits/byte }{1\rm{Gbps}} = 0.012\ millisecond$

$\frac{0.012\ n}{30.012} = 0.98$

$n \approx 2451$

## P19


## P22

* a
* from k - 4 to k
* b
* from k - 4 - 1 to k - 1

## P25

* a
* 10
* b
* No, due to TCP congestion control
* c
* PSH bit in header
* d
* Yes. As the channel is reliable, the application is guaranteed that each message will
correctly be delivered from the source to the destination. So the additional
mechanisms provided by TCP are not needed. Moreover, UDP encapsulates exactly
one character in a segment, since the application sends the input as a sequence of onecharacter messages. The segment is immediately sent to the network layer, thus
reducing delays and improving the user experience.

## P26

* a
* $2^{32} = 4,294,967,296$ possible sequence number
* b
* The number of segments is $\lceil \frac{2^{32}}{536} \rceil = 8,012,999$
* The size of total header is $66 \cdot 8,012,999 = 528,857,934$ bytes
* The total size of transfered segments is $528,857,934 + 2^{32}$
* It would take 249 seconds to transfer data.

## P27

* a
* sequence number = 207
* source port = 302
* destination port = 80

* b
* acknowledgment numbe = 207
* source port = 80
* destination port = 302

* c
* acknowledgment number = 127
* source port = 80
* destination port = 302

* d
* 

## P28

* Since the link capacity is only 100 Mbps, so host A’s sending rate can be at most
100Mbps. Still, host A sends data into the receive buffer faster than Host B can remove
data from the buffer. When the
buffer is full, Host B signals to Host A to stop sending data by setting RcvWindow = 0.
Host A then stops sending until it receives a TCP segment with RcvWindow > 0. Host A
will thus repeatedly stop and start sending as a function of the RcvWindow values it
receives from Host B.

## P29

* a
* The server uses special initial sequence number (that is obtained from the hash of
source and destination IPs and ports) in order to defend itself against SYN FLOOD
attack.
* b
* No, the attacker cannot create half-open or fully open connections by simply sending
and ACK packet to the target. Half-open connections are not possible since a server
using SYN cookies does not maintain connection variables and buffers for any
connection before full connections are established. For establishing fully open
connections, an attacker should know the special initial sequence number
corresponding to the (spoofed) source IP address from the attacker. This sequence
number requires the "secret" number that each server uses. Since the attacker does not
know this secret number, she cannot guess the initial sequence number.
* c
* No, the sever can simply add in a time stamp in computing those initial sequence
numbers and choose a time to live value for those sequence numbers, and discard
expired initial sequence numbers even if the attacker replay them.

## P31

* $DevRTT = (1 - \beta)DevRTT + \beta |SampleRTT -EstimatedRTT|$
* $EstimatedRTT = (1 - \alpha)EstimatedRTT + \alpha SamplRTT$
* $TimeoutInterval = EstimatedRTT + 4 \cdot DevRTT$
* $\alpha = 0.125, \beta = 0.25, EstimatedRTT = 100 ms, DevRTT = 5ms$

| SampleRTT | EstimatedRTT | DevRTT | TimeoutInterval |
| --- | --- | --- | --- |
| 106 ms | 0.875 * 100 + 0.125 * 106 = 100.75 ms | 0.75 * 5 + 0.25 * \|106 - 100\| = 5.25 ms | 100.75 + 4 * 5.25 = 121.75 ms |
| 120 ms | 0.875 * 100.75 + 0.125 * 120 = 103.16 ms | 0.75 * 5.25 + 0.25 * \|120 – 100.75\| = 8.75 ms | 103.16 + 4 * 8.75 = 138.16 ms |
| 140 ms | 0.875 * 103.16 + 0.125 * 140 = 107.76 ms | 0.75 * 8.75 + 0.25 * \|140 – 103.16\| = 15.77 ms | 107.76 + 4 * 15.77 = 170.84 ms |
| 90 ms | 0.875 * 107.76 + 0.125 * 90 = 105.54 ms | 0.75 * 15.77 + 0.25 * \|90 – 107.76\| = 16.27 ms | 105.54 + 4 * 16.27 = 170.62 ms |
| 115 ms | 0.875 * 105.54 + 0.125 * 115 = 106.72 ms | 0.75 * 16.27 + 0.25 * \| 115 – 105.54 \| = 14.57 ms | 106.72 + 4 * 14.57 =165 ms |

## P32

* Denote $EstimatedRTT^{(n)}$ for the estimate after the $n$th sample

* a
* $EstimatedRTT^{(4)} = xSampleRTT_1 + (1-x)xSampleRTT_2 + (1-x)^2xSampleRTT_3 + (1-x)^3SampleRTT_4$

* b
* $EstimatedRTT^{(n)} = x\sum_{j=1}^{n-1}(1-x)^{j-1}SampleRTT_j + (1-x)^{n-1}SampleRTT_n$

* c
* $EstimatedRTT^{(\infty)} = \frac{x}{1-x}\sum_{j=1}^{\infty}(1-x)^jSampleRTT_j = \frac{1}{9}\sum_{j=1}^{\infty}0.9^jSampleRTT_j$
* The weight given to past samples decays exponentially.

## P34

At any given time t, SendBase – 1 is the sequence number of the last byte that the
sender knows has been received correctly, and in order, at the receiver. The actually last
byte received (correctly and in order) at the receiver at time t may be greater if there are
acknowledgements in the pipe. Thus

$SendBase–1 \le LastByteRcvd$

## P35

When, at time t, the sender receives an acknowledgement with value y, the sender knows
for sure that the receiver has received everything up through y-1. The actual last byte
received (correctly and in order) at the receiver at time t may be greater if y 
SendBase or if there are other acknowledgements in the pipe. Thus

$y -1 \le LastByteRvcd$

## P37

* a
* GoBackN
* A sends 9 segments in total. They are initially sent segments 1, 2, 3, 4, 5 and later resent segments 2, 3, 4, and 5.
* B sends 8 ACKs. They are 4 ACKS with sequence number 1, and 4 ACKS with
sequence numbers 2, 3, 4, and 5.
* Selective Repeat
* A sends 6 segments in total. They are initially sent segments 1, 2, 3, 4, 5 and later resent segments 2.
* B sends 5 ACKs. They are 4 ACKS with sequence number 1, 3, 4, 5. And there is one
ACK with sequence number 2.
* TCP
* A sends 6 segments in total. They are initially sent segments 1, 2, 3, 4, 5 and later resent segments 2.
* B sends 5 ACKs. They are 4 ACKS with sequence number 2. There is one ACK with
sequence numbers 6. Note that TCP always send an ACK with expected sequence
number
* b
* TCP. This is because TCP uses fast retransmit without waiting until time out.

## P39

If the arrival rate increases beyond R/2 in Figure 3.46(b), then the total arrival rate to the
queue exceeds the queue’s capacity, resulting in increasing loss as the arrival rate
increases. When the arrival rate equals R/2, 1 out of every three packets that leaves the
queue is a retransmission. With increased loss, even a larger fraction of the packets
leaving the queue will be retransmissions. Given that the maximum departure rate from
the queue for one of the sessions is R/2, and given that a third or more will be
transmissions as the arrival rate increases, the throughput of successfully deliver data can
not increase beyond $\lambda_{out}$. Following similar reasoning, if half of the packets leaving the
queue are retransmissions, and the maximum rate of output packets per session is R/2,
then the maximum value of $\lambda_{out}$ is (R/2)/2 or R/4.

## P40

* a
* TCP slowstart is operating in the intervals [1,6] and [23,26]
* b
* TCP congestion avoidance is operating in the intervals [6,16] and [17,22]
* c
* After the 16th transmission round, packet loss is recognized by a triple duplicate
ACK. If there was a timeout, the congestion window size would have dropped to 1.
* d
* After the 22nd transmission round, segment loss is detected due to timeout, and hence
the congestion window size is set to 1.
* e
* The threshold is initially 32, since it is at this window size that slow start stops and
congestion avoidance begins
* f
* The threshold is set to half the value of the congestion window when packet loss is
detected. When loss is detected during transmission round 16, the congestion
windows size is 42. Hence the threshold is 21 during the 18th transmission round.
* g
* The threshold is set to half the value of the congestion window when packet loss is
detected. When loss is detected during transmission round 22, the congestion
windows size is 29. Hence the threshold is 14 (taking lower floor of 14.5) during the
24th transmission round.
* h
* During the 1st transmission round, packet 1 is sent; packet 2-3 are sent in the 2nd
transmission round; packets 4-7 are sent in the 3rd transmission round; packets 8-15
are sent in the 4th transmission round; packets 16-31 are sent in the 5th transmission
round; packets 32-63 are sent in the 6th transmission round; packets 64 – 96 are sent
in the 7th transmission round. Thus packet 70 is sent in the 7th transmission round.
* i
* The threshold will be set to half the current value of the congestion window (8) when
the loss occurred and congestion window will be set to the new threshold value + 3
MSS . Thus the new values of the threshold and window will be 4 and 7 respectively
* j
* threshold is 21, and congestion window size is 4.
* k
* round 17, 1 packet; round 18, 2 packets; round 19, 4 packets; round 20, 8 packets;
round 21, 16 packets; round 22, 21 packets. So, the total number is 52.

## P44

* a
* It takes 1 RTT to increase CongWin to 7 MSS; 2 RTTs to increase to 8 MSS; 3 RTTs
to increase to 9 MSS; 4 RTTs to increase to 10 MSS; 5 RTTs to increase to 11 MSS; 6
RTTs to increase to 12 MSS.
* b
* In the first RTT 6 MSS was sent; in the second RTT 7 MSS was sent; in the third
RTT 8 MSS was sent; in the fourth RTT 9 MSS was sent; in the fifth RTT, 10 MSS
was sent; and in the sixth RTT, 11 MSS was sent. Thus, up to time 6 RTT,
6+7+8+9+10+11 = 51 MSS were sent (and acknowledged). Thus, we can say that the
average throughput up to time 6 RTT was (51 MSS)/(6 RTT) = 8.5 MSS/RTT.

## P45

* a
* The loss rate, L , is the ratio of the number of packets lost over the number of packets
sent. In a cycle, 1 packet is lost. The number of packets sent in a cycle is
$$
\begin{split}
\frac{W}{2} + (\frac{W}{2} + 1) + \dots + W & = \sum_{n = 0}^{\frac{W}{2}}(\frac{W}{2} + n) \\
& = (\frac{W}{2} + 1)\frac{W}{2} + \sum_{n=0}^{\frac{W}{2}}n \\
& = \frac{3}{8} W^2 + \frac{3}{4}W
\end{split}
$$
Thus the loss rate is
$$
L = \frac{1}{\frac{3}{8} W^2 + \frac{3}{4}W}
$$

* b
* For $W$ large, $\frac{3}{8}W^2 >> \frac{3}{4}W$. Thus $L \approx \frac{3}{8}W^2$ or $W \approx \sqrt{\frac{8}{3L}}$. From the text, we
therefore have
$$
\begin{split}
\text{average throughput} & = \frac{3}{4}\sqrt{\frac{8}{3L}}\cdot \frac{MSS}{RTT} \\
& = \frac{1.22\cdot MSS}{RTT\cdot \sqrt{L}}
\end{split}
$$

## P46

* a
* Let W denote the max window size measured in segments. Then, W * MSS/RTT =
10Mbps, as packets will be dropped if the maximum sending rate exceeds link
capacity. Thus, we have W * 1500 * 8 / 0.15=10 * 10^6, then W is about 125 segments.
* b
* As congestion window size varies from W/2 to W, then the average window size is
0.75W=94 (ceiling of 93.75) segments. Average throughput is 94 * 1500 * 8 / 0.15
=7.52Mbps.
* c
* 125/2 * 0.15 = 9.375 seconds, as the number of RTTs (that this TCP connections needs
in order to increase its window size from W/2 to W) is given by W/2. Recall the
window size increases by one in each RTT.

## P47

Let W denote max window size. Let S denote the buffer size. For simplicity, suppose
TCP sender sends data packets in a round by round fashion, with each round
corresponding to a RTT. If the window size reaches W, then a loss occurs. Then the
sender will cut its congestion window size by half, and waits for the ACKs for W/2
outstanding packets before it starts sending data segments again. In order to make sure
the link always busying sending data, we need to let the link busy sending data in the
period W/(2 * C) (this is the time interval where the sender is waiting for the ACKs for the

W/2 outstanding packets). Thus, S/C must be no less than W/(2 * C), that is, S>=W/2.
Let Tp denote the one-way propagation delay between the sender and the receiver.
When the window size reaches the minimum W/2 and the buffer is empty, we need to
make sure the link is also busy sending data. Thus, we must have W/2/(2Tp)>=C, thus,
W/2 >= C * 2Tp.

Thus, S >= C * 2Tp

## P48

* a
* Let W denote the max window size. Then, W * MSS/RTT = 10Gbps, as packets will
be dropped if maximum sending rate reaches link capacity. Thus, we have
W * 1500 * 8/0.15=10 * 10^9, then W= 125000 segments.
* b
* As congestion window size varies from W/2 to W, then the average window size is
0.75W=93750 segments. Average throughput is 93750 * 1500 * 8/0.1=7.5Gbps.
* c
* 125000/2 * 0.15 /60= 156.25 minutes. In order to speed up the window increase process,
we can increase the window size by a much larger value, instead of increasing
window size only by one in each RTT. Some protocols are proposed to solve this
problem, such as ScalableTCP or HighSpeed TCP.

## P49

As TCP’s average throughput B is given by $B = \frac{1.22\cdot MSS}{RTT\cdot \sqrt{L}}$, so we know that, $L= (1.22*MSS / (B*RTT) )^2$

Since between two consecutive packet losses, there are $1/L$ packets sent by the TCP
sender, thus, $T=(1/L)*MSS/B$. Thus, we find that $T=B*RTT^2/(1.22^2*MSS)$, that is, T is a
function of B.

## P50

* a
* C1’s and C2’s window sizes are 1 segment (**note: if this problem is in the exam, then the answer should be at least described by table**)
* b
* No. In the long run, C1’s bandwidth share is roughly twice as that of C2’s, because
C1 has shorter RTT, only half of that of C2, so C1 can adjust its window size twice as
fast as C2. If we look at the above table, we can see a cycle every 200msec, e.g. from
850msec to 1000msec, inclusive. Within a cycle, the sending rate of C1 is
(40+20+40+20) = 120, which is thrice as large as the sending of C2 given by
(10+10+10+10) = 40.

## P51

* a
* Similarly as in last problem, we can compute their window sizes over time in the
following table. Both C1 and C2 have the same window size 2 after 2200msec.

* b
* Yes, this is due to the AIMD algorithm of TCP and that both connections have the ame RTT.
* c
* Yes, this can be seen clearly from the above table. Their max window size is 2.
* d
* No, this synchronization won’t help to improve link utilization, as these two connections act as a single connection oscillating between min and max window size.
Thus, the link is not fully utilized (recall we assume this link has no buffer). One
possible way to break the synchronization is to add a finite buffer to the link and
randomly drop packets in the buffer before buffer overflow. This will cause different
connections cut their window sizes at different times. There are many AQM (Active
Queue Management) techniques to do that, such as RED (Random Early Detect), PI
(Proportional and Integral AQM), AVQ (Adaptive Virtual Queue), and REM (Random Exponential Marking), etc.

## P52

Note that W represents the maximum window size.
First we can find the total number of segments sent out during the interval when TCP
changes its window size from W/2 up to and include W. This is given by:
$$S = W/2 + (W/2)*(1+\alpha) + (W/2)*(1+\alpha)^2 + (W/2)*(1+\alpha)^3 + \dots + (W/2)(1+\alpha)^k$$
We find $k=log_{1+\alpha}2$, then $S=W*(2\alpha+1)/(2\alpha)$.

Loss rate L is given by:
$$L=1/S=(2\alpha)/(W*(2\alpha+1))$$

The time that TCP takes to increase its window size from W/2 to W is given by:
$$k*RTT=(log_{1+\alpha}2)*RTT$$
which is clearly independent of TCP’s average throughput.

Note, TCP’s average throughput is given by:
$$B=MSS * S/((k+1)*RTT) = MSS / (L*(k+1)*RTT)$$

Note that this is different from TCP which has average throughput: $B = \frac{1.22\cdot MSS}{RTT\cdot \sqrt{L}}$, where the square root of L appears in the denominator.

## P53

Let’s assume 1500-byte packets and a 100 ms round-trip time. From the TCP throughput
$B = \frac{1.22\cdot MSS}{RTT\cdot \sqrt{L}}$, we have

$$
10Gbps = 1.22 * (1500*8 bits) / (.1 sec * \sqrt{L})\\
\sqrt{L} = 14640 bits / (10^9 bits) = 0.00001464\\
L = 2.14 * 10^{-10}
$$

If B = 100Gbps, then

$$
L = 2.14*10^{-12}
$$

## P56

* a
* $RTT + RTT + S/R + RTT + S/R + RTT + 12S/R = 4RTT + 14 S/R$
* b
* $RTT+RTT + S/R + RTT + S/R + RTT + S/R + RTT + 8S/R = 5RTT +11 S/R$
* c
* $RTT + RTT + S/R + RTT + 14 S/R = 3 RTT + 15 S/R$