diff options
author | Jack Sangdahl <[email protected]> | 2024-11-22 08:54:47 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-11-22 08:54:47 -0700 |
commit | 7d3c6e7fbd03645c90613f0140b6597c6dcc2e43 (patch) | |
tree | c5a73c1c29c0bee0a5ad8cff5fb012315bb323ce | |
parent | 17b2b82eba368c8407b05c5bdee6b7c29b8c6abe (diff) | |
download | ecen5273-7d3c6e7fbd03645c90613f0140b6597c6dcc2e43.tar.gz ecen5273-7d3c6e7fbd03645c90613f0140b6597c6dcc2e43.zip |
Problem Set 3
Signed-off-by: Jack Sangdahl <[email protected]>
-rw-r--r-- | problem_sets/ps3.pdf | bin | 0 -> 175324 bytes | |||
-rw-r--r-- | problem_sets/ps3.typ | 274 |
2 files changed, 274 insertions, 0 deletions
diff --git a/problem_sets/ps3.pdf b/problem_sets/ps3.pdf Binary files differnew file mode 100644 index 0000000..315d849 --- /dev/null +++ b/problem_sets/ps3.pdf 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"$. |