A Performance Analysis Approach Based On Stochastic Network Calculus

Network Calculus is a new theory for network performance analysis that has drawngreat attention since 1991 when it was proposed. It has developed along two tracks: de-terministic network calculus (DNC) and stochastic network calculus (SNC). DNC hasbeen thoroughly studied and widely used in the quality of service (QoS) analysis of In-ternet. However, it can only calculate the worst-case performance of network, leading topessimistic estimation. SNC is a stochastic extension of DNC. It can provide stochasticservice guarantees that make better use of the multiplexing gain in networks. Growinginterest has been attracted to improve SNC.This thesis aims to solve the reasoning difficulties of the current SNC and providesome guidance on how to apply SNC in practice. The remarkable contributions of thisresearch are that we provide a radical solution for the reasoning difficulties, and hencedramatically reduce the complexity of SNC and significantly improve the analysis resultsof SNC. These help SNC to be widely accepted in the research areas of performanceanalysis. The research in this thesis can be largely divided into two parts: the research onimproving SNC and the research on applying SNC.About the research on improving SNC, there are three main contributions.(1) Addressing the reasoning difficulties of the current SNC from the perspective ofits algebraic basis and proposing a feasible solutionThe algebraic basis of the current SNC is min-plus algebra. Since it is difficult tohandle the probability operation in min-plus algebra, SNC is not very widely acceptedby now. We address these difficulties from the perspective of min-plus algebra, and findthat it is impossible to integrate the probability operation into min-plus algebra. So, wetry to construct a new SNC without min-plus algebra. We argue that the solution withoutmin-plus algebra is feasible and can lead to better results of performance analysis.(2) Replacing the algebraic basis of DNC with an axiom system for performanceanalysisTo construct a new SNC without min-plus algebra, we need to replace the algebraicbasis of SNC. Note that the min-plus algebra in SNC is from the algebraic basis of DNC,so we consider DNC first. By studying the analysis model of DNC, we outline an axiomsystem that can derive the basic theorems of DNC. Based on the axiom system, we con- struct a new DNC without min-plus algebra (named Min-Plus DNC, NMP-DNC). Theseshow that the axiom system can replace the role of min-plus algebra in DNC.(3) Constructing a new SNC from the axiom system without min-plus algebraThis contribution is the key contribution of this thesis. To provide a radical solu-tion for the reasoning difficulties of the current SNC, we construct a new SNC withoutmin-plus algebra (named Min-Plus SNC, NMP-SNC). NMP-SNC is a stochastically ex-tensionofNMP-DNC.WebuildNMP-SNCinthefollowingtwosteps: 1)extendthebasicconcepts of NMP-DNC to their stochastic versions in NMP-SNC; 2) derive the basic the-orems of NMP-SNC from the concepts and the axiom system. To show the improvementof NMP-SNC, we compare NMP-SNC with the current SNC by analyzing a sample net-work. Evaluations show that NMP-SNC can dramatically reduce the complexity of SNCand significantly improve the analysis results.About the research on applying SNC, there are two main contributions.(4) Studying two common problems on applying SNC: the selection of traffic modeland service model and the limitation of the analytical results of SNCThere are two basic concepts in SNC: arrival curve and service curve. A problemon applying SNC is how to select appropriate arrival curve and service curve so as to getgood results. We present new arrival curve and service curve with free parameters, whichhelps to select optimal curve models. Another problem on applying SNC is whether theanalytical results of SNC is tight enough. We find an inherent problem of SNC that thereis always a gap between the analytical results and the real performance. We solve theinherent problem by introducing a new method and present guidance for applying SNCin practice.(5) Addressing the problems on how to apply Network Calculus in wireless networkcodingNetworkCodingisanewdevelopedtechniquetoimprovecommunicationnetworks.In wireless network coding, different flows can be coded together, raising three specificproblems to apply the flow-based Network Calculus. 1) When flows are coded together,how to identify the original uncoded flows? 2) How to characterize the broadcast proper-ties of wireless channel so as to calculate the service curve provided by a wireless node?3) How to calculate the service capacity of a node if it can perform network coding? Byanalyzingapracticalwirelessnetworkcoding, wefigureoutthefactorsthataffecttheper- formance of wireless network coding. Besides, we introduce a new scheduling scheme toimprove the practical wireless network coding.In summary, we construct a new concise SNC (NMP-SNC) that can avoid the rea-soningdifficultiesofthecurrentSNC.NMP-SNCcandramaticallyreducethecomplexityof SNC and significantly improve the analysis results. Based on NMP-SNC, we addresscommon problems on applying SNC and analyze the performance of wireless networkcoding with Network Calculus. These help SNC to be widely accepted in the researchareas of performance analysis.