Error Sources, Detection and Correction

Error Sources, Detection and Correction The Data Link Layer [Ref: Chap-5 Fitzgerald & Dennis, Chap-5 p.142 Stallings] Error Control In Networks: Network errors are in the form of corrupted data or lost data. Network errors occur naturally on all networks due to electrical noise and distortion and must be detected and corrected by either hardware or software. Bit Error Rates (BERs) are calculated as the number of bits in error divided by the number of bits transmitted. A BER of 1 in 100,000 might be shown as 1:105 or simply as a BER of 10-5. Errors often occur in bursts where many bits in a sequence will be in error. What are Network Errors and What Causes Errors? Noise is any form of undesirable electrical signals introduced by equipment or natural disturbances (lightening). Noise has the effect of causing bits to change state, extra bits or missing bits resulting in errors in a message. Forms of Line Noise and Distortion: White Noise Caused by the thermal agitation of electrons in all matter. Always present (like the background hiss on radios) but not usually a problem unless the signal itself is very weak. Impulse Noise Noise spikes (large voltage fluctuations on the line) are a primary source of errors. Caused by telephone system equipment, lightening, fluorescent lights, poor electrical connections, etc. A 1/100 second voltage spike would damage at least 144 bits if transmission was at 14,400 bps. Cross-talk Signals picked up on one circuit from adjacent circuits. (We often hear this in voice telephone calls when we hear a faint conversation going on in the background.) Intermodulation Noise A special type of crosstalk. The signals from two circuits combine to form a new signal that falls into a frequency band reserved for another signal. Similar to harmonics in music. Echoes and Echo Suppression Echo suppressers are used in the telephone system on long distance calls. Echoes are caused by impedance mismatches in the telephone equipment. Modems automatically disable echo suppressers so they can communicate in full duplex. Echoes can sometimes be strong enough to cause data errors. Attenuation Attenuation is the loss of power or signal strength as signals travel from a transmitting device to a receiving device. Weaker signals are more subject to errors. Attenuation Distortion Not all signal frequencies are attenuated the same amount; high frequencies are attenuated more than low frequencies. This distortion can cause errors. Delay distortion Distortion caused by the fact that different frequencies travel through the cable at slightly different speeds. Jitter Phase jitter refers to small fluctuations in the phase of a carrier signal. If some form of phase modulation is being used by a modem (and most do) then this jitter will incorrectly add to the natural phase shift used by the modem for sending different bit patterns, resulting in errors. Harmonic distortion Distortion introduced by amplifiers on a circuit. Line outages Failure of a communication circuit for a brief period of time resulting in a major loss of data. Caused by telephone system equipment failure or power outages. Error Prevention: Shielding (p.140) Covering a cable or equipment with a grounded metallic conductor shields it from electrical noise, and prevents it from generating any noise as well. Moving Cables Relocating cables away from sources of noise (like power cables, fluorescent lights, and electrical machinery) Changing Multiplexing Techniques - changing frequencies or guard bands. Improving Connection Quality Amplifiers and Repeaters Amplifiers are used on analog phone lines to overcome attenuation. Digital Repeaters are used on digital phone lines. Repeaters and amplifiers placed closer together will improve signal quality. Equalization Equalizers are devices that compensate for attenuation and delay distortion. They can be built into leased phone lines and are built into most modems to improve error rates. Conditioning Leased private lines can be conditioned (at a cost) using many of the techniques described above, to lower error rates. Error Detection: Error detection involves sending extra information with a message (frame, packet, block, etc.) which is used by the receiver to determine whether the data has been received correctly and is complete. Usually some type of calculation is performed on the data by the transmitter. The receiver performs the same calculation on the received data and if the two results are identical it assumes the data is correct. Error Correction: If the data has an error, a short message (NAK or Negative Acknowledgment) must be sent back to the transmitter requesting that the entire message be retransmitted. Forward Error Correction involves sending sufficient redundant information in the original transmission that errors can be corrected at the receiver without requiring retransmission. Error Detection Methods: Parity Checking The oldest, simplest and least effective method of error detection is parity checking. One additional bit is added to each byte transmitted, based on even (total number of 1 bits must be an even number) or odd (total number of 1 bits is an odd number) parity. Even parity - total number of '1's must be an even number Odd parity - total number of '1's must be an odd number Detects single bit errors (or any odd number of errors) but cannot detect 2, 4 or 6 bits (any even number of errors) in error. This results in a very poor error detection rate of about 50%. ASCII Parity Odd Parity ‘D’ 1000100 1 Even Parity ‘D’ 1000100 0 Odd Parity ‘D’ 1000101 1 <== bit 0 damaged (Parity violation detected) Odd Parity ‘D’ 1000111 1 <== bits 0 and 1 damaged (Parity violation NOT detected) LRC: Longitudinal Redundancy Checking LRC adds an additional character, the Block Check Character (BCC) to the end of the message or block of data. The BCC uses parity on each bit position for each character in the message; in other words, by determining parity on the first bit of each character and setting the first bit of the BCC to that value; then determining parity on the second bit of each character, etc. Has an improved error detection rate of more than 98%. Letter ASCII Parity Bit D 1000100 1 A 1000001 1 T 1010100 0 A 1000001 1 BCC 1101111 1 Polynomial Checking Checksum A checksum is calculated by adding up the decimal value of each character in the message, dividing the sum by 255 and using the remainder as the checksum to be transmitted with the message. The receiver calculates its own checksum and compares it with the one sent. If they are the same, it assumes there are no errors. It is able to detect errors about 95% of the time. (Still not very good). CRC: Cyclic Redundancy Checking (Best Method **) This method is used for most network error detection today. An 8, 16, 24 or 32 bit number is added to the end of the data. Known as CRC-8, CRC-16, CRC-24 or CRC-32 based on the number of bits used. All of the data in the message is processed according to a mathematical algorithm (A polynomial is divided by a prime number resulting in a quotient and a remainder. Uses a "linear feedback shift register", normally implemented with hardware to generate a unique 16 or 32 bit remainder based on the data that was sent. ) The remainder is transmitted as the CRC code. The receiver processes the incoming data using the same algorithm and then compares it’s CRC with the one transmitted. If they are the same, the data must be correct. CRC-16 detects 99.99% errors; that is 1 in 10,000 errors goes undetected. CRC-32 is extremely proficient in detecting errors; approximately 1 in 1014 errors go undetected. If transmitting at 9600 bps, 24 hours a day, 365 days a year, it would take 3000 years for a single undetected error to occur. Ethernet Local Area Networks use a 32-bit CRC code. Error Correction via Retransmission: Except for simple asynchronous transmission, most data is sent in frames or packets (Fig 5-12) synchronously. When a packet is received with errors in it, some method must be established to correct the error. The simplest way of dealing with errors is to ask the sender to retransmit the original frame or packet. This method is called ARQ (Automatic Repeat Request). Two variations of ARQ are: Stop and Wait ARQ (Fig 5-4) This is a very slow method, essentially a half-duplex communication method. The sender must stop and wait after sending each packet of data for either an ACK (positive acknowledgment) or a NAK (negative ack) to come back from the receiver. If an error occurred, a NAK is sent and the packet is retransmitted. The sender spends a lot of time waiting. Continuous ARQ (Fig 5-5) a much more efficient method of error handling which communicates in full duplex. The sender does not wait for an acknowledgment before sending the next packet. Acknowledgments must arrive at the sender before a certain number of packets have been sent; this number is the window size. The receiver sends back an ACK or a NAK every so often. This ACK acknowledges all packets received since the last ACK. It must include a packet sequence number so it can identify which packets are being acknowledged. When a NAK is received, the sender must retransmit packets starting from that packet number. Two methods are used: LAP-M: Link Access Protocol for Modems which requires that only the packet containing the error needs to be re-transmitted. (Most efficient) GO-BACK-N ARQ: Must re-transmit all packets starting from the one with the error in it. Sliding window methods are used by many file transfer protocols such as zmodem. Forward Error Correction: Forward Error Correction adds sufficient redundancy to a message so it can detect and correct errors at the receiver without having to retransmit. If a system used 100% redundancy in a message, essentially everything would be sent twice. Typical Forward Error Correction methods add 25% additional bits to a transmission. V.32 and V.34 modems use Forward Error Correction (V.42) Various methods exist: Hagelbarger Code: corrects up to 6 consecutive bit errors provided such a group is followed by al least 19 valid bits before more errors occur. Bose-Chaudhuri code: can correct double-bit errors and detect up to 4 errors. Hamming Codes: See example on p.145 and Figure 5-6.