SEDSAT-2 Communications Design Notes 20080225
From SEDSWiki
Contents |
Sliding Window protocol
The Sliding Window protocol is used for automatic transmission of data that is corrupted or lost during transmission from satellite to the ground station. Here is the basic diagram.
This diagram shows a 10 packet data buffer which is inside the satellite. Each packet is assumed to be 1200 bits of data in size, so the total buffer size is 12000 bits or about 1.5kbytes. I have assumed a 9600bps data rate, so each packet is takes 125ms to transmit. The time axis shows the times when each packet will be transmitted, starting from time=0, when communication begins. There is a 5-packet "window". The packets within the window are the only ones that can be transmitted initially, so at the start, we can only transmit the first five packets. Now if we include the ground station in the diagram, we can use arrows to indicate radio transmissions of packets between the satellite and the ground station, and vice-versa.
In this diagram, transmissions from the satellite to the ground station are shown using dotted lines and transmissions from the ground station to the satellite are shown using dashed lines. I've assumed that the transmission time is about 62ms (half the length of one packet). The numbers next to the radio transmissions are explained below:
1. At time t=0, the satellite starts transmitting packet p1 and 62ms later, the ground stations starts receiving the data.
2. At time t=125ms, the satellite hasn't heard any acknowledgment from the ground station, because the ground station hasn't finished receiving the packet, it's still in the air as radio waves! But there are four more packets visible in the window, p2-p5, so the satellite can start transmitting them and worry about the acknowledgement for packet p1 later. So we start transmitting packet p2.
3. Packet p2 will start arriving at the ground station immediately after packet p1 finished arriving, as it was transmitted from the satellite immediate after transmission of packet p1 finished. But the ground station can multi-task, so after receiving packet p1 and whilst packet p2 is being received, the ground station can quickly check for any errors in packet p1 and if all is OK, the ground station can send an acknowledgment signal to the satellite, acknowledging packet p1 was received successfully.
1. Finally in this diagram, the satellite has received the acknowledgment from the ground station that packet p1 was successfully sent and received. The acknowledgment arrived at about 300ms, shortly after packet p3 began transmitting. At this point, the satellite knows that packet p1 was successfully received so packet p1 no longer needs to be within the visible window. The window is only for packets which need to be sent, or have been sent but are waiting for confirmation of being successfully received from ground. So we slide the window forward:
And this process repeats, sliding the window forward after each acknowledgment, until all the data is sent:
Now there is nothing left in the window - all our data is sent, so transmission stops.
What if a packet goes missing?
What if a packet is damaged or goes missing (out of range etc...)? The following shows what will happen if a packet goes missing on its way from the satellite to the ground station. Note that I've used a seven packet window instead of a five packet window this time. The window size needs to be chosen carefully to maximise datarate.
1. The satellite begins transmissin of packet p1, as before
2. The satellite begins transmitting packet p2, but sometime during transmission, the packet is lost, or perhaps becomes damaged.
3. The ground stations sends an acknowledgement to the satellite that packet p1 was received correctly. At this point, the satellite doesn't know that packet p2 was lost.
4. The satellite begins transmitting packet p3. Shortly after this, the acknowledgment for packet p1 arrives from Ground, so we slide the window forward past packet p1, as shown in the diagram above.
5. And then the satellite begins transmissing packet p4
6. After packet p3 is received by Ground correctly, it sends an acknowledgement to the satellite.
7. At t=500ms, the satellite begins transmitting packet p5. But then at about 525ms, the acknowledgment for packet p3 arrives. At this point the satellite knows that something went wrong: It sent packet p2 before packet p3, but it has just received the acknowledgment for packet p3 but hasn't yet received an acknowledgment for packet p2! p2 must have been damaged or lost! After finishing the transmission of packet p5, the satellite will retransmit packet p2. Whilst the satellite is worrying about retransmission of packets, at around this time Ground is preparing to send an acknowledgment for packet p4.
1. The satellite retransmits packet p2 instead of transmitting packet p6
2. Ground acknowledges receipt of packet p5
3. The satellite has finished transmitting packet p2 so it looks for the next un-transmitted packet in the window. This is packet p6, which is transmitted at t=750ms. At about t=775ms, Ground acknowledges that it has received packet p2.
1. At t=875ms, the satellite finishes transmitting packet p6 and starts transmitting packet p7.
2. Shortly afterwards, at about t=900ms, the acknowledgment for packet p2 from Ground arrives at the satellite. As packet p2 has now been successfully received, the satellite can move its transmit window past packet p2. It also sees that packets p3, p4 and p5 have all also been acknowledged as received successfully, so it jumps the window forward by four places:
And now, assuming we have no further errors, we can continue transmitting and sliding the window forward until we've transmitted all our data:
How does Ground know which is packet p2? And which is packet p3?
Each packet needs to contain a packet number. However, we don't need to use the exact packet number as it appears in the data buffer. In the example above, we have a 7 item transmission window, so we will only ever have a maximum of seven packets in transmission (ie. just transmitted, or transmitted and awaiting acknowledgment) at any one time. So we only need to store a number between one and seven. Seven numbers require 3 bits of storage in binary, so we have a protocol overhead of 3 bits per 1200bit packet.
What if multiple packets go missing?
If multiple packets go missing, then if the window is big enough, transmission can go uninterrupted (except for retransmissions), as above. However, what if all the packets start going missing (eg. we've gone out of range). In that case, we'll keep transmitting until we reach the end of our window, and then we loop back to the start. In this case, we will interrupt the transmission flow - but if you've just had 4 or 5 packets in a row go missing, then maybe it is best to stop transmitting and wait until we receive acknowledgments from ground before we continue again.
One of the advantages of this scheme is that it doesn't require any time-outs. Time-outs require real-time clocks, which are easy on a desktop PC but not so easy on a PIC microchip. Maybe the PIC microchip only has one RTC, which we need for timing the communication beacons? If so, we can't use the RTC for setting timeouts. But that's OK using this sliding window protocol, because it doesn't need timeouts anyway!
How hard is the protocol to implement?
A rough complexity estimate is three out of ten. It is fairly simple. You just need to keep two pointers into our transmit buffer, one pointer to mark the start of the window and one pointer to mark the end of the window. Additionally, you need some memory equal in size to the window. If you have a 7 packet window, you need a seven bit buffer. I'll add some pseudo-code showing how this could be implemented, but not just now, it is late and I need to sleep!
