Data Link Layer Concepts - PDF Document

1502346 - Computer Communications and Networks Dr. Mohamed Saad Department of Computer Engineering University of Sharjah [email protected] Chapter 3: The Data Link Layer ...

1502346 - Computer Communications and Networks Dr. Mohamed Saad Department of Computer Engineering University of Sharjah [email protected] Chapter 3: The Data Link Layer  M. Saad The Data Link Layer The main task of the data link layer is to transform a raw transmission facility into a virtual communication channel for sending frames error-free. Main design issues of the data link layer: – Framing (breaking the received bit stream into discrete frames) – Error detection and correction – Flow control (controlling the transmission rate to avoid overwhelming a slow receiver by a fast transmitter) 1502346 - Computer Communications & Networks 1  M. Saad Virtual vs. Actual Communication Host 1 Host 2 Host 1 Host 2 4 4 4 4 3 3 3 3 Virtual data path 2 2 2 2 1 1 1 1 Actual data path (a) (b) 1502346 - Computer Communications & Networks 2  M. Saad Framing Frame and packet: Sending machine Receiving machine Packet Packet Frame Header Payload field Trailer Header Payload field Trailer Framing methods: 1. Character count 2. Flag bytes with byte stuffing 3. Start & End flags, with bit stuffing 1502346 - Computer Communications & Networks 3  M. Saad Character Count A field in the header is used to specify the number of characters in the frame. When the data link layer at the destination sees he character count, it knows how many characters follow and where the end of the frame is. Character count One character (a) 5 1 2 3 4 5 6 7 8 9 8 0 1 2 3 4 5 6 8 7 8 9 0 1 2 3 Frame 1 Frame 2 Frame 3 Frame 4 5 characters 5 characters 8 characters 8 characters Error (b) 5 1 2 3 4 7 6 7 8 9 8 0 1 2 3 4 5 6 8 7 8 9 0 1 2 3 Frame 1 Frame 2 Now a (Wrong) character count Problem: character count can be changed by a transmission error → the destination will be unable to locate the start of the next frame ⇒ character count is rarely used. 1502346 - Computer Communications & Networks 4  M. Saad Flag Bytes with Byte Stuffing Each frame starts and ends with special flag bytes (FLAG). Most protocols in recent years mark the start and the end of a frame with the same FLAG byte. FLAG Header Payload field Trailer FLAG (a) Original characters After stuffing A FLAG B A ESC FLAG B A ESC B A ESC ESC B A ESC FLAG B A ESC ESC ESC FLAG B A ESC ESC B A ESC ESC ESC ESC B (b) Two consecutive FLAG’s indicate the end of a frame and the start of a new frame. 1502346 - Computer Communications & Networks 5  M. Saad Flag Bytes with Byte Stuffing (contd.) Problem: the FLAG’s bit pattern may occur in the data. Possible solution: byte stuffing or character stuffing – Sender’s data link layer inserts a special escape byte (ESC) before each ”accidental” flag byte in the data. – Receiver’s data link layer removes ESC (and understands that the FLAG that follows is part of the data) before passing the data to the network layer. – ⇒ single FLAG is for framing; FLAG with ESC (before it) is part of the data. Same stuffing of ESC byte if ESC itself occurs in the data. – ⇒ single ESC is an escape sequence, double ESC indicates that the second ESC is part of the data. Disadvantage: closely tied to using 8-byte characters. 1502346 - Computer Communications & Networks 6  M. Saad Starting and Ending Flags with Bit Stuffing Allows character codes with arbitrary number of bits per character. Each frame starts and ends with the special pattern 01111110. Bit stuffing: – Sender: if 5 consecutive 1s in the data, automatically stuff a 0 in the outgoing data stream. – Receiver: if 5 consecutive 1s followed by a 0 is seen, automatically delete the 0. 1502346 - Computer Communications & Networks 7  M. Saad Bit Stuffing Example (a) 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 (b) 0 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 0 0 1 0 Stuffed bits (c) 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 (a) original data, (b) sender’s data after bit stuffing, (c) receiver’s recovered data after bit destuffing (deleting) 1502346 - Computer Communications & Networks 8  M. Saad Error Control Error control can be classified into 2 broad categories: 1. Forward Error Correction (FEC): Enough redundant information is added to the data to enable the receiver to correct any errors and recover the original transmitted data on its own. This strategy uses error-correcting codes. 2. Automatic Repeat Request (ARQ): Only enough redundant information is added to the data to allow the receiver to detect that some errors occurred (without locating or correcting them). The receiver would then request a re-transmission. This strategy uses error-detecting codes. 1502346 - Computer Communications & Networks 9  M. Saad Error-Correcting Codes Based on adding redundant bits to a data bit stream. Let the number of data bits be m ⇒ number of legal codewords (messages) is 2m. Let the number of added check (redundant) bits be r. Let the total length of the codeword be n, i.e., m + r = n ⇒ total number of possible codewords is 2n, where only 2m of them are legal. 1502346 - Computer Communications & Networks 10  M. Saad Important Definitions Hamming distance between 2 codewords: number of bits the two codewords differ. Can be computed by an X-OR operation Example: 10001001 and 10110001 have a Hamming distance of 3. Hamming distance of a code: the distance between the 2 codewords whose Hamming distance is minimum. Example: the code {0000000000, 0000011111, 1111100000, 1111111111} has a hamming distance of 5. 1502346 - Computer Communications & Networks 11  M. Saad Error Correction and Detection Capability of Codes Error will NOT be detected if it converts a valid codeword into another valid codeword. (In the previous code, 5 errors cannot be detected because they may convert a valid codeword into another valid codeword) ⇒ to detect d errors you need a distance d + 1 code (When the receiver sees an invalid codeword it can tell that errors occurred). Example: code {0000000000, 0000011111, 1111100000, 1111111111} can detect 4 errors. To correct d errors you need a distance 2d + 1 code. This is because the valid (legal) codewords are so far apart that even with d changes, the original codeword is still closer than any other codeword, so it can be uniquely determined. Note: if a frame is transmitted and d errors occurred during transmission, the received frame and the transmitted frame will have a Hamming distance d. Note: If the receiver receives an invalid codeword, it chooses the closest (with respect to Hamming distance) valid codeword. 1502346 - Computer Communications & Networks 12  M. Saad The Hamming Code The bits of the codeword are numbered 1, 2, 3,... The bits that are powers of 2 (1, 2, 4, 8, 16,...) are check bits. The rest (3, 5, 6, 7, 9, 10, 11, 12,...) are filled up with the m data bits. Each check bit forces the parity of some collection of bits, including itself to be even (or odd). To see which check bits the data bit in position k contributes to, rewrite k as a sum of powers of 2. Example: 11 = 1 + 2 + 8 ⇒ data bit 11 contributes to the computation of check bits 1,2 and 8. EXAMPLE: 1502346 - Computer Communications & Networks 13  M. Saad The Hamming Code (contd.) 7-bit ASCII characters encoded as 11-bit codewords using a Hamming code. Char. ASCII Check bits H 1001000 00110010000 a 1100001 10111001001 m 1101101 11101010101 m 1101101 11101010101 i 1101001 01101011001 n 1101110 01101010110 g 1100111 01111001111 0100000 10011000000 c 1100011 11111000011 o 1101111 10101011111 d 1100100 11111001100 e 1100101 00111000101 Order of bit transmission 1502346 - Computer Communications & Networks 14  M. Saad Decoding Receiver examines each check bit, to see if it has correct parity. If all check bits have correct parity ⇒ codeword has no errors. The sum of the check bit positions having incorrect parity gives the position of the incorrect bit. Example: check bits 1, 2 and 8 are incorrect ⇒ bit 11 is inverted (because it is the only data bit checked by 1, 2 and 8). 1502346 - Computer Communications & Networks 15  M. Saad Error Detecting Codes Error-correcting codes are useful on communication channels with a high error rate, e.g., wireless channels. When the error rate is much lower, e.g., on copper wires or fiber-optic links, using error detection and retransmission is usually more efficient. We will consider an error-detecting code that is widely used in practice → Cyclic Redundancy Check (CRC) codes. 1502346 - Computer Communications & Networks 16  M. Saad Cyclic Redundancy Check (CRC) Codes A k-bit frame is regarded as a polynomial with k terms, and of order k − 1. Example: 110001 is regarded as the polynomial M (x) = x5 + x4 + 0 · x3 + 0 · x2 + 0 · x1 + x0 = x5 + x4 + 1. Sender and receiver agree upon a generator polynomial G(x). Let r be the order of G(x), then r will be also the number of check bits appended to the data bits. The most significant, and least significant terms of the generator polynomial must be non-zero (generator starts with 1 and ends with 1). Example generator polynomial of degree 4: G(x) = x4 + x + 1. Sender uses G(x) to compute the r check bits and appends them to the data bits. Receiver uses G(x) to detect any errors. 1502346 - Computer Communications & Networks 17  M. Saad Sender Algorithm 1. Let r be the degree of G(x). Append r zeros to the low-order end of the frame, so it now contains m + r bits (last r bits zeros) so it now corresponds to xr M (x). 2. Divide the bit string corresponding to xr M (x) by the bit string corresponding to G(x) using long division. Note: all operations are modulo 2 → addition and substraction are X-OR operations. 3. Subtract (modulo 2) the remainder of the long division from the bit string corresponding to xr M (x). Call the resulting polynomial T (x), and its corresponding bit string is the transmitted frame. Note: remainder of long division is of length r bits or fewer. If fewer than r bits, add zeros to the left to make it r bits. Step 3 is equivalent to replacing the zeros (added in Step 1) by the remainder (obtained in Step 2). Note: the resulting polynomial T (x) is divisible by G(x) with no remainder! 1502346 - Computer Communications & Networks 18  M. Saad Frame : 1101011011 Example Generator: 1 0 0 1 1 Message after 4 zero bits are appended: 1 1 0 1 0 1 1 0 1 1 0 0 0 0 1 1 0 0 0 0 1 0 1 0 10011 1 1 0 1 0 1 1 0 1 1 0 0 0 0 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 1 1 0 1 0 0 1 1 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 1 0 0 1 1 0 1 1 1 0 0 0 0 0 0 Remainder 1 1 1 0 Transmitted frame: 1 1 0 1 0 1 1 0 1 1 1 1 1 0 1502346 - Computer Communications & Networks 19  M. Saad Receiver Algorithm 1. Receiver will receive the bit string corresponding to T (x) with possible errors. 2. Divide received bit string by the bit string corresponding to G(x). 3. If remainder = 0, no errors. If remainder 6= 0, errors occurred. Error-detection capability depends on the choice of G(x). One of the standard polynomials used in Ethernet (e.g., IEEE 802 standard): G(x) = x32 +x26 +x23 +x22 +x16 +x12 +x11 +x10 +x8 +x7 +x5 +x4 +x2 +x1 +1 G(x) above can detect all bursts of errors of length 32 bits or less, and all bursts of odd number of errors. 1502346 - Computer Communications & Networks 20  M. Saad Retransmission Strategies If the receiver detects an error (by means of some error-detecting code, e.g., Cyclic Redundancy Check), the frame will have to be retransmitted. We will consider 2 different Retransmission Strategies: 1. Stop-and-Wait Protocol 2. Go-Back-N Protocol 3. Selective Repeat Protocol The above protocols are also known as Automatic Repeat Request (ARQ) protocols 1502346 - Computer Communications & Networks 21  M. Saad Stop-and-Wait Retransmission Strategy Sender transmits one frame at a time. If frame received at receiver correctly, receiver sends an acknowledgement frame (ACK) to the sender. – When sender receives ACK, it sends a new frame. If frame received with error, receiver discards the frame. – When sender times out , it sends the same frame again. 1502346 - Computer Communications & Networks 22  M. Saad Problem with Basic Stop-and-Wait Consider the following situation: – Frame received correctly by receiver, receiver sends ACK, but ACK gets lost. Sender will time out, assuming that the original frame had an error, will send new frame. Receiver will receive the same frame again, thinking it is a new frame ⇒ loss of track of the frames. 1502346 - Computer Communications & Networks 23  M. Saad Modified Stop-and-Wait Sender transmits a frame including its sequence number (in its header). Receiver checks the sequence number ⇒ new frame will be accepted, duplicate frame will be discarded. If the receiver receives a new frame with no errors, it will send the sequence number of the next frame it expects. 1502346 - Computer Communications & Networks 24  M. Saad Go-Back-N Retransmission Strategy 1502346 - Computer Communications & Networks 25  M. Saad Go-Back-N Sender transmits frames (including sequence numbers), and does not wait for ACK to be received. Receiver sends ACK for every correctly received frame. In the example, frame 2 arrives with errors. – The receiver discards all frames that follow. – The sender will notice after a time-out interval the lack of ACK of frame 2. – The sender will then back up and start all over again sending frames 2, 3, 4,.... 1502346 - Computer Communications & Networks 26  M. Saad Selective Repeat Retransmission Strategy 1502346 - Computer Communications & Networks 27  M. Saad Selective Repeat Sender transmits frames (including sequence numbers), and does not wait for ACK to be received (same as Go-Back-N ). Receiver sends ACK for every correctly received frame (same as Go-Back- N ). In the example, frame 2 arrives with errors. – The receiver discards only the frame with errors (frame 2) and buffers all good frames that follow. – The receiver will send a negative acknowledgement (NAK) for frame 2. – The sender will then retransmit only the frame with errors (frame 2). 1502346 - Computer Communications & Networks 28  M. Saad Thanks 1502346 - Computer Communications & Networks 29