Change search

A Temporal Network Calculus for Performance Analysis of Computer Networks
Norwegian University of Science and Technology, Faculty of Information Technology, Mathematics and Electrical Engineering, Department of Electronics and Telecommunications.
2011 (English)Doctoral thesis, comprehensive summary (Other academic)
##### Abstract [en]

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

NTNU, 2011.
##### Series
Doctoral theses at NTNU, ISSN 1503-8181 ; 2011:199
##### National Category
Electronics Telecommunication
##### Identifiers
ISBN: 978-82-471-2950-0 (printed ver.)ISBN: 978-82-471-2951-7 (electronic ver.)OAI: oai:DiVA.org:ntnu-14619DiVA: diva2:457069
##### Public defence
2011-08-12, 00:00
Available from: 2011-11-16 Created: 2011-11-16 Last updated: 2011-11-16Bibliographically approved
##### List of papers
1. An Analysis on Error Servers for Stochastic Network Calculus
Open this publication in new window or tab >>An Analysis on Error Servers for Stochastic Network Calculus
2008 (English)In: Proceedings of the 33rd IEEE Conference on Local Computer Networks (LCN), 2008, Vol. 2008, 173-180 p.Conference paper (Refereed)
##### Abstract [en]

Network calculus is a recently developed theory dealing with queuing systems found in computer networks with focus on service guarantee analysis. In the current network calculus literature, the behavior of a server is typically modeled with the cumulative amount of service it successfully delivers, and the successfulness of service delivery implies no error in the delivered service. However, there are many networks such as wireless networks, where, not only is the service error-prone due to multi-access contention and/or random error on the communication link, but different error handling methods may also be applied. In such cases, it is difficult to directly apply the existing network calculus results due to lack of server models taking error into account. In this paper, an error server model is proposed for stochastic network calculus, based on which, an analysis on error servers is performed. The corresponding concatenation property is derived, which shows that under some general conditions, the tandem of error servers can be treated as an equivalent error server. In addition, to demonstrate the use and implication of the proposed error server model, performance bounds are derived and compared for a simple network. The study of the simple network shows that error handling may have significant impact on the performance bounds, and the proposed error server model can facilitate the analysis.

##### Identifiers
urn:nbn:no:ntnu:diva-14614 (URN)10.1109/LCN.2008.4664168 (DOI)000262914500023 ()
##### Conference
33rd IEEE Conference on Local Computer Networks (LCN)
##### Note
(c) 2011 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other users, including reprinting/ republishing this material for advertising or promotional purposes, creating new collective works for resale or redistribution to servers or lists, or reuse of any copyrighted components of this work in other works.Available from: 2011-11-16 Created: 2011-11-16 Last updated: 2011-11-16Bibliographically approved
2. Stochastic Network Calculus Models under Max-Plus Algebra
Open this publication in new window or tab >>Stochastic Network Calculus Models under Max-Plus Algebra
2009 (English)In: Proceedings of IEEE Global Telecommunications Conference, 2009, 1121-1126 p.Conference paper (Refereed)
##### Abstract [en]

A challenging research issue of analyzing networks where packets are served probabilistically, such as multi-access networks and wireless networks, is to characterize the stochastic nature of service provided to users. This paper proposes a server model for characterizing a service process with the consideration of the stochastic nature of service. The proposed server model is defined based on a probabilistic bound on the cumulative packet service time. In addition, two traffic models characterizing the arrival process by the cumulative packet inter-arrival time are defined. Based on the proposed models, stochastic service guarantees including delay bound and backlog bound and the output characterization are explored. A two-class Probabilistic Priority server system, a generic server model which can model systems serving packets probabilistically, is analyzed to illustrate that the proposed models can facilitate performance analysis.

##### Identifiers
urn:nbn:no:ntnu:diva-14615 (URN)10.1109/GLOCOM.2009.5425464 (DOI)000280579100185 ()
##### Conference
IEEE Global Telecommunications Conference (Globecom)
##### Note
"(c) 2011 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other users, including reprinting/ republishing this material for advertising or promotional purposes, creating new collective works for resale or redistribution to servers or lists, or reuse of any copyrighted components of this work in other works." Available from: 2011-11-16 Created: 2011-11-16 Last updated: 2011-11-16Bibliographically approved
3. Stochastic Service Guarantee Analysis Based on Time-Domain Models
Open this publication in new window or tab >>Stochastic Service Guarantee Analysis Based on Time-Domain Models
2009 (English)In: 2009 IEEE INTERNATIONAL SYMPOSIUM ON MODELING, ANALYSIS & SIMULATION OF COMPUTER AND TELECOMMUNICATION SYSTEMS (MASCOTS), NEW YORK: IEEE , 2009, 472-483 p.Conference paper (Other academic)
##### Abstract [en]

Stochastic network calculus is a theory for stochastic service guarantee analysis of computer communication networks. In the current stochastic network calculus literature, its traffic and server models are typically defined based on the cumulative amount of traffic and cumulative amount of service respectively. However, there are network scenarios where the applicability of such models is limited, and hence new ways of modeling traffic and service are needed to address this limitation. This paper presents time-domain models and results for stochastic network calculus. Particularly, we define traffic models, which are defined based on probabilistic lower-bounds on cumulative packet inter-arrival time, and server models, which are defined based on probabilistic upper-bounds on cumulative packet service time. In addition, examples demonstrating the use of the proposed time-domain models are provided. On the basis of the proposed models, the five basic properties of stochastic network calculus are also proved, which implies broad applicability of the proposed time-domain approach.

##### Place, publisher, year, edition, pages
NEW YORK: IEEE, 2009
##### Identifiers
urn:nbn:no:ntnu:diva-14616 (URN)10.1109/MASCOT.2009.5426445 (DOI)000275140200046 ()
##### Conference
17th Annual Meeting of the IEEE/ACM International Symposium onModelling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS)
##### Note
"(c) 2011 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other users, including reprinting/ republishing this material for advertising or promotional purposes, creating new collective works for resale or redistribution to servers or lists, or reuse of any copyrighted components of this work in other works."Available from: 2011-11-16 Created: 2011-11-16 Last updated: 2011-11-16Bibliographically approved
4. A network calculus approach to delay evaluation of IEEE 802.11 DCF
Open this publication in new window or tab >>A network calculus approach to delay evaluation of IEEE 802.11 DCF
2010 (English)In: Proceedings of the 35th IEEE Conference on Local Computer Networks (LCN), Denver, USA, October 2010., IEEE , 2010, 560-567 p.Conference paper (Refereed)
IEEE, 2010
##### Identifiers
urn:nbn:no:ntnu:diva-14617 (URN)10.1109/LCN.2010.5735773 (DOI)
##### Note
(c) 2011 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other users, including reprinting/ republishing this material for advertising or promotional purposes, creating new collective works for resale or redistribution to servers or lists, or reuse of any copyrighted components of this work in other worksAvailable from: 2011-11-16 Created: 2011-11-16 Last updated: 2011-11-16Bibliographically approved
5. A Temporal Network Calculus Approach to Service Guarantee Analysis of Stochastic Networks
Open this publication in new window or tab >>A Temporal Network Calculus Approach to Service Guarantee Analysis of Stochastic Networks
2011 (English)In: Proceedings of the 5th International ICST Conference on Performance Evaluation Methodologies and Tools (ValueTools), Paris, France, May 2011, 2011Conference paper (Refereed)
##### Identifiers
urn:nbn:no:ntnu:diva-14618 (URN)
##### Conference
5th International ICST Conference on Performance
##### Note
"© ACM, 2011. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version of the Paper will appear in the ACM Digital Library http://dl.acm.org/Available from: 2011-11-16 Created: 2011-11-16 Last updated: 2011-11-16Bibliographically approved

#### Open Access in DiVA

##### File information
File name FULLTEXT01.pdfFile size 952 kBChecksum SHA-512
Type fulltextMimetype application/pdf
##### By organisation
Department of Electronics and Telecommunications
##### On the subject
ElectronicsTelecommunication