Homework 3 Solution - Data Link Layer

Problem 1: (15 pts) Framing

• a) (10) 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 are used:
  • Character count

    00000101 01000111 11100011 11100000 01111110

  • Flag bytes with byte stuffing

    01111110	01000111	11100011	11100000	11100000	11100000	01111110	01111110
    flag	A	B	Esc (byte stuffed)	Esc	Esc (byte stuffed)	flag	flag

  • Starting and ending flag bytes, with bit stuffing

    01111110	01000111	110100011	111000000	011111010	01111110
    flag	A	B	Esc	flag	flag

• b) (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?

  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.

Problem 2: (45 pts) Error detection and correction

• a) (5) 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?

  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.

• b) (5) One way of detecting errors is to transmit data as a block of n rows of k bits per row and adding parity bits to each row and each column. 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?

  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.

• c) (35) Given an 8-bit message 11010011, answer the following questions:
  • c1) (4) If the message is transmitted using a Hamming code, how many check bits are needed to ensure the receiver can correct single bit error?

    m+r+1<=2^r. If m=8, then r has to be at least 4.

  • c2) (8) Assuming that even parity is used in the Hamming code, show the bit pattern transmitted for this message.

    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

    the numbers used below indicate the bit position
    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

    These relationships tell us that:
    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

    Therefore, C1 = M1 + M2 + M4 + M5 + M7
    C2 = M1 + M3 + M4 + M6 + M7
    C3 = M2+M3+M4+M8
    C4 = M5+M6+M7+M8

    Using even parity,
    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

    So the actuall data stream sent out is as follows:

    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

  • c3) (6) Suppose that the third bit from the left is inverted due to transmission errors. Show how Hamming code detects and corrects it.

    the 3rd bit happens to be M1
    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
    

    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.

  • c4) (4) Suppose that both bit 3 and bit 7 are inverted. Show how Hamming code cannot correct these errors.

    the 3rd and 7th bits are M1 and M4
    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
    

    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.

  • c5) (5) Suppose this message is transmitted using standard CRC method. The generator polynomial is x^3+1. (Notice that x^3+1=(x+1)(x^2-x+1) where (x+1) is a factor and that 1 is a component of the polynomial. Think about what this indicates.) Suppose 3 check bits are added. Show the actual bit stream transmitted. (Since all the following questions are based on the answer to this question. I'm going to give you the correct answer here. But you have to show me the details. Answer: 1101001100001.

    Keep in mind of a few rules in deriving the checksum.

    • If you want to detect all the odd number of errors, x+1 has to be a factor of the generator G(x)
    • If you want to detect burst errors of length less than or equal to r, the degree of your generator polynomial must be r
    • If the degree of the generator is r, then you pad r zeros at the end of the message, and append the remainder to the zeros. Therefore, the number of bits in the checksum should be r
    • If r is less than (i-j) where i and j are the locations of the two isolated single-bit error, then it might not be detected.
    • The checksum is calculated by modulo-2 division.
    (from David Windsor)

  • c6) (3) Suppose in the transmitted message, bit 2, 3, and 10 are inverted (counting from the left). Show how receiver detects errors.

    (from David Windsor)

  • c7) (3) Suppose in the transmitted message, bit 2 and 3 are inverted. Show if the receiver can detect errors.

    (from David Windsor)

  • c8) (4) What conclusions can you draw?
    • If you want to detect all the odd number of errors, x+1 has to be a factor of the generator G(x). But this setup cannot detect all even number of errors
    • If you want to detect burst errors of length less than or equal to r, the degree of your generator polynomial must be r
    • If r is less than (i-j) where i and j are the locations of the two isolated single-bit error, then it might not be detected.

Problem 3: (40+10) Reliable data transfer at the data link layer

• a) (15) Go-Back-N (GBN) and Selective Repeat (SR) are two reliable transfer protocols. Comment on the major differences between GBN and SR (List at least two). What kind of service does HDLC or PPP provide?

  Difference:

  • GBN only has a sender buffer. SR has both the sender buffer and the receiver buffer
  • GBN uses cumulative acknowledgement, while SR uses selective acknowledgement.
  • When retransmitting, GBM has to retransmit all packets in the window, but SR only retransmits the problematic one.
  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.

  HDLC is a bit-oriented data link protocol. It uses reliable data transfer protocols like SR.
  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.

• b) (15) A 3000-km-long T1 trunk is used to transmit a 64-byte frame. Assume the propagation speed is 6musec/km. (Note that the data rate for T1 carrier is 1.544Mbps. Also note the difference between transmission delay and propagation delay.)
  • b1) If using stop-and-wait protocol, calculate the efficiency of the protocol. (Efficiency is defined as the ratio between the waiting time and the round trip delay. Assume you spend l sec to transmit the data, R sec to propagate the data from the sender to receiver, and another R sec to receive the acknowlegement. Then the efficiency would be l/(l+2R). Assume the transmission time for the acknowledgement can be ignored.)

    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%

  • b2) If go-back-N protocol is used, in order to achieve an efficiency of 100%, what is the maximum window size at the sender's side? What is the maximum number of bits of the sequence number? (read page 217 if you don't have any clue)

    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

• c) (10) In lecture note 5, slide 16, a scenario of GBN is illustrated where the sender's window size is 4 and the 3rd packet (pkt 2) got lost during the transmission. Assume that instead of pkt2 getting lost, it is the acknowledgement of pkt2 got lost. Use the same notation in that figure, plot the scenario.

  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.

• d) (+10) Selective repeat dilemma: Two scenarios are given below describing a potential problem that selective repeat protocol might cause when the window size and the sequence number bit are not correctly specified. Study these two scenarios and discuss what kind of problem they have caused. This is the reason that HDLC protocol specifies the following rule: The window size must be less than or equal to half the size of the sequence-number space.
  

  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.