Colored GSPN Models
for the QoS Design
of Internet Subnets
Marco Ajmone Marsan
IEIIT-CNR and Politecnico di Torino - Italy
Eindhoven – June 27, 2003
ICATPN 2003
1
Venice 1988
My previous invited talk at
ICATPN
Goal: convince researchers
to use GSPN models
3
Today
Original goal: publish a paper
that I thought nobody would
accept …
…but the paper was accepted!
4
Today
New goal: explain why (IMO)
GSPN models (and discretestate models in general) are
becoming inadequate for
Internet modeling
5
Colored GSPN Models
for the QoS Design
of Internet Subnets?
Marco Ajmone Marsan
IEIIT-CNR and Politecnico di Torino - Italy
Eindhoven – June 27, 2003
6
Outline
 The Internet today
 Dimensioning IP networks
 GSPN and Queuing network models
 Fluid approaches
 Conclusions
7
Outline
 The Internet today
 Dimensioning IP networks
 GSPN and Queuing network models
 Fluid approaches
 Conclusions
8
Source: Internet Software Consortium (http://www.isc.org/)
9
Source: Internet Traffic Report (http://www.internettrafficreport.com/)
10
Source: Internet Traffic Report (http://www.internettrafficreport.com/)
11
Source: Internet Traffic Report (http://www.internettrafficreport.com/)
12
Source: Internet Traffic Report (http://www.internettrafficreport.com/)
13
Source: Sprint ATL (http://ipmon.sprint.com/packstat)
April 7th 2003, 2.5 Gbps link
14
Source: Sprint ATL (http://ipmon.sprint.com/packstat)
April 7th 2003, 2.5 Gbps link
15
Source: Sprint ATL (http://ipmon.sprint.com/packstat)
April 7th 2003, 2.5 Gbps link
16
Source: Sprint ATL (http://ipmon.sprint.com/packstat)
April 7th 2003, 2.5 Gbps link
17
Source: Sprint ATL (http://ipmon.sprint.com/packstat)
April 7th 2003, 2.5 Gbps link
18
Source: Sprint ATL (http://ipmon.sprint.com/packstat)
April 7th 2003, 2.5 Gbps link
19
Source: Sprint ATL (http://ipmon.sprint.com/packstat)
April 7th 2003, 2.5 Gbps link
20
Source: Sprint ATL (http://ipmon.sprint.com/packstat)
April 7th 2003, 2.5 Gbps link
21
And still growing ...
Subject: [news] Internet still growing 70 to 150 per cent per year
Date: Mon, 23 Jun 2003 09:55:45 -0400 (EDT)
From: [email protected]
...
Andrew Odlyzko, director of the Digital Technology Center at the
University of Minnesota, ... says Internet traffic is steadily growing
about 70 percent to 150 percent per year. On a conference call
yesterday to discuss the results, he said traffic growth slowed
moderately over the last couple of years, but it had mostly remained
constant for the past five years.
...
22
Outline
 The Internet today
 Dimensioning IP networks
 GSPN and Queuing network models
 Fluid approaches
 Conclusions
23
Consideration
 Over 90 % of all Internet traffic is due to
TCP connections
 TCP drives both the network behavior and
the performance perceived by end-users
 Analytical models of TCP are a must for IP
network design and planning
24
A TCP Primer in 10 Slides
• TCP is a reliable packet transfer protocol
that uses a variable window algorithm for:
– Error control
– Flow control
– Congestion control
• Two main algorithms (and a number of
gadgets):
– Slow start
– Congestion avoidance
25
Slow Start Algorithm
• Idea:
– The new segment (packet) transmission rate
adapts to the ACK reception rate
– The TCP transmitter “tests” the link capacity
• At connection setup, cwnd = 1 segment
(actually, cwnd=MSS)
• At every received ACK, cwnd = cwnd + 1
• The resulting growth is exponential
26
Slow Start Algorithm
Host B
RTT
Host A
Time
27
Slow Start: Sample Trace
28
Congestion Avoidance Algorithm
• Idea:
– Slower growth of cwnd
• At every ACK reception
– cwnd = cwnd + 1/ cwnd
– cwnd = cwnd + MSS*MSS/ cwnd (in bytes)
• The resulting growth is linear
– cwnd grows by 1 MSS per RTT
29
Congestion Avoidance
Sample Trace
30
When a Segment is Lost …
• …the transmitter rate has exceeded the
available bandwidth
• Idea:
– Reset the window size (cwnd=1)
– Quickly recover the transmission rate
• The TCP transmitter detects the loss when
the timeout expires, or 3 dupacks are
received
31
Graphically …
cwnd
20
congestion
avoidance
15
ssthresh
10
5
slow start
Time [RTT]
32
TCP Fairness
• The congestion control algorithm in TCP is
AIMD (additive increase, multiplicative
decrease)
• Fairness: N TCP connections sharing one
bottleneck link of capacity C, obtain each
C/N
33
Fairness with 2 TCP connections
• AI: linear increase
• MD: proportional decrease
R
Fair bandwidth sharing
loss: window reduced by factor 2
congestion avoidance: AI
Throughput connection 1 R
34
AQM: RED
RED
P(d)
1
Pmax
minth
maxth
Avg
35
Consideration
Accurate TCP models must consider:
 closed loop behavior
 short-lived flows
 multi-bottleneck topologies
 AQM schemes (or droptail)
 QoS approaches, two-way traffic, ...
36
Consideration
Developing accurate analytical models of the
behavior of TCP is difficult.
A number of approaches have been proposed,
some based on sophisticated modeling tools.
37
Outline
 The Internet today
 Dimensioning IP networks
 GSPN and Queuing network models
 Fluid approaches
 Conclusions
38
Literature
T. Lakshman and U. Madhow, "The performance of TCP/IP for
networks with high bandwidth-delay products and random loss,"
IEEE/ACM Transactions on Networking, vol. 5, no. 3, 1997.
M.Ajmone Marsan, E.de Souza e Silva, R.Lo Cigno, M.Meo, “An
Approximate Markovian Model for TCP over ATM”, UKPEW '97
J. Padhye, V. Firoiu, D. Towsley, J. Kurose, "A Stochastic Model of
TCP Reno Congestion Avoidance and Control“, UMASS CMPSCI
Technical Report, Feb 1999.
39
Literature
C.Casetti, M.Meo, “A New Approach to Model the Stationary
Behavior of TCP Connections”, Infocom 2000
M.Ajmone Marsan, C.Casetti, R.Gaeta, M.Meo, “An Approximate
GSPN Model for the Accurate Performance Analysis of
Correlated TCP Connections”, SPECTS 2000
M.Garetto, R.Lo Cigno, M.Meo, E.Alessio, M.Ajmone Marsan,
“Modeling Short-Lived TCP Connections with Open Multiclass
Queueing Networks”, PfHSN 2002
A.Goel, M.Mitzenmacher, "Exact Sampling of TCP Window States",
Infocom 2002
40
Literature
R.Gaeta, M.Sereno, D.Manini, "Stochastic Petri Nets models for
the performance analysis of TCP connections supporting finite data
transfer", QOS-IP 2003
R.Gaeta, M.Gribaudo, D.Manini, M.Sereno, "On the Use of Petri
Nets for the Computation of Completion Time Distributon for
Short TCP Transfers", ICATPN 2003
41
Problem statement
1
2
finite flows (mice)
F
 URLs/sec
2
3
greedy flows
IP core
 URLs/sec
finite flows
3
N
greedy flows (elephants)
F
...
4
N
4
42
Problem statement
Input variables: only primitive network parameters:
 IP network: channel data rates, node distances,
buffer sizes, AQM algorithms (or droptail), ...
 TCP: number of elephants, mice establishment rates
and file length distribution, segment size, max
window size, ...
Output variables:
 IP network: link utilizations, queuing delays, packet
loss probabilities, ...
 TCP: average elephant window size and throughput,
average mice completion times, ...
43
Our modeling approach
TCP
sub-model
1
load 1
IP network
sub-model
TCP
sub-model
N
load N
packet loss probabilities, queuing delays
 decomposition of the whole system into subsystems: sub-models
are built for groups of homogeneous TCP connections (same TCP
version, similar RTT and routing, ...) and for the IP network.
 iterative solution with FPA (Fixed Point Algorithm).
44
Our modeling approach
45
TCP sub-model
 GSPNs or . / G /  queues describe states of the TCP
protocol
 tokens or customers stand for TCP connections
 transition probabilities and service or firing times depend
on TCP rules and network feedback (packet losses, round trip
times, ...)
 in the case of mice, colors or classes are introduced to
represent the number of segments still to be transferred
46
TCP sub-model (Elephants)
47
TCP sub-model (Mice)
48
IP network sub-model
The IP network sub-model is an open queuing network,
where each queue represents an output interface of an IP
router, with its buffer of finite capacity.
Different queuing models were tested:
 M / M / 1 / B: very simple, but only suitable when dealing with
elephants and heavy load links
 M [D] / M / 1 / B: to better model the traffic burstiness of mice under
variable link utilization
 M [D] / M [D] / 1 / B: a very accurate model, capable of coping with
complex multi-bottleneck topologies
49
Numerical results: topology
Bottleneck 2
Bottleneck 1
50
Numerical results: settings
Packet size: 1000 bytes
Buffer size: 64, 128, 512 packets
Maximum TCP window size: 64 segments
TCP tic: 0.5 s
probability
0.5
Flow length distribution (when mixing
different flow lengths)
0.4
0.1
10 20
length
100 (segments)
51
Elephants crossing both bottlenecks
model
sim
Average window size
6
5
4
3
2
20
40
N1
60
80
100
120
100
200
300
400
N2
52
Elephants crossing both bottlenecks
model
sim
Packet loss
probability
0.1
0.01
400
300
20
40
60
N1
200
80
100 120
100
N2
53
Elephants with increased channel data rates
(100 Mb/s -- 1 Gb/s)
Packet loss
probability
0.1
0.01
12000
9000
0
200
6000
400
N1
600
3000
800
N2
1000 0
54
Mice (NewReno)
0.1
Bottleneck 1
analysis - B = 128
analysis - B = 64
0.01
0.001
0.75
0.8
0.85
0.9
Offered load
0.95
1
55
Mice (NewReno)
Average completion time (s)
10
5.0
10 packets
20 packets
100 packets
2.0
1.0
0.5
0.2
0.75
0.8
0.85
0.9
Offered load
0.95
1
56
Outline
 The Internet today
 Dimensioning IP networks
 GSPN and Queuing network models
 Fluid approaches
 Conclusions
57
Literature
V. Misra, W. Gong, D. Towsley, "Stochastic Differential Equation
Modeling and Analysis of TCP Windowsize Behavior“,
Performance'99
T. Bonald, "Comparison of TCP Reno and TCP Vegas via Fluid
Approximation," INRIA report no. 3563, November 1998
V. Misra, W. Gong, D. Towsley, "A Fluid-based Analysis of a
Network of AQM Routers Supporting TCP Flows with an
Application to RED“, SIGCOMM 2000
58
Literature
Y.Liu, F.Lo Presti, V.Misra, D.Towsley, Y.Gu, "Fluid Models and
Solutions for Large-Scale IP Networks", SIGMETRICS 2003
F. Baccelli, D.Hong, "Interaction of TCP flows as Billiards“, Infocom
2003
F.Baccelli, D.Hong, "Flow Level Simulation of Large IP Networks“,
Infocom 2003
59
Modeling approach
 Abandon a microscopic view of the IP network
behavior, and model packet flows and other system
parameters as fluids
 The system is described with differential
equations
 Solutions are obtained numerically
60
Modeling approach
A simple example:
 One bottleneck link
 RED buffer
 Elephants only (no slow start)
61
TCP model
dWs(t)/dt = 1/Rs(t) – Ws(t) s(t) / 2
Where:
• Ws(t)
• Rs(t)
• s(t)
is the average window
is the average round trip time
is the congestion indication rate
of TCP sources of class s at time t
62
IP network model
dQk(t)/dt = Σs Ws(t) (1-P(t)) / Rs(t) –
- C 1{Qk(t)>0}
Where:
• Qk(t)
is the length of queue k at time t
63
IP network model
Rs(t) = PDs + Qk(t)/C
Where:
• PDs is the propagation delay for source s
64
IP network model
s(t+Rs(t)) = Ws(t)/Rs(t) P(t)
Where:
• P(t) is the loss probability at time t
P(t) = RED(Q(t))
65
Fluid models – work in progress
• Slow start (mice)
• Droptail buffers
• Finite window
• Threshold
• Distributions
• Fast recovery
• Core network topologies
66
Fluid models – results
67
Fluid models – results
68
Fluid models – results
69
Fluid models – results
70
Fluid models – results
71
Fluid models – results
72
Fluid models – results
73
Fluid models – results
74
Fluid models – results
75
Fluid models – results
76
Fluid models – results
77
Fluid models – results
Baccelli and Hong obtained results for an access
network with over one million TCP flows, about ten
thousand routers, and link capacities from 6 Mb/s to
50 Gb/s.
78
Outline
 The Internet today
 Dimensioning IP networks
 GSPN and Queuing network models
 Fluid approaches
 Conclusions
79
Conclusions
 Fluid models today seem the most promising
approach to study large IP networks
 Tools for the model development and solution are
sought
 Fluid Petri Nets may be helpful for the model
construction
 Efficient numerical techniques are a challenge
80
Conclusions
 The modeling paradigms to study the Internet
behaviour are changing
 This is surely due to scaling needs, but probably
also corresponds to a new phase of maturity in Internet
modeling
 Reliable predictions of the behavior of significant
portions of the Internet are within our reach
81
A comment on model complexity
models proposed
We need to go down
models used
model
complexity
understanding of
mechanisms being modeled
early
middle
late
Adapted from [Hluchyj 2001], [Kurose 2001]
time
82
Thank You !
83