1、網絡專題選講:網絡演算論(II)華技大學電子與信息工程系陳京文jwchen2012年12月6日內容提要l 網絡演算論的概率意義擴展l 統計型流量包絡(Statistical Traffic Envelopes)l 統計型服務曲線(Statistical Service Curves)l 統計型服務性能上界-2-網絡專題選講Network Calculus Revisitedservice curvearrival curvel Arrival curve mindicates an upper bound on flowtraffic, while Service curve mexpress

2、es a lowerbound on the network service capacity for a flowl Given the Arrival curve of a flow and the Service curve of the network system, the upper bounds on delay, backlog and traffic departure of this flow can be readily solved-3-網絡專題選講Network Calculus Revisited (contd.)l Two ms are general and a

3、vailable for various typesof multi-node networkl arrival curve -> regulated traffic processesl service curve and other three ml types of scheduling disciplinel single-node or multi-nodesl per-flow or aggregated schedulingl Provides general theoretical results of service bounds of a flow in a mult

4、i-node networkl Worst-case view of service measures-4-網絡專題選講Statistical Service AnalysisQueueing Theoryl classical tool which offers exact resultsll difficult to be applied to nodes with non-FIFO types of schedulerl fit for single node case, but relies on summing up the results at all nodes as the e

5、nd-to-end one in a multi-node casel result is related with specific m lack of generalityof traffic source, and thusEffective Bandwidthl influential theory developed in 1990sl difficult to be applied to practical schedulersl fit for single node case rather than for multi-node casell mainly for comput

6、ing tail distribution of queue length, and offers only loose resultsStatistical/Stochastic Network Calculusl extension of Network Calculus in a probabilistic settingl offers general results of statistical service boundsll thought as a part of information system theory in the area of data networks網絡專

7、題選講-5-Comparison-6-網絡專題選講RequirementsQueueingEffectiveNetworkStatistical NetworkTheoryBandwidthCalculusCalculusTraffic classes (incl. self-similar, heavy-tailed)LimitedBroadBroad (but loose)BroadSchedulingLimitedNoYesYesQoS (bounds on loss, throughput delay)Very limitedLoss, throughputDeterministicY

8、esStatistical MultiplexingSomeYesNoYesExtending Network Calculus to a Probabilistic Settingl Basic ideal traffic process of a flow: Deterministic Traffic Envelope (DTE, i.e., arrival curve) -> Statistical Traffic Envelope (STE)l service capacity of a network system: Service Curve -> Statistica

9、l Service Curve (SSC)l the same mathematical approach: Min-Plus algebral Expectationsl STE: to express traffic sources as much as possible, e.g., aggregate of regulated flows, Gaussian processes, heavy-tailed processesl SSC: to abstract stochastically fluctuated service to a concernedfe with differe

10、nt type of schedulerl tractability of statistical service boundsl given STE and SSC, statistical bounds on delay, backlog andtraffic departure can be solved-7-網絡專題選講Extending Network Calculus to a Probabilistic Setting(contd.)l Further requirementsl concatenation equivalence: the equivalent SSC of a

11、concatenation of multiple nodes can be solved based on the ones of these nodesl per-flow equivalence: per-flow SSC can be attained based on the one for whole aggregate in the case of aggregate scheduling-8-網絡專題選講Basic MsSSCSTEl Statistical traffic envelope (STE) ml a probabilistic upper bound on the

12、 traffic process of a flow during any time periodl Statistical service curve (SSC) ml a probabilistic lower bound on the serving process ofthe network system to a flowl explained roughly as qualifying the amount of traffic at least can be transmitted (served)-9-內容提要l 網絡演算論的概率意義擴展l 統計型流量包絡(Statistica

13、l Traffic Envelopes)l 統計型服務曲線(Statistical Service Curves)l 統計型服務性能上界-10-網絡專題選講Statistical Traffic Envelope (STE)DefinitionGiven a traffic process of a flow, denoted by its accumulatedltraffic A(t, t+t) during t, t+t, if there is a function Ge(t) of, such that, for any t,³ 0, the probability of

14、A(t,time intervalt+t) £ Ge(t) is not less than1-e, Ge(t) is referred to as theStatistical Traffic Envelope (STE) of this flow, where eindicates theum violation probabilityFunction formulationl Explicit Burstiness (EB)：Ge(t) = a(t)+s, and e = f(s)l General: no above limitationsl-11-網絡專題選講STE: Ex

15、pected Propertiesl Generality in terms of characterizing a wide range of stochastic traffic processesl aggregate of regulated flowsl heavy-tailed flowsl Gaussian flowsl l Tractability in terms of computing statistical service boundsl together with deterministic/statistical service curve, statistical

16、 bounds on service measures can be certainly computed-12-網絡專題選講STE: Classesl Three classes of STE distinguished by the sense of probabilistic upper bound on accumulated trafficl Local Statistical Envelope (LSE) Le(t):for any t,³ 0，Pr A(t, t+ ) £ L ( ) ³ 1-l Global Statistical Envelope

17、 (GSE) Ge(t):for any t ³ 0，Pr "³ 0: A(t, t+ ) £ G ( ) ³ 1-l Strong Global Statistical Envelope (SGSE) He(t):Pr " t,³ 0: A(t, t+ ) £ H ( ) ³ 1-l Implications: bound flow traffic during any time period in point-wise or sample path sense-13-網絡專題選講DTE, LSE an

18、d GSEGSE Ge(t)Violated by a few sample pathsDTE a(t)Never violatedSample pathsA(0, t)LSE Le(t)Violated by a few points of each sample path-14-網絡專題選講Implications of Various STEsl EB-form STEsl difficult to characterize aggregated traffic processes ofregulated flowsl General LSEl cannot be used to com

19、pute service bounds with no assumption of Gaussian processl General GSEl results in only point-wise statistical service curvel General SGSEl too strict to provide tight bounds on service measuresl so far available only for a few types of flow-15-網絡專題選講內容提要l 網絡演算論的概率意義擴展l 統計型流量包絡(Statistical Traffic

20、Envelopes)l 統計型服務曲線(Statistical Service Curves)l 統計型服務性能上界-16-網絡專題選講Statistical Service Curve (SSC)l DefinitionGiven a flow with traffic arrival A(t) served by a networksystem, if there is a function Se(t) of time t, such that, for any t³ 0, the probability of traffic departure D(t) ³ A(t)

21、 Ä Se(t) isnot less than1-e, Se(t) is referred to as the Statistical Service Curve (SSC) of the system to this flow, where e indicates theum violation probabilityl Function formulationl Explicit Virtual Backlog (EVB): Se(t) = b(t)- b, and e = f(b)l General: no above limitations-17-網絡專題選講SSC: Cl

22、assesl Two classes of SSC distinguished by the sense of probabilistic lower bound on service capacityl Local Statistical Service Curve (LSSC) Se(t): for any t ³ 0, Pr D(t) ³ A(t) Ä Se(t) ³ 1-el Global Statistical Service Curve (GSSC) Ze(t):Pr"t ³ 0: D(t) ³ A(t)

23、96; Ze(t) ³ 1-el Implications: bound the service capacity of a network system in point-wise or sample path sense-18-網絡專題選講Ming Node Scheduler-19-網絡專題選講Concatenation Equivalence-20-網絡專題選講Per-Flow Equivalence-21-網絡專題選講Implications of Various SSCsl EVB-form SSCl difficult to ma scheduler where bac

24、kground flowcannot be characterized by an EB-form STEl General LSSCl in general, cannot be directly applied either in a multi- node case or in an aggregate scheduling casel General GSSCl too strict to provide tight bounds on service measuresl available only when background flow can be characterized

25、by a SGSE-22-網絡專題選講LSSC and GSSC: GPS Schedulerl For flow il GSSCl LSSC-23-網絡專題選講GSSC and LSSC: Concatenationl GSSCl LSSC-24-網絡專題選講GSSC: Aggregate Schedulingl Equivalent GSSC-25-網絡專題選講From LSSC to GSSCl LSSCS s(x;),s = g(x),x Î Xl Function v(t) 0, ¥) ® X0l GSSCZe(t) = Ses(v(t); t)-26-

26、網絡專題選講內容提要l 網絡演算論的概率意義擴展l 統計型流量包絡(Statistical Traffic Envelopes)l 統計型服務曲線(Statistical Service Curves)l 統計型服務性能上界-27-網絡專題選講Computing Service BoundsDTE/STESC/SSCl Ms: DTE/STE + SC/SSCl both deterministic: only for aggregate of regulated flowsl one or two statistical msl generality of results is determ

27、ined by the ones of ml End-to-end analysis in a multi-node casel approach 1: sum up the ones at all nodessl approach 2: exploit the equivalence properties of SC/SSC ml comparison: approach 2 is preferred since it usually leads to tight results with low computation overhead網絡專題選講-28-In a LSSC SystemG

28、SE Gea(t)LSSC Ses(t)A(t)D(t)l Virtual delayPr W(t) £ infd ³ 0 | "t ³ 0: Gl Backloga(t-d) £ Ss(t) £ 1-(a+s)Pr B(t) £ G aØS s(0) £ 1- ( a+ s)l DepartureGdea+es() = GeaØSes( )-29-網絡專題選講In a GSSC SystemSGSE Hea(t)GSSC Zes(t)A(t)D(t)l Virtual delayPr"

29、;t ³ 0: W(t) £ infd ³ 0 | "t ³ 0: Gea(t-d) £ Zes(t) £ 1-(ea+es)l BacklogPr"t ³ 0: B(t) £ G aØZ s(0) £ 1- ( a+ s)l DepartureHdea+es() = HeaØZes( )-30-網絡專題選講Ms and BoundsStatistical bounds on delay, backlog, departure+STE Gea(t)SSC Ses(t

30、)A(t)D(t)-31-網絡專題選講STESSCProbabilistic Sense of Resulted BoundsGSELSSCpoint-wiseGSEGSSCpoint-wiseSGSELSSCpoint-wiseSGSEGSSCsample pathDelay in GPS Scheduling Networkl Flow a and m: EBB, Le(t) = rt+s, e = pe-qsl Delay bound with violation probability e-32-網絡專題選講Numerical Experimentsl Flow a and m con

31、sist of the sa Off traffic processesmber of Markov On-ltype 1: P1=1.5Mbps, m1=1.0ms-1, l1=0.11ms-1l type 2: P2=1.5Mbps, m2=0.1ms-1,2=0.01ms-1l GPS scheduling nodeC = 100 Mbps, ra = rb = 50 Mbpsl Comparisonl Labeled with GSE: based on the conversion from LSSC to GSSCl Labeled with SE: F. Ciucu et. al

32、, “A network service curve approach for the stochastic analysis of networks,”Sigmetrics05網絡專題選講-33-Numerical Results (1)-34-網絡專題選講Numerical Results (2)-35-網絡專題選講Numerical Results (3)-36-網絡專題選講Numerical Results (4)-37-網絡專題選講小結l Statistical network service analysisl Extending Network Calculus to a pro

33、babilistic settingl Statistical Traffic Envelopesl Classes, forms, implicationsl Statistical Service Curvesl Expected properties, classes, forms, implications, conversionl Statistical service boundsl Bounds and combinations of STE and SSC, numerical evaluation-38-網絡專題選講References1 J. Y. Le Boudec and P. Thiran, Network Calculus. Springer-Verlag, 20012 V. Firoiu, J. Y. Le Boudec, D. Towsley and Z.L. Zhang, “Theories and Ms forInte