FRAMING

• Framing in the data link layer separates a message from one source to a destination, or from other messages to other destinations, by adding a sender address and a destination address.

• The destination address defines where the packet is to go; the sender address helps the recipient acknowledge the receipt.

Fixed-Size Framing

• Frames can be of fixed or variable size. In fixed-size framing, there is no need for defining the boundaries of the frames; the size itself can be used as a delimiter.

• An example of this type of framing is the ATM wide-area network, which uses frames of fixed size called cells.

Variable-Size Framing

• In variable-size framing, we need a way to define the end of the frame and the beginning of the next.

• Historically, two approaches were used for this purpose: a character-oriented approach and a bit-oriented approach.

Character-Oriented Protocols

• Character-oriented framing was popular when only text was exchanged by the data link layers. The flag could be selected to be any character not used for text communication.

• Now, however, we send other types of information such as graphs, audio, and video.

• Any pattern used for the flag could also be part of the information. If this happens,the receiver, when it encounters this pattern in the middle of the data, thinks it has reached the end of the frame. To fix this problem, a byte-stuffing strategy was added to character-oriented framing.

• In byte stuffing (or character stuffing), a special byte is added to the data section of the frame when there is a character with the same pattern as the flag. The data section is stuffed with an extra byte. This byte is usually called theescape character (ESC), which has a predefined bit pattern.

• Whenever the receiver encounters the ESC character, it removes it from the data section and treats the next character as data, not a delimiting flag.

• Byte stuffing by the escape character allows the presence of the flag in the data section of the frame, but it creates another problem.

• What happens if the text contains one or more escape characters followed by a flag?

• The receiver removes the escape character, but keeps the flag, which is incorrectly interpreted as the end of the frame.

• To solve this problem, the escape characters that are part of the text must also be marked by another escape character.

• In other words, if the escape character is part of the text, an extra one is added to show that the second one is part of the text. Figure shows the situation.

Bit-Oriented Protocols

• In a bit-oriented protocol, the data section of a frame is a sequence of bits to be interpreted by the upper layer as text, graphic, audio, video, and so on.

As shown in Figure

• This flag can create the same type of problem we saw in the byte-oriented protocols.

• That is, if the flag pattern appears in the data, we need to somehow inform the receiver that this is not the end of the frame. We do this by stuffing 1 single bit (instead of I byte) to prevent the pattern from looking like a flag. The strategy is called bit stuffing.

• In bit stuffing, if a 0 and five consecutive I bits are encountered, an extra 0 is added.

• This extra stuffed bit is eventually removed from the data by the receiver.

• Note that the extra bit is added after one 0 followed by five 1s regardless of the value of the next bit.

• This guarantees that the flag field sequence does not inadvertently appear in the frame.

Flow Control

• Flow control coordinates the amount of data that can be sent before receiving an acknowledgment and is one of the most important duties of the data link layer.

• In most protocols, flow control is a set of procedures that tells the sender how much data it can transmit before it must wait for an acknowledgment from the receiver.

• The flow of data must not be allowed to overwhelm the receiver. Any receiving device has a limited speed at which it can process incoming data and a limited amount of memory in which to store incoming data.

• The receiving device must be able to inform the sending device before those limits are reached and to request that the transmitting device send fewer frames or stop temporarily.

• Incoming data must be checked and processed before they can be used. The rate of such processing is often slower than the rate of transmission. For this reason, each receiving device has a block of memory, called a buffer, reserved for storing incoming data until they are processed.

• If the buffer begins to fill up, the receiver must be able to tell the sender to halt transmission until it is once again able to receive.

Error Control

• Error control is both error detection and error correction. It allows the receiver to inform the sender of any frames lost or damaged in transmission and coordinates the retransmission of those frames by the sender.

• In the data link layer, the term error control refers primarily to methods of error detection and retransmission.

• Error control in the data link layer is often implemented simply: Any time an error is detected in an exchange, specified frames are retransmitted.

• This process is called automatic repeat request (ARQ).