Multifractal Based Network Traffic Modeling MULTIFRACTAL BASED NETWORK TRAFFIC MODELING MURALI KRISHNA. P SPANN LAB, oerartment of Electrical Engineering Indian Institute 0 Technology -Bombay Powai, Mumbai 400076 INOIA [email protected] VIKRAM M. GAORE SPANN LAB, Oepartment of Electrical Engineering Indian Institute of Technology -Bombay Powai, Mumbai 400076 INOIA [email protected] UOAY B. OESAI SPANN LAB, Oepartment of Electrical Engineering Indian Institute of Technology -Bombay Powai, Mumbai 400076 INOIA [email protected] SPRINGER SCIENCE+BUSINESS MEDIA, LLC oe Library Congress Cataloging-in-Publication Data Murali Krishna. P, 1974- Multifraetal based network traffic modeling / Murali Krishna. P, Vikram M. Gadre, Uday B. Desai p.em. Includes bibliographical referenees and index. ISBN 978-1-4613-5107-8 ISBN 978-1-4615-0499-3 (eBook) DOI 10.1007/978-1-4615-0499-3 I. Teleeommunieation--Traffie--Mathematieal models. 2. Multifraetals. I. Gadre, Vikram M., 1966-11. Desai, Uday B. III. Title. TK5105.895.M872003 621.382--de22 2003054666 Copyright © 2003 by Springer Science+Business Media New York Originally published by Kluwer Academic Publishers in 2003 Softcover reprint of the hardcover 1s t edition 2003 All rights reserved. No part of this work may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, microfilming, recording, or otherwise, without written permission from the Publisher, with the exception of any material supplied specifically for the purpose of being entered and executed on a computer system, for exclusive use by the purchaser of the work. Permission for books published in Europe: [email protected] Permissions for books published in the United States 01' Ameriea: [email protected] Printed on acid-free paper. Contents ListofSymbols xi ListofAcronyms xiii ListofFigures xv ListofTables XIX Acknowledgments xxi Preface xxiii 1. INTRODUCTION 1 1 ComplexityofBroadbandNetworkTraffic 1 1.1 GeographicalComplexity 2 1.2 BehaviorGeneratedComplexity 3 1.3 TemporalComplexity 3 2 TeletrafficModeling: HistoricalPerspective 4 3 Motivationforthe Problem 7 4 Contributionsofthe Monograph 9 5 Organizationofthe Monograph 12 2. MATHEMATICALPRELIMINARIES 15 1 RandomProcesses 16 1.1 Stationary andNonStationaryRandomProcess 16 2 Bernoulli(Counting)Process 18 3 PoissonProcess 20 3.1 ApplicationstoQueuingTheory 22 4 MarkovProcess 24 5 IndependentIncrementProcesses 25 6 SelfSimilarProcesses 28 VI MULTIFRACTALBASEDNETWORKTRAFFICMODELING 6.1 StructureofVariance 28 6.2 StructureofCovariance 29 6.3 LongRangeDependenceProperty 30 7 FractionalBrownianMotion 31 7.1 fBm from LinearSystemTheory 32 7.2 CorrelationoffBm 35 7.3 Multifractal BrownianMotion 37 7.4 FractionalARIMA 37 7.5 WaveletBasedModelsfor SelfSimilarProcess 39 8 HeavyTailedProcesses 41 9 AnalysisandEstimationTechniquesfor SelfSimilarProcesses 42 9.1 RlS Statistic 43 9.2 VarianceAggregationplot 43 9.3 SpectralEstimator 44 10 WaveletBasedAnalysisofSelfSimilarProcess 45 10.1 Statistical Properties of Wavelet Coefficients of Self SimilarProcesses 47 10.2 Abry-VeitchEstimator 47 11 TheNeedfor Multifractal Processes 48 11.1 Characterizingthe Distributionofa 50 11.2 Local SingularityAnalysis UsingWavelets 51 11.3 HolderExponentsfrom TaylorSeries 51 11.4 WaveletVanishingMomentsandLocalRegularity 52 12 Salientpointsfrom the chapter 53 3. BROADBANDNETWORKTRAFFICMODELING 55 1 BroadbandNetworkTrafficCharacteristics 55 2 NetworkTrafficModelingMethodology 57 3 State-of-the-ArtinTeletrafficModeling 58 3.1 ON- OFFModel 58 3.2 CIPPProcess 60 3.3 Multiple ScalinginNetworkData 61 3.4 FromSelfsimilarity toMultifractals 62 3.5 Multifractal WaveletModel 63 4 VideoTrafficModeling 67 4.1 MPEGVideo SourceEncoding 67 4.2 Modelsfor VBRVideoTraffic 69 5 SummaryofBroadbandTrafficModels 70 Contents VB 4. MULTIPLICATIVECASCADES 71 1 BinomialMultiplicative Cascade 72 2 CharacterizingMultifractalsthroughMultifractal Spectrum 75 3 Methodsto EstimateMultifractal Spectrum 81 3.1 HistogramMethod 81 3.2 MethodOfMoments 82 4 InterpretingtheMultifractal Spectrum 84 4.1 Multifractal Spectrumas Fractal Dimension 84 4.2 Multifractal Spectrumfrom LargeDeviationtheory 84 5 GeneralizedDimensions 87 6 SummaryoftheChapter 90 5. V.V.G.MMULTIFRACTALMODEL 93 DevelopmentofVVG.MMultifractal Model 94 1.1 EstimationofMultiplierDistributions 96 1.2 SynthesisAlgorithm 97 2 Statistical ComparisonTests 98 2.1 AutocorrelationFunction 98 2.2 HigherOrderMomentsofAggregatedData 99 2.3 Multifractal SpectrumCurve 101 3 Testfor Robustnessofthe ParametricModel 104 4 PerformanceandQueuingTests 107 4.1 QueuelengthDistribution 107 4.2 ComparisonofPacketLoss 108 4.3 ComparisonofDelay 110 5 InterDepartureProcess 111 6 VVG.Mand MWM :A Comparison 112 7 SalientPointsofthe VVG.M Model 114 6. ANALYSISOFTHEMULTIPLEXINGOFTRAFFIC 115 1 AnalysisofMultiplexing using VV.G.M Model 116 2 AnalysisofMultiplexingusing Multifractal Spectrum 118 3 Analysisofthe Multiplexing using Entropy 120 3.1 ProofofEntropy Scaling 123 3.2 Relation withGeneralizedDimensions 124 4 How ComplexisInterArrival Data? 125 5 Salientpoints from thechapter 127 Vlll MULT/FRACTALBASEDNETWORKTRAFFICMODELING 7. MODELINGOFVBRVIDEOTRACES 129 1 VBRVideoModelingUsing Multifractals 130 2 StatisticalTestsforModel Evaluation 132 2.1 HigherOrderMomentsofAggregatedData 132 2.2 IndexOfDispersionofCounts 134 2.3 Multifractal Spectrum 135 3 ResultsofQueuingSimulations 137 3.1 BehaviorofQueueLengths 137 3.2 VarianceofCellDelay 137 3.3 ComparisonofCell Loss 139 4 ComplexityofVBRVideoTraces 140 5 Salientpointsfrom theChapter 142 8. QOSISSUESANDCONTROLOFBROADBAND TRAFFIC 143 1 StatisticsofMultiplicativeCascadeProcesses 144 1.1 GlobalScalingParameter 146 1.2 HeavyTailedDistributionofVVG.M 149 2 QueuingTheoryfor CascadeProcesses 150 3 EffectiveBandwidthEstimationforQoS 152 3.1 EffectiveBandwidthforVVG.MProcess 153 4 EstimationandPredictionofBurstiness 156 4.1 ResultsofEstimationofTrafficBurstiness 157 4.2 BurstinessPredictionUsing KalmanFilter 159 5 Salientpointsfrom thechapter 161 9. CONCLUSIONS 165 1 VVG.MCascadeProcessfor BroadbandNetworkTraffic 165 2 FutureWork 166 2.1 Systemtheoretic ModelingofComputerNetworks 166 2.2 DevelopmentofNetworkProcessors 167 2.3 SignalProcessingandNetworking 167 2.4 StudyofComplex Systems 167 Appendices 169 A. WaveletTransform 169 B. LegendreTransform 171 C. LargeDeviationTheory. 175 Contents IX D. Norros'sQueuingModel 179 0.1 ParameterizingQoS Requirements 180 0.1.1 ParameterizingBufferLength 182 0.1.2 ParameterizingServiceRate 182 0.1.3 ParameterizingQueueLengthDistribution 182 E. EffectiveBandwidth 185 E.l Properties 185 E.2 ApplicationinQueuingSystems 186 F. KalmanFilter 189 G. SomeWebsitesofInterest 195 References 197 Index 209 List ofSymbols X(t) -Randomprocess withfinitesecondorderstatistics. N(t) -PoissonProcess. H -Hurstparameter(0 <H <1). BH(t) -FractionalBrownianmotionwithHurstparameterH. BH.(t) -MultiFractionalBrownianmotionwithtimevaryingHurstparameterHt. 'YBH(t) -Covariancefunction ofiBm. p(k) -Autocorrelationfunction. r(.) -Gammafunction. 4>(.) -ARIMApolynomial. q,(.) -ARIMApolynomial. XH(Q) -PowerspectrumofselfsimilarprocesswithHurstparameterH. 'Y -Indexofheavytaildistribution. N(f.) -Numberofintervalsofsizef.. DI -Fractaldimension. a -Holderexponent. N.(a) -Noofintervalsofsizef. withH.Ea. /(a) -Multifractalspectrum. di,k -Detailcoefficientsofwavelettransformatscalej andshiftk. 'l/Ji,k(t) -WaveletfunctionatscaleJ andshiftk. cPi,k(t) -Scalingfunction atscalej andshiftk. Wi,k -Waveletcoefficientatscalej andshiftk. Ui,k -Scalingcoefficientatscalej andshiftk. Ai,k -Multiplieratscalej andshiftk forMWMcascade. th Jj(Ik) -Measureofthek intervalinthecascade. th a(Ik) -Holderexponentofthek intervalinthecascade. CPo -Relative%ofoccuranceofmultipliermo. Xq(f.) -Partitionfunction. xii MULT/FRACTAL BASEDNETWORKTRAFFICMODELING r(q) -Freeenergy. 0:0 -MostprobableHolderexponent. rR(o:) -DeviationtotherightsideofmostprobableHolderexponent0'0. XiN •itk pointinthecascadegeneratedprocessattheNk stage. lk fRj(r) -Multiplierdistributionatthe stageinthecascade. T/N -weightedautocorrelationfunction. p.(m)(q) _qtk momentofdatawithm levelaggregation. oX -Bufferutilizationfactor. (3 -Packingdimensionoftheattractorobtainedon multiplexing. Hs -Shannonentropy. Pi -Probabilityofoccupancyoftheitk state. Dq -qtk generalizeddimension. 'Y(n) -Volatilityofthetimeseries. 'Yb(n) -Binaryvolatilitytimeseries. In(T) -IndexofdispersionofcountsforthetimedurationT. w(m) _Aggregatedcascadeprocessuptolevelm. Hell -Effective/globalHurstexponent. j.S2 -Secondmomentofthemultiplierdistribution. V(t) -Queuelength. ebx(8,r) -Effectivebandwidth. r* -Criticaltimescalevalue. 8* -Criticalspacespacevalue. Pu(t) -Taylorseriesexpansionoftheprocessaroundneighborhood u. TI(t)(a,u) -Wavelettransformofprocessf(t) atscaleaandshiftu. o:(k) -EstimatedvalueofHolderexponent. o:(k) -PredictedvalueofHolderexponent. K" -Kalmanfiltergain.