Review Link datalink layer Broadcast network frames sent by one host reaches every other host in same network CS162 Operating Systems and Systems Programming Lecture 22 Multi access protocol didn t go over construct frames error detection and correction flow control Network layer stitch together multiple link layer networks Networking III Deliver a packet to specified network destination didn t go over segmentation reassemble packet scheduling buffer management April 22 2010 Ion Stoica http inst eecs berkeley edu cs162 Transport layer Multiplexing demultiplexing two lectures ago Flow congestion control in order delivery reliability today 4 13 10 Automatic Repeat Request Stop and Wait Send a packet stop and wait until ACK arrives 4 13 10 Lec 22 3 Page 1 Sender Simplest ARQ protocol Stop and Wait Window based Receiver sends acknowledgment ACK when it receives packet Sender waits for ACK and times out if does not arrive within some time period Timeout 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 CS162 UCB Spring 2010 Lec 22 2 Automatic Repeat reQuest ARQ Transport Protocol 4 13 10 CS162 UCB Spring 2010 Receiver Packe t ACK Time CS162 UCB Spring 2010 Lec 22 4 Stop and Wait Properties How Fast Can Stop and Wait Go Flow control yes Suppose we re sending from UCB to New York 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 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 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 What approximately is the fastest we can transmit using Stop and Wait Answer 12 000b 0 1s 120 kbps Reliability yes How about if Bandwidth 1 Gbps 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 4 13 10 CS162 UCB Spring 2010 4 13 10 Lec 22 5 Administrivia CS162 UCB Spring 2010 Lec 22 6 Sliding Window Keys to access AWS will be sent today Idea allow multiple packets in flight Last two lectures on security Window size W number of packets the sender can send without receiving an ack In flight un acked packets 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 Final Exam Friday May 14 7 00PM 10 00PM All material from the course Receiver tells sender W With slightly more focus on second half but you are still responsible for all the material W cannot be larger than receiver s buffer Two sheets of notes both sides 4 13 10 CS162 UCB Spring 2010 4 13 10 Lec 22 7 Page 2 CS162 UCB Spring 2010 Lec 22 8 Sliding Window Example This is NOT TCP Throughput Up to W packets or bytes per RTT Throughput W RTT Sender How large should be the window to fully utilize a link with bandwidth B Receiver Sending rate 1 pkt s Packet size 1000b W Bandwidth x RTT i e Bandwidth Delay or Delay Bandwidth product 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 4 13 10 CS162 UCB Spring 2010 4 13 10 Lec 22 9 Sliding Window Example Sender Sender at 1s 1 Receiver Sender 1s 2s 3s 1 Sender at 1s 1 Receiver 1s 2s 3s 1 Send 1st pkt 4s 5s 6s 1 ack 1 4s 5s 6s Receiver at 3s Get 1st pkt Deliver 1st pkt to appl Send ack 1 to sender 7s 8s 9s 10s 11s 12s 13s 14s CS162 UCB Spring 2010 Lec 22 10 Sliding Window Example Send 1st pkt 4 13 10 CS162 UCB Spring 2010 4 13 10 Lec 22 11 Page 3 7s 8s 9s 10s 11s 12s 13s 14s CS162 UCB Spring 2010 Lec 22 12 Sliding Window Example Sender Sender at 2s Send 2nd pkt which is lost 1 2 1 Sliding Window Example Receiver 2 Sender 1s 2s 3s 1 1 ack Sender at 3s Send 3nd pkt Receiver at 5s 4s 5s 6s 1 2 1 3 2 1 Receiver 2 3 3rd Get pkt doesn t deliver it since out of seq Send nack 2 request 2nd pkt 7s 8s 9s 10s 11s 1s 2s 3s 1 1 ack 2 nack 4s 5s 6s 3 7s 8s 9s 10s 11s 12s 13s 14s 4 13 10 CS162 UCB Spring 2010 12s 13s 14s 4 13 10 Lec 22 13 Sliding Window Example Sender Sender at 4s Send 4th pkt Receiver window full 1 2 1 3 2 1 4 3 2 1 Receiver Receiver at 6s Sender 1s 2s 3s 1 ack 2 nack Sender at 5s 3 4 3 7s 8s 9s 10s 11s 12s 13s 14s CS162 UCB Spring 2010 1 2 1 3 2 1 Get ack 1 Remove 1st pkt 4 3 2 1 from buffer 5 4 3 2 th Send 5 pkt now 2 3 4 5 are in flight window full 4s 5s 6s Get 4th packet 4 13 10 Lec 22 14 Sliding Window Example 1 2 3 4 CS162 UCB Spring 2010 Receiver 1s 2s 3s 1 2 3 4 5 1 ack 2 nack 3 4 3 5 4 3 Get 5th pkt 4 13 10 Page 4 7s 8s 9s 10s 11s 12s 13s 14s Receiver at 7s Lec 22 15 4s 5s 6s CS162 UCB Spring 2010 Lec 22 16 Sliding Window Example Sender Sender at 7s Get nack 2 Resend pkt 2 Receiver at 9s Get 2nd pkt Deliver it to appl Send ack 2 2 3 2 4 3 2 5 4 3 1 1 1 1 2 5 4 3 2 Sliding Window Example Receiver 2 3 4 5 1 ack 2 nack 2 2 ack Sender 1s 2s 3s 1 3 4 3 5 4 3 5 4 3 Receiver at 11s Deliver 3d pkt to appl recall delivery rate is 1pkt every 2s Send ack 3 9s 10s 11s 12s 13s 14s 4 13 10 CS162 UCB Spring 2010 4 13 10 Lec 22 17 Sliding Window Example If no more losses throughput 0 5pkt sec This is max throughput as receiver cannot deliver more than 0 5pkt sec 4 13 10 5 4 …
View Full Document
Unlocking...