3.4-1 Principles of Reliable Data Transfer (Part 1)

[Music] let's now consider what is one of the really most important challenges in all of networking one of the most fundamental challenges and that is how do two distributed entities reliably communicate over a channel which itself is unreliable that can lose messages that can corrupt or reorder messages now this is really one of my favorite topics to teach and networking because I think there are a lot of deep ideas here and I think there's also a lot of intuition that we can draw on because we as humans have the need to communicate reliably with each other I think this is a top 10 probably a top 5 topic in terms of importance in all of networking and here's how we're going to proceed we're going to start with a very simple initial channel model actually a perfect channel model and then we're gonna start introducing increasingly realistic assumptions that message this can be lost that bits can be flipped that messages can be reordered and we'll see the kind of protocol mechanisms that we need to recover from these kinds of impairments I think you're going to really enjoy this section so let's get started so here's the scenario we're going to consider we have a sending process and a receiving process and the sending process simply wants to send data to the receiving process through a reliable channel and let's note here that the reliable channel is unidirectional we want to be able to reliably send simply from a sender to a receiver that's the abstraction we want to implement now when we talk about the implementation of this abstraction this is where it gets interesting and as we see here the implementation is going to be in the form of a transport layer protocol there are two sides to that protocol there's a sender side of the reliable data transfer protocol and a receiver side and the sender and receiver sides are going to be communicating with each other over an unreliable channel that we see down on the bottom and notice that message exchanges between the protocol entities is going to be bi-directional the sender side of the transport protocol will send things to the receiver side and the receiver side of the transport protocol will reply back and send things to the sender side of the reliable data transfer protocol so even though if the application layer we're implementing unidirectional transfer between the sending and receiving processes within the protocol itself we see that the sender and the receiver are each communicating with each other over a bi-directional unreliable channel you're a couple of things to keep in mind as we've developed our reliable data transfer protocol first of all the complexity of the sender and receiver side of the protocol are going to depend very strongly on the characteristics of this unreliable Channel can it lose messages can it corrupt messages can data be reordered within that unreliable channel and here's a point of view to keep in mind it's really easy for us as humans to look at the sender and receiver together and to see what's happening to say oh I see that message was lost therefore this entity has to take a given action but think about it from the sender's point of view how does the sender know whether or not it's transmitted message over that unreliable channel got through that only happens if the receiver somehow signals back to the sender that in fact the receiver receive that message the key point here is that one side does not know what's going on at the other side or what's going on in the channel it's sort of as if there was a curtain between them everything they know about the other side can only be learned through the sending and receiving of messages so before starting to develop a protocol let's look a little bit more closely at the interfaces available to the protocol the API if you will this diagram shows the interfaces above and below the transport layer on both the sending and the receiving sides on the sending side data is being passed down from an application layer process to the transport layer the transport layer is then going to add a header together with the data to create a transport layer segment send that over the unreliable channel to the receiver on the receiving side when a segment does pop out it will have a header and also a data component to the segment the receiving side will then deliver data up to the receiving process at the application layer in such a way that every piece of data sent down from the sending side is delivered exactly once and in order to the receiving process so let's get started in developing our reliable data transfer protocol which we'll call our DT for reliable data transfer protocol you know you need a good acronym for a protocol like HTTP or TCP or UDP or IP we'll develop our DT and remember we're going to be looking only at uni-directional transfer here between sender and receiver but control is going to flow in both directions now if we're going to develop a protocol we'll need some way to specify what that protocol is how is it that we're going to do that well we could write text but text as we know is subject to misinterpretation it might also be incomplete for example you might write out a textual specification and then think oh yeah actually I forgot about that case what we need here is a more formal way to specify a protocol in fact with a formal specification we may even be able to prove properties about that specification but that's actually an advanced topic that we won't get into here we'll start here by adopting a fairly simple protocol specification technique known as finite state machines and as the name suggests a central notion of finite state machines is this notion of state well this notion of state might seem really pretty simple and pretty intuitive but in fact it's pretty hard to define precisely what do we really mean when we say an RTT senders in a given state or a receiver is in a given state maybe some real-world analogies might help here we might think about a link being in a transmitting state or in an idle State we might think of a light bulb being in an on state or an off state but even after we've mastered this notion of state we're also going to have to think about this notion of there being transitions between states and those transitions happening because of an event that takes place and we're also going to have to think about actions that are taken by the system well before heading into networking why don't we take a simple example let's say of the light bulb and see if that can really help us drive home this notion of state the notion of events and the notion of actions so in the case of the light bulb there are two states on and off the events are to press the on side of the switch or press the off side of the switch and these events cause transitions between the on and off states when the light is in the off state and the on switch is pressed the state of the light bulb transitions to the on state and emits a light when the bulb is in the on state and the off switch is pressed it goes to the off state and the light stops and for completeness we should probably specify what happens when the switch is in the on state and on is pressed and similarly for the off state well let's get back to networking now and the challenge of developing a reliable data transfer protocol and we're going to want to specify a separate finite state machine for both the sender and for the receiver we'll start with the simplest case possible an underlying unreliable channel that actually in fact is perfect no segments are going to be lost corrupted duplicated or reordered the sender is just going to send and it's going to pop out the other side perhaps after some delay perfectly as we mentioned earlier we're going to want separate finite state machines for the sender and the receiver and because this is a perfect channel the actions are really simple the sender is just going to send data into the underlying channel and the receiver is going to read data from the underlying channel let's take a look at the finite state machines for these the sender finite state machine is simple there's just a single state where the sender is waiting for a call from above recall the earlier discussion we had about the interface between the application layer and the transport layer below it on the sending side so an event happens rdt send data that call is made to the transport layer sender the transport layer actions then are to take the piece of data make a packet out of that data and then send that packet into the underlying unreliable data transfer medium via the UDT send operation the finite state machine for the Arditi 1. 0 receiver is also simple again just a single state and here the receiver is waiting for a call from below that's the case well they'll be an arriving data packet the event rdt receive where a packet is actually transferred is the event that happens on that event the receiver extracts the data from the packet and delivers the data to the application layer above now that our dt1 protocol was ridiculously simple because the underlying channel between the sender and receiver itself was reliable so the sender and receiver didn't have to do anything more than really send and receive but now let's think about what the sender and receiver need to do when the underlying channel has impairments in the simplest case say that the channel can flip bits in the transmitted message rendering the message unintelligible at the receiver well before we develop an RTT 2. 0 protocol to deal with errors flip bits in the communication channel be a good idea for you to sort of sit back now and think about how do you as a human being what protocol mechanisms do you use to communicate reliably with someone and I think when you think about it you'll see that there really are reliable human to human communication protocol and protocol mechanisms in place and after you pause to think about that when you come back we'll take a look at a few movie clips that show human communication protocol mechanisms in operation stems what you are saying yes I understand what you're saying I understand what you're saying George I understand now my name is Axel Foley and what it's pertaining I didn't understand what you said pertaining what its meaning regarding we know perfectly well what I said I said do you have a veil you mean do I have that room this is what I have been saying I love that Pink Panther movie well what are the protocol mechanisms that we just saw in those in those few short clips we certainly saw the use of acknowledgments saying yes I got your message the use of negative acknowledgments no I didn't get your message and retransmission the restatement of a message that got garbled in transmission from sender to receiver when we come back to the Arditi 2.

0 protocol we're gonna see all of those mechanisms in place and in use okay so let's get going on building our rdt 2. 0 reliable data transfer protocol for dealing with the case that the channel may introduce bit errors into the message as we noted before we're going to use check sums to detect bit errors and here in English is how the protocol is going to work the question is really how are we going to recover from errors and we'll use some of the mechanisms that we just saw in those film clips will use acknowledgments for the receiver to explicitly tell the sender that a packet was received okay we'll also use negative acknowledgments for the receiver to tell the sender hey I received something but it was an error and if something's received an error the sender is going to retransmit the packet on the receipt of that kind of negative acknowledgement mechanism the operation of our sender the operation of our rdt 2. 0 sender is going to be what we might call a stop and wait type of behavior the sender is going to send a packet and then simply wait for the receiver response here's the finite state machine specification for the Arditi 2.

0 sender there are two states in one state the wait for call from above state the sender's waiting for data to be dropped down from the application layer in the other state they wait for a kern act state the sender is waiting to receive either an acknowledgement or a negative acknowledgement from the receiver now let's take a look at the events that can happen in the actions taken by the sender when a piece of data is passed down from the application layer via the Arditi and API call the sender's going to make a packet and then simply send that packet via the UDT send api when the sender's in the wait for AK or nack state and a packet is received and the packets and acknowledgement the sender simply transitions back to the wait for call from above state because it's received an acknowledgement and it knows that that packets been received by the receiver on the other hand when the sender's in the wait for a car next state and a packet is received and it's an ACK the sender's simply going to retransmit that packet via another call to UDT send and passing it the send packet that it had previously created once back in the wait for call from above state the sender's gonna do exactly that wait for another call for rdt send now let's take a look at the finite state machine specification for the Arditi 2. 0 receiver there's just one state here as in the case of RDT 1. 0 the receiver is basically waiting for a call from below the arrival of a packet so if a packet arrives as indicated through our dt receive and that packets corrupt the receivers going to send a negative acknowledgment an ack back to the sender on the other hand if a packets receive and it's not corrupt we're going to extract the data from the packet deliver the data to the application layer above and then finally send a positive acknowledgement back to the sender via the UDT send call let's now take a look at our dt 2.

0 in operation for the case that there are no bit errors detected the sender and the receiver start in the red states that are shown here their initial States and the first action that happens is that our DT send is called data is passed down from the application layer at the sender side the sender creates a packet and send that packet via UDT send over to the receiver the sender to receiver packet is then received at the receiver it's not corrupt in this case so the receiver extracts data from the packet delivers the data to the application layer and sends an acknowledgement packet back to the the sender then transitions back to the wait for call from a buff state and the receiver of course remains in the wait for call from above State now let's take a look at our dt 2. 0 and operation for the case that a packet from senator receiver is actually corrupted the sender and receiver again start in their start states the first action again is that our dt send is called at the sender side dad has passed down packet is made and that packet is then sent to the receiver the sender then transitions to be wait for AK or nak state that packet is then received at the receiver it's determined to be corrupt and the receiver then sends an ACK packet back to the sender that nak packet is received and the action taken by the our dt 2. 0 sender is simply to retransmit the packet the retransmitted packet is then received at the receiver it's determined to not be corrupt so data is extracted data is delivered up to the application layer and since it's been received correctly the receiver then sends an ACK packet back to the sender and then the sender receives the AK packet and transitions back to the state waiting for a call from above the sender and receiver are then back in their original states and the cycle can continue well we've seen how our dt 2.

0 can recover from flip bits on that sender to receiver transmission but there's a fatal flaw here can you see what it is here's the issue what happens if an AK or an AK is corrupted we actually haven't taken care of that in human communication it says if I say something to you and you reply back to me I'll go and live all it got garbled and here's the question what should I is the sender do when I got that are bold AK or nacked back from you I don't know whether or not you received my initial transmission correctly or incorrectly if I simply retransmit I'm going to send you another copy of the data if you'd received it then correctly you'll take that second transmission and treat it like a new piece of data when in fact it was a retransmission on the other hand if you had sent me an AK and that nak was garbled then you really do want another copy of the message that I had originally sent you and so I should retransmit so what the sender will do in the case of RDT 2. 0 is that it will retransmit a packet if an corrupted a Carnac as received and we'll add a sequence number to each packet so that the receiver can detect duplicates if I send you a retransmission I will send you a packet with the same sequence number if you then receive or receive a duplicate you simply discard it meaning you do not deliver the data up to the application layer because the application layer does not want two copies of the same piece of data rdt 2. 1 is a stop and wait protocol and uses a one bit sequence number well note that the sender finite state machine here now has four states rather than two states that we saw in our dt 2.

0 the top two states are for when our DT is sending a packet with sequence number zero and the bottom two states are for our DT is sending a packet with sequence number one now let's look at the transitions between states the events that happen and the actions taken and let's go clockwise around the states first looking at the case of no corruptions the Arditi 2. 1 sender begins in the states that will label as the waiting for call 0 from above state this means that when in the state the sender is going to include a sequence number 0 on the next packet that it sends the sender's eventually pass data from the application layer it makes a packet with sequence number 0 and then sends that packet the sender then transitions to a state where it's waiting for an AK or a knack for that sequence number 0 packet so let's say that the sender receives an uncorrupted ACK packet that it's been waiting for it then transitions to the waiting for call 1 from above state meaning that the next packet it sends will have a sequence number of 1 the sender's eventually pass data from the app ocation layer again it makes a packet again but this time with sequence number one and sends that packet then let's say it receives an act for that packet so it transitions back to the waiting for call zero from above State and the cycle can then repeat let's now look at what happens when bit errors occur either in the sender to receiver packet or in the akron ACK itself which is corrupted on the way back to the sender if the sender's in the wait for ACK or an x0 state and an ACK or a corrupted packet is received it will retransmit the last packet it sent which given the state it's in will have sequence number zero similarly if the sender is in the wait for a corn AK one state and an ACK or corrupted packet is received it will retransmit the last packet at the tenth this time which will have a sequence number of 1 and finally let's look at the Rd T 2. 1 receiver it has two states indicating whether the receivers waiting for a sequence number zero packet or a sequence number one packet to be received so let's start with the receiver in the waiting for 0 from below state if a packet is received it's not corrupt and it has sequence number 0 this is just what the receiver was looking for so it extracts the data passes it up to the application layer creates an ACK packet and then sends the ACK back to the sender there's a mirror set of operations when the receivers in the waiting for one from below state now let's consider what happens when the receiver is waiting for a packet with sequence number one and a corrupted packet is received well in this case as we talked about earlier it sends an ACK if it's waiting for a sequence number one packet in a sequence number zero packet arrives it's going to send an ACK packet back not an ACK packet now you might want to think a bit about a sequence of past events that could actually result in this happening there are a mirrored set of events and actions that can happen when the receiver is in the wait for 0 from below state on the other side of the finite state machine diagram so that wraps up our discussion of RDT 2.

1 and we just summarized a few of the highlights of RDT 2. 1 with respect to r dt 2. 0 here notice that we use both axe and necks here it's actually possible to create an AK free version of our dt 2.

1 that is a protocol that only uses X you can read about our DT 2.