1Stan KurkovskyComputer NetworksPrinciples of Reliable Data TransferBased on Computer Networking, 4thEdition by Kurose and RossStan KurkovskyPrinciples of reliable data transfer• important in app., transport, link layers• top-10 list of important networking topics!• characteristics of unreliable channel will determine complexity of reliable data transfer protocol (rdt)2Stan KurkovskyReliable data transfer: getting startedsendsidereceivesiderdt_send(): called from above, (e.g., by app.). Passed data to deliver to receiver upper layerudt_send(): called by rdt,to transfer packet over unreliable channel to receiverrdt_rcv(): called when packet arrives on rcv-side of channeldeliver_data(): called by rdtto deliver data to upperStan KurkovskyReliable data transfer: getting startedWe’ll:• incrementally develop sender, receiver sides of reliable data transfer protocol (rdt)• consider only unidirectional data transfer• but control info will flow on both directions!• use finite state machines (FSM) to specify sender, receiverstate1state2event causing state transitionactions taken on state transitionstate: when in this “state” next state uniquely determined by next eventeventactions3Stan KurkovskyRdt 1.0: reliable transfer over a reliable channel• underlying channel perfectly reliable• no bit errors• no loss of packets• separate FSMs for sender, receiver:• sender sends data into underlying channel• receiver read data from underlying channelWait for call from abovepacket = make_pkt(data)udt_send(packet)rdt_send(data)extract (packet,data)deliver_data(data)Wait for call from belowrdt_rcv(packet)senderreceiverStan KurkovskyRdt 2.0: channel with bit errors• underlying channel may flip bits in packet• checksum to detect bit errors•thequestion: how to recover from errors:•acknowledgements (ACKs):receiver explicitly tells sender that pkt received OK•negative acknowledgements (NAKs):receiver explicitly tells sender that pkt had errors• sender retransmits pkt on receipt of NAK• new mechanisms in rdt2.0 (beyond rdt1.0):• error detection• receiver feedback: control msgs (ACK,NAK) rcvr->sender4Stan KurkovskyRdt 2.0: FSM specificationWait for call from abovesnkpkt = make_pkt(data, checksum)udt_send(sndpkt)extract(rcvpkt,data)deliver_data(data)udt_send(ACK)rdt_rcv(rcvpkt) && notcorrupt(rcvpkt)rdt_rcv(rcvpkt) && isACK(rcvpkt)udt_send(sndpkt)rdt_rcv(rcvpkt) &&isNAK(rcvpkt)udt_send(NAK)rdt_rcv(rcvpkt) && corrupt(rcvpkt)Wait for ACK or NAKWait for call from belowsenderreceiverrdt_send(data)LStan KurkovskyRdt 2.0 has a fatal flaw!What happens if ACK/NAK corrupted?• sender doesn’t know what happened at receiver!• can’t just retransmit: possible duplicateHandling duplicates: • sender retransmits current pkt if ACK/NAK garbled• sender adds sequence numberto each pkt• receiver discards (doesn’t deliver up) duplicate pktstop and wait• Sender sends one packet, then waits for receiver response5Stan KurkovskyRdt 2.1: sender, handles garbled ACK/NAKsWait for call 0 from abovesndpkt = make_pkt(0, data, checksum)udt_send(sndpkt)rdt_send(data)Wait for ACK or NAK 0udt_send(sndpkt)rdt_rcv(rcvpkt) && ( corrupt(rcvpkt) ||isNAK(rcvpkt) )sndpkt = make_pkt(1, data, checksum)udt_send(sndpkt)rdt_send(data)rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isACK(rcvpkt) udt_send(sndpkt)rdt_rcv(rcvpkt) && ( corrupt(rcvpkt) ||isNAK(rcvpkt) )rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isACK(rcvpkt)Wait forcall 1 from aboveWait for ACK or NAK 1LLStan KurkovskyRdt 2.1: receiver, handles garbled ACK/NAKsWait for 0 from belowrdt_rcv(rcvpkt) && not corrupt(rcvpkt) &&has_seq0(rcvpkt)rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && has_seq1(rcvpkt)extract(rcvpkt,data)deliver_data(data)sndpkt = make_pkt(ACK, chksum)udt_send(sndpkt)Wait for 1 from belowrdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && has_seq0(rcvpkt) extract(rcvpkt,data)deliver_data(data)sndpkt = make_pkt(ACK, chksum)udt_send(sndpkt)rdt_rcv(rcvpkt) && (corrupt(rcvpkt)sndpkt = make_pkt(ACK, chksum)udt_send(sndpkt)rdt_rcv(rcvpkt) && not corrupt(rcvpkt) &&has_seq1(rcvpkt)rdt_rcv(rcvpkt) && (corrupt(rcvpkt)sndpkt = make_pkt(ACK, chksum)udt_send(sndpkt)sndpkt = make_pkt(NAK, chksum)udt_send(sndpkt)6Stan KurkovskyRdt 2.1: discussionSender:• seq # added to pkt• two seq. #’s (0,1) will suffice. Why?• must check if received ACK/NAK corrupted • twice as many states• state must “remember” whether “current” pkt has 0 or 1 seq. #Receiver:• must check if received packet is duplicate• state indicates whether 0 or 1 is expected pkt seq #• note: receiver can notknow if its last ACK/NAK received OK at senderStan KurkovskyRdt 2.2: a NAK-free protocol• same functionality as rdt2.1, using ACKs only• instead of NAK, receiver sends ACK for last pkt received OK• receiver must explicitlyinclude seq # of pkt being ACKed • duplicate ACK at sender results in same action as NAK: retransmit current pkt7Stan KurkovskyRdt 2.2: sender, receiver fragmentsWait for call 0 from abovesndpkt = make_pkt(0, data, checksum)udt_send(sndpkt)rdt_send(data)udt_send(sndpkt)rdt_rcv(rcvpkt) && ( corrupt(rcvpkt) ||isACK(rcvpkt,1) )rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isACK(rcvpkt,0)Wait for ACK0sender FSMfragmentWait for 0 from belowrdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && has_seq1(rcvpkt) extract(rcvpkt,data)deliver_data(data)sndpkt = make_pkt(ACK1, chksum)udt_send(sndpkt)rdt_rcv(rcvpkt) && (corrupt(rcvpkt) ||has_seq1(rcvpkt))udt_send(sndpkt)receiver FSMfragmentLStan KurkovskyRdt 3.0: channels with errors andlossNew assumption: underlying channel can also lose packets (data or ACKs)• checksum, seq. #, ACKs, retransmissions will be of help, but not enoughApproach: sender waits “reasonable” amount of time for ACK • retransmits if no ACK received in this time• if pkt (or ACK) just delayed (not lost):• retransmission will be duplicate, but use of seq. #’s already handles this• receiver must specify seq # of pkt being ACKed• requires countdown timer8Stan KurkovskyRdt 3.0 sendersndpkt = make_pkt(0, data, checksum)udt_send(sndpkt)start_timerrdt_send(data)Wait for ACK0rdt_rcv(rcvpkt) && ( corrupt(rcvpkt) ||isACK(rcvpkt,1) )Wait for call 1 from abovesndpkt = make_pkt(1, data, checksum)udt_send(sndpkt)start_timerrdt_send(data)rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isACK(rcvpkt,0)rdt_rcv(rcvpkt) && ( corrupt(rcvpkt) ||isACK(rcvpkt,0) )rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) &&