ecen5273

#show link: underline
== Problem Set 3 #h(1fr) Jack Sangdahl

=== Problem 1
Figure 1 below is a typical home network setup. An ISP modem provides internet
service; a wireless router is connected to the ISP Modem via Ethernet. Hosts A,
B, and C are connected to the wireless router to access the internet.

#align(center)[
  #image("img/fig1.png", width: 70%)
  Figure 1
]

+ In order for hosts A, B, and C to access the web server, Network Address
  Translation (NAT) with random port mapping needs to be enabled for both the
  wireless router and the ISP modem. Assume hosts will pick a random port number
  between 8000 and 9000, the wireless router can choose a random port number
  between 2000 and 2500, and the ISP modem can choose a random port number between
  3000 and 4000. Fill in the NAT table for the wireless router and ISP modem.

#align(
  center,
)[
NAT Table of Wireless Router
#table(
  columns: 2, table.header[*LAN Side*][*WAN Side*], [`192.168.0.5:8001`], [`10.0.1.5:2001`], [`192.168.0.11:8002`], [`10.0.1.5:2002`], [`192.168.0.22:8003`], [`10.0.1.5:2003`],
)
NAT Table of ISP Modem
#table(
  columns: 2, table.header[*LAN Side*][*WAN Side*], [`10.0.1.5:2001`], [`96.120.12.18:3001`], [`10.0.1.5:2002`], [`96.120.12.18:3002`], [`10.0.1.5:2003`], [`96.120.12.18:3003`],
)
]

+ Now we look into the details about how packets are exchanged between host B and
  the web server. Assume host B sends an HTTP request packet to the web server.
  And the web server then sends HTTP content back to host B. Fill in the tables
  below to show how the packet's IP header changes along the route.

#align(
  center,
)[
Request Before Entering Router
#table(
  columns: 2, [*Source IP*], [`192.168.0.11`], [*Source Port*], [`8002`], [*Destination IP*], [`216.58.217.36`], [*Destination Port*], [`80`],
)
Request After Exiting Router
#table(
  columns: 2, [*Source IP*], [`10.0.1.5`], [*Source Port*], [`2002`], [*Destination IP*], [`216.58.217.36`], [*Destination Port*], [`80`],
)
Request After Exiting Modem
#table(
  columns: 2, [*Source IP*], [`96.120.12.18`], [*Source Port*], [`3002`], [*Destination IP*], [`216.58.217.36`], [*Destination Port*], [`80`],
)
Response Before Entering Modem
#table(
  columns: 2, [*Source IP*], [`216.58.217.36`], [*Source Port*], [`80`], [*Destination IP*], [`96.120.12.18`], [*Destination Port*], [`3002`],
)
Response After Exiting Modem
#table(
  columns: 2, [*Source IP*], [`216.58.217.36`], [*Source Port*], [`80`], [*Destination IP*], [`10.0.1.5`], [*Destination Port*], [`2002`],
)
Response After Exiting Router
#table(
  columns: 2, [*Source IP*], [`216.58.217.36`], [*Source Port*], [`80`], [*Destination IP*], [`192.168.0.11`], [*Destination Port*], [`8002`],
)
]

+ Suppose now host A also runs a web server on port 8888 and it is attached to a
  domain name #link("http://www.mylocalhomeserver.com"). Explain what NAT entries
  should be added so that people from the internet can assess this web server via
  URL. You can assume that the above domain name is registered properly.

The following entries should be added for the router and modem. IP address `192.168.0.5` should
have port `8888`, and address `10.0.1.5` can have a random port number.

#align(
  center,
)[
NAT Table of Wireless Router
#table(
  columns: 2, table.header[*LAN Side*][*WAN Side*], [`192.168.0.5:8888`], [`10.0.1.5:8888`],
)
NAT Table of ISP Modem
#table(
  columns: 2, table.header[*LAN Side*][*WAN Side*], [`10.0.1.5:8888`], [`96.120.12.18:8888`],
)
]

+ The wireless link at the last mile is very error prone and you would like to
  improve the performance. What would you do in this case?

// TODO

=== Problem 2
Suppose a router has three input flows and one output flow. It receives the
packets listed in Table 1 below all at about the same time, in the order listed,
during a period in which the output port is busy, but all queues are otherwise
empty. Give the order in which the packets are transmitted, assuming...

#align(
  center,
)[
  #table(
    columns: 3, table.header[*Packet*][*Size*][*Flow*], [1], [200], [1], [2], [200], [1], [3], [160], [2], [4], [200], [2], [5], [160], [2], [6], [210], [3], [7], [120], [3], [8], [90], [3],
  )
  Table 1
]

+ Fair Queueing

#align(
  center,
)[
  #table(
    columns: 4, table.header[*Packet*][*Size*][*Flow*][*Finish Time*], [1], [200], [1], [200], [2], [200], [1], [400], [3], [160], [2], [160], [4], [200], [2], [300], [5], [160], [2], [460], [6], [210], [3], [210], [7], [120], [3], [350], [8], [90], [3], [440],
  )
]

The order of packet transmission is determined by the finishing time. So as per
above, packets would transmit in the following order: *3, 1, 6, 4, 7, 2, 8, 5*.

+ Weighted fair queueing with flow 2 having twice as much share as flow 1, and
  flow 3 having 1.5 times as much share as flow 1. Note that ties are to be solved
  in the order of flow 1, 2, and 3.

#align(
  center,
)[
  #table(
    columns: 4, table.header[*Packet*][*Size*][*Flow*][*Finish Time (weighted)*], [1], [200], [1], [100], [2], [200], [1], [200], [3], [160], [2], [40], [4], [200], [2], [75], [5], [160], [2], [115], [6], [210], [3], [70], [7], [120], [3], [116.67], [8], [90], [3], [146.67],
  )
]

The order of packet transmission is determined by the finishing time. So as per
above, packets would transmit in the following order: *3, 6, 4, 1, 5, 7, 8, 2*.

=== Problem 3
Assume TCP Reno is the protocol experiencing the behaviour shown in Figure 2.

#align(center)[
  #image("img/fig2.png", width: 70%)
  Figure 2
]

+ Identify the RTT rounds when TCP runs Slow Start. (eg. From the 1st round to
  which?)

Slow Start occurs for the initial 6 RTT's, and the final 4 RTT's.

+ Identify the RTT rounds when TCP runs Congestion Avoidance.

Congestion Avoidance occurs from the 6th transmission, to the 19th transmission.

+ After the 14th RTT round, is segment loss detected by a triple duplicate ACK or
  by a timeout and why?

Segment loss is detected by a triple duplicate ACK, as otherwise the window will
have dropped to 0

+ During which RTT round is the 170th segment sent?

The 170th segment is sent during the 10th transmission.

+ Assuming a packet loss is detected after the 23rd RTT round by the receipt of
  the triple duplicate ACK's, what will be the value of the congestion window?

The value of the congestion window will be *4*.

=== Problem 4
Figure 3 below shows how two disconnected LANs are connected by IP tunneling
(the dashed line). For each interface, the IP and MAC addresses are shown in the
figure (HW1 through HW14 are used to represent the hardware address).

#align(center)[
  #image("img/fig3.png", width: 70%)
  Figure 3
]

Now host B sends a packet to host A. Show how the packet travels along the
route, describe header information along the route (B #sym.arrow.r R6, R6 #sym.arrow.r R3,
R3 #sym.arrow.r R2, R2 #sym.arrow.r R1, R1 #sym.arrow.r A).

#align(
  center,
)[
Host B to Router R6
#table(
  columns: 2, [*Source IP*], [`125.0.2.200`], [*Source MAC*], [`HW14`], [*Destination IP*], [`125.0.2.5`], [*Destination MAC*], [`HW13`],
)
Router R6 to Router R3 Inner IP header: Same as Host B to Router R6 Outer IP
header:
#table(
  columns: 2, [*Source IP*], [`23.30.1.108`], [*Source MAC*], [`HW12`], [*Destination IP*], [`128.38.81.4`], [*Destination MAC*], [`HW7`],
)
Router R3 to Router R2 Inner IP header: Same as Host A to Router R1 Outer IP
header:
#table(
  columns: 2, [*Source IP*], [`23.30.1.108`], [*Source MAC*], [`HW6`], [*Destination IP*], [`128.38.81.4`], [*Destination MAC*], [`HW5`],
)
Router R2 to Router R1 Inner IP header: Same as Host A to Router R1 Outer IP
header:
#table(
  columns: 2, [*Source IP*], [`23.30.1.108`], [*Source MAC*], [`HW4`], [*Destination IP*], [`128.38.81.4`], [*Destination MAC*], [`HW3`],
)
Router R1 to Host A
#table(
  columns: 2, [*Source IP*], [`125.0.2.200`], [*Source MAC*], [`HW2`], [*Destination IP*], [`125.0.2.5`], [*Destination MAC*], [`HW1`],
)
]

=== Problem 5
Derive the expected throughput of the following TCP congestion algorithm: The
additive increment factor is #sym.alpha. Multiplicative decrease #sym.beta,
which means after loss, the window's size will change from $W$ to $(1 - beta)W$.
Order the throughput for each flow. `AIMD(a, b)` means the CWND increases per
each round trip time and the CWND set to $(1 - beta)W$ for $W$ when the loss
happens.

#align(
  center,
)[
  #table(
    columns: 4, table.header[*Flow*][*AIMD*][*RTT*][*Loss*], [1], [$a = 1, b = 0.5$], [10ms], [$10^(-6)$], [2], [$a = 2, b = 0.2$], [100ms], [$10^(-8)$], [3], [$a = 5, b = 0.8$], [300ms], [$10^(-9)$], [4], [$a = 8, b = 0.4$], [1000ms], [$10^(-4)$], [5], [$a = 6, b = 0.5$], [100ms], [$10^(-10)$],
  )
]

To derive the expected throughput, use the Mathis equation for TCP throughput.

$ Tau approx (alpha) / ("RTT" times sqrt(p) times sqrt(beta)) $

Where #sym.alpha is the additive increase factor, #sym.beta is the
multiplicative decrease factor, $p$ is the packet loss probability, and RTT is
the round trip time. Apply this formula for each flow.

+ $alpha = 1, "RTT" = 10 "ms", p = 10^(-6), beta = 0.5$
$ Tau_1 approx (1) / (0.01 times sqrt(10^(-6)) times sqrt(0.5)) approx 141.4 "Mbps" $

+ $alpha = 2, "RTT" = 100 "ms", p = 10^(-8), beta = 0.2$
$ Tau_2 approx (2) / (0.1 times sqrt(10^(-8)) times sqrt(0.2)) approx 447.5 "Mbps" $

+ $alpha = 5, "RTT" = 300 "ms", p = 10^(-9), beta = 0.8$
$ Tau_3 approx (5) / (0.3 times sqrt(10^(-9)) times sqrt(0.8)) approx 186.4 "Mbps" $

+ $alpha = 8, "RTT" = 1000 "ms", p = 10^(-4), beta = 0.4$
$ Tau_4 approx (8) / (1 times sqrt(10^(-4)) times sqrt(0.4)) approx 1266.5 "Kbps" $

+ $alpha = 6, "RTT" = 100 "ms", p = 10^(-10), beta = 0.5$
$ Tau_5 approx (6) / (0.1 times sqrt(10^(-10)) times sqrt(0.5)) approx 848.5 "Mbps" $

Thus, the ordered throughput for each flow is given in descending size: *5, 2,
3, 1, 4*.

=== Problem 6
Suppose that TCP uses the combination of quick acknowledgements (quick ACK) and
delayed acknowledgements (delayed ACK). The quick ACK only triggers up to 8
packets (the CWND at the sender becomes 16 after receiving 8 quick ACKs)
starting from 1 packet during Slow Start. The maximum capacity of the link is
5000 KBps, the RTT is 10ms, and 1 MSS is equal to 1KB.

+ About what is CWND at the time of the first packet loss?

After the quick ACK phase, TCP switches to delayed ACKs, meaning the receiver
sends one ACK for every two packets. In Slow Start, the CWND roughly doubles
with each RTT, and begins at 16 in our current scenario. So after 1 RTT, CWND is
32 MSS, after 2 RTTs, CWND is 64 MSS, and so on. When considering packet loss,
it will occur when the CWND reaches the capacity of the link, which is 5000
KBps. This would be reached after roughly 7 RTTS, or when the CWND is
approximately 1024 MSS (1 MB).

+ About how long until the sender discovers the first loss?

As found above, it takes 7 RTTs to grow the CWND to 1024 MSS, which is the point
where packet loss is expected. The RTT is 10 ms, so the time to discover packet
loss is given by $7 "RTTs" * 10 "ms" = 70 "ms"$.