Tutorials

{0}------------------------------------------------

Computer Networks CSE14B

Tutorial 1 Error Detection

cn-cs-ewi@tudelft.nl

Delft University of Technology, The Netherlands

{1}------------------------------------------------

• O Parity bits
• 2 Parity words
• 8 Checksums
• 4 Cyclic redundancy checks (CRCs)

{2}------------------------------------------------

{3}------------------------------------------------

Question

The following bit strings are received messages with an parity bit added. Assuming an even parity, which of them are guaranteed to be wrong?

$001010101010_{(2)}$ $00111111111_{(2)}$ $001010001101_{(2)}$ $000101100010_{(2)}$

Suggested time for this exercise: 5 minute(s)

Image /page/3/Picture/5 description: The image shows a light blue button with the word "Hint" written in white text. There is a small triangle pointing to the right on the left side of the word "Hint".

Solution

Image /page/3/Picture/7 description: The image shows the logo for TU Delft. The logo consists of the text "TU Delft" in a sans-serif font. The background is a light blue color.

{4}------------------------------------------------

Question

In the previous question, you detected an error with one or more messages. Can you (as a receiver) determine the correct version of these $message(s)?$

Suggested time for this exercise: $2$ minute(s)

Image /page/4/Picture/4 description: The image shows a button with the word "Solution" on it.

{5}------------------------------------------------

Question

In the first question, we saw that parity bit method could not detect an error with some messages.

Can we be sure that these messages were correctly transmitted?

Suggested time for this exercise: $2$ minute(s)

Image /page/5/Picture/5 description: The image shows a blue button with the word "Solution" written on it.

{6}------------------------------------------------

Question

A sender and receiver communicate by a protocol which uses parity words for error detection. Both know that the data block is a $6 \times 8$ matrix and the protocol uses even parity. The receiver receives the following message:

Image /page/6/Figure/3 description: The image shows a grid of binary numbers (0s and 1s) arranged in rows and columns. The grid appears to represent a binary addition problem, with several rows of binary numbers being added together, and the result is shown at the bottom, separated by a horizontal line. The numbers are displayed in a red font against a light red background.

• a. Does the receiver find any error?
• b. Did the receiver receive the bit sequence correctly?

Suggested time for this exercise: $8$ minute(s)

Image /page/6/Picture/7 description: The image shows the logo for TU Delft. The logo consists of the text "TU Delft" in a sans-serif font. The letters "TU" are larger and bolder than the word "Delft". The background is a light blue color.

{7}------------------------------------------------

Suggested time for this exercise: 5 minute(s)

Image /page/7/Picture/3 description: The image shows a light blue button with the word "Solution" written in white text. A small black triangle is to the left of the word "Solution".

Image /page/7/Picture/4 description: The image shows the logo of TU Delft, a technical university in the Netherlands. The logo consists of the text "TU Delft" in a stylized font, with the letters slightly blurred and appearing to glow. The background is a light blue color.

{8}------------------------------------------------

Question

Alice wants to send the data $110100011_{(2)}$ to Bob. For error detection, they decided to use a CRC with the generator $1101_{(2)}$ . Compute the message that Alice sends.

Suggested time for this exercise: 10 minute(s)

Image /page/8/Picture/4 description: The image shows a blue button with the word "Solution" written on it.

{9}------------------------------------------------

Question

You received a message $110011100111100001_{(2)}$ . You know that CRC with a generator polynomial of 110010 was applied to the data before sending. Check whether there was an error during the transmission of the message.

(Note down the remainder of the division)

Suggested time for this exercise: $10$ minute(s)

Image /page/9/Picture/5 description: The image shows a blue button with the word "Solution" written on it.

{10}------------------------------------------------

Question

Ada is using a simple data link layer protocol that only appends one parity bit using even parity. However, the medium she is using is quite unreliable and hence the parity bit often fails to detect errors. She computes a CRC checkvalue and appends it to the message before forwarding it to the data link layer. She uses 10101 as the generator for the CRC.

If her original message is 10110100, which message does the data link layer transmit?

Suggested time for this exercise: 6 minute(s)

Image /page/10/Picture/5 description: The image shows the text "1 Hint" in a light blue rounded rectangle.

Solution

{11}------------------------------------------------

By completing this tutorial, you mastered:

• explaining properties of error detection algorithms
• applying key error detection algorithms
• · design variants of error detection algorithms

{12}------------------------------------------------

Hints

{13}------------------------------------------------

Hint: Parity Bit Q1

Hint

Hint

Remember that when the parity bit is even the sum of the data bits modulo 2 is 0.

< Back to Question

{14}------------------------------------------------

Hint: CRC - Parity

Hint

In which order are the error detection methods applied?

Back to Question

Image /page/14/Picture/4 description: The image shows the logo of TU Delft, a technical university in the Netherlands. The logo consists of the letters "TU Delft" in a sans-serif font, with the "TU" stacked vertically above "Delft". The logo is set against a light blue background.

{15}------------------------------------------------

Solutions

{16}------------------------------------------------

Answer

Method 1: Check if number of 1s in received messages is even: $0.01010101010_{(2)} \rightarrow 5 \mod 2 = 1 \rightarrow$ error 0011 1111 $$ mod 0010 1000 1101₍₂₎ 5 mod 2 = 1 error

Method 2: Consider message without parity bit, compute parity bit, and check if it fits.

00101010101₍₂₎ $\rightarrow$ 5, parity bit should be 1 $\rightarrow$ error 001111111111₍₂₎ $\rightarrow$ 9, parity bit should be 1 $\rightarrow$ ? 0010 1000 110 $_{(2)} \rightarrow 4$ , parity bit should be 0 error 0001 0110 001 , parity bit should be 0 ?

• Back to Question

{17}------------------------------------------------

Answer

No. Parity checks only detect errors but cannot correct them since we don't know where the error occurred.

Back to Question

{18}------------------------------------------------

Answer

No, we cannot be sure. Parity bits with even parity cannot detect errors that flip and even $(2, 4, 6, ...)$ number of bits. For example, if the sent bit stream is $111100000000_{(2)}$ and the received bit stream is ${1111111111}_{(}$ , the error is not detected.

• Back to Question

{19}------------------------------------------------

Answer

Checking columns

$$1+0+1+0+0+1+1=4 \rightarrow \text{even } \checkmark$$

\n

$$0+0+0+1+1+1+1=4 \rightarrow \text{even } \checkmark$$

\n

$$1+0+0+1+0+1+1=4 \rightarrow \text{even } \checkmark$$

\n

$$1+1+0+1+0+1+0=4 \rightarrow \text{even } \checkmark$$

\n

$$0+0+1+0+1+1+1=4 \rightarrow \text{even } \checkmark$$

\n

$$1+1+0+1+0+0+1=4 \rightarrow \text{even } \checkmark$$

\n

$$0+1+1+1+1+0+0=4 \rightarrow \text{even } \checkmark$$

\n

$$0+1+1+1+1+1+1=6 \rightarrow \text{even } \checkmark$$

No error detected.

Answers:

• a No. receiver cannot find an error.
• b The receiver cannot be sure about the correctness of the bit sequence. (See next page) $20/28$

Image /page/19/Picture/8 description: The image shows the logo of TU Delft, a technical university in the Netherlands. The logo consists of the letters "TU Delft" in a sans-serif font, with a stylized image of a building above the letters "TU".

{20}------------------------------------------------

Image /page/20/Figure/1 description: The image shows an answer to a question. The answer states that the bits shown in squares may have been flipped. There are seven rows of numbers, each row containing eight numbers. The numbers are either 0 or 1. Some of the numbers are enclosed in squares.

• Race or Question

{21}------------------------------------------------

Continued on next page

Back to Question

{22}------------------------------------------------

Image /page/22/Figure/1 description: The image shows an example of binary addition. The text "Answer Add carried-over bits 11 to remaining bits:" is at the top of the image. Below this text is the binary addition problem: 00010011 + 0000011 = 00010100. The text "Now flip bits to get 11101011." is at the bottom of the image.

● Back to Question

Image /page/22/Picture/3 description: The image shows the logo for TU Delft. The logo consists of the text "TUDelft" in a light blue color, with a stylized image of a bird or wing above the text. The background is a solid light blue color.

{23}------------------------------------------------

Answer

Our generator polynomial (1101) has degree of 3. So we append 3 zeros to the the end of $110100011_{(2)}$ and get $110100011000_{(2)}$ .

We then divide $110100011000_{(2)}$ by our polynomial (1011), by applying long division in polynomial arithmetic:

• $\blacktriangleright$ no carries,
• subtraction and addition are identical to XOR operation
• only track remainders (no need to track quotient at each division)

(Solution continues on the next slide.)

{24}------------------------------------------------

Image /page/24/Figure/1 description: The image shows the word "Answer" in white text on a green background.

Image /page/24/Figure/2 description: The image shows a binary subtraction problem. The top number is 110100011000. The number being subtracted is 1101. The result of the subtraction is 000000011000 with 1101 subtracted from the right side, resulting in 10.

Remainder is 10. Since the degree of the generator polynomial is 3, the remainder should have a length of 3 as well. We pad it with $zero(s)$ and obtain $010$ .

We append the remainder (010) to the data and obtain the sent message:

$110\,100\,011\,010_{(2)}$

Back to Question

{25}------------------------------------------------

Answer

Apply division modulo 2 without carries and check if the remainder is zero

Image /page/25/Figure/3 description: The image shows a binary long division problem. The dividend is 110011100111100001, and the divisor is 110010. The quotient is not explicitly shown, but the steps of the division are displayed. The remainder is 011011.

Since the remainder is not 0, there is an error.

< Back to Question

{26}------------------------------------------------

Answer

In the first step, Ada computes the checkvalue using long division:

Image /page/26/Picture/3 description: The image shows a binary long division problem. The dividend is 101101000000 and the divisor is 10101. The quotient is not explicitly shown, but the steps of the long division are displayed, including the subtractions and bringing down of digits. The final remainder is 00111.

The message sent to the data link protocol is the following:

101101000111

(Solution continues on the next page.)

{27}------------------------------------------------

Answer

Then, the data link layer calculates the parity bit as 1, and appends it to the message. The message transmitted by the data layer is:

1011010001111

• Back to Question

{28}------------------------------------------------

Computer Networks CSE14B

Tutorial 2 Error Correction

cn-cs-ewi@tudelft.nl

Delft University of Technology, The Netherlands

{29}------------------------------------------------

• O Parity blocks
• ² Hamming codes

{30}------------------------------------------------

{31}------------------------------------------------

Question

Compute the parity bits for the following data arranged in a parity block of 4 rows and 4 columns. Execute the computations first for even and then for odd parity.

Suggested time for this exercise: 8 minute(s)

Image /page/31/Picture/5 description: The image shows a light blue button with the word "Solution" written in white text. There is a small arrow pointing to the right next to the word "Solution".

{32}------------------------------------------------

Question

Compute an $(11,7)$ Hamming Code for $1010110_{(2)}$ using even parity.

Suggested time for this exercise: 10 minute(s)

Solution

{33}------------------------------------------------

Question

Assuming a (15,11)-Hamming Code using odd parity, we receive: $000110111010001_{(2)}$ . What should the original message (including parity bits) be if there was at most one error?

Suggested time for this exercise: 10 minute(s)

Image /page/33/Picture/4 description: The image shows a light blue button with rounded edges. Inside the button, there is a small, dark blue triangle pointing to the right, followed by the word "Solution" in a light-colored font.

{34}------------------------------------------------

By completing this tutorial, you mastered:

• · detecting and correcting bit errors
• applying key error correction algorithms

{35}------------------------------------------------

Hints

{36}------------------------------------------------

Solutions

{37}------------------------------------------------

Answer

Even parity:

Image /page/37/Figure/3 description: The image shows a table of binary numbers. The table has five rows and six columns. The first five columns contain binary digits (0 or 1), and the last column contains the result of an operation on the first five columns. The last row contains the result of an operation on the rows above it. The numbers are 1 0 1 1 1 | 1, 0 0 0 1 1 | 1, 1 0 0 0 1 | 1, 0 1 1 1 1 | 1, 0 1 0 1 | 0.

Image /page/37/Picture/4 description: The image shows the logo of TU Delft, a technical university in the Netherlands. The logo consists of the letters "TU Delft" in a stylized font. The background is a light blue color.

{38}------------------------------------------------

Answer Odd parity: Q $\mathbf{1}$ $0₁$ $\vert 0$ $$ ◆

Image /page/38/Picture/2 description: The image shows a light blue button with the text "Back to Question" on it. The text is in a slightly darker shade of blue and is accompanied by a left-pointing arrow.

Image /page/38/Picture/3 description: The image shows the logo of TU Delft, a technical university in the Netherlands. The logo consists of the letters "TU Delft" in a stylized font, with the "TU" stacked on top of "Delft". The text is in a light blue color and is set against a solid blue background.

{39}------------------------------------------------

Question Compute an (11,7) Hamming Code for $1010110_{(2)}$ using even parity.

Answer

Step 1. The first number in the code description is the total number of bits in the encoded bit stream. So, we will have 11 bits:

Image /page/39/Figure/4 description: The image shows a row of ten white squares with black borders, set against a light green background. The squares are evenly spaced and aligned horizontally.

Image /page/39/Picture/5 description: The image shows the logo for TU Delft. The logo consists of the letters "TU Delft" in a light blue color against a blue background. Above the letters is a stylized image of a tree or plant, also in light blue.

{40}------------------------------------------------

Image /page/40/Figure/1 description: The image shows a question asking to compute an (11,7) Hamming Code for 1010110(2) using even parity.

Answer

Step 2. The bits that are powers of $2$ (1, 2, 4, etc.) are check bits. Let's spare them. (Remember: Position 1 is the leftmost bit.)

Image /page/40/Figure/4 description: The image shows a horizontal bar with a light green background. The bar is divided into 10 equal segments. The first two segments are red, followed by three white segments, then one red segment, and finally four white segments.

Image /page/40/Picture/5 description: The image shows the logo for TU Delft. The logo consists of the letters 'TU Delft' in a sans-serif font. Above the letters is a stylized image of a person with outstretched arms.

{41}------------------------------------------------

Image /page/41/Figure/1 description: The image shows a question asking to compute an (11,7) Hamming Code for 1010110(2) using even parity.

Image /page/41/Figure/2 description: The image shows a diagram with the text "Answer Step 3. Remaining bits should contain the message. Let's write them." Below the text is a sequence of boxes, some red and some white, containing the binary digits 1 and 0. The sequence is: red, red, 1, 0, 1, 0, red, 1, 1, 0.

{42}------------------------------------------------

Question Compute an (11,7) Hamming Code for $1010110_{(2)}$ using even parity.

Answer

Step 4.1. Now, we can calculate check bits. The sum of the values at positions 1, 3, 5, 7, 9 and 11 should be even. If we call the first bit a, then $a+1+0+0+1+0$ should be even. Thus, a should be $\overline{0}$ .

Image /page/42/Figure/4 description: The image shows a sequence of boxes. The first box contains the letter 'a' and is colored red. The second box is also red and contains the number '1'. The third box is white and contains the number '0'. The fourth box is red and contains the number '1'. The fifth box is white and contains the number '0'. The sixth box is red and contains the number '1'. The seventh box is white and contains the number '1'. The eighth box is white and contains the number '0'. There are arrows pointing up below each box.

{43}------------------------------------------------

Answer

Step 4.2. Similarly, the sum of the values at positions 2, 3, 6, 7, 10, 11 should be even. If we call the second bit b, then $b+1+1+0+1+0$ should be even. Thus, b should be 1.

Image /page/43/Figure/4 description: The image shows a sequence of boxes, some red and some white, containing the binary number 0b1010110. Arrows point to the boxes containing the digits 1, 0, 1, 1, and 0.

Image /page/43/Picture/5 description: The image shows the logo for TU Delft. The logo consists of the letters 'TU Delft' in a sans-serif font. Above the letters is a stylized image of a person with outstretched arms.

{44}------------------------------------------------

Answer

Step 4.3. The sum of the values at positions 4, 5, 6 and 7 should be even. If we call the fourth bit c, then $c + 0 + 1 + 0$ should be even. Thus, $c = 1$ .

$$$$

{45}------------------------------------------------

Answer

Step 4.4. Finally, the sum of the values at positions 8, 9, 10 and 11 should be even. If we call the eighth bit d, then $d + 1 + 1 + 0$ should be even. Thus, $d = 0$ .

$$\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|} \hline 0 & 1 & 1 & 0 & 1 & 0 & d & 1 & 1 & 0 \\ \hline & & & & & & \uparrow & & \uparrow & \uparrow & \\ \end{array}$$

{46}------------------------------------------------

Question

Compute an $(11,7)$ Hamming Code for $1010110_{(2)}$ using even parity.

Image /page/46/Picture/4 description: The image shows a button that says "Back to Question".

{47}------------------------------------------------

Answer

We compute the parities of the 4 parity bits and check if they are hho haahni

Image /page/47/Figure/3 description: The image shows a series of binary numbers and their parity checks. The first row contains the binary number 000110111010001. The following rows show the same binary number, but with some of the digits highlighted in black. Each row is labeled with a number (1, 2, 4, 8), and the number of odd digits in each row is indicated, along with a checkmark or cross to indicate whether the parity check is correct. The first two rows have an odd number of odd digits and are marked with a checkmark, while the last two rows have an even number of odd digits and are marked with a cross.

There were errors in the checks associated with checkbits 4 and 8. So, if there was at most one bitflip, bit $4+8=12$ was flipped. The original message was:

Image /page/47/Figure/5 description: The image shows a sequence of binary digits, specifically '0|0|0|1|1|0|1|1|1|0|1|1|0|0|1'. Each digit is separated by a vertical bar, and the eleventh digit, '1', is highlighted in green.

{48}------------------------------------------------

Computer Networks CSE14B

cn-cs-ewi@tudelft nl

Delft University of Technology, The Netherlands

{49}------------------------------------------------

Go Back N and Selective Repeat

Sliding Window Protocol Throughput

{50}------------------------------------------------

EXERCISES

{51}------------------------------------------------

Question

Erie sends 200-byte frames to Piyush who immediately acknowledges them using 4-byte acknowledgments. The latency of their communication channel is 250ms and the bandwidth is 500 bytes per second in both directions. How long does it take until Erie receives the acknowledgment from

the moment she starts sending a frame (without any errors)? If we ignore the transmission delay of the acknowledgment, how inaccurate is the computation, i.e., how much does the result differ from the result computed before?

Suggested time for this exercise: 8 minute(s)

Image /page/51/Picture/5 description: The image shows a blue button with the word "Solution" written on it.

{52}------------------------------------------------

Question

Aniket and Thorsten use Selective Repeat with a sliding window of $k = 4$ and a timeout of 500ms. Their channel has a round trip time of 350ms and a bandwidth of 500 bytes per second. Frames are always of size 150 bytes and acknowledgments are short so that their transmission delay can be ignored.

Aniket sends frames constantly and one frame is lost but the subsequent frame arrives, as does the corresponding negative acknowledgment. Timers are started immediately once frames have heen transmitted

Does the negative acknowledge arrive at Aniket before the timeout for retransmission of the lost frame?

Suggested time for this exercise: 5 minute(s)

Solution

{53}------------------------------------------------

Question

Bert sends Ernie 20 100-byte frames using a duplex channel. Acknowledgments are very short, so their transmission delay can be ignored, and a sliding window protocol with $k=5$ is used. The latency is 50ms in both directions and the channel has a bandwidth of 1000 bytes per second in both directions. There is an error when transmitting frame 5 the first time but all other frames and acknowledgements are transmitted correctly. Assume that when Bert needs to retransmit a frame, he first finishes the transmission of the frame he is currently transmitting if any. He then retransmits before sending other frames in the queue. Which frames are retransmitted when using Go Back N and Selective Repeat, respectively, with a timeout of a) 600ms, b) $210ms$ , and c) $150ms$ ?

Suggested time for this exercise: $20$ minute(s)

{54}------------------------------------------------

Question

Theoden sends 200-byte frames to Faramir using a duplex channel that can handle up 400 bytes per second. The latency of the channel is 230ms from Theoden to Faramir and 270ms from Earamir to Theoden They use a sliding window protocol with $k = 4$ . For the first k frames that Theoden sends, does the acknowledgment for the first frame arrive before Theoden is done transmitting the k-th frame? Assume that there are no errors and Theoden is constantly sending. The transmission delay of the acknowledgment as well as the processing time can be ignored.

Suggested time for this exercise: 5 minute(s)

Solution

{55}------------------------------------------------

Consider an error-free 64-kbps (kilo-bits per second) satellite channel used to send 512-byte data frames in one direction, with very short acknowledgments coming back the other way.

We know that the round trip time from earth to satellite is 540 ms.

Find the throughput for window sizes 1, 7, 15, and 127.

(Assume the processing time at the receiver side and the transmission delay of the acknowledgment can be ignored.)

Suggested time for this exercise: 25 minute(s)

Image /page/55/Picture/9 description: The image contains the word "Solution" in a light blue color against a slightly darker blue background. The word is slightly blurred, giving it a soft appearance.

{56}------------------------------------------------

By completing this tutorial, you mastered:

• analyzing the difference between different sliding window protocols
• calculating throughput in sliding window protocols

{57}------------------------------------------------

Hints

{58}------------------------------------------------

Hint: Selective Repeat/Go Back N

Hint

A negative acknowledgement in Selective Repeat does not count as an acknowledgement of the subsequent frame, i.e., a negative acknowledgement for frame 5 does not acknowledge frame 6.

• Back to Question

{59}------------------------------------------------

Hint

If the acknowledgment for a frame arrives before the following $k-1$ frames are transmitted, the sender does not have to stop sending. Otherwise, they have to stop until the acknowledgment arrives.

The computation differs depending on which of the two cases you are in. So, first establish which case it is and then compute accordingly.

Hint

If the sender has to stop, the throughput is the data sent divided by the time until the acknowledgment arrives.

• Back to Question

{60}------------------------------------------------

Solutions

{61}------------------------------------------------

Answer

The transmission delay for a 200-byte frame is $200/500 = 0.4$ seconds or 400ms. The transmission delay of a 4-byte acknowledgment is $4/500 = 1/125 = 0.008$ seconds or 8ms. The round trip time is 500ms.

The total time until the acknowledgment is received consists of the two transmission delays plus the round trip time, so

$400ms + 500ms + 8ms = 908ms$ .

If we ignore the transmission time of the acknowledgment, we only have 900ms and hence the results differ by 8ms.

• Back to Question

{62}------------------------------------------------

Answer

$No$

The timer is started after Aniket has transmitted the frame that is lost. After the timer is started, Aniket transmits the next frame. The negative acknowledgment arrives after the transmission delay for the next frame and the round trip time. We have to check whether this time is less than the timeout of 500ms. The time to transmit one frame is $150/500 = 3/10$ seconds or 300ms. So the time until the negative acknowledgment arrives is $300ms + 350ms = 650ms > 500ms$ . Hence, the negative acknowledgment does not arrive before the timeout and the timeout is what triggers the retransmission of the lost frame.

A Later to Question

{63}------------------------------------------------

Answer

The maximal throughput is 1000 bytes per second, so it takes 0.1s or 100ms to transmit one frame.

For a successful transmission, it takes another 100ms to receive an acknowledgement (2 times latency of 50ms).

For Selective Repeat, a negative acknowledgement hence arrives 200ms after the timer for frame 5 started, which is the time to send frame 6 and get an acknowledgement back. (Solution continues on next slides)

{64}------------------------------------------------

Answer

$\mathbf{\hat{r}}$ U $\mathsf{D}$ elft

All scenarios share the following time schedule:

• $\triangleright$ Bert starts sending frame 5 at time t
• ightharpoonup at time $t + 100$ ms. Bert is done sending frame 5 and starts the timer for frame 5
• ightharpoonup at time $t + 100$ ms, Bert also starts sending frame 6
• ightharpoonup at time $t + 200$ ms, Bert is done sending frame 6 and starts the timer for frame 6

{65}------------------------------------------------

Answer

a) 600ms: For Selective Repeat, a negative acknowledgement arrives 200ms after the timer starts and triggers a retransmission of frame 5, during this time frame 7 has also been sent. Once frame 5 arrives at Ernie, he acknowledges 5, 6, and 7. It takes another 200ms from the moment Bert started retransmitting frame 5 until the acknowledgement arrives at Bert, so a total of 400ms after the timer for frame 5 initially started. No timeouts occurred and no frame but 5 is retransmitted.

For Go Back N, Bert sends frames until either k frames have not been acknowledged or a timeout has been triggered. It takes 500ms to send 5 frames, which is less than the timeout of 600ms. Thus, Bert sends frames 5,6,7,8, and 9 before stopping and retransmitting all of these frames.

{66}------------------------------------------------

Answer

b) 210ms: For Selective Repeat, a negative acknowledgement arrives 200ms after the timer starts and triggers a retransmission of frame 5, during this time frame 7 has also been sent. Once frame 5 arrives at Ernie, he acknowledges 5, 6, and 7. It takes another 200ms from the moment Bert started retransmitting frame 5 until the acknowledgement arrives at Bert, so a total of 400ms after the timer for frame 5 initially started and 300ms after the timeout for frame 6 started, which is more than 210ms. So, frame 5 and 6 are retransmitted.

For Go Back N. Bert sends frames until either k frames have not been acknowledged or a timeout has been triggered. Bert sends frame 6, 7, and 8, each taking 100ms for transmission. Afterwards, the timeout is triggered. Bert then retransmits 5, 6, 7, and 8.

Image /page/66/Picture/4 description: The image shows the logo for TU Delft. The logo consists of the text "TU Delft" in a sans-serif font, with the "TU" part being slightly larger than the "Delft" part. Above the text is a stylized image of a bird or a wing-like shape. The entire logo is set against a light blue background.

{67}------------------------------------------------

Solution: Selective Repeat/Go Back N

Answer

c) 150ms: For Selective Repeat, a negative acknowledgement arrives 200ms after the timer starts, however the timeout has already triggered a retransmission of frame 5. Note that at 150ms after the time start, Bert is still transmitting frame 7, so he does not start retransmission of 5 until 200ms after the timer starts. The cumulative acknowledgement for 5, 6, and 7 only arrives 200ms after Bert starts retransmitting frame 5, which also starts the timer for frame 7. Hence, the timeouts for frame 6 happens before the ack The timeout for frame 7 is also before the acknowledgement has arrived. For Go Back N, Bert retransmits 5 once the timeout is triggered. Until then, frame 6 and 7 have been transmitted, which also require retransmission, so 5, 6, and 7 are retransmitted

• Back to Question

{68}------------------------------------------------

Solution: Sliding Window Frames

Answer

Yes:

It takes $200/400 = 0.5$ seconds or 500ms to send one frame. So it takes Theoden $4.500ms = 2000ms$ to send $k = 4$ frames In contrast, the time until the first acknowledgment arrives is given by the time to send one frame plus the round trip time, so $500$ Thus, the acknowledgment arrives before Theoden is done sending frames.

• Back to Question

{69}------------------------------------------------

Answer

We can be in the scenario when the sender can send constantly without stopping, as in the following example:

Image /page/69/Figure/3 description: The image shows a diagram of a communication protocol between two entities, labeled A and B. A sends frames 0 through 6 to B, and B sends acknowledgements (Ack) 0, 1, and 2 back to A. The parameter k is set to 6.

{70}------------------------------------------------

Answer

...or we might be in the scenario when there is unused bandwidth, see the following example:

Image /page/70/Figure/3 description: The image shows a diagram of a communication protocol between two entities, labeled A and B. The diagram illustrates the flow of frames and acknowledgements (ACKs) between A and B. A sends frames 0, 1, 2, and 3 to B. B sends an acknowledgement (ACK 0) back to A. The diagram also includes the label 'k=4' and two red boxes labeled 'Unused!' with arrows pointing up and down.

{71}------------------------------------------------

Answer

In the first case, the throughput equals the bandwidth.

Otherwise, the sender repeatedly sends $k$ frames and then waits for the ack of the first. We can hence determine the average throughput as $(k \text{ frames})/(time \text{ until }ack \text{ arrives from moment})$ sender starts sending first frame).

We find out in which of the two scenarios we are by checking whether $k$ frames have been transmitted before the first ack arrives. If that is the case, we are in the second scenario, otherwise in the first scenario.

The time until the first ack is the transmission delay of a frame plus the round trip time, i.e., the overall delay of a frame plus the latency from the receiver to the sender for the ack.

{72}------------------------------------------------