Network Service Analysis: A Statistical Calculus

Statistical analysis of network service measures is a significant research area of de-termining the strategies of network service provisioning due to the increasing needs ofmultimedia communications and value-added services. Due to the advantages in terms ofgenerality of modeling and feasibility in a multi-node case, Statistical Network Calculushas become a powerful tool for statistical network service analysis. This dissertation aimsto summarize and report the research outcomes of the author during the period of his pur-suing a Ph. D degree, which include a series of results in terms of improving and extendingthe theory of statistical network calculus, and applying them to statistical service analysisof networks what are common in practice.Statistical network calculus involves three major aspects. The first is to build up a fun-damental model to characterize network tra?c processes, called statistical tra?c envelope.The second is to build up a principal model to describe network service capacity, referredto as statistical service curve. The final is represented by a systematic approach based onthese two models to attain general results of end-to-end service analysis. However, existingstudies have the following limitations: (1) The statistical tra?c envelopes developed so fareither lack generality in that they are not suitable for a wide range of stochastic tra?cprocess, or do not have analytical tractability in terms of computing the bounds on servicemeasures; (2) Existing statistical service curves do not simultaneously have desired proper-ties, including formulation generality, instancing node schedulers, solving equivalent modelin a multiple-node or aggregate scheduling case. To solve these problems, the followingresults are reported in this dissertation:First, in order to achieve both generality and analytical tractability, two types ofstatistical tra?c envelope are presented, including Global Statistical Envelope (GSE) andStrong Global Statistical envelope (SGSE). They are both defined in a general form, andare applicable for describing common tra?c processes including heavily-tailed ?ows andaggregates of regulated ?ows. Also they can be easily used for computing probabilisticupper bounds on service measures in a general case. In order to solve the problem ofanalytical intractability associated with existing Local Statistical Envelope (LSE), a generalapproach is presented to convert LSE to GSE. It is shown that the use of GSE and SGSE overcomes the limits associated with existing statistical tra?c envelopes, and is e?ectivefor the characterizations and the service analysis of actual ?ows.Then, for remedying the weakness of current statistical service curves, a general modelreferred to as Global Statistical Service Curve (GSSC) is proposed, which is proven to haveall the advantageous properties mentioned above. Existing Local Statistical Service Curve(LSSC) is also instanced with common types of schedulers, and a general approach ispresented to convert LSSC to GSSC, leading to a solution to its problem with respectto concatenation equivalence. It is shown that GSSC has all four properties needed formodeling the service capacity of a complex multi-node network, and the results aboutLSSC release its original limitation.Finally, based on the GSE and SGSE of input tra?c, important parameters are derivedincluding probabilistic bounds on delay, backlog and output tra?c for a ?ow served by anetwork with Service Curve,LSSC or GSSC. These general results are further applied tocompute the tail distribution of end-to-end delay in the cases of some common types of ?owand node scheduler. Numerical experiments show that the theoretical analysis presentedin this dissertation o?er significantly tighter bounds on end-to-end delay than the existingones.It should be mentioned that the above results lead to a statistical network calculusframework, which extends and improves existing studies in the literature. It is expectedthat the statistical calculus developed in this dissertation can be applied to the statisticalservice analysis of actual networks with service di?erentiation, which are more complex innature, and can provide a theoretical basis for determining the strategies of e?cient serviceprovisioning.