UDP: User Datagram Protocol PDF

UDP: User Datagram Protocol § “no frills,” “bare bones” Internet transport protocol § “best effort” service, UDP segments may be: • lost • delivered out-of-order to app § connectionless: • no handshaking between UDP sender, receiver • each UDP segment handled independently of others Why is there a...

UDP: User Datagram Protocol § “no frills,” “bare bones” Internet transport protocol § “best effort” service, UDP segments may be: • lost • delivered out-of-order to app § connectionless: • no handshaking between UDP sender, receiver • each UDP segment handled independently of others Why is there a UDP? § no connection establishment (which can add RTT delay) § simple: no connection state at sender, receiver § small header size § no congestion control § UDP can blast away as fast as desired! § can function in the face of congestion Transport Layer: 3-24 UDP: User Datagram Protocol § UDP use: § streaming multimedia apps (loss tolerant, rate sensitive) § DNS § SNMP (Simple Network Management Protocol) § HTTP/3 § if reliable transfer needed over UDP (e.g., HTTP/3): § add needed reliability at application layer § add congestion control at application layer Transport Layer: 3-25 UDP checksum Goal: detect errors (i.e., flipped bits) in transmitted segment 1st number 2nd number sum Transmitted: 5 6 11 Received: 4 6 11 receiver-computed checksum = sender-computed checksum (as received) Transport Layer: 3-31 UDP checksum Goal: detect errors (i.e., flipped bits) in transmitted segment sender: § treat contents of UDP segment (including UDP header fields and IP addresses) as sequence of 16-bit integers § checksum: addition (one’s complement sum) of segment content § checksum value put into UDP checksum field receiver: § compute checksum of received segment § check if computed checksum equals checksum field value: • Not equal - error detected • Equal - no error detected. But maybe errors nonetheless? More later …. Transport Layer: 3-32 Internet checksum: an example example: add two 16-bit integers 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 wraparound 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 sum 1 0 1 1 1 0 1 1 1 0 1 1 1 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1 checksum Note: when adding numbers, a carryout from the most significant bit needs to be added to the result * Check out the online interactive exercises for more examples: http://gaia.cs.umass.edu/kurose_ross/interactive/ Transport Layer: 3-33 Internet checksum: weak protection! example: add two 16-bit integers 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 wraparound 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 sum 1 0 1 1 1 0 1 1 1 0 1 1 1 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1 checksum 0 1 1 0 Even though numbers have changed (bit flips), no change in checksum! Transport Layer: 3-34 rdt1.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 reads data from underlying channel sender Wait for call from above rdt_send(data) packet = make_pkt(data) udt_send(packet) receiver Wait for call from below rdt_rcv(packet) extract (packet,data) deliver_data(data) Transport Layer: 3-43 rdt2.0: channel with bit errors § underlying channel may flip bits in packet • checksum (e.g., Internet checksum) to detect bit errors § the question: how to recover from errors? How do humans recover from “errors” during conversation? Transport Layer: 3-44 rdt2.0: channel with bit errors § underlying channel may flip bits in packet • checksum to detect bit errors § the question: 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 stop and wait sender sends one packet, then waits for receiver response Transport Layer: 3-45 rdt2.0: FSM specifications rdt_send(data) sender snkpkt = make_pkt(data, checksum) udt_send(sndpkt) rdt_rcv(rcvpkt) && isNAK(rcvpkt) Wait for Wait for call from ACK or udt_send(sndpkt) above NAK rdt_rcv(rcvpkt) && corrupt(rcvpkt) udt_send(NAK) rdt_rcv(rcvpkt) && isACK(rcvpkt) L Wait for call from below receiver rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) extract(rcvpkt,data) deliver_data(data) udt_send(ACK) Transport Layer: 3-46 rdt2.0: FSM specification rdt_send(data) sender snkpkt = make_pkt(data, checksum) udt_send(sndpkt) rdt_rcv(rcvpkt) && isNAK(rcvpkt) Wait for Wait for call from ACK or udt_send(sndpkt) above NAK rdt_rcv(rcvpkt) && corrupt(rcvpkt) udt_send(NAK) rdt_rcv(rcvpkt) && isACK(rcvpkt) L Note: “state” of receiver (did the receiver get my message correctly?) isn’t known to sender unless somehow communicated from receiver to sender § that’s why we need a protocol! Wait for call from below receiver rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) extract(rcvpkt,data) deliver_data(data) udt_send(ACK) Transport Layer: 3-47 rdt2.0: operation with no errors rdt_send(data) sender snkpkt = make_pkt(data, checksum) udt_send(sndpkt) rdt_rcv(rcvpkt) && isNAK(rcvpkt) Wait for Wait for call from ACK or udt_send(sndpkt) above NAK rdt_rcv(rcvpkt) && corrupt(rcvpkt) udt_send(NAK) rdt_rcv(rcvpkt) && isACK(rcvpkt) L Wait for call from below receiver rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) extract(rcvpkt,data) deliver_data(data) udt_send(ACK) Transport Layer: 3-48 rdt2.0: corrupted packet scenario rdt_send(data) sender snkpkt = make_pkt(data, checksum) udt_send(sndpkt) rdt_rcv(rcvpkt) && isNAK(rcvpkt) Wait for Wait for call from ACK or udt_send(sndpkt) above NAK rdt_rcv(rcvpkt) && corrupt(rcvpkt) udt_send(NAK) rdt_rcv(rcvpkt) && isACK(rcvpkt) L Wait for call from below receiver rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) extract(rcvpkt,data) deliver_data(data) udt_send(ACK) Transport Layer: 3-49 rdt2.0 has a fatal flaw! what happens if ACK/NAK corrupted? § sender doesn’t know what happened at receiver! § can’t just retransmit: possible duplicate handling duplicates: § sender retransmits current pkt if ACK/NAK corrupted § sender adds sequence number to each pkt § receiver discards (doesn’t deliver up) duplicate pkt stop and wait sender sends one packet, then waits for receiver response Transport Layer: 3-50 rdt2.1: sender, handling garbled ACK/NAKs rdt_send(data) sndpkt = make_pkt(0, data, checksum) udt_send(sndpkt) rdt_rcv(rcvpkt) && (corrupt(rcvpkt) || Wait for isNAK(rcvpkt) ) Wait for call 0 from above rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isACK(rcvpkt) ACK or NAK 0 udt_send(sndpkt) rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isACK(rcvpkt) L rdt_rcv(rcvpkt) && (corrupt(rcvpkt) || isNAK(rcvpkt) ) udt_send(sndpkt) L Wait for ACK or NAK 1 Wait for call 1 from above rdt_send(data) sndpkt = make_pkt(1, data, checksum) udt_send(sndpkt) Transport Layer: 3-51 rdt2.1: receiver, handling garbled ACK/NAKs rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && has_seq0(rcvpkt) rdt_rcv(rcvpkt) && (corrupt(rcvpkt) extract(rcvpkt,data) deliver_data(data) sndpkt = make_pkt(ACK, chksum) udt_send(sndpkt) rdt_rcv(rcvpkt) && (corrupt(rcvpkt) sndpkt = make_pkt(NAK, chksum) udt_send(sndpkt) rdt_rcv(rcvpkt) && not corrupt(rcvpkt) && has_seq1(rcvpkt) sndpkt = make_pkt(ACK, chksum) udt_send(sndpkt) sndpkt = make_pkt(NAK, chksum) udt_send(sndpkt) Wait for 0 from below Wait for 1 from below rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && has_seq1(rcvpkt) rdt_rcv(rcvpkt) && not corrupt(rcvpkt) && has_seq0(rcvpkt) sndpkt = make_pkt(ACK, chksum) udt_send(sndpkt) extract(rcvpkt,data) deliver_data(data) sndpkt = make_pkt(ACK, chksum) udt_send(sndpkt) Transport Layer: 3-52 rdt2.1: discussion sender: § 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 “expected” pkt should have seq # of 0 or 1 receiver: § must check if received packet is duplicate • state indicates whether 0 or 1 is expected pkt seq # § note: receiver can not know if its last ACK/NAK received OK at sender Transport Layer: 3-53 rdt2.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 explicitly include seq # of pkt being ACKed § duplicate ACK at sender results in same action as NAK: retransmit current pkt As we will see, TCP uses this approach to be NAK-free Transport Layer: 3-54 rdt2.2: sender, receiver fragments rdt_send(data) sndpkt = make_pkt(0, data, checksum) udt_send(sndpkt) rdt_rcv(rcvpkt) && ( corrupt(rcvpkt) || Wait for Wait for isACK(rcvpkt,1) ) ACK call 0 from 0 udt_send(sndpkt) above sender FSM fragment rdt_rcv(rcvpkt) && (corrupt(rcvpkt) || has_seq1(rcvpkt)) udt_send(sndpkt) Wait for 0 from below rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isACK(rcvpkt,0) receiver FSM fragment L rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && has_seq1(rcvpkt) extract(rcvpkt,data) deliver_data(data) sndpkt = make_pkt(ACK1, chksum) udt_send(sndpkt) Transport Layer: 3-55 rdt3.0: channels with errors and loss New channel assumption: underlying channel can also lose packets (data, ACKs) • checksum, sequence #s, ACKs, retransmissions will be of help … but not quite enough Q: How do humans handle lost sender-toreceiver words in conversation? Transport Layer: 3-56 rdt3.0: channels with errors and loss Approach: 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 seq #s already handles this! • receiver must specify seq # of packet being ACKed § use countdown timer to interrupt after “reasonable” amount of time timeout Transport Layer: 3-57 rdt3.0 sender rdt_send(data) sndpkt = make_pkt(0, data, checksum) udt_send(sndpkt) start_timer Wait for call 0 from above rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isACK(rcvpkt,1) Wait for ACK0 rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isACK(rcvpkt,0) stop_timer stop_timer Wait for ACK1 Wait for call 1 from above rdt_send(data) sndpkt = make_pkt(1, data, checksum) udt_send(sndpkt) start_timer Transport Layer: 3-58 rdt3.0 sender rdt_send(data) sndpkt = make_pkt(0, data, checksum) udt_send(sndpkt) start_timer rdt_rcv(rcvpkt) L rdt_rcv(rcvpkt) && ( corrupt(rcvpkt) || isACK(rcvpkt,1) ) Wait for call 0 from above rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isACK(rcvpkt,1) L Wait for ACK0 timeout udt_send(sndpkt) start_timer rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isACK(rcvpkt,0) stop_timer stop_timer timeout udt_send(sndpkt) start_timer rdt_rcv(rcvpkt) && ( corrupt(rcvpkt) || isACK(rcvpkt,0) ) L Wait for ACK1 Wait for call 1 from above rdt_send(data) rdt_rcv(rcvpkt) L sndpkt = make_pkt(1, data, checksum) udt_send(sndpkt) start_timer Transport Layer: 3-59 rdt3.0 in action receiver sender send pkt0 rcv ack0 send pkt1 rcv ack1 send pkt0 pkt0 ack0 pkt1 ack1 pkt0 ack0 send pkt0 rcv pkt0 send ack0 rcv pkt1 send ack1 rcv pkt0 send ack0 rcv ack0 send pkt1 pkt0 ack0 rcv pkt0 send ack0 pkt1 X loss timeout resend pkt1 rcv ack1 send pkt0 (a) no loss receiver sender pkt1 ack1 pkt0 ack0 rcv pkt1 send ack1 rcv pkt0 send ack0 (b) packet loss Transport Layer: 3-60 rdt3.0 in action receiver sender sender send pkt0 pkt0 rcv ack0 send pkt1 ack0 pkt1 ack1 X receiver send pkt0 rcv pkt0 send ack0 rcv ack0 send pkt1 rcv pkt1 send ack1 loss timeout resend pkt1 rcv ack1 send pkt0 pkt1 ack1 pkt0 ack0 (c) ACK loss (detect duplicate) send ack1 rcv pkt0 send ack0 ack0 pkt1 rcv pkt0 send ack0 rcv pkt1 send ack1 ack1 timeout resend pkt1 rcv pkt1 pkt0 rcv ack1 send pkt0 rcv ack1 (ignore) pkt1 rcv pkt1 (detect duplicate) pkt0 send ack1 ack1 rcv pkt0 send ack0 ack0 pkt1 (d) premature timeout/ delayed ACK Transport Layer: 3-61 Performance of rdt3.0 (stop-and-wait) § U sender: utilization – fraction of time sender busy sending § example: 1 Gbps link, 15 ms prop. delay, 8000 bit packet • time to transmit packet into channel: 8000 bits L Dtrans = R = 9 10 bits/sec = 8 microsecs Transport Layer: 3-62 rdt3.0: stop-and-wait operation sender receiver first packet bit transmitted, t = 0 RTT first packet bit arrives last packet bit arrives, send ACK ACK arrives, send next packet, t = RTT + L / R Transport Layer: 3-63 rdt3.0: stop-and-wait operation sender Usender= L/R receiver L/R RTT + L / R .008 = 30.008 RTT = 0.00027 § rdt 3.0 protocol performance stinks! § Protocol limits performance of underlying infrastructure (channel) Transport Layer: 3-64 rdt3.0: pipelined protocols operation pipelining: sender allows multiple, “in-flight”, yet-to-be-acknowledged packets • range of sequence numbers must be increased • buffering at sender and/or receiver Transport Layer: 3-65 Pipelining: increased utilization sender receiver first packet bit transmitted, t = 0 last bit transmitted, t = L / R first packet bit arrives last packet bit arrives, send ACK last bit of 2nd packet arrives, send ACK last bit of 3rd packet arrives, send ACK RTT ACK arrives, send next packet, t = RTT + L / R 3-packet pipelining increases utilization by a factor of 3! U sender = 3L / R RTT + L / R = .0024 30.008 = 0.00081 Transport Layer: 3-66 Go-Back-N: sender § sender: “window” of up to N, consecutive transmitted but unACKed pkts • k-bit seq # in pkt header § cumulative ACK: ACK(n): ACKs all packets up to, including seq # n • on receiving ACK(n): move window forward to begin at n+1 § timer for oldest in-flight packet § timeout(n): retransmit packet n and all higher seq # packets in window Transport Layer: 3-67 Go-Back-N: receiver § ACK-only: always send ACK for correctly-received packet so far, with highest in-order seq # • may generate duplicate ACKs • need only remember rcv_base § on receipt of out-of-order packet: • can discard (don’t buffer) or buffer: an implementation decision • re-ACK pkt with highest in-order seq # Receiver view of sequence number space: … … rcv_base received and ACKed Out-of-order: received but not ACKed Not received Transport Layer: 3-68 Go-Back-N in action sender window (N=4) 012345678 012345678 012345678 012345678 012345678 012345678 sender send pkt0 send pkt1 send pkt2 send pkt3 (wait) rcv ack0, send pkt4 rcv ack1, send pkt5 ignore duplicate ACK pkt 2 timeout 012345678 012345678 012345678 012345678 send send send send pkt2 pkt3 pkt4 pkt5 receiver Xloss receive pkt0, send ack0 receive pkt1, send ack1 receive pkt3, discard, (re)send ack1 receive pkt4, discard, (re)send ack1 receive pkt5, discard, (re)send ack1 rcv rcv rcv rcv pkt2, pkt3, pkt4, pkt5, deliver, deliver, deliver, deliver, send send send send ack2 ack3 ack4 ack5 Transport Layer: 3-69 Selective repeat §receiver individually acknowledges all correctly received packets • buffers packets, as needed, for eventual in-order delivery to upper layer §sender times-out/retransmits individually for unACKed packets • sender maintains timer for each unACKed pkt §sender window • N consecutive seq #s • limits seq #s of sent, unACKed packets Transport Layer: 3-70 Selective repeat: sender, receiver windows Transport Layer: 3-71 Selective repeat: sender and receiver sender data from above: § if next available seq # in window, send packet timeout(n): § resend packet n, restart timer ACK(n) in [sendbase,sendbase+N]: § mark packet n as received § if n smallest unACKed packet, advance window base to next unACKed seq # receiver packet n in [rcvbase, rcvbase+N-1] § send ACK(n) § out-of-order: buffer § in-order: deliver (also deliver buffered, in-order packets), advance window to next not-yetreceived packet packet n in [rcvbase-N,rcvbase-1] § ACK(n) otherwise: § ignore Transport Layer: 3-72 Selective Repeat in action sender window (N=4) 012345678 012345678 012345678 012345678 012345678 012345678 sender send pkt0 send pkt1 send pkt2 send pkt3 (wait) receiver Xloss rcv ack0, send pkt4 rcv ack1, send pkt5 record ack3 arrived pkt 2 timeout 012345678 012345678 012345678 012345678 receive pkt0, send ack0 receive pkt1, send ack1 receive pkt3, buffer, send ack3 receive pkt4, buffer, send ack4 receive pkt5, buffer, send ack5 send pkt2 (but not 3,4,5) rcv pkt2; deliver pkt2, pkt3, pkt4, pkt5; send ack2 Q: what happens when ack2 arrives? Transport Layer: 3-73 Selective repeat: a dilemma! example: § seq #s: 0, 1, 2, 3 (base 4 counting) § window size=3 receiver window (after receipt) sender window (after receipt) 0123012 pkt0 0123012 pkt1 0123012 0123012 pkt2 0123012 0123012 pkt3 0123012 0123012 X pkt0 will accept packet with seq number 0 (a) no problem 0123012 pkt0 0123012 pkt1 0123012 pkt2 timeout retransmit pkt0 pkt0 0123012 (b) oops! 0123012 X X X 0123012 0123012 will accept packet with seq number 0 Transport Layer: 3-74 Selective repeat: a dilemma! example: § seq #s: 0, 1, 2, 3 (base 4 counting) § window size=3 Q: what relationship is needed between sequence # size and window size to avoid problem in scenario (b)? receiver window (after receipt) sender window (after receipt) 0123012 pkt0 0123012 pkt1 0123012 0123012 pkt2 0123012 0123012 pkt3 0123012 X § receiver can’t pkt0 see sender side (a) no problem § receiver behavior identical in both cases! §0something’s pkt0 123012 pkt1 0(very) 1 2 3 0 1wrong! 2 0123012 0123012 pkt2 timeout retransmit pkt0 pkt0 0123012 (b) oops! will accept packet with seq number 0 0123012 X X X 0123012 0123012 will accept packet with seq number 0 Transport Layer: 3-75