Slide 1Today’s LectureCongestion Control & QoS in Packet NetworksNetwork CongestionQueue SchedulingFIFO QueuingFair QueuingFQ illustrationSome ComplicationsBit-by-bit RRBit-by-bit RRWeighted Fair Queuing (WFQ)Congestion Control and Congestion AvoidanceCongestion Control via Router FeedbackSolving the Full Queues ProblemRandom Early Detection (RED)Random Early Detection (RED)RED AlgorithmRED OperationExplicit Congestion ControlQuality of ServiceRealtime ApplicationsPlayback BufferExample Distribution of DelaysApplication requirements & Services ClassesTaxonomy of applicationsComponents of Integrated Services architectureTypes of guaranteesInternet service classes proposed by IETFOverview of mechanismsFlowspecsToken bucket filterToken bucket operationTB characteristicsToken bucket specsAdmission controlReservation protocol: RSVPRSVPBasic message typesMaking a reservationPATH messagesPATH and RESV messagesSoft StateRouter handling of RESV messagesPacket classifying and schedulingRSVP and multicastRSVP versus ATM (Q.2931)ATM Service CategoriesTraffic ShapingTraffic PolicingDifferentiated Services (DiffServ)Differentiated Services (cont)IP DiffServDiffServExpedited Forwarding (EF)Assured Forwarding (AF)An Example DiffServ Network ImplementationPremium traffic flow2-bit differentiated serviceLeaf router input functionalityMarkers to implement two different servicesRouter output interface for two-bit architectureBorder router input interface Profile MetersRed with In or Out (RIO)Today’s HomeworkECE544: Communication Networks-II, Spring 2011D. RaychaudhuriLecture 8 (QoS)Includes teaching materials from D. Raychaudhuri, L. PetersonToday’s Lecture•Congestion control in best effort networks–Basic principles & mechanisms–FQ, WFQ, congestion feedback, TCP, RED•Quality-of-service (QoS)–Mechanisms (traffic shaping, admission control, reservation, priority queuing)–RSVP Intserv and Diffserv, RIO–Comparison to ATM (CBR, VBR; ABR)Congestion Control & QoS in Packet Networks•Congestion control – reactive methods used in best effort networks–Packet scheduling at network nodes–Feedback congestion control•End-to-end•Hop-by-hop•QoS control – proactive methods used for premium or guaranteed services:–Source traffic shaping & policing at entry points–Priority queuing and packet drop at routers–End-to-end reservation and admission controlNetwork Congestion•All networks have saturating throughput–Reduction in performance beyond max capacity–Need to keep input load below G0–Also must avoid unstable equilibrium point in overload regionOverloadregionNormal operatingPoint (G0)Capacity LimitSmaxOffered Traffic (G)ThruTrafficmarginCongestion control policiesUnstable network loadStable network load lineswith congestion controlQueue Scheduling•A queue scheduler employs 2 strategies:–Scheduling discipline: Which packet to serve (transmit) next–Drop policy: Which packet to drop next (when required)FIFO Queuing•FIFO:first-in-first-out (or FCFS: first-come-first-serve)•Arriving packets get dropped when queue is full regardless of flow or importance - implies drop-tail•Important distinction:–FIFO: scheduling discipline–Drop-tail: drop policyFair Queuing•Main idea:–maintain a separate queue for each flow currently flowing through router–router services queues in Round-Robin fashionFQ illustrationFlow 1Flow 2Flow nI/PO/PVariation: Weighted Fair Queuing (WFQ)Some Complications•Packets are of different length•We really need bit-by-bit round-robin (RR)•FQ simulates bit-by-bit RR–Not feasible to interleave bits!Bit-by-bit RR•Single flow: suppose clock ticks when a bit is transmitted. For packet i:–Pi: length, Ai = arrival time, Si: begin transmit time, Fi: finish transmit time. Fi = Si+Pi–Fi = max (Fi-1, Ai) + Pi•Multiple flows: clock ticks when a bit from all active flows is transmitted, that is, the clock advances by one tick when n bits are transmitted (assuming n flows)–calculate Fi for each packet–transmit packet with earliest Fi•RR is only simulated, packet in transmission is not interrupted. •If n flows have data to transmit, each gets 1/nth bandwidth.Bit-by-bit RRFlow 1Flow 2Pkt 2-1=3 unitsPkt 1-1=2 unitsPkt 2-2=2 unitsPkt 1-2=1 unitPkt 1-3=1 unitChannel clock - 1-1P(1,1) = 2P(1,2) = 1P(1,3) = 1P(2,1) = 3P(2,2) = 2Start with A(*,*)=0 (all pkts arrive at T=0)F(1,1) = 1F(1,2) = 1.5F(1,3) = 2F(2,1) = 1.5F(2,2) = 2.5Fi = max (Fi-1, Ai) + Pi2-1 1-2 1-3 2-2Weighted Fair Queuing (WFQ)•Weighted Fair Queuing (WFQ): assign a weight to each flow–Assume transmitting wq bits each time the router serves queue q (simulate in packet scheduling)–Control the percentage of the link’s bandwidth that a flow will get•The bandwidth that flow q gets (n active queues sending data): –FQ is a special case of WFQ with a weight of 1 for each queuenqqqqwwB1Congestion Control and Congestion Avoidance•TCP’s “blind” approach:–Detect congestion (loss) after it happens and back off on offered rate–Increase load trying to maximize utilization until loss occursSourceRate(bps)Congestion detected(via packet loss)Time-out•Alternatively:–We can try to predict congestion and reduce rate before packets start being discarded–This is called congestion avoidanceCongestion Control via Router Feedback•Router has unified view of queuing behavior•Routers can distinguish between propagation and persistent queuing delays•Routers can decide on transient congestion, based on workloadSolving the Full Queues Problem•Router monitor the load•Drop (or mark) packets before queue becomes full (early drop)•Intuition: notify senders of incipient congestion–Simple example: •If qlen > drop level, drop (or mark) each new packet with a fixed probability p•Does not control misbehaving usersRandom Early Detection (RED)•Motivation:–High bw-delay flows have large queues to accommodate transient congestion–TCP detects congestion from loss - after queues have built up and increase delay•Aim:–Keep throughput high and delay low–Accommodate burstsRandom Early Detection (RED)•Detect incipient congestion, allow bursts•Keep power (throughput/delay) high–keep average queue size low–assume hosts respond to lost packets•Avoid window synchronization–randomly mark packets, instead of dropping•Avoid bias against bursty traffic•Some protection against ill-behaved usersRED Algorithm•Maintain running average of queue