AN ABSTRACT OF THE THESIS OF Abdulaziz M. AlNowiser, for the Master of Science degree in Computer Science, presented on November 1, 2013, at Southern Illinois University Carbondale. TITLE: TOWARD ENERGY-EFFICIENT SCHEDULING USING WEIGHTED ROUND- ROBIN AND VM REUSE MAJOR PROFESSOR: Dr. Michelle M. Zhu In recent years, the rapid evolving Cloud Computing technologies multiply challenges such as minimizing power consumption and meeting Quality-of-Services (QoS) requirements in the presence of heavy workloads from a large number of users using shared computing resources. Powering a middle-sized data center normally consumes 80,000kW power every year and computer servers consume around .5% of the global power [1]. Statistics for 5000 production servers over a six-month period show that only 10-50% of the total capacity has been effectively used, and a large portion of the resources is actually wasted. In order to address the skyrocket energy cost from the high level resource management aspect, we propose an energy efficient job scheduling approach based on a modified version of Weighted Round Robin scheduler that incorporates VMs reuse and live VM migration without compromising the Service Level Agreement (SLA). The Weighted Round Robin scheduler can monitor the running VMs status for possible VM sharing for job consolidation or migration. In addition, the VMs utilization rate is observed to start live migration from the over-utilizing Processing Element (PE) to under-utilized PEs or to the hibernated PEs by sending WOL (Wake-On-LAN) signal to activate them. The simulation experiments are conducted under the CloudReports environment based on open source CloudSim simulator. The comparisons with other similar scheduling algorithms demonstrate that our enhanced Weighted Round Robin algorithm (EWRR) can achieve considerable better performance in terms of energy consumption and resource utilization rate.

Real-time system refers to the computing, communication, and information system with deadline requirements. To meet these deadline requirements, most systems use a mechanism known as the schedulability test which determines whether each of the admitted tasks can meet its deadline. A new task will not be admitted unless it passes the schedulability test. Schedulability tests can be either direct or indirect. The utilization based schedulability test is the most common schedulability test approach, in which a task can be admitted only if the total system utilization is lower than a pre-derived bound. While the utilization bound based schedulability test is simple and effective, it is often difficult to derive the bound. For its analytical complexity, utilization bound results are usually obtained on a case-by-case basis. In this dissertation, we develop a general framework that allows effective derivation of schedulability bounds for different workload patterns and schedulers. We introduce an analytical model that is capable of describing a wide range of tasks' and schedulers'€™ behaviors. We propose a new definition of utilization, called workload rate. While similar to utilization, workload rate enables flexible representation of different scheduling and workload scenarios and leads to uniform proof of schedulability bounds. We introduce two types of workload constraint functions, s-shaped and r-shaped, for flexible and accurate characterization of the task workloads. We derive parameterized schedulability bounds for arbitrary static priority schedulers, weighted round robin schedulers, and timed token ring schedulers. Existing utilization bounds for these schedulers are obtained from the closed-form formula by direct assignment of proper parameters. Some of these results are applied to a cluster computing environment. The results developed in this dissertation will help future schedulability bound analysis by supplying a unified modeling framework and will ease the implementation practical real-time systems by providing a set of ready to use bound results.

Real-time system refers to the computing, communication, and information system with deadline requirements. To meet these deadline requirements, most systems use a mechanism known as the schedulability test which determines whether each of the admitted tasks can meet its deadline. A new task will not be admitted unless it passes the schedulability test. Schedulability tests can be either direct or indirect. The utilization based schedulability test is the most common schedulability test approach, in which a task can be admitted only if the total system utilization is lower than a pre-derived bound. While the utilization bound based schedulability test is simple and effective, it is often difficult to derive the bound. For its analytical complexity, utilization bound results are usually obtained on a case-by-case basis. In this dissertation, we develop a general framework that allows effective derivation of schedulability bounds for different workload patterns and schedulers. We introduce an analytical model that is capable of describing a wide range of tasks' and schedulers'€™ behaviors. We propose a new definition of utilization, called workload rate. While similar to utilization, workload rate enables flexible representation of different scheduling and workload scenarios and leads to uniform proof of schedulability bounds. We introduce two types of workload constraint functions, s-shaped and r-shaped, for flexible and accurate characterization of the task workloads. We derive parameterized schedulability bounds for arbitrary static priority schedulers, weighted round robin schedulers, and timed token ring schedulers. Existing utilization bounds for these schedulers are obtained from the closed-form formula by direct assignment of proper parameters. Some of these results are applied to a cluster computing environment. The results developed in this dissertation will help future schedulability bound analysis by supplying a unified modeling framework and will ease the implementation practical real-time systems by providing a set of ready to use bound results.

Edge computing, as an approach to leveraging computation capabilities located in different places, is widely deployed in the industry nowadays. With the development of edge computing, many big companies move from the traditional monolithic software architecture to the microservice design. To provide better performance of the applications which contain numerous loosely coupled modules that are deployed among multiple clusters, service routing among multiple clusters needs to be effective. However, most existing solutions are dedicated to static service routing and load balancing strategy, and thus the performance of the application cannot be effectively optimized when network condition changes.To address the problem mentioned above, we proposed a dynamic weighted round robin algorithm and implemented it on top of the cutting edge service mesh Istio. The solution is implemented as a Docker image called RoutingAgent, which is simple to deployed and managed. With the RoutingAgent running in the system, the weights of the target routing clusters will be dynamically changed based on the detected inter-cluster network latency. Consequently, the client-side request turnaround time will be decreased.The solution is evaluated in an emulated environment. Compared to the Istio without RoutingAgent, the experiment results show that the client-side latency can be effectively minimized by the proposed solution in the multicluster environment with dynamic network conditions. In addition to minimizing response time, emulation results demonstrate that loads of each cluster are well balanced. / Edge computing, som ett tillvägagångssätt för att utnyttja beräkningsfunktioner som finns på olika ställen, används i stor utsträckning i branschen nuförtiden. Med utvecklingen av kantdatabasen flyttar många stora företag från den traditionella monolitiska mjukvaruarkitekturen till mikroserviceteknik. För att ge bättre prestanda för de applikationer som innehåller många löst kopplade moduler som distribueras bland flera kluster, måste service routing bland flera kluster vara effektiva. De flesta befintliga lösningarna är dock dedikerade till statisk service-routing och belastningsbalanseringsstrategi, vilket gör att programmets prestanda inte effektivt kan optimeras när nätverksförhållandena ändras.För att ta itu med problemet som nämnts ovan föreslog vi en dynamisk viktad round robin-algoritm och implementerade den ovanpå den avancerade servicenätverket Istio. Lösningen implementeras som en Docker-bild som heter RoutingAgent, som är enkel att distribuera och hantera. Med agenten som körs i systemet ändras vikten av målruteringsklustret dynamiskt baserat på den upptäckta interklusternätets latens. Följaktligen kommer klientsidans begäran om omställningstid att minskas.Lösningen utvärderas i en emulerad miljö. Jämfört med Istio utan agent visar experimentresultaten att klientens latentitet effektivt kan minimeras av den föreslagna lösningen i multicluster-miljö med dynamiska nätverksförhållanden. Förutom att minimera responstid visar emuleringsresultat att belastningar i varje kluster är välbalanserade.

L'étude des systèmes en réseau supports d'applications collaboratives, distribuées et interconnectées par un réseau repose sur l'identification des exigences de fonctionnement de l'application appelées Qualité de Contrôle (QdC), et sur l'évaluation des performances du réseau pour obtenir son niveau de Qualité de Service (QdS). « Cette thématique comporte d'importants verrous de nature fondamentale relevant du domaine de l'automatique, de la robotique, des capteurs, de la théorie de l'information, des réseaux. Par souci de simplification, les travaux sur les systèmes en réseau se repartissent selon deux approches: la première compense les perturbations générées par les communications au niveau de l'application (« control over network »). La seconde adapte les performances du réseau en fonction des besoins applicatifs (« control of network »). L'objectif de nos travaux de thèse est donc de proposer un environnement de modélisation intégré permettant de représenter le comportement des SCRs. Nous avons choisi les Réseaux de Petri de haut niveau qui possède un fort pouvoir d'expression, de formalisation et dont la modularité permet d'ajouter et/ou de faire évoluer les modèles qui sont développés dans ce travail. Dans un premier temps, nous avons proposé un modèle Ethernet Commuté gérant des mécanismes d'ordonnancement. Le choix de ce réseau a été guidé par le fait qu'il est de plus en plus utilisé dans les SCRs. Ensuite, le modèle d'un SCR a été proposé, et modélisé par des Réseaux de Petri de haut de niveau, en intégrant au modèle Ethernet Commuté, l'environnement applicatif : Contrôleur, Process,.. Enfin, des stratégies pour commander le réseau de façon à adapter sa Qualité de Service en regard de la Qualité de Contrôle requise par l'application, ont été mises en oeuvre. Pour cela, des ordonnanceurs à priorité stricte et de type WRR sont utilisés. Les résultats de simulation montrent clairement que des dispositifs de compensation du réseau pour améliorer les performances du système de communication, permettent aussi d'améliorer les performances du système à commander.