Cette thèse présente de nouveaux résultats liant la théorie des systèmes dits insensibles à la latence, à une sous-classe des réseaux de Pétri dénommée Marked Event Graph et son extension dite Synchronous Data Flow. Ces travaux sont intimement associés avec le problème d'ordonnancement général dénommé problème central répétitif. Nous introduisons les modèles synchrones, Marked Event Graphs, Synchronous Data Flow (SDF) et Latency Insensitive. Après, nous discutons des liens existants entre les modèles synchrones, Marked Event Graphs et Latency Insensitive ; nous montrons que le modèle Latency Insensitive est un cas particulier du modèle Marked Event Graph. Nous présentons ensuite une implémentation vérifiée formellement de Latency Insensitive. Après, nous rappelons un résultat connu : tout Marked Event Graph ayant au moins une partie fortement connexe (et s'évaluant avec une règle d'exécution As Soon As Possible (ASAP)) a un comportement ultimement répétitif : c'est à dire qu'il existe un ordonnancement statique. À partir de ce résultat, nous construisons une technique d'ordonnancement particulière dénommée Égalisation qui altère virtuellement la topologie des communications du système afin de ralentir des chemins trop rapides en rajoutant des "registres", tout en conservant les performances en terme de débit du système originel. Enfin, nous introduisons une notion de contrôle limité au modèle Latency Insensitive, avec des noeuds appelés select et merge dont les conditions sont connueset indépendantes des flots de données, plus exactement les conditions d'aiguillage des données sont dirigées par des mots binaires ultimement périodiques (comme dans le cadre de l'ordonnancement statique). Nous effectuons ensuite une abstraction sur le modèle SDF afin de déterminer si le modèle accepte un ordonnancement où la taille de toute place est bornée. Nous pouvons vérifier ensuite la vivacité du système grâce à une simulation, si le modèle originel disposait d'au moins d'une partie fortement connexe. Finalement, nous concluons et discutons des possibilités de travaux futurs.

No description available.

Stream programming is a paradigm where a program is structured by a set of computational nodes connected by streams. Focusing on data moving between computational nodes via streams, this programming model fits well for applications that process long sequences of data. We call such applications reactive stream programs (RSPs) to distinguish them from stream programs with rather small and finite input data. In stream programming, concurrency is expressed implicitly via communication streams. This helps to reduce the complexity of parallel programming. For this reason, stream programming has gained popularity as a programming model for parallel platforms. However, it is also challenging to analyse and improve the performance without an understanding of the program's internal behaviour. This thesis targets an effi cient execution model for deploying RSPs on parallel platforms. This execution model includes a monitoring framework to understand the internal behaviour of RSPs, scheduling strategies for RSPs on uniform shared-memory platforms; and mapping techniques for deploying RSPs on heterogeneous distributed platforms. The foundation of the execution model is based on a study of the performance of RSPs in terms of throughput and latency. This study includes quantitative formulae for throughput and latency; and the identification of factors that influence these performance metrics. Based on the study of RSP performance, this thesis exploits characteristics of RSPs to derive effective scheduling strategies on uniform shared-memory platforms. Aiming to optimise both throughput and latency, these scheduling strategies are implemented in two heuristic-based schedulers. Both of them are designed to be centralised to provide load balancing for RSPs with dynamic behaviour as well as dynamic structures. The first one uses the notion of positive and negative data demands on each stream to determine the scheduling priorities. This scheduler is independent from the runtime system. The second one requires the runtime system to provide the position information for each computational node in the RSP; and uses that to decide the scheduling priorities. Our experiments show that both schedulers provides similar performance while being significantly better than a reference implementation without dynamic load balancing. Also based on the study of RSP performance, we present in this thesis two new heuristic partitioning algorithms which are used to map RSPs onto heterogeneous distributed platforms. These are Kernighan-Lin Adaptation (KLA) and Congestion Avoidance (CA), where the main objective is to optimise the throughput. This is a multi-parameter optimisation problem where existing graph partitioning algorithms are not applicable. Compared to the generic meta-heuristic Simulated Annealing algorithm, both proposed algorithms achieve equally good or better results. KLA is faster for small benchmarks while slower for large ones. In contrast, CA is always orders of magnitudes faster even for very large benchmarks.

High availability, cost effectiveness and ease of application deployment have accelerated the adoption rate of cloud computing. This fast proliferation of cloud computing promotes the rapid development of large-scale infrastructures. However, large cloud datacenters (DCs) require infrastructure, design, deployment, scalability and reliability and need better management techniques to achieve sustainable design benefits. Resources inside cloud infrastructures often operate at low utilization, rarely exceeding 20-30%, which increases the operational cost significantly, especially due to energy consumption. To reduce operational cost without affecting quality of service (QoS) requirements, cloud applications should be allocated just enough resources to minimize their completion time or to maximize utilization.  The focus of this thesis is to enable resource-efficient and performance-aware cloud infrastructures by addressing above mentioned cost and performance related challenges. In particular, we propose algorithms, techniques, and deployment strategies for improving the dynamic allocation of virtual machines (VMs) into physical machines (PMs).  For minimizing the operational cost, we mainly focus on optimizing energy consumption of PMs by applying dynamic VM consolidation methods. To make VM consolidation techniques more efficient, we propose to utilize multiple paths to spread traffic and deploy recent queue management schemes which can maximize network resource utilization and reduce both downtime and migration time for live migration techniques. In addition, a dynamic resource allocation scheme is presented to distribute workloads among geographically dispersed DCs considering their location based time varying costs due to e.g. carbon emission or bandwidth provision. For optimizing performance level objectives, we focus on interference among applications contending in shared resources and propose a novel VM consolidation scheme considering sensitivity of the VMs to their demanded resources. Further, to investigate the impact of uncertain parameters on cloud resource allocation and applications’ QoS such as unpredictable variations in demand, we develop an optimization model based on the theory of robust optimization. Furthermore, in order to handle the scalability issues in the context of large scale infrastructures, a robust and fast Tabu Search algorithm is designed and evaluated. / High availability, cost effectiveness and ease of application deployment have accelerated the adoption rate of cloud computing. This fast proliferation of cloud computing promotes the rapid development of large-scale infrastructures. However, large cloud datacenters (DCs) require infrastructure, design, deployment, scalability and reliability and need better management techniques to achieve sustainable design benefits. Resources inside cloud infrastructures often operate at low utilization, rarely exceeding 20-30%, which increases the operational cost significantly, especially due to energy consumption. To reduce operational cost without affecting quality of service (QoS) requirements, cloud applications should be allocated just enough resources to minimize their completion time or to maximize utilization.  The focus of this thesis is to enable resource-efficient and performance-aware cloud infrastructures by addressing above mentioned cost and performance related challenges. In particular, we propose algorithms, techniques, and deployment strategies for improving the dynamic allocation of virtual machines (VMs) into physical machines (PMs).

Wireless networks are undergoing an unprecedented revolution in the last decade. With the explosion of delay-sensitive applications in the Internet (i.e., online gaming and VoIP), latency becomes a major issue for the development of wireless technology. Taking advantage of the significant decline in memory prices, industrialists equip the network devices with larger buffering capacities to improve the network throughput by limiting packets drops. Over-buffering results in increasing the time that packets spend in the queues and, thus, introducing more latency in networks. This phenomenon is known as “bufferbloat”. While throughput is the dominant performance metric, latency also has a huge impact on user experience not only for real-time applications but also for common applications like web browsing, which is sensitive to latencies in order of hundreds of milliseconds. Concerns have arisen about designing sophisticated queue management schemes to mitigate the effects of such phenomenon. My thesis research aims to solve bufferbloat problem in both traditional half-duplex and cutting-edge full-duplex wireless systems by reducing delay while maximizing wireless links utilization and fairness. Our work shed lights on buffer management algorithms behavior in wireless networks and their ability to reduce latency resulting from excessive queuing delays inside oversized static network buffers without a significant loss in other network metrics. First of all, we address the problem of buffer management in wireless full-duplex networks by using Wireless Queue Management (WQM), which is an active queue management technique for wireless networks. Our solution is based on Relay Full-Duplex MAC (RFD-MAC), an asynchronous media access control protocol designed for relay full-duplexing. Compared to the default case, our solution reduces the end-to-end delay by two orders of magnitude while achieving similar throughput in most of the cases. In the second part of this thesis, we propose a novel design called “LearnQueue” based on reinforcement learning that can effectively control the latency in wireless networks. LearnQueue adapts quickly and intelligently to changes in the wireless environment using a sophisticated reward structure. Testbed results prove that LearnQueue can guarantee low latency while preserving throughput.

Software-intensive systems are increasingly expected to operate under changing and uncertain conditions, including not only varying user needs and workloads, but also fluctuating resource capacity. Self-adaptation is an approach that aims to address this problem, giving systems the ability to change their behavior and structure to adapt to changes in themselves and their operating environment without human intervention. Self-adaptive systems tend to be reactive and myopic, adapting in response to changes without anticipating what the subsequent adaptation needs will be. Adapting reactively can result in inefficiencies due to the system performing a suboptimal sequence of adaptations. Furthermore, some adaptation tactics—atomic adaptation actions that leave the system in a consistent state—have latency and take some time to produce their effect. In that case, reactive adaptation causes the system to lag behind environment changes. What is worse, a long running adaptation action may prevent the system from performing other adaptations until it completes, further limiting its ability to effectively deal with the environment changes. To address these limitations and improve the effectiveness of self-adaptation, we present proactive latency-aware adaptation, an approach that considers the timing of adaptation (i) leveraging predictions of the near future state of the environment to adapt proactively; (ii) considering the latency of adaptation tactics when deciding how to adapt; and (iii) executing tactics concurrently. We have developed three different solution approaches embodying these principles. One is based on probabilistic model checking, making it inherently able to deal with the stochastic behavior of the environment, and guaranteeing optimal adaptation choices over a finite decision horizon. The second approach uses stochastic dynamic programming to make adaptation decisions, and thanks to performing part of the computations required to make those decisions off-line, it achieves a speedup of an order of magnitude over the first solution approach without compromising optimality. A third solution approach makes adaptation decisions based on repertoires of adaptation strategies— predefined compositions of adaptation tactics. This approach is more scalable than the other two because the solution space is smaller, allowing an adaptive system to reap some of the benefits of proactive latency-aware adaptation even if the number of ways in which it could adapt is too large for the other approaches to consider all these possibilities. We evaluate the approach using two different classes of systems with different adaptation goals, and different repertoires of adaptation strategies. One of them is a web system, with the adaptation goal of utility maximization. The other is a cyberphysical system operating in a hostile environment. In that system, self-adaptation must not only maximize the reward gained, but also keep the probability of surviving a mission above a threshold. In both cases, our results show that proactive latency-aware adaptation improves the effectiveness of self-adaptation with respect to reactive time-agnostic adaptation.

The aim of the theses is to design a methodology for centralized monitoring of data traffic in an ISP network that would detect individual connection with connectivity problems, and evaluate these problems. The methodology should at least evaluate packet loss and latency between a centrally located monitoring point and endpoints at user premises. A further goal is to implement this methodology, test it and evaluate the results.

The relationship between accommodation and myopia has been under investigation for many years, and the effort to understand it is ongoing. In this thesis, an introduction to the state of myopia research is given first, with particular reference to studies of accommodation and higher-order ocular aberrations, which feature in the subsequent chapters. Following a brief introduction to the general technique of aberrometry and visual stimulus control using adaptive optics, the development of a monocular adaptive optics instrument for this purpose is described. The instrument is used to vary a dioptric stimulus and record the accommodation response in pilot studies and a detailed experiment, which has also been published elsewhere. It is found, among other things, that accommodation can respond to more than one different input level during its latency period, and that such inputs can be stored until components of the accommodation control system are free to process them. Indications of a minimum halting time for accommodation, of around 0.6 s, are presented. In later chapters, the development and testing of a new, binocular adaptive optics apparatus will be found. As well as binocular aberrometry and adaptive optics control of stimulus aberrations, this instrument displaces images to allow for and stimulate ocular convergence in binocular accommodation experiments. It is the first instrument in the world with its combined functionalities. Finally, the contribution of this thesis is summarised, and further instrumentation development and experiments are put forward for the continuation of this branch of accommodation and myopia research.

More and more so-called soft real-time traffic is being sent over IP-based networks. The bursty, data-limited traffic pattern as well as the latency requirements from this traffic present challenges to the traditional communication techniques, designed for bulk traffic without considering latency. To meet the requirements from soft real-time traffic, in particular from telephony signaling, the Stream Control Transmission Protocol (SCTP) was designed. Its support for connectivity to multiple networks, i.e., multihoming, provides robustness and opens up for concurrent multipath transfer (CMT) over multiple paths. Since SCTP is a general transport protocol, it also enables for handover of media sessions between heterogeneous networks. Migrating an ongoing session to a new network, as well as CMT with minimal latency, requires tuning of several protocol parameters and mechanisms. This thesis addresses latency reduction for soft real-time traffic using SCTP multihoming from three perspectives. The first focus is on latency for signaling traffic in case of path failure, where a path switch, a failover, occurs. We regard quick failure detection as well as rapid startup on the failover target path. The results indicate that by careful parameter tuning, the failover time may be significantly reduced. The second focus in the thesis is on latency for signaling traffic using CMT. To this end, we address sender-side scheduling. We evaluate some existing schedulers, and design a dynamic stream-aware scheduler. The results indicate that the dynamic stream-aware scheduler may provide significantly improved latency in unbalanced networks. Finally, we target multihomed SCTP to provide for handover of a media session between heterogeneous wireless networks in a mobile scenario. We implement a handover scheme and our investigation shows that SCTP could provide for seamless handover of a media session at walking speed. / So-called soft real-time traffic may be sent over IP-based networks. The bursty, data-limited traffic pattern and the latency requirements from this traffic present a challenge to traditional communication techniques. The Stream Control Transmission Protocol (SCTP), with support for multihoming, was designed to better meet the requirements from soft-real time traffic. Multihoming provides for robustness and for concurrent multipath transfer (CMT) as well as for handover of sessions between heterogeneous networks. Still, to meet the timeliness requirements, tuning of protocol parameters and mechanisms is crucial. This thesis addresses latency reduction for soft real-time traffic using SCTP multihoming. The first focus is on signaling traffic in case of path failure, where a path switch, a failover, occurs. We show that careful parameter tuning may reduce the failover time significantly. The second focus is on signaling traffic using CMT. We address sender-side scheduling and show that dynamic stream-aware scheduling may reduce latency when data is transmitted over asymmetric network  paths. The third focus is multihomed SCTP for handover between heterogeneous networks, where we show that SCTP could provide for seamless handover of a media session at walking speed. / <p>Paper 3 (Efficient Scheduling to Reduce Latency...) ingick i avhandlingen som manuskript med samma namn.</p>

Diversas aplicações são responsáveis por gerar dados ao longo do tempo de maneira contínua, ordenada e ininterrupta em um ambiente dinâmico, denominados fluxo de dados. Entre possíveis tarefas que podem ser realizadas com estes dados, classificação é uma das mais proeminentes. Devido à natureza não estacionária do ambiente responsável por gerar os dados, as características que descrevem os conceitos das classes do problema de classificação podem se alterar ao longo do tempo. Por isso, classificadores de fluxo de dados requerem constantes atualizações em seus modelos para que a taxa de acerto se mantenha estável ao longo do tempo. Na etapa de atualização a maior parte das abordagens considera que, após a predição de cada exemplo, o seu rótulo correto é imediatamente disponibilizado sem qualquer atraso de tempo (latência nula). Devido aos altos custos do processo de rotulação, os rótulos corretos nem sempre podem ser obtidos para a maior parte dos dados ou são obtidos após um considerável atraso de tempo. No caso mais desafiador, encontram-se as aplicações em que após a etapa de classificação dos exemplos, os seus respectivos rótulos corretos nunca sã disponibilizados para o algoritmo, caso chamado de latência extrema. Neste cenário, não é possível o uso de abordagens tradicionais, sendo necessário o desenvolvimento de novos métodos que sejam capazes de manter um modelo de classificação atualizado mesmo na ausência de dados rotulados. Nesta tese, além de discutir o problema de latência na tarefa de classificação de fluxo de dados não estacionários, negligenciado por boa parte da literatura, também sã propostos dois algoritmos denominados SCARGC e MClassification para o cenário de latência extrema. Ambas as propostas se baseiam no uso de técnicas de agrupamento para a adaptação à mudanças de maneira não supervisionada. Os algoritmos propostos são intuitivos, simples e apresentam resultados superiores ou equivalentes a outros algoritmos da literatura em avaliações com dados sintéticos e reais, tanto em termos de acurácia de classificação como em tempo computacional. Aléem de buscar o avanço no estado-da-arte na área de aprendizado em fluxo de dados, este trabalho também apresenta contribuições para uma importante aplicação tecnológica com impacto social e na saúde pública. Especificamente, explorou-se um sensor óptico para a identificação automática de espécies de insetos a partir da análise de informações provenientes do batimento de asas dos insetos. Para a descrição dos dados, foi verificado que os coeficientes Mel-cepstrais apresentaram os melhores resultados entre as diferentes técnicas de processamento digital de sinais avaliadas. Este sensor é um exemplo concreto de aplicação responsável por gerar um fluxo de dados em que é necessário realizar classificações em tempo real. Durante a etapa de classificação, este sensor exige a adaptação a possíveis variações em condições ambientais, responsáveis por alterar o comportamento dos insetos ao longo do tempo. Para lidar com este problema, é proposto um Sistema com Múltiplos Classificadores que realiza a seleção dinâmica do classificador mais adequado de acordo com características de cada exemplo de teste. Em avaliações com mudanças pouco significativas nas condições ambientais, foi possível obter uma acurácia de classificação próxima de 90%, no cenário com múltiplas classes e, cerca de 95% para a identificação da espécie Aedes aegypti, considerando o treinamento com uma única classe. No cenário com mudanças significativas nos dados, foi possível obter 91% de acurácia em um problema com 5 classes e 96% para a classificação de insetos vetores de importantes doenças como dengue e zika vírus. / Many applications are able to generate data continuously over t ime in an ordered and uninterrupted way in a dynamic environment , called data streams. Among possible tasks that can be performed with these data, classification is one of the most prominent . Due to non-stationarity of the environment that generates the data, the features that describe the concepts of the classes can change over time. Thus, the classifiers that deal with data streams require constants updates in their classification models to maintain a stable accuracy over time. In the update phase, most of the approaches assume that after the classification of each example from the stream, their actual class label is available without any t ime delay (zero latency). Given the high label costs, it is more reasonable to consider that this delay could vary for the most portion of the data. In the more challenging case, there are applications with extreme latency, where in after the classification of the examples, heir actual class labels are never available to the algorithm. In this scenario, it is not possible to use traditional approaches. Thus, there is the need of new methods that are able to maintain a classification model updated in the absence of labeled data. In this thesis, besides to discuss the problem of latency to obtain actual labels in data stream classification problems, neglected by most of the works, we also propose two new algorithms to deal with extreme latency, called SCARGC and MClassification. Both algorithms are based on the use of clustering approaches to adapt to changes in an unsupervised way. The proposed algorithms are intuitive, simpleand showed superior or equivalent results in terms of accuracy and computation time compared to other approaches from literature in an evaluation on synthetic and real data. In addition to the advance in the state-of-the-art in the stream learning area, this thesis also presents contributions to an important technological application with social and public health impacts. Specifically, it was studied an optical sensor to automatically identify insect species by the means of the analysis of information coming from wing beat of insects. To describe the data, we conclude that the Mel-cepst ral coefficients guide to the best results among different evaluated digital signal processing techniques. This sensor is a concrete example of an applicat ion that generates a data st ream for which it is necessary to perform real-time classification. During the classification phase, this sensor must adapt their classification model to possible variat ions in environmental conditions, responsible for changing the behavior of insects. To address this problem, we propose a System with Multiple Classifiers that dynamically selects the most adequate classifier according to characteristics of each test example. In evaluations with minor changes in the environmental conditions, we achieved a classification accuracy close to 90% in a scenario with multiple classes and 95% when identifying Aedes aegypti species considering the training phase with only the positive class. In the scenario with considerable changes in the environmental conditions, we achieved 91% of accuracy considering 5 species and 96% to classify vector mosquitoes of important diseases as dengue and zika virus.