1.

An upper-layer packet is split into 10 frames, each of which has an 80% chance of ar-
riving undamaged. If no error control is done by the data link protocol, how many
times must the message be sent on average to get the entire thing through?

Therefore, the expected number of times the message must be sent to get the entire thing through is
given by: 1/(1 - 0.893) = 9.23 Therefore, on average, the message must be sent 9.23 times to get the
entire thing through.

80/100 = 0.8^10 = 0.107

2. The following character encoding is used in a data link protocol:

A: 01000111
B: 11100011
FLAG: 01111110
ESC: 11100000
Show the bit sequence transmitted (in binary) for the four-character frame A B ESC
FLAG when each of the following framing methods is used:
(a) Byte count.
(b) Flag bytes with byte stuffing.
(c) Starting and ending flag bytes with bit stuffing.

Given Character Encodings

 A: 01000111
 B: 11100011
 FLAG: 01111110
 ESC: 11100000

Framing Methods
(a) Byte Count
In the byte count method, the first byte specifies the number of bytes in the frame. Since A, B, ESC,
and FLAG are each 1 byte, we have a total of 4 bytes. So, the transmitted bit sequence is as follows:

1. Byte count (4 bytes): 00000100 (4 in binary)

2. Byte for A: 01000111
3. Byte for B: 11100011
4. Byte for ESC: 11100000
5. Byte for FLAG: 01111110

The resulting bit sequence is:

00000100 01000111 11100011 11100000 01111110

In this case, the frame contains four characters: A, B, ESC, and FLAG. Each character is represented
by one byte (8 bits), so we need a total of 4 bytes to represent these four characters.
To represent the number 4 in an 8-bit binary format:
 The binary representation of the number 4 is 00000100.
This byte (00000100) is added at the beginning of the frame to indicate that the total frame length
is 4 bytes. The transmitted bit sequence for the frame using the byte count method is therefore:
01000111 11100011 11100000 0111111000000100 01000111 11100011 11100000 01111110
(b) Flag Bytes with Byte Stuffing
In this method, frames are delimited by FLAG bytes, and any occurrence of FLAG or ESC within
the frame data must be "stuffed" by preceding it with an ESC byte.

1. Start with a FLAG byte: 01111110

2. Byte for A: 01000111
3. Byte for B: 11100011
4. Byte for ESC: Since ESC appears in the data, we insert an additional ESC byte to indicate
byte stuffing, resulting in 11100000 11100000.
5. Byte for FLAG: Since FLAG appears in the data, we also byte-stuff it by adding an ESC
byte, resulting in 11100000 01111110.
6. End with a FLAG byte: 01111110

The resulting bit sequence is:

01111110 01000111 11100011 11100000 11100000 11100000 01111110 01111110
(c) Starting and Ending Flag Bytes with Bit Stuffing
In this method, the frame starts and ends with FLAG bytes. Inside the frame, bit stuffing is used
whenever there are five consecutive 1s, an extra 0 is added after the five 1s.

1. Start with a FLAG byte: 01111110

2. Byte for A: 01000111 (no bit stuffing needed here)
3. Byte for B: 11100011 (no bit stuffing needed here)
4. Byte for ESC: 11100000 (no bit stuffing needed here)
5. Byte for FLAG: Since FLAG in binary is 01111110, it has five consecutive 1s. To avoid
interpreting it as a frame boundary, we add a 0 after the fifth 1, making it 011111010.
6. End with a FLAG byte: 01111110

The resulting bit sequence is:

01111110 01000111 11100011 11100000 011111010 01111110
3. The following data fragment occurs in the middle of a data stream for which the byte-
stuffing algorithm described in the text is used: A B ESC C ESC FLAG FLAG D.
What is the output after stuffing?

Let’s go through each byte and apply the byte-stuffing rules:

1. A: No need to stuff; output A.
2. B: No need to stuff; output B.
3. ESC: Since ESC is a special character, we add an additional ESC to indicate it is part of the
data. Output ESC ESC.
4. C: No need to stuff; output C.
5. ESC: Another ESC appears, so we add an extra ESC. Output ESC ESC.
 6. FLAG: FLAG is also a special character, so we add an ESC before it. Output ESC FLAG.
7. FLAG: Another FLAG appears, so we add an ESC before it. Output ESC FLAG.
8. D: No need to stuff; output D.

Final Stuffed Output

After applying byte stuffing, the output sequence is:
A B ESC ESC C ESC ESC ESC FLAG ESC FLAG D
This is the data fragment after byte-stuffing has been applied.
3.1. Given the output after byte-stuffing: FLAG A B ESC ESC C ESC ESC ESC FLAG
ESC FLAG D FLAG. What is the original data?
ANS:
A B ESC C ESC FLAG FLAG D

4. What is the maximum overhead in byte-stuffing algorithm?

Maximum overhead in a byte - stuffing algorithm is 2n, where n is the number of bytes in the
payload.

5. One of your classmates, Scrooge, has pointed out that it is wasteful to end each frame
with a flag byte and then begin the next one with a second flag byte. One flag byte
could do the job as well, and a byte saved is a byte earned. Do you agree?

No, I don't agree. Using separate FLAG bytes at the end and beginning of frames helps maintain
clear frame boundaries.

6. A bit string, 0111101111101111110, needs to be transmitted at the data link layer.

What is the string actually transmitted after bit stuffing?

In bit-stuffing, whenever there are five consecutive 1s in the data, an extra 0 is inserted
immediately afterward to prevent confusion with a FLAG pattern (which often uses six 1s, like
01111110).
The output is 011110111110011111010

7. Can you think of any circumstances under which an open-loop protocol (e.g., a Ham-
ming code) might be preferable to the feedback-type protocols discussed throughout
this chapter?

An open-loop protocol might be preferable when minimizing delay, reducing complexity, or

conserving resources is more important than ensuring perfect error recovery.

8. To provide more reliability than a single parity bit can give, an error-detecting coding
scheme uses one parity bit for checking all the odd-numbered bits and a second parity
bit for all the even-numbered bits. What is the Hamming distance of this code?

The proposed code uses two parity bits: one for the odd-numbered bits and one for the even-
numbered bits.
 If a single bit (either odd or even) changes, only one parity bit will be affected.
 This means the code can only detect errors but cannot correct them.
  The minimum Hamming distance of this code is 2.
 To correct errors, the code needs a minimum Hamming distance of 3.

9. Sixteen-bit messages are transmitted using a Hamming code. How many check bits
are needed to ensure that the receiver can detect and correct single-bit errors? Show
the bit pattern transmitted for the message 1101001100110101. Assume that even par-
ity is used in the Hamming code.

10. A 12-bit Hamming code whose hexadecimal value is 0xE4F arrives at a receiver.
What was the original value in hexadecimal? Assume that not more than 1 bit is in
error.

11. One way of detecting errors is to transmit data as a block of n rows of k bits per row
and add parity bits to each row and each column. The bitin the lower-right corner is a
parity bit that checks its row and its column. Will this scheme detect all single errors?
Double errors? Triple errors? Show that this scheme cannot detect some four-bit er-
rors.

Yes, it will detect all single errors, double errors, but NOT triple errors, as there is one case that
three errors occur but none of the parity bits can detect. .

12. Suppose that data are transmitted in blocks of sizes 1000 bits. What is the maximum
error rate under which error detection and retransmission mechanism (1 parity bit per
block) is better than using Hamming code? Assume that bit errors are independent of
one another and no bit error occurs during retransmission.

The error detection and retransmission mechanism with 1 parity bit per block is better than using
Hamming code when the error rate is less than about 1/1000. This is because for low error rates,
retransmitting the entire block after detecting an error is more efficient than using Hamming code's
error correction.

13. A block of bits with n rows and k columns uses horizontal and vertical parity bits for
error detection. Suppose that exactly 4 bits are inverted due to transmission errors.
Derive an expression for the probability that the error will be undetected.

The error will typically be detected unless the flipped bits follow a specific pattern that leaves the
parities intact.

14. Using the convolutional coder of Fig. 3-7, what is the output sequence when the input
sequence is 10101010 (left to right) and the internal state is initially all zero?
15. Suppose that a message 1001 1100 1010 0011 is transmitted using Internet Checksum
(4-bit word). What is the value of the checksum?
16. What is the remainder obtained by dividing x 7 + x 5 + 1 by the generator polynomial
x 3 + 1?

17. A bit stream 10011101 is transmitted using the standard CRC method described in the
text. The generator polynomial is x 3 + 1. Show the actual bit string transmitted. Sup-
pose that the third bit from the left is inverted during transmission. Show that this
error is detected at the receiver’s end. Give an example of bit errors in the bit string
transmitted that will not be detected by the receiver.
19. In the discussion of ARQ protocol in Section 3.3.3, a scenario was outlined that re-
sulted in the receiver accepting two copies of the same frame due to a loss of acknowl-
edgement frame. Is it possible that a receiver may accept multiple copies of the same
frame when none of the frames (message or acknowledgement) are lost?

Yes, a receiver can accept multiple copies of the same frame even if no frames are lost. This can
happen if the sender times out and retransmits a frame, assuming the acknowledgment was lost. The
receiver, not knowing that it already received the frame, accepts the retransmitted copy, leading to
duplicate frames being accepted.

20. A channel has a bit rate of 4 kbps and a propagation delay of 20 msec. For what range
of frame sizes does stop-and-wait give an efficiency of at least 50%?
21. In protocol 3, is it possible for the sender to start the timer when it is already running?
If so, how might this occur? If not, why is it impossible?

It is possible for the sender to start the timer while it is already running,
For example:
1. The sender starts a timer when it sends Frame 1.
 2. If the acknowledgment for Frame 1 is not received in time (due to network delay or some
error), the timer expires.
3. The sender retransmits Frame 1, and in some systems, it may start the timer again, even
though the timer expired previously.

22. A 3000-km-long T1 trunk is used to transmit 64-byte frames using protocol 5. If the
propagation speed is 6 μsec/km, how many bits should the sequence numbers be?

23. Imagine a sliding window protocol using so many bits for sequence numbers that
wraparound never occurs. What relations must hold among the four window edges
and the window size, which is constant and the same for both the sender and the re-
ceiver?

24. If the procedure between in protocol 5 checked for the condition a ≤ b ≤ c instead of
the condition a ≤ b < c, would that have any effect on the protocol’s correctness or ef-
ficiency? Explain your answer.
27. The distance from earth to a distant planet is approximately 9 × 1010 m. What is the
channel utilization if a stop-and-wait protocol is used for frame transmission on a 64
Mbps point-to-point link? Assume that the frame size is 32 KB and the speed of light
is 3 × 108 m/s.
32. Frames of 1000 bits are sent over a 1-Mbps channel using a geostationary satellite
whose propagation time from the earth is 270 msec. Acknowledgements are always
piggybacked onto data frames. The headers are very short. Three-bit sequence num-
bers are used. What is the maximum achievable channel utilization for
(a) Stop-and-wait?
(b) Protocol 5?

34. Consider an error-free 64-kbps satellite channel used to send 512-byte data frames in
one direction, with very short acknowledgements coming back the other way. What is
the maximum throughput for window sizes of 1, 7, 15, and 127? The earth-satellite
propagation time is 270 msec.
35. A 100-km-long cable runs at the T1 data rate. The propagation speed in the cable is
2/3 the speed of light in vacuum. How many bits fit in the cable?
37. What is the minimum overhead to send an IP packet using PPP? Count only the over-
head introduced by PPP itself, not the IP header overhead. What is the maximum
overhead?

The minimum size of protocol field is 1 byte, and checksum field is 2 bytes. The ending and starting
flag byte is 2 bytes in total. Finally, the minimum overhead for PPP is 5 bytes.

36. Give at least one reason why PPP uses byte stuffing instead of bit stuffing to prevent
accidental flag bytes within the payload from causing confusion.

Final answer: PPP uses byte stuffing instead of bit stuffing for reasons such as reducing overhead,
avoiding misinterpretation of data, and improving data transmission speed.

31. In protocol 6, MAX SEQ = 2n − 1. While this condition is obviously desirable to

make efficient use of header bits, we have not demonstrated that it is essential. Does
the protocol work correctly for MAX SEQ = 4, for example?

Yes, Protocol 6 can work correctly with MAX SEQ=4, but only under specific conditions.

The sequence number space must be large enough to prevent ambiguities between new and old
frames.

With MAX SEQ=4, the sender's window size must not exceed 4/2=2 to ensure that
acknowledgments and sequence numbers are uniquely matched.

30. Consider the operation of protocol 6 over a 1-Mbps perfect (i.e., error-free) line. The
maximum frame size is 1000 bits. New packets are generated 1 second apart. The
timeout interval is 10 msec. If the special acknowledgement timer were eliminated,
unnecessary timeouts would occur. How many times would the average message be
transmitted?

Frame approximately 10s/10ms=100 times

Average number of transmissions per message is 1+100=101.

29. In protocol 6, the code for frame arrival has a section used for NAKs. This section is
invoked if the incoming frame is a NAK and another condition is met. Give a scenario
where the presence of this other condition is essential.

The additional condition is essential to prevent redundant retransmissions. For example, if frame 1
is lost and the receiver sends a NAK, the sender retransmits frame 1. If another NAK for frame 1
arrives before the acknowledgment, the sender would retransmit unnecessarily without the
condition to check if the frame was already resent.

26. Suppose that the three-statement while loop near the end of protocol 6 was removed
from the code. Would this affect the correctness of the protocol or just the per-
formance? Explain your answer.

Removing the three-statement while loop near the end of Protocol 6 would affect the performance
but not the correctness of the protocol. The loop is responsible for processing multiple buffered
acknowledgments efficiently in a single go. Without it, the protocol would still function correctly
but would handle acknowledgments one at a time, resulting in increased delays and reduced
throughput.

25. In protocol 6, when a data frame arrives, a check is made to see if the sequence num-
ber differs from the one expected and no nak is true. If both conditions hold, a NAK
is sent. Otherwise, the auxiliary timer is started. Suppose that the else clause were
omitted. Would this change affect the protocol’s correctness?

Omitting the else clause (which starts the auxiliary timer) would not affect the correctness of
Protocol 6 but would impact its performance. The auxiliary timer ensures timely transmission of
acknowledgments when piggybacking is delayed. Without it, acknowledgments might be delayed
until new data is ready to send, increasing latency and potentially causing unnecessary
retransmissions due to sender timeouts.