《计算机组成原理试题及答案计算机组》由会员分享，可在线阅读，更多相关《计算机组成原理试题及答案计算机组（16页珍藏版）》请在金锄头文库上搜索。
1、Scheduling Algorithms to Minimize Session DelaysNandita DukkipatiDavid GutierrezJune 05, 2002IntroductionProvision of QoS in the InternetQoS measure for short flows: Response time seen by the userImportant to minimize average session delays for short flowsScheduling algorithms provide QoS at a singl
2、e nodeCoordinate QoS at each network element to provide end-to-end QoSJune 05, 2002ProblemOptimal schedule of sessions in the single node case and the network case for a known traffic arrival patternWeight (or ) allocations for sessions in Generalized Processor Sharing schedulers to minimize delaysC
3、omparison of average session delays in Generalized Processor Sharing and Shortest Job First schedulersJune 05, 2002Arrival process: deterministic and knownFluid arrivals and fluid serviceSession delay, di = Di - AiAverage session delay, Optimal scheduling policyBackgroundJune 05, 2002Minimizing Dela
4、ys in Single NodeN SessionsAi(t) : Arrival rate of session i at time tSi(t) : Size of session iOptimal schedule ?June 05, 2002Shortest Job FirstOptimal policy when all jobs are present in the server at once in the systemNot optimal in our system of interestJune 05, 2002Shortest Time to Finish First
5、(STFF)2 sessionsNon unique optimal schedule STFF-2:1.TAi: Maximum time to arrival of last bit2.Compute the minimum time to finish, Tfi = max(TAi, Si / C)3.Determine the priorities of the sessionsJune 05, 2002Optimality of STFF-2Lemma 1: The STFF-2 discipline minimizes the session delay of 2 sessions
6、 at a single node serverSketch of Proof : June 05, 2002STFF - NDefinition: Pair wise STFFLemma 2: Every optimal discipline must be pair wise STFFSTFF-N:1.Initialization 1.Np : Set of all sessions whose priorities have been decided = 2. j = 1 to | N |3.Compute the minimum time to finish, TFi, for unp
7、rioritized sessions4.Assign priority j to the session with min(TFi)5.Update Np and remaining capacity C(t) = C(t) (capacity taken by sessions belonging to Np) June 05, 2002STFF - NNot optimalExample:June 05, 2002Minimizing Delays in GPSProblem: Find weights i in GPS to minimize session delays i1, i2
8、, ., iN: Increasing order of session sizes Find i such that:June 05, 2002Minimizing Delays in GPSGPS can realize any strict priority based schedule June 05, 20021. For every session identify the bottleneck router along its path2. For a session i:Ni : Set of sessions bottlenecked at router iCi : Capa
9、city of router3.4. Minimum average delay Scheduling Sessions - Network CaseEquivalent to Job Shop Scheduling problem: NP-hardA lower bound on average session delay:June 05, 2002STFF - Network 1. j = 1 to |N|2. 3. Assign priority j to the session with min(Fi)Heuristic Schedule - Network CaseMotivatio
10、n:Littles lawBlocking FactorJune 05, 2002SummarySTFF - 2: Optimal scheduling discipline for 2 sessions at a single nodeSTFF - N: A heuristic for N sessions at a single nodeGeneralized Process Sharing can realize any strict priority based scheduleWeight allocation in GPS schedulers to minimize delaysLower bound on delay of sessions in the network caseSTFF - Network: A heuristic for the network caseQuestionsJune 05, 2002
