Data Link Layer Fundamentals PDF

Computer Networks (CSC305) Course Outline: √Overview of Data Communication and Networking √Physical Layer √Data Link Layer - Logical Link Control (LLC) - Medium Access Control (MAC) - Network Layer - Transport Layer - Application Layer OSI Refe...

Computer Networks (CSC305) Course Outline: √Overview of Data Communication and Networking √Physical Layer √Data Link Layer - Logical Link Control (LLC) - Medium Access Control (MAC) - Network Layer - Transport Layer - Application Layer OSI Reference Model OSI Reference Model Data Link Layer Responsible for NODE-TO-NODE Communication. The data-link layer of the source host needs only to encapsulate, the data-link layer of the destination host needs to de-capsulate, but each intermediate node needs to both encapsulate and de-capsulate. Data Link Layer It has two sub-layers:  Data Link Layer Medium Logical Link Access Control (LLC) Control (MAC)  Data Link Layer Data Link Layer | Logical Link Control (LLC) Logical Link Control (LLC) Medium Access Control (MAC) Deals with procedures for communication between two adjacent nodes (node-to-node communication) – no matter whether the link is dedicated or broadcast. Framing Error Detection and Correction ▪ Character Count ▪ Types of Errors ▪ Character or Byte Stuffing ▪ Detection ▪ Bit Stuffing ▪ Correction ▪ Physical Layer Coding Violation Protocols Flow Control ▪ High-Level Data Link Control (HDLC) ▪ Stop-and-Wait ▪ Point-to-Point Protocol (PPP) ▪ Sliding Window Error Control ▪ Stop-and-Wait ARQ ▪ Go-back-n ARQ ▪ Selective-repeat ARQ Data Link Layer | Logical Link Control (LLC) Data Link Layer Logical Link Medium Access Control (LLC) Control (MAC) Framing ▪ Character Count ▪ Character or Byte Stuffing Error Detection and Correction ▪ Bit Stuffing ▪ Types of Errors ▪ Physical Layer Coding Violation ▪ Detection ▪ Correction Flow Control ▪ Stop-and-Wait Protocols ▪ Sliding Window ▪ High-Level Data Link Control (HDLC) Error Control ▪ Point-to-Point Protocol (PPP) ▪ Stop-and-Wait ARQ ▪ Go-back-n ARQ ▪ Selective-repeat ARQ  Data Link Layer Logical Link Control (LLC) | Framing Logical Link Control (LLC) Medium Access Control (MAC) The physical layer provides bit synchronization to ensure that the sender and receiver use the same bit durations and timing. The data-link layer needs to pack bits into frames, so that each frame is distinguishable from another. Framing separates a message from source to a destination by adding a sender address and a destination address. Can we put whole message in one frame? - Flow and error control will become inefficient for large frame. - Even a single-bit error would require the re-transmission of the whole frame. Frames can be of fixed or variable size: - In fixed-size framing, there is no need for defining the boundaries of the frames. - In variable-size framing, need a way to define the end of one frame and beginning of the next.  Data Link Logical Link Control (LLC) | Framing Layer Medium Logical Link Access Control Control (LLC) (MAC) A frame is composed of four fields: - Kind: tells whether the frame contains data or control information. Control - Seq: tells about the sequence number of the frame. Information - Ack: tells about the acknowledgement of a frame. - Info: Only used in case of data frame. It contains a single packet. Actual Data The packet from the network layer is passed to the data link layer for the inclusion in to ‘info’ field of an outgoing frame. When the frame arrives at the destination, the data link layer extracts the packet from the frame and passes the packet to the network layer. The data link layer break the bit stream into discrete frames. This process is more difficult in case of variable-size framing.  Data Link Framing | Character Count Layer Medium Logical Link Access Control Control (LLC) (MAC) Methods to mark the START and END of each frame are: Character Count Uses a field in the header to specify the number of characters in the frame. LOVE HATE MAKE A FUN 5 L O V E 5 H A T E 5 M A K E 2 A 4 F U N When the data link layer at the destination sees the character count, it knows how many characters follow and hence where the end of the frame is. Problem: Count can be garbled by a transmission error. The character count method is rarely used anymore.  Data Link Framing | Character or Byte Stuffing Layer Medium Logical Link Access Control Control (LLC) (MAC) Character Count Character or Byte Stuffing This framing method gets around the problem of resynchronization after an error by having each frame start and end with special bytes. To separate one frame from the next, an 8-bit (1-byte) FLAG is added at the beginning and the end of a frame. FLAG Header Payload Field (Data from Network Layer) Trailer FLAG The FLAG, composed of protocol-dependent special characters, signals the start or end of a frame. If the receiver ever loses synchronization, it can just search for the FLAG byte to find the end of the current frame. Two consecutive FLAG bytes indicate the end of one frame and start of the next one.  Data Link Framing | Character or Byte Stuffing Logical Link Lay er Medium Access Control Control (LLC) (MAC) Problem: The FLAG bytes bit pattern may occurs in the data. If this happens, the receiver, when it encounters this pattern in the middle of the data, thinks it has reached the end of the frame. Solution: A Character or byte-stuffing strategy was added to character-oriented framing. A special byte (ESC) is added to the data section of the frame when there is a character with the same pattern as the flag. 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 Whenever the receiver encounters the ESC character, it removes it from the data section and treats the next character as data, not as a delimiting flag. Framing | Bit Stuffing Data Link Layer Logical Link Medium Access Control (LLC) Control (MAC) Character Count | Character or Byte Stuffing Bit Stuffing The byte-stuffing framing is closely tied to the use of 8-bit characters (only ASCII). Each frame begins and ends with a special bit pattern (01111110). 01111110 Header Payload Field (data from Network Layer Trailer 01111110 Whenever the sender’s data link layer encounters five consecutive 1s in the data, it automatically stuffs a 0 bit into the outgoing bit stream – This is called BIT STUFFING. When the receiver sees five consecutive incoming 1 bits, followed by a 0 bit, it automatically de-stuffs the 0 bit. Original Data 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 Outgoing Data 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 Even if there is a 0 after five 1s, still stuff a 0. The 0 will be removed by the receiver.  Data Link Framing | Physical Layer Coding Violations Logical Link Lay er Medium Access Control Control (LLC) (MAC) Character Count | Character or Byte Stuffing | Bit Stuffing Physical Layer Coding Violations This method of framing is only applicable to networks in which the encoding on the physical medium contains some redundancy. For example, some LANs encode 1 bit of data by using 2 physical bits. Normally, a 1 bit is a high-low pair and 0 bit is a low-high pair. The combinations high-high and low-low are not used for data. Data Link Layer | Logical Link Control (LLC) Data Link Layer Logical Link Medium Access Control (LLC) Control (MAC) Framing ▪ Character Count ▪ Character or Byte Stuffing Error Detection and Correction ▪ Bit Stuffing ▪ Types of Errors ▪ Physical Layer Coding Violation ▪ Detection ▪ Correction Flow Control ▪ Stop-and-Wait Protocols ▪ Sliding Window ▪ High-Level Data Link Control (HDLC) Error Control ▪ Point-to-Point Protocol (PPP) ▪ Stop-and-Wait ARQ ▪ Go-back-n ARQ ▪ Selective-repeat ARQ Logical Link Control (LLC) | Flow Control Data Link Layer Logical Link Medium Access Control (LLC) Control (MAC) Set of procedure to tell the sender that how much data it can transmit before it must wait for an acknowledgement from the receiver. Each receiving device has its limited speed of processing data and has a limited amount of memory (buffer) to store such data. The receiving device must be able to inform the sending device before those limits are reached and to request that the sending device send fewer frames or stop temporarily. Two methods have been developed to control the flow of data across communication links: Stop-and-Wait Sliding Window Logical Link Control (LLC) | Flow Control Data Link Layer Medium Logical Link Access Control Control (LLC) (MAC) Stop-and-Wait Protocol The sender waits for an acknowledgement after every frame it sends. Next frame is sent on receipt of an acknowledgement of the previously sent frame. Advantage: Simplicity. Each frame is checked and acknowledged before the next frame is sent. Disadvantage: Inefficiency. Protocol is slow. Flow Control | Stop-and-Wait Protocol Data Link Layer Medium Logical Link Access Control Control (LLC) (MAC) Calculation for an Efficiency/Utilization of Link: Let us determine the maximum potential efficiency of a Half-Duplex Point-to-Point Link. Suppose that a long message is to be sent as a sequence of frames F1, F2, …..,Fn from station S1 to S2 in the following fashion: - Station S1 sends F1 - Station S2 sends an ACK - Station S1 sends F2 - Station S2 sends an ACK.. - Station S1 sends Fn - Station S2 sends an ACK Flow Control | Stop-and-Wait Protocol Data Link Layer Logical Link Medium Access Control (LLC) Control (MAC) The total time (T) to send the data can be expressed as: 𝑻 = 𝒏 ∗ 𝑻𝑭 , where TF is the time to send one frame and receive an ACK. TF can be expressed as: 𝐓𝐅 = 𝐭 𝐩𝐫𝐨𝐩 + 𝐭 𝐟𝐫𝐚𝐦𝐞 + 𝐭 𝐩𝐫𝐨𝐜 + 𝐭 𝐩𝐫𝐨𝐩 + 𝐭 𝐚𝐜𝐤 + 𝐭 𝐩𝐫𝐨𝐜 where tprop is propagation time from S1 to S2 or from S2 to S1. tframe is time to transmit a frame (time for the transmitter to send out all the bits of the frame). tproc is processing time at each station to react to an incoming event. tack is time to transmit an ACK. Assume, tproc is relatively negligible. tack is also very small, as the ACK frame is very small compared to the data frame. 𝐓 = 𝐧 ∗ 𝟐 ∗ 𝐭 𝐩𝐫𝐨𝐩 + 𝐭 𝐟𝐫𝐚𝐦𝐞  Data Link Flow Control | Stop-and-Wait Protocol Layer Medium Logical Link Access Control Control (LLC) (MAC) 𝐓 = 𝐧 ∗ 𝟐 ∗ 𝐭 𝐩𝐫𝐨𝐩 + 𝐭 𝐟𝐫𝐚𝐦𝐞 Only (𝑛 ∗ 𝑡𝑓𝑟𝑎𝑚𝑒) is actually spent transmitting data and the rest is overhead. The maximum possible utilization or efficiency of the link is: 𝑛 ∗ 𝑡𝑓𝑟𝑎𝑚𝑒 𝑈= 𝑛 ∗ 2 ∗ 𝑡𝑝𝑟𝑜𝑝 +𝑡𝑓𝑟𝑎𝑚𝑒 𝟏 𝒕𝒑𝒓𝒐𝒑 𝑼= 𝒘𝒉𝒆𝒓𝒆 𝒂 = 𝟏 + 𝟐𝒂 𝒕𝒇𝒓𝒂𝒎𝒆 𝐃𝐢𝐬𝐭𝐚𝐧𝐜𝐞 𝐨𝐟 𝐭𝐡𝐞 𝐋𝐢𝐧𝐤 𝐝 𝐭 𝐩𝐫𝐨𝐩 = = 𝐕𝐞𝐥𝐨𝐜𝐢𝐭𝐲 𝐨𝐟 𝐏𝐫𝐨𝐩𝐚𝐠𝐚𝐭𝐢𝐨𝐧 𝐕 ‘V’ is 3x108 m/sec in air or space and is 0.67 times the speed of light in cable. 𝐋𝐞𝐧𝐠𝐭𝐡 𝐨𝐟 𝐭𝐡𝐞 𝐟𝐫𝐚𝐦𝐞 𝐋 𝑹∗𝒅 𝐭 𝐟𝐫𝐚𝐦𝐞 = = Therefore, 𝒂 = 𝐃𝐚𝐭𝐚 𝐑𝐚𝐭𝐞 𝐑 𝑽∗𝑳  Data Link Flow Control | Stop-and-Wait Protocol Layer Medium Logical Link Access Control (LLC) 𝟏 𝐭 𝐩𝐫𝐨𝐩 𝐑∗𝐝 Control (MAC) 𝐔= , where 𝐚 = = 𝟏 + 𝟐𝐚 𝐭 𝐟𝐫𝐚𝐦𝐞 𝐕∗𝐋 Case I: a < 1 Frame Size > Link Length Propagation Time < Transmission Time t0 Transmission started at t0. Transmission started at t0. Acknowledgement arrives back to First bits of the frame arrived at the sender at t0+1+2a. t0+a receiver before the source has completed the transmission of the frame. Total time elapsed = (t0+1+2a) - t0 = (1+2a) t0+1 Total Transmission time = 1 Total Transmission time = 1 Last bit of the frame arrived at the t0+1+a receiver. 𝟏 𝑼𝒕𝒊𝒍𝒊𝒛𝒂𝒕𝒊𝒐𝒏 = Acknowledgement arrives back to 𝟏 + 𝟐𝒂 t0+1+2a sender at t0+1+2a. Flow Control | Stop-and-Wait Protocol Data Link Layer Medium Logical Link Access Control 𝟏 𝐭 𝐩𝐫𝐨𝐩 𝐑∗𝐝 Control (LLC) (MAC) 𝐔= , where 𝐚 = = 𝟏 + 𝟐𝐚 𝐭 𝐟𝐫𝐚𝐦𝐞 𝐕∗𝐋 Case II: a > 1 Frame Size < Link Length Propagation Time > Transmission Time t0 Transmission started at t0. Transmission started at t0. Acknowledgement arrives back to sender at t0+1+2a. t0+1 Total Transmission time = 1 Total time elapsed = (t0+1+2a) - t0 First bits of the frame arrived at = (1+2a) t0+a the receiver. Total Transmission time = 1 Frame completely arrived at the t0+1+a receiver. 𝟏 𝐔𝐭𝐢𝐥𝐢𝐳𝐚𝐭𝐢𝐨𝐧 = Acknowledgement arrives back to 𝟏 + 𝟐𝐚 t0+1+2a sender at t0+1+2a. Logical Link Control (LLC) | Flow Control Data Link Layer Medium Logical Link Access Control Control (LLC) Sliding Window Protocol (MAC) There is a need for transmitting data in both directions (Full Duplex). Options: Have two separate communication channels and use each one for simplex data traffic (in different direction). - There will be two separate physical circuits each with forward and reverse channel. - Bandwidth of the reverse channel is almost entirely wasted. - The user will PAY for two circuits and will USE only the capacity of one. Use same circuit for data in both directions. - Data frames from A to B will inter-mixed with the ACK frames from A to B. - ‘kind’ field of the header will tell receiver about the type of frame arrived. Flow Control | Sliding Window Protocol Data Link Layer Logical Link Medium Access Control (LLC) Control (MAC) Options: Have two separate communication channels and use each one for simplex data traffic (in different direction). Use same circuit for data in both directions. When a data frame arrives, instead of immediately sending a separate control frame, the receiver restrains itself and waits until the network layer passes it the next packet. - The ACK is attached to the outgoing data frame (by setting ‘ack’ field in header). - The ACK gets a free ride on the next outgoing data frame. This is called PIGGYBACKING. - Better use of the available channel bandwidth. Flow Control | Sliding Window Protocol Data Link Layer Medium Logical Link Access Control Control (LLC) (MAC) The sender can transmit several frames before needing an ACK. The receiver acknowledges only some of the frames, using a single ACK to confirm the receipt of multiple data frames. The sliding window refers to imaginary boxes at both the sender and the receiver. This window can hold frames at either end and provides the upper limit on the number of frames that can be transmitted before requiring an ACK. Frames may be acknowledged at any point without waiting for the window to fill up and may be transmitted as long as the window is not yet full. To keep track of which frames have been transmitted and which received, sliding window introduces an identification scheme based on the size of the window. The frames are numbered modulo-n, which means they are numbered from 0 to n-1. When the receiver sends an ACK, it includes the number of the next frame it expects to receive. Flow Control | Sliding Window Protocol Data Link Layer Logical Link Medium Access Control (LLC) Control (MAC) Sender Window  Data Link Flow Control | Sliding Window Protocol Layer Medium Logical Link Access Control Control (LLC) (MAC) Receiver Window  Data Link Lay er Flow Control | Sliding Window Protocol Logical Link Control (LLC) Medium Access Control (MAC) Sender Receiver 0 1 2 3 4 5 6 7 0 1 2 3 4.. 0 1 2 3 4 5 6 7 0 1 2 3 4.. Data 0 0 1 2 3 4 5 6 7 0 1 2 3 4.. 0 1 2 3 4 5 6 7 0 1 2 3 4.. Data 1 0 1 2 3 4 5 6 7 0 1 2 3 4.. 0 1 2 3 4 5 6 7 0 1 2 3 4.. ACK 2 0 1 2 3 4 5 6 7 0 1 2 3 4.. 0 1 2 3 4 5 6 7 0 1 2 3 4.. Data 2 0 1 2 3 4 5 6 7 0 1 2 3 4.. 0 1 2 3 4 5 6 7 0 1 2 3 4.. ACK 3 0 1 2 3 4 5 6 7 0 1 2 3 4.. 0 1 2 3 4 5 6 7 0 1 2 3 4.. Data 3 0 1 2 3 4 5 6 7 0 1 2 3 4.. 0 1 2 3 4 5 6 7 0 1 2 3 4.. Data 4 0 1 2 3 4 5 6 7 0 1 2 3 4.. 0 1 2 3 4 5 6 7 0 1 2 3 4.. Data 5 0 1 2 3 4 5 6 7 0 1 2 3 4.. 0 1 2 3 4 5 6 7 0 1 2 3 4.. ACK 6 0 1 2 3 4 5 6 7 0 1 2 3 4.. 0 1 2 3 4 5 6 7 0 1 2 3 4..  Data Link Layer Flow Control | Sliding Window Protocol Logical Link Medium Access Control Control (LLC) Calculation for an efficiency of link: (MAC) 𝑡𝑝𝑟𝑜𝑝 𝑅∗𝑑 Case I: W >= 2a+1 where, 𝑎 = 𝑡𝑓𝑟𝑎𝑚𝑒 = 𝑉∗𝐿 t0 t0+1 Normalized t0+2 Throughput/Efficiency is 1. t0+a t0+1+a The ACK for frame 1 reaches ‘A’ before ‘A’ has exhausted its window. Thus, ‘A’ can transmit continuously with no pause. t0+1+2a  Data Link Flow Control | Sliding Window Protocol Layer Medium Logical Link Access Control (LLC) Control (MAC) 𝑡𝑝𝑟𝑜𝑝 𝑅∗𝑑 Case II: W < 2a+1 where, 𝑎 = 𝑡𝑓𝑟𝑎𝑚𝑒 = 𝑉∗𝐿 t0 𝟏, 𝐖 ≥ 𝟐𝐚 + 𝟏 𝐔𝐭𝐢𝐥𝐢𝐳𝐚𝐭𝐢𝐨𝐧 = ቐ 𝐖 , 𝐖 < 𝟐𝐚 + 𝟏 𝟐𝐚 + 𝟏 t0+1 t0+a Normalized Throughput/Efficiency is ‘W’ t0+1+a time units out of a period of (2a+1) time units. t0+W ‘A’ exhausts its window at t=W and cannot t0+1+2a send additional frames until t=2a+1.  Data Link Layer Flow Control | Sliding Window Protocol Logical Link Medium Access Control Control (LLC) (MAC) One Bit Sliding Window Protocol with a maximum window size of 1. Uses stop-and-wait since the sender transmits a frame and waits for its acknowledgement before sending the next one. Data Link Layer | Logical Link Control (LLC) Data Link Layer Medium Logical Link Access Control Control (LLC) (MAC) Framing ▪ Character Count ▪ Character or Byte Stuffing Error Detection and Correction ▪ Bit Stuffing ▪ Types of Errors ▪ Physical Layer Coding Violation ▪ Detection ▪ Correction Flow Control ▪ Stop-and-Wait ▪ Sliding Window Protocols ▪ High-Level Data Link Control (HDLC) Error Control ▪ Point-to-Point Protocol (PPP) ▪ Stop-and-Wait ARQ ▪ Go-back-n ARQ ▪ Selective-repeat ARQ Logical Link Control (LLC) | Error Control Data Link Layer Logical Link Medium Access Control (LLC) Control (MAC) The underlying technology at the physical layer is not fully reliable, there is a need to implement error control at the data-link layer to prevent the receiving node from delivering corrupted packets to the network layer. The term error control refers primarily to methods of Error Detection and Retransmission. Feedback from the receiver is required to ensure reliable delivery of frames. The receiver is expected to send back special control frames bearing positive or negative acknowledgements (ACK or NAK) about the incoming frames. When the sender transmits a frame, it also starts a timer. The timer is set to go off after an interval long enough for the frame to reach the destination, be processed there, and have the ACK propagate back to the sender. Logical Link Control (LLC) | Error Control Data Link Layer Medium Logical Link Access Control Control (LLC) (MAC) Automatic Repeat Request (ARQ) Anytime an error is detected in an exchange, a negative acknowledgement (NAK) is returned and the specified frames are re-transmitted. This process is called AUTOMATIC REPEAT REQUEST (ARQ). Receipt of the Damaged Frame (due to noise in Error Control transmission) will be treated as the frame has been lost. Stop-and- Sliding Wait ARQ Window ARQ The automatic re-transmission of lost frames includes lost acknowledgement (ACK) and lost negative acknowledgement (NAK) frames. Go-back-n Selective Repeat  Error Control Logical Link Control (LLC) | Error Control Stop-and- Wait ARQ Sli di ng Window ARQ Stop-and-Wait ARQ Go-back-n Selective Repeat It is a form of Stop-and-Wait flow control extended to include re-transmission of data in case of lost or damaged frames. Four features are added to the basic Stop-and-Wait flow control mechanism: The sending device keeps a copy of the last frame transmitted until it receives an ACK for that frame. For identification purposes, both data frames and ACK frames are numbered alternately 0 and 1. A NAK frame is returned on receipt of the corrupted frame at the receiver end. NAK frames are unnumbered. The sending device is equipped with a timer. If an expected ACK is not received within an allotted time period, the sender assumes that the last data frame was lost in transit and sends it again.  Error Control Error Control | Stop-and-Wait ARQ Stop-and- Wait ARQ Sli di ng Window ARQ Selective Go-back-n Repeat  Error Control Error Control | Stop-and-Wait ARQ Stop-and- Wait ARQ Sli di ng Window ARQ Damaged Frame Go-back-n Selective Repeat Frame is discovered by the receiver to contain an ERROR The sender re-transmit the frame on receipt of NAK  Error Control Error Control | Stop-and-Wait ARQ Stop-and- Wait ARQ Sli di ng Window ARQ Lost Data Frame Go-back-n Selective Repeat The sender waits for an ACK or NAK frame until its timer goes off, at which point it tries again. Re-transmits the last data frame. Restarts its timer. Wait for an ACK.  Error Control Error Control | Stop-and-Wait ARQ Stop-and- Wait ARQ Sli di ng Window ARQ Lost Acknowledgement Go-back-n Selective Repeat The sender waits for an ACK or NAK frame until its timer goes off, at which point it tries again. Re-transmits the last data frame. Discards duplicate packet (Packet-0) Restarts its timer. and resends ACK1. Wait for an ACK. If the lost frame was a NAK, accepts the new copy of packet (Packet-0) and returns the appropriate ACK.  Error Control Logical Link Control (LLC) | Error Control Stop-and- Wait ARQ Sli di ng Window ARQ Sliding Window ARQ Go-back-n Selective Repeat Three features are added to the basic Sliding Window flow control mechanism: The sending device keeps copies of all transmitted frames until they have been acknowledged. Both ACK and NAK frames must be numbered for identification. Data frames that are received without errors do not have to be acknowledged individually. However, every damaged frame must be acknowledged IMMEDIATELY. The sending device is equipped with a timer to enable it to handle lost acknowledgements (ACK/NAK). n-1 frames may be sent before an ACK must be received. If n-1 frames (the size of the window) are awaiting ACK, the sender starts a timer and waits before sending any more. If the allotted time has run out with no ACK, the sender assumes that the frames were not received and retransmit one or all of the frames depending on the protocol.  Error Control Error Control | Sliding Window ARQ Stop-and- Wait ARQ Sli di ng Window ARQ Go-back-n ARQ Go-back-n Selective Repeat If one frame is lost or damaged, all frames sent since the last frame acknowledged are retransmitted. Damaged Frame As soon as receivers recovers problem, it stops accepting subsequent frames until the damaged frame has been replaced correctly. Receiver send NAK to the sender. Here, NAK2 means either the frame 2 is damaged or missing. On the receipt of NAK#, the sender retransmits all frames starting from #.  Error Control Error Control | Sliding Window ARQ Stop-and- Wait ARQ Sli di ng Window ARQ Go-back-n ARQ | Lost Data Frame Go-back-n Selective Repeat The data frames must be transmitted sequentially. The receiver checks the identifying number on each frame, discovers that one or more have been skipped, and returns a NAK for the first missing frame. NAK2 means either the frame 2 is damaged or missing. On the receipt of NAK#, the sender retransmits all frames starting from #.  Error Control Error Control | Sliding Window ARQ Stop-and- Wait ARQ Sli di ng Window ARQ Go-back-n ARQ | Lost Acknowledgement Go-back-n Selective Repeat The sending device can send as many frames as the window allows before waiting for an ACK. Once that limit has been reached or the sender has no more frames to send, it must wait. The sender is equipped with a timer that begins counting whenever the window capacity is reached. If an ACK has not been reached within the time limit, the sender retransmits every frame transmitted since the last ACK.  Error Control Error Control | Sliding Window ARQ Stop-and- Wait ARQ Sli di ng Window ARQ Go-back-n ARQ | Problem Go-back-n Selective Repeat Consider a network connecting two systems located 8000 KMs apart. The bandwidth of the network is 500*106 b/s. The propagation speed of the media is 4*106 m/s. It is needed to design a Go-back-n sliding window protocol for this network. The average packet size is 107 bits. The network is to be used for its full capacity. Then the minimum size in bits of the sequence number field has to be?  Error Control Error Control | Sliding Window ARQ Stop-and- Wait ARQ Sli di ng Window ARQ Selective-Repeat ARQ Go-back-n Selective Repeat If a frame is corrupted in transit, a NAK is returned and the frame is resent out of sequence. If one frame is lost, only the specific damaged or lost frame is retransmitted. The receiving device must be able to sort the frames it has and insert the retransmitted frame into its proper place in the sequence. The sending device must contain a searching mechanism that allows it to find and select only the requested frame for retransmission. A buffer in the receiver must keep all previously received out-of-sequence frames on hold. To aid selectivity, ACK number must refer to the FRAME RECEIVED instead of the next frame expected. Due to above complexity in the process, the recommended window size is less than or equal to (n+1)/2, where (n-1) is the Go-back-n window size.  Error Control Error Control | Sliding Window ARQ Stop-and- Wait ARQ Sli di ng Window ARQ Selective-Repeat ARQ | Damaged Frame Go-back-n Selective Repeat A NAK is returned. Frames received after the The damaged frame is damaged frame cannot resent out of sequence. be acknowledged until the damaged frames have been retransmitted.  Error Control Error Control | Sliding Window ARQ Stop-and- Wait ARQ Sli di ng Window ARQ Selective-Repeat ARQ | Lost Data Frame Go-back-n Selective Repeat If the lost frame was the LAST of the transmission, the receiver does nothing and the sender treats the silence like a lost of ACK. Frames can be accepted out-of sequence BUT they cannot be acknowledged out of sequence. A NAK is returned. The lost frame is resent out of sequence.  Error Control Error Control | Sliding Window ARQ Stop-and- Wait ARQ Sli di ng Window ARQ Selective-Repeat ARQ | Lost Acknowledgement Go-back-n Selective Repeat Same as that of Go-back-n ARQ. When the sending device reaches either the capacity of its window or the end of its transmission, it sets a timer. If no ACK arrives in the time allotted, the sender retransmits all of the frames that remain unacknowledged. In most cases, the receiver will recognize any duplications and discards them.  Error Control Error Control | Sliding Window ARQ Stop-and- Wait ARQ Sli di ng Window ARQ Selective-Repeat ARQ | Problem Go-back-n Selective Repeat In Selective-Repeat protocol, suppose frames through 0 to 4 have been transmitted. Now imagine that NAK received for frame 0, frame 5 (a new frame) is transmitted, NAK received for frame 1, NAK received for frame 2 and frame 6 (another new frame) is transmitted. At this point, what will be the outstanding packets in sender’s window? Data Link Layer | Logical Link Control (LLC) Data Link Layer Logical Link Medium Access Control (LLC) Control (MAC) Framing ▪ Character Count ▪ Character or Byte Stuffing Error Detection and Correction ▪ Bit Stuffing ▪ Types of Errors ▪ Physical Layer Coding Violation ▪ Detection ▪ Correction Flow Control ▪ Stop-and-Wait Protocols ▪ Sliding Window ▪ High-Level Data Link Control (HDLC) Error Control ▪ Point-to-Point Protocol (PPP) ▪ Stop-and-Wait ARQ ▪ Go-back-n ARQ ▪ Selective-reject ARQ Logical Link Control (LLC) | Error Detection and Correction Data Link Layer Logical Link Medium Access Control (LLC) Control (MAC) Data can be corrupted during transmission. Networks must be able to transfer data from one device to another with complete accuracy. Reliable systems must have a mechanism for DETECTING AND CORRECTING ERRORS. Whenever an electromagnetic signal flows from one point to another, it is subject to unpredictable Types of interference from heat, magnetism, and other forms of electricity. This interference can change the shape Errors or timing of the signal. Error detection and correction are implemented either Single-Bit Burst at the data link layer or the transport layer of the OSI Error Error reference model. Error Detection and Correction | Types of Errors Types of Errors Single-Bit Burst Error Error Single-Bit Error Only one bit of a given data unit (such as a byte, character, data unit, or packet) is changed from 1 to 0 or from 0 to 1. The least likely type of error in serial data transmission. Sender sends data at 1 Mbps. Each bit lasts only 1/1,000,000 second or 1µsec. The noise must have a duration of only 1µsec, which is very rare. Happens if we are sending data using parallel transmission. If one of the wires is noisy, one bit of each byte will be corrupted. Error Detection and Correction | Types of Errors Types of Errors Single-Bit Burst Error Error Burst Error Two or more bits in the data unit have changed from 1 to 0 or from 0 to 1. Burst error does not necessarily mean that the errors occurs in consecutive bits. The length of the bursts is measured from the first corrupted bit to the last corrupted bit. Burst error is most likely to happen in a serial transmission. The duration of noise is normally longer than the duration of a bit. When noise affects data, it affects a set of bits. Number of bits affected depends on the data rate and duration of noise. Logical Link Control (LLC) | Error Detection Data Link Layer Logical Link Medium Access Control (LLC) Control (MAC) The central concept in detecting or correcting errors is REDUNDANCY. To be able to detect or correct errors, we need to send come 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. Send every data unit twice: Receiving device would then be able to do a bit-for-bit comparison. Any discrepancy would indicate an error and appropriate Including extra correction mechanism could be set in place. information is needed but need Completely accurate system but its would also be insupportably to add shorter SLOW. group of bits. Transmission time will be Double and also time to compare every unit bit by bit will slow the system. Extra bits are redundant to the information and they are discarded as soon as the accuracy of the transmission has been determined. Logical Link Control (LLC) | Error Detection Data Link Layer Logical Link Medium Access Control (LLC) Control (MAC) Redundancy Concept Data R 10100000010101010101010 S E Accept Reject E C E N I Redundant Bit Generator D V Checking E Function R E R 101001 10100000010101010101010 101001 Detection Types of Methods redundancy checks used in VRC LRC CRC Checksum VRC: Vertical Redundancy Check data LRC: Longitudinal Redundancy Check communication. CRC: Cyclic Redundancy Check Block Coding Error Detection | Vertical Redundancy Check (VRC) Detection Methods VRC LRC CRC Checksum Other name is Parity Check. A redundant bit (parity bit) is appended to every data unit so that the total number of 1s in the unit (including the parity bit) becomes EVEN (if even parity is being followed otherwise ODD). Most common and least expensive mechanism for error detection. Error Detection | Vertical Redundancy Check (VRC) Detection Methods VRC LRC CRC Checksum What if the data unit has been changed in transit? The receiver checks the parity at its end and it will know that an error has been introduced into data somewhere and therefore rejects the whole unit. VRC can detect all single-bit errors. It can also detect burst errors as long as the total number of bits changed is ODD.  Detection Error Detection | Longitudinal Redundancy Check (LRC) Methods VRC LRC CRC Checksum 1. A block of bits is organized in a table (rows and columns). 2. Calculate the parity bit for each column and create a new row of same number of bits, which are the parity bits for the whole block. 3. Attach the parity bits block (redundant) to the original data and send them to the receiver. LRC increases the likelihood of detecting burst errors.  Detection Error Detection | Longitudinal Redundancy Check (LRC) Methods VRC LRC CRC Checksum It two bits in one data unit are damaged and two bits in exactly the same positions in another data unit are also damaged, the LRC checker will not detect an error. 10101001 00111001 11011101 11100111 LRC Calculation at the Original Data Receiver Data sent to the Receiver LRC 1 0 1 0 1 0 0 1 10101001 00111001 11011101 11100111 10101010 1 0 1 0 0 0 1 1 0 0 1 1 1 0 0 1 0 0 1 1 0 0 1 1 Error introduced on Transit 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 10100011 00110011 11011101 11100111 10101010 1 1 1 0 0 1 1 1 1 1 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 LRC 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 Comparison MATCHED NO ERROR!  Detection Error Detection | VRC & LRC Methods VRC LRC CRC Checksum Two-dimensional Parity Code Data Blocks VRC 1 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 1 1 0 0 0 0 1 1 0 0 1 0 0 0 1 0 1 0 1 0 0 0 1 1 0 1 1 0 0 0 1 1 1 1 1 0 0 0 1 0 LRC 0 0 0 0 0 0 1 1 10000010 01000010 11000011 00100010 10100011 01100011 11100010 00000011 Data to be Sent  Detection Error Detection | VRC & LRC Methods VRC LRC CRC Checksum Hamming Distance The hamming distance between two words is the number of differences between corresponding bits. Codeword Sent Codeword Received The Minimum Hamming Distance is the smallest Hamming distance between all possible pairs of codewords. 0 0 0 0 1 0 0 1 0 0 1 1 1 0 1 0 Minimum Hamming Distance = 2 0 1 0 1 1 1 0 0 0 1 1 0 1 1 1 1  Detection Methods Error Detection | VRC & LRC VRC LRC CRC Checksum All possible 4 bits Datawords All valid Codewords 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 1 0 0 0 1 1 1 0 0 1 0 0 0 1 0 1 0 1 0 0 0 1 0 1 1 0 1 0 0 0 0 1 1 1 0 1 1 0 0 1 1 0 1 0 1 1 1 Even parity 0 1 0 0 1 1 0 0 0 1 0 0 1 1 1 0 0 0 0 1 0 1 1 1 0 1 0 1 0 1 0 1 1 0 1 1 0 1 1 0 1 1 1 0 0 1 1 0 0 1 1 1 0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 Minimum Hamming distance of any pair of the possible valid codewords = 2 The system can detect an error of = 1 bit only 1 1 0 0 0 0 1 0 0 0 1 1 0 0 0 0 1 1 0 0 To guarantee the detection of up to ‘s’ errors, the Minimum Hamming Distance in a block code must be (s+1). Error Detection | Cyclic Redundancy Check (CRC) Detection Methods VRC LRC CRC Checksum Most powerful of the redundancy check technique. VRC and LRC are based on addition. CRC is based on division. A sequence of redundant bits (called CRC remainder) is appended to the end of a data unit so that the resulting data unit becomes exactly divisible by a second, predetermined binary number. At the receiver end, the incoming data unit is divided by the same number. If at this step there is no remainder, the data unit assumed to be intact and is therefore accepted. The remainder indicates that the data unit has been damaged in transit and therefore must be rejected. Error Detection | Cyclic Redundancy Check (CRC) Detection Methods VRC LRC CRC Checksum Error Detection | Cyclic Redundancy Check (CRC) Detection Methods VRC LRC CRC Checksum Original data unit is (100100). A string of ‘n’ 0’s is appended to the original data unit. The number ‘n’ is one less than the number of bits in the pre-determined divisor (1101), which is n+1 bits. A CRC generator uses modulo-2 division. Binary division of elongated data unit (100100000) and divisor (1101). The remainder resulting from the division is CRC (001). 100100 001 Error Detection | Cyclic Redundancy Check (CRC) Detection Methods VRC LRC CRC Checksum The CRC divisor is most often represented as an POLYNOMIAL. The Polynomial should be selected to have at least the following properties: It should not be divisible by x. Guarantees that all burst errors of a length equal to the degree of the polynomial are detected. It should be divisible by (x+1). Guarantees that all burst errors affecting an odd number of bits are detected. Error Detection | Cyclic Redundancy Check (CRC) Detection Methods VRC LRC CRC Checksum CRC Division using Polynomial: Shifting left 3 bits: 1001 becomes 1001000. 𝑥 3 + 1 𝑏𝑒𝑐𝑜𝑚𝑒𝑠 𝑥 6 + 𝑥 3 Shifting left 3 bits: Multiply dataword with x3. Subtraction is in modulo-2. Error Detection | Cyclic Redundancy Check (CRC) Detection Methods VRC LRC CRC Checksum CRC Analysis Codeword Transmitted: 𝑪 𝒙 Imagine a transmission error (𝑬 𝒙 ) occurs. Those errors that are divisible by 𝑮 𝒙 are not Codeword Received: 𝑪 𝒙 + 𝑬 𝒙 caught; all other errors will be caught. Each 1 bit in 𝐸 𝑥 corresponds to a bit that has been inverted. If there are ‘k’ 1 bits in 𝐸 𝑥 , ‘k’ single-bit errors have occurred. 𝑪 𝒙 +𝑬 𝒙 𝑪 𝒙 𝑬 𝒙 On receipt of the data, it does the same modulo-2 division: = + 𝑮 𝑿 𝑮 𝒙 𝑮 𝒙 If the remainder is all 0’s, the CRC is dropped and the data accepted. Otherwise, the received stream of bits is discarded and data are resent.  Detection Methods Error Detection | Cyclic Redundancy Check (CRC) VRC LRC CRC Checksum Find the criteria that must be imposed on the generator (𝐺 𝑥 ) to detect the type of error to be detected. CASE – I: Single Bit Error Data: 1001 Divisor: 1011 Codeword Txed: 1001110 Codeword Rxed: 1011110 Divisor(𝐺 𝑥 ): 𝑥 3 + 𝑥 + 1 Error at 𝑥 4 bit. Structure of 𝐺 𝑥 to guarantee the detection of a single bit error: If a single bit error (say 𝐸 𝑥 = 𝑥 𝑖 ) is caught, then 𝐸 𝑥 is not divisible by 𝐺 𝑥. If 𝑮 𝒙 has at least two terms and the co-efficient of 𝒙𝟎 is not zero, then 𝐸 𝑥 cannot be divided by 𝐺 𝑥. Check for: 𝑮 𝒙 = (x+1) 𝑮 𝒙 = x3 Error Detection | Cyclic Redundancy Check (CRC) Detection Methods VRC LRC CRC Checksum CASE – II: Two Isolated Single Bit Errors Date: 1001 Divisor: 1011 Codeword Txed: 1001110 Codeword Rxed : 1101010 Divisor(𝐺 𝑥 ): 𝑥 3 + 𝑥 + 1 Error at 𝑥 5 + 𝑥 2 bit. Under what conditions can this type of error be caught? 𝐸 𝑥 = 𝑥 𝑗 + 𝑥 𝑖 = 𝑥 𝑖 𝑥 𝑗−𝑖 + 1 If 𝐺 𝑥 has more than one term and one term is 𝒙𝟎 , it cannot divide 𝑥 𝑖. If 𝐺 𝑥 is to divide 𝐸 𝑥 , it must divide 𝒙𝒋−𝒊 + 𝟏. In other words, 𝑮 𝒙 must not divide 𝒙𝒕 + 𝟏 , where ‘t’ is between 0 and n-1. t = 0 is meaningless. t = 1 is needed. Check for: 𝑮 𝒙 = (x+1) 𝑮 𝒙 = x +1 4 𝑮 𝒙 = x +x +1 7 6 Means ‘t’ should be between 2 and n-1. Error Detection | Cyclic Redundancy Check (CRC) Detection Methods VRC LRC CRC Checksum CASE – III: Odd Numbers of Errors A generator that contains a factor of (x+1) can detect all odd-numbered errors. Example: 𝑥 4 + 𝑥 2 + 𝑥 + 1 can catch all odd-numbered errors since it can be written as a product of the two polynomials 𝒙 + 𝟏 and 𝒙𝟑 + 𝒙𝟐 + 𝟏. Generator should not be only (x+1) - It cannot catch the two adjacent isolated errors. CASE – IV: Burst Errors 𝐸 𝑥 = 𝑥 𝑗 + ⋯ + 𝑥 𝑖 = 𝑥 𝑖 ∗ 𝑥 𝑗−𝑖 + ⋯ + 1 If the generator can detect a single error (minimum condition for a generator), then it cannot divide 𝑥 𝑖. 𝒙𝒋−𝒊 + ⋯ + 𝟏 must not be zero. 𝒙𝒓 + ⋯ + 𝟏 Error Detection | Cyclic Redundancy Check (CRC) Detection Methods 𝒙𝒋−𝒊 + ⋯ + 𝟏 VRC LRC CRC Checksum 𝒓 must not be zero. 𝒙 + ⋯+ 𝟏 𝒙𝟑 + 𝒙𝟐 + 𝟏 If (𝒋 − 𝒊) < 𝒓 :– The remainder can never be zero. 𝒙𝟒 + 𝒙𝟐 + 𝟏 All burst errors with length (L) ≤ the number of check bits ‘r’ will be detected. 𝒙𝟑 + 𝒙𝟐 + 𝟏 If 𝒋 − 𝒊 = 𝒓 :– In some rare cases, the syndrome is 0 and the error is undetected. 𝒙𝟑 + 𝒙𝟐 + 𝟏 The probability of undetected burst error of length (r+1) is: 𝟏Τ𝟐 𝒓−𝟏 𝒙𝟒 + 𝒙𝟐 + 𝟏 If 𝒋 − 𝒊 > 𝒓 :– The syndrome is 0 and the error is undetected. 𝒙𝟑 + 𝒙𝟐 + 𝟏 The probability of undetected burst error of length greater than (r+1) is : 𝟏Τ𝟐 𝒓 Generator: 𝑮 𝒙 = (𝑥 6 + 1) Can detect all burst errors with a length less than or equal to 6 bits. 3 out of 100 burst errors with length 7 will slip by. [0.55 = 0.03125] 16 out of 1000 burst errors with length 8 or more will slip by. [0.56 = 0.015625] Error Detection | Cyclic Redundancy Check (CRC) Detection Methods 𝒙𝒋−𝒊 + ⋯ + 𝟏 VRC LRC CRC Checksum 𝒓 must not be zero. 𝒙 + ⋯+ 𝟏 j = 12 i=8 Here, L = j – i + 1 = 12 – 8 + 1 = 5 All burst errors with 𝐿 ≤ 𝑟 will be detected. All burst errors with 𝐿 = 𝑟 + 1 will be detected with probability 1 − 1Τ2 𝑟−1. All burst errors with 𝐿 > 𝑟 + 1 will be detected with probability 1 − 1Τ2 𝑟. Error Detection | Cyclic Redundancy Check (CRC) Detection Methods VRC LRC CRC Checksum A good polynomial generator needs to have the following characteristics: It should have at least two terms. The co-efficient of the term 𝑥0 should be 1. It should not divide 𝑥𝑡 + 1, for ‘t’ between 2 and (𝑛 − 1). It should have the factor (𝑥 + 1). Standard Polynomial: CRC-8: 𝑥 8 + 𝑥 2 + 𝑥 + 1 CRC-10: 𝑥10 + 𝑥 9 + 𝑥 5 + 𝑥 4 + 𝑥 2 + 1 CRC-16: 𝑥16 + 𝑥12 + 𝑥 5 + 1 CRC-32: 𝑥 32 + 𝑥 26 + 𝑥 23 + 𝑥 22 + 𝑥16 + 𝑥12 + 𝑥11 + 𝑥10 + 𝑥 8 + 𝑥 7 + 𝑥 5 + 𝑥 4 + 𝑥 2 + 𝑥 + 1 Error Detection | Cyclic Redundancy Check (CRC) Detection Methods VRC LRC CRC Checksum Hardware Implementation of CRC Encoder and Decoder Encoder Decoder 1-bit Shift Register (n-k) Dataword has ‘k’ bits. CRC check has ‘n-k’ bits. Codeword has ‘n’ bits. Divisor has ‘n-k+1’ bits. XOR Device (n-k) Error Detection | Cyclic Redundancy Check (CRC) Detection Methods VRC LRC CRC Checksum Assume that the remainder is originally all 0s. At each time click (arrival of 1 bit from an augmented Dataword), repeat the following two actions: 1. Use the leftmost bit of the remainder to make a decision about the divisor (011 or 000). 2. The other 2 bits of the remainder and the next bit from the augmented dataword (total of 3 bits) are XORed with the 3-bit divisor to create the next remainder. Error Detection | Cyclic Redundancy Check (CRC) Detection Methods VRC LRC CRC Checksum Error Detection | Cyclic Redundancy Check (CRC) Detection Methods VRC LRC CRC Checksum Error Detection | Cyclic Redundancy Check (CRC) Detection Methods VRC LRC CRC Checksum Error Detection | Cyclic Redundancy Check (CRC) Detection Methods VRC LRC CRC Checksum  Detection Methods Error Detection | Checksum VRC LRC CRC Checksum Error-detecting technique that can be applied to a message of any length. Mostly used in Network and Transport layer rather than the data-link layer. Checksum Generator: At Sender Side Sub-divides the data unit into equal segments of ‘n’ bits. All segments are added together using 1’s complement arithmetic in such a way that the total is also ‘n’ bits long. Total sum is then complemented and appended to the end of the original data as redundant bits, called the checksum field. The extended data unit is transmitted across the network.  Detection Methods Error Detection | Checksum VRC LRC CRC Checksum Checksum Checker: At Receiver Side Sub-divides the received data unit into equal segments of ‘n’ bits. All segments are added together using 1’s complement arithmetic in such a way that the total is also ‘n’ bits long. Total sum is then complemented. No error -> New Checksum field should be ZERO. The receiver accepts the packet. Error -> New Checksum field should be NON-ZERO. The receiver rejects the packet. Error Detection | Checksum Detection Methods VRC LRC CRC Checksum Checksum Generator Transmitted Data 10011001 11100010 00100100 10000100 11011010 Checksum Error Detection | Checksum Detection Methods VRC LRC CRC Checksum Checksum Checker Received Data 10011001 11100010 00100100 10000100 11011010 Final Data after dropping Redundant Bits 10011001 11100010 00100100 10000100 Indicates no ERROR New Error Detection | Checksum Detection Methods VRC LRC CRC Checksum If the value of one word is incremented and the value of another word is decremented by the same amount, the two errors cannot be detected because the sum and checksum remain the same. Fletcher Checksum This method is devised to weight each data item according to its position. 8-bit Fletcher: It calculates on 8-bit data items and creates a 16-bit checksum. The calculation is done modulo 256 (28), which means the intermediate results are divided by 256 and the remainder is kept. Uses two accumulators: R & L. The first (R) simply adds a data items together and the second (L) adds a weight to the calculation. Error Detection | Checksum Detection Methods VRC LRC CRC Checksum Fletcher Checksum | Problem Identify the Fletcher checksum for the following data sequence: 2B, 3F, 6A and AF. Error Detection | Checksum Detection Methods VRC LRC CRC Checksum Adler Checksum It is a 32-bit checksum. It is similar to the 16-bit Fletcher Checksum with three differences: a) Calculation is done on single bytes instead of 2 bytes at a time. b) The modulus is a prime number (65,521) instead of 65,536. c) R is initialized to 1 instead of 0. It has been proved that a prime modulo has a better detecting capability in some combinations of data. Error Detection | Checksum Detection Methods VRC LRC CRC Checksum Adler Checksum | Problem Identify the Adler checksum for the following string: Eagles are great! Logical Link Control (LLC) | Error Correction Data Link Layer Medium Logical Link Access Control Control (LLC) (MAC) Error correction can be handled in two ways: When an error is discovered, the receiver can request the sender to retransmit the entire data unit. The receiver can use an error-correcting code, which automatically corrects certain errors. Error correcting codes are more sophisticated than error-detection codes and require more redundancy bits. Most error correction is limited to one, two or three-bit errors. Logical Link Control (LLC) | Error Correction Data Link Layer Logical Link Medium Access Control (LLC) Control (MAC) Single-Bit Error Correction VRC can be used to detect a single-bit error in the received frame. BUT the major concern is to locate the invalid bit. To correct a single-bit error in an ASCII character, the error correction code must determine which of the seven bits has changed. This requires enough redundancy bits to show all eight states (No Error, Error in position 1 to 7). A three-bit redundancy code should be adequate and can therefore indicate the locations of eight different possibilities. What if an error occurs in redundancy bits themselves? Additional bits are necessary to cover all possible error locations. Error Correction | Single-Bit Error Correction Data Link Layer Logical Link Medium Access Control (LLC) Control (MAC) If the total number of bits in a transmittable unit is (𝒎 + 𝒓), then ‘r’ must be able to indicate at least (𝒎 + 𝒓 + 𝟏) different states. ‘r’ bits can indicate 2r different states. Therefore, 𝟐𝐫 ≥ 𝐦 + 𝐫 + 𝟏 If the value of ‘m’ is 7, the smallest ‘r’ value that can satisfy the above equation will be 4: 𝟐𝟒 ≥ 𝟕 + 𝟒 + 𝟏 Error Correction | Single-Bit Error Correction Data Link Layer Logical Link Medium Access Control (LLC) Control (MAC) How do we manipulate those bits to discover which state has occurred? Hamming Code The Hamming code can be applied to data units of any length and uses the relationship between data and redundancy bits. Example: A 7-bit ASCII code requires 4 redundancy bits that can be added to the end of the data unit or interspersed with the original data bits. The redundant bits are placed in positions 1, 2, 4, and 8 (the positions in an 11-bit sequence that are powers of 2). Error Correction | Single-Bit Error Correction Data Link Layer Logical Link Medium Access Control (LLC) Control (MAC) 4th 3rd 2nd 1st Each ‘r’ bit is the VRC bit for one combination of data units. The combinations used to calculate each of the four ‘r’ values (r1, r2, r3, r4) for a 7-bit data sequence are as follows: 1 3 5 7 9 11 4 5 6 7 r1 0001 0011 0101 0111 1001 1011 r4 0100 0101 0101 0111 Check for availability of ‘1’ at 1st place. Check for availability of ‘1’ at 3rd place. 2 3 6 7 10 11 8 9 10 11 r2 0010 0011 0110 0111 1010 1011 r8 1000 1001 1010 1011 Check for availability of ‘1’ at 2nd place. Check for availability of ‘1’ at 4th place. Each data bit may be included in more than one VRC calculation. Each of the ‘m’ bits is included in at least two sets, while the ‘r’ bits are included in only one. Error Correction | Single-Bit Error Correction Data Link Layer Logical Link Medium Access Control (LLC) Control (MAC) Original Data (m) = 1001101 1 0 0 1 1 0 1 11 10 9 8 7 6 5 4 3 2 1 Adding r1: 1 0 0 1 1 0 1 r1 = 1 E 11 10 9 8 7 6 5 4 3 2 1 V E Adding r2: 1 0 0 1 1 0 1 1 r2 = 0 N 11 10 9 8 7 6 5 4 3 2 1 P A Adding r4: 1 0 0 1 1 0 1 0 1 r4 = 0 R 11 10 9 8 7 6 5 4 3 2 1 I T Adding r8: 1 0 0 1 1 0 0 1 0 1 r8 = 1 Y 11 10 9 8 7 6 5 4 3 2 1 Code (m+r) = 10011100101 Error Corr