Server farms are popular architectures for computing infrastructures such as supercomputing centers, data centers and web server farms. As server farms become larger and their workloads more complex, designing efficient policies for managing the resources in server farms via trial-and error becomes intractable. In this thesis, we employ stochastic modeling and analysis techniques to understand the performance of such complex systems and to guide design of policies to optimize the performance. There is a rich literature on applying stochastic modeling to diverse application areas such as telecommunication networks, inventory management, production systems, and call centers, but there are numerous disconnects between the workloads and architectures of these traditional applications of stochastic modeling and how compute server farms operate, necessitating new analytical tools. To cite a few: (i) Unlike call durations, supercomputing jobs and file sizes have high variance in service requirements and this critically affects the optimality and performance of scheduling policies. (ii) Most existing analysis of server farms focuses on the First-Come- First-Served (FCFS) scheduling discipline, while time sharing servers (e.g., web and database servers) are better modeled by the Processor- Sharing (PS) scheduling discipline. (in) Time sharing systems typically exhibit thrashing (resource contention) which limits the achievable concurrency level, but traditional models of time sharing systems ignore this fundamental phenomenon. (iv) Recently, minimizing energy consumption has become an important metric in managing server farms. State-of-the-art servers come with multiple knobs to control energy consumption, but traditional queueing models don’t take the metric of energy consumption into account. In this thesis we attempt to bridge some of these disconnects by bringing the stochastic modeling and analysis literature closer to the realities of today’s compute server farms. We introduce new queueing models for computing server farms, develop new stochastic analysis techniques to evaluate and understand these queueing models, and use the analysis to propose resource management algorithms to optimize their performance.

Wireless networks promise ubiquitous communication, and thus facilitate an array of applications that positively impact human life. At a fundamental level, these networks deal with compression and transmission of sources over channels. Thus, accomplishing this task efficiently is the primary challenge shared by these applications. In practice, sources include data and video while channels include interference and relay networks. Hence, effective source and channel aware resource allocation for these scenarios would result in a comprehensive solution applicable to real-world networks. This dissertation studies the problem of source and channel aware resource allocation in certain scenarios. A framework for network resource allocation that stems from rate-distortion theory is presented. Then, an optimal decomposition into an application-layer compression control, a transport-layer congestion control and a network-layer scheduling is obtained. After deducing insights into compression and congestion control, the scheduling problem is explored in two cross-layer scenarios. First, appropriate queue architecture for cooperative relay networks is presented, and throughput-optimality of network algorithms that do not assume channel-fading and input-queue distributions are established. Second, decentralized algorithms that perform rate allocation, which achieve the same overall throughput region as optimal centralized algorithms, are derived. In network optimization, an underlying throughput region is assumed. Hence, improving this throughput region is the next logical step. This dissertation addresses this problem in the context of three significant classes of interference networks. First, degraded networks that capture highly correlated channels are explored, and the exact sum capacity of these networks is established. Next, multiple antenna networks in the presence of channel uncertainty are considered. For these networks, robust optimization problems that result from linear precoding are investigated, and efficient iterative algorithms are derived. Last, multi-cell time-division-duplex systems are studied in the context of corrupted channel estimates, and an efficient linear precoding to manage interference is developed. / text

In this study the maximum entropy formalism [JAYN 57] is suggested as an alternative theory for general queueing systems of computer performance analysis. The motivation is to overcome some of the problems arising in this field and to extend the scope of the results derived in the context of Markovian queueing theory. For the M/G/l model a unique maximum entropy solution., satisfying locALl balance is derived independent of any assumptions about the service time distribution. However, it is shown that this solution is identical to the steady state solution of the underlying Marko-v process when the service time distribution is of the generalised exponential (CE) type. (The GE-type distribution is a mixture of an exponential term and a unit impulse function at the origin). For the G/M/1 the maximum entropy solution is identical in form to that of the underlying Markov process, but a GE-type distribution still produces the maximum overall similar distributions. For the GIG11 model there are three main achievements: first, the spectral methods are extended to give exaft formulae for the average number of customers in the system for any G/G/l with rational Laplace transform. Previously, these results are obtainable only through simulation and approximation methods. (ii) secondly, a maximum entropy model is developed and used to obtain unique solutions for some types of the G/G/l. It is also discussed how these solutions can be related to the corresponding stochastic processes. (iii) the importance of the G/GE/l and the GE/GE/l for the analysis of general networks is discussed and some flow processes for these systems are characterised. For general queueing networks it is shown that the maximum entropy solution is a product of the maximum entropy solutions of the individual nodes. Accordingly, existing computational algorithms are extended to cover general networks with FCFS disciplines. Some implementations are suggested and a flow algorithm is derived. Finally, these results are iised to improve existing aggregation methods. In addition, the study includes a number of examples, comparisons, surveys, useful comments and conclusions.

Capacity pooling in production systems, in the form of production capacity or inventory pooling, has been extensively studied in the literature. While production capacity pooling has been proven to be beneficial, the impact of inventory pooling has been less significant. These results cannot be easily extended to repairable systems due to fundamental differences between repairable and production systems. For one thing, in repairable systems, the demand rate is a function of the number of operational machines, whereas it is exogenous and constant in production systems. In this Thesis, to serve different fleets of machines possibly at different locations, we study whether repair shop pooling is more cost effective than having dedicated on-site repair shops for each fleet. In the first model, we consider transportation delays and related costs, which have been traditionally ignored in the literature. We include on-site spare-part inventories that operate according to a continuous-review base-stock policy. Our numerical findings indicate that when transportation costs are reasonable, repair shop pooling is a better alternative. Next, we model a pooled repair shop that fixes failed components from different k-out-of-n:G systems. We permit a shared spare parts inventory serving all systems and/or reserved spare parts inventories for each system; we call this a hybrid model. The destination for a repaired component can be chosen either on a first-come-first-served basis or by following a static priority rule. Our findings show that both hybrid policies are more cost effective than having separate repair shops and inventories for each system. We propose implementing the multilevel rationing (MR) policy in systems with shared inventory. The MR policy prioritizes classes, and stops serving a class from inventory if the inventory level is below the inventory threshold identified for that class. When there is no inventory, the repaired component is sent to the highest priority class among those with down machines. To approximate the cost of the MR policy, we study an M/G/1//N queueing system serving multiple classes of customers with an unreliable server. Our numerical findings indicate that the MR policy performs as well as the epsilon-optimal policy and outperforms the hybrid policies.

Capacity pooling in production systems, in the form of production capacity or inventory pooling, has been extensively studied in the literature. While production capacity pooling has been proven to be beneficial, the impact of inventory pooling has been less significant. These results cannot be easily extended to repairable systems due to fundamental differences between repairable and production systems. For one thing, in repairable systems, the demand rate is a function of the number of operational machines, whereas it is exogenous and constant in production systems. In this Thesis, to serve different fleets of machines possibly at different locations, we study whether repair shop pooling is more cost effective than having dedicated on-site repair shops for each fleet. In the first model, we consider transportation delays and related costs, which have been traditionally ignored in the literature. We include on-site spare-part inventories that operate according to a continuous-review base-stock policy. Our numerical findings indicate that when transportation costs are reasonable, repair shop pooling is a better alternative. Next, we model a pooled repair shop that fixes failed components from different k-out-of-n:G systems. We permit a shared spare parts inventory serving all systems and/or reserved spare parts inventories for each system; we call this a hybrid model. The destination for a repaired component can be chosen either on a first-come-first-served basis or by following a static priority rule. Our findings show that both hybrid policies are more cost effective than having separate repair shops and inventories for each system. We propose implementing the multilevel rationing (MR) policy in systems with shared inventory. The MR policy prioritizes classes, and stops serving a class from inventory if the inventory level is below the inventory threshold identified for that class. When there is no inventory, the repaired component is sent to the highest priority class among those with down machines. To approximate the cost of the MR policy, we study an M/G/1//N queueing system serving multiple classes of customers with an unreliable server. Our numerical findings indicate that the MR policy performs as well as the epsilon-optimal policy and outperforms the hybrid policies.

The advances of high-throughput technologies, such as next-generation sequencing and microarrays, have rapidly improved the accessibility of molecular profiles in tumor samples. However, due to the immaturity of relevant theories, analyzing these data and systematically understanding the underlying mechanisms causing diseases, which are essential in the development of therapeutic applications, remain challenging. This dissertation attempts to clarify the effects of DNA copy number alterations (CNAs), which are known to be common mutations in genetic diseases, on steady- state gene expression values, time-course expression activities, and the effectiveness of targeted therapy. Assuming DNA copies operate as independent subsystems producing gene transcripts, queueing theory is applied to model the stochastic processes representing the arrival of transcription factors (TFs) and the departure of mRNA. The copy-number-gene-expression relationships are shown to be generally nonlinear. Based on the mRNA production rates of two transcription models, one corresponding to an unlimited state with prolific production and one corresponding to a restrictive state with limited production, the dynamic effects of CNAs on gene expression are analyzed. Simulations reveal that CNAs can alter the amplitudes of transcriptional bursting and transcriptional oscillation, suggesting the capability of CNAs to interfere with the regulatory signaling mechanism. With this finding, a string-structured Bayesian network that models a signaling pathway and incorporates the interference due to CNAs is proposed. Using mathematical induction, the upstream and downstream CNAs are found to have equal influence on drug effectiveness. Scoring functions for the detection of unfavorable CNAs in targeted therapy are consequently proposed. Rigorous experiments are keys to unraveling the etiology of genetic diseases such as cancer, and the proposed models can be applied to provide theory-supporting hypotheses for experimental design.

Although healthcare operations management has been an active and popular research direction over the past few years, there is a lack of formal quantitative models to analyze the ambulance o oad delay problem. O oad delays occur when an ambulance arriving at a hospital Emergency Department (ED) is forced to remain in front of the ED until a bed is available for the patient. Thus, the ambulance and the paramedic team are responsible to care for the patient until a bed becomes available inside the ED. But it is not as simple as waiting for a bed, as EDs also admit patients based on acuity levels. While the main cause of this problem is the lack of capacity to treat patients inside the EDs, Emergency Medical Services (EMS) coverage and availability are signi cantly a ected. In this thesis, we develop three network queueing models to analyze the o oad delay problem. In order to capture the main cause of those delays, we construct queueing network models that include both EMS and EDs. In addition, we consider patients arriving to the EDs by themselves (walk-in patients) since they consume ED capacity as well. In the rst model, ED capacity is modeled as the combination of bed, nurse, and doctor. If a patient with higher acuity level arrives to the ED, the current patient's service is interrupted. Thus, the service discipline at the EDs is preemptive resume. We also assume that the time the ambulance needs to reach the patient, upload him into the ambulance, and transfer him to the ED (transit time) is negligible. We develop e cient algorithms to construct the model Markov chain and solve for its steady state probability distribution using Matrix Analytic Methods. Moreover, we derive di erent performance measures to evaluate the system performance under di erent settings in terms of the number of beds at each ED, Length Of Stay (LOS) of patients at an ED, and the number of ambulances available to serve a region. Although capacity limitations and increasing demand are the main drivers for this problem, our computational analysis show that ambulance dispatching decisions have a substantial impact on the total o oad delays incurred. In the second model, the number of beds at each ED is used to model the service capacity. As a result of this modeling approach, the service discipline of patients is assumed to be nonpreemptive priority. We also assume that transit times of ambulances are negligible. To analyze the queueing network, we develop a novel algorithm to construct the system Markov chain by de ning a layer for each ED in a region. We combine the Markov chain layers based on the fact that regional EDs are only connected by the number of available ambulances to serve the region. Using Matrix Analytic Methods, we nd the limiting probabilities and use the results to derive di erent system performance measures. Since each ED's patients are included in the model simultaneously, we solve only for small instances with our current computational resources. In the third model, we decompose the regional network into multiple single EDs. We also assume that patients arriving by ambulances have higher nonpreemptive priority discipline over walk-in patients. Unlike the rst two models, we assume that transit times of ambulances are exponentially distributed. To analyze the decomposed queueing network performance, we construct a Markov chain and solve for its limiting probabilities using Matrix Analytic Methods. While the main objective for the rst two models is performance evaluation, in this model we optimize the steady state dispatching decisions for ambulance patients. To achieve this goal, we develop an approximation scheme for the expected o oad delays and expected waiting times of patients. Computational analysis conducted suggest that larger EDs should be loaded more heavily in order to keep the total o oad delays at minimal levels.

Thesis (M. Sc.)--Carleton University, 2008. / Includes bibliographical references (p. 81-83). Also available in electronic format on the Internet.

The goal of this thesis was to understand Queueing Theory and use it for analysis of queueing system of hypermarket company PZV. Theoretical part is consists of basic iformations which is necessary to know for application of queueing theory. First chapter is about random variables, random event, random proces, stochastic and Poisson processes and Markov chains. Then was possible to describe queueing theory basic characteristics, parameters, analy-sis, classification and basic models. In the practical part was from the beginning analyze development of custo-mers going through cashier zone. On the base of analysis were customers divided into 4 groups. For these groups were counted characteristics and parameters, next was analyzed the system, but because data were too inaccurate, it was necessary to use different values for the groups and to count analysis for these values. The last step was to find number of cashiers to make system optimal. The result, it was 4 ca-shiers, was unfortunately not accurate. For better results it would be necessary to have more detail data.

Orientadores: Edson Luiz Ursini, Paulo Sérgio Martins Pedro / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Tecnologia / Made available in DSpace on 2018-08-24T15:16:37Z (GMT). No. of bitstreams: 1 Santos_VlademirFazio_M.pdf: 4330659 bytes, checksum: a576d09102c26740d57f44a9686c5b76 (MD5) Previous issue date: 2014 / Resumo: Iniciativas industriais para finalizar a produção de multi-commodities embaladas sem formar estoque requerem inovação tecnológica constante. Atuam sincronizadamente com o múltiplo carregamento simultâneo diretamente em caminhões. Para isso desenvolvemos um modelo de simulação por eventos discretos e apresentamos seu modelo analítico de tráfego validado com Redes de Filas de Jackson e pela Lei de Conservação de Little. Descrevemos os limites do intervalo de variação de tempos máximos e médios de permanência de multi-commodities em sistemas de tempo real para três servidores paralelos. Esse sistema opera com mudanças dinâmicas de diferentes políticas de escalonamento. Um resultado é a confirmação do compromisso entre tempos máximos e médios independentemente de intensidade de tráfego e de políticas de escalonamento a que o modelo seja submetido. Outro é a identificação de uma faixa de relativa estabilidade operacional fora de regiões críticas. Assim, contribuímos com os princípios de um método que pode ser adotado como apoio às decisões de planejamento em ambientes industriais complexos submetidos a filas em tempo real / Abstract: The industrial initiatives for the production finalization of packed multi-commodities without forming stock require constant technological innovation. They operate a synchronous process to simultaneous multi-loading straightly into trucks. Regarding to this we developed a discrete event simulation model and present its traffic analytical model validated with the theory of Jackson Queueing Networks and the Little's Conservation Law. We describe the limits for the range of multi-commodities throuput-times and maximum waiting time in real-time systems with three parallel servers. This system operates with dynamical changes of different scheduling policies. A reached result is the confirmation of the average and maximum times mutual commitment despite of traffic intensity and scheduling policies that the model is submitted to. Another is the identification of a range of relative operational stability out of critical regions. As a contribution we offer the principles of a method that can be used to planning decision support in complex industrial environments subject to real-time queues / Mestrado / Tecnologia e Inovação / Mestre em Tecnologia