Discussion 8 HDLC Framing Error Detection ARQ 1 Layer 2 The Data Link Layer n Data Link n Physical n n We are now going into more of a study of Layer 2 in the OSI layered architecture We ve talked about different kinds of Physical Layers At this point we have a physical connection How do we start sending data 2 Framing n n n n Problem Breaking sequence of bits into a frame Must determine first and last bit of the frame Typically implemented by network adaptors Adaptor fetches deposits frames out of into host memory 3 Framing continued 4 Bit Stuffing n On synchronous links bit stuffing is used to guarantee NO sequence of binary data appears to be a frame delimiter n n n n The sending device ensures that any sequence of 5 contiguous 1 bits is automatically followed by a 0 bit A simple digital circuit inserts a 0 bit after 5 1 bits The receiving device knows this is being done and will automatically strip out the extra 0 bits At the receiver n Should five consecutive 1s arrive look at next bit s n If next bit is a 0 remove it n If next bits are 10 end of frame marker n If next bits are 11 error n So if a flag is received it will have 6 contiguous 1 bits Assuming NRZI encoding it also provides a minimum of one transition per 6 bit times so the receiver can stay in sync with the transmitter 5 Example Bit Stuffing 6 Error Detection and Correction Using FCS n n n n n n Frame Check Sequence FCS refers to the redundant information Extra Checksum Characters added to a Frame in a communication protocol for error detection and correction The sender computes a checksum on the entire frame and sends this along The receiver computes the checksum on the frame using the same algorithm and compares it to the received FCS It can then detect whether any data was lost or altered in transit discard the data and request retransmission of the corrupted frame FCS is used in Ethernet X 25 HDLC Frame Relay and other data link layer protocols A cyclic redundancy check CRC is often used to compute the FCS An Ethernet frame including the FCS terminating the frame 7 Cyclic Redundancy Check n Add K redundancy bits to N bits of data n n n n K N e g Ethernet Frame 12 000 bits 32 bits Redundancy Add k bits of redundant data to an n bit message Represent n bit message as an n 1 degree polynomial e g MSG 10011010 corresponds to M x x 7 x 4 x 3 x 1 n 8 n Let k be the degree of some divisor polynomial G x e g G x x 3 x 2 1 corresponds to 1101 K 3 8 CRC Continued n n n n n Instead of sending M x Transmit polynomial P x that is evenly divisible by G x Receive polynomial P x E x If E x 0 it implies no bit errors happened Recipient divides P x E x by G x the remainder will be zero only in two cases n Either E x was zero i e there was no error n Or E x is exactly divisible by G x Must choose G x to make the second case extremely rare 9 Sender Example n Sender wants to transmit MSG 10011010 MSG 10011010 n 8 Divisor 1101 k 3 n n n corresponds to corresponds to M x x 7 x 4 x 3 x G x x 3 x 2 1 1 Multiply M x by x k In this example we get M x x 3 x 10 x 7 x 6 x 4 10011010000 Divide result by G x 1101 Subtraction or addition is XOR in polynomial arithmetic The remainder is E x x 2 1 101 Send P x M x x k E x which is exactly divisible by G x i e Send 10011010000 101 10011010101 since this is exactly divisible by G x 1101 10 Division 10011010000 x10 x7 x6 x4 1101 x3 x2 1 11111001 1101 10011010000 1101 1001 1101 1000 1101 1011 1101 1100 1101 1000 1101 101 Remainder x2 1 11 Example of CRC checking n Do the same example in Polynomial 10011010000 x10 x7 x6 x4 1101 x3 x2 1 x7 x6 x5 x4 x3 1 Quotient 11111001 x3 x2 1 x10 x7 x6 x4 x10 x9 x7 x9 x6 x4 x9 x8 x6 x8 x4 x8 x7 x5 x7 x 5 x7 x6 x6 x6 x4 x4 x5 x5 x3 x3 x3 x2 1 x2 1 Remainder 101 12 Receiver n Divides the Received Polynomial by G X n n n n If the remainder is zero No errors If not zero Discard What Kind of errors can we check It depends on G X 13 Data Link Control Exercise n Frames are generated at node A and sent to node C through node B Determine the minimum data rate on the link connecting nodes B and C so that the buffer at node B does not overflow The following is given n Data Rate on link A B is 100 Kbps n Propagation delay is 5 sec km on both links n Links are FDX n Data Frames are 1000 bits long ACK frames are of negligible length n Link A B is 4000 Km Link B C is 1000 Km n A can transmit 3 frames to B before it has to stop and wait for ACK from B While B can transmit ONLY one frame to C before it has to stop and wait for ACK from C 14 Solution n A B Propagation time 4000 x 5 sec 20 msec Transmission time per frame 1000 3 10msec 100 10 n B C Propagation time 1000 x 5 sec 5 msec Transmission time per frame x 1000 R R data rate between B and C unknown 15 Solution Continued n A can transmit three frames to B and then must wait for the acknowledgment of the first frame before transmitting additional frames The first frame takes 10 msec to transmit the last bit of the first frame arrives at B 20 msec after it was transmitted and therefore 30 msec after the frame transmission began It will take an additional 20 msec for B s acknowledgment to return to A Thus A can transmit 3 frames in 50 msec 16 Solution Continued n B can transmit one frame to C at a time It takes 5 x msec for the frame to be received at C and an additional 5 msec for C s acknowledgment to return to B Thus B can transmit one frame every 10 x msec or 3 frames every 30 3x msec Thus 30 3x 50 x 6 66 msec R 1000 x 150 kbps 17