Data Link Layer - ch_10_Update PDF

PART III Data Link Layer 10.1  Position of the data-link layer 10.2  - A packet at the data- link layer is normally called a frame. - The data-link layer of the source host needs only to encapsulate, the data-link layer of the...

PART III Data Link Layer 10.1  Position of the data-link layer 10.2  - A packet at the data- link layer is normally called a frame. - The data-link layer of the source host needs only to encapsulate, the data-link layer of the destination host needs to decapsulate, but each intermediate node needs to both encapsulate and decapsulate. -A different protocol with a different frame format are used between source and destination. -Different data-link layers have different formats for framing (datagram from Network Layer) 10.3  Data Link Layer (Services) ◼ Framing ◼ Flow Control (Buffer) ◼ Error Control (Detect and correct) ◼ Congestion Control (Loss frame, congestion control is considered an issue in the network layer or the transport layer because of its end-to-end nature) ◼ Two Categories of Links (Point to point and broadcasting) 10.4  Two Sublayers 10.5  LINK-LAYER ADDRESSING ◼ IP addresses in a datagram should not be changed for source and destination. (Internet) ◼ The source and destination IP addresses define the two ends but cannot define which links the datagram should pass through. ◼ Connectionless internetwork. We need another address to connect between two nodes. ◼ Link-layer addresses of the two nodes. A link-layer address is sometimes called a link address, sometimes a physical address, and sometimes a MAC address. ◼ Unicast Address (one-to-one communication.) ◼ Multicast Address (one-to-many communication) ◼ Broadcast Address (one-to-all communications) 10.6  Address Resolution Protocol (ARP) (1) ◼ The ARP protocol is one of the auxiliary protocols defined in the network layer. ◼ The packet includes the link-layer and IP addresses of the sender and the IP address of the receiver. ◼ The response packet contains the recipient’s IP and link-layer addresses. 10.7  Address Resolution Protocol (ARP) (2) ◼ Caching (Reduce number of unicast datagrams and keep the link layer for the complete connection) Example ( 20 systems, and 10 datagrams. Send one unicast to 19 and one replay unicast to source. Otherwise, it will be 180 broadcast messages ). ◼ Packet Format 10.8  An Example of Communication 10.9 10.10 10.11 10.12  Data link layer duties 10.13  Chapters Chapter 10 Error Detection and Correction Chapter 11 Data Link Control Chapter 12 Multiple Access Chapter 15 Connecting LANs 10.14  Chapter 10 Error Detection and Correction 10.15 Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.  Note Data can be corrupted during transmission. Some applications require that errors be detected and corrected. Other applications can tolerate a small level of error. 10.16  10-1 INTRODUCTION Let us first discuss some issues related, directly or indirectly, to error detection and correction. Topics discussed in this section: Types of Errors Redundancy Detection Versus Correction Forward Error Correction Versus Retransmission Coding 10.17  Figure 10.1 Single-bit error In a single-bit error, only 1 bit in the data unit has changed. 10.18  Figure 10.2 Burst error of length 8 A burst error means that 2 or more bits in the data unit have changed. Why burst error is more likely to occur than a single-bit error? 10.19  Figure 10.3 The structure of encoder and decoder To detect or correct errors, we need to send extra (redundant) bits with data. 10.20  10-2 BLOCK CODING Topics discussed in this section: Error Detection Error Correction Hamming Distance Minimum Hamming Distance 10.21  Figure 10.5 Datawords and codewords in block coding 10.22  Table 10.1 A code for error detection (Example 10.2) Let us assume that k = 2 and n = 3. Table 10.1 shows the list of datawords and codewords. Assume the sender encodes the dataword 01 as 011 and sends it to the receiver. Consider the following cases: 1. The receiver receives 011. It is a valid codeword. The receiver extracts the dataword 01 from it. 2. The codeword is corrupted during transmission, and 111 is received. This is not a valid codeword and is discarded. 3. The codeword is corrupted during transmission, and 000 is received. This is a valid codeword. The receiver incorrectly extracts the dataword 00. Two corrupted bits have made the error undetectable. 10.23  Note An error-detecting code can detect only the types of errors for which it is designed; other types of errors may remain undetected. 10.24  Note The Hamming distance between two words is the number of differences between corresponding bits. Example 10.4 Let us find the Hamming distance between two pairs of words. 1. The Hamming distance d(000, 011) is 2 because 2. The Hamming distance d(10101, 11110) is 3 because 10.25  Note Example 10.6 Find the minimum Hamming distance of this coding scheme. Solution We first find all the Hamming distances. The dmin in this case is 2. If two errors occur, however, the received codeword may match a valid codeword and the errors are not 10.26 detected.  Note To guarantee the detection of up to s errors in all cases, the minimum Hamming distance in a block code must be dmin = s + 1. To guarantee correction of up to t errors in all cases, the minimum Hamming distance in a block code must be dmin = 2t + 1. 10.27  Example 10.9 A code scheme has a Hamming distance dmin = 4. What is the error detection and correction capability of this scheme? Solution This code guarantees the detection of up to three errors (s = 3), but it can correct up to one error. In other words, if this code is used for error correction, part of its capability is wasted. Error correction codes need to have an odd minimum distance (3, 5, 7,... ). 10.28  10-3 LINEAR BLOCK CODES Almost all block codes used today belong to a subset called linear block codes. A linear block code is a code in which the exclusive OR (addition modulo-2) of two valid codewords creates another valid codeword. Topics discussed in this section: Minimum Distance for Linear Block Codes Some Linear Block Codes: Parity Check Hamming Code 10.29  Example 10.10 Let us see if the two codes we defined in Table 10.1 Table 10.1 and Table 10.2 belong to the class of linear block codes. 1. The scheme in Table 10.1 is a linear block code because the result of XORing any codeword with any other codeword is a valid codeword. For example, the XORing of the second and third codewords creates the fourth one. Table 10.2 2. The scheme in Table 10.2 is also a linear block code. We can create all four codewords by XORing two other codewords. 10.30  Detection and correction methods LINEAR BLOCK CODES Parity Check Hamming Code 10.31  Simple parity-check code A simple parity-check code is a single-bit error-detecting code in which n = k + 1 with dmin = 2. Example 10.11 In Table 10.1, the numbers of 1s in the nonzero codewords are 2, 2, and 2. So the minimum Hamming distance is dmin = 2. In our second code (Table 10.2), the numbers of 1s in the nonzero codewords are 3, 3, and 4. So in this code we have dmin = 3. 10.32  parity-check code 10.33  Table 10.3 Simple parity-check code C(5, 4) In parity check, a parity bit is added to every data unit so that the total number of 1s is even (or odd for odd-parity). 10.34  Example 10.12 Let us look at some transmission scenarios. Assume the sender sends the dataword 1011. The codeword created from this dataword is 10111, which is sent to the receiver. We examine five cases: 1. No error occurs; the received codeword is 10111. The syndrome is 0. The dataword 1011 is created. 2. One single-bit error changes a1. The received codeword is 10011. The syndrome is 1. No dataword is created. 3. One single-bit error changes r0. The received codeword is 10110. The syndrome is 1. No dataword is created. 4. An error changes r0 and a second error changes a3. The received codeword is 00110. The syndrome is 0. The dataword 0011 is created at the receiver. Note that here the dataword is wrongly created due to the syndrome value. 5. Three bits—a3, a2, and a1—are changed by errors. The received codeword is 01011. The syndrome is 1. The dataword is not created. This shows that the simple parity check, guaranteed to detect one single error, can also find any odd number of errors. 10.35  Note A simple parity-check code can detect an odd number of errors. 10.36  Figure 10.11 Two-dimensional parity-check code The parity bit: Odd numbers of one’s add – 1 Even numbers of one’s add – 0 10.37  Figure 10.11 Two-dimensional parity-check code 10.38  Figure 10.11 Two-dimensional parity-check code 10.39  Hamming Code 40 McGraw-Hill ©The McGraw-Hill Companies, Inc., 2000  Hamming code Data and redundancy bits Number of Number of Total data bits redundancy bits bits m r m+r 1 2 3 2 3 5 3 3 6 4 3 7 5 4 9 6 4 10 7 4 11 10.41  Positions of redundancy bits in Hamming code 10.42  Redundancy bits calculation 10.43  Example of redundancy bit calculation 10.44  Error detection using Hamming code 10.45  Figure 10.13 Burst error correction using Hamming code 10.46  10-4 CYCLIC CODES Cyclic codes are special linear block codes with one extra property. In a cyclic code, if a codeword is cyclically shifted (rotated), the result is another codeword. Topics discussed in this section: Cyclic Redundancy Check Polynomials Cyclic Code Analysis Advantages of Cyclic Codes Other Cyclic Codes 10.47  cyclic redundancy check (CRC ) CCRC generator and checker 10.48  Figure 10.15 Division in CRC encoder 10.49  Figure 10.16 Division in the CRC decoder for two cases 10.50  Figure 10.21 A polynomial to represent a binary word 10.51  Table 10.7 Standard polynomials 10.52  10-5 CHECKSUM The last error detection method we discuss here is called the checksum. The checksum is used in the Internet by several protocols although not at the data link layer. However, we briefly discuss it here to complete our discussion on error checking Topics discussed in this section: Idea Internet Checksum 10.53  Checksum 10.54  Data unit and checksum 10.55  Figure 10.24 Example 10.22 10.56 10.57