System Resilience and Performance

Data Link Layer Overview

• The data link layer translates the physical layer into a link responsible for node-to-node communication.
• Key responsibilities: framing, addressing, flow control, error control, and media access control.

DLL Design Issues

• Services Provided to the Network Layer: The network layer wants to send packets to its neighbors without concern for the details of physical transmission.
• Framing: Frames group physical layer bits into units for communication, and are often used interchangeably with packets or messages.
• Error Control: Sending and receiving checksums verifies data integrity.
• Flow Control: Prevents a fast sender from overwhelming a slow receiver.

Data Link Layer Design Issues

• Provides a well-defined service interface to the network layer.
• Deals with transmission errors.
• Regulates data flow to prevent slow receivers from being overwhelmed by fast senders.

Services Provided to the Network Layer

• The data link layer's primary service is transferring data between network layers on source and destination machines.
• The data link layer can provide unacknowledged connectionless service, acknowledged connectionless service, or acknowledged connection-oriented service. These services vary based on the system's requirements.

Unacknowledged Connectionless Service

• Source machine sends independent frames to the destination machine.
• No prior or subsequent connections are established.
• Lost frames are not recovered in the data link layer; higher layers handle recovery.
• Ideal for real-time traffic (e.g., voice) where delay is critical. Often used in LANs.

Acknowledged Connectionless Service

• Each frame is individually acknowledged by the destination machine.
• Sender knows if a frame is correctly received.
• Unsuccessful delivery within a specified time interval causes retransmission.
• Effective over unreliable channels, such as wireless systems.

Acknowledged Connection-Oriented Service

• Source and destination machines establish a connection before transfer.
• Each frame is numbered and guaranteed to be received exactly once.
• Guarantees all frames are received in the correct order.
• Transfer occurs in three phases: connection establishment, transmission, and connection release.

Placement of Data Link Protocol

• Data link protocol processes frames and packets, routing process handles packet routing, and transmission line to router manages communication through a router.

Framing

• The data link layer translates the raw bit stream to discrete units (frames)
• Framing methods involve character count, flag byte with byte stuffing, starting and ending flags with bit stuffing, and encoding violations.

Framing - Character Count

• The first framing method uses a field in the header to specify the number of characters in the frame.
• The receiver reads the count and knows the frame end.

Framing - Byte Stuffing

• Method uses reserved characters to indicate the start and end of a frame.

Framing - Bit Stuffing

• The transmission of a data frame is done by using a specific bit stream (e.g., 01111110) as start and end delimiters.
• A 0 bit is inserted into the data stream whenever 5 consecutive 1 bits occur.
• The receiver detects the bits and removes the inserted 0 bit.

Physical Layer Coding Violations

• Some computer networks employ redundancy into their encoding scheme.
• Manchester coding encodes a bit of data as two bits of different polarity (e.g., high-low for bit 1, low-high for bit 0).

Error Control

• Error control ensures delivery of all frames to a destination, possibly in order.
• Using acknowledgements (ACKs): Returns a message confirming correct frame receipt. Some systems also use negative acknowledgements (NACKs) for errors.
• Timers: Resend frames if no ACK or NACK is received within a specific time period.
• Sequence numbers: Prevent duplicate frames during retransmissions.

Flow Control

• Flow control throttles sender speed to match receiver's speed using feedback-based or rate-based approaches.

Error Correction and Detection

• Error detection ensures that the data received is correct without having the original message.
• Error correction methods add redundancy to detect and correct errors.
• Common methods include vertical redundancy check (VRC), longitudinal redundancy check (LRC), cyclic redundancy check (CRC), and checksum.

Types of Errors

• Single-bit error: Only one bit in the data unit is changed (e.g., 1 to 0 or 0 to 1).
• Burst error: Two or more bits in the data unit are changed; not necessarily consecutive.

Error Detection vs Error Correction

• Error Detecting Codes: Detect errors but don't usually correct them.
• Error Correcting Codes: Detect and correct errors, often referred to as forward error correction

Error Detection

• Error detection determines if the received data is correct without needing the original message.
• Redundancy is commonly added by adding extra bits to detect errors.

Vertical Redundancy Check (VRC)

• Appends a bit at the end of a data block to ensure the total number of 1's is even or odd (even parity or odd parity).
• Detects all odd-numbered errors in a data block.

Longitudinal Redundancy Check (LRC)

• Adds a new character (BCC) to each data block.
• Counts bits longitudinally, akin to parity but counted in a columnar fashion.
• More effective in detecting burst errors compared to VRC.

Two Dimensional Parity Check

• Checks each character using Vertical Redundancy Check (VRC).
• The entire block of characters is verified using the Longitudinal Redundancy Check (LRC) character.

Cyclic Redundancy Check (CRC)

• CRC is a bit stream that is placed at the end of the data block with specific characteristics.
• Based on polynomial arithmetic; determining a remainder when dividing one polynomial by another to detect errors.
• Implementable with a small amount of hardware. Includes shift registers and XORs.

Generator Polynomial

• A pattern to be divided into received data to detect errors if they occurred during transmission.

CRC Calculation

• The transmitter generates an n-bit sequence called the Frame Check Sequence (FCS).
• The resulting frame (k+n) bits is divided by a predetermined number to ensure data integrity.

Cyclic Redundancy Check

• Uses a message polynomial and a generator polynomial to calculate a block polynomial divisible by the generator polynomial.

Sending CRC

• Multiplies the message polynomial by the highest power in the generator polynomial (adding zero-bits).
• Divides the result by the generator polynomial.
• The results are the CRC bits to be added to the data.

Receiving CRC

• Receives the entire received message and divides by the generator polynomial.
• If remainder is zero, the receive is accepted and no error was detected.

Checksum

• Checksum is an error-detection scheme used in IP, TCP, and UDP.
• Divides the data into segments, calculates the sum of the segments using 1's complement arithmetic.
• Calculates the checksum of the sum and appends that to the original data.
• The receiver performs the same process, and checks if the final sum is zero. If it is zero, no errors are detected.

Checksum Example

• The data is divided into segments; each of the segments are n bits long.
• The sum of the segments is calculated using 1's complement addition.
• The sum is complemented to get the checksum, which is appended to the original data.
• The receiver performs the same process and checks if the result is zero; if so no errors are detected.

Error Correction

• Two techniques for error correction; retransmission (backward error correction) and forward error correction (FEC).
• Retransmission involves retransmitting data if an error is detected; simpler and common technique.
• FEC allows the receiving device to correct errors, often more complex than retransmission.

Hamming Code

• Hamming code is an error-correcting code that can detect or correct single-bit errors in a binary data stream.
• It adds extra bits called redundant bits to the original data bit to find if any error occurred. The redundant bits are placed at specific positions based on the power of 2.
• To calculate the number of redundant bits, the relation to be satisfied is 2^r ≥ m+r+1.

Burst Error Correction

• Hamming code is not designed to handle burst errors directly.
• Rearranging the bits or sending in multiple parts can reduce error occurrences.

Sliding Window Protocols

• These protocols are bidirectional and belong to a class of sliding window protocols.
• The number of frames that a sender can send before getting an acknowledgement is restricted by the sliding window.

Data Frame Transmission

• The approach to sending data frames has evolved.
• Uni-directional protocols, full-duplex (using two separate circuits), full-duplex (using one circuit), and piggybacking, are different approaches that have been used depending on the communication channel.

Control Variables

• Variables in the receiver and sender side that control transmission.

Go Back N Protocol

• Improves efficiency by allowing multiple frames to be sent before acknowledgement.
• If an error occurs, all subsequent frames are retransmitted.

Selective Repeat Protocol

• More efficient than Go Back N.
• Only the damaged frame is retransmitted, reducing bandwidth waste.
• Uses a negative acknowledge (NAK) to notify the sender about errors.

Sending & Receiving Windows

• Sender & receiver windows control frames that can be sent and accepted respectively.

Acknowledgement Timer

• The time the sender waits to get confirmation for correct transfer of a frame.
• Essential to prevent unnecessary retransmits.

This quiz explores key principles of complex systems, focusing on resilience and adaptation mechanisms. Participants will assess factors affecting resource allocation and the consequences of component failures. Test your knowledge of how these elements impact overall system efficiency.