ECE544: Communication Networks-II, Spring 2010Today’s LectureCongestion Control & QoS in Packet NetworksNetwork CongestionQueue SchedulingFIFO QueuingFair QueuingFQ illustrationSome ComplicationsBit-by-bit RRSlide 11Congestion AvoidanceCongestion Control via Feedback to SourceCongestion Control via Router FeedbackSolving the Full Queues ProblemRandom Early Detection (RED)Slide 17RED AlgorithmRED OperationQuality of ServiceRealtime ApplicationsPlayback BufferExample Distribution of DelaysComponents of Integrated Services architectureTypes of guaranteesInternet service classes proposed by IETFTaxonomy of applicationsOverview 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 ManagementGeneric Cell Rate AlgorithmSmooth TrafficBursty TrafficPayload Type IdentifierABR FeedbackExample Source Cell Rate ProfileDiffServTypes of serviceDifferences with RSVPPremium servicePremium traffic flow2-bit differentiated serviceLeaf router input functionalityMarker function in routersMarkers to implement two different servicesOutput forwardingRouter output interface for two-bit architectureBorder router input interface Profile MetersRed with In or Out (RIO)RIO drop probabilitiesToday’s HomeworkECE544: Communication Networks-II, Spring 2010D. RaychaudhuriLecture 7Includes teaching materials from 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:–Which packet to serve (transmit) next–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•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–calculate Fi for each packet–transmit packet with lowest FiBit-by-bit RRSource 1Source 2Outbound Link1 unit/secPkt 2-1=3 unitsPkt 1-1=2 unitsPkt 2-2=2 unitsPkt 1-2=1 unitPkt 1-3=1 unitChannel clock - 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 3 4 5Congestion Avoidance•TCP approach:–Detect congestion after it happens and back off on offered rate–Increase load trying to maximize utilization until loss occurs•Alternatively:–We can try to predict congestion and reduce rate before loss occurs–This is called congestion avoidanceCongestion Control via Feedback to Source•TCP’s “blind” approach:–Detect congestion 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-outPkt lossclearedAdditive increaseMultiplicative decreaseCongestion 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•Drop packets before queue becomes full (early drop)•Intuition: notify senders of incipient congestion–Example: early random drop (ERD):•If qlen > drop level, drop each new packet with 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•Avoid bias against bursty traffic•Some protection against ill-behaved usersRED Algorithm•Maintain running average of queue length•If avg < minth do nothing–Low queuing, send packets through•If avg > maxth, drop packet–Protection from misbehaving sources•Else mark packet in a manner proportional to queue length–Notify sources of incipient congestionRED OperationMin threshMax threshAverage queuelengthminthresh maxthreshMaxP1.0Avg lengthP(drop)Quality of ServiceOutlineRealtime ApplicationsIntegrated ServicesDifferentiated ServicesRealtime Applications•Require “deliver on time” assurances–must come from inside the network–Example