Homework 3 - Data Link Layer (Due 09/14, extended to 09/21) (100+10)

Note: please TYPE your answer wherever possible.

Problem 1: (15 pts) Framing

• a) (10 pts) problem 2 (page 243)
• b) (5 pts) problem 4 (page 243)

Problem 2: (45 pts) Error detection and correction

• a) (5) problem 8 (page 244)
• b) (5) problem 12 (page 244)
• 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?
  • c2) (8) Assuming that even parity is used in the Hamming code, show the bit pattern transmitted for this message.
  • c3) (4) Suppose that the third bit from the left is inverted due to transmission errors. Show how Hamming code detects and corrects it.
  • c4) (4) Suppose that both bit 3 and bit 7 are inverted. Show how Hamming code cannot correct these errors.
  • 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: 11010011010 if using 3 check bits.)
  • c6) (3) Suppose in the transmitted message, bit 2, 3, and 10 are inverted (counting from the left). Show how receiver detects errors.
  • c7) (3) Suppose in the transmitted message, bit 2 and 8 are inverted. Show if the receiver can detect errors.
  • c8) (4) Based on the results from c6) and c7), what conclusion can you draw or verify?

Problem 3: (40 pts + 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?
• b) (15) A 3000-km-long T1 trunk is used to transmit a 64-byte frame. Assume the propagation speed is 6musec/km (6 x 10^(-6) sec/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 acknowledgement. Then the efficiency would be l/(l+2R). Assume the transmission time for the acknowledgement can be ignored.)
  • 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)
• 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.
• 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.