Unit 3: Data link layer - Subjective Questions

The data link layer is the second layer of the OSI model. It provides reliable and organized communication between two directly connected nodes over a physical link.

Its major responsibilities are:

• Framing: Dividing the continuous stream of bits received from the network layer into manageable data units called frames.
• Physical addressing: Adding source and destination MAC addresses to frames.
• Flow control: Preventing a fast sender from overwhelming a slow receiver.
• Error control: Detecting and, in some cases, correcting transmission errors.
• Access control: Deciding which device may use a shared communication channel.
• Reliable delivery: Providing acknowledgments and retransmissions when required.

Thus, the data link layer converts the unreliable physical link into a more dependable link for the network layer.

Transmission errors occur when the received data differs from the transmitted data. The main types are:

• Single-bit error: Only one bit in a data unit changes from to or from to . For example, may become .
• Burst error: Two or more bits within a data unit are affected. The corrupted bits need not be consecutive in value, but the error span extends from the first corrupted bit to the last corrupted bit.
• Random error: Errors occur independently at scattered positions in the data.
• Packet or frame loss: A complete frame may be lost because of noise, buffer overflow, or link failure.

Errors are caused by noise, attenuation, interference, synchronization problems, and hardware faults. Error detection and correction techniques are used to identify or recover from these errors.

Error detection techniques add redundant bits to the original data so that the receiver can determine whether corruption has occurred. Important techniques include:

• Vertical redundancy check: A parity bit is added to each character. Even parity makes the total number of s even, while odd parity makes it odd.
• Longitudinal redundancy check: Data is arranged in rows and columns, and parity is calculated for each column. It is more effective than simple parity for detecting burst errors.
• Checksum: The data is divided into fixed-size words, which are added using one's-complement arithmetic. The complement of the sum is transmitted as the checksum.
• Cyclic redundancy check: The data is treated as a binary polynomial and divided by a generator polynomial. The remainder is appended to the frame. The receiver repeats the division and checks whether the remainder is zero.

Among these methods, CRC is widely used because it provides strong detection of burst errors with relatively small overhead.

CRC procedure:

1. Let the data be .
2. The generator is , whose degree is .
3. Append four zeros to the data:
   
4. Divide the appended data by using modulo-2 division, where subtraction is performed using XOR.
5. The remainder has at most four bits.
6. Transmit the codeword:
   

Modulo-2 division gives the remainder:

Therefore, the transmitted frame is:

At the receiver, the complete frame is divided by . If the remainder is , the frame is assumed to be error-free; otherwise, an error is detected. CRC detects all single-bit errors and many multiple-bit and burst errors, depending on the generator polynomial.

Hamming code is a forward error correction technique that inserts parity bits at specific positions in a data word. The receiver uses the parity checks to locate and correct a single-bit error.

For data bits and parity bits, the number of parity bits must satisfy:

The parity bits are placed at positions that are powers of two:

Each parity bit checks a selected group of bit positions. At the receiver:

• The parity checks are recomputed.
• Their results form a binary syndrome.
• A zero syndrome indicates no detected error.
• A nonzero syndrome gives the position of the erroneous bit.
• The identified bit is complemented to correct the error.

Standard Hamming code corrects all single-bit errors and detects many double-bit errors. Extended Hamming code adds an overall parity bit and can correct one-bit errors while detecting two-bit errors.

Framing is the process of dividing a stream of bits into identifiable data units called frames. It enables the receiver to determine the beginning and end of each data unit.

Major framing methods are:

• Character count: A field in the header specifies the number of characters in the frame. Its disadvantage is that an error in the count can make the receiver lose synchronization.
• Byte stuffing: Special flag bytes mark the beginning and end of a frame. If the flag or escape byte appears in the data, an escape byte is inserted before it.
• Bit stuffing: A flag such as is used. After five consecutive s in the data, the sender inserts a . The receiver removes this stuffed bit.
• Physical-layer coding violations: Special signal patterns that are not used for normal data represent frame boundaries.

Framing also supports addressing, error detection, sequencing, and flow control.

Byte stuffing and bit stuffing are techniques used to prevent data from being confused with a frame delimiter.

In byte stuffing, suppose the flag byte is FLAG and the escape byte is ESC. If the data contains FLAG, the sender transmits ESC FLAG. The receiver removes the inserted ESC.

In bit stuffing, if the data contains:

then the sender inserts a after the fifth consecutive so that the sequence cannot be mistaken for the flag. The receiver removes the extra after detecting five consecutive s.

Both methods maintain frame transparency, but bit stuffing is independent of character encoding.

Data link layer protocols define how frames are organized and exchanged between neighboring nodes. Their important design issues and functions include:

• Service definition: The layer may offer connectionless or connection-oriented service, with or without acknowledgment.
• Framing: It identifies frame boundaries and ensures synchronization between sender and receiver.
• Physical addressing: It includes hardware addresses in the frame header.
• Flow control: It regulates the transmission rate according to receiver capacity.
• Error control: It detects damaged or lost frames and uses acknowledgments, timers, and retransmissions.
• Sequencing: Sequence numbers help identify duplicate, missing, or out-of-order frames.
• Medium access control: It coordinates access when multiple stations share a broadcast channel.
• Acknowledgment and retransmission: The receiver confirms successful delivery, while the sender retransmits frames when necessary.

Examples of data link protocols include HDLC, PPP, Ethernet, and wireless LAN protocols.

Flow control and error control solve different communication problems.

Flow control may temporarily stop the sender when the receiver cannot accept more frames. Error control identifies corrupted or missing frames and causes recovery through retransmission or forward error correction.

In practical protocols, both functions often operate together. For example, a sliding-window ARQ protocol limits the number of outstanding frames while also retransmitting frames that are lost or damaged.

In the basic stop-and-wait protocol, the sender transmits one frame and waits for an acknowledgment before sending the next frame.

Operation:

1. The sender sends a frame.
2. The receiver accepts the frame and sends an acknowledgment.
3. The sender waits until the acknowledgment arrives.
4. It then transmits the next frame.

This method provides flow control but may not provide error recovery unless timers and retransmissions are added. Its efficiency is low on long-delay links because the sender remains idle while waiting.

If the frame transmission time is and the one-way propagation delay is , the approximate utilization is:

Ignoring processing and acknowledgment transmission times, the efficiency decreases as propagation delay increases. Stop-and-wait is simple and suitable for short-distance or low-speed links, but it underutilizes high-bandwidth networks.

Stop-and-wait ARQ adds error control to the stop-and-wait protocol.

• The sender transmits one frame and starts a timer.
• If the receiver receives the frame correctly, it sends an acknowledgment.
• If the frame is damaged, the receiver discards it and may send a negative acknowledgment.
• If the frame or acknowledgment is lost, the timer expires and the sender retransmits the frame.
• A one-bit sequence number, usually or , distinguishes a new frame from a duplicate.

For example, after sending frame , the sender expects an acknowledgment indicating receipt of frame and then sends frame . If the acknowledgment is lost, the sender retransmits frame . The receiver recognizes the duplicate sequence number, discards the duplicate data, and sends the acknowledgment again.

Stop-and-wait ARQ is reliable and simple, but its throughput is limited because only one frame can be outstanding at a time.

Go-Back-N ARQ is a sliding-window error-control protocol in which the sender can transmit several frames before receiving acknowledgments.

Working:

• The sender maintains a window of up to unacknowledged frames.
• Frames are numbered using sequence numbers.
• The receiver normally accepts only the next expected frame.
• A cumulative acknowledgment confirms the receipt of all frames up to a specified sequence number.
• If one frame is lost or damaged, the receiver discards that frame and all subsequent out-of-order frames.
• After timeout, the sender retransmits the erroneous frame and every frame sent after it.

Advantages:

• Better channel utilization than stop-and-wait ARQ.
• Cumulative acknowledgments reduce acknowledgment overhead.
• Receiver implementation is relatively simple.

Disadvantages:

• Correct frames following an erroneous frame are retransmitted.
• It can waste bandwidth on noisy or long-delay links.
• A large window may cause many unnecessary retransmissions.

Selective Repeat ARQ is a sliding-window protocol in which only lost or damaged frames are retransmitted.

Working:

• The sender may transmit multiple frames within its window.
• The receiver accepts and buffers correct frames even if they arrive out of order.
• Individual acknowledgments identify successfully received frames.
• A separate timer may be maintained for each outstanding frame.
• When a frame is lost or damaged, only that frame is retransmitted.
• The receiver reorders buffered frames before delivering them to the upper layer.

Selective Repeat is more efficient but requires additional memory, timers, and processing at the receiver.

With an -bit sequence number field, the total number of distinct sequence numbers is:

Go-Back-N ARQ:

The receiver accepts frames in order, so the sender window may contain at most:

The unused sequence number prevents ambiguity between an old frame and a new frame after sequence numbers wrap around.

Selective Repeat ARQ:

Because the receiver buffers out-of-order frames, the sender and receiver windows must not overlap after sequence number wraparound. Therefore, the maximum window size is:

For example, if , there are sequence numbers:

• Go-Back-N maximum window: frames.
• Selective Repeat maximum window: frames.

These limits ensure that a received sequence number can be interpreted unambiguously.

ARQ protocols use feedback and timers to provide reliable delivery.

• Acknowledgment (ACK): Indicates that a frame or group of frames has been received correctly. ACKs may be individual or cumulative.
• Negative acknowledgment (NAK): Indicates that a frame is damaged or missing and should be retransmitted.
• Timer: The sender starts a timer after transmitting a frame. If the expected ACK does not arrive before timeout, the sender assumes that the frame or ACK was lost and retransmits.
• Sequence number: Identifies frames and prevents duplicate delivery when retransmissions occur.

An ACK may itself be lost. In that case, timeout causes retransmission, and the receiver uses the sequence number to recognize the duplicate. It does not deliver the duplicate to the upper layer but sends the appropriate ACK again.

Together, these mechanisms allow ARQ protocols to recover from damaged frames, lost frames, and lost acknowledgments.

Multiple access control is the set of techniques used to coordinate the transmission of several devices that share a common communication medium.

It is necessary because simultaneous transmissions may interfere with one another. This interference can cause collisions, corrupted frames, reduced throughput, and unfair access to the channel.

A multiple access protocol determines:

• Which station may transmit.
• When a station may transmit.
• How a station detects or avoids collisions.
• How stations recover after a collision.
• How bandwidth is shared fairly among users.

Multiple access protocols are commonly classified as:

• Random access: Stations compete for the channel, and collisions may occur.
• Controlled access: Stations take turns according to a coordination mechanism.
• Channelization: The available channel is divided among users by frequency, time, code, or space.

Examples include ALOHA, CSMA, polling, token passing, FDMA, TDMA, and CDMA.

Pure ALOHA:

• A station transmits whenever it has a frame.
• If a collision occurs, it waits for a random time and retransmits.
• A frame is vulnerable to collision for a period of , where is the frame transmission time.
• Its maximum throughput is:
  

Slotted ALOHA:

• Time is divided into slots of one frame duration.
• A station may begin transmission only at the start of a slot.
• The vulnerable period is reduced to .
• Its maximum throughput is:
  

Slotted ALOHA is more efficient because it reduces the time during which a collision can occur.

Carrier Sense Multiple Access (CSMA) requires a station to listen to the channel before transmitting. This reduces collisions because a station avoids transmission when it senses that the channel is busy.

Important CSMA variants are:

• 1-persistent CSMA: A station transmits immediately when the channel becomes idle. If the channel is busy, it continuously senses it. This can cause collisions when several stations are waiting.
• Nonpersistent CSMA: If the channel is busy, the station waits for a random time before sensing again. This reduces collisions but increases delay.
• p-persistent CSMA: Used with slotted channels. When the channel is idle, the station transmits with probability and defers with probability .

ALOHA transmits without first checking the channel, whereas CSMA uses carrier sensing. Therefore, CSMA generally provides better throughput and fewer collisions, although it cannot eliminate collisions caused by propagation delay.

CSMA/CD means Carrier Sense Multiple Access with Collision Detection. It is traditionally used in shared, half-duplex Ethernet.

• The station senses the channel.
• It transmits if the channel is idle.
• While transmitting, it monitors the channel for a collision.
• On collision detection, it sends a jam signal, stops transmission, and waits using binary exponential backoff.

CSMA/CA means Carrier Sense Multiple Access with Collision Avoidance. It is used mainly in wireless networks, where collision detection is difficult because a wireless station cannot reliably transmit and listen simultaneously.

• The station senses the channel.
• It waits for an interframe space and selects a random backoff period.
• Optional RTS/CTS exchange reserves the medium.
• ACKs confirm successful reception.

Controlled access protocols coordinate stations so that transmissions occur in an orderly manner and collisions are avoided.

• Reservation: Stations reserve future transmission slots using reservation bits or control messages. After the reservation phase, stations transmit according to the reservation order.
• Polling: A central controller asks each station in turn whether it has data to transmit. A station transmits only when it is polled. Polling provides orderly access but introduces controller overhead and a possible single point of failure.
• Token passing: A special control frame called a token circulates among stations. Only the station holding the token may transmit. After transmission or when its time expires, it releases the token to the next station.

Advantages:

• Collisions are avoided.
• Access can be made fair and predictable.
• Performance is stable under heavy load.

Disadvantages:

• Control overhead is required.
• A failed controller or lost token can disrupt communication.
• Delay may increase when many stations are waiting.