00000101 01000111 11100011 11100000 01111110
01111110
01000111
11100011
11100000
11100000
11100000
01111110
01111110
flag
A
B
Esc (byte stuffed)
Esc
Esc (byte stuffed)
flag
flag
01111110
01000111
110100011
111000000
011111010
01111110
flag
A
B
Esc
flag
flag
Solution: No. In a perfect situation when the data stream is continuous and there's no error, having only the starting flag byte is OK. However, if there is a long interval between the first frame and the 2nd frame, the receiver wouldn't be able to determine if the first frame has finished transmitting or not. Having both flags is also more stable.
Although the first parity bit can detect even-numbered bits and the second parity bit can detect odd-numbered bits, this coding scheme can only detect ALL single error for sure, that is, d=1. Therefore, the Hamming distance is d+1=2. Although it can sometimes detect 2 errors (one even-numbered, one odd-numbered), it cannot detect all the 2 errors.
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. That is, when one message bit is flipped, and the corresponding row and column parity bits are flipped as well.
m+r+1<=2^r. If m=8, then r has to be at least 4.
the numbers used below indicate the bit position
These relationships tell us that:
Therefore,
C1 = M1 + M2 + M4 + M5 + M7
Using even parity,
So the actuall data stream sent out is as follows:
bit position 1 2 3 4 5 6 7 8 9 10 11 12
check and msg bits C1 C2 M1 C3 M2 M3 M4 C4 M5 M6 M7 M8
? ? 1 ? 1 0 1 ? 0 0 1 1
3 = 1+2
5 = 1+4
6=2+4
7=1+2+4
9=1+8
10=2+8
11=1+2+8
12=4+8
bits 3, 5, 7, 9, and 11 determine bit 1, which is check bit C1
bits 3, 6, 7, 10, and 11 determine bit 2, which is check bit C2
bits 5, 6, 7, and 12 determine bit 4, which is check bit C3, and
bits 9, 10, 11, and 12 determine bit 8, which is check bit C4
C2 = M1 + M3 + M4 + M6 + M7
C3 = M2+M3+M4+M8
C4 = M5+M6+M7+M8
C1 = 1+1+1+0+1 = 0
C2 = 1+0+1+0+1 = 1
C3 = 1+0+1+1=1
C4 = 0+0+1+1=0
check and msg bits C1 C2 M1 C3 M2 M3 M4 C4 M5 M6 M7 M8
0 1 1 1 1 0 1 0 0 0 1 1
the 3rd bit happens to be M1
therefore, the first and second check bits failed the even parity check. The bit position of the first and 2nd check bits are 1 and 2, and 1+2=3. Hence, bit 3 has error, and should be 1.
C1 + M1 + M2 + M4 + M5 + M7 = 1
C2 + M1 + M3 + M4 + M6 + M7 = 1
C3 + M2+M3+M4+M8 = 0
C4 + M5+M6+M7+M8 = 0
the 3rd and 7th bits are M1 and M4
Therefore, the third check bit failed the even parity check. The bit position of the 3rd check bit is 4. Therefore, bit 4 has error which is a wrong judgement.
C1 + M1 + M2 + M4 + M5 + M7 = 0
C2 + M1 + M3 + M4 + M6 + M7 = 0
C3 + M2+M3+M4+M8 = 1
C4 + M5+M6+M7+M8 = 0
Keep in mind of a few rules in deriving the checksum.
(from David Windsor)
(from David Windsor)
(from David Windsor)
Difference:
HDLC is a bit-oriented data link protocol. It uses reliable data transfer protocols like SR.
These differences indicate that the receiver side of GBN only acknowledge the most recently received frame. It will discard any arriving frames that's out of order, since it doesn't provide receiver buffer. On the other hand, SR buffers out-of-order frames until the correct one comes.
PPP is a byte-oriented data link protocol. It uses unreliable data transfer protocol. PPP is the data link protocol used in the Internet. The reliable service is handled at the transport layer.
l = t_tran = 64*8/1.544M = 0.331ms
r = t_prop = 3000*6 = 18ms
efficiency = l / (l + 2r) = 0.331/(0.331+2*18) = 0.9127%
In order to achieve 100% efficiency, the sender has to be able to transmit all the time. In another word, there shouldn't be any idle time at the sender. That is, during the (l+2r) end-to-end delay, the sender should keep sending frames. Hence, the number of frames (or the number of windows) that the sender should maintain is
(l + 2r)/(l) = 109.76
Therefore, there should be 110 windows or sequence number bit of 7
Assume that the acknowledgement for pkt3 arrives before pkt2 times out, then the sender would know that the receiver has correctly received pkt2, even though the acknowledgement got lost. This is because GBN uses cumulative acknowledgement which only acknowledge the most recent received packet. Therefore, the sender is able to send out pkt 6 and pkt 7.
In scenario (a), the receiver thinks the pkt0 it receives is a new packet while it really should have been the old pkt0. SR has no way to distinguish between these two packets under this circumstance.