diff options
author | Jack Sangdahl <[email protected]> | 2024-12-13 14:21:21 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-12-13 14:21:21 -0700 |
commit | d3b273cbebd8a4d6b890d11bd4ae505b45abf739 (patch) | |
tree | 9b70380fa8b6ebc9ad756c58a69d3c16019fc1d9 | |
parent | 24f111e3dff96dfafcef6676b9c21ef4d257b53e (diff) | |
download | ecen5273-d3b273cbebd8a4d6b890d11bd4ae505b45abf739.tar.gz ecen5273-d3b273cbebd8a4d6b890d11bd4ae505b45abf739.zip |
Problem Set 1: Rewrite LaTeX -> Typst
Signed-off-by: Jack Sangdahl <[email protected]>
-rw-r--r-- | problem_sets/.gitignore | 5 | ||||
-rw-r--r-- | problem_sets/ps1.pdf | bin | 105455 -> 81123 bytes | |||
-rw-r--r-- | problem_sets/ps1.tex | 265 | ||||
-rw-r--r-- | problem_sets/ps1.typ | 293 |
4 files changed, 293 insertions, 270 deletions
diff --git a/problem_sets/.gitignore b/problem_sets/.gitignore index bf7e12b..bb2ede3 100644 --- a/problem_sets/.gitignore +++ b/problem_sets/.gitignore @@ -1,7 +1,2 @@ -*.log -*.aux -*.fdb_latexmk -*.fls -*.synctex.gz *_questions.pdf img diff --git a/problem_sets/ps1.pdf b/problem_sets/ps1.pdf Binary files differindex 1bc473e..2da2b30 100644 --- a/problem_sets/ps1.pdf +++ b/problem_sets/ps1.pdf diff --git a/problem_sets/ps1.tex b/problem_sets/ps1.tex deleted file mode 100644 index 8bd8df3..0000000 --- a/problem_sets/ps1.tex +++ /dev/null @@ -1,265 +0,0 @@ -\documentclass[11pt]{article} -\usepackage{amsmath, amsthm, amssymb, fancyhdr, pgfplots} -\usepackage[headsep=5mm]{geometry} -\renewcommand{\baselinestretch}{1.2} -\fancypagestyle{firstpage} { - \lhead{Problem Set 1 (ECEN 5273) 2024-09-17} - \rhead{Jack Sangdahl} - \renewcommand{\footrulewidth}{0pt} - \renewcommand{\headrulewidth}{0.4pt} -} -\begin{document} -\thispagestyle{firstpage} -\begin{enumerate} - \item What advantage does a circuit-switched network have over a packet-switched network? - - A circuit-switched network can guarantee a certain amount of end-to-end bandwidth for the duration of - data transmission. Most packet-switched networks (ie. the internet) cannot make any end-to-end guarantees - with regard to bandwidth. - - \item What advantage does TDM have over FDM in a circuit-switched network? - - FDM requires sophisticated analogue hardware to shift signal into appropriate frequency bands. TDM is simple to implement, but it requires clock synchronisation nodes. - - \item We consider sending real-time voice from host A to host B over a packet-switched network. Host A converts analogue voice to a digital 65 Kbps bit stream and sends these bits into 56-byte packets. There is one link between hosts A and B and the transmission rate is 1 Mbps and its propagation delay is 20 ms. As soon as host A gathers a packet, it sends it to host B. As soon as Host B receives an entire packet, it converts the packet's bits into an analogue signal. How much time elapses from the time a bit is created until the bit is decoded? - - Consider first bit in a packet. Before this bit can be transmitted, all of the bits in the packet must be generated. This requires: - \[ - \frac{56 \times 8}{65 \times 10^3} = 0.006892\text{ sec} - \] - The time required to transmit the packet is: - \[ - \frac{56 \times 8}{1 \times 10^6} = 0.000448\text{ sec} - \] - The propagation delay is 0.02 seconds, meaning the delay until decoding is: - \[ - 0.006892 + 0.000448 + 0.02 = 0.02734\text{ sec} - \] - A similar analysis shows that all bits experience a delay of 27.34 ms delay. Note, the answer could include decoding time at host B too. - - \item Consider a Go-Back-N sliding window algorithm (1 packet is 250 bytes long) running over a 100 Km point-to-point fibre link with bandwidth of 100 Mbps. - \begin{enumerate} - \item Compute the one-way propagation delay for this link, assuming that the speed of light is $2 \times 10^8$ m/s in the fibre. - - \[ - \frac{100\text{ Km}}{2 \times 10^8\text{ ms}} = 0.0005\text{ sec} - \] - - \item Suggest a suitable timeout value for the algorithm to use. List factors you need to consider. - - If we assume the transmission time of acknowledgement packets is similar to the data packet, the timeout needs to be greater than the packet transmission delay plus propagation delay, times 2: - \[ - 2\Big(\frac{250 \times 8}{1 \times 10^8} + 0.5\Big) = 2(0.02 + 0.5) = 1.04\text{ ms} - \] - - \item Suggest N to achieve 100\% utilisation in this link. - - Bandwidth times one-way delay: - \[ - (1 \times 10^8)(0.0005) = 50000\text{ bits} = \frac{50000}{8 \times 250} = 25\text{ packets} - \] - - \end{enumerate} - \item Suppose a 1 Gbps point-to-point link is being set up between the Earth and a new lunar colony. The distance from the moon to the Earth is approximately 385,000 Km, and data travels over the link at the speed of light \textemdash $\:3 \times 10^8$ m/s. - \begin{enumerate} - \item Calculate the minimum RTT for the link. - - Assuming that the packet transmission time is negligible, the minimum RTT can be found by 2 times the distance from moon to Earth, divided by speed of light: - \[ - \frac{2 \times 385000000}{3 \times 10^8\text{ ms}} = 2.57\text{ sec} - \] - - \item Using the RTT as the delay, calculate the bandwidth delay product for the link. - - Bandwidth delay product given by: - \[ - (1\text{ Gbps})(2.57\text{ sec}) = 2.57 \times 10^9\text{ bits} - \] - - \item What is the significance of the bandwidth delay product computed above? - - BDP represents the amount of data the sender can send before it's possible to receive a response. - In this context, bandwidth delay product refers to the product of a data link's capacity and its round-trip delay time. - The result, an amount of data, is equivalent to the maximum amount of data on the network circuit at any - given time, ie. the data that has been transmitted, but not yet acknowledged. - - \end{enumerate} - \item Host A wants to send a 1,000 KB file to host B. The RTT of the duplex link between host A and host B is 160 ms. Packet size is 1 KB. A handshake between A and B is needed before data packets can start transferring which takes $2 \times \text{RTT}$. Calculate the total required time of file transfer in the following cases. The transfer is considered complete when the acknowledgement for the final packet reaches A. - \begin{enumerate} - \item The bandwidth of the link is 4 Mbps. Data packets can be continuously transferred on the link. - - Total time given by the sum of initial handshake, transmit time for 1000 packets, RTT, and terminating handshake: - \[ - (5 \times 160) + \frac{2(1000) \times 8}{2(1000) \times 4} = 2.8\text{ sec} - \] - - \item The bandwidth of the link is 4 Mbps. After sending each packet, A needs to wait one RTT before the next packet can be transferred. - - Total time given by the sum of initial handshake, transmit time for 1 packet, RTT, terminating handshake, multiplied by 1000 packets: - \[ - 320 + 2 + (160 \times 1000) + 320 = 162.64\text{ sec} - \] - - \item Assume that we have "unlimited" bandwidth on the link, meaning that we assume transmit time to be zero. After sending 50 packets, A needs to wait one RTT before sending next group of 50 packets. - - Total time given by the sum of initial handshake, transmit time and RTT for 50 packets, multiplied by 20, and terminating handshake: - \[ - 320 + (160 \times 20) + 320 = 3.84\text{ sec} - \] - - \item The bandwidth of the link is 4 Mbps. During the first transmission, A can send one ($2^{1 - 1}$) packets, during the 2nd transmission A can send $2^{2 - 1}$ packets, during the 3rd transmission A can send $2^{3 - 1}$ packets, and so on. Assume A still needs to wait for 1 RTT between each transmission. - - Between each transmission, one RTT is required, so we need 10. Total time given by the sum of initial handshake, transmission time for 1000 packets, 10 RTT, and terminating handshake: - \[ - 14 \times 160 + 2 = 4.24\text{ sec} - \] - - \end{enumerate} - \item Determine the width of a bit on a 10 Gbps link. Assume a copper wire, where the speed of propagation is $2.3 \times 10^8$ m/s. - - Width of a bit on a 10 Gbps link is given by speed divided by bandwidth: - \[ - \frac{2.3 \times 10^8}{10 \times 10^9} = 0.023 \rightarrow 2.3\text{ cm/bit} - \] - Thus, a single bit has a width of 2.3 cm on the wire. - - \item Suppose two hosts, A and B, are separated by 20,000 Km and they are connected by a direct link of 1 Gbps. Suppose the propagation speed over the link is $2.5 \times 10^8$ m/s. - \begin{enumerate} - \item Calculate the BDP of the link. - \[ - 1 \times 10^9 \Big(\frac{20000 \times 10^3}{2.5 \times 10^8}\Big) = 80,000,000\text{ bits} - \] - \item Consider sending a file of 800,000 bits from host A to host B as one large message. What is the maximum number of bits that will be in the link at any given time? - - The maximum number of bits in the link is given by the smallest value of the file size or the BDP, so in this case, it's the file size of 800,000 bits. - - \item What is the width (in metres) of a bit in the link? - - \[ - \frac{2.5 \times 10^8}{10 \times 10^9} = 0.25\text{ metres} - \] - - \item Suppose now the file is broken up into 20 packets with each packet containing 40,000 bits. Suppose that each packet is acknowledged by the receiver and the transmission time of an acknowledgement packet is negligible. Finally, assume that the sender cannot send a packet until the preceding one is acknowledged. How long does it take to send the file? - - First calculate the propagation delay: - \[ - \frac{20000 \times 10^3}{2.5 \times 10^8} = 0.08\text{ sec} - \] - Next calculate transmission time per packet: - \[ - \frac{40000}{1 \times 10^9} = 0.00004\text{ sec} - \] - Total time given by number of packets times transmission time per packet, plus propagation delay: - \[ - 20(0.00004 + 2(0.08)) = 3.2\text{ sec} - \] - - \end{enumerate} - \item Suppose there is a 10 Mbps microwave link between a geostationary satellite and its base station on Earth. Every minute the satellite takes a digital photo and sends it to the base station. Assume a propagation speed of $2.4 \times 10^8$ m/s. The geostationary satellite is 36,000 Km away from Earth's surface. - \begin{enumerate} - \item What is the propagation delay of the link? - - \[ - \frac{36000}{2.4 \times 10^8} = 150\text{ ms} - \] - - \item What is the BDP, R times propagation delay? - - \[ - 150(10 \times 10^6) = 1500000 \rightarrow 1.5\text{ Mbit} - \] - - \item Let $x$ denote the size of the photo. What is the minimum value of $x$ for the microwave link to be continuously transmitting? - - Data is transferred at 10 Mbps, so 600 Mbits over period of 60 seconds. So\dots - \[ - \frac{600}{8} = 75\text{ Mbyte} - \] - - \end{enumerate} - \item Explain collision domain and broadcast domain with respect to a hub, switch, and a router - - \begin{itemize} - \item \textbf{Collision Domain}: the part of network where packet collisions can occur - \item \textbf{Broadcast Domain}: the part of network where a broadcast packet is forwarded, meaning it dictates how far a broadcast packet can tranverse - \item \textbf{Hub}: combines collision domains. Each port in a hub has same collision domain, meaning only one device can transmit a packet at a time - \item \textbf{Switch}: separates collision domain, alleviating the issue mentioned above, and combines broadcast domain - \item \textbf{Router}: separates broadcast domain - \end{itemize} - - \item Consider the following networked computers connected by bridge X and Y. Bridge X has interface 1, 2, and 3. Bridge Y has interface 1 and 2. Assume at the beginning the address tables of bridge X and Y are all empty. Write down the address tables of bridge X and Y after the following communication finished (Assume that the receiver does not respond to the packet sent by the sender). - \begin{enumerate} - \item A send packet to C - \item B send packet to D - \item C send packet to E - \item E send packet to A - \item D send packet to A - \end{enumerate} - \begin{center} - \begin{tabular} {| c | c |} - \hline - Address & Interface \\ - \hline - A & 1 \\ - \hline - B & 1 \\ - \hline - C & 2 \\ - \hline - E & 3 \\ - \hline - D & 3 \\ - \hline - \end{tabular} - \quad - \begin{tabular} {| c | c |} - \hline - Address & Interface \\ - \hline - A & 1 \\ - \hline - B & 1 \\ - \hline - C & 1 \\ - \hline - E & 2 \\ - \hline - D & 1 \\ - \hline - \end{tabular} - \end{center} - \item Given the extended LAN shown in Figure 2, indicate which ports are not selected by the spanning tree algorithm. Note that the bridge with the smallest ID becomes a root. - - Both ports beloning to B2, the port belonging to B5 spanning to F, and port belonging to B6 spanning to I, all are not selected by the spanning tree algorithm. - - \item Still considering Figure 2 above, if bridge B1 suffers catastrophic failure, indicate which ports are not selected by the spanning tree algorithm. - - If B1 fails, only the port belonging to B6 spanning to I is not selected. - - \item Consider the GBN protocol with a sender window size of 4 and a sequence number range of 1,024. Suppose that at time $t$, the next in-order packet that the receiver is expecting has a sequence number of $k$. Assume that the medium does not reorder messages. Answer the following questions: - \begin{enumerate} - \item What are the possible sets of sequence numbers inside the sender's window at time $t$? Justify your answer. - - Suppose receiver has received packet $k - 1$, as well as all other preceding packets, and has confirmed via an ACK. - If all of these ACKs have been acknowledged by the sender, then the sender's window is $[k, k + N - 1]$. - Next, suppose none of the ACKs have been received by the sender. In this case, the sender's window contains $k - 1$, - and the $N$ packets leading up to and including $k - N$. Now, the sender's window is $[k - N, k - 1]$, meaning - the sender's window is of size $N = 3$ and begins somewhere in range $[k - N, k]$. - - \item What are all the possible values of the ACK filed in all possible messages currently propagating back to the sender at time $t$? Justify your answer. - - If the receiver is waiting for packet $k$, it has acknowledged it has received packet $k - 1$, as well as $N - 1$ packets before that. - If none of these ACKs have been received by the sender, thn ACK messages with values of $[k - N, k - 1]$ may still be propagating back. - Since the sender has already sent $[k - N, k - 1]$, the sender must have already received an ACK for $k - N - 1$. - Once the receiver has acknowledged for $k - N -1$, it will never send an ACK that is less than $k - N - 1$. - - \item With the Go-Back-N protocol, is it possible for the seto receive an ACK for a packet that falls outside of its current window? Justify your answer with an example. - - Yes, this scenario is possible. Suppose the sender has a window size of 3 and sets packets 0, 1, and 2 at time T0. At time T1, - the receiver acknowledges packets 0, 1, and 2. At T2, the sender times out and retries sending packets 0, 1, and 2. At T3, - the receiver acknowledges the duplicate packets 0, 1, and 2. At T4, the sender receives the ACKs that the receiver sent at T1. - The sender's window is now packets 3, 4, and 5. At T5, the sender receives the ACKs that the receiver sent at T2. - - \end{enumerate} -\end{enumerate} -\end{document} diff --git a/problem_sets/ps1.typ b/problem_sets/ps1.typ new file mode 100644 index 0000000..c8740a4 --- /dev/null +++ b/problem_sets/ps1.typ @@ -0,0 +1,293 @@ +#show link: underline +== Problem Set 1 #h(1fr) Jack Sangdahl + +=== Problem 1 +What advantage does a circuit-switched network have over a packet-switched +network? + +A circuit-switched network can guarantee a certain amount of end-to-end +bandwidth for the duration of data transmission. Most packet-switched networks +(ie. the internet) cannot make any end-to-end guarantees with regard to +bandwidth. + +=== Problem 2 +What advantage does TDM have over FDM in a circuit-switched network? + +FDM requires sophisticated analogue hardware to shift signal into appropriate +frequency bands. TDM is simple to implement, but it requires clock +synchronisation nodes. + +=== Problem 3 +We consider sending real-time voice from host A to host B over a packet-switched +network. Host A converts analogue voice to a digital 65 Kbps bit stream and +sends these bits into 56-byte packets. There is one link between hosts A and B +and the transmission rate is 1 Mbps and its propagation delay is 20 ms. As soon +as host A gathers a packet, it sends it to host B. As soon as Host B receives an +entire packet, it converts the packet's bits into an analogue signal. How much +time elapses from the time a bit is created until the bit is decoded? + +Consider first bit in a packet. Before this bit can be transmitted, all of the +bits in the packet must be generated. This requires: + +$ (56 times 8)/(65 times 10^3) = 0.006892 "sec" $ + +The time required to transmit the packet is: + +$ (56 times 8)/(1 times 10^6) = 0.000448 "sec" $ + +The propagation delay is 0.02 seconds, meaning the delay until decoding is: + +$ 0.006892 + 0.000448 + 0.02 = 0.02734 " sec" $ +A similar analysis shows that all bits experience a delay of 27.34 ms delay. +Note, the answer could include decoding time at host B too. + +=== Problem 4 +Consider a Go-Back-N sliding window algorithm (1 packet is 250 bytes long) +running over a 100 Km point-to-point fibre link with bandwidth of 100 Mbps. + ++ Compute the one-way propagation delay for this link, assuming that the speed of + light is $2 times 10^8$ m/s in the fibre. + +$ (100 "km")/(2 times 10^8 "ms") = 0.0005 "sec" $ + ++ Suggest a suitable timeout value for the algorithm to use. List factors you need + to consider. + +$ 2((250 times 8)/(8 times 10^8) + 0.5) = 2(0.02 + 0.5) = 1.04 "ms" $ + ++ Suggest N to achieve 100% utilisation in this link. + +$ (1 times 10^8)(0.0005) = 50000 "bits" = 50000/(8 times 250) = 25 "packets" $ + +=== Problem 5 +Suppose a 1 Gbps point-to-point link is being set up between the Earth and a new +lunar colony. The distance from the moon to the Earth is approximately 385,000 +Km, and data travels over the link at the speed of light #sym.dash.em $3 times 10^8$ m/s. + ++ Calculate the minimum RTT for the link. + +Assuming that the packet transmission time is negligible, the minimum RTT can be +found by 2 times the distance from moon to Earth, divided by speed of light: + +$ (2 times 385000000)/(3 times 10^8 "ms") = 2.57 "sec" $ + ++ Using the RTT as the delay, calculate the bandwidth delay product for the link. + +Bandwidth delay product given by: + +$ (1 "Gbps")(2.57 "sec") = 2.57 times 10^9 "bits" $ + ++ What is the significance of the bandwidth delay product computed above? + +BDP represents the amount of data the sender can send before it's possible to +receive a response. In this context, bandwidth delay product refers to the +product of a data link's capacity and its round-trip delay time. The result, an +amount of data, is equivalent to the maximum amount of data on the network +circuit at any given time, ie. the data that has been transmitted, but not yet +acknowledged. + +=== Problem 6 +Host A wants to send a 1,000 KB file to host B. The RTT of the duplex link +between host A and host B is 160 ms. Packet size is 1 KB. A handshake between A +and B is needed before data packets can start transferring which takes $2 times "RTT"$. +Calculate the total required time of file transfer in the following cases. The +transfer is considered complete when the acknowledgement for the final packet +reaches A. + ++ The bandwidth of the link is 4 Mbps. Data packets can be continuously + transferred on the link. + +Total time given by the sum of initial handshake, transmit time for 1000 +packets, RTT, and terminating handshake: + +$ (5 times 160) + (2(1000) times 8)/(2(1000) times 4) = 2.8 "sec" $ + ++ Assume that we have "unlimited" bandwidth on the link, meaning that we assume + transmit time to be zero. After sending 50 packets, A needs to wait one RTT + before sending next group of 50 packets. + +Total time given by the sum of initial handshake, transmit time and RTT for 50 +packets, multiplied by 20, and terminating handshake: + +$ 320 + 160 times 20 + 320 = 3.84 "sec" $ + ++ The bandwidth of the link is 4 Mbps. During the first transmission, A can send + one ($2^(1 - 1)$) packets, during the 2nd transmission A can send $2^(2 - 1)$ packets, + during the 3rd transmission A can send $2^(3 - 1)$ packets, and so on. Assume A + still needs to wait for 1 RTT between each transmission. + +Between each transmission, one RTT is required, so we need 10. Total time given +by the sum of initial handshake, transmission time for 1000 packets, 10 RTT, and +terminating handshake: + +$ 14 times 160 + 2 = 4.24 "sec" $ + +=== Problem 7 +Determine the width of a bit on a 10 Gbps link. Assume a copper wire, where the +speed of propagation is $2.3 times 10^8$ m/s. + +Width of a bit on a 10 Gbps link is given by speed divided by bandwidth: + +$ (2.3 times 10^8)/(10 times 10^9) = 0.023 arrow.r 2.3 "cm/bit" $ + +Thus, a single bit has a width of 2.3 cm on the wire. + +=== Problem 8 +Suppose two hosts, A and B, are separated by 20,000 Km and they are connected by +a direct link of 1 Gbps. Suppose the propagation speed over the link is $2.5 times 10^8$ m/s. + ++ Calculate the BDP of the link. + +$ 1 times 10^9 ((20000 times 10^3)/(2.5 times 10^8)) = 80000000 "bits" $ + ++ Consider sending a file of 800,000 bits from host A to host B as one large + message. What is the maximum number of bits that will be in the link at any + given time? + +The maximum number of bits in the link is given by the smallest value of the +file size or the BDP, so in this case, it's the file size of 800,000 bits. + ++ What is the width (in metres) of a bit in the link? + +$ (2.5 times 10^8)/(10 times 10^9) = 0.25 "metres" $ + ++ Suppose now the file is broken up into 20 packets with each packet containing + 40,000 bits. Suppose that each packet is acknowledged by the receiver and the + transmission time of an acknowledgement packet is negligible. Finally, assume + that the sender cannot send a packet until the preceding one is acknowledged. + How long does it take to send the file? + +First calculate the propagation delay: + +$ (20000 times 10^3)(2.5 times 10^8) = 0.08 "sec" $ + +Next calculate transmission time per packet: + +$ 40000/(1 times 10^9) = 0.00004 "sec" $ + +Total time given by number of packets times transmission time per packet, plus +propagation delay: + +$ 20(0.00004 + 2(0.08)) = 3.2 "sec" $ + +=== Problem 9 +Suppose there is a 10 Mbps microwave link between a geostationary satellite and +its base station on Earth. Every minute the satellite takes a digital photo and +sends it to the base station. Assume a propagation speed of $2.4 times 10^8$ m/s. +The geostationary satellite is 36,000 Km away from Earth's surface. + ++ What is the propagation delay of the link? + +$ 36000/(2.4 times 10^8) = 150 "ms" $ + ++ What is the BDP, R times propagation delay? + +$ 150(10 times 10^6) = 1500000 arrow.r 1.5 "MBit" $ + ++ Let $x$ denote the size of the photo. What is the minimum value of $x$ for the + microwave link to be continuously transmitting? + +Data is transferred at 10 Mbps, so 600 Mbits over period of 60 seconds. So $600/8 = 75$ Mbyte. + +=== Problem 10 +Explain collision domain and broadcast domain with respect to a hub, switch, and +a router + +- *Collision Domain*: the part of network where packet collisions can occur +- *Broadcast Domain*: the part of network where a broadcast packet is forwarded, + meaning it dictates how far a broadcast packet can tranverse +- *Hub*: combines collision domains. Each port in a hub has same collision domain, + meaning only one device can transmit a packet at a time +- *Switch*: separates collision domain, alleviating the issue mentioned above, and + combines broadcast domain +- *Router*: separates broadcast domain + +=== Problem 11 +Consider the following networked computers connected by bridge X and Y. Bridge X +has interface 1, 2, and 3. Bridge Y has interface 1 and 2. Assume at the +beginning the address tables of bridge X and Y are all empty. Write down the +address tables of bridge X and Y after the following communication finished +(Assume that the receiver does not respond to the packet sent by the sender). + +#align(center)[ + #image("img/fig1.png", width: 70%) + Figure 1 +] + ++ A send packet to C ++ B send packet to D ++ C send packet to E ++ E send packet to A ++ D send packet to A + +#align( + center, +)[ + Bridge X + #table( + columns: 2, table.header[*Address*][*Interface*], [A], [1], [B], [1], [C], [2], [D], [3], [E], [3], + ) + Bridge Y + #table( + columns: 2, table.header[*Address*][*Interface*], [A], [1], [B], [1], [C], [1], [D], [2], [E], [1], + ) +] + +=== Problem 12 +Given the extended LAN shown in Figure 2, indicate which ports are not selected +by the spanning tree algorithm. Note that the bridge with the smallest ID +becomes a root. + +#align(center)[ + #image("img/fig2.png", width: 70%) + Figure 2 +] + +Both ports beloning to B2, the port belonging to B5 spanning to F, and port +belonging to B6 spanning to I, all are not selected by the spanning tree +algorithm. + +=== Problem 13 +Still considering Figure 2 above, if bridge B1 suffers catastrophic failure, +indicate which ports are not selected by the spanning tree algorithm. + +If B1 fails, only the port belonging to B6 spanning to I is not selected. + +=== Problem 14 +Consider the GBN protocol with a sender window size of 4 and a sequence number +range of 1,024. Suppose that at time $t$, the next in-order packet that the +receiver is expecting has a sequence number of $k$. Assume that the medium does +not reorder messages. Answer the following questions: + ++ What are the possible sets of sequence numbers inside the sender's window at + time $t$? Justify your answer. + +Suppose receiver has received packet $k - 1$, as well as all other preceding +packets, and has confirmed via an ACK. If all of these ACKs have been +acknowledged by the sender, then the sender's window is $[k, k + N - 1]$. Next, +suppose none of the ACKs have been received by the sender. In this case, the +sender's window contains $k - 1$, and the $N$ packets leading up to and +including $k - N$. Now, the sender's window is $[k - N, k - 1]$, meaning the +sender's window is of size $N = 3$ and begins somewhere in range $[k - N, k]$. + ++ What are all the possible values of the ACK filed in all possible messages + currently propagating back to the sender at time $t$? Justify your answer. + +If the receiver is waiting for packet $k$, it has acknowledged it has received +packet $k - 1$, as well as $N - 1$ packets before that. If none of these ACKs +have been received by the sender, thn ACK messages with values of $[k - N, k - 1]$ may +still be propagating back. Since the sender has already sent $[k - N, k - 1]$, +the sender must have already received an ACK for $k - N - 1$. Once the receiver +has acknowledged for $k - N -1$, it will never send an ACK that is less than $k - N - 1$. + ++ With the Go-Back-N protocol, is it possible for the seto receive an ACK for a + packet that falls outside of its current window? Justify your answer with an + example. + +Yes, this scenario is possible. Suppose the sender has a window size of 3 and +sets packets 0, 1, and 2 at time T0. At time T1, the receiver acknowledges +packets 0, 1, and 2. At T2, the sender times out and retries sending packets 0, +1, and 2. At T3, the receiver acknowledges the duplicate packets 0, 1, and 2. At +T4, the sender receives the ACKs that the receiver sent at T1. The sender's +window is now packets 3, 4, and 5. At T5, the sender receives the ACKs that the +receiver sent at T2. |