Scheduling calls with known holding times
Scheduling calls with known holding times. Reinette Grobler * Prof. M. Veeraraghavan University of Pretoria Polytechnic University email@example.com firstname.lastname@example.org. * Supported by Polytechnic University. Acknowledgement: David Rouse, Lucent Technologies. - PowerPoint PPT Presentation
Scheduling calls with known holding times Reinette Grobler* Prof. M. VeeraraghavanUniversity of Pretoria Polytechnic Universityrgrobler@cs.up.ac.za email@example.com*Supported by Polytechnic UniversityAcknowledgement: David Rouse, Lucent TechnologiesOutlineProblem statementMotivation for solving this problemProposed algorithms: F and timeslotsSimulation comparisonConclusions and future workProblem statement and motivationProblem statementDefine call scheduling algorithms for calls with known holding timesMotivationThere are applications that could generate calls with known holding timesImproves network utilization and call blocking probabilities by allowing for call queueingApplications vs. data transfersCommunications applications consist of data transfersData transfers can be classified as shown belowDefine a call as a data transfer rather than an application sessionInteractive/Live streamingRecordingStored streamingFile transfersData transfers (calls) with known holding timesFor calls to have known holding times, two characteristics must be met:Sending end of the data transfer is storedNetwork uses preventive congestion controlExamples:Transferring a file on a circuit or CBR ATM connectionCan compute holding time using knowledge of file size, data rate of circuit, and propagation delayDemonstrates need for the preventive congestion control clauseFile transfer on a TCP/IP network does not have a known holding timeVideo-on-demand transfer on an VBR ATM connectionLoss, delay, utilizationLearning from the packet worldPacket switches use buffers to achieve high line utilization and tradeoff packet delays with packet lossApply this concept to calls appears to be only possible if calls have known holding timesCall blocking vs. call queueingTelephone networks, ATM networks and MPLS networks only allow call blockingIf only call blocking is allowed (i.e., no delayed starts), then need to overprovision to keep call loss lowWhy not allow for delayed starts?If call holding times are unknown and calls are queued at each switch in sequence, then utilization could really suffer and call blocking could even increase with finite buffersThe call waits (queues) until resources becomeavailable on link 1, reserves and holds bandwidth forthis call until the call is setup all throughWhile call is being queued for link 2 resources, link 1resources are idlereferred to as kTwait schemeKnowledge of holding timesAllows switches to immediately determine an agreed upon delayed start time for a call cAllow other calls sharing segments of the end-to-end path of c to use the network resources before c startsResults in high utilization and lower call lossCall scheduling schemesEach switch maintains a time variant available capacity function ai(t) for each outgoing interface I reflecting the scheduled start times of all admitted connectionsCall scheduling schemes (cont.)F scheme:Ingress switch selects an earliest possible start time (epst) and reserves resources for a time period F (from epst), where F is much larger than the holding time, and sends this time period in the SETUP messageIntermediate switches search for largest time period inside the received period during which it can accommodate the connectiontimeslots scheme:The ingress switch selects a set of time ranges during which it has the resources available for the new call, and sends these in SETUP messageAn intermediate switch attempts to admit the call during each of the time ranges or any part of each range greater than or equal to the holding time, the new time ranges are passed in a SETUP messageExample: F and timeslots schemesF scheme (large time period: F=4): Swith1 - (10pm,2am), Switch2 (10pm,12am)Connection request for a call starting immediately with holding time of 1 hourtimeslots scheme (number of time ranges = 3): Switch1 - ([3pm,5pm],[8pm,9pm],[10pm,], Swicth3 - ([4pm,5pm], [10pm,12am], [1am,2am])SimulationSwitch1Switch2Switch4SourceDestSwitch3dest3dest2dest1src1src2src3kTwait has no parameters.Parameter (scheme)ValuesF (Large period)20, 50 and 100 secondsn ( number of timeslots)2, 3 and 4Results: Blocked callsResults: Start time delayIndicates time from connection request to start of data transmission of study trafficHigh F values increase delayLarge queueing delays cause kTwait to provide later start timestimeslots scheme performs bestResults: Utilizationtimeslots scheme allows for close to optimal utilizationkTwait unable to handle load of more than 70%Increasing F decreases utilizationConclusions and future workUse known holding times to schedule connections to improve network resource utilization and call queueing delaysRequired extensions:Switch programming timePropagation delayTime synchronizationOne application (for example http) can consist of multiple data transfers, even from different classes.