1 Transport Reliability: Sliding Window Protocols 3/1/2012Admin.: PS2 proj-sol: 129 400 3045 FishThread.java 388 1457 12873 Node.java 51 167 1145 PingRequest.java 83 250 2106 SimpleTCPSockSpace.java 181 605 5248 TCPManager.java 889 3088 26381 TCPSock.java 60 149 1316 TCPSockID.java 123 382 3866 TransferClient.java 147 500 5059 TransferServer.java 2051 6998 61039 total 2 proj: 129 400 3045 FishThread.java 341 1301 11313 Node.java 51 167 1145 PingRequest.java 50 128 909 TCPManager.java 132 460 3146 TCPSock.java 123 382 3866 TransferClient.java 147 500 5059 TransferServer.java 973 3338 28483 total ❒ Exam 1 ❒ PS23 Recap: Reliable Data Transfer send side receive side rdt_send(): called from above, (e.g., by app.) udt_send(): called by rdt, to transfer packet over unreliable channel to receiver rdt_rcv(): called from below; when packet arrives on rcv-side of channel deliver_data(): called by rdt to deliver data to upper4 Recap: Potential Channel Errors ❒ bit errors ❒ loss (drop) of packets ❒ reordering or duplication Characteristics of unreliable channel will determine complexity of reliable data transfer protocol (rdt).5 Recap: rdt3.0 Sender (Bit Error/Loss) sndpkt = make_pkt(0, data, checksum) udt_send(sndpkt) start_timer rdt_send(data) Wait for ACK0 rdt_rcv(rcvpkt) && ( corrupt(rcvpkt) || isACK(rcvpkt,1) ) Wait for call 1 from above sndpkt = make_pkt(1, data, checksum) udt_send(sndpkt) start_timer rdt_send(data) rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isACK(rcvpkt,0) rdt_rcv(rcvpkt) && ( corrupt(rcvpkt) || isACK(rcvpkt,0) ) rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isACK(rcvpkt,1) stop_timer stop_timer udt_send(sndpkt) start_timer timeout udt_send(sndpkt) start_timer timeout rdt_rcv(rcvpkt) Wait for call 0 from above Wait for ACK1 Λ"rdt_rcv(rcvpkt) Λ"Λ"Λ"6 Recap: rdt3.0 sender data 0 (n-1) receiver data 0 (n-1) ACK for 0 (n-1) data 1 (n) waiting for 0 (n-1) sending 0 (n-1) waiting for 1 (n) sending 1 (n) waiting for 0 (n+1) ACK for 0 (n-1) State consistency: When receiver’s state is waiting n, the state of the sender is either sending for n-1 or sending for n When sender’s state is sending for n, receiver’s state is waiting for n or n + 17 Recap: rdt3.0 (Stop-and-Wait Operation) Efficiency first packet bit transmitted, t = 0 sender receiver RTT last packet bit transmitted, t = L / R first packet bit arrives last packet bit arrives, send ACK ACK arrives, send next packet, t = RTT + L / R U sender = L / R RTT + L / R8 Recap: A Summary of Questions q How to improve the performance of rdt3.0? ❒ What if there are reordering and duplication? ❒ How to determine the “right” timeout value?9 Outline ❒ Review Ø Reliable data transfer o perfect channel o channel with bit errors o channel with bit errors and losses Ø sliding window: reliability with throughput10 Sliding Window Protocols: Pipelining Pipelining: sender allows multiple, “in-flight”, yet-to-be-acknowledged pkts ❍ range of sequence numbers must be increased ❍ buffering at sender and/or receiver11 Pipelining: Increased Utilization first packet bit transmitted, t = 0 sender receiver RTT last bit transmitted, t = L / R first packet bit arrives last packet bit arrives, send ACK ACK arrives, send next packet, t = RTT + L / R last bit of 2nd packet arrives, send ACK last bit of 3rd packet arrives, send ACK U sender = .024 30.008 = 0.0008 microseconds 3 * L / R RTT + L / R = increase utilization by a factor of 3! Question: a rule-of-thumb window size?12 Forms of Pipelining Protocols ❒ Two generic forms of pipelined protocols ❍ go-Back-N ❍ selective repeat13 Go-Back-n Sender: ❒ k-bit seq # in pkt header ❒ “window” of up to W, consecutive unack’ed pkts allowed ❒ ACK(n): ACKs all pkts up to, including seq # n - “cumulative ACK” ❍ note: ACK(n) could mean two things: I have received upto and include n, or I am waiting for n; we use the former ❒ timer for the packet at base ❒ timeout(n): retransmit pkt n and all higher seq # pkts in window W14 GBN: Sender Extended FSM Wait start_timer udt_send(sndpkt[base]) udt_send(sndpkt[base+1]) … udt_send(sndpkt[nextseqnum-1]) timeout rdt_send(data) if (nextseqnum < base+W) { sndpkt[nextseqnum] = make_pkt(nextseqnum,data,chksum) udt_send(sndpkt[nextseqnum]) if (base == nextseqnum) start_timer nextseqnum++ } else block sender if (new packets ACKed) { advance base; if (more packets waiting) send more packets } if (base == nextseqnum) stop_timer else start_timer for the packet at new base rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) base=1 nextseqnum=1 rdt_rcv(rcvpkt) && corrupt(rcvpkt) Λ"15 GBN: Receiver Extended FSM ACK-only: always send ACK for correctly-received pkt with highest in-order seq # ❍ need only remember expectedseqnum ❒ out-of-order pkt: ❍ discard (don’t buffer) -> no receiver buffering! ❍ re-ACK pkt with highest in-order seq # ❍ may generate duplicate ACKs Wait udt_send(sndpkt) default rdt_rcv(rcvpkt) && notcurrupt(rcvpkt) && hasseqnum(rcvpkt,expectedseqnum) extract(rcvpkt,data) deliver_data(data) sndpkt = make_pkt(expectedseqnum,ACK,chksum) udt_send(sndpkt) expectedseqnum++ expectedseqnum=1 sndpkt = make_pkt(expectedseqnum,ACK,chksum) Λ"16 GBN in Action window size = 417 Discussion: Efficiency of Go-Back-n ❒ Assume window size W ❒ Assume each packet is lost with probability p ❒ Assume always busy ❒ On average, how many packets do we send on average for each succ packet?18 Selective Repeat ❒ Sender window ❍ Window size W: W consecutive unACKed seq #’s ❒ Receiver individually acknowledges correctly received pkts ❍ buffers pkts as needed, for eventual in-order delivery to upper layer ❍ ACK(n) means received packet with seq# n only ❍ buffer size at receiver • window size ❒ Sender only resends pkts for which ACK not received  sender timer for each unACKed pkt19 Selective Repeat: Sender, Receiver Windows W W20 Selective Repeat data from above : ❒ unACKed packets is less than window size W, send/timer; otherwise block app. timeout(n): ❒ resend pkt n, restart timer ACK(n) in [sendbase,sendbase+W-1]: ❒ mark pkt n as received ❒ update sendbase to the first packet