Computer Networks Dr. Jorge A. Cobb Congestion Control2 Outline l Queuing Discipline l Reacting to Congestion l Avoiding Congestion3 Issues l Congestion: input rate exceeds output rate l Avoidance vs Control: • pre-allocate resources so as to avoid congestion (avoidance) • control congestion if (and when) it occurs (control) l Underlying service model • best-effort (assume for now) • multiple qualities of service (later) Destination 1.5-Mbps T1 link Router Source 2 Source 1 10-Mbps Ethernet4 Framework l Flow • sequence of packets sent between source/destination pair l Connectionless flows • maintain soft state (if any) at the routers (not created/removed by signaling) l Connection-oriented flows • State at each router is explicitly allocated for the flow (like virtual circuits) Router Source 2 Source 1 Source 3 Router Router Destination 2 Destination 15 Taxonomy of schemes l Point of implementation? • router-centric versus host-centric l Resource allocation scheme? • reservation-based: literally reserve resources • feedback-based: the network tells you to go faster/slower • explicit feedback • implicit feedback (TCP) l Rate control Method? • window-based (TCP) • rate-based6 Evaluation Criteria l Fairness – allocate resources fairly among flows. l Power (ratio of throughput to delay) • If you increase load • Packet losses increase • Queuing delay increases Optimal load Load Throughput/delay7 Queuing Discipline (Scheduling) l First-In-First-Out (FIFO) • does not discriminate between traffic sources (one queue for all) l Fair Queuing (FQ) • explicitly segregates traffic based on flows (how?) • ensures no flow captures more than its share of capacity • variation: weighted fair queuing (WFQ) l FQ problems: • How to differentiate between flows • Must consider variable packet size Flow 1 Flow 2 Flow 3 Flow 4 Round-robin service8 Fair Queuing Algorithm l In FQ, there are two “servers” (or systems) • The real system • This is the real router with a real output link and the real flows arriving into the router • The “fake” system • It does not exist • Has the same output link capacity as the real system • Has the same input flows (with the same packets) as the real system • However, it is a “bit-by-bit” (fluid) server, not a packet server.9 The “fake” system l Bit-by-bit round-robin server • not real service!, i.e. fake! l Suppose a fake clock ticks each time a bit is transmitted from every active flow (i.e., after each round) • i.e., it is not a real-time clock l Let Lf,i denote the length of f.i, i.e., ith packet of flow f l Let Sf,i denote the fake time when start to transmit packet i l Let Ff,i denote the fake time when finish transmitting packet i Ff,i = Sf,i + Lf,iComputing Sf,i l When does the (fake) server start to transmit first bit of packet f,i? i.e., what is Sf,i? • if when f,i arrives, server has not finished packet f,(i -1) from f, then immediately after last bit of f,(i – 1), i.e., Sf,i = Ff,i-1 • if no current packets queued for this flow, then start transmitting f,i when it arrives, i.e., Sf,i = Vf,i • where Vf,i is the fake time when the packet arrives l Thus: Ff,i = Sf,i + Lf,i = MAX (Ff,i - 1, Vf,i) + Lf,i 1011 Calculating V l V is not “real-time” l It grows depending on the number of backlogged flows • Output channel rate is constant • We tick after transmitting one bit of each flow • If more flows, then it takes more time to transmit one bit of each flow (the round takes more time) • Hence, the number of queued flows dictates how fast (with respect to real-time) V grows.12 Virtual time rate changes with backlogged flows time V(t) Virtual time of real time t Backlogged flows at fake server increased Backlogged flows at fake server decreased13 Calculating V (continued) l Actually, the rate of growth of V “changes” when the set of backlogged flows (i.e. with non-empty queue) changes. • The rate of growth increases when a flow is no longer queued • The rate of growth decreases when a the queue of a flow becomes non-empty l It is somewhat of a mess to compute it • We will cover all the gory details soon …14 “Real” FQ Server l Packets are sent out according to which one would exit the fake server first. (try to mimic the fake server) l When a packet Pf,i is received • Compute the value Ff,i (this depends on V) • Insert packet into a priority queue, ordered by F value l When the output channel becomes idle • Retrieve the packet from the priority queue with least F value • I.e. the one that would exit first from the fake server. • Transmit this packet.15 FQ Algorithm limitations l Want to emulate the behavior of the bit-by-bit server as much as possible • We want each packet to exit from the real server no later than it exits from the bit-by-bit server • However, not perfect: can’t preempt current packet, so exit time may be greater l Example Flow 1 Flow 2 (a) What you want (b) What you may get instead Output Output F = 8 F = 10 F = 5 F = 10 F = 2 Flow 1 (arriving) Flow 2 (transmitting)16 TCP Congestion Control l Idea • assumes best-effort network (FIFO or FQ routers) • each source determines network capacity for itself • uses implicit feedback • ACKs pace transmission (self-clocking) l Challenge • determining the available capacity in the first place • adjusting to changes in the available capacitySliding Window Protocol (review) 17 Receiver Sender Data Data Data Data Receiver Sender Data ACK Time Data ACK Data ACK Data ACK Advantages: • More frames in pipe • Less time overall Data Data Data Data Data Data Data Data ACK ACK ACK ACK ACKMessage Sequence Numbers l TCP transfers a stream of bytes to the destination l data(x): • x is the sequence number, assume the message is L bytes long • x corresponds to the stream byte number of the first byte in the message • The next data message has sequence number x+L l ack(y): • Ack’s are cumulative, it indicates the receiver has received bytes 0
View Full Document
Unlocking...