1 Discussion #8 HDLC Framing Error Detection ARQ2 Layer 2 – The Data Link Layer n We are now going into more of a study of Layer 2 in the OSI layered architecture n We’ve talked about different kinds of Physical Layers n At this point we have a physical connection n How do we start sending data? PhysicalData Link3 Framing n Problem: Breaking sequence of bits into a frame n Must determine first and last bit of the frame n Typically implemented by network adaptors n Adaptor fetches (deposits) frames out of (into) host memory4 Framing (continued)5 n On synchronous links, bit stuffing is used to guarantee, NO sequence of binary data appears to be a frame delimiter. n The sending device ensures that any sequence of 5 contiguous 1-bits is automatically followed by a 0-bit. n A simple digital circuit inserts a 0-bit after 5 1-bits. n 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. n 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. Bit Stuffing6 Example – Bit Stuffing7 Error Detection and Correction Using FCS 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. n The sender computes a checksum on the entire frame and sends this along. n The receiver computes the checksum on the frame using the same algorithm, and compares it to the received FCS. n It can then detect whether any data was lost or altered in transit, discard the data, and request retransmission of the corrupted frame. n FCS is used in Ethernet, X.25, HDLC, Frame Relay, and other data link layer protocols. n A cyclic redundancy check (CRC) is often used to compute the FCS. An Ethernet frame including the FCS terminating the frame8 Cyclic Redundancy Check n Add K redundancy bits to N bits of data n K << N n e.g.: Ethernet Frame 12,000 bits – 32 bits Redundancy n Add k bits of redundant data to an n-bit message. n 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=39 CRC - Continued n Instead of sending M(x), Transmit polynomial P(x) that is evenly divisible by G(x) n Receive polynomial P(x) + E(x) n If E(x)=0, it implies no bit errors happened. n 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). n Must choose G(x) to make the second case extremely rare.10 n Sender wants to transmit MSG=10011010 MSG=10011010 , n=8 corresponds to M(x) = x 7+ x 4 + x 3 + x 1 Divisor=1101 , k=3 corresponds to G(x) = x 3+ x 2 + 1 n Multiply M(x) by x k In this example, we get: M(x).x 3 = x 10 + x 7 + x 6 + x 4 =10011010000 n Divide result by G(x) =1101 (Subtraction or addition is XOR in polynomial arithmetic) The remainder is E(x) = x 2 +1 = 101 n 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 Sender: Example11 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 Division12 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 + x5 + x4 x7 + x6 + x4 x6 + x5 x6 + x5 + x3 x3 x3 + x2 + 1 x2 + 1 Remainder = 10113 Receiver n Divides the Received Polynomial by G(X) n If the remainder is zero – No errors n If not zero - Discard! n What Kind of errors can we check? n It depends on G(X)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”. 14Solution n A -> B: Propagation time = 4000 x 5 µsec = 20 msec Transmission time per frame = 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 10msec1010010003=×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. 16Solution 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