EE 122 Error detection and reliable transmission Ion Stoica September 16 2002 High Level View Goal transmit correct information Problem bits can get corrupted Electrical interference thermal noise Solution Detect errors Recover from errors Correct errors Retransmission istoica cs berkeley edu 2 Overview Error detection Reliable transmission istoica cs berkeley edu 3 Error Detection Problem detect bit errors in packets frames Solution add redundancy bits to each packet Goals Reduce overhead i e reduce the number of redundancy bits Increase the number and the type of bit error patterns that can be detected Examples Two dimensional parity Checksum Cyclic Redundancy Check CRC istoica cs berkeley edu 4 Two dimensional Parity Add 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 packet Example five 7 bit character packet even parity 0110100 1 1011010 0 0010110 1 1110101 1 1001011 0 1000110 1 istoica cs berkeley edu 5 How Many Errors Can you Detect All 1 bit errors Example 0110100 1 1011010 0 0000110 1 1110101 1 1001011 0 1000110 1 odd number of 1 s error bit istoica cs berkeley edu 6 How Many Errors Can you Detect All 2 bit errors Example 0110100 1 1011010 0 0000111 1 1110101 1 1001011 0 1000110 1 error bits odd number of 1 s on column istoica cs berkeley edu 7 How Many Errors Can you Detect All 3 bit errors Example 0110100 1 1011010 0 0000111 1 1100101 1 1001011 0 1000110 1 error bits odd number of 1 s on column istoica cs berkeley edu 8 How Many Errors Can you Detect Most 4 bit errors Example of 4 bit error that is not detected 0110100 1 1011010 0 0000111 1 1100100 1 1001011 0 1000110 1 error bits How many errors can you correct istoica cs berkeley edu 9 Checksum Sender add all words of a packet and append the result checksum to the packet Receiver add all words of a packet and compare the result with the checksum Can detect all 1 bit errors Example Internet checksum Use 1 s complement addition istoica cs berkeley edu 10 1 s Complement Revisited Negative number x is x with all bits inverted When two numbers are added the carry on is added to the result Example 15 16 assume 8 bit representation 15 00001111 15 11110000 16 00010000 15 16 1 1 00000000 1 00000001 istoica cs berkeley edu 11 Cyclic 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 x0 Choose 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 no errors otherwise errors If C x divides T x istoica cs berkeley edu 12 Some 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 C x x3 x1 x0 B x C x x7 x5 x2 x1 istoica cs berkeley edu 10101101 00001011 10100110 13 Computing 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 Compute R x 11011100 101 11011100 101 111 101 101 101 100 101 1 T x M x xk R x R x 11011100 xor 1 11011101 istoica cs berkeley edu 14 CRC Properties Detect all single bit errors if coefficients of xk and x0 of C x are one Detect all double bit errors if C x has a factor with at least three terms Detect all number of odd errors if C x contains factor x 1 Detect all burst of errors smaller than k bits istoica cs berkeley edu 15 Overview Error detection Reliable transmission istoica cs berkeley edu 16 Reliable Transmission Problem obtain correct information once errors are detected Solutions 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 overhead istoica cs berkeley edu 17 Latency Bandwidth Round Trip Time Latency 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 transmitted Note 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 oneway latency from receiver to sender istoica cs berkeley edu 18 Automatic Repeat Request ARQ Algorithms Use two basic techniques Acknowledgements ACKs Timeouts Two examples Stop and go Sliding window istoica cs berkeley edu 19 Stop and Go Receiver 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 packet Sender Receiver Time frame ACK frame ACK istoica cs berkeley edu 20 What Can Go Wrong Receiver Sender Receiver Sender frame Timeout frame ACK Receiver frame Timeout Sender K AC frame frame frame ACK ACK ACK Frame lost on Timeout resent it ACK lost resent packet ACK delayed resent packet Need a mechanisms to detect duplicate packet Need a bit to differentiate between ACK for current and previous packet istoica cs berkeley edu 21 Stop and Go Disadvantage May lead to inefficient link utilization Example assume One way propagation 15 ms Bandwidth 100 Mbps Packet size 1000 bytes transmit 8 1000 108 0 08ms Neglect queue delay Latency approx 15 ms RTT 30 ms Propagation 15 ms Bandwidth 100 Mbps istoica cs berkeley edu 22 Stop and Go Disadvantage cont d Send a message every 30 ms Throughput 8 1000 0 03 0 2666 Mbps Thus the protocol uses less than 0 3 of the link capacity Sender Receiver 30 ms frame ACK 30 ms frame ACK istoica cs berkeley edu 23 Solution Don t wait for the ACK of the previous packet before sending the next one istoica cs berkeley edu 24 Sliding Window Protocol Sender Each packet has a sequence number Assume infinite sequence numbers for simplicity Sender maintains a window of sequence numbers SWS sender window size maximum number of packets that can be sent without receiving an ACK LAR last ACK received LFS last frame sent Acknowledged packets LAR Packets …
View Full Document
Unlocking...