In this thesis, we study different scheduling policies in service networks. In Chapter 2, we consider two service level (SL) measures in a two-server tandem queue system: the average sojourn time and the probability of long waits. We demonstrate that a family of Threshold Based Policies (TBP) can reduce the probability of long waits while maintaining sojourn times that are only slightly higher than those of a non-idling policy. In Chapter 3, we present a case study for improving the operations of a healthcare provider that has an open-shop queueing network. We propose an effective implementation of Dynamic Scheduling Policies (DSPs) and a generalized TBP to improve the SL in an open-shop queueing networks. Using a simulation model we demonstrate that an open-shop queueing network can be managed in a systematic fashion to deliver improved SL. In Chapter 4, we study the waiting time distribution of two different priority classes in an M/M/c queue with different service times. For the c=2 case, we provide closed form expression of the Generating Function (GF) of the number of low-priority jobs in the system, which can lead to the waiting time distribution. For c>2 case, we present an efficient numerical algorithm for deriving this GF. We discuss several insights gained from numerical results. Both Chapter 2 and 3 were supervised by Professors Opher Baron, Oded Berman, and Dmitry Krass. Chapter 4 was supervised by Professors Opher Baron and Alan Scheller-Wolf.

No description available.

Esta dissertação tem por objetivo apresentar a proposta de uma política de escalonamento para grids computacionais. Essa política, intitulada Dynamic Max-Min2x, é orientada ao escalonamento de aplicações cujas tarefas não realizam comunicação entre si e visa a redução do tempo de resposta dessas aplicações através da utilização de atribuição dinâmica de tarefas e replicação das mesmas. Experimentos, feitos através de simulação, mostram que o tempo médio de resposta de aplicações utilizando-se a Dynamic Max-Min2x é inferior ao de outras políticas da literatura. Análises dos resultados desses experimentos apontam que esse tempo tende a ser mais atrativo principalmente quando as tarefas necessitam de muito processamento e quando há grande variação de carga no sistema, caracteristicas comuns em grids computacionais. Além disso, esta dissertação apresenta a implementação de um framework utilizando-se o Globus Toolkit, onde é possível a inserção de políticas de escalonamento para a submissão inteligente de tarefas em um grid computacional. / This Master thesis proposes a new grid scheduling policy called Dynamic Max-Min2x. This policy focuses on applications in which tasks do not communicate among themsenves and targets a response time reduction of these applications through the use of dynamic task distribution and replication techniques. Experiments, done using simulations, have shown that the response time related to Dynamic Max-Min2x is smaller than others policies found in literature. Analysis of the results have demonstrated that this time tends to become more attractive when tasks do not need much processing power and when there is a great load variation in the system, characteristics frequently found in grids. Furthermore, this thesis presents the implementation of a framework using Globus Toolkit, which makes possible the new scheduling policies insertion to provide an intelligent submission tasks in a computational grid system.

Diversas políticas de escalonamento para aplicações paralelas voltadas a ambientes computacionais distribuídos têm sido propostas. Embora tais políticas apresentem bons resultados, elas são, geralmente, avaliadas em cenários específicos. Quando o cenário muda, com diferentes ambientes distribuídos e condições de carga, essas políticas podem ter seu desempenho deteriorado. Nesse contexto, este trabalho apresenta um estudo comparativo envolvendo dez políticas de escalonamento avaliadas em diferentes cenários. Cada uma das políticas foi submetida a uma combinação de quatro cargas de trabalho de ocupação da UCP e três variações da taxa de comunicação média entre os processos, utilizando a rede. Foram considerados ainda três sistemas distribuídos distintos: dois clusters, com diferentes quantidades de nós, e um grid computacional. Foi utilizada a simulação com ambientes próximos ao real e cargas de trabalho obtidas de modelos realísticos. Os resultados demonstraram que, embora as políticas sejam voltadas a ambientes computacionais paralelos e distribuídos, quando o cenário muda, o desempenho cai e a ordem de classificação entre as políticas se altera. Os resultados permitiram ainda demonstrar a necessidade de se considerar a comunicação entre os processos durante o escalonamento em grids computacionais. / Several scheduling policies for parallel applications directed to the distributed computational environments have been proposed. Although such policies present good results, they, generally, are evaluated in specific scenarios. When scenario change, by using different distributed environments and workload conditions, these policies can have its performance spoiled. In this context, this work presents a comparative study involving ten scheduling policies evaluated on different scenarios. Each policy was submitted to a combination of four CPU occupation workloads and three variations of interprocess average communication rates, using the network. Three different distributed systems had been yet considered: two clusters, with different amounts of nodes, and one grid computing. Simulation was used with environments near to the real and workloads obtained of realistic models. Although the policies are directed to parallel and distributed environments, the results have demonstrated that when scenario change, the performance falls and the ranking between the policies changes too. The results have still allowed to demonstrate the necessity of considering interprocess communication during the scheduling in a grid computing.

Heavy-tailed workload distributions are commonly experienced in many areas of distributed computing. Such workloads are highly variable, where a small number of very large tasks make up a large proportion of the workload, making the load very hard to distribute effectively. Traditional task assignment policies are ineffective under these conditions as they were formulated based on the assumption of an exponentially distributed workload. Size-based task assignment policies have been proposed to handle heavy-tailed workloads, but their applications are limited by their static nature and assumption of prior knowledge of a task's service requirement. This thesis analyses existing approaches to load distribution under heavy-tailed workloads, and presents a new generalised task assignment policy that significantly improves performance for many distributed applications, by intelligently addressing the negative effects on performance that highly variable workloads cause. Many problems associated with the modelling and optimisations of systems under highly variable workloads were then addressed by a novel technique that approximated these workloads with simpler mathematical representations, without losing any of their pertinent original properties. Finally, we obtain advance queuing metrics (such as the variance of key measurements like waiting time and slowdown that are difficult to obtain analytically) through rigorous simulation.

Diversas políticas de escalonamento para aplicações paralelas voltadas a ambientes computacionais distribuídos têm sido propostas. Embora tais políticas apresentem bons resultados, elas são, geralmente, avaliadas em cenários específicos. Quando o cenário muda, com diferentes ambientes distribuídos e condições de carga, essas políticas podem ter seu desempenho deteriorado. Nesse contexto, este trabalho apresenta um estudo comparativo envolvendo dez políticas de escalonamento avaliadas em diferentes cenários. Cada uma das políticas foi submetida a uma combinação de quatro cargas de trabalho de ocupação da UCP e três variações da taxa de comunicação média entre os processos, utilizando a rede. Foram considerados ainda três sistemas distribuídos distintos: dois clusters, com diferentes quantidades de nós, e um grid computacional. Foi utilizada a simulação com ambientes próximos ao real e cargas de trabalho obtidas de modelos realísticos. Os resultados demonstraram que, embora as políticas sejam voltadas a ambientes computacionais paralelos e distribuídos, quando o cenário muda, o desempenho cai e a ordem de classificação entre as políticas se altera. Os resultados permitiram ainda demonstrar a necessidade de se considerar a comunicação entre os processos durante o escalonamento em grids computacionais. / Several scheduling policies for parallel applications directed to the distributed computational environments have been proposed. Although such policies present good results, they, generally, are evaluated in specific scenarios. When scenario change, by using different distributed environments and workload conditions, these policies can have its performance spoiled. In this context, this work presents a comparative study involving ten scheduling policies evaluated on different scenarios. Each policy was submitted to a combination of four CPU occupation workloads and three variations of interprocess average communication rates, using the network. Three different distributed systems had been yet considered: two clusters, with different amounts of nodes, and one grid computing. Simulation was used with environments near to the real and workloads obtained of realistic models. Although the policies are directed to parallel and distributed environments, the results have demonstrated that when scenario change, the performance falls and the ranking between the policies changes too. The results have still allowed to demonstrate the necessity of considering interprocess communication during the scheduling in a grid computing.

Esta dissertação tem por objetivo apresentar a proposta de uma política de escalonamento para grids computacionais. Essa política, intitulada Dynamic Max-Min2x, é orientada ao escalonamento de aplicações cujas tarefas não realizam comunicação entre si e visa a redução do tempo de resposta dessas aplicações através da utilização de atribuição dinâmica de tarefas e replicação das mesmas. Experimentos, feitos através de simulação, mostram que o tempo médio de resposta de aplicações utilizando-se a Dynamic Max-Min2x é inferior ao de outras políticas da literatura. Análises dos resultados desses experimentos apontam que esse tempo tende a ser mais atrativo principalmente quando as tarefas necessitam de muito processamento e quando há grande variação de carga no sistema, caracteristicas comuns em grids computacionais. Além disso, esta dissertação apresenta a implementação de um framework utilizando-se o Globus Toolkit, onde é possível a inserção de políticas de escalonamento para a submissão inteligente de tarefas em um grid computacional. / This Master thesis proposes a new grid scheduling policy called Dynamic Max-Min2x. This policy focuses on applications in which tasks do not communicate among themsenves and targets a response time reduction of these applications through the use of dynamic task distribution and replication techniques. Experiments, done using simulations, have shown that the response time related to Dynamic Max-Min2x is smaller than others policies found in literature. Analysis of the results have demonstrated that this time tends to become more attractive when tasks do not need much processing power and when there is a great load variation in the system, characteristics frequently found in grids. Furthermore, this thesis presents the implementation of a framework using Globus Toolkit, which makes possible the new scheduling policies insertion to provide an intelligent submission tasks in a computational grid system.

Wireless resources are scarce, shared and time-varying making resource allocation mechanisms, e.g., scheduling, a key and challenging element of wireless system design. In designing good schedulers, we consider three types of performance metrics: system capacity, quality of service (QoS) seen by users, and the energy expenditures (battery lifetimes) incurred by mobile terminals. In this dissertation we investigate the impact of scheduling policies on these performance metrics, their interactions, and/or tradeoffs, and we specifically focus on flow-level performance under stochastic traffic loads. In the first part of the dissertation we evaluate interactions among flow-level performance metrics when integrating QoS and best effort flows in a wireless system using opportunistic scheduling. We introduce a simple flow-level model capturing the salient features of bandwidth sharing for an opportunistic scheduler which ensures a mean throughput to each QoS stream on every time slot. We show that the integration of QoS and best effort flows results in a loss of opportunism, which in turn results in a reduction of the stability region, degradation in system capacity, and increased file transfer delay. In the second part of the dissertation we study several ways in which mobile terminals can backoff on their uplink transmit power (thus slow down their transmissions) in order to extend battery lifetimes. This is particularly effective when a wireless system is underloaded, so the degradation in the users' perceived performance can be negligible. The challenge, however, is developing a mechanism that achieves a good tradeoff among transmit power, idling/circuit power, and the performance customers will see. We consider systems with flow-level dynamics supporting either real-time or best effort (e.g., file transfers) sessions. We show that significant energy savings can be achieved by leveraging dynamic spare capacity. We then extend our study to the case where mobile terminals have multiple transmit antennas. In the third part of the dissertation we develop a framework for user association in infrastructure-based wireless networks, specifically focused on adaptively balancing flow loads given spatially inhomogeneous traffic distributions. Our work encompasses several possible user association objective functions resulting in rate-optimal, throughput-optimal, delay-optimal, and load-equalizing policy, which we collectively denote [alpha]-optimal user association. We prove that the optimal load vector that minimizes this function is the fixed point of a certain mapping. Based on this mapping we propose an iterative distributed user association policy and prove that it converges to the globally optimal decision in steady state. In addition we address admission control policies for the case where the system cannot be stabilized. / text

[pt] Os sistemas de agendamento de consultas tradicionalmente realizam as marcações dos pacientes em intervalos fixos de tempo, sem levar em consideração diversos fatores de complexidade do sistema de saúde. Isso pode causar mão de obra ociosa em alguns períodos do dia e longas filas de espera de pacientes em outros momentos. Nesse contexto, esta dissertação tem como intuito propor uma nova política de agendamento para uma clínica especializada em cirurgia bariátrica do Rio de Janeiro, considerando os fatores desse sistema: tempos de serviços estocásticos, impontualidade do paciente, atrasos e interrupções do serviço, e presenças de no-shows. Esta dissertação analisou diversos cenários com overbooking (marcação de pacientes adicionais), e testou as principais políticas por meio de simulação, propondo a mais adequada para a clínica. As 18 políticas de agendamento aplicadas foram encontradas através de uma extensa revisão sistemática da literatura. Com a utilização da política de agendamento OFFSET, foi possível aumentar o número de atendimentos em 30 por cento para o agendamento do principal provedor da clínica, mantendo o nível de serviço prestado. Além disto, foi proposta uma nova política de agendamento, denominada DOME CYCLE, que teve resultados superiores às demais políticas da literatura na média dos cenários realizados. / [en] Appointment-scheduling systems traditionally schedule patient appointments at fixed intervals, without taking into account several complexity factors of health-care system. This schedule can make the server idle at certain times of the day and can produce long queues of patients at other times. In this context, the objective of this study is to propose a new scheduling policy for a clinic specialized in bariatric surgery in Rio de Janeiro, considering the following factors of this system: stochastic service times, patient unpunctuality, delays and interruptions of the provider and presences of no-shows. This study analyzed several scenarios with overbooking, and tested the main policies with a simulation model, proposing the most appropriate for the clinic. The 18 scheduling policies applied were found through an extensive systematic review of the literature. With the use of the OFFSET scheduling policy, it was possible to increase the number of appointments by 30 percent to the scheduling of the main clinic provider, maintaining the level of service provided. In addition, a new scheduling policy, called DOME CYCLE, was proposed, which has outperformed the other policies in the average of the tests performed.

Immersion based technologies such as Augmented Reality (AR), Virtual Reality (VR) and Mixed Reality (MR), together falling under the umbrella of Extended Reality (XR) have taken the world by storm in the recent past. However, with the growing market and the increasing number of applications of XR, multiple challenges have arisen. To maintain acceptable levels of motion-to-photon latency, there is a need to serve the users with ultra low latency and with high reliability. To provide high quality rendering, these solutions have traditionally been deployed with wired connections, but severely inhibiting user mobility. Thus, the need to develop wireless solutions promising ultra low latency and high reliability emerges. Cloud/Edge based solutions promise to provide great dividends in this regard but it still remains crucial to understand how different scheduling policies perform against one another in terms of average throughput, mean system time, the number of UEs which can be serviced simultaneously etc. In this thesis, we explore how online packet scheduling policies such as first-come-first-serve, earliestdeadline-first, maximum weight scheduling etc. compare against other Quality of Experience(QoE)/ packet weight aware online scheduling policies and also against optimal offline schemes such as maximum-weighted-bipartitematching. We perform a detailed analysis of how these policies fare by studying various metrics such as the average-packet system time, competitive ratios, packet drop percentages and weight throughput, amongst others. Finally, we also explore how the introduction of multi-layered video encoding impacts XR service. Amongst the findings of the thesis, we conclude that it is possible to come up with solutions such as EDFα (which is a deadline and weight aware derivative of the earliest deadline first scheduling policy), which can either increase the weight throughput when compared to other baselines while also providing lesser packet drops and lower average system times for the scheduled packets. This algorithm can be further tuned by varying α to accordingly alter the weight throughput, system time and packet drop ratio depending on the precise user application. Additionally, we establish with the help of simulations that the introduction of multi-layered video encoding conclusively helps in reducing the average system time and eventually allows for more users to be accommodated in an XR based system at the cost of worsening video quality. / Immersionsbaserade teknologier som Augmented Reality (AR), Virtual Reality (VR) och Mixed Reality (MR), som tillsammans faller under paraplyet Extended Reality (XR) har tagit världen med storm på senare tid. Men med den växande marknaden och det ökande antalet tillämpningar av XR har flera utmaningar uppstått. För att förhindra åksjuka hos användare och för att upprätthålla acceptabla nivåer av rörelse-till-foton-latens, finns det ett behov av att betjäna användarna med ultralåg latens och med hög tillförlitlighet. För att ge högkvalitativ rendering har dessa lösningar traditionellt implementerats med trådbundna anslutningar, men de hämmar kraftigt användarens rörlighet. Därför uppstår behovet av att utveckla trådlösa lösningar som lovar ultralåg latens och hög tillförlitlighet. Moln/Edge-baserade lösningar lovar att ge stor utdelning i detta avseende, men det är fortfarande viktigt att förstå hur olika schemaläggningspolicyer fungerar mot varandra när det gäller genomsnittlig genomströmning, genomsnittlig systemtid, antalet UE:er som kan betjänas samtidigt etc. I den här avhandlingen undersöker vi hur online-paketschemaläggningspolicyer som round robin, först till kvarnförst-kvarn, tidigast-deadline-först, schemaläggning för maximal vikt etc. jämförs med andra Quality of Experience (QoE)/Viktmedvetna onlineschemaläggningspolicyer och även mot optimala offline-scheman såsom maximalt viktad-bipartite-matchning. Vi utför en detaljerad analys av hur dessa policyer klarar sig genom att studera olika mätvärden, såsom den genomsnittliga paketets systemtid, konkurrensförhållanden, procentsatser för paketnedgång och viktad genomströmning, bland annat. Slutligen undersöker vi också hur introduktionen av flerskiktad videokodning påverkar XRtjänsten. Bland resultaten av avhandlingen drar vi slutsatsen att det är möjligt att komma med lösningar som EDFα (som är en deadline- och viktmedveten derivata av Earliest deadline first scheduling policy), som antingen kan öka den viktade genomströmning jämfört med andra baslinjer samtidigt som det ger mindre paketnedgångar och lägre genomsnittliga systemtider för de schemalagda paketen. Denna algoritm kan ställas in ytterligare genom att variera α för att följaktligen ändra den viktade genomströmningen, systemtiden och paketnedgångshastigheten beroende på den exakta användarapplikationen. Dessutom fastställer vi med hjälp av simuleringar att införandet av flerskiktsvideokodning definitivt hjälper till att minska den genomsnittliga systemtiden och så småningom tillåter fler användare att få plats i ett XR-baserat system.