Slide 1AnnouncementsFinal ExamOutlineRouting: Persistent OscillationsRouting: Persistent OscillationsRouting: Persistent OscillationsRouting: Persistent OscillationsOutlineTCP Congestion ControlThe big picture (with timeouts)The big picture (with timeouts)The big picture (with timeouts)The big picture (with timeouts)The big picture (with timeouts)The big picture (with timeouts)The big picture (with timeouts)The big picture (with timeouts)Congestion Detection RevisitedFast RetransmitsFast Retransmit and Fast RecoveryFast Recovery: After a Fast RetransmitOutlineDistance Vector Multicast Routing Protocol (DVRMP)Reverse Path FloodingReverse Path FloodingReverse Path BroadcastingTruncated Reverse BroadcastingTruncated Reverse BroadcastingPruning DetailsOutlineToken Bucket and Arrival CurveTraffic Enforcement: ExampleSource Traffic Characterization: Arrival CurveArrival Curve: ExamplePer-hop ReservationOutlineIntegrated ServicesControl Plane: Resource ReservationControl Plane: Resource ReservationControl Plane: Resource ReservationControl Plane: Resource ReservationControl Plane: Admission ControlControl Plane: Admission ControlData PlaneData PlaneData PlaneDifferentiated Services (DiffServ)Diffserv ArchitectureDifferentiated ServicesComparison to Best-Effort & IntservOutlineRouting in CANRouting in Chord using FingersRouting in Chord using FingersRecursive vs. Iterative RoutingFinal Exam1EE 122: Final ReviewIon StoicaTAs: Junda Liu, DK Moon, David Zatshttp://inst.eecs.berkeley.edu/~ee122/fa09 (Materials with thanks to Vern Paxson, Jennifer Rexford,and colleagues at UC Berkeley)AnnouncementsProject 2 due Friday, Dec 11, 11:59pmFinal exam: Dec 17, 8-11am, 10 Evans HallMy office hours next weekMy office hours: MW 10-11:30amThe office hours of everyone else unchangedFinal ExamOpen book, open notes!Crib sheets ok if you likeComprehensive, but greater focus on material since midtermQuestions similar in format to the first midtermProblem set-up descriptions + multipart fill-insAll answers on the exam sheets we hand outBring PENCIL, ERASER, no calculators neededOutlinePersistent OscillationsTCPMulticast: DVRMPToken BucketIntegrated & Differentiated ServicesRouting in Chord5Routing: Persistent OscillationsAssume link cost = amount of carried traffic ADCB000000No trafficADCB110000B to A: 1 unit of trafficD to A: 1 unit of traffic1 1ADCB11+ee100CA: e units of traffic11e6Routing: Persistent OscillationsAssume link cost = amount of carried traffic ADCB11+ee0e1100ADCB2+e0001+e1B to A:cost(BCDA) = 1 lowerthan cost(BA) = 1+eC to A:cost(CDA) = 1 lowerthan cost(CBA) = 1+2*e1 1eB to A: switches to BCDAC to A: switches to CDA7Routing: Persistent OscillationsAssume link cost = amount of carried traffic ADCB2+e000e111+e 1B to A:cost(BA) = 0 lower thancost(BCDA) = 4+2*eC to A:cost(CBA) = 0 lowerthan cost(CDA) = 3+2*eD to A:cost(DCBA) = 0 lowerthan cost(DA) = 2+eB to A: switches to BAC to A: switches to CBAD to A: switches to DCBAADCB02+e1+e10011e8Routing: Persistent OscillationsAssume link cost = amount of carried traffic B to A:cost(BCDA) = 0 lower thancost(BCDA) = 4+2*eC to A:cost(CBA) = 0 lowerthan cost(CDA) = 3+2*eD to A:cost(DCBA) = 0 lowerthan cost(DA) = 2+eB to A: switches to BCDAC to A: switches to CDAD to A: switches to DAADCB02+e1+e10011eADCB2+e0e01+e11 1eOutlinePersistent OscillationsTCPWireless MACMulticast: DVRMPToken BucketIntegrated & Differentiated ServicesRouting in CAN & ChordTCP Congestion ControlFlow control keeps one fast sender from overwhelming a slow receiverCongestion control keeps a set of senders from overloading the networkThree congestion control problems:Adjusting to bottleneck bandwidthWithout any a priori knowledgeCould be a Gbps link; could be a modemAdjusting to variations in bandwidthSharing bandwidth between flows11The big picture (with timeouts)TimecwndInitially: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;12The big picture (with timeouts)TimecwndSlowStartInitially: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;13The big picture (with timeouts)TimecwndTimeoutSlowStartInitially: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;1/2 cwndssthresh14The big picture (with timeouts)TimecwndTimeoutSlowStart1/2 cwndssthreshInitially: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;SlowStart15The big picture (with timeouts)TimecwndTimeoutSlowStartAIMDssthreshSlowStart1/2 cwndInitially: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;16The big picture (with timeouts)TimecwndTimeoutSlowStartAIMDTimeoutssthreshSlowStart1/2 cwndInitially: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;17The big picture (with timeouts)TimecwndTimeoutSlowStartAIMDTimeoutssthreshSlowStartSlowStartAIMD1/2 cwndInitially: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;18The big picture (with timeouts)TimecwndAIMDTimeoutSlowStartAIMDInitially:cwnd = 1;ssthresh = infinite;New ack received:if (cwnd < ssthresh) /* Slow Start*/ cwnd = cwnd +
View Full Document