EE 122: Error detection and reliable transmissionHigh Level ViewOverviewError DetectionTwo-dimensional ParityHow Many Errors Can you Detect?Slide 7Slide 8Slide 9Checksum1’s Complement RevisitedCyclic Redundancy Check (CRC)Some Polynomial Arithmetic Modulo 2 PropertiesComputing T(x)CRC PropertiesSlide 16Reliable TransmissionLatency, Bandwidth, Round-Trip TimeAutomatic Repeat Request (ARQ) AlgorithmsStop-and-GoWhat Can Go Wrong?Stop-and-Go DisadvantageStop-and-Go Disadvantage (cont’d)SolutionSliding Window Protocol: SenderExampleSliding Window Protocol: ReceiverSlide 28Properties of ARQ ProtocolsSummaryEE 122: Error detection and reliable transmissionIon StoicaSeptember 16, [email protected] 2High Level ViewGoal: transmit correct informationProblem: bits can get corrupted-Electrical interference, thermal noiseSolution-Detect errors-Recover from errors •Correct errors•[email protected] 3OverviewError detectionReliable [email protected] 4Error DetectionProblem: detect bit errors in packets (frames)Solution: add redundancy bits to each packetGoals: -Reduce overhead, i.e., reduce the number of redundancy bits-Increase the number and the type of bit error patterns that can be detectedExamples:-Two-dimensional parity-Checksum-Cyclic Redundancy Check (CRC)[email protected] 5Two-dimensional ParityAdd one extra bit to a 7-bit code such that the number of 1’s in the resulting 8 bits is even (for even parity, and odd for odd parity)Add a parity byte for the packetExample: five 7-bit character packet, even parity 01101001011010001011011101011001011101101000110 [email protected] 6How Many Errors Can you Detect?All 1-bit errorsExample:01101001011010000011011101011001011101101000110 1error bitodd number of 1’[email protected] 7How Many Errors Can you Detect?All 2-bit errorsExample:011010010110100000111 11101011001011101101000110 1error bitsodd number of 1’s on [email protected] 8How Many Errors Can you Detect?All 3-bit errorsExample:011010010110100000111 11001011001011101101000110 1error bitsodd number of 1’s on [email protected] 9How Many Errors Can you Detect?Most 4-bit errorsExample of 4-bit error that is not detected:011010010110100000111 11001001001011101101000110 1error bitsHow many errors can you [email protected] 10ChecksumSender: add all words of a packet and append the result (checksum) to the packetReceiver: add all words of a packet and compare the result with the checksumCan detect all 1-bit errorsExample: Internet checksum-Use 1’s complement [email protected] 111’s Complement RevisitedNegative number –x is x with all bits invertedWhen two numbers are added, the carry-on is added to the resultExample: -15 + 16; assume 8-bit representation15 = 00001111 -15 = 1111000016 = 00010000+00000000 1+100000001 -15+16 = [email protected] 12Cyclic Redundancy Check (CRC)Represent a (n+1)-bit message by an n-degree polynomial M(x)-E.g., 10101101 M(x) = x7 + x5 + x3 + x2 + x0Choose a divisor k-degree polynomial C(x)Compute reminder R(x) of M(x)*xk / C(x), and then compute T(x) = M(x)*xk - R(x)-T(x) is divisible by C(x)-First n coefficients of T(x) represent M(x) Sender: -Compute and send T(x), i.e., the coefficients of T(x)Receiver: -Let T’(x) be the (n+k)-degree polynomial generated from the received message-If C(x) divides T’(x) no errors; otherwise [email protected] 13Some Polynomial Arithmetic Modulo 2 Properties If C(x) divides B(x), then degree(B(x)) >= degree(C(x))Subtracting C(x) from B(x) reduces to perform an XOR on each pair of matching coefficients of C(x) and B(x)-E.g.: B(x) = x7 + x5 + x3 + x2 + x0 10101101 C(x) = x3 + x1 + x0 00001011 B(x) - C(x) = x7 + x5 + x2 + x1 [email protected] 14Computing T(x)Compute the reminder R(x) of M(x)*xk / C(x)T(x) = M(x)*xk - R(x)Example: send packet 110111, assume C(x) = 101-k = 2, M(x)*xK 11011100 -Compute R(x) -T(x) = M(x)*xk - R(x) 11011100 xor 1 = 11011101 101) 11011100 101 111 101 101 101 100 101 1R(x)[email protected] 15CRC PropertiesDetect all single-bit errors if coefficients of xk and x0 of C(x) are oneDetect all double-bit errors, if C(x) has a factor with at least three termsDetect all number of odd errors, if C(x) contains factor (x+1) Detect all burst of errors smaller than k [email protected] 16OverviewError detectionReliable [email protected] 17Reliable TransmissionProblem: obtain correct information once errors are detectedSolutions:-Use error correction codes (can you give an example of error detection code that can also correct errors?)-Use retransmission (we’ll do this in details)Algorithmic challenges: -Achieve high link utilization, and low [email protected] 18Latency, Bandwidth, Round-Trip TimeLatency = propagation + transmit + queue-Propagation: time it takes the signal to propagate along the link-Transmit: time it takes to transmit the packet = (packet_size)/(link_bandwidth)-Queue: time for which the packet waits into the adapter at the sender before being transmittedNote: next we’ll assume short packets, i.e, transmit term can be neglected !Round-Trip Time (RTT) = time it takes to a packet to travel from sender to destination and back-RTT = one-way latency from sender to receiver + one-way latency from receiver to [email protected] 19Automatic Repeat Request (ARQ) AlgorithmsUse two basic techniques: -Acknowledgements (ACKs)-TimeoutsTwo examples:-Stop-and-go-Sliding [email protected] 20Stop-and-GoReceiver: send an acknowledge (ACK) back to the sender upon receiving a packet (frame)Sender: excepting first packet, send a packet only upon receiving the ACK for the previous packetTimeSender [email protected] 21What Can Go Wrong?Sender ReceiverframeframeACKTimeoutFrame lost resent it on TimeoutSender ReceiverframeframeACKACKTimeoutACK lost resent packet Need a mechanisms todetect duplicate packetSender ReceiverframeframeACKACKTimeoutACK delayed resent packet Need a bit to differentiate between ACK for currentand previous
View Full Document
Unlocking...