Page 1 CS162 Operating Systems and Systems Programming Lecture 22 Networking III April 22, 2010 Ion Stoica http://inst.eecs.berkeley.edu/~cs162 Lec 22.2 4/13/10 CS162 ©UCB Spring 2010 Review • Link (datalink) layer: Broadcast network; frames sent by one host reaches every other host in same network – Multi-access protocol – (didn’t go over) construct frames, error detection and correction, flow control, … • Network layer: stitch together multiple link layer networks – Deliver a packet to specified network destination – (didn’t go over) segmentation/reassemble, packet scheduling, buffer management • Transport layer – Multiplexing/demultiplexing (two lectures ago) – Flow & congestion control, in-order delivery, reliability (today) Lec 22.3 4/13/10 CS162 ©UCB Spring 2010 Transport Protocol • Flow control keeps one fast sender from overwhelming a slow receiver • Congestion control keeps a set of senders from overloading the network • Reliability makes sure the receiver got all packets sent by sender • In-order delivery makes sure the receiver delivers the packet to application in same order sender sent them • Two protocols: – Stop-and-Wait – Window based Lec 22.4 4/13/10 CS162 ©UCB Spring 2010 Automatic Repeat reQuest (ARQ) Time Packet ACK Timeout Automatic Repeat Request Receiver sends acknowledgment (ACK) when it receives packet Sender waits for ACK and times out if does not arrive within some time period Simplest ARQ protocol Stop and Wait Send a packet, stop and wait until ACK arrives Sender ReceiverPage 2 Lec 22.5 4/13/10 CS162 ©UCB Spring 2010 Stop-and-Wait Properties • Flow control: yes – Receiver can implicitly slow down sender by acking a packet only if it has room for at lest another packet – Assumption: timeout doesn’t trigger before receiving ack • Congestion control: yes – Sender sends a new packet only after previous one made it – If network is congested packet or ack is lost sender doesn’t send new data • Reliability: yes – If a packet is lost, sender timeouts and resends the packet • In-order delivery: yes – Receiver doesn’t get next packet before receiving (and acking) previous one • So what’s the problem with Stop-and-Wait? Efficiency! Lec 22.6 4/13/10 CS162 ©UCB Spring 2010 How Fast Can Stop-and-Wait Go? • Suppose we’re sending from UCB to New York: – Bandwidth = 1 Mbps (megabits/sec) – RTT = 100 msec – Maximum packet size a.k.a. Maximum Transmission Unit (MTU) = 1500 B = 12,000 b – No other load on the path and no packet loss • What (approximately) is the fastest we can transmit using Stop-and-Wait? – Answer: 12,000b/0.1s = 120 kbps • How about if Bandwidth = 1 Gbps? Lec 22.7 4/13/10 CS162 ©UCB Spring 2010 Administrivia • Keys to access AWS will be sent today • Last two lectures on security • Final Exam – Friday, May 14, 7:00PM-10:00PM – All material from the course » With slightly more focus on second half, but you are still responsible for all the material – Two sheets of notes, both sides Lec 22.8 4/13/10 CS162 ©UCB Spring 2010 Sliding Window • Idea: allow multiple packets in-flight – “In-flight” = un-acked packets • Window size (W): number of packets the sender can send without receiving an ack – E.g., after receiving ack for all packet before and including K, send packets K+1, K+2, …, K+W+1 – Stop-and-wait: particular case of sliding window, W=1 • Receiver tells sender W – W cannot be larger than receiver’s buffer!Page 3 Lec 22.9 4/13/10 CS162 ©UCB Spring 2010 Throughput • Up to W packets (or bytes) per RTT • Throughput = W/RTT • How large should be the window to fully utilize a link with bandwidth B? – W = Bandwidth x RTT (i.e., “Bandwidth-Delay” or “Delay-Bandwidth” product) Lec 22.10 4/13/10 CS162 ©UCB Spring 2010 Sliding Window Example (This is NOT TCP !) • Sender – Sending rate = 1 pkt/s – Packet size = 1000b • Receiver: – Delivering rate = 0.5 pkt/s – Delivers packets in to application – Acknowledges (acks) each delivered pkt – Send negative ack. (nack) if packet lost • Round-trip time = 4 sec, 2sec each way • Receiver Window = 4 packets • Note: max. achievable throughput = 0.5pkt/s = 500b/s Lec 22.11 4/13/10 CS162 ©UCB Spring 2010 Sliding Window Example Sender Receiver 1 1 1s 2s 3s 4s 5s 6s 7s 8s 9s 10s 11s 12s 13s 14s • Sender, at 1s – Send 1st pkt Lec 22.12 4/13/10 CS162 ©UCB Spring 2010 Sliding Window Example Sender Receiver 1 1 1 1s 2s 3s 4s 5s 6s 7s 8s 9s 10s 11s 12s 13s 14s • Sender, at 1s – Send 1st pkt • Receiver, at 3s – Get 1st pkt – Deliver 1st pkt to appl. – Send ack=1 to sender ack=1Page 4 Lec 22.13 4/13/10 CS162 ©UCB Spring 2010 Sliding Window Example • Sender, at 2s – Send 2nd pkt, which is lost Sender Receiver 1 1 ack=1 1s 2s 3s 4s 5s 6s 7s 8s 9s 10s 11s 12s 13s 14s 2 1 2 Lec 22.14 4/13/10 CS162 ©UCB Spring 2010 Sliding Window Example 1s 2s 3s 4s 5s 6s 7s 8s 9s 10s 11s 12s 13s 14s Sender Receiver 1 2 1 3 2 1 3 1 2 3 ack=1 nack=2 • Sender, at 3s – Send 3nd pkt • Receiver, at 5s: – Get 3rd pkt; doesn’t deliver it since out of seq. – Send nack=2 (request 2nd pkt) Lec 22.15 4/13/10 CS162 ©UCB Spring 2010 Sliding Window Example 1s 2s 3s 4s 5s 6s 7s 8s 9s 10s 11s 12s 13s 14s Sender Receiver 1 2 1 3 2 1 3 1 2 3 ack=1 nack=2 • Sender, at 4s – Send 4th pkt – Receiver window full! • Receiver, at 6s – Get 4th packet 4 3 2 1 4 4 3 Lec 22.16 4/13/10 CS162 ©UCB Spring 2010 Sliding Window Example 1s 2s 3s 4s 5s 6s 7s 8s 9s 10s 11s 12s 13s 14s Sender Receiver 1 2 1 3 2 1 3 1 2 3 ack=1 nack=2 • Sender, at 5s – Get ack=1 – Remove 1st pkt from buffer – Send 5th pkt; now 2, 3, 4, 5 are in flight (window full!) • Receiver, at 7s – Get 5th pkt 4 3 2 1 4 4 3 5 4 3 2 5 4 3 5Page 5 Lec 22.17 4/13/10 CS162 ©UCB Spring 2010 Sliding Window Example 1s 2s 3s 4s 5s 6s 7s 8s 9s 10s 11s 12s 13s 14s Sender Receiver 1 2 1 3 2 1 3 1 2 3 ack=1 nack=2 • Sender, at 7s – Get nack=2 – Resend pkt 2 • Receiver, at 9s – Get 2nd pkt – Deliver it to appl. –
View Full Document
Unlocking...