Quick Review of Sliding Window (Go-Back-N).ppt

Quick Review of Sliding Window (Go-Back-N) CS 681 Tutorial Flow Control Ensuring the sending entity does not overwhelm the receiving entity Preventing buffer overflow Transmission time Time taken to emit all bits into medium Propagation time Time for a bit to traverse the link Model of Frame Transmission Stop and Wait Source transmits frame Destination receives frame and replies with acknowledgement Source waits for ACK before sending next frame Destination can stop flow by not send ACK Works well for a few large frames Stop and Wait Link Utilization rdt3.0: stop-and-wait operation Pipelined protocols Pipelining: sender allows multiple, “in-flight”, yet-to-be-acknowledged pkts range of sequence numbers must be increased buffering at sender and/or receiver Two generic forms of pipelined protocols: go-Back-N, selective repeat Pipelining: increased utilization Sliding Windows Flow Control Allow multiple frames to be in transit Receiver has buffer W long Transmitter can send up to W frames without ACK Each frame is numbered ACK includes number of next frame expected Sequence number bounded by size of field (k) Frames are numbered modulo 2k Sliding Window Diagram Example Sliding Window GBN inaction 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 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 Increase utilization by a factor of 3! Go Back-N: Sender sliding window 11.7 Go-Back_N: Receiver sliding window 11.8 GBN: Control variables 11.9 Go-Back-N ARQ, normal operation 11.10 Go-Back-N ARQ, lost frame 11.11 Go-Back-N ARQ: sender window size In Go-Back-N ARQ, the size of the sender