Data Link Layer Design Issues: An integral element of every Network Stack

In this article, we take a closer look at why the Data Link Layer is an important protocol, its anatomy and Data Link Layer design issues.

The publication of the OSI (Open Systems Interconnection) Model by the International Organization for Standardization (ISO) back in 1984 was marked as an important milestone in the evolution of networked systems and services. Specifically, the OSI Model provides a conceptual framework for describing the main components and functionalities of networked systems [1]. It facilitates the development of network protocols and boosts interoperability across heterogeneous networks. 

The model defines seven abstract layers of networked functionalities, namely the Physical Layer, Data Link Layer, Network Layer, Transport Layer, Session Layer, Presentation Layer, and Application Layer. Each of the layers implements functionalities over the transmitted data i.e., they transmit and process the data of networked communications based on appropriate hardware, software, and middleware implementations.

Over the years, many networked systems and devices were designed and developed in line with the OSI model. Hence, network designers, network service providers and network operators had the chance to provide feedback about the practical deployment and use of functions across the above-listed layers. In this context, some layers were deemed more important and are more widely used than others. Some layers are part of every network implementation, while others (e.g., the Presentation layer) are barely used. One of the most important layers is the Data Link Layer (layer 2), which is widely deployed and used.

To give you an overview, the main functions and the design issues of this layer are:

• Providing services to the network layer
• Framing
• Error Control
• Synchronization
• Flow Control 
• Media Access Control

Data Link Layer Design Issues & Anatomy

Data Link Layer functionalities are integral to any network implementation. This is because the layer ensures reliable data exchange between network nodes while providing the means for establishing, managing, and releasing end-to-end data-link connections across different networking devices [2]. It provides intermediate functionalities between network nodes, which ensure that messages are properly delivered to their destination.  To this end, the data are assembled into data frames, which contain source and destination addresses as needed for guaranteeing reliably delivery.

Services provided by the Data Link to the Network layer

In the OSI model, the Data Link layer resides between the physical layer and the network layer. Hence, it receives bits from the physical layer and undertakes to deliver them in a proper format to the network layer. When sending data, messages leverage the network layer services first, invoke data link layer services, and end up sending data through the physical layer. At the receiving side, the reverse path is followed: bits from the physical layer are delivered to the data link layer, which then delivers the message to the network layer. Thus, the data link layer intermediates between the physical and the network layers to ensure the reliability of the delivery by structuring the data into well-defined frames.

The data link layer ensures that the network layer receives the data of the sender without any losses. It can also establish a logical communication channel between the sender and the receiver of a message by keep track of a virtual connection between them. Virtual connections are managed by the data link Layer. In this context, the data link layer provides to the network layer the following types of services:

• Unacknowledged Connectionless Service: This service ensures data delivery without errors. However, the transmitted data frames are independent of each other and are not subject to any acknowledgement from the destination machine regarding their proper delivery. The service is characterized as “connectionless” because the data link layer does not establish any virtual connection between the sender and the receiver. Likewise, the service is unacknowledged i.e., in case a frame is lost, there are no provisions for detecting the loss and recovering from it. In essence, a connectionless service provides no error control and no flow control. The most prominent example of a connectionless data link layer protocol is the popular Ethernet protocol.
• Acknowledged Connectionless Service: Like in the case of the previous service, this service does not establish and does not keep track of any virtual connection between sender and receiver. Nevertheless, contrary to the previous service, the receiver acknowledges packet delivery. Hence, the sender knows whether the data that it has transmitted are gracefully and safely received. Given that there is no virtual connection between sender and receiver, the various frames are acknowledged individually.  In case no acknowledgement is received within a specified time interval, the sender resends the data frame. In this way, this service provides increased reliability when compared with the unacknowledged connectionless service. Acknowledged connectionless services are commonly used over unreliable physical channels such as wider Wi-Fi services.
• Acknowledged Connection-Oriented Service: This service establishes a logical connection between the server and the receiver. The establishment takes place prior to the transferring of any data. Accordingly, data is transmitted over the established logical connection. Moreover, in the scope of this service, frames are labelled with appropriate numbers to ensure that each of the frames is received only one time, while also certifying their proper order and sequence.

In practice the data link layer provides also framing services to the network layer i.e., it encapsulates the transmitted information in frames. The latter is picked up at the receiving side and passed to the network layer. Moreover, the data link layer offers addressing functionalities based on the use of hardware addresses that are unique on the network link. Such addresses are encoded in network devices (e.g., switches, network interface cards) by their OEM (Original Equipment Manufacturer). Also, the data link layer enables the synchronization of senders and receivers and offers this as a service to the network later i.e., it obviates the need for the network layer to deal with synchronization issues. The framing and synchronization services are illustrated in the following paragraphs.

Framing

Framing helps to establish the logical point to point connection between the send and the receiver. By including the bits of the physical layer in frames, the receiver structures the transmitted bits into meaningful data chunks. Different techniques can be used for the implementation of the framing process i.e., for defining the boundaries of a frame. One of the techniques is based on the definition of the number of characters (i.e., “character count”) that comprise the frame. This number is included in a special field of each frame’s header. By looking at this field, the receiver understands how many of the following characters belong to the frame and determines the point where the frame ends.  The character count method can lead to errors, in cases where the character count field is distorted during transmission. In such cases, the synchronization of the framing process can be lost and the receiver might not be able to identify the end of the frame.

To alleviate the risks of the character count method, the character stuffing technique can be used. In this case, the boundaries of the frame are identified based on a transmission of a special “Escape” character, which has a predefined and well-known pattern. By identifying this character, the receiver can infer the boundaries of the frame. It can then remove the Escape character and convey the rest of the message to the network layer. 

It is also possible to identify the beginning and end of a frame based on a specified sequence of bits. This bit sequence is added in the frame to denote its boundaries. The method is called bit stuffing. Bit stuffing is implemented in many data link layer instances, including the data link layer of the popular USB (Universal Serial Bus) protocol.

Synchronization

Based on the previously presented techniques, receivers can identify the actual data from the frame. This is also known as the synchronization function of the data link layer. There are however cases where the sequence of data frames is interrupted i.e. synchronization is lost. In this case, the receiver must resynchronize itself with the sender.

Error Control

As already outlined, certain services of the data link layer (i.e. the acknowledged services) offer error control functionalities. The latter identify possible errors in the transmission (e.g., flipped bits) and attempt to recover from them. Specifically, the data link layer provides the means for reporting errors to the sender and for recovering the altered bits. Overall, two main functionalities are supported, namely error detection and error correction.

Error Detection detects bits that have been affected by noise or other transmission problems. On the other hand, error correction attempts to fix the identified errors. To this end, the data link layer attempts to reconstruct the original data in its error-free form. This is generally a costly and challenging process, which can be based on a variety of different techniques that provide diverse throughput and robustness propositions. Specifically, some of the most popular error control techniques include:

• Stop-and-Wait ARQ (Automatic Repeat Request): This is one of the simplest error control mechanisms. It is based on the acknowledgement of frames from the receiver. Specifically, the sender transmits data packets to the receiver and waits for an ACK (Acknowledgement). In case the ACK is not received by the sender within a pre-defined time interval, the sender resends the non-acknowledged frame. However, when the ACK is received, the sender transmits the next packet and waits for the next ACK message.  The process is repeated until all packets and all data frames are successfully transmitted and acknowledged.
• Sliding Window ARQ: This technique provides the means for continuous transmission of packets in ways that improve the overall data throughput. A sliding window mechanism i.e., a finite buffer is used.  It operates in one of the following two modes: (i) Go-Back-N ARQ (Automatic Repeat Request): In this mode, the sender transmits packets without a need to wait for an ACK packet. The number of packets that can be sent without an ACK is indicated by the size of a specified window (N). In cases, no errors are detected, and the sender has sent the packets of the N sized window in their correct order, the sender has to wait for an ACK prior to sending more packets. The reception of ACK(s) from the receiver unblocks the sender, which becomes able to transmit up to N extra packets depending on the number of frames that were acknowledged. In this mode the receiver will discard any duplicate frames or frames having numbers outside the specified window; (ii) Selective Repeat ARQ: This mode focuses on retransmission of potentially damaged or lost data. Data transmission from the sender to receiver is continuous and not constrained by any window. The sender retransmits only the frames that have not been acknowledged. Hence, this mode results typically in fewer retransmissions and higher throughput than the previous one. However, it tends to be less popular than Go-Back-N as it is more complex to implement both at the sender and at the receiver side.

Flow Control

Flow control is the process of ensuring that the sender and the receiver exchange data at the same speed. In general flow control functionalities are implemented based on two main approaches: (i) Feedback based Flow Control: In this case, the sender sends frames following the reception of ACK packets from the receiver; and (ii) Rate based Flow Control: In this case, the transmission rate is restricted without depending on an ACK from the receiver. 

The data link layer leverages feedback-based flow control mechanisms, including:

• Stop and Wait Techniques: As already outlined, in the scope of these techniques, senders send a packet and wait for ACK from the receiver. Upon reception of the ACK, the sender sends the next frame, and the process continues in the same way.
• Sliding Window Techniques: In this case, multiple frames can be sent without waiting for an ACK, which results in better efficiency than in the case of stop and wait protocols. As explained, in the scope of the sliding window technique both the sender and the receiver maintain windows of a certain size (N). The sender sends up to N frames without waiting for an ACK. As soon as the window is filled, an ACK in expected. Upon the reception of an ACK for some frames, the sender advances the window (i.e., “slides the window”) and is able to send more frames i.e., equal to the number of frames that have been acknowledged.

These are obvious similarities in the flow control and error control mechanisms of the data link layer. However, there is also a major difference: Error control strives to detect and correct errors, while flow control is only concerned about ensuring that senders and receivers operate at the same speed.  

Media Access Control

Data link layer implementations for broadcast networks must also ensure how different senders gain access to the shared channel. This is a typical concern in Ethernet networks and various types of wireless networks. To address this concern, many data link layer implementations comprise a special sublayer, namely the Medium Access Control (MAC) sublayer. The MAC provides mechanisms for regulating access to the shared physical medium.

Concluding Remarks

Previous paragraphs have illustrated the main functionalities of the data link layer. They have also presented the techniques that are most widely used when implementing these functionalities.  It is quite evident that the data link layer is very rich in functionalities. Therefore, its implementations are sometimes complex and challenging, yet important for the good functioning of most networking infrastructures. Most importantly, the data link layer functionalities include many concepts that are replicated and implemented in other layers as well [3]. As a prominent example, error control and flow control functionalities are present in the transport layer. They are very important for ensuring reliable data delivery and for boosting the scalability and availability of the network. Likewise, connection-oriented and connectionless services are seen in many other protocol implementations. Overall, the data link layer does not only have practical value for the operation of modern networks. It is also an excellent educational device for researchers, engineers, and network practitioners.

References

1. J. D. Day and H. Zimmermann, "The OSI reference model," in Proceedings of the IEEE, vol. 71, no. 12, pp. 1334-1340, Dec. 1983, doi: 10.1109/PROC.1983.12775.
2. J. W. Conard, "Services and protocols of the data link layer," in Proceedings of the IEEE, vol. 71, no. 12, pp. 1378-1383, Dec. 1983, doi: 10.1109/PROC.1983.12781.
3. Andrew S. Tanenbaum, Nick Feamster, David J. Wetherall, “Computer Networks, 6th Edition”, ©2021 Pearson, ISBN-13: 9780137523214.