aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-11-22 08:54:47 -0700
committerJack Sangdahl <[email protected]>2024-11-22 08:54:47 -0700
commit7d3c6e7fbd03645c90613f0140b6597c6dcc2e43 (patch)
treec5a73c1c29c0bee0a5ad8cff5fb012315bb323ce
parent17b2b82eba368c8407b05c5bdee6b7c29b8c6abe (diff)
downloadecen5273-7d3c6e7fbd03645c90613f0140b6597c6dcc2e43.tar.gz
ecen5273-7d3c6e7fbd03645c90613f0140b6597c6dcc2e43.zip
Problem Set 3
Signed-off-by: Jack Sangdahl <[email protected]>
-rw-r--r--problem_sets/ps3.pdfbin0 -> 175324 bytes
-rw-r--r--problem_sets/ps3.typ274
2 files changed, 274 insertions, 0 deletions
diff --git a/problem_sets/ps3.pdf b/problem_sets/ps3.pdf
new file mode 100644
index 0000000..315d849
--- /dev/null
+++ b/problem_sets/ps3.pdf
Binary files differ
diff --git a/problem_sets/ps3.typ b/problem_sets/ps3.typ
new file mode 100644
index 0000000..c4d8443
--- /dev/null
+++ b/problem_sets/ps3.typ
@@ -0,0 +1,274 @@
+#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"$.