Sunday, 1 September 2019

Controlling the Flow

Once again we seem to be going over some old ground, particularly the second half of my post on the Intricacies of data transfer. However, there are a number of things that weren't discussed, and this is what we will be looking at, namely error control and flow control.

Both of these functions occur on the data link layer, which is a layer on the OSI model that exists above the physical layer. It is here that data is packaged into frames and then sent down to the physical layer where the data is then passed on to the destination. Basically, the functions that the Data Link layer looks after are addressing, packetising, error control, flow control, and access control. Now, we have already looked at error control previously, so now it is time to look at flow control.

At its basic level, flow control is a mechanism that is used so that one computer is not overwhelmed by a heap of data being sent to it by the sending computer. The process works on the sender sending a frame and then waiting for an acknowledgement before sending the next frame. This is flow control at its basic level. Further, there is a timer on both sides, so if the timer runs out on the sender's side, that indicates that the frame was not received, or if it was received, it was received with an error, so it sends it again. A similar function occurs on the sender's side, though what is being sent is an acknowledgement as opposed to the frame.

So, at the data link layer, the sender sends a series of frames each containing the data and some control information (known as the header). When the frame is received, the receiver then processes the data before passing it on to the higher level. Normally there is a buffer where frames are stored while they are being processed, and the sending entity needs to avoid sending frames at such a rate that the receiver is unable to process them in time resulting in a buffer overflow.

Stop and Wait

This is the simplest form of flow control. Basically the sender sends a frame, the receiver receives it, processes it, and then sends an acknowledgement. However, the acknowledgement will be for the next frame in the queue. So, if the sender sends frame 0, the receiver will respond with acknowledgement 1, or rather ack 1. This tells the sender that it should now send frame 1, which is the next frame in the queue. Once that is sent, received, and processed, the receiver then sends ack 0, which, once again, requests the next frame in the queue.

If the receiver is getting overwhelmed, it can stop the flow by not sending an acknowledgement, and then only send one when it is ready to receive the next frame.

Okay, time for some more maths, namely because when determining the length of the timer, we need to know a few other things, such as how long it will take for the frame to get from the sender to the receiver. So, first we have the transmission delay, or the length of time for the frame from the first bit to the last bit to leave the sender, and we get that by using the following formula:

T=L/R, or Time = Length of Frame/Transmission rate.

So, we have a frame that is the size of 12000 bits being sent along a medium that is a 100 Mbps link. The formula will then come out as follows:

T = 12000x(1s/108 bits).

We came up with that because the formula would be 12000/100 Mbps, which is 12000/108 bps, or 12000/(108/1). When we are dividing by a fraction, we actually flip the fraction and then multiply it, as such, which produces 12000x(1s/108 bits), however since 12000 x 1s is 12000, we end up with 12000/108 bits. Once again, we switch the sign of the indicie and then multiply it:


We round down:

1.2 x 10-4

And plug the problem into our trusty calculator, which produces:

0.00012 seconds.

Well, let us fix this up a bit:

0.12 milliseconds

And that is the transmission delay, or the length of time it takes for the first bit to the last bit to leave the sender.

Next we go to propagation delay, which is the length of time it takes for the first bit to travel from the sender to the receiver. We get that using the following formula:

T = d/s, or distance divided by the speed that it takes for the bit to travel through the transmission medium, with the upper limit being the speed of light (and we aren't taking into account quantum entanglement here, namely because we haven't worked out how to utilise it). Signals traveling along copper wire travel at 2x 108 m/s

So, let us look at an example, namely the propagation delay between Cairns and Melbourne (which is about 4000 km).

Here it is on a map.
4x 106 m / 2x 108 m/s

4x 106 m x (1s / 2x 108 m)

4x 106 m / 2x 108 m

2 x 10-2 s or 0.02 seconds, or 20 milliseconds.

Sounds pretty slow doesn't, in the grand scheme of things. No wonder we need a proper working NBN.

The reason that we went through all of that math is basically to help us understand how long the timer should be set, because if it is set too short, then the whole flow control system will fail.

Sliding Window

The sliding window protocol is a way of speeding up this process. The stop and wait protocol can be pretty slow, because the frame has to be sent, and then the sender needs to wait for the acknowledgement, or the timer to expire, before sending the next frame. So, we solve this through the use of buffering. Basically the frames are stored in a buffer, and are held in the buffer until the acknowledgement is received, and when the acknowledgement is received, the sent frames are discarded and new frames are then loaded into the buffer. So, the receiver will have a buffer size of W, and the sender can send up to W frames without having to wait for an acknowledgement, as below:

Like the stop and wait protocol, the acknowledgement contains the number of the next frame expected. This works well for error control also, since if one of the frames received is in error, then that, and the subsequent frames, are discarded and an acknowledgement is sent for the frame that was in error. There is also the RNR, or receive not ready, which means that the frames have been received, but it is not ready to receive any further frames. So at the sending end, the sequence number of those sent is maintained, and as the acknowledgements are received, the window grows. A similar function occurs at the receiving end.

In the case of duplex system, there needs to be two sliding windows at either end. In this situation we can utilise a method called piggy backing, which means that each frame that is sent carries a frame, and an acknowledgement, as such:

When Errors Occur

Well, as mentioned, both sides need to buffer data just in case an error is received. If an error is received, the sender continues to send the data until an acknowledgement is received that the frame was received correctly. The sender needs to buffer data to resend any frames that were either lost or damaged, while the receiver needs to buffer data just in case frames are received out of order.

Also, acknowledgements may not be received, which means that after the time out, the sender will resend the frame. When the receiver receives the frame that it has already received, it just discards it and resends the acknowledgement. This diagram might be useful:

Then there is also the Go Back N ARQ, in which the size of the frame is always 1. However, the sender does have a buffer, just in case an acknowledgement is not received.

We also have the idea of the negative acknowledgement. So, if a damaged frame is received, then the receiver will send a negative acknowledgement requesting that the frame be resent. If there is no buffer at the receiving end, frames will continue to be discarded until the correct frame is received. However, if there is a buffer, then subsequent frames will be received, and when the damaged frame is resent, it can be reordered into where it was supposed to go. The greater the size of the buffer at the receiver's end, the less repeat transmissions that there are, though this makes it somewhat more complex to implement.

So, that is flow control, and error control. Next time we will look at multiplexing, or how we send multiple signals along the same channel.

Creative Commons License

Controlling the Flow by David Alfred Sarkies is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License. This license only applies to the text and any image that is within the public domain. Any images or videos that are the subject of copyright are not covered by this license. Use of these images are for illustrative purposes only are are not intended to assert ownership. If you wish to use this work commercially please feel free to contact me

No comments:

Post a Comment