A Temporal Network Calculus for Performance Analysis of Computer Networks

Abstract

One inevitable trend of network development is to deliver information with various traffic characteristics and diverse Quality of Service (QoS) requirements. In response to the continually growing demand for more bandwidth, network performance analysis is needed to optimize the performance of existing technologies and evaluate the efficiency of new ones. Performance analysis investigates how traffic management mechanisms deployed in the network affect the resource allocation among users and the performance which the users experience. This topic can be investigated by constructing models of traffic management mechanisms and studying how these mechanisms perform under various types of network traffic.

To this end, appropriate mathematical models are needed to characterize the traffic management mechanisms which we are interested in and represent different types of network traffic. In addition, fundamental properties which can be employed to manipulate the models should be explored.

Over the last two decades a relatively new theory, stochastic network calculus, has been developed to enable mathematical performance analysis of computer networks. Particularly, several related processes are mathematically modeled, including the arrival process, the waiting process and the service process. This theory can be applied to the derivation and calculation of several performance metrics such as the backlog bound and the delay bound. The most attractive contribution of stochastic network calculus is to characterize the behavior of a process based on some bound on the complementary cumulative distribution function (CCDF). The behavior of a computer network is often subject to many irregularities and stochastic fluctuations. The models based on the bound on the CCDF are not very accurate, while they are more feasible for abstracting computer network systems and representing various types of network traffic.

This thesis is devoted to investigate the performance of networks from the temporal perspective. Specifically, the traffic arrival process characterizes the distribution of the cumulative inter-arrival time and the service process describes the distribution of the cumulative service time. Central to finding a bound on the CCDF of the cumulative interarrival time and the cumulative service time, several variations of the traffic characterization and the service characterization are developed. The purpose of developing several variations to characterize the same process is to facilitate the derivation and calculation of performance metrics.

In order to derive and calculate the performance metrics, four fundamental properties are explored, including the service guarantees, the output characterization, the concatenation property and the superposition property. The four properties can be combined differently when deriving the performance metrics of a single node, a series of nodes or the superposition flow.

Compared to the available literature on stochastic network calculus which mainly focuses on studying network performance in the spacedomain, this work develops a generic framework for mathematically analyzing network performance in the time-domain. The potential applications of this temporal approach include the wireless networks and the multi-access networks.

Furthermore, the complete procedure of concretizing the generic traffic models and service models is presented in detail. It reveals the key of applying the developed temporal network calculus approach to network performance analysis, i.e., to derive the bounding function which is the upper bound on the tail probability of a stochastic process. Several mathematical methods are introduced, such as the martingale, the moment generating function (MGF) and a concentration theory result