Traffic Behavior and Queuing in a QoS Environment
Session 1813
Traffic Behavior and
Queuing in a QoS
Environment
NetworkingTutorials
[Link]
DepartmentofElectricalEngineering
M.I.T.
Copyright 2002 OPNET Technologies, Inc.
Traffic Behavior and Queuing in a QoS Environment
Objectives
Providesomebasicunderstandingofqueuingphenomena
Explaintheavailablesolutionapproachesandassociated
tradeoffs
Giveguidelinesonhowtomatchapplicationsandsolutions
Copyright 2002 OPNET Technologies, Inc.
Traffic Behavior and Queuing in a QoS Environment
Outline
Basicconcepts
Sourcemodels
Servicemodels(demo)
Singlequeuesystems
Priority/sharedservicesystems
Networksofqueues
Hybridsimulation(demo)
Copyright 2002 OPNET Technologies, Inc.
Traffic Behavior and Queuing in a QoS Environment
Outline
Basicconcepts
Performancemeasures
Solutionmethodologies
Queuingsystemconcepts
Stabilityandsteadystate
Causesofdelayandbottlenecks
Sourcemodels
Servicemodels(demo)
Singlequeuesystems
Priority/sharedservicesystems
Networksofqueues
Hybridsimulation(demo)
Copyright 2002 OPNET Technologies, Inc.
Traffic Behavior and Queuing in a QoS Environment
Performance Measures
Delay
Delayvariation(jitter)
Packetloss
Efficientsharingofbandwidth
Relativeimportancedependsontraffictype(audio/video,
filetransfer,interactive)
Challenge:Provideadequateperformancefor(possibly)
heterogeneoustraffic
Copyright 2002 OPNET Technologies, Inc.
Traffic Behavior and Queuing in a QoS Environment
Solution Methodologies
Analyticalresults(formulas)
Pros:Quickanswers,insight
Cons:Ofteninaccurateorinapplicable
Explicitsimulation
Pros:Accurateandrealisticmodels,broadapplicability
Cons:Canbeslow
Hybridsimulation
Intermediatesolutionapproach
Combinesadvantagesanddisadvantagesofanalysisandsimulation
Copyright 2002 OPNET Technologies, Inc.
Traffic Behavior and Queuing in a QoS Environment
Examples of Applications
Analytical Modeling
Discrete-Event Simulation
Hybrid DES
with Explicit
DES only with
and
Explicit Traffic
Background
Traffic
M/G/./. &
G/G/./.
FIFO
Analysis
M/G/./. &
G/G/./.
Priority
Analysis
Decomposition
with Kleinrock
Independence
Assumption
Yes
N/A
N/A
Yes
Yes
Yes
N/A
N/A
Yes
Yes
Yes
N/A
N/A
Yes
Yes
Using QoS to differentiate service levels for
the same type of traffic
N/A
Yes (loss of
accuracy)
N/A
Yes
Yes
Using QoS to support different requirements
for different application types given as a
detailed study of setting Cisco Router
queueing parameters
N/A
Highly
approximate
N/A
Yes
Yes
General network model extending the
previous QoS queueing model
N/A
Hop-by-hop
Analysis (loss
of accuacy)
Reduction of the general model to a
representative end-to-end path
N/A
Hop-by-hop
Analysis (loss
of accuacy)
Analysis Scenarios
Single Link with FIFO Service
Best Effort Service for Standard Data Traffic
Best Effort Service for LRD/Self-Similar
Behavior Traffic
"Chancing It" with Best Effort Service for
Voice, Video and Data
Single Link with QoS-Based Queueing
Network of Queues
Copyright 2002 OPNET Technologies, Inc.
Yes (some loss of
Yes (Run time a
accuracy - e.g., traffic function of network
shaping)
complexity)
Yes [Fast with
minimal loss of
accuracy]
Yes (Run time a
function of network
complexity)
Yes [Fast with
minimal loss of
accuracy]
N/A
Traffic Behavior and Queuing in a QoS Environment
Queuing System Concepts:
Arrival Rate, Occupancy, Time in the
System
Queuingsystem
Datanetworkwherepacketsarrive,waitinvariousqueues,receive
serviceatvariouspoints,andexitaftersometime
Arrivalrate
Longtermnumberofarrivalsperunittime
Occupancy
Numberofpacketsinthesystem(averagedoveralongtime)
Timeinthesystem(delay)
Timefrompacketentrytoexit(averagedovermanypackets)
Copyright 2002 OPNET Technologies, Inc.
Traffic Behavior and Queuing in a QoS Environment
Stability and Steady-State
Asinglequeuesystemisstableif
packet arrival rate < system transmission capacity
Forasinglequeue,theratio
packet arrival rate / system transmission capacity
iscalledtheutilizationfactor
Describestheloadingofaqueue
Inanunstablesystempacketsaccumulateinvariousqueues
and/orgetdropped
Forunstablesystemswithlargebufferssomepacketdelays
becomeverylarge
Flow/admissioncontrolmaybeusedtolimitthepacketarrivalrate
Prioritizationofflowskeepsdelaysboundedfortheimportanttraffic
Stablesystemswithtimestationaryarrivaltrafficapproacha
steadystate
Copyright 2002 OPNET Technologies, Inc.
Traffic Behavior and Queuing in a QoS Environment
Littles Law
Foragivenarrivalrate,thetimeinthesystemisproportional
topacketoccupancy
N=T
where
N:average#ofpacketsinthesystem
:packetarrivalrate(packetsperunittime)
T:averagedelay(timeinthesystem)perpacket
Examples:
Onrainydays,streetsandhighwaysaremorecrowded
Fastfoodrestaurantsneedasmallerdiningroomthanregular
restaurantswiththesamecustomerarrivalrate
Largebufferingtogetherwithlargearrivalratecauselargedelays
Copyright 2002 OPNET Technologies, Inc.
10
Traffic Behavior and Queuing in a QoS Environment
Explanation of Littles Law
Amusementparkanalogy:peoplearrive,spendtimeat
varioussites,andleave
Theypay$1perunittimeinthepark
Therateatwhichtheparkearnsis$Nperunittime(N:
average#ofpeopleinthepark)
Therateatwhichpeoplepayis$Tperunittime(:traffic
arrivalrate,T:timeperperson)
Overalonghorizon:
Rateofparkearnings=Rateofpeoplespayment
or
N=T
Copyright 2002 OPNET Technologies, Inc.
11
Traffic Behavior and Queuing in a QoS Environment
Delay is Caused by Packet Interference
Ifarrivalsareregularorsufficientlyspacedapart,noqueuing
delayoccurs
T
2
4
3
1
ime Times
Arrival
Departure
Times
RegularTraffic
T
2
4
3
1
ime Times
Arrival
Departure
Times
Irregularbut
SpacedApartTraffic
Copyright 2002 OPNET Technologies, Inc.
12
Traffic Behavior and Queuing in a QoS Environment
Burstiness Causes Interference
Notethatthedeparturesarelessbursty
Queuing
Delays
BurstyTraffic
4
3
2
1
Time
Copyright 2002 OPNET Technologies, Inc.
13
Traffic Behavior and Queuing in a QoS Environment
Burstiness Example
Different Burstiness Levels at Same Packet Rate
Source: Fei Xue and S. J. Ben Yoo, UCDavis, On the Generation and Shaping Self-similar Traffic in Optical Packet-switched Networks, OPNETWORK 2002
Copyright 2002 OPNET Technologies, Inc.
14
Traffic Behavior and Queuing in a QoS Environment
Packet Length Variation Causes
Interference
Time
QueuingDelays
Regulararrivals,irregularpacketlengths
Copyright 2002 OPNET Technologies, Inc.
15
Traffic Behavior and Queuing in a QoS Environment
High Utilization Exacerbates Interference
Time
QueuingDelays
Astheworkarrivalrate:
(packetarrivalrate*packetlength)
increases,theopportunityforinterferenceincreases
Copyright 2002 OPNET Technologies, Inc.
16
Traffic Behavior and Queuing in a QoS Environment
Bottlenecks
Typesofbottlenecks
Ataccesspoints(flowcontrol,prioritization,QoSenforcementneeded)
Atpointswithinthenetworkcore
Isolated(canbeanalyzedinisolation)
Interrelated(networkorchainanalysisneeded)
Bottlenecksresultfromoverloadscausedby:
Highloadsessions,or
Convergenceofsufficientnumberofmoderateloadsessionsatthe
samequeue
Copyright 2002 OPNET Technologies, Inc.
17
Traffic Behavior and Queuing in a QoS Environment
Bottlenecks Cause Shaping
Time
Thedeparturetrafficfromabottleneckismoreregularthanthe
arrivaltraffic
Theinterdeparturetimebetweentwopacketsisatleastas
largeasthetransmissiontimeofthe2ndpacket
Copyright 2002 OPNET Technologies, Inc.
18
Traffic Behavior and Queuing in a QoS Environment
Bottlenecks Cause Shaping
Incomingtraffic
Outgoingtraffic
Exponential
interarrivals
gap
Bottleneck
90%utilization
Copyright 2002 OPNET Technologies, Inc.
19
Traffic Behavior and Queuing in a QoS Environment
Incomingtraffic
Outgoingtraffic
Small
Medium
Bottleneck
90%utilization
Large
Copyright 2002 OPNET Technologies, Inc.
20
Traffic Behavior and Queuing in a QoS Environment
Packet Trains
Interdeparturetimesforsmallpackets
Copyright 2002 OPNET Technologies, Inc.
21
Traffic Behavior and Queuing in a QoS Environment
Variable packet sizes
Histogramofinterdeparturetimesforsmallpackets
#ofpackets
Variablepacket
Peakssmeared
sizes
Constantpacketsizes
sec
Copyright 2002 OPNET Technologies, Inc.
22
Traffic Behavior and Queuing in a QoS Environment
Outline
Basicconcepts
Sourcemodels
Poissontraffic
Batcharrivals
Exampleapplicationsvoice,video,filetransfer
Servicemodels(demo)
Singlequeuesystems
Priority/sharedservicesystems
Networksofqueues
Hybridsimulation(demo)
Copyright 2002 OPNET Technologies, Inc.
23
Traffic Behavior and Queuing in a QoS Environment
Poisson Process with Rate
Interarrivaltimesareindependentand
exponentiallydistributed
Modelswelltheaccumulatedtrafficofmany
independentsources
Theaverageinterarrivaltimeis1/
(secs/packet),soisthearrivalrate
(packets/sec)
Time
Interarrival
Times
Copyright 2002 OPNET Technologies, Inc.
24
Traffic Behavior and Queuing in a QoS Environment
Batch Arrivals
Somesourcestransmitinpacketbursts
Maybebettermodeledbyabatcharrivalprocess(e.g.,bursts
ofpacketsarrivingaccordingtoaPoissonprocess)
Thecaseforabatchmodelisweakeratqueuesafterthefirst,
becauseofshaping
Time
Interarrival
Copyright 2002 OPNET Technologies, Inc.
Times
25
Traffic Behavior and Queuing in a QoS Environment
Markov Modulated Rate Process (MMRP)
State 0
State 1
OFF
ON
Stay in each state an exponentially
distributed time,
Transmit according to different model
(e.g., Poisson, deterministic, etc) at each state
Extension:Modelswithmorethantwostates
Copyright 2002 OPNET Technologies, Inc.
26
Traffic Behavior and Queuing in a QoS Environment
Source Types
Voicesources
Videosources
Filetransfers
Webtraffic
Interactivetraffic
DifferentapplicationtypeshavedifferentQoSrequirements,
e.g.,delay,jitter,loss,throughput,etc.
Copyright 2002 OPNET Technologies, Inc.
27
Traffic Behavior and Queuing in a QoS Environment
Source Type Properties
Characteristics
Voice
Video
Interactive
FTP
telnet
web
QoS
Requirements
Model
*Alternatingtalk
spurtsandsilence
intervals.
*Talkspurtsproduce
constantpacketrate
traffic
Delay<~150ms
Jitter<~30ms
Packetloss<~1%
*Twostate(onoff)Markov
ModulatedRateProcess(MMRP)
*Exponentiallydistributedtimeat
eachstate
*Highlyburstytraffic
(whenencoded)
*Longrange
dependencies
Delay<~400ms
Jitter<~30ms
Kstate(onoff)MarkovModulated
RateProcess(MMRP)
*Poissontype
*Sometimesbatch
arrivals,orbursty,
orsometimesonoff
Zeroornearsero
packetloss
Delaymaybe
important
Copyright 2002 OPNET Technologies, Inc.
Packetloss<~1%
Poisson,Poissonwithbatcharrivals,
TwostateMMRP
28
Traffic Behavior and Queuing in a QoS Environment
Typical Voice Source Behavior
Copyright 2002 OPNET Technologies, Inc.
29
Traffic Behavior and Queuing in a QoS Environment
MPEG1 Video Source Model
TheMPEG1MMRPmodelcanbeextremelybursty,andhas
longrangedependencybehaviorduetothedeterministic
framesequence
Diagram Source: Mark W. Garrett and Walter Willinger, Analysis, Modeling, and Generation of Self-Similar VBR Video Traffic, BELLCORE, 1994
Copyright 2002 OPNET Technologies, Inc.
30
Traffic Behavior and Queuing in a QoS Environment
Outline
Basicconcepts
Sourcemodels
Servicemodels
[Link]
FIFO,priority,andsharedservers
Demo
Singlequeuesystems
Priority/sharedservicesystems
Networksofqueues
Hybridsimulation(demo)
Copyright 2002 OPNET Technologies, Inc.
31
Traffic Behavior and Queuing in a QoS Environment
Device Queuing Mechanisms
CommonqueueexamplesforIProuters
FIFO:FirstInFirstOut
PQ:PriorityQueuing
WFQ:WeightedFairQueuing
Combinationsoftheabove
Servicetypesfromaqueuingtheorystandpoint
Singleserver(onequeueonetransmissionline)
Multipleserver(onequeueseveraltransmissionlines)
Priorityserver(severalqueueswithhardprioritiesonetransmission
line)
Sharedserver(severalqueueswithsoftprioritiesonetransmission
line)
Copyright 2002 OPNET Technologies, Inc.
32
Traffic Behavior and Queuing in a QoS Environment
Single Server FIFO
SingletransmissionlineservingpacketsonaFIFO(FirstIn
FirstOut)basis
Eachpacketmustwaitforallpacketsfoundinthesystemto
completetransmission,beforestartingtransmission
DepartureTime=ArrivalTime+WorkloadFoundintheSystem+
Transmissiontime
Packetsarrivingtoafullbufferaredropped
Arrivals
Transmission
Line
Copyright 2002 OPNET Technologies, Inc.
33
Traffic Behavior and Queuing in a QoS Environment
FIFO Queue
PacketsareplacedonoutboundlinktoegressdeviceinFIFOorder
Device(router,switch)multiplexesdifferentflowsarrivingonvariousingress
portsontoanoutputbufferformingaFIFOqueue
Copyright 2002 OPNET Technologies, Inc.
34
Traffic Behavior and Queuing in a QoS Environment
Multiple Servers
Multiplepacketsaretransmittedsimultaneouslyonmultiple
lines/servers
Headofthelineservice:packetswaitinaFIFOqueue,and
whenaserverbecomesfree,thefirstpacketgoesintoservice
Arrivals
Transmission
Lines
Copyright 2002 OPNET Technologies, Inc.
35
Traffic Behavior and Queuing in a QoS Environment
Priority Servers
Packetsformpriorityclasses(eachmayhaveseveralflows)
ThereisaseparateFIFOqueueforeachpriorityclass
Packetsoflowerprioritystarttransmissiononlyifnohigher
prioritypacketiswaiting
Prioritytypes:
Nonpreemptive(highprioritypacketmustwaitforalowerpriority
packetfoundundertransmissionuponarrival)
Preemptive(highprioritypacketdoesnothavetowait)
Transmission
Class
Class
Class123Arrivals
Arrivals
Arrivals
Interm.
High
Low
Line
Priority
Priority
Priority
Copyright 2002 OPNET Technologies, Inc.
36
Traffic Behavior and Queuing in a QoS Environment
Priority Queuing
Packetsareclassifiedintoseparatequeues
E.g.,basedonsource/destinationIPaddress,source/destinationTCPport,etc.
Allpacketsinahigherpriorityqueueareservedbeforealowerpriority
queueisserved
Typicallyinrouters,ifahigherprioritypacketarriveswhilealowerpriority
packetisbeingtransmitted,itwaitsuntilthelowerprioritypacketcompletes
Copyright 2002 OPNET Technologies, Inc.
37
Traffic Behavior and Queuing in a QoS Environment
Shared Servers
Againwehavemultipleclasses/queues,buttheyareserved
withasoftpriorityscheme
Roundrobin
Weightedfairqueuing
Transmission
Class
Class
Class123Arrivals
Arrivals
Arrivals
Weight
Weight
Line
Weight
10
31
Copyright 2002 OPNET Technologies, Inc.
38
Traffic Behavior and Queuing in a QoS Environment
Round-Robin/Cyclic Service
Roundrobinserveseachqueueinsequence
Aqueuethatisemptyisskipped
Eachqueuewhenservedmayhavelimitedservice(atmostkpackets
transmittedwithk=1ork>1)
Roundrobinisfairforallqueues(aslongassomequeuesdo
nothavelongerpacketsthanothers)
Roundrobincannotbeusedtoenforcebandwidthallocation
amongthequeues.
Copyright 2002 OPNET Technologies, Inc.
39
Traffic Behavior and Queuing in a QoS Environment
Fair Queuing
Thisschedulingmethodisinspiredbythemostfairofmethods:
Transmitonebitfromeachqueueincyclicorder(bitbybitroundrobin)
Skipqueuesthatareempty
Toapproximatethebitbybitprocessingbehavior,foreachpacket
Wecalculateuponarrivalitsfinishtimeunderbitbybitroundrobin
assumingallotherqueuesarecontinuouslybusy,andwetransmitbyFIFO
withineachqueue
Transmitnextthepacketwiththeminimumfinishtime
Importantproperties:
Priorityisgiventoshortpackets
Equalbandwidthisallocatedtoallqueuesthatarecontinuouslybusy
Finish
Arrival
i-1
iDeparture
-1
Time
times
times
of Packet i
Copyright 2002 OPNET Technologies, Inc.
40
Traffic Behavior and Queuing in a QoS Environment
Weighted Fair Queuing
Fairqueuingcannotbeusedtoimplementbandwidthallocationandsoft
priorities
Weightedfairqueuingisavariationthatcorrectsthisdeficiency
Letwkbetheweightofthekthqueue
Thinkofroundrobinwithqueuektransmittingwkbitsuponitsturn
Ifallqueueshavealwayssomethingtosend,thekthqueuereceivesbandwidth
equaltoafractionwk/iwiofthetotalbandwidth
Fairqueuingcorrespondstowk=1
Priorityqueuingcorrespondstotheweightsbeingveryhighaswemoveto
higherpriorities
Again,todealwiththesegmentationproblem,weapproximateasfollows:
Foreachpacket:
Wecalculateitsfinishtime(undertheweightedbitbybitroundrobin
scheme)
Wenexttransmitthepacketwiththeminimumfinishtime
Copyright 2002 OPNET Technologies, Inc.
41
Traffic Behavior and Queuing in a QoS Environment
Weighted Fair Queuing Illustration
Weights:
Queue 1 = 3
Queue 2 = 1
Queue 3 = 1
Copyright 2002 OPNET Technologies, Inc.
42
Traffic Behavior and Queuing in a QoS Environment
Combination of Several Queuing
Schemes
Examplevoice(PQ),guaranteedb/w(WFQ),BestEffort
(CiscosLLQimplementation)
Copyright 2002 OPNET Technologies, Inc.
43
Traffic Behavior and Queuing in a QoS Environment
Demo: FIFO
FIFO
Bottleneck
90%utilization
Copyright 2002 OPNET Technologies, Inc.
44
Traffic Behavior and Queuing in a QoS Environment
Demo: FIFO Queuing Delay
Applications have different
requirements
Video
delay, jitter
FTP
packet loss
Control beyond best effort
needed
Priority Queuing (PQ)
Weighted Fair Queuing (WFQ)
Copyright 2002 OPNET Technologies, Inc.
45
Traffic Behavior and Queuing in a QoS Environment
Demo: Priority Queuing (PQ)
PQ
Bottleneck
90%utilization
Copyright 2002 OPNET Technologies, Inc.
46
Traffic Behavior and Queuing in a QoS Environment
Demo: PQ Queuing Delays
PQFTP
FIFO
PQVideo
Copyright 2002 OPNET Technologies, Inc.
47
Traffic Behavior and Queuing in a QoS Environment
Demo: Weighted Fair Queuing (WFQ)
WFQ
Bottleneck
90%utilization
Copyright 2002 OPNET Technologies, Inc.
48
Traffic Behavior and Queuing in a QoS Environment
Demo: WFQ Queuing Delays
PQFTP
WFQFTP
FIFO
WFQ/PQVideo
Copyright 2002 OPNET Technologies, Inc.
49
Traffic Behavior and Queuing in a QoS Environment
Queuing: Take Away Points
Choiceofqueuingmechanismcanhaveaprofoundeffecton
performance
Toachievedesiredservicedifferentiation,appropriatequeuing
mechanismscanbeused
Complexqueuingmechanismsmayrequiresimulation
techniquestoanalyzebehavior
Improperconfiguration(e.g.,queuingmechanismselectionor
weights)mayimpactperformanceoflowprioritytraffic
Copyright 2002 OPNET Technologies, Inc.
50
Traffic Behavior and Queuing in a QoS Environment
Outline
Basicconcepts
Sourcemodels
Servicemodels(demo)
Singlequeuesystems
M/M/1M/M/m/k
M/G/1G/G/1
Demo:[Link]
Priority/sharedservicesystems
Networksofqueues
Hybridsimulation(demo)
Copyright 2002 OPNET Technologies, Inc.
51
Traffic Behavior and Queuing in a QoS Environment
M/M/1 System
Nomenclature:MstandsforMemoryless(apropertyofthe
exponentialdistribution)
M/M/1standsforPoissonarrivalprocess(whichismemoryless)
M/M/1standsforexponentiallydistributedtransmissiontimes
Assumptions:
ArrivalprocessisPoissonwithratepackets/sec
Packettransmissiontimesareexponentiallydistributedwithmean1/
Oneserver
Independentinterarrivaltimesandpackettransmissiontimes
Transmissiontimeisproportionaltopacketlength
Note1/issecs/packetsoispackets/sec(packet
transmissionrateofthequeue)
Utilizationfactor:=/stablesystemif1)
Copyright 2002 OPNET Technologies, Inc.
52
Traffic Behavior and Queuing in a QoS Environment
Delay Calculation
Let
Q=Averagetimespentwaitinginqueue
T=Averagepacketdelay(transmissionplusqueuing)
NotethatT=1/+Q
AlsobyLittleslaw
N=TandNq=Q
where
Nq=Averagenumberwaitinginqueue
Thesequantitiescanbecalculatedwithformulasderivedby
Markovchainanalysis(seereferences)
Copyright 2002 OPNET Technologies, Inc.
53
Traffic Behavior and Queuing in a QoS Environment
M/M/1 Results
Theanalysisgivesthesteadystateprobabilitiesof
numberofpacketsinqueueortransmission
P{npackets}=n(1)where=/
Fromthiswecangettheaverages:
N=/(1)
T=N/=/(1)=1/()
1
0
1/m
m
N
T
Copyright 2002 OPNET Technologies, Inc.
54
Traffic Behavior and Queuing in a QoS Environment
Example: How Delay Scales with
Bandwidth
Occupancyanddelayformulas
N=/(1)
T=1/()
Assume:
Trafficarrivalrateisdoubled
Systemtransmissioncapacityisdoubled
Then:
=/
Queuesizesstayatthesamelevel(staysthesame)
Packetdelayiscutinhalf(andaredoubled
Aconclusion:Inhighspeednetworks
propagationdelayincreasesinimportancerelativetodelay
buffersizeandpacketlossmaystillbeaproblem
Copyright 2002 OPNET Technologies, Inc.
55
Traffic Behavior and Queuing in a QoS Environment
M/M/m, M/M/ System
SameasM/M/1,butithasm(or)servers
InM/M/m,thepacketattheheadofthequeuemoves
toservicewhenaserverbecomesfree
Qualitativeresult
Delayincreasestoas=/mapproaches1
Thereareanalyticalformulasfortheoccupancy
probabilitiesandaveragedelayofthesesystems
Copyright 2002 OPNET Technologies, Inc.
56
Traffic Behavior and Queuing in a QoS Environment
Finite Buffer Systems: M/M/m/k
TheM/M/m/ksystem
SameasM/M/m,butthereisbufferspaceforatmostk
[Link]
Formulasforaveragedelay,steadystateoccupancy
probabilities,andlossprobability
TheM/M/m/msystemisusedwidelytosize
telephoneorcircuitswitchingsystems
Copyright 2002 OPNET Technologies, Inc.
57
Traffic Behavior and Queuing in a QoS Environment
Characteristics of M/M/. Systems
Advantage:Simpleanalyticalformulas
Disadvantages:
ThePoissonassumptionmaybeviolated
Theexponentialtransmissiontimedistributionisan
approximationatbest
Interarrivalandpackettransmissiontimesmaybe
dependent(particularlyinthenetworkcore)
Headofthelineassumptionprecludesheterogeneousinput
trafficwithpriorities(hardorsoft)
Copyright 2002 OPNET Technologies, Inc.
58
Traffic Behavior and Queuing in a QoS Environment
M/G/1 System
SameasM/M/1butthepackettransmissiontime
distributionisgeneral,withgivenmean1/and
variance2
Utilizationfactor=/
PollaczekKinchineformulafor
Averagetimeinqueue=(2+1/2)/2(1)
Averagedelay=1/+(2+1/2)/2(1)
Theformulasforthesteadystateoccupancy
probabilitiesaremorecomplicated
Insight:As2increases,delayincreases
Copyright 2002 OPNET Technologies, Inc.
59
Traffic Behavior and Queuing in a QoS Environment
G/G/1 System
SameasM/G/1butnowthepacketinterarrivaltime
distributionisalsogeneral,withmeanand
variance2
WestillassumeFIFOandindependentinterarrival
timesandpackettransmissiontimes
Heavytrafficapproximation:
Averagetimeinqueue~(2+2)/2(1)
Becomesincreasinglyaccurateas
Copyright 2002 OPNET Technologies, Inc.
60
Traffic Behavior and Queuing in a QoS Environment
Demo: M/G/1
Packetinterarrivaltimes
exponential(0.02)sec
Packetsize
1250bytes
(10000bits)
Capacity
1Mbps
Packetsizedistribution:
exponential
constant
lognormal
Whatistheaveragedelayandqueuesize?
Copyright 2002 OPNET Technologies, Inc.
61
Traffic Behavior and Queuing in a QoS Environment
Demo: M/G/1 Analytical Results
PacketSize
Distribution
DelayT(sec)
QueueSize(packets)
Exponential
mean=10000
variance =1.0*108
0.02
1.0
Constant
mean=10000
variance=N/A
0.015
0.75
Lognormal
mean=10000
variance=9.0*108
0.06
3.0
Copyright 2002 OPNET Technologies, Inc.
62
Traffic Behavior and Queuing in a QoS Environment
Demo: M/G/1 Simulation Results
AverageDelay(sec)
Copyright 2002 OPNET Technologies, Inc.
AverageQueueSize(packets)
63
Traffic Behavior and Queuing in a QoS Environment
Demo: M/G/1 Limitations
Applicationtrafficmixnotmemoryless
Video
constantpacketinterarrivals
Http
burstytraffic
Delay
PKformula
Simulation
Copyright 2002 OPNET Technologies, Inc.
64
Traffic Behavior and Queuing in a QoS Environment
Outline
Basicconcepts
Sourcemodels
Servicemodels(demo)
Singlequeuesystems
Priority/sharedservicesystems
[Link]
Cyclic,WFQ,PQsystems
Demo:Simulationresults
Networksofqueues
Hybridsimulation(demo)
Copyright 2002 OPNET Technologies, Inc.
65
Traffic Behavior and Queuing in a QoS Environment
Non-preemptive Priority Systems
Wedistinguishbetweendifferentclassesoftraffic(flows)
Nonpreemptivepriority:packetundertransmissionisnot
preemptedbyapacketofhigherpriority
PKformulafordelaygeneralizes
Transmission
Class
Class
Class123Arrivals
Arrivals
Arrivals
Interm.
High
Low
Line
Priority
Priority
Priority
Copyright 2002 OPNET Technologies, Inc.
66
Traffic Behavior and Queuing in a QoS Environment
Cyclic Service Systems
Multipleflows,eachwithitsownqueue
Fairsystem:Eachflowgetsaccesstothetransmissionlinein
turn
Severalpossibleassumptionsabouthowmanypacketseach
flowcantransmitwhenitgetsaccess
FormulasfordelayunderM/G/1typeassumptionsare
available
Transmission
Class
3
2
1
Arrivals
Line
Copyright 2002 OPNET Technologies, Inc.
67
Traffic Behavior and Queuing in a QoS Environment
Weighted Fair Queuing
Acombinationofpriorityandcyclicservice
Noexactanalyticalformulasareavailable
Copyright 2002 OPNET Technologies, Inc.
68
Traffic Behavior and Queuing in a QoS Environment
Outline
Basicconcepts
Sourcemodels
Servicemodels(demo)
Singlequeuesystems
Priority/sharedservicesystems
Networksofqueues
ViolationofM/M/.assumptions
Effectsondelaysandtrafficshaping
Analyticalapproximations
Hybridsimulation(demo)
Copyright 2002 OPNET Technologies, Inc.
69
Traffic Behavior and Queuing in a QoS Environment
Two Queues in Series
Firstqueueshapesthetrafficintosecondqueue
Arrivaltimesandpacketlengthsarecorrelated
M/M/1andM/G/1formulasyieldsignificanterrorforsecond
queue
FirstQueue
SecondQueue
Time
Time
Copyright 2002 OPNET Technologies, Inc.
70
Traffic Behavior and Queuing in a QoS Environment
Two bottlenecks in series
Exponential
interarrivals
Bottleneck
Delay
Copyright 2002 OPNET Technologies, Inc.
Bottleneck
Noqueuing
delay
71
Traffic Behavior and Queuing in a QoS Environment
Approximations
Kleinrockindependenceapproximation
Performadelaycalculationineachqueueindependentlyofother
queues
Addtheresults(includingpropagationdelay)
Note:Intheprecedingexample,theKleinrockindependence
approximationoverestimatesthequeuingdelayby100%
Tendstobemoreaccurateinnetworkswithlotsoftraffic
mixing,e.g.,nodesservingmanyrelativelysmallflowsfrom
severaldifferentlocations
Copyright 2002 OPNET Technologies, Inc.
72
Traffic Behavior and Queuing in a QoS Environment
Outline
Basicconcepts
Sourcemodels
Servicemodels(demo)
Singlequeuesystems
Priority/sharedservicesystems
Networksofqueues
Hybridsimulation
[Link]
ConceptualFramework
Demo:PQandWFQwithaggregatedtraffic
Copyright 2002 OPNET Technologies, Inc.
73
Traffic Behavior and Queuing in a QoS Environment
Basic Concepts of Hybrid Simulation
Aimstocombinethebestofanalyticalresultsandsimulation
Achievesignificantgaininsimulationspeedwithlittlelossof
accuracy
Dividesthetrafficthroughanodeintoexplicitand
background
Explicittrafficissimulatedaccurately
Backgroundtrafficisaggregated
Theinteractionofexplicitandbackgroundismodeledeither
analyticallyorthroughafastsimulation(oracombination)
Explicit
Background
Copyright 2002 OPNET Technologies, Inc.
74
Traffic Behavior and Queuing in a QoS Environment
Explicit Traffic
Modeledindetail,includingtheeffectsofvariousprotocols
Eachpacketsarrivalanddeparturetimesarerecorded(together
withotherdataofinterest,e.g.,loss,etc.)alongeachlinkthatit
traverses
Departuretimesatalinkarethearrivaltimesatthenextlink(plus
propagationdelay)
Objective:Ateachlink,giventhearrivaltimes(andthepacket
lengths),determinethedeparturetimes
.. .
Time
a
d
Delay
Departure
Arrival
times
times
at aatlink
the link
1
4
2
3
Copyright 2002 OPNET Technologies, Inc.
75
Traffic Behavior and Queuing in a QoS Environment
Aggregated Traffic
Simplifiedmodeling
Wedontkeeptrackofindividualpackets,onlyworkloadcounts
(numberofpacketsorbytes)
Wegenerateworkloadcounts
byprobabilistic/analyticalmodeling,or
bysimplifiedsimulation
Aggregated(orbackground)trafficislocal(perlink)
Shapingeffectsarecomplextoincorporate
Somedependencesbetweenexplicitandbackgroundtraffic
alongachainoflinksarecomplicatedandareignored
Copyright 2002 OPNET Technologies, Inc.
76
Traffic Behavior and Queuing in a QoS Environment
Hybrid Simulation (FIFO Links):
Conceptual Framework
Giventhearrivaltimeakofthekthexplicitpacket
Generatetheworkloadwkfoundinqueuebythekthpacket
Fromakandwkgeneratethedeparturetimeofthekthpacketas
DepartureTimedk=ak+wk+sk
th
whereskisthetransmissiontimeofthek
packet
ARRIVAL TIMES
Explicit
aK
wK
Explicit
a K+1
w K+1
Time
Background
Explicit
Background
Explicit
d K = aK + wK + sK
Copyright 2002 OPNET Technologies, Inc.
DEPARTURE TIMES
77
Traffic Behavior and Queuing in a QoS Environment
Simulating the Background Traffic Effects
Useatrafficdescriptorforthebackgroundtraffic(e.g.,carried
byspecialpackets)
Trafficdescriptorincludes:
Trafficvolumeinformation(e.g.,packets/sec,bits/sec)
Probabilitydistributionofinterarrivaltimes
Probabilitydistributionofpacketlengths
Timeintervalofvalidityofthedescriptor
Generatewkusingoneofseveralideasandcombinations
thereof
Successivesampling(forFIFOcase)
Steadystatequeuelengthdistribution(ifwecangetit)
Simplifiedsimulation(microsimappliestocomplexqueuing
disciplines)
Copyright 2002 OPNET Technologies, Inc.
78
Traffic Behavior and Queuing in a QoS Environment
Hybrid Simulation (FIFO Case)
CriticalQuestion:Givenarrivaltimesakandak+1,workloadwk,andbackground
trafficdescriptor,howdowefindwk+1?
Arrival times/Workload found
a1
w1
a2
w2
d1 = a1 + w1 + s1
a3
.
.
.
w
3
d2 = a2 + w2 + s2
.. .
Time
d3 = a3 + w3 + s3
Departure times
Note:wk+1consistsofwkandtwomoreterms:
Backgroundarrivalsinintervalak+1ak
(Minus)transmittedworkloadinintervalak+1ak
Mustcalculate/simulatethetwoterms
Thefirsttermissimulatedbasedonthetrafficdescriptorofthebackgroundtraffic
Thesecondtermiseasilycalculatedifthequeueiscontinuouslybusyinak+1ak
Copyright 2002 OPNET Technologies, Inc.
79
Traffic Behavior and Queuing in a QoS Environment
Short Interval Case (Easy Case)
Shortintervalak+1ak(i.e.,ak+1<dk)
Queueisbusycontinuouslyinak+1ak
Sowk+1isquicklysimulated
Samplethebackgroundtrafficarrivaldistributiontosimulatethenew
workloadarrivalsinak+1ak
Dotheaccounting(addtowkandsubtractthetransmittedworkloadin
ak+1ak)
Short Interval
wk+1 = wk + (New bkg arrivals) - (Old bkg transmissions)
a k w k a k+1 w k+1
.. .
dk
Copyright 2002 OPNET Technologies, Inc.
Time
d k+1
80
Traffic Behavior and Queuing in a QoS Environment
Long Interval Case
Longintervalak+1ak(i.e.,ak+1>dk)
Queuemaybeidleduringportionsoftheintervala k+1ak
Needtogenerate/simulate
Thenewarrivalsinak+1ak
Thelengthsofthebusyperiodsandtheidleperiods
Canbedonebysamplingthebackgroundarrivaldistributionineachbusy
period
Time
Long
a
w
d
Idle
Busy
Periods
Periods
Interval
k Otheralternativesarepossible
k+1
kk+1
.. .
Copyright 2002 OPNET Technologies, Inc.
81
Traffic Behavior and Queuing in a QoS Environment
Steady-State Queue Length Distribution
Iftheintervalbetweentwosuccessiveexplicitpacketsisvery
long,wecanassumethatthequeuefoundbythesecond
packetisinsteadystate
So,wecanobtainwk+1bysamplingthesteadystate
distribution
Appliestocaseswherethesteadystatedistributioncanbe
foundorcanbereasonablyapproximated
M/M/1andotherM/M/.Queues
SomeM/G/.systems
Copyright 2002 OPNET Technologies, Inc.
82
Traffic Behavior and Queuing in a QoS Environment
Micro Simulation: Conceptual Framework
Handlescomplexqueuingsystems
Micropacketsaregeneratedtorepresenttrafficloadwithinthecontext
ofthequeueonly(i.e.,theyarenottransmittedtoanyexternallinks)
Forlongintervals,whereconvergencetoasteadystateislikely
Trytodetectconvergenceduringthemicrosim
Estimatesteadystatequeuelengthdistribution
Samplethesteadystatedistributiontoestimatewk+1
Microsimspeedsupthesimulationwithoutsacrificing
accuracy
Microsimprovidesageneralframework
Appliestononstationarybackgroundtraffic
AppliestononFIFOservicemodels(withpropermodification)
Copyright 2002 OPNET Technologies, Inc.
83
Traffic Behavior and Queuing in a QoS Environment
Examples of Applications
Analytical Modeling
Discrete-Event Simulation
Hybrid DES
with Explicit
DES only with
and
Explicit Traffic
Background
Traffic
M/G/./. &
G/G/./.
FIFO
Analysis
M/G/./. &
G/G/./.
Priority
Analysis
Decomposition
with Kleinrock
Independence
Assumption
Yes
N/A
N/A
Yes
Yes
Yes
N/A
N/A
Yes
Yes
Yes
N/A
N/A
Yes
Yes
Using QoS to differentiate service levels for
the same type of traffic
N/A
Yes (loss of
accuracy)
N/A
Yes
Yes
Using QoS to support different requirements
for different application types given as a
detailed study of setting Cisco Router
queueing parameters
N/A
Highly
approximate
N/A
Yes
Yes
General network model extending the
previous QoS queueing model
N/A
Hop-by-hop
Analysis (loss
of accuacy)
Reduction of the general model to a
representative end-to-end path
N/A
Hop-by-hop
Analysis (loss
of accuacy)
Analysis Scenarios
Single Link with FIFO Service
Best Effort Service for Standard Data Traffic
Best Effort Service for LRD/Self-Similar
Behavior Traffic
"Chancing It" with Best Effort Service for
Voice, Video and Data
Single Link with QoS-Based Queueing
Network of Queues
Copyright 2002 OPNET Technologies, Inc.
Yes (some loss of
Yes (Run time a
accuracy - e.g., traffic function of network
shaping)
complexity)
Yes [Fast with
minimal loss of
accuracy]
Yes (Run time a
function of network
complexity)
Yes [Fast with
minimal loss of
accuracy]
N/A
84
Traffic Behavior and Queuing in a QoS Environment
Demo End-to-end Delay: Baseline Network
Trafficmodeledas
1)Explicittraffic
2)Backgroundtraffic
Copyright 2002 OPNET Technologies, Inc.
85
Traffic Behavior and Queuing in a QoS Environment
Target Flow: ETE delay as a function of ToS
Targetflow:SeattleHoustonmodeledusingexplicittraffic
VaryingitsTypeofService(ToS)
BestEffort(0)
StreamingMultimedia(4)
Copyright 2002 OPNET Technologies, Inc.
86
Traffic Behavior and Queuing in a QoS Environment
Explicit Simulation Results for Target Flow
Totaltrafficvolume
500Mbps
Timemodeled
35minutes
Simulationduration
31hours
Copyright 2002 OPNET Technologies, Inc.
87
Traffic Behavior and Queuing in a QoS Environment
Hybrid Simulation Results for Target Flow
Totaltrafficvolume
500Mbps
Timemodeled
35minutes
Simulationduration
14minutes
Copyright 2002 OPNET Technologies, Inc.
88
Traffic Behavior and Queuing in a QoS Environment
Comparison: Hybrid vs Explicit Simulation
Copyright 2002 OPNET Technologies, Inc.
89
Traffic Behavior and Queuing in a QoS Environment
References
Networking
BertsekasandGallager,DataNetworks,PrenticeHall,1992
DeviceQueuingImplementations
Vegesna,IPQualityofService,[Link],2001
[Link]
ProbabilityandQueuingModels
BertsekasandTsitsiklis,IntroductiontoProbability,AthenaScientific,2002,
[Link]
Cohen,TheSingleServerQueue,NorthHolland,1992
Takagi,QueuingAnalysis:AFoundationofPerformanceEvaluation.(3
Volumes),NorthHolland,1991
GrossandHarris,FundamentalsofQueuingTheory,Wiley,1985
Cooper,IntroductiontoQueuingTheory,CEEPress,1981
OPNETHybridSimulationandMicroSimulation
SeeCaseStudiespapersin
[Link]
Copyright 2002 OPNET Technologies, Inc.
90