Lecture notes on Congestion control

lecture notes congestion control algorithms, tcp congestion control lecture notes, congestion control vs flow control,congestion control mechanism,pdf free download
Dr.GriffinWood Profile Pic
Dr.GriffinWood,United Kingdom,Teacher
Published Date:23-07-2017
Your Website URL(Optional)
Comment
' COMPUTER NETWORKS CS 45201 CS 55201 CHAPTER 6 Congestion Control P. Farrell and H. Peyravi Department of Computer Science Kent State University Kent, Ohio 44242 farrellmcs.kent.edu http://www.cs.kent.edu/farrell Fall 2001 & % CS 4/55201: Computer Networks Fall 2001' COMPUTER NETWORKS CS 45201 CS 55201 CHAPTER 6 Congestion Control P. Farrell and H. Peyravi Department of Mathematics and Computer Science Kent State University Kent, Ohio 44242 farrellcs.kent.edu Fall 2001 & % CS 4/55201: Computer Networks Fall 2001' Contents  Congestion Control Issues  Queuing Disciplines  TCP Congestion Control  Congestion Avoidance Mechanisms & % CS 4/55201: Computer Networks Fall 200110 Mbps Ethernet Chapter 6: Congestion Control Congestion Control Issues ' Congestion Control Issues  Two sides of the same coin I pre-allocate resources so that to avoid congestion I send data and control congestion if (and when) is occurs Source 1 Router Dest 1.5 Mbps T1 Link Source 2  Two points of implementation I hosts at the edges of the network (transport protocol) I routers inside the network (queuing discipline)  Underlying service model I best-e ort (assume for now) I multiple qualities of service (later) & % CS 4/55201: Computer Networks Fall 2001 1 of ?? 100 Mbps FDDIChapter 6: Congestion Control Congestion Control Issues '  Connectionless ows I sequence of packets sent between source/destination pair I maintain soft state at the routers Source 1 Router Dest 1 Router Source 2 Router Dest 2 Source 3  Taxonomy I router-centric versus host-centric I reservation-based versus Feedback-based I window-based versus rate-based  Evaluation I fairness I power (ratio of throughput to delay) Throughput Power = Delay Optimal Load Load & % CS 4/55201: Computer Networks Fall 2001 2 of ??Chapter 6: Congestion Control Queuing Disciplines ' Queuing Disciplines  First-In-First-Out (FIFO) I does not discriminate between trac sources  Fair Queuing (FQ) I explicitly segregates trac based on ows I ensures no ow captures more than its share of capacity I variation: weighted fair queuing (WFQ) Flow 1 Flow 2 Round−Robin Service Flow 3 Flow 4 & % CS 4/55201: Computer Networks Fall 2001 3 of ??Chapter 6: Congestion Control Queuing Disciplines '  Problem: packets not all the same length I really want bit-by-bit round robin I not feasible to interleave bits (schedule on packet basis) I simulate by determining when packet would nish  For a single ow I suppose clock ticks each time a bit is transmitted I let P denote the length of packet i i I let S denote the time when start to transmit packet i i I let F denote the time when nish transmitting packet i i I F = S + P i i i I When does router start transmitting packet i?  If before router nished packet i 1 from this ow, then immediately after last bit of i 1 (F ) i1  If no current packets for this ow, then start transmitting when arrives (call this A ) i I Thus: F = MAX(F ; A ) + P i i1 i i  For multiple ows I calculate F for each packet that arrives on each ow i I treat all F 's as timestamps i I next packet to transmit is one with lowest timestamp  Not perfect: can't preempt the packet currently being transmitted & % CS 4/55201: Computer Networks Fall 2001 4 of ??Chapter 6: Congestion Control TCP Congestion Control ' TCP Congestion Control  Idea I assumes best-e ort network (FIFO or FQ routers) I each source determines network capacity for itself I uses implicit feedback I ACKs pace transmission (self-clocking)  Challenge I determining the available capacity in the rst place I adjusting to changes in the available capacity & % CS 4/55201: Computer Networks Fall 2001 5 of ??Chapter 6: Congestion Control TCP Congestion Control ' Additive Increase/Multiplicative Decrease  Objective: adjust to changes in the available capacity  New state variable per connection: CongestionWindow I limits how much data source has in transit MaxWin = MIN(CongestionWindow, AdvertisedWindow) EffWin = MaxWin - (LastByteSent - LastByteAcked)  Idea: I increase CongestionWindow when congestion goes down I decrease CongestionWindow when congestion goes up  Question: how does the source determine whether or not the network is congested?  Answer: a timeout occurs I timeout signals that a packet was lost I packets are seldom lost due to transmission error I lost packet implies congestion & % CS 4/55201: Computer Networks Fall 2001 6 of ??Chapter 6: Congestion Control TCP Congestion Control '  Algorithm: I increment CongestionWindow by one packet per RTT (linear increase) I divide CongestionWindow by two whenever a timeout occurs (multiplicative decrease) Source Destination  In practice: increment a little for each ACK Increment = (MSS MSS)/CongestionWindow CongestionWindow += Increment where MSS is maximum message size & % CS 4/55201: Computer Networks Fall 2001 7 of ?? . . .Chapter 6: Congestion Control TCP Congestion Control '  Example trace: sawtooth behavior 70 60 50 40 30 20 10 0 1.0 2.0 3.0 4.0 5.0 6.0 7.0 8.0 9.0 10.0 Time in seconds & % CS 4/55201: Computer Networks Fall 2001 8 of ?? KBChapter 6: Congestion Control TCP Congestion Control ' Slow Start  Objective: determine the available capacity in the rst place  Idea: I begin with CongestionWindow = 1 packet I double CongestionWindow each RTT Source Destination  Exponential growth, but slower than all in one blast  Used... I when rst starting connection I when connection goes dead waiting for a timeout & % CS 4/55201: Computer Networks Fall 2001 9 of ?? . . .Chapter 6: Congestion Control TCP Congestion Control ' Fast Retransmit and Fast Recovery  Problem: coarse-grain TCP timeouts lead to idle periods  Fast retransmit: use duplicate ACKs to trigger retransmission segment 1 segment 2 segment 3 ack 1 segment 4 ack 2 segment 5 ack 2 segment 6 ack 2 ack 2 retransmit segment 3 ack 6 & % CS 4/55201: Computer Networks Fall 2001 10 of ??Chapter 6: Congestion Control Congestion Avoidance Mechanisms ' Congestion Avoidance Mechanisms  TCP's strategy I to control congestion once it happens I to repeatedly increase load in an e ort to nd the point at which congestion occurs, and then back o  Alternative strategy I predict when congestion is about to happen, and reduce the rate at which hosts send data just before packets start being discarded I we call this congestion avoidance, to distinguish it from congestion control  Two possibilities I router-centric: DECbit and RED Gateways I host-centric: TCP Vegas & % CS 4/55201: Computer Networks Fall 2001 11 of ??Chapter 6: Congestion Control Congestion Avoidance Mechanisms ' DECbit  Add binary congestion bit to each packet header  Router I monitors average queue length over last busy+idle plus current busy cycle Queue Length Current Time Time Previous Current Cycle Cycle Averaging Interval I set congestion bit if average queue length greater than 1 when packet arrives I attempts to balance throughput against delay  End Hosts I destination echos bit back to source I source records how many packets resulted in set bit I if less than 50% of last window's worth had bit set, then increase CongestionWindow by 1 packet I if 50% or more of last window's worth had bit set, then decrease CongestionWindow by 0.875 times & % CS 4/55201: Computer Networks Fall 2001 12 of ??Chapter 6: Congestion Control Congestion Avoidance Mechanisms ' Random Early Detection (RED) Gateways  Noti cation is implicit I just drop the packet (TCP will timeout) I could make explicit by marking the packet  Early random drop I rather than wait for queue to become full, drop each arriving packet with some drop probability whenever the queue length exceeds some drop level  RED: lls in the details I compute average queue length AvgLen = (1 - Weight) AvgLen + Weight SampleLen  0 Weight 1 (usually 0.002)  SampleLen is queue length each time a packet arrives Queue length Instantaneous Average Time & % CS 4/55201: Computer Networks Fall 2001 13 of ??Chapter 6: Congestion Control Congestion Avoidance Mechanisms '  two queue length thresholds if AvgLen = MinThreshold then enqueue the packet if MinThreshold AvgLen MaxThreshold calculate probability P drop arriving packet with probability P if MaxThreshold = AvgLen drop arriving packet MaxThreshold MinThreshold AvgLength  probability P I not xed I function of AvgLen and how long since last drop (count) keeps track of new packets that have been queued while AvgLen has been between the two thresholds TempP = MaxP (AvgLen - MinThreshold) / (MaxThreshold - MinThreshold) P = TempP/(1 - count TempP) & % CS 4/55201: Computer Networks Fall 2001 14 of ??Chapter 6: Congestion Control Congestion Avoidance Mechanisms ' P(drop) 1.0 MaxP AvgLen MinThresh MaxThresh  Notes I probability of dropping a particular ow's packet(s) is roughly proportional to the share of the bandwidth that ow is currently getting I MaxP is typically set to 0.02, meaning that when the average queue size is halfway between the two thresholds, the gateway drops roughly one out of 50 packets. I if trac is bursty, then MinThreshold should be suciently large to allow link utilization to be maintained at an acceptably high level I di erence between two thresholds should be larger than the typical increase in the calculated average queue length in one RTT; setting MaxThreshold to twice MinThreshold is reasonable for trac on today's Internet & % CS 4/55201: Computer Networks Fall 2001 15 of ??Chapter 6: Congestion Control Congestion Avoidance Mechanisms ' TCP Vegas  Idea: source watches for some sign that some router's queue is building up and congestion will happen soon; e.g., I RTT is growing I sending rate attens  Algorithm I let BaseRTT be the minimum of all measured RTTs (commonly the RTT of the rst packet) I if not over owing the connection, then ExpectedRate = CongestionWindow / BaseRTT I source calculates current sending rate (ActualRate) once per RTT (read how) I source compares ActualRate with ExpectedRate Diff = ExpectedRate - ActualRate if Diff increase CongestionWindow linearly else if Diff decrease CongestionWindow linearly else leave CongestionWindow unchanged & % CS 4/55201: Computer Networks Fall 2001 16 of ??Chapter 6: Congestion Control Congestion Avoidance Mechanisms '  Parameters I : 1 packet I : 3 packets  Why not multiplicative decrease?  Go to multiplicative if there is a timeout & % CS 4/55201: Computer Networks Fall 2001 17 of ??

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.