VTU BCS 502 Computer Networks Module 2 – Data Link Layer: Error Detection, Flow Control, Framing, and Media Access Protocols

Module 2 delves into the Data Link Layer, the crucial bridge between the physical transmission of signals and the reliable delivery of data frames. This layer ensures that communication across a link is accurate, synchronized, and free from errors, making it one of the most critical aspects of networking.

The module begins with Error Detection and Correction, introducing concepts such as block coding, cyclic redundancy check (CRC), and checksum methods. These techniques allow networks to detect and often correct errors caused by noisy channels, thereby ensuring reliable communication.

Next, students study Data Link Control (DLC) services, including framing, flow control, error control, and the distinction between connectionless and connection-oriented services. Protocols like High-Level Data Link Control (HDLC) are introduced to show how data is structured and managed across links.

The module also explores Media Access Control (MAC) techniques, which determine how multiple devices share the communication medium. Both random access methods (like ALOHA, CSMA, CSMA/CD) and controlled access techniques (like polling and token passing) are examined. Additionally, point-to-point protocols (PPP) are discussed as an important standard for direct connections.

By completing Module 2, students gain the ability to analyze and implement reliable data link communication mechanisms, understand how networks detect and correct errors, and appreciate how shared media can be efficiently accessed by multiple devices. This knowledge forms the backbone for studying higher layers of networking.

1. 10. 1 Chapter 10 Error Detection and Correction Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display. 5 th

2. Data can be corrupted during transmission. Some applications require that errors be detected and corrected. Note

3. 10-1 INTRODUCTION Let us first discuss some issues related, directly or indirectly, to error detection and correction. Types of Errors Redundancy Detection Versus Correction Forward Error Correction Versus Retransmission Coding Modular Arithmetic Topics discussed in this section:

4. In a single-bit error, only 1 bit in the data unit has changed. Note

5. 10. 5 Figure 10.1 Single-bit error

6. 10. 6 A burst error means that 2 or more bits in the data unit have changed. Note

7. 10. 7 Figure 10.2 Burst error of length 8

8. 10. 8 To detect or correct errors, we need to send extra (redundant) bits with data. Note The central concept in detecting or correcting errors is redundancy . To be able to detect or correct errors, we need to send some extra bits with our data . These redundant bits are added by the sender and removed by the receiver. Their presence allows the receiver to detect or correct corrupted bits.

9. correction of errors is more difficult than the detection. In error detection , we are only looking to see if any error has occurred. The answer is a simple yes or no. A single-bit error is the same for us as a burst error. In error correction , we need to know the exact number of bits that are corrupted and, more importantly, their location in the message. To correct single error in an 8-bit data unit, we need to consider eight possible error locations. For two bit errors in same size…? 10 bit error in 1000 bits..? 10. 9 10.1.3 Detection versus Correction

10. The sender adds redundant bits through a process that creates a relationship between the redundant bits and the actual data bits. The receiver checks the relationships between the two sets of bits to detect errors. The ratio of redundant bits to data bits and the robustness of the process are important factors in any coding scheme. block coding and convolution coding . In block coding, we divide our message into blocks, each of k bits, called datawords . We add r redundant bits to each block to make the length n = k + r . The resulting n -bit blocks are called codewords. As of now.. we have a set of datawords , each of size k , and a set of codewords, each of size of n. With k bits, we can create a combination of 2 k datawords ; with n bits, we can create a combination of 2 n codewords. Since n > k , the number of possible codewords is larger than the number of possible datawords . 10.1.4 Coding 10.2 BLOCK CODING

11. How can errors be detected by using block coding? If the following two conditions are met, the receiver can detect a change in the original codeword. The receiver has (or can find) a list of valid codewords The original codeword has changed to an invalid one 10.2.1 Error Detection

12. 10. 12 Let us assume that k = 2 and n = 3. Table 10.1 shows the list of datawords and codewords (even parity). It is only good for detecting one bit error. Example 10.1 Table 10.1 A code for error detection (Example 10.2)

13. 10. 13

14. 10. 14 An error-detecting code can detect only the types of errors for which it is designed; other types of errors may remain undetected. Note

15. 10. 15 The Hamming distance between two words is the number of differences between corresponding bits. Note

16. 10. 16 Let us find the Hamming distance between two pairs of words. 1 . The Hamming distance d(000, 011) is 2 because Example 10.4 2. The Hamming distance d(10101, 11110) is 3 because

17. 10. 17 The minimum Hamming distance is the smallest Hamming distance between all possible pairs in a set of words. Note

18. 10. 18 Find the minimum Hamming distance of the coding scheme in Table 10.1. Solution We first find all Hamming distances. Example 10.5 The d min in this case is 2.

19. 10. 19 To guarantee the detection of up to s errors in all cases, the minimum Hamming distance in a block code must be d min = s + 1. Note Why? More than s-bit error is possible to detect, but not guaranteed.

20. 10. 20 Figure 10.8 Geometric concept for finding d min in error detection

21. 10. 21 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 XOR (addition modulo-2) of two valid codewords creates another valid codeword. Minimum Distance for Linear Block Codes Some Linear Block Codes Topics discussed in this section:

22. 10. 22 In a linear block code, the exclusive OR (XOR) of any two valid codewords creates another valid codeword. Note

23. 10. 23 Let us see if the two codes we defined in Table 10.1 belong to the class of linear block codes. 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. Example 10.10

24. 10. 24 In our first code (Table 10.1), the numbers of 1s in the nonzero codewords are 2, 2, and 2. So the minimum Hamming distance is d min = 2. Example 10.11 In a linear block code, the minimum Hamming distance is the number of 1s in the nonzero valid codeword with the smallest number of 1s. Note

25. Perhaps the most familiar error-detecting code is the parity-check code. This code is a linear block code. In this code, a k -bit dataword is changed to an n -bit codeword where n = k + 1. The extra bit, called the parity bit, is selected to make the total number of 1s in the codeword even. Although some implementations specify an odd number of 1s, we discuss the even case. The minimum Hamming distance for this category is d min = 2, which means that the code is a single-bit error-detecting code 10. 25 Parity-Check Code

26. 10. 26 A simple parity-check code is a single-bit error-detecting code in which n = k + 1 with d min = 2. Note

27. 10. 27 Table 10.3 Simple parity-check code C(5, 4)

28. 10. 28 Figure 10.10 Encoder and decoder for simple parity-check code

29. Parity-check code r0 = a3 + a2 + a1 + a0 (modulo-2) Syndrome (calculated by the receiver) s0 = b3 + b2 + b1 + b0 + q0 (modulo-2) 10. 29

30. 10. 30

31. 10. 31 A simple parity-check code can detect an odd number of errors. Note

32. 10. 32 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. Cyclic Redundancy Check Hardware Implementation Polynomials Cyclic Code Analysis Advantages of Cyclic Codes Other Cyclic Codes Topics discussed in this section:

33. 10. 33 Table 10.6 A CRC code with C(7, 4)

34. 10. 34 Figure 10.14 CRC encoder and decoder

35. 10. 35 Figure 10.15 Division in CRC encoder

36. 10. 36 Figure 10.16 Division in the CRC decoder for two cases

37. 10. 37 Figure 10.20 General design of encoder and decoder of a CRC code

38. 10. 38 The divisor in a cyclic code is normally called the generator polynomial or simply the generator. Note

39. 10. 39 Figure 10.21 A polynomial to represent a binary word

40. 10. 40 Table 10.7 Standard polynomials

41. 10.4 Checksum Checksum is an error-detecting technique that can be applied to a message of any length. In the Internet, the checksum technique is mostly used at the network and transport layer rather than the data-link layer. 10. 41

42. 10. 42

43. 10. 43 Suppose our data is a list of five 4-bit numbers that we want to send to a destination. In addition to sending these numbers, we send the sum of the numbers. For example, if the set of numbers is (7, 11, 12, 0, 6), we send (7, 11, 12, 0, 6, 36 ), where 36 is the sum of the original numbers. The receiver adds the five numbers and compares the result with the sum. If the two are the same, the receiver assumes no error, accepts the five numbers, and discards the sum. Otherwise, there is an error somewhere and the data are not accepted. Example 10.18

44. 10. 44 We can make the job of the receiver easier if we send the negative (complement) of the sum, called the checksum . In this case, we send (7, 11, 12, 0, 6, −36 ). The receiver can add all the numbers received (including the checksum). If the result is 0, it assumes no error; otherwise, there is an error. Example 10.19

45. 10. 45 How can we represent the number 21 in one’s complement arithmetic using only four bits? Solution The number 21 in binary is 10101 (it needs five bits). We can wrap the leftmost bit and add it to the four rightmost bits. We have (0101 + 1) = 0110 or 6 . Example 10.20

46. 10. 46 How can we represent the number −6 in one’s complement arithmetic using only four bits? Solution In one’s complement arithmetic, the negative or complement of a number is found by inverting all bits. Positive 6 is 0110; negative 6 is 1001. If we consider only unsigned numbers, this is 9. In other words, the complement of 6 is 9. Example 10.21

47. 10. 47 Figure 10.24 Example 10.22 1 1 1

48. 10. 48 Sender site: 1. The message is divided into 16-bit words. 2. The value of the checksum word is set to 0. 3. All words including the checksum are added using one’s complement addition. 4. The sum is complemented and becomes the checksum. 5. The checksum is sent with the data. Note

49. 10. 49 Receiver site: 1. The message (including checksum) is divided into 16-bit words. 2. All words are added using one’s complement addition. 3. The sum is complemented and becomes the new checksum. 4. If the value of checksum is 0, the message is accepted; otherwise, it is rejected. Note

50. 10. 50

51. Internet Checksum Example Note When adding numbers, a carryout from the most significant bit needs to be added to the result Example: add two 16-bit integers 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1 wraparound sum checksum

52. Data Link Control (DLC) The data link control (DLC) deals with procedures for communication between two adjacent nodes—node-to-node communication—no matter whether the link is dedicated or broadcast. Data link control functions include framing and flow and error control . In this section, we first discuss framing, or how to organize the bits that are carried by the physical layer. We then discuss flow and error control. 10. 52