Transcript slides

Using Partial Differential Equations
to Modek TCP Mice and Elephantsin
large IP Networks
M. Ajmone Marsan, M. Garetto, P. Giaccone,
E. Leonardi, E.Schiattarella, A. Tarello
Politecnico di Torino - Italy
Hong-Kong – March 7-11 , 2004
TANGO
1
Outline
 Dimensioning IP networks
 Queuing network models
 Fluid approaches
 Conclusions
2
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
3
Consideration
Accurate TCP models must consider:
 closed loop behavior
 short-lived flows
 multi-bottleneck topologies
 AQM schemes (or droptail)
 QoS approaches, two-way traffic, ...
4
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
5
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, ...
6
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
7
Modeling approach
A simple example:
 One bottleneck link
 RED buffer
 Elephants only (no slow start)
8
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
9
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
10
IP network model
Rs(t) = PDs + Qk(t)/C
Where:
• PDs is the propagation delay for source s
11
Problems
Difficult to deal with mice since the start time of
each mouse detemines the window dynamics
over time.
One equation shoud be written for each mouse
Difficult to consider droptail buffers due to the
intrinsic burstiness of the loss process
experienced by sources
12
Problems
Difficult to deal with mice since the start time
of each mouse detemines the window
dynamics over time.
One equation shoud be written for each mouse
13
Our Approach
Consider a population of TCP sources: P(w,t) is the number of
TCP flows that at time t have window not greater than w.
.
P(w,t)
w
window
Partial differential equations are obtained
14
Basic source model
Where:
15
Mice Source Equations
16
Fluid models – extensions
• Slow start (mice)
• Finite window
• Threshold
• Fast recovery
• Droptail buffers
•Core network topologies
17
Fluid models – results
18
Fluid models – model results
19
Fluid models – NS results
20
Fluid models – model results
21
Fluid models – NS results
22
Fluid models – results
23
Fluid models – results
24
Fluid models – results
25
Fluid models – results
26
Fluid models – results
27
Fluid models – results
We obtained results for the GARR network with over
one million TCP flows, and link capacities up to 2.5
Gb/s.
28
Conclusions
 Fluid models today seem the most promising
approach to study large IP networks
 Tools for the model development and solution are
sought
Efficient numerical techniques are a challenge
29
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
30
Thank You !
31
Outline
 The Internet today
 Dimensioning IP networks
 Queuing network models
 Fluid approaches
 Conclusions
32
Source: Internet Software Consortium (http://www.isc.org/)
33
Source: Internet Traffic Report (http://www.internettrafficreport.com/)
34
Source: Internet Traffic Report (http://www.internettrafficreport.com/)
35
Source: Sprint ATL (http://ipmon.sprint.com/packstat)
April 7th 2003, 2.5 Gbps link
36
Source: Sprint ATL (http://ipmon.sprint.com/packstat)
April 7th 2003, 2.5 Gbps link
37
Source: Sprint ATL (http://ipmon.sprint.com/packstat)
April 7th 2003, 2.5 Gbps link
38
Source: Sprint ATL (http://ipmon.sprint.com/packstat)
April 7th 2003, 2.5 Gbps link
39
Source: Sprint ATL (http://ipmon.sprint.com/packstat)
April 7th 2003, 2.5 Gbps link
40
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.
...
41
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
42
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
43
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.
44
Literature
C.Casetti, M.Meo, “A New Approach to Model the Stationary
Behavior of TCP Connections”, Infocom 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
45
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.
46
Fluid models – results
47