EE 122 Final Review Ion Stoica TAs Junda Liu DK Moon David Zats http inst eecs berkeley edu ee122 fa09 Materials with thanks to Vern Paxson Jennifer Rexford and colleagues at UC Berkeley 1 Announcements Project 2 due Friday Dec 11 11 59pm Final exam Dec 17 8 11am 10 Evans Hall My office hours next week My office hours MW 10 11 30am The office hours of everyone else unchanged Final Exam Open book open notes Crib sheets ok if you like Comprehensive but greater focus on material since midterm Questions similar in format to the first midterm Problem set up descriptions multipart fill ins All answers on the exam sheets we hand out Bring PENCIL ERASER no calculators needed Outline Persistent Oscillations TCP Multicast DVRMP Token Bucket Integrated Differentiated Services Routing in Chord Routing Persistent Oscillations Assume link cost amount of carried traffic 0 A 0 D 0 0 B 0 0 C A 1 1 D 0 0 B 0 0 C 1 1 A 1 1 e D 0 0 B 1 e C 1 1 e No traffic B to A 1 unit of traffic D to A 1 unit of traffic C A e units of traffic Routing Persistent Oscillations Assume link cost amount of carried traffic 1 A 1 e D 0 0 B e 0 C 1 1 e B to A cost B C D A 1 lower than cost B A 1 e C to A cost C D A 1 lower than cost C B A 1 2 e 2 e A 0 D 1 e 1 B 0 0 C 1 1 e B to A switches to B C D A C to A switches to C D A Routing Persistent Oscillations Assume link cost amount of carried traffic 2 e A 0 D 1 e 1 B 0 0 C 1 1 e B to A cost B A 0 lower than cost B C D A 4 2 e C to A cost C B A 0 lower than cost C D A 3 2 e D to A cost D C B A 0 lower than cost D A 2 e A 0 2 e D 0 0 B 1 1 e C 1 1 e B to A switches to B A C to A switches to C B A D to A switches to D C B A Routing Persistent Oscillations Assume link cost amount of carried traffic A 0 2 e D 0 0 B 1 1 e C 1 1 2 e A 0 D 1 e 1 B e 0 C 1 1 e e B to A cost B C D A 0 lower than cost B C D A 4 2 e C to A cost C B A 0 lower than cost C D A 3 2 e D to A cost D C B A 0 lower than cost D A 2 e B to A switches to B C D A C to A switches to C D A D to A switches to D A Outline Persistent Oscillations TCP Wireless MAC Multicast DVRMP Token Bucket Integrated Differentiated Services Routing in CAN Chord TCP Congestion Control Flow control keeps one fast sender from overwhelming a slow receiver Congestion control keeps a set of senders from overloading the network Three congestion control problems Adjusting to bottleneck bandwidth Without any a priori knowledge Could be a Gbps link could be a modem Adjusting to variations in bandwidth Sharing bandwidth between flows The big picture with timeouts cwnd Initially cwnd 1 ssthresh infinite New ack received if cwnd ssthresh Slow Start cwnd cwnd 1 else Congestion Avoidance cwnd cwnd 1 cwnd Timeout Multiplicative decrease ssthresh cwnd 2 cwnd 1 Time 11 The big picture with timeouts Initially cwnd 1 ssthresh infinite New ack received if cwnd ssthresh Slow Start cwnd cwnd 1 else Congestion Avoidance cwnd cwnd 1 cwnd Timeout Multiplicative decrease ssthresh cwnd 2 cwnd 1 cwnd Slow Start Time 12 The big picture with timeouts Initially cwnd 1 ssthresh infinite New ack received if cwnd ssthresh Slow Start cwnd cwnd 1 else Congestion Avoidance cwnd cwnd 1 cwnd Timeout Multiplicative decrease ssthresh cwnd 2 cwnd 1 cwnd Timeout 1 2 cw nd ssthresh Slow Start Time 13 The big picture with timeouts Initially cwnd 1 ssthresh infinite New ack received if cwnd ssthresh Slow Start cwnd cwnd 1 else Congestion Avoidance cwnd cwnd 1 cwnd Timeout Multiplicative decrease ssthresh cwnd 2 cwnd 1 cwnd Timeout 1 2 cw nd ssthresh Slow Start Slow Start Time 14 The big picture with timeouts Initially cwnd 1 ssthresh infinite New ack received if cwnd ssthresh Slow Start cwnd cwnd 1 else Congestion Avoidance cwnd cwnd 1 cwnd Timeout Multiplicative decrease ssthresh cwnd 2 cwnd 1 cwnd Timeout 1 2 cw nd AIMD ssthresh Slow Start Slow Start Time 15 The big picture with timeouts cwnd Timeout 1 2 cw nd AIMD Timeout Initially cwnd 1 ssthresh infinite New ack received if cwnd ssthresh Slow Start cwnd cwnd 1 else Congestion Avoidance cwnd cwnd 1 cwnd Timeout Multiplicative decrease ssthresh cwnd 2 cwnd 1 ssthresh Slow Start Slow Start Time 16 The big picture with timeouts cwnd Timeout 1 2 cw nd AIMD Timeout Initially cwnd 1 ssthresh infinite New ack received if cwnd ssthresh Slow Start cwnd cwnd 1 else Congestion Avoidance cwnd cwnd 1 cwnd Timeout Multiplicative decrease ssthresh cwnd 2 cwnd 1 AIMD ssthresh Slow Start Slow Start Slow Start Time 17 The big picture with timeouts Initially cwnd 1 ssthresh infinite New ack received if cwnd ssthresh Slow Start cwnd cwnd 1 else Congestion Avoidance cwnd cwnd 1 cwnd Timeout Multiplicative decrease ssthresh cwnd 2 cwnd 1 cwnd Timeout AIMD AIMD AIMD sstresh Slow Start Slow Start Time 18 Congestion Detection Revisited Wait for Retransmission Time Out RTO In BSD TCP implementations RTO is usually more than 500ms RTO kills throughput The granularity of RTT estimate is 500 ms Retransmission timeout is RTT 4 mean deviation Solution Don t wait for RTO to expire 19 Fast Retransmits Resend a segment after 3 duplicate ACKs Duplicate ACK means that an out of sequence segment was received ACK 2 cwnd 2 Notes ACKs are for next expected packet Packet reordering can cause duplicate ACKs Window may be too small to get enough duplicate ACKs segment 2 segment 3 ACK 3 cwnd 4 segment 1 cwnd 1 3 duplicate ACKs ACK 4 ACK 4 segment 4 segment 5 segment 6 segment 7 ACK 4 ACK 4 20 Fast Retransmit and Fast Recovery cwnd AIMD Slow Start Fast retransmit Retransmit after 3 duplicated acks Time Prevent expensive timeouts Reduce slow starts At steady state cwnd oscillates around the optimal window size 21 Fast Recovery After a Fast Retransmit ssthresh cwnd 2 cwnd ssthresh For each dup ack arrival dupack Indicates packet left network so we may be able to send more MaxWindow min cwnd dupack AdvWin Receive ack for new data beyond initial dup ack Instead of setting cwnd to 1 cut cwnd in half multiplicative decrease dupack 0 Exit fast recovery But when RTO expires still do cwnd …
View Full Document
Unlocking...