1

Prof. M. Gerla & R. Dzhanidze. Class 117. Chapter 3a

Chapter 3a

The Data Link Layer Protocols

1. Introduction
2. DLL Design. / a. Network Layer Services.
b. Error Control
c. Flow Control
3. Elementary Data Link Protocols / a. Stop-and-Wait Protocol
b. A Simplex protocol for a
Noisy Channel; Time-out
c. Sliding-Window Protocols
d. Sliding-window FlowControl
e. A One-Bit Sliding-Window
f. A Protocol Using-Go-Back- N
g. Selective Reject
4. High-Level Data Link Control / a. HDLC Operation
b. HDLC Protocol
5. DLL in the Internet / a. PPP-The point-to-pointProtocol

(T. 183-229; 234-246)

1. Introduction

In this chapter we will consider the design principle for layer 2- DLL. We will consider communication between two adjacent machines (connected by point-to-point communication channel, and the bits are delivered in the same order in which they are sent) at the DLL.

Our discussion so far has concerned sending signals over a transmission link. For effective digital data communications, much more is needed to control and manage the exchange. To achieve the necessary control, a layer of logic is added above the physical interfacing. This logic is referred to as data link control, or data link control protocol. The layer that provides the data link control is called Data Link Layer (DLL). When a data link control protocol is used, the transmission medium between systems is referred to as adatalink.

To see the need for DLL, we list some of the requirements and objectives for effective data communication between two directly connected transmitting-receiving stations:

  • Frame synchronization. Data are sent in blocks called frames. The beginning and end of each frame must be recognized.
  • Error control. Any bit errors introduced by the transmission system must be corrected.
  • Flow control. The sending station must not send frames at a rate faster then the receiving station can absorb them.
  • Addressing. On a multipoint line, such as a LAN, the identity of the two stations involved in a transmission must be specified.
  • Link management. The initiation, maintenance, and termination of a data exchange requires a fair amount of coordination and cooperation among stations.

Procedures for the management are satisfied by the DLL. Data Link Protocols used for the communication must take circuit errors, data rate, and time delay factors into consideration.

2. DLL Design.

Functions of the DLL are:

  1. Providing service interface to the network layer.
  2. Dealing with transmission errors
  3. Regulating the flow of data (slow receivers will not overloaded by fast senders).

For solution of these functions, the DLL takes the packets from the network layer and encapsulates them into frames for transmission. Each frame contains a frame header, payload field for holding the packets, and a frame trailer, see Figure 1.

Figure 1. “Packet” and “Frame” relationship

Frame management is basic task of the DLL. In some cases, functions of error control and flow control are allocated in transport or other upper layer protocols and not in the DLL, but principles are pretty much the same. In the DLL they often show up in their simplest and purest forms, making this a good place to consider them in this chapter.

a. Network Layer Services.

The function of the DLL is to provide services to the network layer. The principal service is transferring data from the network layer on the source machine to the layer on the destination machine. Actual path of the data transfer process follows layers 3-2-1 on the sender machine and 1-2-3 on the destination machine, but it is easier to think that two DLL processes data transfer using a data link protocol.The actual services can vary from system to system. Three reasonable possibilities that are commonly provided are:

  1. Unacknowledged connectionless service.
  2. Acknowledged connectionless service.
  3. Acknowledged connection-oriented service.

Let us consider each of them.

1. Unacknowledged connectionless service consists of having the source machine send independent frames to the destination machine without having the destination machine acknowledged them. No logical connection is established beforehand or released afterward. If a frame is lost due to noise on the line, no attempt is made to detect the loss or recover from it in the DLL. This class of service is appropriate when the error rate is very low so that recovery task is left for solution to higher layers. It is also appropriate for real-time traffic, such as voice, in which late data are worse than bad data. Most LANs use unacknowledged connectionless service in the DLL.

2. Acknowledged connectionless service is more reliable. When this service is offered, there are still no logical connections used, but each frame sent is individually acknowledged. In this way, the sender knows whether a frame has arrived correctly. If it has not arrived within a specific time interval, it can be sent again. This service is useful over unreliable channels, such as wireless system. The trouble with this strategy is that, frames usually have a strict maximum length imposed by the hardware and network layer packets do not. If the average packet is broken up into frames, and let say, 20% of all frames are lost, it may take a very long time for the packet to get through. If individual frames are acknowledged and retransmitted, entire packets get through much faster. On reliable channels, such as fiber, the overhead of a heavyweight data link protocol may be unnecessary, but on wireless channels, with their unreliability, it is well worth the cost.

3. Acknowledged connection-oriented service requires established connection between source and destination machines before any data are transferred. Any frame sent over the connection is numbered, and the DLL guarantees that each frame sent is indeed received, and are received in the same order. With connectionless service, in contrast, it is possible that a lost acknowledgement causes a packet to be sent several times and thus received several times. When connection-oriented service is used, transfers go through three distinct phases:

a. the connection is established and counters needed to keep track of

which frames have been received and which ones have not.

b. One or more frames are transmitted.

c. Connection is released, freeing up the variables, buffers and other

resources used to maintain the connection.

A typical example is a WAN subnet consisting of routers connected by point-to-point leased telephone lines. When a frame arrives at a router, the hardware checks it for errors, and then passes the frame to the DLL software (which might be embedded in a chip on the network interface board). The DLL software checks to see if it is the frame expected, and if so, gives the packet (contained the payload field) to the routing software. The routing software then chooses the appropriate outgoing line and passes the packet back down to the DLL software, which then transmits it. The flow over two routers is shown in Figure 2.

The routing code frequently wants the job done right. It does not want to be bothered too often with packets that got lost on the way. It is up to the DLL protocol, shown in the dotted rectangle, to make unreliable communication lines look perfect or, at least, fairly good.

To provide service to the network layer, the DLL must use the service provided to it by the physical layer. What the physical layer does is accept a raw of a bit stream and attempt to deliver it to the destination. This bit stream is not guaranteed to be error free. The numbers of bits received may be less than, equal to, or more than that the number of bits transmitted, and they may have different values. It is up to the DLL to detect and, if necessary, correct errors. The usual approach is for the DLL to break the bit stream up into discrete frames and compute the checksum for each frame. Method of bit stream breaking into frames, checksum algorithm, the checksum recompilation and error control methods are widely considered in literature, so we will not consider in this note, but recommend readers to observe the methods.

Figure 2. The flow over two routers

b. Error Control

Error control refers to mechanisms to detect and correct errors that occur in the transmission of frames. We will usethe model, which covers the typical case. As before, data are sent as a sequence of frames, frames arrive in the same order in which they are sent; and each transmitted frame suffers an arbitrary and variable amount of delay before reception. In addition, we disclose the possibility of two types of errors:

  • Lost frame
  • Damaged frame

The usual way to ensure reliable delivery is to provide the sender with some feedback about what is happening at the other end of the line. Typically, the protocol calls for the receiver to send back special control frames carrying positive or negative acknowledgment about the incoming frames. If the sender receives a positive ACK about a frame, it knows the frame has arrived safely. On the other hand, a negative ACK means that something has gone wrong, and the frame must be transmitted again.

The most common techniques for error control are based on some or all of the following ingredients:

  • Error detection.
  • Positive Acknowledgment.
  • Retransmission after time-out.
  • Negative acknowledgment and retransmission

When the sender transmits a frame, it generally also starts a timer. The timer is set to expire after an interval long enough for the frame to reach the destination, be processed there, and have the ACK propagate back to the sender. Normally, the frame will be correctly received and the ACK will get back before the timer runs out, in which case the timer will be cancelled. However, if either the frame or the ACK is lost, the timer will go off, alerting the sender to a potential problem. The solution is to just transmit the frame again. However, when frames may be transmitted multiple times is a danger that the receiver will accept the same frame two or more times and passé it to the network layer more than once. To prevent this from happening, it is generally necessary to assign sequence numbers to outgoing frames, so that the receiver can distinguish retransmissions from originals.

Collectively, these mechanisms are all referred to as Automatic Report Request (ARQ); the effect of ARQ is to turn an unreliable data link into a reliable one. Three versions Of ARQ have been standardized:

  • Stop-and-wait ARQ
  • Go-back-N ARQ
  • Selective-reject ARQ

All of these forms are based on the use of the flow control technique; we examine each of them in turn.

c. Flow Control

Another important design issue that occurs in the DLL (and higher layers as well) is what to do with a sender that systematically wants to transmit frames less than the receiver can accept them. This situation can occur when the sender is running on a fast computer and the receiver is running a slow machine. The sender keeps pumping the frames out at a high rate until the receiver is completely overloaded. Even if the transmission is error free, at a certain point the receiver will simply be unable to handle the frames as they arrive and will start to lose some. Clearly, something has to be done to prevent this situation.

Two approaches are commonly used: 1. Feedback-based flow control, the receiver sends back information to the sender giving it permission to send more data or at least telling the sender how the receiver is doing. 2. Rate-based flow control, the protocol has a built-in mechanism that limits the rate at which senders may transmit data, without using feedback from the receiver. Since rate-based schemes are never used in the DLL we will look at feedback-based flow control schemes.

Various feedback-based flow control schemes are known, but most of them use the same basic principle. The protocol contains well-defined rules about when a sender may transmit the next frame. These rules often prohibit frames from being sent the receiver has granted permission. For example, when connection is set up, the receiver might say: “You may send me n frames now, but after they have been sent, do not send any more until I have told you to continue”.

3. Elementary Data Link Protocols

Let us consider DLL three protocols with increasing complexity. Before we look at protocols let us make some assumptions underlying the model of communication. Let us assume that:

1). DLL and Network layer are independent processes that communicate by passing messages back and forthtrough the physical layer. In many cases, the physical and DLL processes will be running on a processor inside a special network I/0 chip and the network layer code will be running on the main CPU. However, other implementations are also possible (e.g., three processes inside a single I/O chip, or the physical and DLL as procedures called by the network layer process). In any event, training the three layers as separate processes makes the discussion conceptually cleaner and also serves to emphasize the independence of the layers.

2). Machine A wants to send a long stream of data to machine B, using a reliable, connection-oriented service. Latter, we will consider the case where B also wants to send data to A simultaneously. A is assumed to have an infinite supply of data ready to send and never has to wait for data to be produced, when A’s DLL asks for data, the network layer is always able to comply immediately.

3). Machines do not crash. That is, these protocols deal with communication errors, but not the problems caused by computers crashing and rebooting.

As far as the DLL is concerned, the packet passed across the interface to it from the network layer is pure data, whose every bit is to be delivered to the destination’s network layer. The fact that the destination’s network layer may interpret part of the packet as a header is of no concern to the DLL.

When the DLL accepts a packet, it encapsulates the packet in a frame by adding a data link header and trailer to it see Figure 1. Thus, a frame consists of an embedded packet, some control information (in the header), and a checksum (in the trailer). The frame is then transmitted to the DLL on the other machine. We will assume that there exists suitable library procedures to_physical_layer to send a frame and from_physical_layer to receive a frame. The transmitting hardware computes and appends the checksum (thus creating the trailer), so that the DLL software need not worry about it.

Initially, the receiver has nothing to do. It just is waiting for something to happen by procedure call wait_for event(&event). This procedure only returns when something has happened (a frame has arrived). Upon return, the variable event tells what happened. The set of possible events differs for the various protocols to be described and will be defined separately for each protocol. (In realistic situation, the DLL will not wait for event, but will receive an interrupt, which will cause it to stop whatever it was doing and go handle the incoming frame).

When a frame arrives at the receiver, the hardware computes the checksum. If the checksum is incorrect (i.e. there was transmission error), the DLL is so informed (event=cksum_error). If the inbound frame arrived undamaged, the DLL is also informed (event=frame_arrived) so that it can acquire the frame for inspection using from_physical_layer. As soon as the receiving DLL has acquired an undamaged frame, it checks the control information in the header, and if everything is all right, passes the packet portion to the network layer. Under no circumstances is a frame header ever given to a network layer.

There is good reason why the network layer must never be given any part of the frame header: to keep the network and data link protocols completely separate. As long as the network layer knows nothing at all about the data link protocol or the frame format, these things can be changed without requiring changes to the network layer’s software. Providing an interface between network layer and DLL greatly simplifies the software design because communication protocols in different layers can evolve independently.

More general solution is to have the receiver provide feedback to the sender. After having passed a packet to its network layer, the receiver sends a little frame back to the sender which gives the sender permission to transmit the next frame. After having sent a frame, the sender is required by the protocol to wait its time until the little (acknowledgment) arrives. Using feedback from the receiver to let the sender know when it may send more data.