Bluetooth is an emerging technology for providing short range, low power, low cost, and ubiquitous wireless environments. In a Bluetooth piconet, the Bluetooth device, known as master, dynamically allocates time slots by way of polling other individual Bluetooth devices called slaves. During the polling interval, a POLL packet will be sent if master has no data to send to the slave; while a NULL packet will be sent if slave has no data to send to the master. Both the POLL and NULL packets are of zero payload and each captures one time slot. In order to avoid transmitting POLL/NULL packets, many polling schemes have been proposed by skipping visit to the slaves that might have no data packet to be sent to the master, but they still have much space to be further improved. In this thesis, we devise a new, efficient and practicable polling scheme¡XCRR (Credit-based Round Robin). In this scheme, the visit to each slave is dynamically adjusted based on the current and historical traffic between the master and slave to reduce the visit to idle slaves. CRR improves the prior polling schemes on four key issues¡GThe first is to enhance the packet transmitting rate and packet receiving rate in a unit time. The second is to avoid unnecessary POLL/NULL packets to save bandwidth and power consumption. The third is to reduce the transmission delay. The fourth is to avoid the starvation and interruption effect. Our simulation results demonstrate that CRR can enhance the throughput among various numbers of active slaves and idle slaves, can improve the transmitting rate and receiving rate of data packets, can reduce the bandwidth by diminishing the visit to idle slaves, and can decrease the packets end-to-end delay. Moreover, to restrict the number of frames exchanged during a single visit to the slave, a threshold is used to prevent the starvation and interruption effect.

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.

No description available.

L’objectif que nous nous sommes fixés dans ce travail est la conception d’algorithmes d’ordonnancement temps réel en-ligne faisables optimisant l’utilisation de la plate-forme d’exécution et/ou des critères applicatifs de qualité de service propres à l’application. Nous avons en particulier étudié l’ordonnancement d’activités sur une ressource unique. Deux cas ont été analysés : le cas de tâches indépendantes périodiques s’exécutant sur un processeur et le cas de flux de messages indépendants périodiques sur un réseau de terrain avec accès au médium priorisé. Nos contributions reposent sur le “modèle classique” de l’ordonnancement temps réel où le système est représenté par un ensemble d’activités périodiques indépendantes et deux problématiques ont été abordées : • optimisation de l’utilisation de la plate-forme d’exécution : utiliser au mieux le potentiel de la plate-forme d’exécution tout en garantissant le respect des contraintes temporelles imposées au système ; ceci optimise le nombre de configurations faisables, • optimisation des critères applicatifs de qualité de service propres à l’application (i.e., pris en compte des performances de l’application autre que la faisabilité) : garantir les contraintes de temps tout en optimisant les performances de l’application. Nous avons donc proposé : • des méthodes de configurations permettant d’optimiser l’utilisation de la plate-forme d’exécution (i.e., maximiser faisabilité) en fixant les paramètres des politiques ou des systèmes considérés d’une manière appropriée. Deux études ont été conduites dans ce cadre : • allocation des “offsets” dans les systèmes “offset free”, • allocation de priorités, de politiques et de quantum dans les systèmes conformes au standard Posix 1003.1b, • une nouvelle classe de politiques d’ordonnancement permettant d’optimiser des critères de performances propres à l’application. De plus, une analyse d’ordonnancement générique pour cette classe a été proposée / Our goal is to come up with feasible (i.e., all required time constraints are met) on-line real-time scheduling algorithms. These algorithms have to optimise 1) the utilisation of the execution platform (i.e., meet time constraints and use platform at its fullest potential) and/or 2) optimise the application dependent performance criteria. We study two cases : the case of independent periodic tasks scheduled on a processor and the case of periodic traffic streams scheduled on a priority bus. To deal with these two problems, we propose : • Configuration methods to allow to optmlise the utilisation rate of the execution platform by setting the parameters of the policies or of the activities of the considered system. We perform two studies : the allocation of offsets in "Offset free" systems (I.E., offsets can be chosen off-line) and the priorities, policies and quantum allocations in systems compliant to the standard Posix 1003.1B, • A new class of scheduling policies to allow optimising application performance dependent criteria

This thesis deals with the use of operation research methods in sports scheduling. The theoretical part is focused on basic methods of operation research, linear programming and assignment problems are described in greater detail. The thesis presents the principles of sports tournaments and selected optimization softwares in the next part. In the practical part own mathematical models for sport scheduling are introduced. The solution procedure is demonstrated on real life problem of sports scheduling for actual men's basketball season. This example provides the reader with complex concept of solving process of sport scheduling problems.

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.

With the increasing demand of computation capabilities, many-core processors are gain-ing more and more attention. As a communication subsystem many-core processors, Network-on-Chip (NoC) draws a lot of attention in the related research fields. A NoC is used to deliver messages among different cores. For many applications, timeliness is of great importance, especially when the application has hard real-time requirements. Thus, the worst-case end-to-end delays of all the messages passing through a NoC should be concerned. Unfortunately, there is no existing analysis tool that can support multiple NoC architectures as well as provide a user-friendly interface.This thesis focuses on a wormhole switched NoC using different arbitration policies which are Fixed Priority (FP) and Round Robin (RR) respectively. FP based arbitration policy includes distinct and shared priority based arbitration policies. We have developed a timing analysis tool targeting the above NoC designs. The Graphical User Interface (GUI) in the tool can simplify the operation of users. The tool takes characteristics of flow sets as input, and returns results regarding the worst-case end-to-end delay of each flow. These results can be used to assist the design of real-time applications on the corre-sponding platform.A number of experiments have been generated to compare different arbitration mecha-nisms using the developed tool. The evaluation focuses on the effect of different param-eters including the number of flows and the number of virtual-channels in a NoC, and the number of hops of each flow. In the first set of experiment, we focus on the schedulabil-ity ratio achieved by different arbitration policies regarding the number of flows. The sec-ond set of experiments focus on the comparison between NoCs with different number of virtual-channels. In the last set of experiments, we compare different arbitration mecha-nisms with respect to the worst-case end-to-end latencies.

Multidisciplinary design optimization (MDO) for large-scale engineering problems poses many challenges (e.g., the design of an efficient concurrent paradigm for global optimization based on disciplinary analyses, expensive computations over vast data sets, etc.) This work focuses on the application of distributed schemes for massively parallel architectures to MDO problems, as a tool for reducing computation time and solving larger problems. The specific problem considered here is configuration optimization of a high speed civil transport (HSCT), and the efficient parallelization of the embedded paradigm for reasonable design space identification. Two distributed dynamic load balancing techniques (random polling and global round robin with message combining) and two necessary termination detection schemes (global task count and token passing) were implemented and evaluated in terms of effectiveness and scalability to large problem sizes and a thousand processors. The effect of certain parameters on execution time was also inspected. Empirical results demonstrated stable performance and effectiveness for all schemes, and the parametric study showed that the selected algorithmic parameters have a negligible effect on performance. / Master of Science

Denna rapport behandlar en undersökning av olika lastbalanseringsalgoritmer i Linux Virtual Server. Undersökningen har gjorts i ett webbkluster (Apache var webbservern som användes) med tre heterogena noder, där operativsystemet var den detalj som skiljde dem åt. Operativsystemen som ingick i undersökningen var Windows Server 2008 R2, CentOS 6.2 och FreeBSD 9.0. De faktorer som undersöktes mellan de olika algoritmerna var klustrets genomsnittliga svarstid vid olika belastning och hur många anslutningar som kunde hanteras av klustret, detta gjordes med verktyget httperf. Undersökningen ger svar på hur ett heterogent webbklusters genomsnittligasvarstid och arbetskapacitet kan skilja sig åt beroende på vilken algoritm som används för lastbalansering. Resultatet visar att den genomsnittliga svarstiden håller sig låg tills en hastig stigning inträffar. Shortest Expected Delay och Weighted Least-Connection Scheduling kunde hantera störst antal anslutningar. / This report covers an investigation of different load balancing algorithms in Linux Virtual Server. The investigation was done in a web cluster (with Apache as the software being used) consisting of three heterogeneous nodes, where the operating system was the detail that differentiated the nodes. The operating systems that were used in the investigation were Windows Server 2008 R2, CentOS 6.2 and FreeBSD 9.0. The factors examined were average response time at different load and how many connections the cluster could cope with, these factors were examined by measurements taken with the tool httperf. The investigation gives an answer to how a heterogeneous web clustersaverage response time and working capacity can be affected by the choice of load balancing algorithm. The result shows that the average response time stays low until a sudden rise occurs. Shortest Expected Delay and Weighted Least-Connection Scheduling could handle the largest number of connections.