Analytical modelling and characterization of Weighted Fair Queueing (WFQ) have recently received considerable attention by several researches since WFQ offers the minimum delay and optimal fairness guarantee. However, all previous work on WFQ has focused on developing approximations of the scheduler with an infinite buffer because of supposed scalability problems in the WFQ computation. The main aims of this thesis are to study WFQ system, by providing an analytical WFQ model which is a theoretical construct based on a form of processor sharing for finite capacity. Furthermore, the solutions for classes with Poisson arrivals and exponential service are derived and verified against global balance solution. This thesis shows that the analytical models proposed can give very good results under particular conditions which are very close to WFQ algorithms, where accuracy of the models is verified by simulations of WFQ model. Simulations were performed with QNAP-2 simulator. In addition, the thesis presents several performance studies signifying the power of the proposed analytical model in providing an accurate delay bounds to a large number of classes. These results are not able to cover all unsolved issues in the WFQ system. They represent a starting point for the research activities that the Author will conduct in the future. The author believes that the most promising research activities exist in the scheduler method to provide statistical guarantees to multi-class services. The author is convinced that alternative software, for example, on the three class model buffer case, is able to satisfy the large number of buffer because of the software limitation in this thesis. While they can be a good topic for long-term research, the short-medium term will show an increasing interest in the modification of the WFQ models to provide differentiated services.

A aplicação de redes sem fio vem crescendo consideravelmente nos últimos anos. Protocolos baseados nesta tecnologia estão sendo desenvolvidos para uma grande variedade de aplicações. A confiabilidade é um dos principais requisitos dos protocolos de comunicação nos ambientes industriais. Interferências, ambiente ruidoso e o grande risco das aplicações industriais que são monitoradas são fatores que elevam os níveis de exigência no que se refere à confiabilidade, redundância e segurança do protocolo. O protocolo WirelessHART é um padrão de comunicação sem fio desenvolvido especificamente para monitoramento e controle de processos com os requisitos necessários para ser utilizado em ambientes industriais. A norma do WirelessHART define diversos aspectos técnicos a serem utilizados no desenvolvimento de algoritmos. Os algoritmos de roteamento e escalonamento de mensagens são de grande relevância para o cumprimento dos requisitos temporais, de confiabilidade e segurança. Requisitos de roteamento e escalonamento são especificados, porém, os algoritmos a serem utilizados não são definidos. O objetivo nessa dissertação é analisar alguns dos principais algoritmos que tem sido propostos especificamente para o protocolo WirelessHART e apresentar um conjunto capaz de ser aplicado nesse protocolo. Análises e comparações entre os algoritmos são realizadas proporcionando um estudo aprofundado sobre seus impactos no desempenho do protocolo. / The application of wireless networks has grown considerably in recent years. Protocols based on this technology are being developed for a great variety of applications. Reliability is one of the main requirements for communication protocols in industrial environments. Interferences, noisy environment and high risk processes that are monitored are factors that increase the levels of requirements in terms of reliability, redundancy and security of the protocol. The WirelessHART protocol is a wireless communication standard specifically designed for process monitoring and control applications with the necessary requirements for to be used in industrial environments. The WirelessHART standard defines several technical aspects to be used in the development of the algorithms. The algorithms of routing and scheduling messages are highly relevant to meeting the timing requirements of reliability and safety. Routing and scheduling strategies are specified, however, the routing and scheduling algorithms are not defined for use. The goal of this dissertation is to analyze some of the main algorithms that have been proposed specifically for the WirelessHART protocol and to present a set able to be applied in this protocol. Analyzes and comparisons between algorithms are realized by providing a detailed study of their impacts on the protocol performance.

Thesis (Ph. D.)--University of Hong Kong, 2007. / Title proper from title frame. Also available in printed format.

The problem of designing scheduling algorithm for multi-channel (e.g., OFDM-based) wireless downlink networks is considered, where the system has a large bandwidth and proportionally large number of users to serve. For this system, while the classical MaxWeight algorithm is known to be throughput-optimal, its buffer-overflow performance is very poor (formally, it is shown that it has zero rate function in our setting). To address this, a class of algorithms called iHLQF (iterated Heaviest matching with Longest Queues First) is proposed. The algorithms in this class are shown to be throughput-optimal for a general class of arrival/channel processes, and also rate-function optimal (i.e., exponentially small buffer overflow probability) for certain arrival/channel processes, where the channel-rates are 0 or 1 packets per timeslot. iHLQF however has higher computational complexity than MaxWeight (n⁴ vs. n² computations per timeslot respectively). To overcome this issue, a new algorithm called SSG (Server-Side Greedy) is proposed. It is shown that SSG is throughput-optimal, results in a much better per-user buffer overflow performance than the MaxWeight algorithm (positive rate function for certain arrival/channel processes), and has a computational complexity (n²) that is comparable to the MaxWeight algorithm. Thus, it provides a nice trade-off between buffer-overflow performance and computational complexity. For multi-rate channel processes, where the channels can serve multiple packets per timeslot, new Markov chain-based coupling arguments are used to derive rate-function positivity results for the SSG algorithm. Finally, an algorithm called DMEQ is proposed and shown to be rate-function optimal for certain multi-rate channel scenarios, whose definition characterizes the sufficient conditions for rate-function optimality in this regime. These results are validated by both analysis and simulations. / text

Η παρούσα εργασία έχει σαν στόχο την ανάλυση ενός προβλήματος δρομολόγησης το οποίο στη βάση του έχει ως εξής: Δίνεται ακολουθία διεργασιών που πρόκειται να δοθεί για επεξεργασία σε ένα σύνολο μηχανών. Η κάθε διεργασία χαρακτηρίζεται από το χρόνο επεξεργασίας της και θα πρέπει να δρομολογηθεί σε κάποια απ' τις μηχανές για χρόνο τουλάχιστον ίσο με αυτό. Επιπλέον υπάρχει απαίτηση από ένα υποσύνολο διεργασιών για επιτάχυνση. Το ζητούμενο είναι να δοθεί αλγόριθμος που δρομολογεί τις διεργασίες στις μηχανές ελαχιστοποιώντας κάποια μετρική απόδοσης, παράλληλα με την εξυπηρέτηση όσο το δυνατόν περισσότερων αιτήσεων για επιτάχυνση. Στα πλαίσια ενός εισαγωγικού κεφαλαίου δίνεται θεωρητικό υπόβαθρο που αφορά σε προβλήματα και αλγορίθμους δρομολόγησης, σημειώνοντας ιδιαίτερα τη διαφορά μεταξύ στατικών και δυναμικών αλγορίθμων. Αντικείμενο της εργασίας αυτής γίνεται στη συνέχεια η μελέτη του παραπάνω προβλήματος, σε περιβάλλον μιας μηχανής και σε παραλλαγές του οι οποίες σχετίζονται με παραμέτρους, όπως για παράδειγμα, προθεσμίες ολοκλήρωσης. Αποτέλεσμα της μελέτης αυτής είναι η ανάπτυξη, αλλά και η αξιολόγηση αποτελεσματικών μεθόδων επίλυσης, χρησιμοποιώντας γνωστά κριτήρια βελτιστοποίησης όπως ο χρόνος που απαιτείται για την ολοκλήρωση των διεργασιών, αλλά και κάποιες νέες μετρικές που συστήνονται και η ανάγκη τους επεξηγείται αναλυτικά. Τέλος στο τρίτο κεφάλαιο γίνεται επισκόπηση προβλημάτων που αφορούν δρομολόγηση σε περισσότερες από μία μηχανές. Τα προβλήματα αυτά ενώ αποδεικνύονται ΝΡ-πλήρη, οι αποδείξεις παραλείπονται και δίδονται παρατηρήσεις για την πολυπλοκότητα παραλλαγών τους. Η εργασία κλείνει με μια παρουσίαση της υπολογιστικής μεθόδου του δυναμικού προγραμματισμού, που γίνεται προσπάθεια να εφαρμοστεί σε προβλήματα δρομολόγησης. / The purpose of the present study is to analyze a scheduling problem, the def- inition of which is: We are given a sequence of tasks that are to be processed on a set of machines. Each task is characterized by its running time and has to be scheduled on a machine, for at least its running time. In addition, there are speedup requests from a subset of tasks. The scheduling algorithm is asked to produce a schedule that minimizes an objective function in par- allel with serving as many as possible speedup requests. The introduction gives a theoretical background concerning scheduling prob- lems and algorithms, with an emphasis on the di_erence between static and dynamic algorithms. The objective of the second chapter, is to study the problem above, in its many variations, with a reference to parameters like the number of the machines, deadlines etc. The result of this study, is the development and the evaluation of two algorithms, using objective functions like makespan, and also some new ones that arise in the essay and their need is analyzed. The thesis closes with a consideration of already known schedul- ing problems and its variants, that have been proved to be NP-complete.

Thesis (Ph. D.)--University of Hong Kong, 2008. / Includes bibliographical references (leaf 99-108) Also available in print.

abstract: Driven by stringent power and thermal constraints, heterogeneous multi-core processors, such as the ARM big-LITTLE architecture, are becoming increasingly popular. In this thesis, the use of low-power heterogeneous multi-cores as Microservers using web search as a motivational application is addressed. In particular, I propose a new family of scheduling policies for heterogeneous microservers that assign incoming search queries to available cores so as to optimize for performance metrics such as mean response time and service level agreements, while guaranteeing thermally-safe operation. Thorough experimental evaluations on a big-LITTLE platform demonstrate, on an heterogeneous eight-core Samsung Exynos 5422 MpSoC, with four big and little cores each, that naive performance oriented scheduling policies quickly result in thermal instability, while the proposed policies not only reduce peak temperature but also achieve 4.8x reduction in processing time and 5.6x increase in energy efficiency compared to baseline scheduling policies. / Dissertation/Thesis / Masters Thesis Electrical Engineering 2015

A aplicação de redes sem fio vem crescendo consideravelmente nos últimos anos. Protocolos baseados nesta tecnologia estão sendo desenvolvidos para uma grande variedade de aplicações. A confiabilidade é um dos principais requisitos dos protocolos de comunicação nos ambientes industriais. Interferências, ambiente ruidoso e o grande risco das aplicações industriais que são monitoradas são fatores que elevam os níveis de exigência no que se refere à confiabilidade, redundância e segurança do protocolo. O protocolo WirelessHART é um padrão de comunicação sem fio desenvolvido especificamente para monitoramento e controle de processos com os requisitos necessários para ser utilizado em ambientes industriais. A norma do WirelessHART define diversos aspectos técnicos a serem utilizados no desenvolvimento de algoritmos. Os algoritmos de roteamento e escalonamento de mensagens são de grande relevância para o cumprimento dos requisitos temporais, de confiabilidade e segurança. Requisitos de roteamento e escalonamento são especificados, porém, os algoritmos a serem utilizados não são definidos. O objetivo nessa dissertação é analisar alguns dos principais algoritmos que tem sido propostos especificamente para o protocolo WirelessHART e apresentar um conjunto capaz de ser aplicado nesse protocolo. Análises e comparações entre os algoritmos são realizadas proporcionando um estudo aprofundado sobre seus impactos no desempenho do protocolo. / The application of wireless networks has grown considerably in recent years. Protocols based on this technology are being developed for a great variety of applications. Reliability is one of the main requirements for communication protocols in industrial environments. Interferences, noisy environment and high risk processes that are monitored are factors that increase the levels of requirements in terms of reliability, redundancy and security of the protocol. The WirelessHART protocol is a wireless communication standard specifically designed for process monitoring and control applications with the necessary requirements for to be used in industrial environments. The WirelessHART standard defines several technical aspects to be used in the development of the algorithms. The algorithms of routing and scheduling messages are highly relevant to meeting the timing requirements of reliability and safety. Routing and scheduling strategies are specified, however, the routing and scheduling algorithms are not defined for use. The goal of this dissertation is to analyze some of the main algorithms that have been proposed specifically for the WirelessHART protocol and to present a set able to be applied in this protocol. Analyzes and comparisons between algorithms are realized by providing a detailed study of their impacts on the protocol performance.

Context. Train re-scheduling during disturbances is a time-consuming task. Modified schedules need to be found, so that trains can meet in suitable locations and delays minimized. Domino effects are difficult to manage. Commercial optimization software has been shown to find optimal solutions, but modied schedules need to be found quickly. Therefore, greedy depth-first algorithms have been designed to find solutions within a limited time-frame. Modern GPUs have a high computational capacity, and have become easier to use for computations unrelated to computer graphics with the development of technologies such as CUDA and OpenCL. Objectives. We explore the feasibility of running a re-scheduling algorithm developed specifically for this problem on a GPU using the CUDA toolkit. The main objective is to find a way of exploiting the computational capacity of modern GPUs to find better re-scheduling solutions within a limited time-frame. Methods. We develop and adapt a sequential algorithm for use on a GPU and run multiple experiments using 16 disturbance scenarios on the single-tracked iron ore line in northern Sweden. Results. Our implementation succeeds in finding re-scheduling solutions without conflicts for all 16 scenarios. The algorithm visits on average 7 times more nodes per time unit than the sequential CPU algorithm when branching at depth 50, and 4 times more when branching at depth 200. Conclusions. The computational performance of our parallel algorithm is promising but the approach is not complete. Our experiments only show that multiple solution branches can be explored fast in parallel, but not how to construct a high level algorithm that systematically searches for better schedules within a certain time limit. Further research is needed for that. We also find that multiple threads explore redundant solutions in our approach.

No description available.