Flag bit with bit stuffing Framing
Flag bits with bit stuffing is a bit-oriented approach of framing and therefore data to be carried is considered as a sequence of bits. In Flag bits with bit stuffing a special 8-bit flag is used to define the beginning and end of the frame. The special 8-bit pattern is 01111110.
Let’s understand this method of framing with an example. Suppose the data link layer receives a bit stream 1011 1011 1010 from the network layer.
The data link layer first encapsulates this data into the frame by adding a header and trailer. The header contains the address of the source and destination, and the trailer carries error detection and correction bits.
In this method of framing a special pattern of bits i.e., 01111110 is added at the beginning and at the end of the data frame. When this frame arrives at the receiver’s data link layer. The data link layer will very correctly detect the beginning and end of this frame; because when the first bit sequence 01111110 occurs, it will be considered as the beginning of the frame and when another bit sequence 01111110 occurs, it will be considered as the end of the frame.
In bit stuffing framing, a special pattern of bits i.e., 01111110 is added at the beginning and at the end of the data frame. When this frame arrives at the receiver’s data link layer. The data link layer will very correctly detect the beginning and end of this frame; because when the first bit sequence 01111110 occurs, it will be considered as the beginning of the frame and when another bit sequence 01111110 occurs, it will be considered as the end of the frame.
What if 01111110 occurs in data?
The 8-bit sequence 01111110 is chosen such that it might not be present in the data part or message part while text encoding. But when this protocol is used for transmitting audio files and video files, there is always the possibility that this pattern of bits might be present in the data part. In this case, there will be a conflict on the receiver side. The receiver will not be able to understand whether this bit sequence (01111110) which is present in the data part is indicating some beginning or end of the frame or it is data.
Let me explain this with an example. Suppose the data to be sent including header and trailer is 010010111111010010; while framing using the bit stuffing method data link layer will add 01111110 as the start indicator and end indicator.
It is important to understand that the receivers’ data link layer is always looking for an 8-bit flag pattern. When the flag pattern occurs, the first 8-bit flag is considered the beginning of the frame. The data link layer knows whatever follow-up to another 8-bit flat pattern must be data or a message. But in this example, there is a bit sequence like the flag bit sequence in the data. The data link layer considers this as the end of the frame. Here data link layer loses the frame synchronization. (The bit sequence is considered as the end of the frame where it is not.) When the flag pattern occurs, which indicates the end of the frame; will be considered as the start of another frame.
Bit Stuffing mechanism
To overcome this problem bit stuffing mechanism is used. In the bit stuffing method, an extra zero is inserted in any pattern of bits that is beginning to look like a flag. The flag bits chosen to be used as a frame delimiter are 01111110. (Zero followed by 6 consecutive ones followed by zero) In this method, the data link layer must make sure that it will never send 6 consecutive ones. It is done by inserting an extra zero after 5 consecutive ones. Therefore, there will never be 6 consecutive ones in the frame body and hence flag pattern will never occur in the data part.
Let me explain this with an example, suppose the data to be sent including header and trailer is 0100010111111010010. To Frame, 01111110 is inserted at the beginning to indicate the start of the frame, and the same pattern 01111110 is inserted at the end of the frame.
In this example, there are six consecutive 1’s in the data. In the bit stuffing mechanism an extra ‘0’ is inserted after 5 consecutive ones and then this frame is transmitted.
At the receiver’s end, first 8-bit flag pattern will be considered as beginning of the frame and whatever follows after that up to next 8 bit flag will be considered as data or frame body. The extra ‘0’ which was stuffed in by sender will be removed from the data part.
To summarize, in flag bits with bit stuffing mechanism when there are 6 consecutive ones in the frame body an extra ‘0’ is always stuffed in or inserted after 5 consecutive ones. Regardless of what follows 5 consecutive ones (After these 5 consecutive ones there may be zero or one) an extra ‘0’ is stuffed in by sender. Receiver will always destuffs or removes an extra ‘0’, which is followed by 5 consecutive ones in the data part.
