On the Characteristics ofInternet Traffic Variability:
Spikes and Elephants

Tatsuya Mori,(1) (2) Ryoichi Kawahara,(1)(3)(2)
Shozo Naito, Shigeki Goto
(1) NTT Service Integration Laboratories(2) Waseda University(3) NTT Information Sharing Platform Laboratories
January 28, 2004

Outline:• Overview• Internet traffic model• Measurement and analysis– Aggregated traffic– User traffic– Their relationship• SummaryOutline:• Overview• Internet traffic model• Measurement and analysis– Aggregated traffic– User traffic– Their relationship• Summary

Overview:• We need a practical Internet traffic model– for efficient designing and controlling ofnetworks– They should be realistic!
Æ wide-range measurement is required!

• Measurement and analysis of traffic– Traditional traffic models cannot cover thecharacteristics of today’s Internet traffic– What are they?

Outline:• Overview• Internet traffic model• Measurement and analysis– Aggregated traffic– User traffic– Their relationship• SummaryInternet traffic model:• Aggregated traffic– aggregation of user traffic• User traffic– Traffic produced by Application– Characterized by “flow”• flow = {srcIP, dstIP, srcPort, dstPort, protocol}user traffic

aggregatedtraffic

Internet traffic model (cont.):• Characteristics of aggregated traffic– Essential metrics for controlling/designingnetwork• Queuing behavior• Utilization monitoring• Characteristics of user traffic– Essential metrics for traffic engineering• Router algorithms to control per-flow bandwidth– WFQ, CSFQ, RED, etc.

• Adequate parameters are required– flow size, flow duration, etc.

Some invariant characteristics
assumed in traditional traffic models:• Aggregated traffic– Variability has “long-range dependence”(LRD)• since early 1990’s [Willinger et. al]• significant effect on network performance– Marginal dist. of variability is assumed
to be “Gaussian”• Also important metrics for networkperformance• Central limit theorem, fGn (fBm) models

Some invariant characteristics
assumed in traditional traffic models:• User traffic– Flow durations are “heavy-tailed”• well known Pareto ON/OFF model– Transmission rate of each flow is fixed in themodel• related to LRD of aggregated traffic– Aggregation of Pareto on/off sources Æ LRD• related to file size distibution– Web objects follow zipf’s law

Are they realistic in today’sInternet? :• Aggregated traffic– LRD: in most cases, YES– Gaussian: Æ ???

• User traffic

traditional traffic model
can cover these? (NO)– Heavy-tailed duration: YES– Fixed transmission rate: Æ ???

Outline:• Overview• Internet traffic model• Measurement and analysis– Aggregated traffic– User traffic– Their relationship• Summary

Measured traffic data:• Internet uplinks– NTTlab: corporation– Waseda: university• Internet backbone links– OCN-SINET: domestic– APAN: international– WIDE: international

Total:
269 one-way traces(each 300 sec long)

Measured traffic data (cont.) :• Passive measurement– captures headers of packets– can analyze aggregated/user traffic
Uplinks, backbone links

Network tapMeasurement
equipment

Outline:• Overview• Internet traffic model• Measurement and analysis– Aggregated traffic– User traffic– Their relationship• SummaryAggregated traffic :• Traffic variability– Variability of throughput– X(ti): throughput time series– Throughput time bin = 0.1 (s)Throughput variability:
X (ti) Mbps

average
NTTlab

WasedaOCN-SINET

APANWIDEtititititi

Throughput time series

much higher values than the average.

Marginal distribution of X(ti):measuredPr [X (ti) > x]

Gaussian
NTTlab

WasedaOCN-SINET

APANWIDE

x Mbpsx Mbpsx Mbpsx Mbpsx MbpsComplementary cumulative distribution
They are all skewed (not Gaussian dist.)

Gaussian(fGn model)

X (ti)ti

Pr [X (ti) = x]tihistogramskewedX (ti)Pr [X (ti) = x]measuredX (ti)Marginal distribution of X(ti)(cont.):

histogramsymmetric
X (ti)

Skewness:(X(t ) − X(t ) )3

skewness =ii

σ3σ : standad deviation
symmetric

skewness < 0skewness = 0

skewness > 0

skewness

Skewness (cont.) :Positively
skewedsymmetric
negatively
skewedMost of traces are positively skewed

Skewness and spikes:• Positively skewed distribution– Existence of larger values of throughput X(ti)Æspikes• Definition of spikes– X(ti) which exceeds mean + 2σ
• σ= standard deviation of X(ti)spike>

2σmean+Skewness and spikes (cont.):

Skewness and spikes (cont.):• Occurrence ratio of spikes vs. skewness
NTTlab

WasedaOCN-SINET

APAN

They are positively correlated!
i.e., more spikes, more skewed

Outline:• Overview• Internet traffic model• Measurement and analysis– Aggregated traffic– User traffic– Their relationship• Summary

WIDEPer-time-unit flow:• To see how each user traffic contributes
to the aggregated traffic

per-time-unit flows

t1 t2 t3

ti-1titi+1tN

Per-time-unit flow (cont.):#X(ti) = ∑ti-1

titi+1ID

size (bit)Nti

fl(ti,Nti) b(fl(Ti,Nti))

jfl(ti,j)b(fl(ti,j))2
1

fl(ti,2)fl(ti,1)b(fl(ti,2))b(fl(ti,1))

log Pr [b(fl(ti,j)) > x]

Size dist. of Per-time-unit flow:
NTTlab

WasedaOCN-SINET

APAN

WIDE

log(x)log(x)log(x)log(x)log(x)Size distributions of per-time-unit flows
are heavy-tailedi.e., quite large per-time-unit flows exist= elephant flows

Elephant flows:• Definition of an elephant flow

– A flow fl(ti,j) whose size b(fl(ti,j)) exceeds
mean + 2σ• σ = standard deviation of b(fl(ti,j))elephant
flow>

mean2σ+Elephant flows (cont.):
Occurrence/occupation ratio of elephant flows

1. # of Elephant flows is not large.
2. Elephant flows occupy large part of traffic.

[cf] Pareto ON/OFF model:[Park 96]C

fixed rate

CS…

SC
File size dist.

τP[τ > t ] ≈ t−α

P[X > x ] ≈ x −α

All b(fl(ti,j)) s are almost samei.e., No elephant flows!

Outline:• Overview• Internet traffic model• Measurement and analysis– Aggregated traffic– User traffic– Their relationship• Summary

Per-time-unit flow andspike/non-spike:Nti for each traces

The difference between spikes and non-spikes
is not remarkablei.e., number of per-time-unit flows
does NOT largely contribute to spikes

elephant flow and spike/non-spike:
spike
non-spikeOccurrence ratio of elephant flows

elephant flow and spike/non-spike(cont.):
spike
non-spike

Occupation ratio of elephant flowselephant flow and spike/non-spike(cont.):• # of elephant flows– within spikes > within non-spikes– about 1.7 – 2.9 times higher• A large part of spikes are elephant flows– about 42 – 61 %– non-spikes Æ about 22 – 35 %Thus, spikes and elephant flows arestrongly related!

Outline:• Overview• Internet traffic model• Measurement and analysis– Aggregated traffic– User traffic– Their relationship• SummarySummary:• Variability of aggregated traffic
Æ positively skewed (non-Gaussian)• User trafficÆ elephant flows exist– flow rates are NOT fixed• Elephant flows are more likely within
spikes
These findings are useful in constructing
a practical and realistic traffic model.

Appendix:
Example of aggregated traffic and flows
Total

traffic of about 5 minutes

ftp

ftp
nntp

http

http

http

http

http

Appendix:
time-scale issue (aggregated traffic)
measuredNTTlab trace: CCD plots of X(ti)bin = 0.01 sec

bin = 0.1 sec

bin = 1.0 sec

bin = 10.0 sec

Appendix:
time-scale issue (user traffic)
NTTlab trace: LLCD plots of b(fl(ti,j))bin = 0.01 sec

bin = 0.1 sec

bin = 1.0 sec

bin = 10.0 sec

GaussianAppendix:
time-scale issue (spikes and elephants)
NTTlab trace: occupation ratio of elephant flows
spike
non-spike

0.01 sec

0.1 sec

1.0 sec

10.0 sec