Data Link Layer Protocols

• The main task of the data link layer is to transform a raw transmission facility into a virtual communication channel for sending frames error-free
• The main design issues of the data link layer include framing, error detection and correction, and flow control

Framing

• Framing involves breaking the received bit stream into discrete frames
• A frame and packet are distinct units in data transmission.
• Framing methods include character count, flag bytes with byte stuffing, and start/end flags with bit stuffing.

Character Count

• A field in the header specifies the number of characters in the frame
• If the data link layer at the destination finds a character count, it knows how many characters follow and where the end of the frame is
• Character count can be changed by a transmission error, which makes it unreliable
• Due to error vulnerability, the character count method is rarely used.

Flag Bytes with Byte Stuffing

• Each frame starts and ends with special flag bytes (FLAG)
• Protocols often mark the start and the end of a frame with the same FLAG byte
• Two consecutive FLAG's indicate the end of a frame and the start of a new frame
• The FLAG's bit pattern might occur in the data and cause issues
• A solution is byte stuffing or character stuffing
• The sender's data link layer inserts a special escape byte (ESC) before each "accidental" flag byte in the data
• The receiver's data link layer removes ESC before passing the data to the network layer, and understands that the FLAG that follows is part of the data
• If ESC itself occurs in the data, it undergoes the same stuffing
• Single ESC indicates an escape sequence, and double ESC indicates that the second ESC is part of the data
• A disadvantage is that it is closely tied to using 8-byte characters

Starting and Ending Flags with Bit Stuffing

• Allows character codes with an arbitrary number of bits per character
• Each frame starts and ends with the special bit pattern 01111110
• If 5 consecutive 1s occur in the data, the sender automatically stuffs a 0 in the outgoing data stream
• If the receiver sees 5 consecutive 1s followed by a 0, it automatically deletes the 0

Error Control

• Error control can be classified into two broad categories: Forward Error Correction (FEC) and Automatic Repeat Request (ARQ)

Forward Error Correction (FEC)

• FEC involves adding enough redundant information to the data to enable the receiver to correct any errors and recover the original transmitted data on its own
• FEC uses error-correcting codes

Automatic Repeat Request (ARQ)

• ARQ involves adding only enough redundant information to the data to allow the receiver to detect that some errors occurred (without locating or correcting them)
• The receiver then requests a re-transmission
• ARQ uses error-detecting codes

Error-Correcting Codes

• Error-correcting codes are based on adding redundant bits to a data bit stream
• If the number of data bits is m, the number of legal codewords (messages) is 2^m
• The number of added check (redundant) bits is r
• If the total length of the codeword is n, then m + r = n
• The total number of possible codewords is 2^n, where only 2^m of them are legal

Important Definitions

• Hamming distance between 2 codewords is the number of bits the two codewords differ; it can be computed by an X-OR operation
• Hamming distance of a code is the distance between the 2 codewords whose Hamming distance is a minimum

Error Correction and Detection Capability of Codes

• Error will not be detected if it converts a valid codeword into another valid codeword
• To detect d errors, a distance of d + 1 code is needed
• Meaning that when the receiver sees an invalid codeword, it can tell that errors occurred
• To correct d errors, a distance of 2*d + 1 code is needed
• The valid (legal) codewords are so far apart that even with d changes, the original codeword is still closer than any other codeword, so it can be uniquely determined
• If a frame is transmitted and 'd' errors occurred during transmission, the received frame and the transmitted frame will have a Hamming distance 'd'
• If the receiver receives an invalid codeword, it chooses the closest (with respect to Hamming distance) valid codeword

The Hamming Code

• The bits of the codeword are numbered starting from 1
• The bits that are powers of 2 (1, 2, 4, 8, 16, ...) are check bits
• The rest of the bits (3, 5, 6, 7, 9, 10, 11, 12, ...) are filled up with the m data bits
• Each check bit forces the parity of some collection of bits, including itself, to be even (or odd)
• To see which check bits the data bit in position k contributes to, rewrite k as a sum of powers of 2
• If check bits 1, 2, and 8 are incorrect then bit 11 is inverted (because it is the only data bit checked by 1, 2, and 8)

Decoding

• The receiver examines each check bit to see if it has the correct parity.
• If all check bits have the correct parity, then the codeword has no errors.
• If any incorrect parity then the sum of the check bit positions having incorrect parity gives the position of the incorrect bit.

Error Detecting Codes

• Error-correcting codes are useful on communication channels with a high error rate, such as wireless channels.
• When the error rate is much lower, such as on copper wires or fiber-optic links, using error detection and retransmission is typically more efficient.
• Cyclic Redundancy Check (CRC) codes are an error-detecting code that is widely used in practice.

Cyclic Redundancy Check (CRC) Codes

• A k-bit frame is regarded as a polynomial with k terms and of order k - 1
• Example: 110001 is regarded as the polynomial M(x) = x^5 + x^4 + 0x^3 + 0x^2 + 0*x^1 + x^0 = x^5 + x^4 + 1
• Sender and receiver agree upon a generator polynomial G(x)
• If r is the order/degree of G(x), then r will also be the number of check bits appended to the data bits
• The most significant and least significant terms of the generator polynomial must be non-zero (the generator starts with 1 and ends with 1)
• Example of a generator polynomial of degree 4: G(x) = x^4 + x + 1
• The sender uses G(x) to compute the r check bits and appends them to the data bits
• The receiver uses G(x) to detect any errors

Sender Algorithm

1. Let r be the degree of G(x). Append r zeros to the low-order end of the frame, which now contains m + r bits (and the last r bits are zeros), so that it corresponds to x^r M(x)
2. Divide the bit string corresponding to x^r M(x) by the bit string corresponding to G(x) using long division, with all operations modulo 2 (addition and subtraction being X-OR operations)
3. Subtract (modulo 2) the remainder of the long division from the bit string corresponding to x^r M(x)

• Results in the polynomial T(x) with the corresponding bit string being the Transmitted Frame

Sender Algorithm - additional information

• The remainder of long division has length equal to or less than 'r' bits, in which case zeros are added to the left to make it 'r' bits
• Replacing the zeros yields the remainder obtained in Step 2
• The resulting polynomial T(x) is divisible by G(x) with no remainder

Receiver Algorithm

1. The receiver will receive the bit string corresponding to T(x) with possible errors.
2. Used for dividing the received bit string by the bit string corresponding to G(x).
3. • A zero remainder indicates no errors
   • A non-zero remainder indicates some errors

• Error-detection capability depends on the choice of G(x)
• One of the standard polynomials used in Ethernet (e.g., IEEE 802 standard): G(x) = x^32 + x^26 +* x^23 + x^22 + x^16 + x^12 + x^11 + x^10 + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1
• G(x) above can detect all bursts of errors of length 32 bits or less, and all bursts of an odd number of errors

Retransmission Strategies

• If the receiver detects an error (using some error-detecting code, e.g., Cyclic Redundancy Check), the frame will have to be retransmitted
• 3 different retransmission strategies inclue Stop-and-Wait Protocol, Go-Back-N Protocol, and Selective Repeat Protocol
• These protocols are also known as Automatic Repeat Request (ARQ) protocols

Stop-and-Wait Retransmission Strategy

• The sender transmits one frame at a time
• If a frame is received correctly at the receiver, the receiver sends an acknowledgement frame (ACK) to the sender
  • If the sender receives an ACK, it sends a new frame
• If a frame is received with an error, the receiver discards the frame
  • If the sender times out, it sends the same frame again
• Drawbacks to stop-and-wait:
  • Frame is received correctly by receiver, receiver sends ACK, but ACK gets lost.
  • Sender will time out, assuming that the original frame had an error and will send new frame
  • The repeated frames and loss of ACK results in loss of tracking the frames

Modified Stop-and-Wait

• The sender transmits a frame including its sequence number in its header
• The receiver checks the sequence number
  • A new frame is accepted, while a duplicate frame is discarded
• If the receiver receives a new frame with no errors, it will send the sequence number of what the next frame it expects

Go-Back-N Retransmission Strategy

• The sender transmits frames (including sequence numbers) and does not wait for ACK to be received.
• The receiver sends an ACK for every correctly received frame
• The receiver discards all frames that follow
• The sender will notice a lack of any ACK of any frame after some timeout
• Finally, the sender will back up and start all over again sending frames and the processes are looped

Selective Repeat Retransmission Strategy

• The sender transmits frames (including sequence numbers), and does not wait for ACK to be received (same as Go-Back-N)
• The receiver sends ACK for every correctly received frame (same as Go-Back-N)
• In the event of an error:
  • The receiver discards only the frame with errors and buffers all subsequent frames
  • The sends a negative acknowledgement (NAK) for the error frame
  • Sends a negative acknowledgement NAK for the error frame

Explore data link layer protocols. Learn about frame structure, error detection using generator polynomials G(x), character count, and bit stuffing techniques. Understand Forward Error Correction (FEC) and Automatic Repeat Request (ARQ).