CS 268: Packet SchedulingPacket SchedulingWhy Packet Scheduling?Fair QueueingFair Rate ComputationFair Rate Computation in GPSGeneralized Processor SharingSlide 8Properties of GPSPacket vs. Fluid SystemPacket Approximation of Fluid SystemSystem Virtual TimeService Allocation in GPSVirtual Time Implementation of Weighted Fair QueueingSlide 15System Virtual Time in GPSVirtual Start and Finish TimesGoals in Designing Packet Fair Queueing AlgorithmsWorst-case Fair Index (WFI)WFI exampleHierarchical Resource SharingHierarchical-GPS ExamplePacket Approximation of H-GPSProblems with Idea 1Hierarchical-WFQ ExampleHierarchical-WF2Q ExampleWF2Q+Example HierarchyUncorrelated Cross TrafficCorrelated Cross TrafficWhy Service Curve?What is a Service Model?Arrival and Departure ProcessTraffic Envelope (Arrival Curve)Service CurveBig PictureDelay and Buffer BoundsService Curve-based Earliest Deadline (SCED)Linear Service Curves: ExampleNon-Linear Service Curves: ExampleSummaryCS 268: Packet SchedulingIon StoicaMarch 29, [email protected] 2Packet SchedulingDecide when and what packet to send on output link-Usually implemented at output interface12Schedulerflow 1flow 2flow nClassifierBuffer [email protected] 3Why Packet Scheduling?Can provide per flow or per aggregate protectionCan provide absolute and relative differentiation in terms [email protected] 4Fair QueueingIn a fluid flow system it reduces to bit-by-bit round robin among flows-Each flow receives min(ri, f) , where•ri – flow arrival rate•f – link fair rate (see next slide)Weighted Fair Queueing (WFQ) – associate a weight with each flow [Demers, Keshav & Shenker ’89]-In a fluid flow system it reduces to bit-by-bit round robinWFQ in a fluid flow system Generalized Processor Sharing (GPS) [Parekh & Gallager ’92][email protected] 5Fair Rate ComputationIf link congested, compute f such that Cfrii),min(862442f = 4: min(8, 4) = 4 min(6, 4) = 4 min(2, 4) = 2 [email protected] 6Fair Rate Computation in GPSAssociate a weight wi with each flow iIf link congested, compute f such that Cwfriii),min(862442f = 2: min(8, 2*3) = 6 min(6, 2*1) = 2 min(2, 2*1) = 2 10(w1 = 3)(w2 = 1)(w3 = 1)[email protected] 7Generalized Processor Sharing0 152104 6 85 1 1 11 1Red session has packets backlogged between time 0 and 10Other sessions have packets continuously [email protected] 8Generalized Processor SharingA work conserving GPS is defined aswhere-wi – weight of flow i-Wi(t1, t2) – total service received by flow i during [t1, t2)-W(t1, t2) – total service allocated to al flows during [t1, t2)-B(t) – number of backlogged flows)(),(),()(tBiwdtttWwdtttWitBjji9Properties of GPSEnd-to-end delay bounds for guaranteed service [Parekh and Gallager ‘93]Fair allocation of bandwidth for best effort service [Demers et al. ‘89, Parekh and Gallager ‘92][email protected] 10Packet vs. Fluid SystemGPS is defined in an idealized fluid flow model-Multiple queues can be serviced simultaneouslyReal system are packet systems-One queue is served at any given time-Packet transmission cannot be preemptedGoal-Define packet algorithms approximating the fluid system-Maintain most of the important [email protected] 11Standard techniques of approximating fluid GPS-Select packet that finishes first in GPS assuming that there are no future arrivalsImportant properties of GPS-Finishing order of packets currently in system independent of future arrivalsImplementation based on virtual time-Assign virtual finish time to each packet upon arrival-Packets served in increasing order of virtual timesPacket Approximation of Fluid [email protected] 12System Virtual TimeVirtual time (VGPS) – service that backlogged flow with weight = 1 would receive in GPS )(),(),()(tBiwdtttWwdtttWtBjjiitWwtVtBjjGPS )(1)()(tBitWwwtWtBjjii)(1),(21)(21tBidttWwwttWttttBjjii[email protected] 13Service Allocation in GPSThe service received by flow i during an interval [t1,t2), while it is backlogged is)(),(2121tBidttVwttWtttGPSii)())()((),(1221tBitVtVwttWGPSGPSii[email protected] 14Virtual Time Implementation of Weighted Fair QueueingwjkjkjkjLSF 0)0( VGPS))(,max(1 kjkjkjaVFSif session j backloggedin generalajk – arrival time of packet k of flow jSjk – virtual starting time of packet k of flow jFjk – virtual finishing time of packet k of flow jLjk – length of packet k of flow j1[email protected] 15Virtual Time Implementation of Weighted Fair QueueingNeed only to keep per flow not per packet stateSystem virtual time is used to reset a flow’s virtual start time when a flow becomes backlogged again after being [email protected] 16System Virtual Time in GPS 0 4 128 161/21/81/81/81/8)(tVGPS2*CC2*[email protected] 17Virtual Start and Finish TimesUtilize the time the packets would start Sik and finish Fik in a fluid system0 4 128 16kiFkiSikikikiwLSF )([email protected] 18Goals in Designing Packet Fair Queueing AlgorithmsImprove worst-case fairness (see next):-Use Smallest Eligible virtual Finish time First (SEFF) policy-Examples: WF2Q, WF2Q+Reduce complexity-Use simpler virtual time functions-Examples: SCFQ, SFQ, DRR, FBFQ, leap-forward Virtual Clock, WF2Q+Improve resource allocation flexibility-Service [email protected] 19Worst-case Fair Index (WFI)Maximum discrepancy between the service received by a flow in the fluid flow system and in the packet systemIn WFQ, WFI = O(n), where n is total number of backlogged flowsIn WF2Q, WFI = [email protected] 20WFI exampleFluid-Flow (GPS)WFQ (smallest finish time first): WFI = 2.5WF2Q (earliest finish time first); WFI = [email protected] 21Hierarchical Resource SharingResource contention/sharing at different levelsResource management policies should be set at different levels, by different entities -Resource owner-Service providers-Organizations-ApplicationsLinkProvider 1seminar videoStatStanford.BerkeleyProvider 2WEB155 Mbps50 Mbps50 Mbps10 Mbps20 Mbps100 Mbps55 MbpsCampusseminar
View Full Document
Unlocking...