Introduction to Computer Networks CMPE 150 Fall 2005 Lecture 11 CMPE 150 Introduction to Computer Networks 1 Announcements No labs this week Except for make up sessions Homework 2 is up Due 10 24 Graded homework 1 is back Midterm on 10 28 CMPE 150 Introduction to Computer Networks 2 Last Class Started DLL layer 2 Functionality Error control Flow control Framing Different approaches Counters Flag byte Byte stuffing Bit stuffing CMPE 150 Introduction to Computer Networks 3 Reading Assignment Tanenbaum Chapter 3 CMPE 150 Introduction to Computer Networks 4 Today Layer 2 cont d CMPE 150 Introduction to Computer Networks 5 Error Control CMPE 150 Introduction to Computer Networks 6 Error Control Reliable delivery Hop by hop Detecting errors Detecting and correcting errors CMPE 150 Introduction to Computer Networks 7 Acknowledgments Special control info in the case of the DLL control frame acknowledging receipt of data Positive and negative ACKs ACKs NACKs Are ACKs sufficient CMPE 150 Introduction to Computer Networks 8 Reliable Delivery Timers Retransmission Duplicate detection CMPE 150 Introduction to Computer Networks 9 Flow Control Handles mismatch between sender s and receiver s speed Receiver s buffer limitation Feedback based flow control Explicit permission from receiver Rate based flow control Implicit mechanism for limiting sending rate DLL typically uses feedback based flow control CMPE 150 Introduction to Computer Networks 10 Error Detection and Correction Add control information to the original data being transmitted Error detection enough info to detect error Need retransmissions Error correction enough info to detect and correct error A k a forward error correction FEC CMPE 150 Introduction to Computer Networks 11 Why Error detection versus error correction Cost efficiency Environment Application CMPE 150 Introduction to Computer Networks 12 What s an error Frame m data bits r bits for error control n m r Given the original frame f and the received frame f how many corresponding bits differ Hamming distance Hamming 1950 CMPE 150 Introduction to Computer Networks 13 Hamming Distance Examples CMPE 150 Introduction to Computer Networks 14 Hamming Distance If f and f are Hamming distance of d apart there needs to be d single bit errors to convert f to f Error detecting correcting properties of a code depend on the code s Hamming distance To detect d errors need code with Hamming distance d 1 Need d 1 single bit errors to change a valid f to a valid f If receiver sees invalid f it knows an error occurred CMPE 150 Introduction to Computer Networks 15 Parity Bit Simple error detecting code Even or odd parity Example Transmit 1011010 Add parity bit 1011010 0 even parity or 1011010 1 odd parity Code with single parity bit has Hamming distance of 2 Any single bit error produces frame with wrong parity CMPE 150 Introduction to Computer Networks 16 Error Correcting Codes To correct d errors need 2d 1distance code Code words are 2d 1 apart With d changes original frame is closer than any other valid frame CMPE 150 Introduction to Computer Networks 17 Error Correction Example Suppose code with 4 valid words 0000000000 0000011111 1111100000 1111111111 Hamming distance is 5 Possible to correct double errors Example If 0000000111 arrives at receiver receiver assumes original must have been 0000011111 But if triple error changes 0000000000 into 0000000111 not able to correct it properly CMPE 150 Introduction to Computer Networks 18 Hamming Code Bits in positions that are power of 2 are check bits The rest are data bits Each check bit used in parity even or odd computation of collection of bits Example check bit in position 11 checks for bits in positions 11 1 2 8 Similarly bit 11 is checked by bits 1 2 and 8 CMPE 150 Introduction to Computer Networks 19 Hamming Code Example 7 bit Hamming codes can only correct single errors CMPE 150 Introduction to Computer Networks 20 Error Detecting Codes Typically used in reliable media Examples parity bit polynomial codes a k a CRC or Cyclic redundancy Check CMPE 150 Introduction to Computer Networks 21 Polynomial Codes Treat bit strings as representations of polynomials with coefficients 1 s and 0 s K bit frame is coefficient list of polynomial with k terms and degree k 1 from xk 1to x0 Highest order bit is coefficient of xk 1 etc Example 110001 represents x5 x4 x0 Generator polynomial G x Agreed upon by sender and receiver CMPE 150 Introduction to Computer Networks 22 CRC Checksum appended to frame being transmitted Resulting polynomial divisible by G x When receiver gets checksummed frame it divides it by G x If remainder then error CMPE 150 Introduction to Computer Networks 23 Cyclic Redunancy Check At Transmitter with M 1 1 1 0 1 1 compute 2rM 1 1 1 0 1 1 0 0 0 with G 1 1 0 1 T 2 rM R note G starts and ends with 1 Transmit R 111 T 1 1 1 0 1 1 1 1 1 CMPE 150 Introduction to Computer Networks 24 Cyclic Redundancy Check At the Receiver compute Note remainder 0 no errors detected CMPE 150 Introduction to Computer Networks 25 CRC Performance Errors go through undetected only if divisible by G x With suitably chosen G x CRC code detects all single bit errors And more CMPE 150 Introduction to Computer Networks 26 More on CRC CMPE 150 Introduction to Computer Networks 27
View Full Document
Unlocking...