An Origin-Destination (OD) traffic matrix provides a major input to the design, planning and management of a telecommunications network. Since the Internet is being proposed as the principal delivery mechanism for telecommunications traffic at the present time, and this network is not owned or managed by a single entity, there are significant challenges for network planners and managers needing to determine equipment and topology configurations for the various sections of the Internet that are currently the responsibility of ISPs and traditional telcos. Planning of these sub-networks typically requires a traffic matrix of demands that is then used to infer the flows on the administrator's network. Unfortunately, computation of the traffic matrix from measurements of individual flows is extremely difficult due to the fact that the problem formulation generally leads to the need to solve an under-determined system of equations. Thus, there has been a major effort f rom among researchers to obtain the traffic matrix using various inference techniques. The major contribution of this thesis is the development of inference techniques for traffic matrix estimation problem according to three different approaches, viz: (1) deterministic, (2) statistical, and (3) dynamic approaches. Firstly, for the deterministic approach, the traffic matrix estimation problem is formulated as a nonlinear optimization problem based on the generalized Kruithof approach which uses the Kullback distance to measure the probabilistic distance between two traffic matrices. In addition, an algorithm using the Affine scaling method is developed to solve the constrained optimization problem. Secondly, for the statistical approach, a series of traffic matrices are obtained by applying a standard deterministic approach. The components of these matrices represent estimates of the volumes of flows being exchanged between all pairs of nodes at the respective measurement points and they form a stochastic counting process. Then, a Markovian Arrival Process of order two (MAP-2) is applied to model the counting processes formed from this series of estimated traffic matrices. Thirdly, for the dynamic approach, the dual problem of the multi-commodity flow problem is formulated to obtain a set of link weights. The new weight set enables flows to be rerouted along new paths, which create new constraints to overcome the under-determined nature of traffic matrix estimation. Since a weight change disturbs a network, the impact of weight changes on the network is investigated by using simulation based on the well-known ns2 simulator package. Finally, we introduce two network applications that make use of the deterministic and the statistical approaches to obtain a traffic matrix respectively and also describe a scenario for the use of the dynamic approach.

No / Given only the traffic correlations of counts and intervals, a Batch Renewal Arrival Process (BRAP) is completely determined, as the least biased choice and thus, it provides the analytic means to construct suitable traffic models for the study of queueing systems independently of any other traffic characteristics. In this context, the BRAP and the Batch Markovian Arrival Process (BMAP) are employed in the continuous time domain towards the analysis of the stable BRAP/GE/1 and BMAP/GE/1 queues with infinite capacity, single servers and generalized exponential (GE) service times. Novel closed form expressions for the steady state probabilities of these queues are obtained, based on the embedded Markov chains (EMCs) technique and the matrix-geometric (M-G) method, respectively. Moreover, the stable GEsGGeo/GE/1 queue with GE-type service times and a GEsGGeo BRAP consisting of bursty GE-type batch interarrival times and a shifted generalized geometric (sGGeo) batch size distribution is adopted to assess analytically the combined adverse effects of varying degrees of correlation of intervals between individual arrivals and the burstiness of service times upon the typical quality of service (QoS) measure of the mean queue length (MQL). Moreover, a comprehensive experimental study is carried out to investigate numerically the relative impact of count and interval traffic correlations as well as other traffic characteristics upon the performance of stable BRAP/GE/1 and BMAP/GE/1 queues. It is suggested via a conjecture that the BRAP/GE/1 queue is likely to yield pessimistic performance metrics in comparison to those of the stable BMAP/GE/1 queues under the worst case scenario (i.e., a worst case scenario) of the same positive count and interval traffic correlations arising from long sojourn in each phase.

A MAP/PH/1 queue is a queue having a Markov arrival process (MAP), and a single server with phase-type (PH -type) distributed service time. This thesis considers the departure process from these type of queues. We use matrix analytic methods, the Jordan canonical form of matrices, non-linear filtering and approximation techniques. The departure process of a queue is important in the analysis of networks of queues, as it may be the arrival process to another queue in the network. If a simple description were to exist for a departure process, the analysis of at least feed-forward networks of these queues would then be analytically tractable. Chapter 1 is an introduction to some of the literature and ideas surrounding the departure process from MAP/PH/1 queues. Chapter 2 sets up the basic notation and establishes some results which are used throughout the thesis. It contains a preliminary consideration of PH -type distributions, PH -renewal processes, MAP s, MAP/PH/1 queues, non-linear filtering and the Jordan canonical form. Chapter 3 is an expansion of "The Output process of an MMPP/M/1 queue", where the question of whether a MAP description can exist for the departure process of a non-trivial MAP/M/1 queue is considered. In a 1994 paper, Olivier and Walrand conjectured that the departure process of a MAP/PH/1 queue is not a MAP unless the queue is a stationary M/M/1 queue. This conjecture was prompted by their claim that the departure process of an MMPP/M/1 queue is not MAP unless the queue is a stationary M/M/1 queue. We show that their proof has an algebraic error, which leaves open the above question of whether the departure process of an MMPP/PH/1 queue is a MAP or not. In Chapter 4, the more fundamental problem of identifying stationary M/M/1 queues in the class of MAP/PH/1 queues is considered. It is essential to be able to determine from its generator when a stationary MAP is a Poisson process. This does not appear to have been discussed in the literature prior to the author's paper, where this deficiency was remedied using ideas from non-linear filtering theory, to give a characterisation as to when a stationary MAP is a Poisson process. Chapter 4 expands upon "When is a MAP Poisson". This investigation of higher order representations of the Poisson process is motivated by first considering when a higher order PH -type distribution is just negative exponential. In Chapter 5, we consider the related question of minimal order representations for PH -type distributions, an issue which has attracted much interest in the literature. A discussion of other authors' ideas is given and these ideas are then inter-related to the work presented in Chapter 4 on the PH -type distributions. The MAP/M/1 queue is then considered in Chapter 6 from the perspective of whether having an exact level and phase independent stationary distribution of the geometric form [Formula - Not available: see pdf version of the abstract] implies that the MAP is Poisson. The answer is in the affirmative for this question, but the converse is not strictly true. Apart from showing the ubiquitous asymptotic form of level and phase independence exhibited by all stable MAP/M/1 queues, we prove that a very large class of stable queues, exhibits what we have termed shift-one level and phase independence. Stable MAP/M/1 queues exhibiting shift-one level and phase independence, are characterised by a stationary distribution of the following form: [Formula - Not Available: see pdf version of the abstract] In Chapter 7, a family of approximations is proposed for the output process of a stationary MAP/PH/1 queue. To check the viability of these approximations, they are used as input to another single server queue. Performance measures for the second server are obtained analytically in both the tandem and approximation cases, thus eliminating the need for simulation to compare results. Comparison of these approximations is also made against other approximation methods in the literature. In Chapter 8, we show that our approximations from Chapter 7 have the property of exactly matching the inter-departure time distribution. Our kth approximation also accurately captures the first k-1 lag-correlation coefficients of the stationary departure process. The proofs of this direct association between lag-correlation coefficients and the level of complexity k are given. / Thesis (Ph.D.)--School of Applied Mathematics, 1999.

A MAP/PH/1 queue is a queue having a Markov arrival process (MAP), and a single server with phase-type (PH -type) distributed service time. This thesis considers the departure process from these type of queues. We use matrix analytic methods, the Jordan canonical form of matrices, non-linear filtering and approximation techniques. The departure process of a queue is important in the analysis of networks of queues, as it may be the arrival process to another queue in the network. If a simple description were to exist for a departure process, the analysis of at least feed-forward networks of these queues would then be analytically tractable. Chapter 1 is an introduction to some of the literature and ideas surrounding the departure process from MAP/PH/1 queues. Chapter 2 sets up the basic notation and establishes some results which are used throughout the thesis. It contains a preliminary consideration of PH -type distributions, PH -renewal processes, MAP s, MAP/PH/1 queues, non-linear filtering and the Jordan canonical form. Chapter 3 is an expansion of "The Output process of an MMPP/M/1 queue", where the question of whether a MAP description can exist for the departure process of a non-trivial MAP/M/1 queue is considered. In a 1994 paper, Olivier and Walrand conjectured that the departure process of a MAP/PH/1 queue is not a MAP unless the queue is a stationary M/M/1 queue. This conjecture was prompted by their claim that the departure process of an MMPP/M/1 queue is not MAP unless the queue is a stationary M/M/1 queue. We show that their proof has an algebraic error, which leaves open the above question of whether the departure process of an MMPP/PH/1 queue is a MAP or not. In Chapter 4, the more fundamental problem of identifying stationary M/M/1 queues in the class of MAP/PH/1 queues is considered. It is essential to be able to determine from its generator when a stationary MAP is a Poisson process. This does not appear to have been discussed in the literature prior to the author's paper, where this deficiency was remedied using ideas from non-linear filtering theory, to give a characterisation as to when a stationary MAP is a Poisson process. Chapter 4 expands upon "When is a MAP Poisson". This investigation of higher order representations of the Poisson process is motivated by first considering when a higher order PH -type distribution is just negative exponential. In Chapter 5, we consider the related question of minimal order representations for PH -type distributions, an issue which has attracted much interest in the literature. A discussion of other authors' ideas is given and these ideas are then inter-related to the work presented in Chapter 4 on the PH -type distributions. The MAP/M/1 queue is then considered in Chapter 6 from the perspective of whether having an exact level and phase independent stationary distribution of the geometric form [Formula - Not available: see pdf version of the abstract] implies that the MAP is Poisson. The answer is in the affirmative for this question, but the converse is not strictly true. Apart from showing the ubiquitous asymptotic form of level and phase independence exhibited by all stable MAP/M/1 queues, we prove that a very large class of stable queues, exhibits what we have termed shift-one level and phase independence. Stable MAP/M/1 queues exhibiting shift-one level and phase independence, are characterised by a stationary distribution of the following form: [Formula - Not Available: see pdf version of the abstract] In Chapter 7, a family of approximations is proposed for the output process of a stationary MAP/PH/1 queue. To check the viability of these approximations, they are used as input to another single server queue. Performance measures for the second server are obtained analytically in both the tandem and approximation cases, thus eliminating the need for simulation to compare results. Comparison of these approximations is also made against other approximation methods in the literature. In Chapter 8, we show that our approximations from Chapter 7 have the property of exactly matching the inter-departure time distribution. Our kth approximation also accurately captures the first k-1 lag-correlation coefficients of the stationary departure process. The proofs of this direct association between lag-correlation coefficients and the level of complexity k are given. / Thesis (Ph.D.)--School of Applied Mathematics, 1999.

No / An investigation is carried out on the nature of QoS measures for queues with correlated traffic in both discrete and continuous time domains. The study focuses on the single server GI(G)/M-[x]/1/N and GI(G)/Geo([x])/1/N queues with finite capacity, N, a general batch renewal arrival process (BRAP), GI(G) and either batch Poisson, M-[x] or batch geometric, Geo([x]) service times with general batch sizes, X. Closed form expressions for QoS measures, such as queue length and waiting time distributions and blocking probabilities are stochastically derived and showed to be, essentially, time domain invariant. Moreover, the sGGeo(sGGo)/Geo/l/N queue with a shifted generalised geometric (sGGeo) distribution is employed to assess the adverse impact of varying degrees of traffic correlations upon basic QoS measures and consequently, illustrative numerical results are presented. Finally, the global balance queue length distribution of the M-Geo/M-Geo/1/N queue is devised and reinterpreted in terms of information theoretic principle of entropy maximisation. (C) 2014 Elsevier Inc. All rights reserved.

<p>This thesis, consisting of three papers and a summary, studies topics in the theory of stochastic processes related to long-range dependence. Much recent interest in such probabilistic models has its origin in measurements of Internet traffic data, where typical characteristics of long memory have been observed. As a macroscopic feature, long-range dependence can be mathematically studied using certain scaling limit theorems. </p><p>Using such limit results, two different scaling regimes for Internet traffic models have been identified earlier. In one of these regimes traffic at large scales can be approximated by long-range dependent Gaussian or stable processes, while in the other regime the rescaled traffic fluctuates according to stable ``memoryless'' processes with independent increments. In Paper I a similar limit result is proved for a third scaling scheme, emerging as an intermediate case of the other two. The limit process here turns out to be a non-Gaussian and non-stable process with long-range dependence.</p><p>In Paper II we derive a representation for the latter limit process as a stochastic integral of a deterministic function with respect to a certain compensated Poisson random measure. This representation enables us to study some further properties of the process. In particular, we prove that the process at small scales behaves like a Gaussian process with long-range dependence, while at large scales it is close to a stable process with independent increments. Hence, the process can be regarded as a link between these two processes of completely different nature.</p><p>In Paper III we construct a class of processes locally behaving as Gaussian and globally as stable processes and including the limit process obtained in Paper I. These processes can be chosen to be long-range dependent and are potentially suitable as models in applications with distinct local and global behaviour. They are defined using stochastic integrals with respect to the same compensated Poisson random measure as used in Paper II.</p>

This thesis, consisting of three papers and a summary, studies topics in the theory of stochastic processes related to long-range dependence. Much recent interest in such probabilistic models has its origin in measurements of Internet traffic data, where typical characteristics of long memory have been observed. As a macroscopic feature, long-range dependence can be mathematically studied using certain scaling limit theorems. Using such limit results, two different scaling regimes for Internet traffic models have been identified earlier. In one of these regimes traffic at large scales can be approximated by long-range dependent Gaussian or stable processes, while in the other regime the rescaled traffic fluctuates according to stable ``memoryless'' processes with independent increments. In Paper I a similar limit result is proved for a third scaling scheme, emerging as an intermediate case of the other two. The limit process here turns out to be a non-Gaussian and non-stable process with long-range dependence. In Paper II we derive a representation for the latter limit process as a stochastic integral of a deterministic function with respect to a certain compensated Poisson random measure. This representation enables us to study some further properties of the process. In particular, we prove that the process at small scales behaves like a Gaussian process with long-range dependence, while at large scales it is close to a stable process with independent increments. Hence, the process can be regarded as a link between these two processes of completely different nature. In Paper III we construct a class of processes locally behaving as Gaussian and globally as stable processes and including the limit process obtained in Paper I. These processes can be chosen to be long-range dependent and are potentially suitable as models in applications with distinct local and global behaviour. They are defined using stochastic integrals with respect to the same compensated Poisson random measure as used in Paper II.