Unit5 - Subjective Questions

The Data Link Layer is the second layer of the OSI model, responsible for the node-to-node delivery of data. Its primary functions include:

• Framing: Divides the stream of bits received from the Network Layer into manageable data units called frames.
• Physical Addressing: Adds a header to the frame to define the sender and/or receiver of the frame (MAC addresses).
• Flow Control: Implements mechanisms to prevent an overwhelming amount of data from being sent by a fast transmitter to a slow receiver.
• Error Control: Adds mechanisms to detect and retransmit damaged or lost frames (usually achieved through a trailer added to the end of the frame).
• Access Control: When two or more devices are connected to the same link, data link layer protocols determine which device has control over the link at any given time (MAC sublayer).

1. Simplest Protocol:

• It is a hypothetical protocol with no flow or error control.
• It assumes that the receiver can handle any amount of data at any rate, and the communication channel is completely error-free.
• The sender simply sends frames continuously without waiting for any acknowledgment.

2. Stop-and-Wait Protocol:

• This protocol introduces basic flow control.
• The sender sends one frame and then stops and waits for a confirmation (acknowledgment or ACK) from the receiver.
• Once the ACK is received, the sender transmits the next frame.
• It is inefficient for long-distance links because the sender remains idle for a significant amount of time waiting for acknowledgments.

Error Detection:

• It is the process of identifying whether an error has occurred in the transmitted data during transmission over the network.
• It only informs the receiver that the data is corrupted but does not identify the exact location or the number of errors.
• Common techniques: Parity Check, Checksum, CRC (Cyclic Redundancy Check).
• Requires fewer redundant bits.

Error Correction:

• It is the process of not only detecting the error but also identifying the exact bit(s) that are corrupted and correcting them.
• It requires more complex algorithms and a higher number of redundant bits compared to error detection.
• Common techniques: Hamming Code, Reed-Solomon Code.
• Error correction can be done via Forward Error Correction (FEC) or by requesting retransmission (ARQ).

Simple Parity Check (1D Parity):

• A single redundant bit (parity bit) is added to the end of a data block.
• Even Parity: The bit is chosen so that the total number of 1s in the block (including the parity bit) is even.
• Odd Parity: The bit is chosen so that the total number of 1s is odd.
• Drawback: It can only detect single-bit errors or an odd number of errors. It fails if an even number of bits are flipped.

Two-Dimensional (2D) Parity Check:

• Data is organized into a matrix (rows and columns).
• A parity bit is calculated for each row and each column.
• This method increases the likelihood of detecting errors. It can detect all 1, 2, and 3-bit errors, and most 4-bit errors. It can also be used to correct a single-bit error by intersecting the faulty row and column.

The Checksum is an error detection technique often used at higher layers (like TCP/IP) but applicable conceptually.

Sender Side:

1. The data is divided into segments, each of bits.
2. All segments are added together using 1's complement arithmetic.
3. The sum is complemented (bitwise NOT) to yield the checksum.
4. The checksum is appended to the data and sent across the network.

Receiver Side:

1. The received message (including the checksum) is divided into segments of bits.
2. All segments are added together using 1's complement arithmetic.
3. The sum is complemented.
4. If the result is all $0$s, the data is accepted (assumed error-free). If the result is not zero, the data is rejected.

CRC is a robust error-detecting code based on polynomial arithmetic (modulo-2 division).

Mechanism:

1. Data bits are treated as the coefficients of a polynomial, .
2. A predetermined generator polynomial, , is shared between sender and receiver. If is of degree , then redundant bits (zeros) are appended to the data.
3. Sender Side: The padded data is divided by using modulo-2 arithmetic (XOR operations). The remainder of this division is the CRC.
4. The CRC is appended to the original data and transmitted.
5. Receiver Side: The received data (including CRC) is divided by the same .
6. If the remainder is $0$, the message is accepted as error-free. Otherwise, it is rejected.

Hamming Code is an error-correcting code that can detect up to two-bit errors and correct single-bit errors. It places redundant bits at specific positions (powers of 2) in the data block.

Formula for redundant bits (r):
, where is the number of data bits.
For , (which is ). So, redundant bits are needed.
Total bits = bits.

Positioning:
Bits are numbered from 1 to 7.
Redundant bits () are at positions 1, 2, and 4.
Data bits () are at positions 3, 5, 6, and 7.

Calculation (Even Parity):

• : Checks bits 1, 3, 5, 7.
• : Checks bits 2, 3, 6, 7.
• : Checks bits 4, 5, 6, 7.
  The values are set to ensure the total number of 1s in each set is even. The receiver performs the same checks to find the error position.

The Medium Access Control (MAC) sublayer is the lower sublayer of the Data Link Layer (the upper being Logical Link Control or LLC).

Purpose and Necessity:

• In a shared-medium network (like early Ethernet or Wi-Fi LANs), multiple stations are connected to the same physical link.
• If two or more stations transmit simultaneously, their signals will collide and garble the data.
• The MAC sublayer is necessary to provide Multiple Access Resolution. It dictates the rules of how devices share a common medium, determining who gets to transmit next and when.
• It also handles framing, physical addressing (MAC addresses), and basic error detection (like FCS/CRC at the end of the frame).

Pure ALOHA:

• Mechanism: Any station can transmit data at any time whenever it has data to send. It relies on acknowledgments; if no ACK is received, a collision is assumed, and the station waits a random backoff time before retransmitting.
• Vulnerable Time: (where is the frame transmission time).
• Maximum Efficiency: The maximum throughput is . The peak efficiency is only about 18.4% at .

Slotted ALOHA:

• Mechanism: Time is divided into discrete slots equal to the frame transmission time. A station can only transmit at the beginning of a timeslot. If it misses the start, it must wait for the next slot.
• Vulnerable Time: (halved compared to Pure ALOHA, as partial collisions are avoided).
• Maximum Efficiency: The maximum throughput is . The peak efficiency is doubled to about 36.8% at .

CSMA (Carrier Sense Multiple Access) is a probabilistic MAC protocol based on the principle of "sense before transmit" or "listen before talk."

Principle:
To minimize the chances of collision, a station wishing to transmit must first listen to the transmission medium (carrier sense) to check if another station is currently transmitting.

• If the medium is idle, the station transmits.
• If the medium is busy, the station defers its transmission.

While CSMA significantly reduces collisions compared to ALOHA, collisions can still occur due to propagation delay. If station A transmits, it takes time for the signal to reach station B. Before the signal arrives, B might sense the medium as idle and start transmitting, leading to a collision.

These methods dictate how a station behaves after sensing the medium in CSMA:

• 1-Persistent CSMA: If the channel is busy, the station continuously listens to the channel until it becomes idle. Once idle, it transmits immediately with a probability of 1. It is greedy and leads to high collisions if multiple stations are waiting.
• Non-Persistent CSMA: If the channel is busy, the station does not continuously listen. Instead, it waits for a random period of time and then senses the channel again. This reduces collisions but increases delay (idle time on the channel).
• p-Persistent CSMA: (Used in slotted channels). If the channel is idle, it transmits with probability . With probability , it defers to the next slot. If the next slot is also idle, it again transmits with probability . This balances collision reduction with channel utilization.

CSMA/CD improves upon CSMA by adding the ability to detect collisions and abort transmission, saving bandwidth.

Mechanism:

1. A station senses the channel. If idle, it begins transmitting.
2. While transmitting, the station simultaneously listens to the channel to compare the signal being sent with the signal on the wire.
3. Collision Detection: If the received signal differs from the transmitted signal, a collision is detected.
4. Abort and Jam: The station immediately aborts transmission and sends a short "jam signal" to ensure all other stations recognize the collision.
5. Backoff: The station waits a random amount of time calculated using the Binary Exponential Backoff algorithm before attempting to sense and transmit again.

Note: For CSMA/CD to work, the frame transmission time must be at least twice the maximum propagation delay ().

The Binary Exponential Backoff algorithm is used in CSMA/CD to determine the random waiting time a station must observe after a collision before attempting retransmission.

Algorithm:

1. After a collision, time is divided into discrete slots.
2. On the collision (for a specific frame), the station chooses a random number from the range .
3. The wait time is (where Slot Time ).
4. For example, on the 1st collision, , range is . On the 2nd collision, , range is .
5. The maximum value of is typically capped at 10. If 16 collisions occur, the transmission is aborted, and an error is reported to upper layers.

Random Access (Contention Protocols):

• No station is assigned priority over another.
• Any station can transmit data at any time (contention for the medium).
• Collisions are possible and expected, and mechanisms (like CSMA/CD) are needed to handle them.
• Decentralized control.
• Examples: ALOHA, CSMA, CSMA/CD, CSMA/CA.

Controlled Access (Contention-Free Protocols):

• Stations consult one another to determine which has the right to send. A station cannot send unless it has been authorized.
• Collisions are eliminated as access is coordinated.
• Control can be centralized or distributed.
• Examples: Reservation, Polling, Token Passing.

Token Passing is a controlled access MAC protocol where devices are organized in a logical ring.

Mechanism:

• A special control frame called a token circulates around the logical ring from one station to the next.
• A station can only transmit data if it possesses the free token.
• When a station receives the token and has data to send, it changes the token status to "busy" and appends its data, transmitting it to the next node.
• The data frame circulates the ring until it reaches the destination, which copies the data.
• The frame returns to the sender, which releases a new free token onto the ring for the next station to use.
• Advantages: No collisions, predictable delay.
• Example: Token Ring (IEEE 802.5).

Polling works in a topology where one device is designated as a primary station and others are secondary stations. All data exchanges must go through the primary station.

Functions:

• Select: Used when the primary station has data to send to a secondary station. The primary sends a SEL (select) frame to alert the secondary. If the secondary is ready, it replies with an ACK. The primary then sends the data.
• Poll: Used when the primary wants to receive data from a secondary. The primary sends a POLL frame to the secondary, asking if it has data to send.
  • If yes, the secondary sends the data, and the primary sends an ACK.
  • If no, the secondary sends a NAK (Negative Acknowledgment), and the primary polls the next secondary in the sequence.

Ethernet (IEEE 802.3) is the most widely used LAN technology. It uses CSMA/CD for medium access in its traditional half-duplex, shared-medium implementations.

Ethernet Frame Format:

1. Preamble (7 bytes): Alternating 1s and 0s for clock synchronization.
2. SFD (Start Frame Delimiter - 1 byte): 10101011, indicating the start of the frame.
3. Destination Address (6 bytes): MAC address of the receiver.
4. Source Address (6 bytes): MAC address of the sender.
5. Length/Type (2 bytes): Indicates the length of the data or the upper-layer protocol (like IPv4).
6. Data and Padding (46 to 1500 bytes): The actual payload. If data is less than 46 bytes, padding is added to meet the minimum frame size requirement.
7. FCS (Frame Check Sequence - 4 bytes): Contains a 32-bit CRC for error detection.

In standard Ethernet (CSMA/CD), a transmitting station must be able to detect a collision before it finishes sending the frame. If the frame is too short, the sender might finish transmitting and assume success before the collision signal reaches back to it.

Mathematical Condition:
The transmission time of the frame () must be greater than or equal to the Round Trip Time (RTT), which is twice the maximum propagation delay ().

Since (where is frame length and is bandwidth), and (where is distance and is velocity):


For standard 10 Mbps Ethernet, this results in a minimum frame size of 64 bytes (512 bits). Hence, padding is used if the data payload is too small.

Hamming Distance:
The Hamming distance between two binary words of the same length is the number of bit positions in which they differ. It can be found by applying the XOR operation between the two words and counting the number of 1s in the result.

Minimum Hamming Distance ():
The minimum Hamming distance of a coding scheme is the smallest Hamming distance between all valid codeword pairs.

Relation to Error Control:

• Error Detection: To guarantee detection of up to errors in all cases, the minimum Hamming distance in a block code must be .
• Error Correction: To guarantee correction of up to errors, the minimum Hamming distance must be .

In the Reservation method, a station needs to make a reservation before sending data. Time is divided into intervals. In each interval, a reservation frame precedes the data frames sent in that interval.

Mechanism:

• If there are stations in the system, the reservation frame has minislots.
• Each minislot belongs to one station.
• When a station has data to send, it transmits a 1-bit signal in its corresponding minislot to reserve a spot.
• After the reservation frame, the stations that made reservations can transmit their data frames in the order of their minislots.
• Stations that did not reserve a slot must wait for the next reservation interval.
• This guarantees collision-free data transmission at the cost of the overhead of the reservation frame.