Better to know some
... than all
The Data Link Layer
The data link layer transforms the logical communication channel provided by the physical layer into a reliable channel by splitting the data into frames which are subjected to error control and flow control procedures. We will first look at various link protocol types, and then describe the constituent functions of link protocols, such as acknowledgment of frames, error checking, and flow control. These functions are embodied by a general technique called the sliding window protocol, which will be described next. Finally, we will discuss two popular data link standards: BSC and HDLC.
Link Protocol Types
Data link protocols are divided into two basic categories: synchronous and asynchronous. These are described below. It is important not to confuse synchronization at the data link layer with synchronization at the physical layer. These two are distinct and essential in their own right: physical layer synchronization ensures that the transmitter and the receiver share a common clock signal so that bit boundaries can be detected; data link layer synchronization ensures that user data is not confused with control data.
Synchronous protocols operate by delimiting user data with unique bit patterns which the receiver uses to detect where the user data begins and where it ends. Synchronous protocols may be character-oriented or bit-oriented. In a character-oriented protocol, user data consists of a sequence of characters and is delimited by two unique control characters (SYN and EOT). The biggest disadvantage of character-oriented protocols is that they are based on specific character sets (e.g., ASCII or EBSDIC) and are therefore character-set dependent.
In a bit-oriented protocol, no specific character set is assumed. The unit of transmission is a frame, which consists of user data (an arbitrary bit sequence), control data, address data, error checksum, and two delimiting bit patterns at either end of the frame.
The delimiting bit pattern used is 01111110 and is called a flag. To avoid this bit pattern occurring in user data, the transmitter inserts a 0 bit after every five consecutive 1 bits it finds. This is called bit stuffing; its effect is canceled by the receiver, which removes every 0 bit that occurs after every five consecutive 1 bits. Bit-oriented protocols are by comparison more recent than other protocols and have dominated the market. To acknowledge their importance, most of this chapter is devoted to the description of this class of protocols.
Asynchronous protocols are character-oriented and operate by having the transmitter surround each character with a start and a stop bit. These two bits indicate to the receiver where the character starts and where it ends. The receiver extracts the user data by removing the start and stop bits.
Master-slave protocols are used in situations where a primary station (such as a host) controls one or more secondary stations (such as peripheral devices). Communication between the master and its slaves is governed by a general technique called polling. Polling is typically used in a multidrop line configuration where, for example, a set of terminals are connected to a host via a shared communication line. In its simplest form, polling works as follows. The master can send data in form of a message to any of the slaves. The message contains an address which uniquely identifies the slave for which it is intended. To receive data from the slaves, the master 'polls' each slave in turn by sending a message to it and asking if it has any data to send. The slave responds by either sending data or by sending a rejection message to indicate it has nothing to send.
In peer-to-peer protocols, all stations have similar status and communicate in a democratic fashion. The majority of network link protocols fall into this category. The carrier-sense protocol serves as an example, where all stations share a common communication channel. To transmit, a station monitors the channel for transmission by other stations and awaits its becoming free. Once the channel is free, the station starts transmitting. Collisions (when two stations attempt to transmit simultaneously) are resolved by requiring a transmitting station to monitor the channel at the same time and stop the transmission if it detects another station also transmitting. The collided stations then wait for some random period of time before attempting to retransmit.
Link Protocol Functions
Data link layer does not provide end-to-end accountability; this is a responsibility of higher layers. Instead, each station is responsible for ensuring that the data received by it is correctly passed to the next station. This is facilitated by the use of acknowledgments, of which there are two types:
*An acknowledgment (ACK) is sent by a receiver to a transmitter to indicate that a frame has been received seemingly intact.
* A negative acknowledgment (NAK) is sent by a receiver to a transmitter to indicate that a corrupt frame has been received, or that a frame is missing. In character-based protocols, acknowledgments are implemented as control characters. In bit-oriented protocols, they are implemented as acknowledgment frames.
The control field of a frame can contain two sequence numbers: a send sequence number and a receive sequence number. The frames dispatched by a transmitter are sequentially numbered using the send sequence number. The receiver compares the send sequence number of a frame against the send sequence numbers of earlier frames to check for lost frames. A NAK frame uses the receive sequence number to identify a corrupted frame, while an ACK frame uses the receive sequence number to identify the next frame it expects to receive, implying that it has correctly received all frames with sequence numbers less than that number. To improve the use of network bandwidth, an acknowledgment method known as piggybacking is often used. In piggybacking, instead of sending a separate acknowledgment frame, the receiver waits until it has data to send to the receiver and embeds the acknowledgment in that frame.
Timers provide a mechanism for placing a time limit on certain operations to be completed. A timer is set by a process and has a predefined expiry period. When the timer expires, the corresponding process is notified to take appropriate action. Link protocols make use of a number of different timers, the exact number and function of which is protocol-dependent. However, two important timers (called T1 and T2) are used by most protocols.
T1 is set by a transmitter upon transmitting a frame. The transmitter expects to receive an acknowledgment frame before T1 expires. Otherwise, the transmitter resets T1 and retransmits the frame. The protocol allows a certain number of retries before the problem is propagated to a higher layer.
T2 is set by a receiver to ensure that an acknowledgment frame is sent to the transmitter before its T1 timer expires. This is intended to avoid the transmitter having to retransmit frames because the receiver has been slow in acknowledging their receipt. When piggybacking is used, the receiver will send a separate acknowledgment frame if T2 expires.