Let's go back to Error control first, and let's discuss the technique known as CRC. Using CRC has a stronger error detection than checksum. CRC is also known as polynomial code, and treats bit strings as polynomials with coefficients of 0 and 1. For example, 1101 maps to (1.x^3 + 1.x^2 + 0.x^1 + 1.x^0) = x^3 + x^2 + 1. The sender and receiver agree on generator polynomial and adds bits so transmitted frame viewed as polynomial is evenly divisible by G(x). For example ethernet goes to x^32 since it is 32 bits. Therefore, ethernet uses 4 bytes of sequencing.
There is modulo 2 arithmetic in polynomial arithmetic. Addition/subtraction identical to XOR, and Division is identical to binary division Mod 2. Let r be the degree of G(x) and I expect r bits for redundancy and CRC. The message to transfer has M bits of data with R bits of CRC. It is represented by x^r * M(x). The R 0's that have appended, we will try to figure out what the value of the R bits should before the CRC.
Let r be the degree of G(x). Append r zero bits to the end of the frame M(x) of m bits. Result has m + r bits and corresponds to polynomial of x^r * M(x). We then divide x^r * M(x) by G(x). I finally have to subtract the remainder from x^r M(x). The result, T(x) is the check sum frame to be transmitted. Such is the CRC sender algorithm.
Let's consider example. Consider frame M(x) = 1101011111 and Generator is x^4 + x + 1 and binary is 1 0 0 1 1. Now all the coefficient are 0's except for the constant. If G(x) is 10011, we divide the entire message by G(x) number and we are going to get a quotient and a remained (2 bits). Once I get the remainder, I can use it to get the four 0's replaced at the end.
Interesting part is we want to show properties of this CRC computation. The receiver will get (T(x) + E(x)) / G(x). Since T(x)/G(x) = 0, then the receiver computes E(x) / G(x). Errors are not detected if E(x)/G(x) = 0 which means that there is no remainder.
Let's investigate if CRC detects single-bit errors. Here, E(x) = x^i and if G(x) contains 2 or more terms it will never divide E(x) so as a result, all single bit errors will be detected. E(x) = x^i + x^j where i > j. It can be rewritten as E(x) = x^j(x^(i-j) + 1). If we assume G(x) does not divide x then errors will be detected if G(x) does not divide x^k + 1 for all k up to i 32- j. For example, x^15 + x^14 + 1 does not divide x^k +1 for valeu of k below 32,768, or x^15. We just want to see if E(x) is divisible by G(x), or the generator. As long as I now G(x) has 2 terms then I know it will never divide by x^j. Interestingly, no polynomial with odd number of terms has (x + 1) as a factor in the mod 2 system. By making (x + 1) as a factor of G(x) we catch all errors with odd number of inverted bits.
Let's identify another rule. This time, set E(x) = x^i(x^k-1 + ... + 1) where i determines how far from the right the burst is located if we have burst errors of r buts. If G(x) has an x^0 term then x^i will not have G(x) as a factor. Now if degree of G(x) is larger than degree of (x^k-1 + ... + 1) then the (x^ k - 1 + ... + 1) will not have G(x) as a factor. Now if G(x) has x^0 term and G(x) has large degree as mentioned before, then the bursts of size r will be successfully detected.
Now, let's go through flow control. Layer 2 gets a packet from the network layer, will do framing and addressing, then deploy some service, error detection/correction (ethernet uses CRC) then finally deploy some logic. I have to be able to detect errors to retransmit whatever I send. Flow control is about the one link we are sending. I am trying in layer 2 to adjust the rate to make the next hub "happy".
Since we're still talking about communication we have point-to-point channels (dedicated to connections between these 2 devices) and Multi-access channels. With point-to-point, we don't have to deal with interference. Multi-access channels need media access codes to see if the transmission will collide or not. These point to point channels can be assumed as lossless, without thinking about the possibility of collision/contention. You can think of old ethernet as Multi-access channels and switch ethernet as point-to-point channels. We wanna do flow control over this point-to-point channel, reacting to errors and flow control naturally without having issue with the next hub.
Utopian Simplex protocol, assumes there are no errors in the point to point link between the 2 devices, and the receiver is fast at processing the packet as it makes it to its end. The receiver is at least as fast as the sender. The sender can simply blast frames and the receiver "eats" them. This is in an ideal situation.
Another protocol is the stop and wait flow control protocol in an error-free channel. This assumes that the channel is noisy so there could be errors. Simple stop-and-wait assumes that there is no error on the channel. In practice, though there are lossless channels (for example in datacenters some channels are assumed to be lossless). You want point-to-point links that can process very high speed amount of data. The stop-and-wait error free channel will make sure sender doesn't outpace the receiver. So I first send the packet, then wait for acknowledgement in receiver (dummy acknowledgement). Receiver sends dummy ACK in response to a received frame and when ready to receive extra frames. The receiver sends the dummy ACK when it is ready, waiting for the ACK coming back from the receiver. The Receiver also passes ack to different layer.
Let's see how the sender can adjust its rate to make sure that the frames are retransmitted. At the same time, I don't want the sender to overwhelm the receiver. The stop-and-wait noisy channel is when frames can be lost-dropped or delivered with bit errors, and it adds error control in addition to flow control.
In Error control, the sender sends one packet at a time and waits for a positive ACK, and the receiver sends a positive ACK when the frame is correctly received and none when frame isn't correct. The protocols in which the sender waits for ACK before advancing are ARQ (automatic Repeat Request) or PAR (Positive ACK with Retransmission). ACKs can also be lost or messed up. We need retransmission timers and sequence numbers once we start dealing with errors. Retransmission timer is how the sender will know its needs to transmit, or that it can send a new frame. Distinguishing frame number from duplicate retransmission would use Sequence Numbers.
So again a sequence number and retransmission timer is associated with each frame. In a stop-and-wait protocol, a 1 bit sequence number is sufficient. The sender sends one frame at a time, and waits for an acknowledgement or for timer to expire. If it is an acknowledgement, send a new frame, but retransmit old frame if the timer expires.
On the receiver side, you receive the frame, check for correctness, if the receiver is new and frame is correct, send acknowledgement, else if the sequence number is not correct/expected then don't send the acknowledgement.
The blue is the retransmission. You don't need the sequence number to be large in size (can be binary value). Other protocols would require sequence number of some size. Else, there will be problems. If you set a timer to long amount of time, when packets happen you're not going to respond well. Timers can't be too fast either. Today's internet speed is in Gbps. Stop and wait is not great at utilizing the channel bandwidth/capacity.
Comments
Post a Comment