Eytan ModianoSlide 16.263/16.37: Lecture 2The Data Link Layer: Framing and Error DetectionEytan ModianoMITEytan ModianoSlide 2Data 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 layerEytan ModianoSlide 3Framing _____________________________________ 010100111010100100101010100111000100Where is the DATA??• Three approaches to find frame and idle fill boundaries:1) Character oriented framing2) Length counts- fixed length3) Bit oriented protocols (flags)Eytan ModianoSlide 4Character Based Framing• Standard character codes such as ASCII and EBCDIC contain specialcommunication characters that cannot appear in data• Entire transmission is based on a character codeFrameSYN SYN STX Header Packet ETX CRC SYN SYNSYN is synchronous idleSTX is start textETX is end textEytan ModianoSlide 5Issues 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 messyNOTE: Primary Framing method from 1960 to ~1975Eytan ModianoSlide 6Length 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 nextframe– Receiver looks at the respective length field in the next packet header to findthat 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– Resynchronization is needed after an error in the length countEytan ModianoSlide 7Fixed 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 ratesEytan ModianoSlide 8Bit 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 beprevented 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 ModianoSlide 91 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 00 0 0 0Stuffed bitsOriginal frameBIT STUFFING (Transmitter)• Used to remove flag from original data• A 0 is stuffed after each consecutive five 1's in the original frame• Why is it necessary to stuff a 0 in 0111110?– If not, then0111110111 -> 0111110111011111111 -> 0111110111– How do you differentiate at the receiver?Eytan ModianoSlide 10DESTUFFING (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 below1001111101100111011111011001111110flagEytan ModianoSlide 11Overhead• In general with a flag 01K0 the bit stuffing is require whenever 01k-1appears in the original data stream• For a packet of length L this will happen about L/2k timesE{OH} = L/ 2k + (k+ 2) bits• For 8 bit flag OH ~ 8 + L/64– For large packets efficiency ~ 1 - 1/64 = 98.5 (or 1.5% overhead)• Optimal flag length– If packets are long want longer flag (less stuffing)– If packets are short want short flag (reduce overhead due to flag)Kopt ~ log2(L)Eytan ModianoSlide 12Framing Errors• All framing techniques are sensitive to errors– An error in a length count field causes the frame to be terminated at thewrong point (and makes it tricky to find the beginning of the next frame)– An error in DLE, STX, or ETX causes the same problems– An error in a flag, or a flag created by an error causes a frame to disappearor an extra frame to appear• Flag approach is least sensitive to errors because a flag will eventuallyappear again to indicate the end of a next packet– Only thing that happens is that an erroneous packet was created– This erroneous packet can be removed through an error detection techniqueEytan ModianoSlide 13Error detection techniques• Used by the receiver to determine if a packet contains errors• If a packet is found to contain errors the receiver requests the transmitterto re-send the packet• Error detection techniques– Parity check single bit Horizontal and vertical redundancy check– Cyclic redundancy check (CRC)Eytan ModianoSlide 14Effectiveness of error detection technique• Effectiveness of a code for error detection is usually measured by threeparameters: 1) minimum distance of code (d) (min # bit errors undetected)The minimum distance of a code is the smallest number of errors that can mapone codeword onto another. If fewer than d errors occur they will alwaysdetected. Even more than d errors will often be detected (but not always!)2) burst detecting ability (B) (max burst length always detected)3) probability of random bit pattern mistaken as error free (good estimate if# errors in a frame >> d or B)– Useful when framing is lost– K info bits => 2k valid codewords– With r check bits the probability that a random string of length k+r mapsonto one of the 2k valid codewords is 2k/2k+r = 2-rEytan ModianoSlide 15Parity check codes• Each parity check is a modulo 2 sum of some of the data bits Example: c1 = x1 + x2 + x3c2 = x2 + x3 + x4c3 = x1 + x2 + x4k Data bits r Check bitsEytan ModianoSlide 16Single Parity Check Code• The check bit is 1 if frame contains odd number of 1's; otherwise it is 01011011 -> 1011011 11100110 -> 1100110 0• Thus, encoded frame contains even number of 1's• Receiver counts number of ones in frame– An even number of 1’s is interpreted as no errors– An odd number of 1’s means that an error must have occured A single error (or an odd number of