EECS 122: Introduction to Computer Networks Midterm II ReviewTopics to be CoveredSlide 3Transport LayerUDPTCPTCP ServiceFlow Control vs. Congestion ControlCongestion Window (cwnd)Slide 10Why do You Care About Congestion Control?Solutions?TCP: Slow StartSlow Start ExampleCongestion AvoidanceSlow Start/Congestion Avoidance ExamplePutting Everything Together: TCP PseudocodeThe big picturePacket Loss DetectionFast RetransmitFast RecoveryFast Retransmit and Fast RecoveryTCP FlavorsTCP VegasTCP-SACKSlide 26Packet SchedulingGoals of Packet SchedulingRandom Early Detection (RED)RED AdvantagesExplicit Congestion NotificationECN AdvantagesSlide 33Token Bucket and Arrival CurveSource Traffic CharacterizationSource Traffic Characterization: ExampleQoS Guarantees: Per-hop ReservationPacket Scheduling and Fair QueuingFluid Flow System: ExamplePacket System: ExampleExample: Problem 6.14 (a)Solution: Virtual TimeSlide 43Properties of WFQWhat You Need to KnowSlide 46Differentiated ServicesAdvantages of DiffServDisadvantages of DiffServIntegrated ServicesResource Reservation Protocol: RSVPAdvantages of IntServDisadvantages of IntServSlide 54Katz, Stoica F04EECS 122: Introduction to Computer Networks Midterm II ReviewComputer Science DivisionDepartment of Electrical Engineering and Computer SciencesUniversity of California, BerkeleyBerkeley, CA 94720-17762Katz, Stoica F04Topics to be CoveredTransport ProtocolsCongestion Control and Congestion Avoidance concepts, TCP variantsQoS (Packet Scheduling) and Congestion Control (RED) MechanismsFluid Model and Token Bucket methodEssential DiffServ and IntServ ConceptsP&D: Sections 5.1, 5.2, 6.1- 6.3, 6.4.2, 6.5.1- 6.5.3Project #2 Specification3Katz, Stoica F04Topics to be CoveredTransport ProtocolsCongestion Control and Congestion Avoidance concepts, TCP variantsQoS (Packet Scheduling) and Congestion Control (RED) MechanismsFluid Model and Token Bucket methodEssential DiffServ and IntServ Concepts4Katz, Stoica F04Transport LayerProvide a way to decide which packets go to which applications (multiplexing/demultiplexing)Can provide more reliability, in order delivery, at most once deliveryCan support messages of arbitrary lengthGovern when hosts should send data can implement congestion and flow control5Katz, Stoica F04UDPUser Datagram ProtocolMinimalist transport protocolSame best-effort service model as IPMessages up to 64KBProvides multiplexing/demultiplexing to IPDoes not provide flow and congestion controlApplication examples: video/audio streaming6Katz, Stoica F04TCPTransmission Control ProtocolReliable, in-order, and at most once deliveryMessages can be of arbitrary lengthProvides multiplexing/demultiplexing to IPProvides congestion control and avoidanceApplication examples: file transfer, chat7Katz, Stoica F04TCP Service1) Open connection2) Reliable byte stream transfer from (IPa, TCP Port1) to (IPb, TCP Port2)•Indication if connection fails: Reset3) Close connection8Katz, Stoica F04Flow Control vs. Congestion ControlFlow control: regulates how much data can a sender send without overflowing the receiverCongestion control: regulates how much data can a sender send without congesting the networkCongestion: dropping packets into the network due to buffer overflow at routers9Katz, Stoica F04Congestion Window (cwnd) Limits how much data can be in transit, i.e., how many unacknowledged bytes can the sender sendEffectiveWindow = MaxWindow – (LastByteSent – LastByteAcked)MaxWindow = min(cwnd, AdvertisedWindow) LastByteAcked LastByteSentsequence number increasesAdvertisedWindow is used for flow control10Katz, Stoica F04Topics to be CoveredTransport ProtocolsCongestion Control and Congestion Avoidance concepts, TCP variantsQoS (Packet Scheduling) and Congestion Control (RED) MechanismsFluid Model and Token Bucket methodEssential DiffServ and IntServ Concepts11Katz, Stoica F04Why do You Care About Congestion Control?Otherwise you get to congestion collapseHow might this happen?-Assume network is congested (a router drops packets) -You learn the receiver didn’t get the packet•Either by ACK or Timeout-What do you do? -Retransmit packet-Still receiver didn’t get the packet (because it is dropped again)-Retransmit again-…. and so on …-And now assume that everyone is doing the same!Network will become more and more congested-And this with duplicate packets rather than new packets!12Katz, Stoica F04Solutions?Increase buffer size. Why not?Slow down-If you know that your packets are not delivered because network congestion, slow downQuestions:-How do you detect network congestion? Use packet loss as indication!-By how much do you slow down?13Katz, Stoica F04TCP: Slow StartGoal: discover congestion quicklyHow? -Quickly increase cwnd until network congested get a rough estimate of the optimal size of cwnd:-Whenever starting traffic on a new connection, or whenever increasing traffic after congestion was experienced:• Set cwnd =1 • Each time a segment is acknowledged increment cwnd by one (cwnd++).14Katz, Stoica F04Slow Start ExampleThe congestion window size grows very rapidlyTCP slows down the increase of cwnd when cwnd >= ssthresh segment 1cwnd = 1cwnd = 2segment 2segment 3cwnd = 4segment 4segment 5segment 6segment 7cwnd = 8cwnd = 315Katz, Stoica F04Congestion AvoidanceAdditive increase: starting from the rough estimate, slowly increase cwnd to probe for additional available bandwidthMultiplicative decrease: cut congestion window size aggressively if a timeout occursIf cwnd > ssthresh then each time a segment is acknowledged increment cwnd by 1/cwnd (cwnd += 1/cwnd).16Katz, Stoica F04Slow Start/Congestion Avoidance ExampleAssume that ssthresh = 8cwnd = 1cwnd = 2cwnd = 4cwnd = 8cwnd = 9cwnd = 10Roundtrip timesCwnd (in segments)ssthresh17Katz, Stoica F04Putting Everything Together:TCP PseudocodeInitially: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;18Katz, Stoica F04The big pictureTimecwndTimeoutSlow StartCongestionAvoidancesstresh19Katz, Stoica F04Packet Loss DetectionWait for Retransmission Time Out (RTO)What’s the problem with this? Because RTO is performance killerIn the BSD TCP implementation,
View Full Document
Unlocking...