Plan Ahead!Week 4:!! Reliable data delivery!! TCP!Week 5:!! Congestion control!! Midterm!Week 6:!! Network layer: Internet Protocol (IP), NAT!Week 7:!! Routing protocols!! Routing in the Internet!Week 8:!! Broadcast and multicast routing!! Data link layer, Ethernet!Week 9:!! Hubs and Switches!! wireless networking!Week 10:!! Mobile networking !! Review!CS118!1!What we learned last week!" DNS: made of 4 pieces!(1)Name space, (2)authoritative servers, (3)caching resolvers, and (4) the access protocol!" Transport protocol functions!! Multiplexity and demultiplexing among processes in the same computer!! For UDP: nothing more!# Offers unreliable, best-effort delivery!! For TCP!# Reliable delivery!# Flow control!# Congestion control!CS118!2!How to Achieve Reliable Data Transfer!" consider one-way data transfer (control info will flow in both directions)!" What can go wrong in the unreliable channel?!! Bit error, packet loss, re-ordering!!CS118!3!Reliable transport protocol Unreliable network delivery Error Detection and Recovery!" Bit errors!" Error detection: data checksum!" Error recovery: send negative-ACK to sender to retransmit!" re-ordering!" Error detection: by sequence number!" Error recovery: receiver can re-sequence the data!" Packet loss!" Loss detection: alarm timer (at sender end)!" Loss recovery: retransmit!" Correct reception of data: receiver sends an ACK!CS118!4!Three basic components"in reliable data delivery by retransmission!" sequence #: used to uniquely identify individual packets!" Acknowledgment (ACK): reception report sent by receiver to the sender!" Retransmission timer set by the sender for the already sent, yet to be ack'ed packet!! Retransmit the packet when timer expires!CS118!5!rdt3.0: channel with bit errors & packet loss!" Sender waits “reasonable” amount of time for ACK from receiver!! Set up a retransmission timer!" When timeout: retransmits!" In case the packet (or ACK) just delayed but not lost!! Retransmitted packet will be a duplicate!! Sequence number can detect this!CS118!6!rdt3.0 in action!CS118!7!Rdt3.0: a stop-and-wait protocol!Stop-and-Wait!" Sender sends one packet, then waits for receiver’s ACK!" Still need a sequence number!! Consider the case of retransmission!" Speed up recovery: when a received packet is in error, receiver sends an ACK with the seq# of the last correctly received packet!! When sender sees a duplicate ACK: take same action as NAK: retransmit current pkt!" This protocol functions correctly, but suffers from performance problems!CS118!8!A B P0!A0!P1!timeout!P1!A1!A1!P0!Bit error!A1!rdt3.0: stop-and-wait operation!CS118!9!first packet bit transmitted, t = 0 sender receiver RTT last packet bit transmitted, t = L / R first bit of packet arrives last bit of packet arrives, send ACK ACK arrives, send next packet, t = RTT + L / R Link speek: 1 Gbps Propagation delay: 15 ms Packet size: 1000 bytes ! dtrans=LR=8000bits109bps= 8µs! Usender=dtransRTT + dtrans=0.008ms30.008ms= 0.00027Pipelining transmission!" Allowing multiple, yet-to-be-acknowledged, packets to be “in-flight”!! range of sequence numbers must increase!! Need packet buffering at sender (and receiver too)!CS118!10!Pipelining: increased utilization!CS118!11!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!!! Usender =3 "LRRTT +LR=0.02430.008= 0.0008What if some packets get lost?!(1) Go-Back-N (GBN)!" Sender can send up to N unack’ed packets!! N = Flow control window size!" Receiver only sends cumulative acks!! Doesn’t ack packet if there’s any gap!" Sender has timer for oldest unack’ed packet!! If timer expires, retransmit all unack’ed packets!CS118!12!Go-Back-N!Sender:!" “window” of up to N consecutive unack’ed packets allowed!CS118!13!• ACK(n): Acknowledge all pkts up to, and include seq # n (cumulative ACK)!• Set retransmission timer for the first unacked packet!• When timeout(i): retransmit packet i and all packets after i within the flow control window!GBN: sender FSM!CS118!14!Wait if (nextseqnum < base+N) {! sndpkt[nextseqnum] = make_pkt(nextseqnum,data,chksum)! udt_send(sndpkt[nextseqnum])! if (base == nextseqnum)! start_timer! nextseqnum++! }!else refuse_data(data)!base=1!nextseqnum=1!!!"rdt_send(data) !Call from application!rdt_rcv(rcvpkt) !&& corrupt(rcvpkt) !!Call from network start_timer!udt_send(sndpkt[base])!udt_send(sndpkt[base+1])!…!udt_send(sndpkt[nextseqnum-1])!!timeout!!base = getacknum(rcvpkt)+1!If (base == nextseqnum)! stop_timer!else! start_timer!If (nextseqnum < base+N), send pkt!rdt_rcv(rcvpkt) && ! notcorrupt(rcvpkt) !!start GBN: receiver FSM!" When receive a packet with seq= expectedseqnum, send an ACK!" When receive an out-of-order packet: !! discard (don’t buffer) $ no receiver buffering!!! Send an ACK with seq # of the last in-order, correctly-received packet (May generate duplicate ACKs)!" Receiver only needs to keep track a single control variable: expectedseqnum CS118!15!Wait!rdt_rcv(rcvpkt)! && notcurrupt(rcvpkt)! && hasseqnum(rcvpkt,expectedseqnum) !extract(rcvpkt,data)!deliver_data(data)!sndpkt = make_pkt(expectedseqnum,ACK,chksum)!udt_send(sndpkt)!expectedseqnum++!udt_send(sndpkt)!Default (received data in error)!!expectedseqnum=1!sndpkt = make_pkt(expectedseqnum,ACK,chksum)!!!!"CS118!16!Window size = 4 packets!GBN in action!What if some packets get lost?!(2) Selective repeat!" Sender can send up to N unacked packets!" Receiver individually acknowledges each correctly received pkt!! buffers pkts that arrived out-of-order for eventual in-order delivery to upper layer!" Sender maintains timer for each unack’ed packet!! When timer expires, retransmit only unack’ed packets!" Flow control window: works as before!! Sender can send N consecutive packets!! N controls the range of sent but unACK’ed pkts!CS118!17!Selective Repeat: sender, receiver windows!CS118!18!Selective Repeat!Receive data from upper layer:!" if next seq # is in window, send
View Full Document
Unlocking...