11 The Data Link Layer

Prof. Bhushan Trivedi

Introduction

The data link layer lays just above the physical layer. Two immediate neighbors are connected by this layer. One of them sends a data in form of a frame which the other layer receives. Both communicating parties take services of their physical layer for this process. The data which they send using frame arrives from the network layer. Similarly, the receiver extracts the network layer data from the received frame and pass it up to its own network layer. The first job this layer does is deciding the size of the frame and encapsulate network layer data into that frame. This layer also ensures the data being received is same as what is sent, the process known as error handling. The third requirement is to ensure the fast sender does not swamp the receiver with more amount of data than it can handle. Let us begin with an important idea called no monopoly which is an important reason to frame data.

Framing for no monopoly

When there are many users acting in the network and sending their data simultaneously, it is critical that the network is fair to all users. If the network system works in a sequential way that the data of every user is sent one after another completely, i.e. if one user starts downloading, others will have to wait till he completes, it is not fair. This is especially important when the first user is downloading a huge file which demands the others to wait for an inappropriate time. A solution which gives equal opportunity to all users is always a better choice.

Avoiding this problem is solved using a simple technique. Every user sends data in small chunks known as frames. The frames are interleaved or multiplexed together and thus everybody gets a fair chance. Thus instead of a stream of data, every user sends data in form of frames. There are few other advantages of framing but this is most important. Some other reasons include the restriction by the hardware card’s memory to hold data1, or restriction by the OS or the application which generates data2 etc. Here users take turns to transmit and routers along the line route their packets in the appropriate directions, thus no user is starved of bandwidth3. This process is done to make sure that no user can monopolize the channel.

The sender’s LAN card is responsible for framing and usually the maximum size of the frame that can be sent. The maximum size also enforces a limit on the other layer’s data size. For example, in the case of Ethernet, the maximum data that a frame can carry is 1500 bytes so the network layer packet cannot be bigger than that. The network layer of Internet has minimum 20 bytes of header and thus the transport layer data cannot be more than 1480 bytes. Thus the data link layer restriction enforces other layers.

1  For historical reasons, Ethernet allows maximum 1500 bytes of data

2, For example, the telnet generate data like ls, ps etc., which is quite short so the packet is also short

3 In some cases, some users are given higher priority than others and some packets may be dealt with more urgency than others. We looked at that part in module 6 during our discussion of packet classification and will come back to discuss this again in modules 31,32 and 33 while we discuss SDN.

There are a few questions that one may ask. For example, what will be the size of the frame? how can one frame the data? How to find if there are errors in the transmission and how to handle them? We will try to get the answers to all these questions in the following. We begin with techniques to frame.

Framing techniques

There are many ways to frame, we will look at four most used methods to do so.

1. Using the flag byte and stuff by byte stuffing,

2. Using the flag byte and stuff by bit stuffing

3. Using Illegal character combination

4. Using Character counter for length of frame

Framing using flag byte and stuff using byte

In this framing method, the beginning and end of the frame are indicated by a special byte, known as a flag byte. One of the popular methods is known as High-level Data Link Control or HDLC. It is used in point to point links like the router to router links. In this method, the frame is preceded and terminated by a ~ (tilt) character which is basically a bit pattern 01111110. Whenever a sender wants to send a frame, it begins its communication with this bit pattern and ends with the same. The receiver, when receives this typical bit pattern, learn about new frame coming in and record everything as a frame until it receives another similar bit pattern. However, that may be a problem if the ~ character is part of the data. For example, if the sender wants to send following.

“To stop input please enter X and then press a”

it is converted to

“~To stop input please enter X and then press a~”

When the receiver receives it, it omits the ~ character and gets the data. However, the process might run into trouble if the data itself contains a ~ character. For example, sender wants to send following.

“To stop input please enter ~ and then press a”

The receiver receives the following

“~To stop input please enter ~ and then press a~”

But understands it to be

“~To stop input please enter ~”

because at the first sign of ~ it stops. The problem is, the receiver has no way of knowing that the ~ it encounters is the part of data and not the terminator. There has to be some way to differentiate.

One of the ways to do so is known as byte stuffing, which stuffs a specific control byte just before the ~ sign appearing in data. The character for stuffing is an escape character and denoted by Esc. That means the above string is converted to following before transmission.

“~To stop input please enter <Esc>~ and then press a~”.

The receiver, when receives an Esc, the immediate next ~ character as the terminator and problem are solved. However, what if the data itself contains Esc? It will be preceded by another Esc, done. Here is an example.

“To stop input please enter <Esc>~ and then press <Esc>a, for main menu press <Esc>”

It is converted to the following.

“To stop input please enter <Esc<Esc ><Esc>~ and then press <Esc><Esc>a. for main menu press <Esc><Esc>”

This solution is quite fine but with two problems. First when the data is not considered to be 8-byte in size. For example, a word of 16, 32 or 64 bit is very common. The systems which process data using that larger chunk need to convert this 8-bit delimiter into a bigger character and read the data byte by byte rather than word by word. That is not much difficult but needs to be done. The second case is where the byte boundary is not preserved. For example, when the image is compressed, the result may not be in exact multiple of bytes (the compressed size in bits is not multiple of 8). The Terminator might happen to be part of two bytes, as 0010 0111 1110 0101. Look closely at this example. There are two bytes (separately underlined), the second half of first byte and the first half of second byte (indicated by bold) contains a delimiter. If we are reading the content byte by byte, we will miss the final ~ character. The solution, read the data bit by bit and process in terms of bits.

The framing process remains the same as before but the stuffing part requires a different approach. Let us try to see.

Framing using flag byte with bit stuffing

The solution to above is to send and receive the data as a bit pattern irrespective of word or byte boundaries. When we find the terminator, we stop.

The only question left is, what if the data itself contain the pattern 01111110? We can still go ahead and add an entire Esc character but a more compact solution is possible. We need to pick up and not an entire byte. The algorithm is simple, whenever sender encounters hardware-based consecutive 1s in the bit stream, pad a zero after that. Similarly, when the receiver gets a five consecutive 1s and next 0, the zero is removed. Stuffed zero is boldfaced for readability.

Here are four examples.

1.    If the input is 111000, then the output remains unchanged (8-bit input results in 8-bit output).

2.    If the input is 11111111, then the output is 111110111 (8-bit input results in 9-bit output).

3.    If the input is 11111011, then the output is 111110011(8-bit input results in 9-bit output).

4.    If the input is 01111110, then the output is 011111010 (8-bit input results in 9-bit output)

You may wonder why we are padding zero in all such cases where it is actually needed only in the final (4th) case. The reason is, the receiver has no idea of that case. If he receives a pattern 111110 how do it know that the zero after five ones is original zero or a padded one? The receiver cannot determine that. The solution is to pad zero in all cases and remove in all cases, thus receiver does not need to guess.

One of the popular protocols in Internet PPP (point to point protocol) is using this method for framing.

Framing by illegal characters

Another method to use characters for framing which are not permitted in data. For example, when Manchester encoding is used for Ethernet, two different voltage levels used, one is called High and another is called Low. The combination High + Low indicates 1 while Low + High indicates 0. The combination High + High and Low + Low are not allowed. Those combinations were used as frame delimiters in the first version of Ethernet.

Framing by encoding length as character counter

The following is to store the length of the frame as a character (a kind of counter) and precede the frame by that character. The receiver, upon receipt of the frame, first read the length and read the characters accordingly. The problem with this approach is that when the character indicating the length is corrupted, the receiver is misguided about the length of the frame4. This method, if ever used, used in conjunction with other methods. For example, Ethernet-I frame contains a field called Length for the same purpose along with another form of delimiters.

Once we have looked at how framing is done at data link layer, let us look at its second job, error handling. Before we learn that, let us try to understand what is an error and what are their types.

Error

When the received data is different than sent data, the difference is known as an error. For example, if the sender sends 10101010 and the receiver receives 10101011 then the error is 00000001. i.e. the difference between the values 10101010 and 10101011. The error rate for wired communication is reduced drastically in recent years due to better cabling systems based on cat-5 and FO cables, the wireless networks still remain prone to errors. Errors are inevitable, the communication systems must live with them and find way out of malfunctioning routers and dropped packets and content modification during transit. One of the important function of data link layer is to identify and/or correct errors. We will be discussing some important ways the data link layer manages errors in the next section. Though we mention data link layer, the processes that we divisor are quite general and used at other places as well. Before we start discussing error handling, let us see two different types of errors found in computing systems.

Error Types

Errors can occur due to various reasons some of which we have already discussed. Recent cables have improved the transmission but errors still creep in from wireless network connections. The idea is to communicate despite errors. The first type of error is called a single bit error while the second type is known as a burst error.

4  Look at reference 1 for the detailed description of this problem.

The computer data traffic usually encounters errors which affect multiple bits together and thus results in a burst error.

Figure 14.1 showcases both types of errors. Note that burst errors do not change every bit in a given range but some bits in that range including the first and the last bit. Single bit errors are easy to be detected and as we will see later, even possible to be corrected. Burst errors, technically more probable in current communication, are harder to detect and not possible to correct always. However, it has a distinct advantage. If the probability of error is fixed, single bit errors mean the errors are spread across entire message while burst errors mean that the errors are centered at a few places and the rest of the message is clear. Let us understand this by an example. Assume the probability of error is 1 bit in 1500 bytes (divisor size of an Ethernet frame). Assume we are sending 100 frames, each of them of 1500 bytes, how many frames will be in error? For a single bit case, all of them. If we expect a burst of 100 bits? 1 frame in 100 is in error the and thus 99 frames are in clear! So burst errors are not as bad as they seem at first look!

Redundancy

To keep the errors during transmission in check, there is an important component must be present in any error handling mechanism. It is called redundancy. Let us try to understand it with an example. Those who recharge their prepaid mobile phones sometimes opt for using a scratch card and type in the number present there for recharge (usually ending with #). It contains (usually) a long 16-digit number. If somebody tries to get lucky and just input a random number instead won’t succeed. If a random number entry is successful in recharging a mobile (without a voucher and money too!), all mobile service providers would have shut their shops by now. The arbitrary number is never going to work because this 16-bit number follows a typical pattern, some part of the number depends on the rest so much so that if somebody picks up a random number, it is almost impossible that that part of the number is correct. The actual recharge code may be 8 digits only and the rest 8 digits are calculated on that basis. The calculation is such that the probability of a random number being correct is almost zero.

The additional 8 bit in the above example is called redundant bits which are generated from the original 8 bits. Let us elaborate that further. Consider a mobile company generates voucher values from 1025 to 1035. If the number is kept as it is, a user can easily guess it. If one gets is genuine recharge with a value 1028, for example, and try nearby value he might succeed. To prevent that, two more digits are appended to this four-digit number. Those two digits are derived from the summation of all these four digits. Thus 1028 becomes 102811 (as 11 is the summation of the four digits, 1,0,2,8). 1025 becomes 102508 and so on. If one tries a nearby value or a random six-digit value, it would be difficult for him to pick up a right number.

These two additional bits are the redundant bits. The process to generate redundant bits is simple here (a plain addition), but more complex things are possible and used in practice. We will soon learn about a method called Cyclic Redundancy Check which is used in Ethernet and many other solutions.

The other critical point, what if the attacker relentlessly tries all possible digits one after the another? The solution is to restrict the lifetime of the voucher (to a month for example) and restrict the number of attempts to some feasible value (for example only five tires in a day). Once the lifetime or the number of attempts expired, the system stops accepting it. Thus the attacker does not get a chance to try all possible combinations.

Before we learn how redundancy is related to error handling, let us try to understand one more critical point. The data link layer might forgo error handling and it is just fine. Let us see why and when it is so.

Data link layer may not handle errors

It sounds ironic but the data link layer might forgo handling errors altogether or even check if the error has occurred but does not do anything about it. The Ethernet card, for example, check if the error has occurred and does not pass it up to the network layer, but does not report sender about the erroneous frame or take any action about it. The missing frame content is not received by the receiver’s TCP process eventually different strategies and it reports back the sender’s TCP layer about the missing segment. The missing segment is retransmitted using a fresh frame. Thus Ethernet does not handle error but the higher layer like TCP does so. On the contrary, a Wi-Fi connection checks for errors at every hop and report back. The sender retransmits the missing wireless frame in that case. Why are different strategies adopted in these two cases? Let us try to understand.

In a case of Ethernet, it is so reliable that once in 32 years a bit may be lost. If the data passes through 10 routers in a typical communication and each router checks every packet passes through, it is almost a waste of their time as the error is almost impossible. It is better if the Ethernet does not look for errors and pass the data without that check. It will improve the speed with which the routers can process the packets. If ever, a frame is garbled, the receiver eventually will learn about that segment being absent and ask for retransmission. Thus even when the data link layer misses out, there is no real harm. This is like a double security check. When there is a little chance that an unscrupulous person enters the premise, there is no real harm if we keep only one level of security and save time for everybody who is entering the premise.

Unlike that, in the case of data link layer based on wireless networks like 802.11. there is a much higher chance of a corrupted frame. Figure 13.2 describes a case where the errors are not handled at data link layer and 13.3 describes the case that the errors are handled. S is the sender, and R is the receiver, A, B, C, D are routers. A caravan of 10 frames are sent from S to R. When the errors are not handled at the data link layer and the probability of error is 1 out of 10 frames in every transmission, each hop loses a frame. Eventually, when D receives the caravan, only 5 out of that caravan contains valid frames. When those 5 frames are retransmitted to the complete path, at each hop, it demands total 5 * 5 = 25 retransmissions. Even after that, 2.5 of them will again be corrupted and needs retransmission. This will go on for a while.

Unlike that, if errors are handled at each hop (the data link layer of each hop), each hop loses one frame and thus need one retransmission. Eventually, we will be able to send all frame by just 5 retransmissions. This is really a huge saving. Thus, it is always better to handle errors at data link layer when the error rate is high. Unlike that, if the error rate is much lower, say one bit in one Gb. Assuming our frames are of 1000 bits, one of every 10,00,000 frames are corrupted and thus out of this 100 frames that we are sending, no frame is generally corrupted. If we send such caravan of 100 frames 1000 times, one frame is lost. In that case, there is no need to check errors at data link layer and overburden it.

Thus the rule of thumb is observed in networking, if the error rate is high, use data link layer with error handling, if the error rate is low, forgo it and rely on higher layers.

When a data link layer decides to handle the error, there are two different ways to do so. One is called error detection and the other is known as error correction. Error detection is about finding out if the received frame is erroneous or not. Error correction is about finding out if the received frame is erroneous and correct the error as well.

IT seems that the error correction is a better method but we will hold off that discussion till we discuss both approaches. The right answer is; it depends on the situation. We will elaborate that answer later. Let us understand how error detection is carried out.

Error Detection

One of the simplest methods of error detection is called checksum. The checksum is very similar to the process we discussed the recharge voucher problem. A checksum is a negative summation of all other data items. Suppose the data is to be transmitted as 23,45,43,21,77,24,09,51,11. The summation of all these numbers is 304. We now take -304 as the checksum and send it with other data. The idea is to have summation to be zero. When receiver sums up everything received and it equals zero, it is just fine but otherwise, the data is erroneous. TCP, UDP and many other Internet protocols use this method. They pick up 16-bit entities of the packet header and find the summation in binary form. The value is one’s complemented and added to the header. This is a lightweight method and thus very much suited for a transport layer protocol. Transport layer protocols are usually designed as a software process so the speed is critical for them. Data link layers usually deploy a heavy duty, hardware-based method like CRC that we are going to discuss next. As Data link layer is usually embedded in a network card, a hardware component, this works well for them. Cyclic Redundancy check is more accurate method than simple checksum but demands more computing and thus usually embedded in hardware. Ethernet card and Wi-Max card, for example, deploys CRC. Let us learn how it works.

CRC

The idea of CRC is based on simple division. Consider we want to send 427 to the other end. Assume we have decided to divide it by 13. When we do so, we cannot exactly divide 427 and get the remainder 11. When we subtract the value 11 from 427 we get 416 which is exactly divisible by 13. Now we send the value 416 to the other end, receiver divides it by 13 and it is divisible so receiver accepts the value as correct. If not, the receiver rejects it. Problem solved! There is a small problem though. We actually wanted to send 427 and not 416, how will receiver determine the actual value? We will also send the reminder that we subtracted so the receiver will add at the other end get the actual value back.

In fact, when the process is implemented in binary, it becomes little easier and we do not need to send explicit remainder. The binary division is performed using modulo 2 arithmetic. Let us understand how modulo 2 arithmetic works.

Modulo-2 Arithmetic

Modulo-2 arithmetic is the simplest possible addition and subtraction. The addition is without a carry and subtraction without borrow. If ever they occur, they are ignored. Thus when we have 1 + 1 the answer is 0 and the carry (1) is ignored. Similarly, when executing 0 – 1 we will have 1 as an answer without a borrow.

Hence the operation of addition and subtraction produces same results in modulo-2 arithmetic. Figure 13.4 describes the operation. Our division process uses a modulo-2 subtraction. Let us try to see how the CRC calculation is carried out. Assume a case where number 11001001010 is to be sent across. The frames normally are much longer but we take this small number for simplicity. Assume our divisor is 10101. Again, the normal divisors are 32 bits long but we take a smaller one for demonstration. Before we commence division, we will take an additional step, append four zeros at the end of the frame. Four is a maximum number of digits in a remainder so we use four digits.

Now we are ready to divide. We will take a deviser and divide the resultant number. The division is binary modulo-2. That means if the first bit of the number is 1, we will divide it by 1, subtract using modulo-2 and end when we have a number less than the size of the divisor. When we cannot divide, we add zero to quotient and bring the next digit from the dividend (the appended number) and stop when there is no digit to bring down (like normal division). Interestingly, we will only take the reminder now and forget the quotient. The remainder is to be subtracted from the dividend and what we get is the number that we are sending across. You can see that this division and subtraction process only affect the last four digits and the actual content of the number remains the same. Now, when the receiver receives the frame (the number that we sent), and divide it by the same divisor, and it divides perfectly, it will only need to remove last four digits and send the remaining part up.

Our objective is to catch the error if there are any. So far, we have only looked at a case of no errors. What if there is an error? What is the probability that an error goes undetected? Before we proceed to answer these queries, let us get a few things clear. The number that we take is basically a frame, generated by user’s data and we don’t have any control on it. On the contrary, the divisor that the sender and receiver uses is under our control. The point is, we must get a divisor which reduces the probability of error going through undetected. The following section throws more light on how that can be achieved.

Representing a binary number as a polynomial

We begin with a method to represent the number as a polynomial. This will help us prove in general form for any number. When we want to represent a binary number as a polynomial, each 1 appearing in the number at position p is represented as Xp. Let us take an example. 1101, has 1’s at position 0, 2 and 3 (position is counted from the right side and begins with 0).

The polynomial representation is x3 +x2 + x0 (which is basically 23+ 22 + 20). In the same fashion, 100100111 can be represented as x8 + x5 + x2 + x1 + x0. A polynomial can also be represented as p(x) or q(x). Suppose we are sending 110110110 and receiver receives 110110010. Let us call the number the sender sends p(x) and number the receiver receives is q(x). That means p(x) = x8+  x7 + x5 + x4 + x2 + x1, and q(x) = x8 + x7 + x5 + x4 + x1. You can see that one term, x2 is missing in q(x). If we look at the number, we can see that the third bit (2nd if start from left as 0) is inverted in the received polynomial. Let us try to see how CRC calculation is carried out.

CRC calculation as polynomial form

If we subtract p(x) from q(x) we will get 100, that means p(x) + 100 = q(x). The 100 is known as an error and we write it as e(x). That means p(x) + e(x) = q(x). This is true for any error and not just 100. Now, when the receiver divides q(x) with the divisor, he is dividing p(x) + e(x) by the divisor. We know that p(x) is already divisible. If and only if e(x) is perfectly divisible by the divisor, the error will go through unnoticed (q(x) is divided by the divisor when it should not). Now we must find that probability that e(x)/r(x) (where the divisor is named as r(x)) is an integer value.

We have control over r(x) and thus we would like to have a value of r(x) which make sure the probability of perfect division is as less as possible.

Let us now try to see what should be there in a good divisor. We will begin with simplest of errors, the single bit error. A single bit error e(x) is written as xi where i is the position of the bit which is inverted. If the divisor r(x) is at least two terms long and does not have a factor x it won’t divide any single term and thus e(x) won’t be divisible by r(x). The same logic is also applied to all other cases where the e(x) is shorter than r(x). For example, if r(x) has no factor of less than of 32 bit, any e(x) less than 32 bit will always be caught as it is not divisible by r(x)5.

If the error is of two bits, for example, 264 + 22, that means 2nd and 64th bits are inverted. The term

264 + 22 can be written as 22 (262 + 1). If the r(x) is not divisible by 2, it won’t be for any value 2n. so it won’t be for 22. What about 262 + 1? we must also find a divisor r(x) such that it does not divide for xk + 1 for k > 62, our second term is also not divisible and we are sure that the polynomial describing a two-bit error, xi + xj will not be able to divide e(x) and will be caught. However, if we are using an irreducible divisor of more than 2 bit, it will anyway be able to catch as there are no factors of r(x) which are less than 2 bits.

What if the error is larger than 32 bit and our r(x) is of 32-bit? Again, with irreducible r(x), only if the error is multiple of 32 bit, there is a chance of perfect division and not otherwise.

Interestingly, one more observation is, if the r(x) has a factor x+1, it will not divide any polynomial with odd number of terms. How? Let us try to understand. Assume the receiver receives q(x) as p(x) + e(x) where e(x) contain odd number of terms. Also assume e(x) is divisible by x+1. In that case, we can always write e(x) = (x+1) ee(x) where ee(x) is the polynomial

5  Normally irreducible polynomials are used in such cases which correspond to prime numbers, which do not have any factors other than itself and the identity element. Thus a 32-bit irreducible divisor can find any error less than 32 bit.

obtained from dividing e(x) by x+1. Take the case of x = 1, the e(x) having odd number of terms and using modulo arithmetic e(x) = 1+1+1+….+1 where number of ones are odd. For modulo-2 every pair of 1’s cancel each other and the result is 1 (as the terms are odd). The (x+1) ee(x) value, when put x as 1, becomes (1+1) ee(x) which is 0 * ee(x) = 0. That means e(x) = (x+1) ee(x) cannot be true as the LHS is 1 and RHS is 0. That means, our assumption is wrong and x+1 does not divide e(x). That means if an error has odd number of terms it cannot be divided by x+1.

That means, if our r(x) has a factor x+1, it will catch all odd number of errors, which is almost half of total errors.

That means we can have a divisor which can catch all single bit, multi-bit till a typical number of bits and all error containing odd numbers of bits inverted. Quite impressive. Such divisors are found and used in Ethernet (called CRC-32) and other systems and used by many commercial systems.

Summary

In this module, we looked at the data link layer, its characteristics, and process of framing and error handling. We have seen four different methods to frame and we have seen that using a flag byte is a normal method to frame. Both byte stuffing and bit stuffing for stuffing purpose are used with these two methods in practice. The errors occur normally in bursts but sometimes as a single bit error. Handling error at data link layer is not normally preferred in wired network layer but at the wireless network layer. We have concluded with a typical method used by Ethernet to assess if the error has occurred. Ethernet, however, does not report back to the sender about erroneous frame nor demand a retransmission, but just do not pass the erroneous frame up to network layer.

References

1. Computer Networks by Bhushan Trivedi, Oxford University Press
2. Data Communication and Networking, Bhushan Trivedi, Oxford University Press