A distributed virtual environment (DVE) is a shared virtual environment where multiple users at their workstations interact with each other. Some of these systems may support a large number of users, e. g. , massive multi-player online games, and these users may be geographically distributed. An important performance measure in a DVE system is the delay for an update of a user's state (e. g. , his position in the virtual environment) to arrive at the workstations of those users who are affected by the update. This update delay often has a stringent requirement (e. g. , less than 100 ms) in order to ensure interactivity among users. <br /><br /> In designing a DVE system, an important issue is how well the system scales as the number of users increases. In terms of scalability, a promising system architecture is a two-level hierarchical architecture. At the lower level, multiple service facilities (or basic systems) are deployed; each basic system interacts with its assigned users. At the higher level, the various basic systems ensure that their copies of the virtual environment are as consistent as possible. Although this architecture is believed to have good properties with respect to scalability, not much is known about its performance characteristics. <br /><br /> This thesis is concerned with the performance characteristics of the two-level hierarchical architecture. We first investigate the issue of scalability. We obtain analytic results on the workload experienced by the various basic systems as a function of the number of users. Our results provide valuable insights into the scalability of the architecture. We also propose a novel technique to achieve weak consistency among copies of the virtual environment at the various basic systems. Simulation results on the consistency/scalability tradeoff are presented. <br /><br /> We next study the update delay in the two-level hierarchical architecture. The update delay has two main components, namely the delay at the basic system (or server delay) and the network delay. For the server delay, we use a network of queues model where each basic system may have one or more processors. We develop an approximation method to obtain results for the distribution of server delay. Comparisons with simulation show that our approximation method yields accurate results. We also measure the time to process an update on an existing online game server. Our approximate results are then used to characterize the 95th-percentile of the server delay, using the measurement data as input. <br /><br /> As to the network delay, we develop a general network model and obtain analytic results for the network delay distribution. Numerical examples are presented to show the conditions under which geographical distribution of basic systems will lead to an improvement in the network delay. We also develop an efficient heuristic algorithm that can be used to determine the best locations for the basic systems in a network.

A distributed virtual environment (DVE) is a shared virtual environment where multiple users at their workstations interact with each other. Some of these systems may support a large number of users, e. g. , massive multi-player online games, and these users may be geographically distributed. An important performance measure in a DVE system is the delay for an update of a user's state (e. g. , his position in the virtual environment) to arrive at the workstations of those users who are affected by the update. This update delay often has a stringent requirement (e. g. , less than 100 ms) in order to ensure interactivity among users. <br /><br /> In designing a DVE system, an important issue is how well the system scales as the number of users increases. In terms of scalability, a promising system architecture is a two-level hierarchical architecture. At the lower level, multiple service facilities (or basic systems) are deployed; each basic system interacts with its assigned users. At the higher level, the various basic systems ensure that their copies of the virtual environment are as consistent as possible. Although this architecture is believed to have good properties with respect to scalability, not much is known about its performance characteristics. <br /><br /> This thesis is concerned with the performance characteristics of the two-level hierarchical architecture. We first investigate the issue of scalability. We obtain analytic results on the workload experienced by the various basic systems as a function of the number of users. Our results provide valuable insights into the scalability of the architecture. We also propose a novel technique to achieve weak consistency among copies of the virtual environment at the various basic systems. Simulation results on the consistency/scalability tradeoff are presented. <br /><br /> We next study the update delay in the two-level hierarchical architecture. The update delay has two main components, namely the delay at the basic system (or server delay) and the network delay. For the server delay, we use a network of queues model where each basic system may have one or more processors. We develop an approximation method to obtain results for the distribution of server delay. Comparisons with simulation show that our approximation method yields accurate results. We also measure the time to process an update on an existing online game server. Our approximate results are then used to characterize the 95th-percentile of the server delay, using the measurement data as input. <br /><br /> As to the network delay, we develop a general network model and obtain analytic results for the network delay distribution. Numerical examples are presented to show the conditions under which geographical distribution of basic systems will lead to an improvement in the network delay. We also develop an efficient heuristic algorithm that can be used to determine the best locations for the basic systems in a network.

Σκοπός της παρούσας διπλωματικής εργασίας είναι η μελέτη της θεωρίας της Near Complete Decomposability (NCD) και η εφαρμογή της στην ανάλυση της απόδοσης ενός υπολογιστικού συστήματος, του οποίου η μοντελοποίηση με παραδοσιακές τεχνικές οδηγεί σε απαγορευτικά μεγάλο χώρο κατάστασης. Αρχικά, παραθέτουμε τα βασικά σημεία της θεωρίας όπως αυτή θεμελιώνεται μαθηματικά από τον Courtois στην κλασική του μονογραφία (Courtois, 1977), ενώ στη συνέχεια προβαίνουμε στη μοντελοποίηση ενός υποθετικού σταθμού εργασίας κάποιου πολυεπεξεργαστικού συστήματος, στο οποίο εκτελούνται ανά πάσα στιγμή το πολύ Κ έργα. Ο σταθμός εργασίας που μελετάμε διαθέτει buffer πεπερασμένου μεγέθους και είναι επιφορτισμένος με τη συγκέντρωση και το συνδυασμό των επιμέρους υποέργων κάθε έργου και την αποθήκευση του στη μνήμη. Οι κλασικές τεχνικές μοντελοποίησης του buffer οδηγούν σε ένα μοντέλο με πολύ μεγάλο χώρο κατάστασης. Ωστόσο εμείς μοντελοποιούμε μία συναθροιστική εκδοχή του αρχικού μοντέλου, η οποία υπό αρκετά ρεαλιστικές συνθήκες χαίρει της NCD ιδιότητας. Την ιδιότητα αυτή του μοντέλου μας τη δικαιολογούμε τόσο διαισθητικά, όσο και μαθηματικά. Επίσης, επιβεβαιώνουμε πως το NCD μοντέλο πετυχαίνει υψηλής ποιότητας εκτίμηση των πιθανοτήτων μόνιμης κατάστασης και μίας σειράς άλλων χρήσιμων μετρικών, με σημαντικά μικρότερο υπολογιστικό κόστος σε σχέση με το αρχικό μοντέλο, εκτελώντας μία σειρά μετρήσεων στο περιβάλλον Matlab. Παράλληλα, η αξιοποίηση του NCD μοντέλου αυξάνει σημαντικά την ικανότητά μας να ερμηνεύσουμε τη δυναμική συμπεριφορά του συστήματος καθώς αυτό οδεύει προς μια κατάσταση στατιστικής ισορροπίας. Τέλος, επιχειρούμε μία σειρά από “educated guesses” για πιθανές κλάσεις συστημάτων τα οποία θα μπορούσαν να αναλυθούν με μεθοδολογία αντίστοιχη με αυτήν που ακολουθήσαμε εμείς στο παρόν κείμενο. / The purpose of this diploma dissertation is, on one hand the brief study of the theory of Near Complete Decomposability (NCD), and on the other hand the application of NCD in the analysis of a system, the modeling of which leads to a prohibitively large state space. First, we point out the fundamental mathematical principles of NCD as established by Courtois in his classic monograph (Courtois, 1977). Then, we proceed to the modeling of a hypothetical service station (R) of a multiprocessing computer system, which executes at most K jobs simultaneously. R has a finite buffer and its duty is to combine the arriving tasks into a single job and store it to memory. The usual modeling techniques applied to this “task buffer”, lead to a model with extremely large state space. So, we construct a lumped model instead, which enjoys the property of NCD. We prove this, using intuitive arguments as well as mathematical ones. Then, we confirm that the NCD model achieves a reliable estimation of the steady state probability vector and other important metrics, with significantly reduced computational complexity in comparison with the initial model. Furthermore, the exploitation of the NCD model increases significantly our ability to understand the dynamics of our system and to interpret aspects of its transient behavior towards statistical equilibrium. Finally, we make a number of “educated guesses” about possible classes of systems that could be analyzed using the same kind of techniques we used in this dissertation.

Orientador: Marina Vachkovskaia / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-21T12:11:37Z (GMT). No. of bitstreams: 1 Oliveira_HeloisaMariade_D.pdf: 1371327 bytes, checksum: 1913d92f9ff81812cfbf5b4fab73215d (MD5) Previous issue date: 2012 / Resumo: Considere as redes de filas com N servidores e K tipos de trabalho. Suponha que os tipos de trabalho i chegam independentemente à rede de acordo com o processo de Poisson com taxa...Observação: O resumo, na íntegra, poderá ser visualizado no texto completo da tese digital / Abstract: Consider a queueing network with N servers and K types of jobs (or customer classes). The types of jobs i, i = 1; ¿ ;K, arrive at the system accordingly to independent Poisson process with rate...Note: The complete abstract is available with the full electronic document / Doutorado / Estatistica / Doutora em Estatística

The Internet has been more and more intensively used in recent years. Although network infrastructure has been regularly upgraded, and the ability to manage heavy traffic greatly increased, especially on the core networks, congestion never ceases to appear, as the amount of traffic that flow on the Internet seems to be increasing at an even faster rate. Thus, congestion control mechanisms play a vital role in the functioning of the Internet. Active Queue Management (AQM) is a popular type of congestion control mechanism that is implemented on gateways (most notably routers), which can predict and avoid the congestion before it happens. When properly configured, AQMs can effectively reduce the congestion, and alleviate some of the problems such as global synchronisation and unfairness to bursty traffic. However, there are still many problems regarding AQMs. Most of the AQM schemes are quite sensitive to their parameters setting, and these parameters may be heavily dependent on the network traffic profile, which the administrator may not have intensive knowledge of, and is likely to change over time. When poorly configured, many AQMs perform no better than the basic drop-tail queue. There is currently no effective method to compare the performance of these AQM algorithms, caused by the parameter configuration problem. In this research, the aim is to propose a new analytical model, which mainly uses discrete-time queueing theory. A novel transient modification to the conventional equilibrium-based method is proposed, and it is utilised to further develop a dynamic interactive model of responsive traffic and bottleneck queues. Using step-by-step analysis, it represents the bursty traffic and oscillating queue length behaviour in practical network more accurately. It also provides an effective way of predicting the behaviour of a TCP-AQM system, allowing easier parameter optimisation for AQM schemes. Numerical solution using MATLAB and software simulation using NS-2 are used to extensively validate the proposed models, theories and conclusions.

(i) The thesis sets out to address the problematic phenomenon of Systems of Congestion via Basic Queueing Theory. The theory, and its application in practice, appears to be a field of study which is the common domain of “theorists” and “practitioners”. (ii) This professional dichotomy has come about due to diverging interests in that one group is mainly interested in the purity of mathematical modelling, and the other group is motivated to use modelling, which conveniently employs applications oriented solutions. (iii) The schism between the groups has been accentuated by the “practitioners” who in addition to having an interest in steady state system behaviour make use of methods of modelling of the transient operation of complex Systems of Congestion. (iv) At the outset the thesis demonstrates how closed form solutions are obtained for steady state and transient state operation of a selection of Systems of Congestion. The attendant mathematical derivations are elegant and intricate. (v) Having revealed the limited utility of closed-form solutions the thesis proceeds to investigate the feasibility of using dynamical systems theory to study the transient behaviour of complex Systems of Congestion. (vi) The creation of Chaos Theory in recent decades suggests that it may be employed as a useful tool in analysing Systems of Congestion. Iterative Chaos Theory methods of orbit generation for complete Systems of Congestion are therefore examined. The use of such orbit generation methods is found to be satisfactory for simple Systems of Congestion. More than a perfunctory knowledge of chaos mapping is however required. The simplicity of modelling is emphasized. (vii) Based on the results of benchmarking the creation of dynamic system orbits against an existing simulation method, the research advances to modelling of the transient operation of complex systems. Once again the iterative method of orbit generation displays the ease of modelling while simultaneously unfolding system dynamics graphically. (viii) One may hopefully contend that a tool of eminent utility has been developed to aid practitioners in studying and optimizing Systems of Congestion. / Thesis (PhD (Industrial Engineering))--University of Pretoria, 2006. / Industrial and Systems Engineering / Unrestricted

No description available.

The objective of this master thesis is to optimize a number of service desk operators in Atos IT Solutions and Services s.r.o. The thesis introduces a general and ITIL methodology definition of the service desk. The practical analysis section covers data mining in order to carry out an analysis and propose measures leading to optimal utilization of service desk employees. The method applied in the thesis allows a creation of service desk services demand predictions for any given period of time.

La génération aléatoire d'objets combinatoires est un problème qui se pose dans de nombreux domaines de recherche (réseaux de communications, physique statistique, informatique théorique, combinatoire, etc.). Couramment, la distribution des échantillons est définie comme la distribution stationnaire d'une chaîne de Markov ergodique. En 1996, Propp et Wilson ont proposé un algorithme permettant l'échantillonnage sans biais de la distribution stationnaire. Ce dernier appelé aussi algorithme de simulation parfaite, requiert la simulation en parallèle de tous les états possibles de la chaîne. Plusieurs stratégies ont été mises en œuvre afin de ne pas avoir à simuler toutes les trajectoires. Elles sont intrinsèquement liées à la structure de la chaîne considérée et reposent essentiellement sur la propriété de monotonie, la construction de processus bornants qui exploitent la structure de treillis de l'espace d'états ou le caractère local des transitions. Dans le domaine des réseaux de communications, on s'intéresse aux performances des réseaux de files d'attente. Ces derniers se distinguent en deux groupes : ceux dont la distribution stationnaire possède une forme produit qui est facile à évaluer par le calcul et les autres. Pour ce dernier groupe, on utilise la génération aléatoire pour l'évaluation de performances. De par la structure des chaînes qui leurs sont associées, les réseaux ouverts de files d'attente se prêtent bien à la simulation via l'algorithme de simulation parfaite mais pas les réseaux fermés. La difficulté réside dans la taille de l'espace des états qui est exponentielle en le nombre de files à laquelle s'ajoute une contrainte globale à savoir le nombre constant de clients. La contribution principale de cette thèse est une nouvelle structure de données appelée diagramme. Cette structure est inspirée de la programmation dynamique et introduit une nouvelle technique de construction de processus bornant. La première partie du manuscrit est consacrée à la mise en œuvre de l'algorithme de Propp et Wilson pour des réseaux fermés n'étant pas nécessairement à forme produit. La représentation des états par un diagramme et l'opération de transition pour le processus bornant a dès lors une complexité polynomiale en le nombre de files et de clients. Cette technique est ensuite étendue aux réseaux fermés multiclasses ainsi qu'aux réseaux possédant des synchronisations. Une spécification des ensembles d'objets pouvant être représentés par un diagramme ainsi que des algorithmes agissant sur cette structure de données sont également proposés dans cette thèse. La méthode de Botzmann est une autre technique de simulation sans biais. Basée sur la combinatoire analytique, elle permet l'échantillonnage uniforme d'objets appartenant à une même classe combinatoire. Elle est employée dans la seconde partie de cette thèse afin d'échantillonner la distribution stationnaire de réseaux fermés à forme produit et pour la génération des multi-ensembles de taille fixe. Dans ce cadre, les diagrammes sont une nouvelle fois mis à profit. Enfin, la troisième partie présente les logiciels découlant des travaux présentés tout au long de ce travail, et qui implémentent les diagrammes et mettent en œuvre la simulation parfaite de réseaux fermés de files d'attente. / Random generation of combinatorial objects is an important problem in many fields of research (communications networks, theoretical computing, combinatorics, statistical physics, ...). This often requires sampling the stationary distribution of an ergodic Markov chain. In 1996, Propp and Wilson introduced an algorithm to produce unbiased samples of the stationary distribution, also called a perfect sampling algorithm. It requires parallel simulation of all possible states of the chain. To avoid simulating all the trajectories, several strategies have been implemented. But they are related to the structure of the chain and require a monotonicity property, or a construction of a bounding chain that exploits the lattice structure of the state space or the local character of the transitions.In the field of communications networks, attention is paid to the performance of queueing networks, that can be distinguished into two groups: the networks that have a product form stationary distribution which is easy to compute. Random generation can be used for the others. Perfect sampling algorithms can be used for open queueing networks, thanks to the lattice structure of their state space. Unfortunately, that is not the case for closed queueing networks, due to the size of the state space which is exponential in the number of queues and a global constraint (a constant number of customers). The main contribution of this thesis is a new data structure called a diagram. It is inspired by dynamic programming and allows a new technique of construction of bounding processes. The first part of the manuscript is devoted to the implementation of the Propp and Wilson algorithm for closed queueing networks. The representation of a set of states by a diagram and the transition operation for the bounding process has a polynomial complexity in the number of queues and customers. This technique is extended to closed multi-class networks and to networks with synchronizations. Specification of sets of objects that can be represented by a diagram and generic algorithms that use this data structure are proposed in this manuscript. The Boltzmann method is another unbiased sampling technique. It is based on analytical combinatorics and produces uniform samples from objects that belong to the same combinatorial class. It is used in the second part of this thesis in order to sample the stationary distribution of closed networks with product form and for the generation of multisets of fixed cardinality. Diagrams are used again in this context. Finally, the third part presents the software produced during this thesis, implementing diagrams and perfect simulation of closed queueing networks.

Hospital systems in the United States are facing a dilemma regarding capacity management in the emergency department (ED) and the inpatient care setting. The average wait time in EDs across the United States exceeds 98 minutes, which is also the point at which patients begin to abandon healthcare treatment. The purpose of this quantitative study was to examine the use of queueing theory in capacity management on length-of-stay (LOS) rates, left-without-being-seen (LWBS) rates, and boarding rates in the ED and inpatient setting. The boarding rates represent the rate in which patients were roomed in the ED but required inpatient care. This study assessed the relationships between capacity management using queueing theory and a reduction in the aforementioned rates compared to traditional processes across systems within the continental United States. A linear regression analysis with a confidence interval 95% paired with an independent sample t test was used to analyze the secondary datasets. A sample size of approximately 33,000 patients was tested in the areas of LOS, LWBS, and boarding. The results of the analysis determined that access was improved in the ED and inpatient setting when queueing theory was deployed within the hospital system compared to traditional processes for managing capacity within the system. Queuing theory used for capacity management resulted in lower LOS, LWBS, and boarding rates. The implications of this study for positive social change include the opportunity to provide greater access to care for the population as a whole, and better health outcomes for the promotion of population health.