Transcript Scheduling calls with known holding times

Scheduling calls
with known holding times
Reinette Grobler*
University of Pretoria
[email protected]
*Supported
Prof. M. Veeraraghavan
Polytechnic University
[email protected]
by Polytechnic University
Acknowledgement: David Rouse, Lucent Technologies
1
Outline
•
•
•
•
•
Problem statement
Motivation for solving this problem
Proposed algorithms: F and timeslots
Simulation comparison
Conclusions and future work
2
Problem statement and
motivation
• Problem statement
– Define call scheduling algorithms for calls with
known holding times
• Motivation
– There are applications that could generate calls
with known holding times
– Improves network utilization and call blocking
probabilities by allowing for call queueing
3
Applications vs. data transfers
• “Communications applications” consist of data transfers
• Data transfers can be classified as shown below
Consuming end
Stored
Live
Sending end
Live
Stored
Interactive/
Live streaming
Recording
Stored streaming
File transfers
• Define a call as a “data transfer” rather than an “application session”
4
Data transfers (“calls”)
with known holding times
• For calls to have known holding times, two characteristics must be
met:
– Sending end of the data transfer is stored
– Network uses preventive congestion control
• Examples:
– Transferring a file on a circuit or CBR ATM connection
• Can compute holding time using knowledge of file size, data rate of circuit,
and propagation delay
• Demonstrates need for the “preventive congestion control clause”
– File transfer on a TCP/IP network does not have a known holding time
– Video-on-demand transfer on an VBR ATM connection
5
Loss, delay, utilization
• Learning from the “packet world”
– Packet switches use buffers to achieve high line
utilization and tradeoff packet delays with
packet loss
– Apply this concept to calls
• appears to be only possible if calls have known
holding times
6
Call blocking vs. call queueing
•
Telephone networks, ATM networks and MPLS networks only allow call
blocking
–
•
If only call blocking is allowed (i.e., no delayed starts), then need to overprovision to keep call
loss low
Why 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 buffers
SETUP
SETUP
Host
Switch
link 1
The call waits (queues) until resources become
available on link 1, reserves and holds bandwidth for
this call until the call is setup all through
referred to as kTwait scheme
Switch
link 2
Host
While call is being queued
for link 2 resources, link 1
resources are idle
7
Knowledge of holding times
• Allows switches to immediately determine an agreed upon
delayed start time for a call c
• Allow other calls sharing segments of the end-to-end path
of c to use the network resources before c starts
• Results in high utilization and lower call loss
8
Call scheduling schemes
• Each switch maintains a time variant available capacity
function ai(t) for each outgoing interface I reflecting the
scheduled start times of all admitted connections
9
Call 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 message
– Intermediate switches search for largest time period inside the received
period during which it can accommodate the connection
• timeslots 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 message
– An 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 message
10
Example: F and timeslots schemes
SETUP
Host
Switch1
•
Switch1
SETUP
Switch2
SETUP
Host
Switch2
Connection request for a call starting immediately with holding time of 1 hour
– F scheme (large time period: F=4): Swith1 - (10pm,2am), Switch2 – (10pm,12am)
– timeslots scheme (number of time ranges = 3): Switch1 - ([3pm,5pm],[8pm,9pm],[10pm,],
Swicth3 - ([4pm,5pm], [10pm,12am], [1am,2am])
11
Simulation
Source
src1
src2
src3
Switch1
Switch2
Switch3
dest1
dest2
Switch4
Dest
dest3
Parameter (scheme)
Values
F (Large period)
20, 50 and 100 seconds
n ( number of timeslots) 2, 3 and 4
•kTwait has no parameters.
12
Results: Blocked calls
13
Results: Start time delay
• Indicates time from
connection request
to start of data
transmission of
study traffic
• High F values
increase delay
• Large queueing
delays cause kTwait
to provide later
start times
• timeslots scheme
performs best
14
Results: Utilization
• timeslots scheme
allows for close to
optimal utilization
• kTwait unable to
handle load of more
than 70%
• Increasing F
decreases utilization
15
Conclusions and future work
• Use known holding times to schedule
connections to improve network resource
utilization and call queueing delays
• Required extensions:
– Switch programming time
– Propagation delay
– Time synchronization
16