The aim of this thesis is to first give a brief review of waiting line problems which often is a subject related to queueing theory. Simple counting processes such as the Poisson process and the duration of service time of each customer being exponentially distributed are often taught in a undergraduate or graduate stochastic process course. In this thesis, we will continue discussing such waiting line problems with priority assignment on each customer. This type of queueing processes are called priority queueing models. Patients requiring ER service are triaged and the order of providing service to patients more than often reflects early symptoms and complaints than final diagnoses. Triage systems used in hospitals vary from country to country and region to region. However, the goal of using a triage system is to ensure that the sickest patients are seen first. Such wait line system is much comparable to a priority queueing system in our study. The finite Markov chain imbedding technique is very effective in obtaining the waiting time distribution of runs and patterns. Applying this technique, we are able to obtain the probability distribution of customer wait time of priority queues. The results of this research can be applied directly when studying patient wait time of emergency medical service. Lengthy ER wait time issue often is studied from the view of limited spacing and complications in hospital administration and allocation of resources. In this thesis, we would like to study priority queueing systems by mathematical and probabilistic modeling.

This thesis is devoted to the investigation of prioritization mechanism for web based anomaly detection. We propose a hardware realization of parallel binary heap as an application of web based anomaly prioritization. The heap is implemented in pipelined fashion in FPGA platform. The propose design takes O(1) time for all operations by ensuring minimum waiting time between two consecutive operations. We present the various design issues and hardware complexity. We explicitly analyze the design trade-offs of the proposed priority queue implementations.

The aim of this thesis is to first give a brief review of waiting line problems which often is a subject related to queueing theory. Simple counting processes such as the Poisson process and the duration of service time of each customer being exponentially distributed are often taught in a undergraduate or graduate stochastic process course. In this thesis, we will continue discussing such waiting line problems with priority assignment on each customer. This type of queueing processes are called priority queueing models. Patients requiring ER service are triaged and the order of providing service to patients more than often reflects early symptoms and complaints than final diagnoses. Triage systems used in hospitals vary from country to country and region to region. However, the goal of using a triage system is to ensure that the sickest patients are seen first. Such wait line system is much comparable to a priority queueing system in our study. The finite Markov chain imbedding technique is very effective in obtaining the waiting time distribution of runs and patterns. Applying this technique, we are able to obtain the probability distribution of customer wait time of priority queues. The results of this research can be applied directly when studying patient wait time of emergency medical service. Lengthy ER wait time issue often is studied from the view of limited spacing and complications in hospital administration and allocation of resources. In this thesis, we would like to study priority queueing systems by mathematical and probabilistic modeling.

This thesis investigates various aspects of bandwidth allocation and scheduling in the Medium Access Control (MAC) layer of IEEE 802.16 systems. We highlight the important aspects of designing a scheduler and describe the scheduler design problem from a general perspective. That is, we provide a scheduler design framework driven by a set of objectives defined for the systems. In addition, we include Subscriber Station differentiation into our scheduler design. This approach is comprehensive, as it covers the requirements of both the network provider and the end users. In developing the framework, we discuss the importance of achieving customer satisfaction. This leads to an interesting objective that maximises the number of satisfied customers, rather than network centric objectives, such as fairness. We contend that providing fairness to customers does not necessarily achieve the best outcome for customer satisfaction and artificially limits the choices available to service providers. In order to maximise the number of satisfied customers, we analyse in detail the Dual-Queue (DQ) scheduling discipline proposed by Hayes et al. [2]. The DQ algorithms of Hayes’ work are focused on wireline networks, and are not directly deployable in an 802.16 environment, as we discuss in this thesis. We propose a modified DQ implementation for 802.16 systems to handle real-time services. In 802.16 systems, there are two scheduling processes that we need to consider: Downlink (DL) scheduling for data transmission from the Base Station to the Subscriber Stations and Uplink (UL) scheduling for data transmission from the Subscriber Stations to the Base Stations. We investigate the DL and UL implementations separately because the UL scheduling process is more complicated due to the fundamentally distributed nature of the problem. We demonstrate that our proposed approach is able to operate effectively in an 802.16 system. We then compare the performance of our proposed DL and UL Dual- Queue schedulers to a Weighted Fair Queue scheduler in noisy environments, where re-transmissions are required. In addition, we also compare our proposed schedulers to an enhanced Weighted Fair Queue scheduler with an Explicit Packet Dropping mechanism. Furthermore, we show that our Dual-Queue system can handle mixed traffic profiles, such as video and voice. Having proposed a DQ implementation that maximises the number of satisfied customers, we investigate alternative objectives that the DQ scheduler may try to achieve. We find that our proposed DQ implementation may fail to achieve these alternative objectives, and hence, we remedy this shortfall by proposing the Priority- Based Dual-Queue scheduler, which is made up of multiple DQs differentiated by the priority classes of connections. That is, each priority class is handled in a separate DQ. The Priority-Based Dual-Queue scheduler ensures connections that belong to the highest priority class are served ahead of connections that belong to lower priority classes at all times, even when there are changes in the priority class of connections in the system. Lastly, we investigate the benefits of carrying out the DQ scheduling for both the DL and UL of an 802.16 network jointly. We first investigate a scenario where the network consists of only one-directional connections. We propose a joint scheme that is able to maximise the number of satisfied one-directional connections in the network. We then extend our investigation to another scenario where the network consists of bi-directional sessions, such as Voice over IP and video conferencing. In this case, we propose two joint schemes, which are able to maximise the number of satisfied bi-directional sessions. / http://proxy.library.adelaide.edu.au/login?url= http://library.adelaide.edu.au/cgi-bin/Pwebrecon.cgi?BBID=1363601 / Thesis (Ph.D.) -- University of Adelaide, School of Electrical and Electronic Engineering, 2009

The diploma thesis focuses on the issue of controll network traffic in wireless link. The requirements specification is suggested solution which is implemented and tested in laboratory conditions. The verification is carried out in the WAN network of TS-Hydro, s.r.o. The results are evaluated in the discussion.

In this thesis, our objective is to improve the energy efficiency and load balance for wireless networks. We first study the relationships between the base station (BS) on/off operation and traffic distribution. A cooperative power saving method called clustering BS-off (CBSO) scheme is proposed. Instead of adopting a unified and consistent BS-off scheme in the whole network, the proposed centralized and distributed CBSO schemes can adaptively group BSs in several clusters based on the traffic fluctuations with space and time. Second, to further improve the network load balance and energy efficiency in distributed manner, we propose a power efficient self-organized virtual small networking (VSN) protocol. A heuristic firefly algorithm is applied to arrange the BSs' operation in small groups based on the traffic level. By jointly considering the load balance, the effectiveness of the proposed algorithm is demonstrated based on the average and min-max traffic levels of BSs' groups. Finally, the importance of detailed BS operation between active and sleep modes is considered. The operating procedure of femtocell base station, i.e., HeNB, is modeled as an MAP/PH/1/k queueing system. Such queueing analysis particularly focuses on the HeNB vacation process with user priorities. The HeNB's power on/off scheme is modeled as alternative service and vacation periods. The hybrid access is regarded as high and low priority users in the queuing system. We further propose the adaptive service rate and vacation length (ASV) method, so that the HeNB can work in a more energy-efficient way while satisfying QoS requirements such as blocking probability and users waiting time. Simulation results show the effectiveness of the proposed strategies and the overall network energy efficiency can be improved significantly. / October 2016

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.

This work aims to create a library in C++, which implements various variants of the pending event set, which is used in discrete simulations. The library includes nine different implementations of the pending event set, accessible through a single interface. This interface is designed to make it easy to extend the library with additional implementations. In addition to the library itself, the work also describes the design of the test application and evaluates the time complexity of individual implementations.

Two-periodic random walks are models for the one-dimensional motion of particles in which the jump probabilities depend on the parity of the currently occupied state. Such processes have interesting applications, for instance in chemical physics where they arise as embedded random walk of a special queueing problem. In this paper we discuss in some detail first passage time problems of two-periodic walks, the distribution of their maximum and the transition functions when the motion of the particle is restricted by one or two absorbing boundaries. As particular applications we show how our results can be used to derive the distribution of the busy period of a chemical queue and give an analysis of a somewhat weird coin tossing game. / Series: Research Report Series / Department of Statistics and Mathematics