Abstract |
Modern networks have become increasingly complex over the past years in terms of control algorithms, applications and service expectations. Since classical theories for the analysis of telephone networks were found inadequate to cope with these complexities, new analytical tools have been conceived as of late. Among these, the stochastic network calculus has given rise to the optimism that it can emerge as an elegant mathematical tool for assessing network performance. This thesis argues that the stochastic network calculus can provide new analytical insight into the scaling properties of network performance metrics. In this sense it is shown that end-to-end delays grow as Θ(H log H) in the number of network nodes H , as opposed to the Θ(H) order of growth predicted by other theories under simplifying assumptions. It is also shown a comparison between delay bounds obtained with the stochastic network calculus and exact results available in some product-form queueing networks. The main technical contribution of this thesis is a construction of a statistical network service curve that expresses the service given to a flow by a network as if the flow traversed a single node only. This network service curve enables the proof of the O(H log H) scaling of end-to-end delays, and lends itself to explicit numerical evaluations for a wide class of arrivals. The value of the constructed network service curve becomes apparent by showing that, in the stochastic network calculus, end-to-end delay bounds obtained by adding single-node delay bounds grow as O(H3). Another technical contribution is the application of supermartingales based techniques in order to evaluate sample-path bounds in the stochastic network calculus. These techniques are suitable to arrival processes with stationary and independent increments, and improve the performance bounds obtained with existing techniques. |