Computer Networks - Lecture 9

Data Link Layer and error Control

•Objective:
—Achieving reliable communication between two adjacent machines
•Design Issues:
—Framing: data are sent in blocks called frames, the beginning and end of each frame must be recognized by the receiver.
—Error control: bit errors introduced by the transmission system should be detected and/or corrected.
—Flow control: the sending station must not send frames at a rate faster than 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.
—Transmit control information and data on the same line



Framing

Frame Structure

Single frame format for all data and control exchanges


•Flag: delimit frame at both ends
•Address: identify the frame receiver
•Control: specify different frame types
•FCS: frame check sequence (error detecting code)


•Large block of data may be broken up into small frames at the source because:
—limited buffer size at the receiver
—A larger block of data has higher probability of error

•With smaller frames, errors are detected sooner, and only a smaller amount of data needs to be retransmitted
—On a shared medium, such as Ethernet and Wireless LAN, small frame size can prevent one station from occupying medium for long periods
•Need to indicate the start and end of a block of data
•Use preamble (e.g., flag byte) and postamble
•If the receiver ever loses synchronization, it can just search for the flag byte.
•Frame: preamble + control info + data + postamble
•Problem: it is possible that the flag byte’s bit pattern occur in the data
•Two popular solutions:
—Byte stuffing
•The sender inserts a special byte (e.g., ESC) just before each “accidental” flag byte in the data (like in C language, “ is replaced with \”).
•The receiver’s link layer removes this special byte before the data are given to the network layer.
—Bit stuffing: each frame starts with a flag byte “01111110”.
•Whenever the sender encounters five consecutive 1s in the data, it automatically stuffs a 0 bit into the outgoing bit stream.
•When the receiver sees five consecutive incoming 1 bits, followed by a 0 bit, it automatically deletes the 0 bit.
—character count
•use a field in the header to indicate the number of characters in the frame
•e.g. 51234 56789 80123456
•unreliable and rarely used
—starting & ending characters, with character stuffing
•STX and ETX are used for frame synchronization
•DLE and DLE insertion are used for data transparency
—starting & ending characters/flags, with bit stuffing
•01111110 as flag byte (flag pattern) for frame and character sync. (for beginning and end)
•zero bit insertion (bit stuffing) to achieve data transparency -- to insert a 0 after 5 contiguous 1’s
•e.g. original data 011011111111111111110010
data sent 011011111011111011111010010
data stored 011011111111111111110010