Transcript Performability Modeling

Performance Modeling of
Stochastic Capacity Networks
Carey Williamson
iCORE Chair
Department of Computer Science
University of Calgary
CanQueue September 15, 2006
1
Introduction



There exist many practical systems
in which the system capacity varies
unpredictably with time
These systems are complicated to
model and understand
Main focus of this talk:



Stochastic capacity networks
Lots of modeling issues and questions
A few answers (mostly from simulation)
CanQueue September 15, 2006
2
Some Examples









Queueing
systems
Safeway checkout line
Variable-rate servers
Loss
systems
Load-dependent servers
Grid computing center
Priority-based reservation networks
Wireless Local Area Networks (WLANs)
Wireless media streaming scenarios
Handoffs in mobile cellular networks
“Soft capacity” cellular networks
CanQueue September 15, 2006
3
Some Examples









Queueing
systems
Safeway checkout line
Variable-rate servers
Loss
systems
Load-dependent servers
Grid computing center
Priority-based reservation networks
Wireless Local Area Networks (WLANs)
Wireless media streaming scenarios
Handoffs in mobile cellular networks
“Soft capacity” cellular networks
CanQueue September 15, 2006
4
Grid Computing Example



Jobs of random sizes arrive at
random times to central dispatcher,
and are then sent to one of M
possible computing nodes
If a computing node fails, then all
jobs that are currently in progress
on that node are irretrievably lost
Performance impacts:


Lost work needs to be redone
Increased queue delay for waiting jobs
CanQueue September 15, 2006
5
Wireless LAN (WLAN) Example

An IEEE 802.11b WLAN (“WiFi”) supports
four different physical transmission rates:



1 Mbps, 2 Mbps, 5.5 Mbps, 11 Mbps
Stations can dynamically switch between
these rates on a per-frame basis
depending on signal strength and
perceived channel error rate
Performance impacts:

The presence of one low-rate station actually
degrades throughput for all WLAN users
[Pilosof et al. IEEE INFOCOM 2003]
CanQueue September 15, 2006
6
Cellular Network Terminology
MS
PSDN
BSC
BS
CanQueue September 15, 2006
7
Cellular Handoff Example




Mobile phones communicate via a
cellular base station (BS)
Movement of active users beyond
the coverage area of current BS
necessitates handoff to another BS
If no resources available, drop call
Possible strategies:


Guard channels (static or dynamic)
Power control, “soft handoff”, etc.
CanQueue September 15, 2006
8
Handoff Traffic in a Base Station
Channel Pool with
total C channels
New Calls
(Poisson)
(blocking
possible)
(dropping
possible)
Handoff Calls
(non-Poisson)
From neighbour cells
[Dharmaraja et al. 2003]
Call completion
(exponential
distribution)
C-g
g
Handoff Calls
To neighbour cells
Cell Site
Guard channels
(static scheme)
CanQueue September 15, 2006
9
Handoff Traffic in a Base Station
Channel Pool with
total C channels
New Calls
(Poisson)
(blocking
possible)
(dropping
possible)
Handoff Calls
(non-Poisson)
From neighbour cells
Call completion
(exponential
distribution)
C-g
(dropping
possible!)
g
Handoff Calls
To neighbour cells
Cell Site
Guard channels
(dynamic scheme)
CanQueue September 15, 2006
10
“Soft Capacity” Example





Problem originally motivated by
research project with TELUS Mobility
Q: How many users at a time can be
supported by one BS? - CLW
A: “It depends”
- MW
CDMA cellular systems are typically
interference-limited rather than
channel limited (i.e., time varying)
Intra-cell and inter-cell interference
CanQueue September 15, 2006
12
Soft Capacity: “Cell Breathing”
The effective service area expands and contracts according to the number of active users!
CanQueue September 15, 2006
13
Observation and Motivation


Networks with time-varying capacity
tend to exhibit higher call blocking
rates and higher outage (dropping)
probabilities than regular networks
Investigating performance in such
systems requires consideration of the
traffic process as well as the capacity
variation process (and interactions
between these two processes)
CanQueue September 15, 2006
14
Research Questions



What are the performance
characteristics observed in
stochastic capacity networks?
How sensitive are the results to the
parameters of the stochastic
capacity variation process?
Can one develop an “effective
capacity” model for such networks?
CanQueue September 15, 2006
15
Background: Erlang Blocking Formula

The Erlang B formula expresses the
relationship between call blocking,
offered load, and the number of
channels in a circuit-based network
CanQueue September 15, 2006
16
Circuit-Switched Network Model
Capacity
for C Calls
CanQueue September 15, 2006
17
Markov Chain Model

State
0

State
1


...
2
State
N
N
Blocking
state
•Call arrival process: Poisson
•Call holding time distribution: Exponential
CanQueue September 15, 2006
18
Erlang B Results
2%
CanQueue September 15, 2006
19
Erlang B Model Summary
Offered
Load
Blocking
Probability
p
Capacity
C
CanQueue September 15, 2006
20
Our Goal: Effective Capacity Model
Blocking
Probability
p
Offered
Load
Dropping
Policy
Equivalent
Capacity
Dropping
Probability
d
CanQueue September 15, 2006
21
Modeling Methodology Overview
Traffic
Model
Analytic
Approach
System
Model
Capacity
Model
Simulation
Approach
CanQueue September 15, 2006
22
Traffic Model

State
0

State
1


...
2
State
N
...
N
•Arrival process: Poisson, Self-similar
•Holding time: Exponential, Pareto
CanQueue September 15, 2006
23
Traffic and Capacity Example
Fixed Capacity C = 10
Fixed Capacity C = 5
Stochastic Capacity
Fixed Capacity C = 4
Traffic
Occupancy
Process
(Counting
Process)
Traffic Arrival and Departure Process (Point Process)
CanQueue September 15, 2006
t
24
Stochastic Capacity Example
CanQueue September 15, 2006
25
Stochastic Capacity Terminology
“High variance”
“Low variance”
CanQueue September 15, 2006
26
Stochastic Capacity Terminology
“High frequency”
“Low frequency”
CanQueue September 15, 2006
27
Stochastic Capacity Terminology
“Correlated”
“Uncorrelated”
CanQueue September 15, 2006
28

Stochastic Capacity Model
High
value
{cH , H }
{ci }
H
Medium
value
...

L
Low
value
{cM , M }
{ i }
•Value process {Ci}
{cL , L }
•Timing process {ti}
CanQueue September 15, 2006
29
Effective Capacity
High
value

H
Medium
value
...

L
+
State
0

State
1

...
2

State
N
...
N
Low
value
•Effects of Capacity Value process
•Effects of Capacity Timing process
•Effect of Correlations
•Interactions between Traffic and Capacity
CanQueue September 15, 2006
30
Full Model Structure
Traffic Process
Dropping
Transitions
Capacity
Variation
Blocking
States
CanQueue September 15, 2006
31
Parameters in Simulations
Parameter
Network
Traffic
Network
Capacity
(calls)
Level
Call arrival rate (per sec)
1.0
Mean holding time (sec)
30
Mean
30, 40, 50
Standard Deviation
2, 5, 10
Mean Time Between Capacity Changes
(sec)
Hurst Parameter H (for LRD model)
CanQueue September 15, 2006
10, 15, 30, 60, 120
0.5, 0.7, 0.9
34
Results and Observations (Preview)

Factors that matter:







Mean of capacity value process
Variance of capacity value process
Correlation of capacity value process
Frequency of capacity timing process
Choice of call dropping policy used
Relative time scales of joint processes
Factors that don’t matter:

Distribution for capacity timing process
CanQueue September 15, 2006
35
Effect of Capacity Value Mean
Small capacity C = 30 (100% load)
Medium capacity C = 40 (75% load)
Large capacity C = 50 (60% load)
CanQueue September 15, 2006
36
Effect of Capacity Value Variance
High variance (75% load)
Medium variance (75% load)
Low variance (75% load)
CanQueue September 15, 2006
37
Effect of Capacity Correlation
Uncorrelated
Correlated
CanQueue September 15, 2006
38
Effect of Capacity Timing Process
CanQueue September 15, 2006
39
Effect of Call Dropping Policy (1 of 2)
CanQueue September 15, 2006
40
Effect of Call Dropping Policy (2 of 2)
CanQueue September 15, 2006
41
Effect of Relative Time Scale
R = E[call arrivals/capacity change]
CanQueue September 15, 2006
42
Results and Observations (Recap)

Factors that matter:







Mean of capacity value process
Variance of capacity value process
Correlation of capacity value process
Frequency of capacity timing process
Choice of call dropping policy used
Relative time scales of joint processes
Factors that don’t matter:

Distribution for capacity timing process
CanQueue September 15, 2006
43
Summary and Conclusion





Studied call-level performance in a
network with stochastic capacity variation
Shows influences from the properties of
the stochastic capacity variation process
Shows that mean and variance of capacity
process have the largest impact, as do
the correlation structure and timing
Shows impact of interactions between
traffic and capacity processes
One step closer to our goal, but the hard
part is still ahead!
CanQueue September 15, 2006
44
Our Goal: Effective Capacity Model
Blocking
Probability
p
Offered
Load
Dropping
Policy
Equivalent
Capacity
Dropping
Probability
d
CanQueue September 15, 2006
45
References




H. Sun and C. Williamson, “Simulation Evaluation
of Call Dropping Policies for Stochastic Capacity
Networks”, Proceedings of SCS SPECTS 2005,
Philadelphia, PA, pp. 327-336, July 2005.
H. Sun and C. Williamson, “On Effective Capacity
in Time-Varying Wireless Networks”, Proceedings
of SCS SPECTS 2006, Calgary, AB, July 2006.
H. Sun, Q. Wu, and C. Williamson, “Impact of
Stochastic Traffic Characteristics on Effective
Capacity in CDMA Networks”, to appear,
Proceedings of P2MNet, Tampa, FL, Nov. 2006.
H. Sun and C. Williamson, “On the Role of Call
Dropping Controls in Stochastic Capacity
Networks”, submitted for publication, 2006.
CanQueue September 15, 2006
46
Related Work




S. Dharmaraja, K. Trivedi, and D. Logothetis,
“Performance Modelling of Wireless Networks with
Generally Distributed Hand-off Interarrival Times”,
Computer Communications, Vol. 26, No. 15, pp.
1747-1755, 2003.
V. Gupta, M. Harchol-Balter, A. Scheller-Wolf, and U.
Yechiali, “Fundamental Characteristics of Queues
with Fluctuating Load”, Proceedings of ACM
SIGMETRICS 2006, St. Malo, France, June 2006.
G. Haring, R. Marie, R. Puigjaner, and K. Trivedi,
“Loss Formulae and Optimization for Cellular
Networks”, IEEE Transactions on Vehicular
Technology, Vol. 50, No. 3, pp. 664-673, 2001.
B. Haverkort, R. Marie, R. Gerardo, and K. Trivedi,
Performability Modeling: Techniques and Tools,
2001.
CanQueue September 15, 2006
47
Thanks!


Questions?
Credits:





Hongxia Sun
Jingxiang Luo
Qian Wu
S. Dharmaraja
For more information:


Email [email protected]
http://www.cpsc.ucalgary.ca/~carey
CanQueue September 15, 2006
48