Consider a multi-priority, nonpreemptive, N-server Poisson arrival queueing system. The number of servers requested by an arrival has a known probability distribution. Service times are negative exponential. In order to save available servers for higher priority customers, arriving customers of each lower priority are deliberately queued whenever the number of servers busy equals or exceeds a given priority-dependent cutoff number. A queued priority i customer enters service the instant the number of servers busy is at most the respective cutoff number of servers minus the number of servers requested (by the customer) and all higher priority queues are empty. In other words the queueing discipline is in a sense HOL by priorities, FCFS within a priority. All servers requested by a customer start service simultaneously; service completion instants are independent. We derive the priority i waiting time distribution (in transform domain) and other system statistics.

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.

Vehicular Ad-Hoc Network (VANET)s are a key element of Intelligent Transport System (ITS)s. One of the challenges in VANETs is dealing with awareness and congestion due to the high amount of messages received from the vehicles in communication range. As VANETs are used in critical applications, congestion on the receiver side caused by the buffering of the packets is a safety hazard. In this thesis, we propose a stream-wise queuing system on the receiver side and show how it improves the timeliness of the messages received and main- tains the awareness of the system in a congestion situation.

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

There are several approaches for creating double-ended heaps from the single-ended heaps. We build on one of them, the leaf correspondence heap, to create a generic double ended heap scheme called L-correspondence heap. This will broaden the class of eligible base single-ended heaps (e.g. by Fibonacci heap, Rank-pairing heap) and make the operations Decrease and Increase possible. We show this approach on specific examples for three different single-ended base heaps and give time complexity bounds for all operations. Another result is that for these three examples, the expected amortized time for Decrease and Increase operations in the L-correspondence heap is bounded by a constant.

Differentiated-Service networks is designed for solving scalability problems through traffic aggregation. However, it can't guarantee end-to-end QoS of individual flow. In this thesis, we propose a Self-Adaptive Control Scheme for Differentiated-Service networks that can improve the throughput of individual flows dynamically. In this scheme, egress routers monitor the average throughput of individual flow, and send the Self-Adaptive Control Messages to ingress routers if need. The ingress router re-allocate network resources to improve throughput of high-priority flows depending on the Control Messages. We use NS-2 simulator to prove that our scheme that can improve throughput of high-priority flows dynamically, and suggest that a better time interval of Self-Adaptive control can be determined based on the queue sizes, packets arrival rate and departure rate. Finally, we use Random Early Detection (RED) queue instead of Drop-Tail queue to reduce unfairness of individual flows when there are congestion and insufficient network resources.

Network analysis in GIS is often related to finding solutions to transportation problems. In a GIS the real world is represented by either one of two spatial models, vector-based, or raster-based. Prefering raster or vector GIS is more a question of choice than of accuracy. A raster-based GIS model shows a better fit, when the problem is concerned with finding a path across terrain which does not have predefined paths. The approach of this study is to translate the scenario into a &lsquo / least-cost path&rsquo / graph with an associated cost function on the raster-based GIS layer. Sometimes, computation of shortest paths between different locations on a raster-based GIS has to be done in real-time. Therefore, knowing which shortest path algorithm runs fastest on real networks is needed. In order to meet this requirement, Dijsktra&rsquo / s algorithm with priority queue implementation is selected, because it reduces the time complexity of Dijsktra&rsquo / s algorithm from O(V2 log V) to O(E log V ). The run-time results of Dijsktra&rsquo / s algorithm, Dijsktra&rsquo / s algorithm with priority queue implementation and ArcMap Spatial Analyst Tool are compared for a number of raster GIS layers which have different number of nodes. Dijsktra&rsquo / s algorithm with priority queue implementation and Spatial Analyst tool of ArcMap show a linear relationship between node numbers and time, whereas Dijsktra&rsquo / s algorithm represents a quadratic relationship. Hence, when the number of nodes and edges in graph is increased, the run-time performance of the Dijsktra&rsquo / s algorithm decreases rapidly.

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.