Monday, 5 June 2017

Data link layer - Framing


Before we discuss framing there is a small prerequisite needed. You should know the structure of the frame. You can read about this here.

How does a frame travel in a network:

Whenever a frame is transmitted by a node in a network, it is very important that the other nodes should know that a frame is travelling in the network. For this very reason, there is an important field in the frame, it's SFD. SFD is called start frame delimiter. SFD is a continuous sequence of 10's, something similar to this sequence 10101011. SFD is present at the start of the frame.

(0+1)*(rest of the frame)

To understand how SFD is used let's consider the following arrangements of the nodes.

A terminal is used to connect a node to the network. Every terminal has a sequential circuit present in it. Whenever a frame passes through the terminal the sequential circuit finds out that, a frame is starting. You might get be curious to know, how it does that?.

Initially, we come up with a regular expression that represents the pattern of the SFD. Now that regular expression is converted to an NFA. This NFA is converted to a DFA using the appropriate algorithms from TOC (you must be knowing the algorithm). And then this DFA is converted to a sequential circuit. So now you know that entire credit of constructing sequential circuits doesn't go to electrical engineers. Software engineers do play some role in this.

Now after understanding how does a sequential circuit detects the start of the frame, next thing is, it should know the end of SFD. For this very reason, every SFD ends with 11. Whenever the sequential circuit sees 11 it comes to know that SFD is about to end and everything after this is useful data.

Now let me explain the entire process briefly. Every station has terminals at its end. These terminals have sequential circuits. Whenever a frame passes the terminal a signal is sent to NIC of the node. The NIC is told that a new frame is passing through the terminal. Check if the frame is for you or not?. Then NIC reads the content of the frame such as the destination address and finds out whether the frame is intended for it or not.

If the frame destination address matches the MAC address of the node it reads the frame and then destroys it. Now having understood the complete outline of framing, let's understand framing in depth.

What is Framing?

Framing is defined as the process of wrapping up the data coming from the network layer and putting it in the data link layer frame. This is an informal definition of framing. Framing is of two types.
  • Fixed length framing
  • Variable length framing
Fixed length framing means that the length of the frame remains same, no matter whatever amount of data is delivered by the network layer. This means, that the data link layer passes a fixed amount of data to the physical layer. On the other hand, variable length framing means that the length of the frame at data link layer is variable. It means the data passed on to physical layer is depending upon the data received from the network layer.

Fixed length framing:

Fixed length is not important and is not used practically. The reason being that it is very inefficient. It was proposed because, with it, it becomes very easy for the stations to find out the end of the frame. Since the frame size is fixed the stations can add the fixed length to the beginning of the SFD to get the end of the frame.


Assume the length of the frame is fixed and is 1000 bytes. Now if we want to send 900 bytes of data we can easily send it as 900 bytes can easily fit in 1000 bytes. And if data is larger than 1000 bytes say 2000 bytes, we can divide it into 2 equal parts of 1000 bytes and send it. But the problem comes in when we don't have enough data to send.
Let's say we have to send 10 bytes of data. We can easily fit in 10 bytes in 1000 bytes of a frame but remaining 990 bytes goes wasted. And you will unnecessarily occupy extra bandwidth in the network. It was because of this major drawback we quit fixed length framing and moved onto variable length framing.

Variable length framing:

Variable length framing is widely used and is the topic of discussion here. Now you might get the doubt that, how are we going find the length of the frame and how will we come to know the end of the frame. To overcome this issue there were two new things introduced in the frame. 
  • The length of the frame: This was introduced to find the total length of the frame.
  • End delimiter: It was introduced to find out the end of the frame.
But there are certain issues with this also. It might happen that our frame gets corrupted and the length might not be correct. In this case, CRC also cannot help us, it is because by the time you read CRC you would have already read the wrong length. This is the reason we have end delimiter. End delimiter can tell us that it's the end of the frame.
Next, it might happen that the End delimiter matches with part of the data. The solution to this problem is to use such characters for data which cannot match with any part of data or which is not very likely to be in the data part. There are two different ways of implementing the concept of end delimiter.
  • Character stuffing or byte stuffing: A character or a byte is stuffed in between the data to unmatch it with end delimiter.
  • Bit stuffing: Instead of inserting a special character or a byte in between the data we use a single bit to unmatch it with end delimiter.

Character stuffing or byte stuffing:

The structure of a frame is shown below -
End delimiter

Let's say our data is 1010001010110100 to send this data with SFD and end delimiter we have the following packet structure.

When a station encounters $ it understands that it's the end of the frame and it should stop reading the frame. But the problem comes in when the data matches with $. 

Till late 1980's this concept worked fine because the data used to be simple mainly characters and digits. But with the advancement in the technology, the types of data sent changed. Now people started sending music, pictures and videos. This caused problems. Till now nothing matched the end delimiter but now data started matching end delimiter.
To overcome this problem people came up with another solution. If data matched with end delimiter, they used to append data with NULL. For example, data is 10110101$00 and end delimiter is $ then we append a null after $ and data sent will be 10110101$'\0'00. When the frame reaches the receiver, it sees null in the data part and understands that the data would have matched ED so sender has appended a NULL. It removes the NULL part and then reads it.
Question- What happens if NULL is to be included in the data. Then we append another null for this NULL. Example: Data = 1010'\0'1 then data sent will be 1010'\0''\0'1. 
But this method was tedious and was soon ruled out after bit stuffing came into the picture.

Bit stuffing:

In this case, instead of using NULL or any other symbol in between the data to unmatch it with ED, we use a single bit. We decide on a fixed end limiter say 01111 and send it with data. Now again there are chances that data might get matched with our ED. To overcome this problem we use bit stuffing.

To understand it more clearly let's take an example. Assume we have some data (011110) to be sent along with ED (01111). Now data will not be sent directly. We try to find out if there is any part of the data that is matching with ED. If we find anything of that kind we try to modify that part of the data.
Considering the above example we can clearly see that data matches with ED. Now to unmatch data with ED we have many choices. But we'll follow a simple technique. Whenever any part of the data matches ED, we insert a '0' just before the last 1 of the ED (011101). In the above case, the first 5-bits matches with ED so while sending the data we insert a '0', just before the last 1. And we get 0111010 as the data.
To make it more clear let's take one more example. Assume data is 01111011110 and ED are 01111. Then the data sent will be 0111010111010.
Now when this data reaches the receiver with the ED it examines the data. The rule at the receiver is whenever it sees 0 followed by 3 1's, it should remove the next bit and then process the data. These rules are prior known to both sender and receiver. In the above case when the data (0111010111010) reaches the receiver, it removes the zeroes from the 5th and 11th position. Finally, data at receiver is 01111011110.
This is the entire concept of framing at data link layer. 

If I missed out something or you have some suggestions, put it in the comments section below. I will be happy to answer your queries. And yes if you found this post useful, please show your support by following the blog. And follow us on facebook and google+.

Thank you.