Lecture 2 6.263/1637 The Data Link Layer: Framing and Error Detection Eytan Modiano MIT LIDS
Lecture 2 6.263/16.37 The Data Link Layer: Framing and Error Detection Eytan Modiano MIT, LIDS Eytan Modiano Slide 1
Data Link Layer (DLC) Responsible for reliable transmission of packets over a link Framing: Determine the start and end of packets(sec 2.5) Error Detection: Determine when a packet contains errors ( sec 2.3) Error recovery: Retransmission of packets containing errors(sec 2. 4) DLC layer recovery May be done at higher layer
Data Link Layer (DLC) • Responsible for reliable transmission of packets over a link – Framing: Determine t he star t and end of packets (sec 2.5) – Error Detection: Determine w hen a packet contains errors (sec 2.3) – Error recovery: Retransmissio n of packets containing errors (sec 2..4) DLC lay er recovery May be done at higher lay er Eytan Modiano Slide 2
Framing 010100111010100100101010100111000100 Where is the data?? Three approaches to find frame and idle fill boundaries 1)Character oriented framing 2)Length counts fixed length 3)Bit oriented protocols( flags)
Framing _____________________________________ 010100111010100100101010100111000100 Where is the DATA?? • Three approaches to find frame and idle fill boundaries: 1) Character oriented framing 2) Length counts - fixed length 3) Bit oriented protocols (flags) Eytan Modiano Slide 3
Character Based Framing Frame SYNSYN STX Header Packet ETX CRC SYN SYN SYN is synchronous idle STX is start text ETX is end text Standard character codes such as ascll and ebcDic contain special communication characters that cannot appear in data Entire transmission is based on a character code
Character Based Framing Frame SYN SYN STX Header Packet ETX CRC SYN SYN SYN is synchronous idle STX i s start text ETX is end text • Standard character codes such as ASCII and EBCDIC contain special communication characters that cannot appear in data • Entire transmission is based on a character code Eytan Modiano Slide 4
Issues with Character Based Framing Character code dependent How do you send binary data? Frames must be integer number of characters Errors in control characters are messy NOTE: Primary Framing method from 1960 to-1975
Issues With Character Based Framing • Character code dependent – How do you send binary data? • Frames must be integer number of characters • Errors in control characters are messy NOTE: Primary Framing method from 1960 to ~1975 Eytan Modiano Slide 5
Length field approach(DECNET) Use a header field to give the length of the frame(in bits or bytes) Receiver can count until the end of the frame to find the start of the next frame Receiver looks at the respective length field in the next packet header to find that packet's length Length field must be log,(Max_Size_Packet)+ 1 bits long This restricts the packet size to be used Issues with length counts Difficult to recover from errors Resynchronization is needed after an error in the length count
Length field approach (DECNET) • Use a header field to give the length of the frame (in bits or bytes) – Rec eiver can count until the end of the frame to find the start of the next frame – Receiver looks at the respective length field in the next packet header to find t hat packet’s length • Length field must be log2 (Max_Size_Packet) + 1 bits long – This restricts the packet size to be used • Issues with length counts – Difficult to recover from errors – Res ynchronization is neede d after an error in the length count Eytan Modiano Slide 6
Fixed Length Packets(e.g, ATM) All packets are of the same size In ATM networks all packets are 53 Bytes Requires synchronization upon initialization Issues. Message lengths are not multiples of packet size Last packet of a message must contain idle fill(efficiency) Synchronization issues Fragmentation and re-assembly is complicated at high rates
Fixed Length Packets (e.g., ATM) • All packets are of the same size – In ATM networks all packets are 53 Bytes • Requires synchronization upon initialization • Issues: – Message lengths are not multiples of packet size Last packet of a message must contain idle fill (efficiency) – Synchronization issues – Fragmentation and re-assembly is complicated at high rates Eytan Modiano Slide 7
Bit Oriented Framing( Flags) a flag is some fixed string of bits to indicate the start and end of a packet a single flag can be used to indicate both the start and the end of a packet In principle, any string could be used, but appearance of flag must be prevented somehow in data Standard protocols use the 8-bit string 01111110 as a flag Use 01111111..1110(<16 bits) as abort under error conditions Constant flags or 1's is considered an idle state Thus 0111111 is the actual bit string that must not appear in data INVENTED- 1970 by IBM for SDLC (synchronous data link protocol)
Bit Oriented Framing (Flags) • A flag is some fixed string of bits to indicate the start and end of a packet – A single flag can be used to indicate both the start and the end of a packet • In principle, any string could be used, but appearance of flag must be prevented somehow in data – Standard protocols use the 8-bit string 01111110 as a flag – Use 01111111..1110 ( <16 bits) as abort under error conditions – Constant flags or 1's is considered an idle state • Thus 0111111 is the actual bit string that must not appear in data • INVENTED ~ 1970 by IBM for SDLC (synchronous data link protocol) Eytan Modiano Slide 8
BIT STUFFING (Transmitter) Used to remove flag from original data A0 is stuffed after each consecutive five 1's in the original frame Stuffed bits 111191011191114011110 Original frame Why is it necessary to stuff a o in 0111110? If not. then 111110111 0111110111 011111111 →0111110111 How do you differentiate at the receiver?
BIT STUFFING (Transmitter) • Used to remove flag from original data • A 0 is stuffed after each consecutive five 1's in the original frame Stuffed bits 0 0 0 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 Original frame • Why is it necessary to stuff a 0 in 0111110? – If not, then 0111110111 -> 0111110111 011111111 -> 0111110111 – How do you differentiate at the receiver? Eytan Modiano Slide 9
DESTUFFING(Receiver) If o is preceded by 011111 in bit stream remove it If o is preceded by 0111111, it is the final bit of the flag Example: Bits to be removed are underlined below 1001111101100111011111011001111110 flag
DESTUFFING (Receiver) • If 0 is preceded by 011111 in bit stream, remove it • If 0 is preceded by 0111111, it is the final bit of the flag. Example: Bits to be removed are underlined below 1001111101100111011111011001111110 flag Eytan Modiano Slide 10