MOD 5 - Data link layer.pptx. .

A beginner guide to the data link layer in Computer Networks.

1. CMT 107:-COMPUTER NETWORKS Module 5: Data Link Layer

2. Learning Objectives Data Link Layer Data Link Layer Functions Error Detection Hamming Algorithm and Code CSMA CA vs CSMA CD Module 5: Data Link Layer 2

3. Data Link Layer Data Link Layer is second layer of OSI Layered Model. This layer is one of the most complicated layers and has complex functionalities and liabilities. Data link layer hides the details of underlying hardware and represents itself to upper layer as the medium to communicate. Data link layer works between two hosts which are directly connected in some sense. This direct connection could be point to point or broadcast. Systems on broadcast network are said to be on same link. The work of data link layer tends to get more complex when it is dealing with multiple hosts on single collision domain. Module 5: Data Link Layer 3

4. What is Data Link Layer? The Data Link layer transforms a raw transmission facility into a line that appears free of undetected transmission errors to the network layer and is responsible for node-to-node delivery. It makes error-free the physical layer appear to the upper layer (network layer) . Data Link Layer is the second layer of OSI Layered Model after Physical Layer. When a packet or message reaches to a network, it is the responsibility of Data Link Layer to transmit it to the Host using its MAC address. Data Link Layer devices are Switch & Bridges. Module 5: Data Link Layer 4

5. Data Link Layer Functions Data link layer is responsible for converting data stream to signals bit by bit and to send that over the underlying hardware . At the receiving end, Data link layer picks up data from hardware which are in the form of electrical signals, assembles them in a recognizable frame format, and hands over to upper layer . The main functions of data link layer include  framing, error detection and correction, acknowledgement, flow control , ensuring well-defined reliable service interface to the network layer, encapsulating packets from network layer to frames, etc. Module 5: Data Link Layer 5

6. Data link layer has two sub-layers: Logical Link Control:  It deals with protocols, flow-control, and error control This is the uppermost sub-layer, LLC consists of protocols running at the top of the data link layer, and also provides flow control, acknowledgment, and error notification . The LLC provides addressing and data link control. It specifies which methods are to be used for addressing channels over the transmission medium and for controlling the data exchanged between the generator of packet and recipient of the message. Module 5: Data Link Layer 6

7. ii. Media Access Control It deals with actual control of media . Who can access the media at any one time, determines by the MAC sublayer(e.g. CSMA/CD). The packet obtains from the Network layer is further divided into frames depending on the frame size of NIC (Network Interface Card). DLL also encases Sender's and Receiver's MAC address in the header. An ARP(Address Resolution Protocol) request is placed onto the wire asking  "Who has that IP address?"  and after getting this message destination host replies with its MAC address. By this, the receiver's MAC address is obtained. Module 5: Data Link Layer 7

8. Functionality of Data-link Layer Data link layer does many tasks on behalf of upper layer. These are: i . Framing The data link layer receives the stream of bits from the network layer divides into manageable data units called frames. Data-link layer takes packets from Network Layer and encapsulates them into Frames. Then, it sends each frame bit-by-bit on the hardware . At receiver’ end, data link layer picks up signals from hardware and assembles them into frames. ii. Physical Addressing Data-link layer provides layer-2 hardware addressing mechanism. Hardware address is assumed to be unique on the link. It is encoded into hardware at the time of manufacturing . If frames are to be distributed to different stations on the network. To define the physical address of the sender (source address) and/or receiver (destination address) of the frame, the DLL adds a header to the frame. If the frame is to be sent for a system outside the sender's network. The receiver's address means the address of the device that connects one network to the another. Module 5: Data Link Layer 8

9. Module 5: Data Link Layer 9

10. iii. Synchronization When data frames are sent on the link, both machines must be synchronized in order to transfer to take place . iv. Error Control The data link layer also deals with damaged or lost frames . By adding mechanisms to detect and retransmit lost frames increases reliability. Sometimes signals may have encountered problem in transition and the bits are flipped . These errors are detected and attempted to recover actual data bits. It also provides error reporting mechanism to the sender. v. Flow Control If the rate at which the data are consumed by the receiver is less than the rate produced by the sender, the data link layer deals with a flow control mechanism to prevent overrun the receiver . Stations on same link may have different speed or capacity. Data-link layer ensures flow control that enables both machine to exchange data on same speed. Module 5: Data Link Layer 10

11. vi. Multi-Access When more than two or two devices are connected to the common link, data link layer protocols are necessary to determine which device has control over the link at any point of time. When host on the shared link tries to transfer the data, it has a high probability of collision. Data-link layer provides mechanism such as CSMA/CD to equip capability of accessing a shared media among multiple Systems. Module 5: Data Link Layer 11

12. Example : In this figure, a node with physical address 23 sends a frame to a node with physical address 92. The two nodes connected by a link level. At the link level this frame contains physical (link) addresses in the header . These are the only addresses needed. The remaining header contains other information that is required at this level. The extra bits needed for error detection contains by the trailer . Module 5: Data Link Layer 12

13. Module 5: Data Link Layer 13

14. Design Issues with Data Link Layer The issue that arises in the data link layer (and most of the higher layers as well) is the speed mismatch between sender and receiver . Some traffic regulation mechanism is often needed to know the exact available free space, the receiver has at the moment . Frequently, the flow regulation and error handling are combined in this layer. Here is an additional issue in the data link layer with broadcast networks that is how to control access to the shared channel. The Medium Access Control (MAC), the sub-layer of the data link layer deals with this problem. Module 5: Data Link Layer 14

15. Error Detection When data is transmitted from one device to another device, the system does not guarantee whether the data received by the device is identical to the data transmitted by another device . An Error is a situation when the message received at the receiver end is not identical to the message transmitted. Module 5: Data Link Layer 15

16. Types Of Errors Errors can be classified into two categories: Single-Bit Error Burst Error Module 5: Data Link Layer 16

17. Single-Bit Error: The only one bit of a given data unit is changed from 1 to 0 or from 0 to 1. In the above figure, the message which is sent is corrupted as single-bit, i.e., 0 bit is changed to 1. Module 5: Data Link Layer 17

18. Single-Bit Error  does not appear more likely in Serial Data Transmission. For example, Sender sends the data at 10 Mbps, this means that the bit lasts only for 1 ?s and for a single-bit error to occurred, a noise must be more than 1 ?s. Single-Bit Error mainly occurs in Parallel Data Transmission . For example, if eight wires are used to send the eight bits of a byte, if one of the wire is noisy, then single-bit is corrupted per byte. Module 5: Data Link Layer 18

19. Burst Error: The two or more bits are changed from 0 to 1 or from 1 to 0 is known as Burst Error. The Burst Error is determined from the first corrupted bit to the last corrupted bit. Module 5: Data Link Layer 19

20. The duration of noise in Burst Error is more than the duration of noise in Single-Bit. Burst Errors are most likely to occur in Serial Data Transmission . The number of affected bits depends on the duration of the noise and data rate. Module 5: Data Link Layer 20

21. Hamming Algorithm and Code Basic idea : combine bits in an intelligent fashion so that each extra bit checks whether there is an error in a subset of information bits. Hamming code is a  set of error-correction codes  that can be used to detect and correct the errors that can occur when the data is moved or stored from the sender to the receiver . It is technique developed by R.W. Hamming for error correction. Like other error-correction code, Hamming code makes use of the concept of  parity  and  parity bit ( s) , which are bits that are added to data so that the validity of the data can be checked when it is read or after it has been received in a data transmission. Module 5: Data Link Layer 21

22. Using more than one parity bit, an error-correction code can not only identify a single bit error in the data unit, but also its location in the data unit. Detecting odd number of error for a block with n − 1 information bits, add one extra bit so that parity of the entire block is 0 (the number of 1’s in the block is even). Parity check code : if we use multiple parity check bits. Hamming code is one example. Module 5: Data Link Layer 22

23. Hamming Code Hamming Code:- Hamming code is a block code that is capable of detecting up to two simultaneous bit errors and correcting single-bit errors . It was developed by R.W. Hamming for error correction. In this coding method, the source encodes the message by inserting redundant bits within the message . These redundant bits are extra bits that are generated and inserted at specific positions in the message itself to enable error detection and correction. When the destination receives this message, it performs recalculations to detect errors and find the bit position that has error . Module 5: Data Link Layer 23

24. Encoding a message by Hamming Code The procedure used by the sender to encode the message encompasses the following steps. Step 1  − Calculation of the number of redundant bits. Step 2  − Positioning the redundant bits. Step 3  − Calculating the values of each redundant bit. Module 5: Data Link Layer 24

25. Once the redundant bits are embedded within the message, this is sent to the user. Step 1 − Calculation of the number of redundant bits. If the message contains  m 𝑚number of data bits,  r 𝑟number of redundant bits are added to it so that  m 𝑟 is able to indicate at least ( m  +  r + 1) different states. Here, ( m  +  r ) indicates location of an error in each of (𝑚 + 𝑟) bit positions and one additional state indicates no error. Since,  r 𝑟 bits can indicate 2 r 𝑟 states, 2 r 𝑟 must be at least equal to ( m  +  r  + 1). Thus the following equation should hold  2 r  ≥ m+r+1. Module 5: Data Link Layer 25

26. Step 2 − Positioning the redundant bits. The  r  redundant bits placed at bit positions of powers of 2, i.e. 1, 2, 4, 8, 16 etc. They are referred in the rest of this text as  r 1  (at position 1),  r 2  (at position 2),  r 3  (at position 4),  r 4  (at position 8) and so on. Module 5: Data Link Layer 26

27. Step 3 − Calculating the values of each redundant bit. The Step 3 − Calculating the values of each redundant bit. The redundant bits are parity bits. A parity bit is an extra bit that makes the number of 1s either even or odd. The two types of parity are − Even Parity  − Here the total number of bits in the message is made even. Odd Parity  − Here the total number of bits in the message is made odd. Module 5: Data Link Layer 27

28. Each redundant bit, r i , is calculated as the parity, generally even parity, based upon its bit position . It covers all bit positions whose binary representation includes a 1 in the i th  position except the position of r i . Thus: − r 1  is the parity bit for all data bits in positions whose binary representation includes a 1 in the least significant position excluding 1 (3, 5, 7, 9, 11 and so on). r 2  is the parity bit for all data bits in positions whose binary representation includes a 1 in the position 2 from right except 2 (3, 6, 7, 10, 11 and so on). r4 is the parity bit for all data bits in positions whose binary representation includes a 1 in the position 3 from right except 4 (5-7, 12-15, 20-23 and so on). r8 is the parity bit for all data bits in positions whose binary representation includes a 1 in the position 4 from right except 8 (9-16 and so on). Module 5: Data Link Layer 28

29. Decoding a message in Hamming Code Once the receiver gets an incoming message, it performs recalculations to detect errors and correct them. The steps for recalculation are − Step 1  − Calculation of the number of redundant bits. Step 2  − Positioning the redundant bits. Step 3  − Parity checking. Step 4  − Error detection and correction Step 1 − Calculation of the number of redundant bits Using the same formula as in encoding, the number of redundant bits are ascertained. 2 r  ≥ m + r + 1 where  m  is the number of data bits and  r  is the number of redundant bits. Step 2 − Positioning the redundant bits The  r  redundant bits placed at bit positions of powers of 2, i.e. 1, 2, 4, 8, 16 etc. Module 5: Data Link Layer 29

30. Step 3 − Parity checking Parity bits are calculated based upon the data bits and the redundant bits using the same rule as during generation of c 1 ,c 2  ,c 3  ,c 4  etc. Thus:- c 1  = parity(1, 3, 5, 7, 9, 11 and so on) c 2  = parity(2, 3, 6, 7, 10, 11 and so on) c 3  = parity(4-7, 12-15, 20-23 and so on) Step 4 − Error detection and correction The decimal equivalent of the parity bits binary values is calculated. If it is 0, there is no error. Otherwise, the decimal value gives the bit position which has error. For example, if c 1 c 2 c 3 c 4  = 1001, it implies that the data bit at position 9, decimal equivalent of 1001, has error. The bit is flipped to get the correct message. Module 5: Data Link Layer 30

31. Data Link Controls Data-link control is the main function of the data link layer. It deals with the configuration and coordination for connection between two neighboring nodes: node-to-node communication . The task of the data link layer includes: error-control software-implemented protocols flow-control, and framing That provide efficient and smooth transmission of frames between nodes . Module 5: Data Link Layer 31

32. Framing The data link layer separates the bit-stream obtained from the network layer into usable data units called frames. Module 5: Data Link Layer 32

33. Flow control Flow control is one of the essential duties of the data link layer. It manages the amount of data that can be sent before obtaining confirmation. Flow control is a set of methods that tell the sender how much data it can transmit before the receiver is overloaded . Any receiving device has limited speed and limited memory for the process of incoming data and storage of the incoming data. Module 5: Data Link Layer 33

34. Module 5: Data Link Layer 34

35. Error control Error control includes both methods of error detection and error correction. The error control helps the receiver to notify the sender of any lost frames or damaged frames during the transmission . It allows to retransmission of those frames by the sender. At the data link layer, error control is often easily implemented: whenever an error is detected at the frames, those frames are re-transmitted . Module 5: Data Link Layer 35

36. Byte and Bits Stuffing Byte stuffing  is a mechanism to convert a message formed of a sequence of bytes that may contain reserved values such as frame delimiter, into another byte sequence that does not contain the reserved values. Bit stuffing  is the mechanism of inserting one or more non-information bits into a message to be transmitted, to break up the message sequence, for synchronization purpose. Module 5: Data Link Layer 36

37. Purposes of byte stuffing and bit stuffing In Data Link layer, the stream of bits from physical layer are divided into data frames. The data frames can be of fixed length or variable length. In variable - length framing, the size of each frame to be transmitted may be different. So, a pattern of bits is used as a delimiter to mark the end of one frame and the beginning of the next frame. However, if the pattern occurs in the message, then mechanisms needs to be incorporated so that this situation is avoided. Module 5: Data Link Layer 37

38. The two common approaches are − Byte - Stuffing  − A byte is stuffed in the message to differentiate from the delimiter. This is also called character-oriented framing . Bit - Stuffing  − A pattern of bits of arbitrary length is stuffed in the message to differentiate from the delimiter. This is also called bit - oriented framing . Module 5: Data Link Layer 38

39. Data link layer frames in byte stuffing and bit stuffing A data link frame has the following parts − Frame Header  − It contains the source and the destination addresses of the frame. Payload field  − It contains the message to be delivered. In bit stuffing it is a variable sequence of bits, while in byte stuffing it is a variable sequence of data bytes. Trailer  − It contains the error detection and error correction bits. Flags  − Flags are the frame delimiters signaling the start and end of the frame. In bit stuffing, flag comprises of a bit pattern that defines the beginning and end bits. It is generally of 8-bits and comprises of six or more consecutive 1s. In byte stuffing, flag is of 1- byte denoting a protocol - dependent special character. Module 5: Data Link Layer 39

40. Module 5: Data Link Layer 40

41. Mechanisms of byte stuffing versus bit stuffing Byte Stuffing Mechanism If the pattern of the flag byte is present in the message byte sequence, there should be a strategy so that the receiver does not consider the pattern as the end of the frame. Here, a special byte called the escape character (ESC) is stuffed before every byte in the message with the same pattern as the flag byte . If the ESC sequence is found in the message byte, then another ESC byte is stuffed before it. Bit Stuffing Mechanism Here, the delimiting flag sequence generally contains six or more consecutive 1s. Most protocols use the 8-bit pattern 01111110 as flag. In order to differentiate the message from the flag in case of same sequence, a single bit is stuffed in the message . Whenever a 0 bit is followed by five consecutive 1bits in the message, an extra 0 bit is stuffed at the end of the five 1s . When the receiver receives the message, it removes the stuffed 0s after each sequence of five 1s. The un-stuffed message is then sent to the upper layers . Module 5: Data Link Layer 41

42. Module 5: Data Link Layer 42

43. CSMA CA vs CSMA CD CSMA  is a mechanism that senses the state of the shared channel to prevent or recover data packets from a collision . It is also used to control the flow of data packets over the network so that the packets are not get lost, and data integrity is maintained . In CSMA, when two or more data packets are sent at the same time on a shared channel, the chances of collision occurred. Due to the collision, the receiver does not get any information regarding the sender's data packets. And the lost information needs to be resented so that the receiver can get it. Therefore we need to sense the channel before transmitting data packets on a network . It is divided into two parts,  CSMA CA  (Collision Avoidance) and  CSMA CD  (Collision Detection). Module 5: Data Link Layer 43

44. CSMA CD CSMA/CD stands for Carrier Sense Multiple Access/Collision Detection is a network protocol for carrier transmission. It is operated in the medium access control layer. The Carrier Sense Multiple Access/ Collision Detection protocol is used to detect a collision in the media access control ( MAC ) layer. Once the collision was detected, the CSMA CD immediately stopped the transmission by sending the signal so that the sender does not waste all the time to send the data packet. Suppose a collision is detected from each station while broadcasting the packets. In that case, the CSMA CD immediately sends a jam signal to stop transmission and waits for a random time context before transmitting another data packet. If the channel is found free, it immediately sends the data and returns it. Module 5: Data Link Layer 44

45. Advantage and Disadvantage of CSMA CD Advantages of CSMA CD: It is used for collision detection on a shared channel within a very short time. CSMA CD is better than CSMA for collision detection. CSMA CD is used to avoid any form of waste transmission. When necessary, it is used to use or share the same amount of bandwidth at each station. It has lower CSMA CD overhead as compared to the CSMA CA. Module 5: Data Link Layer 45

46. Disadvantage of CSMA CD It is not suitable for long-distance networks because as the distance increases, CSMA CD' efficiency decreases. It can detect collision only up to 2500 meters, and beyond this range, it cannot detect collisions. When multiple devices are added to a CSMA CD, collision detection performance is reduced. Module 5: Data Link Layer 46

47. CSMA/CA CSMA stands for  Carrier Sense Multiple Access  with  Collision Avoidance . It means that it is a network protocol that uses to avoid a collision rather than allowing it to occur, and it does not deal with the recovery of packets after a collision . It is similar to the CSMA CD protocol that operates in the media access control layer. In CSMA CA, whenever a station sends a data frame to a channel, it checks whether it is in use. If the shared channel is busy, the station waits until the channel enters idle mode. Hence, we can say that it reduces the chances of collisions and makes better use of the medium to send data packets more efficiently. Module 5: Data Link Layer 47

48. Advantage and Disadvantage of CSMA CA Advantage of CSMA CA When the size of data packets is large, the chances of collision in CSMA CA is less. It controls the data packets and sends the data when the receiver wants to send them. It is used to prevent collision rather than collision detection on the shared channel. CSMA CA avoids wasted transmission of data over the channel. It is best suited for wireless transmission in a network. It avoids unnecessary data traffic on the network with the help of the RTS/ CTS extension. Module 5: Data Link Layer 48

49. The disadvantage of CSMA CA Sometime CSMA/CA takes much waiting time as usual to transmit the data packet. It consumes more bandwidth by each station. Its efficiency is less than a CSMA CD. Module 5: Data Link Layer 49

50. Difference between CSMA CA and CSMA CD S/No. CSMA CD CSMA CA 1. It is the type of CSMA to detect the collision on a shared channel. It is the type of CSMA to avoid collision on a shared channel. 2. It is the collision detection protocol. It is the collision avoidance protocol. 3. It is used in 802.3 Ethernet network cable. It is used in the 802.11 Ethernet network. 4. It works in wired networks. It works in wireless networks. 5. It is effective after collision detection on a network. It is effective before collision detection on a network. 6. Whenever a data packet conflicts in a shared channel, it resends the data frame. Whereas the CSMA CA waits until the channel is busy and does not recover after a collision. 7. It minimizes the recovery time. It minimizes the risk of collision. Module 5: Data Link Layer 50

51. 8. The efficiency of CSMA CD is high as compared to CSMA. The efficiency of CSMA CA is similar to CSMA. 9. It is more popular than the CSMA CA protocol. It is less popular than CSMA CD. Module 5: Data Link Layer 51

52. ***END*** Module 5: Data Link Layer 52