5 (2) 5 1
ACK ACK (a) stop-and-wait (b) 2 Go-Back-N (GBN) Selective Repeat (SR) 5 2
Stop-and-wait vs. ACK 3. t = 0. t = L/R RTT. ACK ACK. t = RTT + L/R 2. ACK L: packet size (bit) R: rate (bit/sec) 5 Stop-and-wait 3
Go-Back-N (GBN) ACK N 4 [0, base 1]: ACK [base, nextseqnum 1]: ACK [nextseqnum, base + N 1]: base + N base nextseqnum N ACK 5 4
Go-Back-N NACK ACK N GBN: (sliding-window protocol) (e.g, k ) [0, 2 k 1] modulo 2 k 5 5
Λ base = 1 nextseqnum = 1 ACK 5 GBN: FSM rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) base = getacknum(rcvpkt) + 1 if (base = = nextseqnum) stop_timer else start_timer rdt_send(data) if (nextseqnum < base + N) { sndpkt[nextseqnum] = make_pkt(nextseqnum, data, cksum) udt_send(sndpkt[nextseqnum]) if (base = = nextseqnum) start_timer nextseqnum++ } else refuse_data(data) Wait ACK rdt_rcv(rcvpkt) && corrupt(rcvpkt) Λ timeout start_timer udt_send(sndpkt[base]) udt_send(sndpkt[base + 1]) udt_send(sndpkt[nextseqnum 1]) 6
GBN: ACK n ACK n ACK (cumulative acknowledgment) ACK (Go-Back-N ) ACK ( 1 ) ACK ACK 5 7
GBN: FSM Λ expectedseqnum = 1 sndpkt = make_pkt(0, ACK, cksum) default udt_send(sndpkt) Wait rdt_rcv(rcvpkt) && notcorrupted(rcvpkt) && hasseqnum(rcvpkt, expectedseqnum) extract(rcvpkt, data) deliver_data(data) sndpkt = make_pkt(expectedseqnum, ACK, cksum) udt_send(sndpkt) expectedseqnum++ 5 8
GBN: n n ACK (in-order) ACK Q:? (out-of-order) expectedseqnum cf. base, nextseqnum, N 5 9
GBN 4 [ ] nextseqnum 0 1 2 3 4 5 6 7 base base + N 1 [ ] 0 1 2 3 4 5 6 7 expectedseqnum 5 10
GBN 4 [ ] nextseqnum 0 1 2 3 4 5 6 7 send pkt0 send pkt1 rcv pkt0 send ACK0 rcv pkt1 send ACK1 base base + N 1 [ ] 0 1 2 3 4 5 6 7 expectedseqnum 5 11
GBN 4 [ ] nextseqnum send pkt0 send pkt1 send pkt2 rcv pkt0 send ACK0 rcv pkt1 send ACK1 0 1 2 3 4 5 6 7 send pkt3 (wait) rcv pkt3, discard send ACK1 base base + N 1 [ ] 0 1 2 3 4 5 6 7 expectedseqnum 5 12
GBN 4 [ ] nextseqnum send pkt0 send pkt1 send pkt2 rcv pkt0 send ACK0 rcv pkt1 send ACK1 0 1 2 3 4 5 6 7 base base + N 1 send pkt3 rcv ACK0 send pkt4 (wait) rcv pkt3, discard send ACK1 rcv pkt4, discard send ACK1 [ ] 0 1 2 3 4 5 6 7 expectedseqnum 5 13
GBN 4 [ ] nextseqnum send pkt0 send pkt1 send pkt2 rcv pkt0 send ACK0 rcv pkt1 send ACK1 0 1 2 3 4 5 6 7 base base + N 1 [ ] 0 1 2 3 4 5 6 7 send pkt3 rcv ACK0 send pkt4 rcv ACK1 send pkt5 (wait) rcv pkt3, discard send ACK1 rcv pkt4, discard send ACK1 rcv pkt5, discard send ACK1 expectedseqnum 5 14
GBN 4 [ ] nextseqnum send pkt0 send pkt1 send pkt2 rcv pkt0 send ACK0 rcv pkt1 send ACK1 0 1 2 3 4 5 6 7 send pkt3 (wait) rcv pkt3, discard send ACK1 base base + N 1 [ ] 0 1 2 3 4 5 6 7 expectedseqnum 5 rcv ACK0 send pkt4 rcv ACK1 send pkt5 pkt2 timeout send pkt2 send pkt3 send pkt4 send pkt5 rcv pkt4, discard send ACK1 rcv pkt5, discard send ACK1 rcv pkt2, delivered send ACK2 rcv pkt3, delivered send ACK3 15
GBN GBN stop-and-wait 1 () 5 16
Selective Repeat (SR) ACK (out-of-order) (in-order) ACK ACK N ACK N 5 17
Selective Repeat: send_base nextseqnum N (a) N ACK out-of-order (buffered), (expected), () rcv_base (b) 5 18
Selective Repeat timeout(n) n ACK(n) n [send_base, send_base + N 1] n n send_base ACK 5 n n [rcv_base, rcv_base + N 1] ACK(n) out-of-order: n n [rcv_base N, rcv_base 1] ACK(n) ( ) 19
Selective Repeat 5 20
Selective Repeat pkt0 sent pkt0 pkt0 rcvd, delivered, ACK0 sent ACK 5 21
Selective Repeat pkt0 sent pkt1 sent pkt0 pkt1 pkt0 rcvd, delivered, ACK0 sent pkt1 rcvd, delivered, ACK1 sent ACK 5 22
Selective Repeat pkt0 sent pkt1 sent pkt2 sent pkt3 sent pkt0 pkt1 pkt2 pkt3 pkt0 rcvd, delivered, ACK0 sent pkt1 rcvd, delivered, ACK1 sent pkt3 rcvd, buffered, ACK3 sent out-of-order, 5 23
Selective Repeat pkt0 sent pkt1 sent pkt2 sent pkt3 sent ACK0 rcvd, pkt4 sent pkt0 pkt1 pkt2 pkt3 pkt4 pkt0 rcvd, delivered, ACK0 sent pkt1 rcvd, delivered, ACK1 sent pkt3 rcvd, buffered, ACK3 sent pkt4 rcvd, buffered, ACK4 sent out-of-order, 5 24
Selective Repeat pkt0 sent pkt1 sent pkt2 sent pkt0 pkt1 pkt2 pkt0 rcvd, delivered, ACK0 sent pkt1 rcvd, delivered, ACK1 sent pkt3 sent ACK0 rcvd, pkt4 sent pkt2 timeout, pkt2 resent pkt3 pkt4 pkt2 pkt3 rcvd, buffered, ACK3 sent pkt4 rcvd, buffered, ACK4 sent pkt2 rcvd, deliver pkts 2, 3, 4, ACK2 sent 5 25
Selective Repeat pkt0 sent pkt1 sent pkt2 sent pkt0 pkt1 pkt2 pkt0 rcvd, delivered, ACK0 sent pkt1 rcvd, delivered, ACK1 sent pkt3 sent ACK0 rcvd, pkt4 sent pkt2 timeout, pkt2 resent ACK1 rcvd, pkt5 sent 5 pkt3 pkt4 pkt5 pkt2 pkt3 rcvd, buffered, ACK3 sent pkt4 rcvd, buffered, ACK4 sent pkt2 rcvd, deliver pkts 2, 3, 4, ACK2 sent pkt5 rcvd, delivered, ACK5 sent 26
send_base Selective Repeat: nextseqnum N (a) N ACK out-of-order (buffered), (expected), () rcv_base (b) 5 27
Selective Repeat: 0, 1, 2, 3 = 3 0 1 2 3 0 1 2 0 1 2 3 0 1 2 0 1 2 3 0 1 2 pkt0 0 1 2 3 0 1 2 pkt0 pkt1 pkt2 pkt0 0 1 2 3 0 1 2 ACK0 0 1 2 3 0 1 2 ACK1 0 1 2 3 0 1 2 ACK2 pkt0 Q:? 0 1 2 3 0 1 2 0 1 2 3 0 1 2 0 1 2 3 0 1 2 0 1 2 3 0 1 2 0 1 2 3 0 1 2 pkt0 pkt1 pkt2 pkt3 pkt0 0 1 2 3 0 1 2 ACK0 0 1 2 3 0 1 2 ACK1 0 1 2 3 0 1 2 ACK2 pkt0 5 28
RTT RTT: Round Trip Time e.g., 1Gbps, 20msec 1 10 9 (bit/s) 20 10-3 (s) = 2.5MB 1 = 1K bytes 2,500 ACK 5 29
/ ACK 5 ACK ACK ACK 30
Quiz-8 P.28 (P.27 ) 5 31
Quiz-9: Selective Repeat [rcv_base N, rcv_base 1] ACK 5 32