15-744: Computer NetworkingQoSOverviewCore-Stateless Fair QueuingSlide 5Core Router BehaviorF vs. AlphaSlide 8How does XCP Work?Slide 10Slide 11How Does an XCP Router Compute the Feedback?Getting the devil out of the details …Slide 14MotivationInelastic ApplicationsWhy a New Service Model?Utility Curve ShapesUtility curve – Elastic trafficAdmission ControlUtility Curves – Inelastic trafficSlide 22Slide 23Components of Integrated Services1. Type of commitmentPlayback ApplicationsCharacteristics of Playback ApplicationsApplications VariationsSlide 29Type of CommitmentsSlide 31Scheduling for Guaranteed TrafficToken Bucket FilterToken Bucket OperationToken Bucket CharacteristicsToken Bucket SpecsUnified SchedulingService InterfacesSlide 41Internet Video TodayClient-Server Streaming: Adaptation Quality to LinkProblems Adapting to Network StateCongestion Manager ArchitectureTransmission APIFeedback about Network StateSlide 49DiffServBasic ArchitecturePer-hop Behaviors (PHBs)Slide 53Expedited Forwarding PHBExpedited Forwarding Traffic FlowAssured Forwarding PHBRed with In or Out (RIO)RIO Drop ProbabilitiesEdge Router Input FunctionalityTraffic ConditioningRouter Output ProcessingEdge Router PolicingComparisonNext Lecture: Router Design15-744: Computer NetworkingL-7 QoSQoS•IntServ•DiffServ•Assigned reading•[She95] Fundamental Design Issues for the Future Internet•Optional•[CSZ92] Supporting Real-Time Applications in an Integrated Services Packet Network: Architecture and Mechanisms•[CF98] Explicit Allocation of Best-Effort Packet Delivery Service2Overview•Core-stateless FQ•XCP•Why QOS?•Integrated services•Adaptive applications•Differentiated services34Core-Stateless Fair Queuing•Key problem with FQ is core routers•Must maintain state for 1000’s of flows•Must update state at Gbps line speeds•CSFQ (Core-Stateless FQ) objectives•Edge routers should do complex tasks since they have fewer flows•Core routers can do simple tasks•No per-flow state/processing this means that core routers can only decide on dropping packets not on order of processing•Can only provide max-min bandwidth fairness not delay allocation5Core-Stateless Fair Queuing•Edge routers keep state about flows and do computation when packet arrives•DPS (Dynamic Packet State)•Edge routers label packets with the result of state lookup and computation•Core routers use DPS and local measurements to control processing of packets•Flow transmission rate attached to each packet6Core Router Behavior•Keep track of fair share rate α•Increasing α does not increase load (F) by N * α•F(α) = Σi min(ri, α) what does this look like?•Periodically update α•Keep track of current arrival rate•Only update α if entire period was congested or uncongested•Drop probability for packet = max(1- α/r, 0)F vs. Alpha•What if a mistake was made?•Forced into dropping packets due to buffer capacity•When queue overflows α is decreased slightly7New αC [linked capacity]r1 r2 r3 old αalphaOverview•Core-stateless FQ•XCP•Why QOS?•Integrated services•Adaptive applications•Differentiated services89Feedback Round Trip TimeCongestion WindowCongestion HeaderFeedback Round Trip TimeCongestion Window How does XCP Work?Feedback = + 0.1 packet10Feedback = + 0.1 packet Round Trip TimeCongestion WindowFeedback = - 0.3 packet How does XCP Work?11 Congestion Window = Congestion Window + FeedbackRouters compute feedback without any per-flow state Routers compute feedback without any per-flow state How does XCP Work?XCP extends ECN and CSFQ12How Does an XCP Router Compute the Feedback?Congestion ControllerFairness ControllerGoal: Divides between flows to converge to fairnessLooks at a flow’s state in Congestion Header Algorithm:If > 0 Divide equally between flowsIf < 0 Divide between flows proportionally to their current rates MIMD AIMDGoal: Matches input traffic to link capacity & drains the queueLooks at aggregate traffic & queueAlgorithm:Aggregate traffic changes by ~ Spare Bandwidth ~ - Queue SizeSo, = davg Spare - QueueCongestion ControllerFairness Controller13 = davg Spare - Queue22402 andTheorem: System converges to optimal utilization (i.e., stable) for any link bandwidth, delay, number of sources if:(Proof based on Nyquist Criterion)Getting the devil out of the details …Congestion ControllerFairness ControllerNo Parameter Tuning No Parameter Tuning Algorithm:If > 0 Divide equally between flowsIf < 0 Divide between flows proportionally to their current ratesNeed to estimate number of flows NTinpktspktpktRTTCwndTN)/(1RTTpkt : Round Trip Time in header Cwndpkt : Congestion Window in headerT: Counting IntervalNo Per-Flow StateNo Per-Flow StateOverview•Core-stateless FQ•XCP•Why QOS?•Integrated services•Adaptive applications•Differentiated services1415Motivation•Internet currently provides one single class of “best-effort” service•No assurances about delivery•Existing applications are elastic•Tolerate delays and losses•Can adapt to congestion•Future “real-time” applications may be inelastic16Inelastic Applications•Continuous media applications•Lower and upper limit on acceptable performance.•BW below which video and audio are not intelligible•Internet telephones, teleconferencing with high delay (200 - 300ms) impair human interaction•Hard real-time applications•Require hard limits on performance•E.g. control applications17Why a New Service Model?•What is the basic objective of network design?•Maximize total bandwidth? Minimize latency?•Maximize user satisfaction – the total utility given to users•What does utility vs. bandwidth look like?•Must be non-decreasing function •Shape depends on application18Utility Curve ShapesStay to the right and youare fine for all curvesBWUElasticBWUHard real-timeBWUDelay-adaptive19Utility curve – Elastic trafficBandwidthUElasticDoes equal allocation of bandwidth maximize total utility?20Admission Control•If U(bandwidth) is concave elastic applications•Incremental utility is decreasing with increasing bandwidth•Is always advantageous to have more flows with lower bandwidth•No need of admission control; This is why the Internet works!BWUElastic21Utility Curves – Inelastic
View Full Document
Unlocking...