A key aspect of cloud computing is the promise of infinite, scalable resources, and that cloud services should scale up and down on demand. This thesis investigates methods for dynamic resource allocation and management of services in cloud datacenters, introducing new approaches as well as improvements to established technologies.Virtualization is a key technology for cloud computing as it allows several operating system instances to run on the same Physical Machine, PM, and cloud services normally consists of a number of Virtual Machines, VMs, that are hosted on PMs. In this thesis, a novel virtualization approach is presented. Instead of running each PM isolated, resources from multiple PMs in the datacenter are disaggregated and exposed to the VMs as pools of CPU, I/O and memory resources. VMs are provisioned by using the right amount of resources from each pool, thereby enabling both larger VMs than any single PM can host as well as VMs with tailor-made specifications for their application. Another important aspect of virtualization is live migration of VMs, which is the concept moving VMs between PMs without interruption in service. Live migration allows for better PM utilization and is also useful for administrative purposes. In the thesis, two improvements to the standard live migration algorithm are presented, delta compression and page transfer reordering. The improvements can reduce migration downtime, i.e., the time that the VM is unavailable, as well as the total migration time. Postcopy migration, where the VM is resumed on the destination before the memory content is transferred is also studied. Both userspace and in-kernel postcopy algorithms are evaluated in an in-depth study of live migration principles and performance.Efficient mapping of VMs onto PMs is a key problem for cloud providers as PM utilization directly impacts revenue. When services are accepted into a datacenter, a decision is made on which PM should host the service VMs. This thesis presents a general approach for service scheduling that allows for the same scheduling software to be used across multiple cloud architectures. A number of scheduling algorithms to optimize objectives like revenue or utilization are also studied. Finally, an approach for continuous datacenter consolidation is presented. As VM workloads fluctuate and server availability varies any initial mapping is bound to become suboptimal over time. The continuous datacenter consolidation approach adjusts this VM-to-PM mapping during operation based on combinations of management actions, like suspending/resuming PMs, live migrating VMs, and suspending/resuming VMs. Proof-of-concept software and a set of algorithms that allows cloud providers to continuously optimize their server resources are presented in the thesis.

The emergence of large-scale Internet services coupled with the evolution of computing technologies such as distributed systems, parallel computing, utility computing, grid, and virtualization has fueled a movement toward a new resource provisioning paradigm called cloud computing. The main appeal of cloud computing lies in its ability to provide a shared pool of infinitely scalable computing resources for cloud services, which can be quickly provisioned and released on-demand with minimal effort. The rapidly growing interest in cloud computing from both the public and industry together with the rapid expansion in scale and complexity of cloud computing resources and the services hosted on them have made monitoring, controlling, and provisioning cloud computing resources at runtime into a very challenging and complex task. This thesis investigates algorithms, models and techniques for autonomously monitoring, controlling, and provisioning the various resources required to meet services’ performance requirements and account for their resource usage. Quota management mechanisms are essential for controlling distributed shared resources so that services do not exceed their allocated or paid-for budget. Appropriate cloud-wide monitoring and controlling of quotas must be exercised to avoid over- or under-provisioning of resources. To this end, this thesis presents new distributed algorithms that efficiently manage quotas for services running across distributed nodes. Determining the optimal amount of resources to meet services’ performance requirements is a key task in cloud computing. However, this task is extremely challenging due to multi-faceted issues such as the dynamic nature of cloud environments, the need for supporting heterogeneous services with different performance requirements, the unpredictable nature of services’ workloads, the non-triviality of mapping performance measurements into resources, and resource shortages. Models and techniques that can predict the optimal amount of resources needed to meet service performance requirements at runtime irrespective of variations in workloads are proposed. Moreover, different service differentiation schemes are proposed for managing temporary resource shortages due to, e.g., flash crowds or hardware failures. In addition, the resources used by services must be accounted for in order to properly bill customers. Thus, monitoring data for running services should be collected and aggregated to maintain a single global state of the system that can be used to generate a single bill for each customer. However, collecting and aggregating such data across geographical distributed locations is challenging because the management task itself may consume significant computing and network resources unless done with care. A consistency and synchronization mechanism that can alleviate this task is proposed.

In this thesis, our goal is to enable and achieve effective and efficient real-time stream processing in a geo-distributed infrastructure, by combining the power of central data centers and micro data centers. Our research focus is to address the challenges of distributing the stream processing applications and placing them closer to data sources and sinks. We enable applications to run in a geo-distributed setting and provide solutions for the network-aware placement of distributed stream processing applications across geo-distributed infrastructures.  First, we evaluate Apache Storm, a widely used open-source distributed stream processing system, in the community network Cloud, as an example of a geo-distributed infrastructure. Our evaluation exposes new requirements for stream processing systems to function in a geo-distributed infrastructure. Second, we propose a solution to facilitate the optimal placement of the stream processing components on geo-distributed infrastructures. We present a novel method for partitioning a geo-distributed infrastructure into a set of computing clusters, each called a micro data center. According to our results, we can increase the minimum available bandwidth in the network and likewise, reduce the average latency to less than 50%. Next, we propose a parallel and distributed graph partitioner, called HoVerCut, for fast partitioning of streaming graphs. Since a lot of data can be presented in the form of graph, graph partitioning can be used to assign the graph elements to different data centers to provide data locality for efficient processing. Last, we provide an approach, called SpanEdge that enables stream processing systems to work on a geo-distributed infrastructure. SpenEdge unifies stream processing over the central and near-the-edge data centers (micro data centers). As a proof of concept, we implement SpanEdge by extending Apache Storm that enables it to run across multiple data centers. / <p>QC 20161005</p>

[pt] Muitas aplicações necessitam do processamento de eventos de streeams de fontes diferentes em combinação com grandes quantidades de dados de bases de conhecimento. CEP Semântico é um paradigma especificamente designado para isso, ele extende o processamento complexo de eventos (CEP) para adicionar o suporte para a linguagem RDF e utiliza uma rede de operadores para processar streams RDF em combinação com bases de conhecimento em RDF. Outra classe popular de sistemas projetados para um proposito similar são os processadores de stream RDF (RSPs). Estes são sistemas que extendem a linguagem SPARQL (a linguaguem de query padrão para RDF) para adicionar a capacidade de fazer queries em stream. CEP Semântico e RSPs possuem propositos similares porém focam em objetivos diferentes. O CEP Semântico, foca na scalabilidade e processamento distribuido enquanto os RSPs focam nos desafios do processamento de streams RDF. Nesta tese, propomos o uso de RSPs como unidades para processamento de streams RDF dentro do contexto de CEP Semântico. Apresentamos uma infraestrutura, chamada DSCEP, que permite o encapsulamento de RSPs existentes em operadores do estilo CEP, de maneira que estes RSPs possam ser interconectados formando uma rede de operadores distribuída e descentralizada. DSCEP lida com os desafios e obstáculos desta interconexão, como comunicação confiável, divisão e agregação de streams, identificação de eventos e time-stamping, etc., permitindo que os usuários se concentrem nas consultas. Também discutimos nesta tese como o DSCEP pode ser usado para diminuir o tempo de processamento de consultas SPARQL monolíticas, seja dividindo-as em subconsultas e operando-as em paralelo através do uso de operadores ou seja dividingo a stream de entrada em multiplos operadores que possuem a mesma query e são executados em paralelo. Além disso também é avaliado o impacto que a base de conhecimento possui no tempo de processamento de queires contínuas. / [en] Many applications require the processing of event streams from different sources in combination with large amounts of background knowledge. Semantic CEP is a paradigm explicitly designed for that. It extends complex event processing (CEP) with RDF support and uses a network of operators to process RDF streams combined with RDF knowledge bases. Another popular class of systems designed for a similar purpose is the RDF stream processors (RSPs). These are systems that extend SPARQL (the RDF query language) with stream processing capabilities. Semantic CEP and RSPs have similar purposes but focus on different things. The former focuses on scalability and distributed processing, while the latter tends to focus on the intricacies of RDF stream processing per se. In this thesis, we propose the use of RSP engines as building blocks for Semantic CEP. We present an infrastructure, called DSCEP, that allows the encapsulation of existing RSP engines into CEP-like operators so that these can be seamlessly interconnected in a distributed, decentralized operator network. DSCEP handles the hurdles of such interconnection, such as reliable communication, stream aggregation and slicing, event identification and time-stamping, etc., allowing users to concentrate on the queries. We also discuss how DSCEP can be used to speed up monolithic SPARQL queries; by splitting them into parallel subqueries that can be executed by the operator network or even by splitting the input stream into multiple operators with the same query running in parallel. Additionally, we evaluate the impact of the knowledge base on the processing time of SPARQL continuous queries.

Une grande partie de ces données volumineuses ont plus de valeur lorsqu'elles sont analysées rapidement, au fur et à mesure de leur génération. Dans plusieurs scénarios d'application émergents, tels que les villes intelligentes, la surveillance opérationnelle de grandes infrastructures et l'Internet des Objets (Internet of Things), des flux continus de données doivent être traités dans des délais très brefs. Dans plusieurs domaines, ce traitement est nécessaire pour détecter des modèles, identifier des défaillances et pour guider la prise de décision. Les données sont donc souvent rassemblées et analysées par des environnements logiciels conçus pour le traitement de flux continus de données. Ces environnements logiciels pour le traitement de flux de données déploient les applications sous-la forme d'un graphe orienté ou de dataflow. Un dataflow contient une ou plusieurs sources (i.e. capteurs, passerelles ou actionneurs); opérateurs qui effectuent des transformations sur les données (e.g., filtrage et agrégation); et des sinks (i.e., éviers qui consomment les requêtes ou stockent les données). Nous proposons dans cette thèse un ensemble de stratégies pour placer les opérateurs dans une infrastructure massivement distribuée cloud-edge en tenant compte des caractéristiques des ressources et des exigences des applications. En particulier, nous décomposons tout d'abord le graphe d'application en identifiant quelques comportements tels que des forks et des joints, puis nous le plaçons dynamiquement sur l'infrastructure. Des simulations et un prototype prenant en compte plusieurs paramètres d'application démontrent que notre approche peut réduire la latence de bout en bout de plus de 50% et aussi améliorer d'autres métriques de qualité de service. L'espace de recherche de solutions pour la reconfiguration des opérateurs peut être énorme en fonction du nombre d'opérateurs, de flux, de ressources et de liens réseau. De plus, il est important de minimiser le coût de la migration tout en améliorant la latence. Des travaux antérieurs, Reinforcement Learning (RL) et Monte-Carlo Tree Searh (MCTS) ont été utilisés pour résoudre les problèmes liés aux grands nombres d’actions et d’états de recherche. Nous modélisons le problème de reconfiguration d'applications sous la forme d'un processus de décision de Markov (MDP) et étudions l'utilisation des algorithmes RL et MCTS pour concevoir des plans de reconfiguration améliorant plusieurs métriques de qualité de service. / A large part of this big data is most valuable when analysed quickly, as it is generated. Under several emerging application scenarios, such as in smart cities, operational monitoring of large infrastructure, and Internet of Things (IoT), continuous data streams must be processed under very short delays. In multiple domains, there is a need for processing data streams to detect patterns, identify failures, and gain insights. Data is often gathered and analysed by Data Stream Processing Engines (DSPEs).A DSPE commonly structures an application as a directed graph or dataflow. A dataflow has one or multiple sources (i.e., gateways or actuators); operators that perform transformations on the data (e.g., filtering); and sinks (i.e., queries that consume or store the data). Most complex operator transformations store information about previously received data as new data is streamed in. Also, a dataflow has stateless operators that consider only the current data. Traditionally, Data Stream Processing (DSP) applications were conceived to run in clusters of homogeneous resources or on the cloud. In a cloud deployment, the whole application is placed on a single cloud provider to benefit from virtually unlimited resources. This approach allows for elastic DSP applications with the ability to allocate additional resources or release idle capacity on demand during runtime to match the application requirements.We introduce a set of strategies to place operators onto cloud and edge while considering characteristics of resources and meeting the requirements of applications. In particular, we first decompose the application graph by identifying behaviours such as forks and joins, and then dynamically split the dataflow graph across edge and cloud. Comprehensive simulations and a real testbed considering multiple application settings demonstrate that our approach can improve the end-to-end latency in over 50% and even other QoS metrics. The solution search space for operator reassignment can be enormous depending on the number of operators, streams, resources and network links. Moreover, it is important to minimise the cost of migration while improving latency. Reinforcement Learning (RL) and Monte-Carlo Tree Search (MCTS) have been used to tackle problems with large search spaces and states, performing at human-level or better in games such as Go. We model the application reconfiguration problem as a Markov Decision Process (MDP) and investigate the use of RL and MCTS algorithms to devise reconfiguring plans that improve QoS metrics.

Der technologische Fortschritt im Bereich multimedialer Sensorik und zugehörigen Methoden zur Datenaufzeichnung, Datenhaltung und -verarbeitung führt im Big Data-Umfeld zu immensen Datenbeständen in Mediatheken und Wissensmanagementsystemen. Zugrundliegende State of the Art-Verarbeitungsalgorithmen werden oftmals problemorientiert entwickelt. Aufgrund der enormen Datenmengen lassen sich nur bedingt zuverlässig Rückschlüsse auf Güte und Anwendbarkeit ziehen. So gestaltet sich auch die intellektuelle Erschließung von großen Korpora schwierig, da die Datenmenge für valide Aussagen nahezu vollumfänglich semi-intellektuell zu prüfen wäre, was spezifisches Fachwissen aus der zugrundeliegenden Datendomäne ebenso voraussetzt wie zugehöriges Verständnis für Datenhandling und Klassifikationsprozesse. Ferner gehen damit gesonderte Anforderungen an Hard- und Software einher, welche in der Regel suboptimal skalieren, da diese zumeist auf Multi-Kern-Rechnern entwickelt und ausgeführt werden, ohne dabei eine notwendige Verteilung vorzusehen. Folglich fehlen Mechanismen, um die Übertragbarkeit der Verfahren auf andere Anwendungsdomänen zu gewährleisten. Die vorliegende Arbeit nimmt sich diesen Herausforderungen an und fokussiert auf die Konzeptionierung und Entwicklung einer verteilten holistischen Infrastruktur, die die automatisierte Verarbeitung multimedialer Daten im Sinne der Merkmalsextraktion, Datenfusion und Metadatensuche innerhalb eines homogenen Systems ermöglicht. Der Fokus der vorliegenden Arbeit liegt in der Konzeptionierung und Entwicklung einer verteilten holistischen Infrastruktur, die die automatisierte Verarbeitung multimedialer Daten im Sinne der Merkmalsextraktion, Datenfusion und Metadatensuche innerhalb eines homogenen aber zugleich verteilten Systems ermöglicht. Dabei sind Ansätze aus den Domänen des Maschinellen Lernens, der Verteilten Systeme, des Datenmanagements und der Virtualisierung zielführend miteinander zu verknüpfen, um auf große Datenmengen angewendet, evaluiert und optimiert werden zu können. Diesbezüglich sind insbesondere aktuelle Technologien und Frameworks zur Detektion von Mustern zu analysieren und einer Leistungsbewertung zu unterziehen, so dass ein Kriterienkatalog ableitbar ist. Die so ermittelten Kriterien bilden die Grundlage für eine Anforderungsanalyse und die Konzeptionierung der notwendigen Infrastruktur. Diese Architektur bildet die Grundlage für Experimente im Big Data-Umfeld in kontextspezifischen Anwendungsfällen aus wissenschaftlichen Evaluationskampagnen, wie beispielsweise TRECVid. Hierzu wird die generische Applizierbarkeit in den beiden Aufgabenfeldern Instance Search und Activity in Extended Videos eruiert.:Abbildungsverzeichnis Tabellenverzeichnis 1 Motivation 2 Methoden und Strategien 3 Systemarchitektur 4 Instance Search 5 Activities in Extended Video 6 Zusammenfassung und Ausblick Anhang Literaturverzeichnis / Technological advances in the field of multimedia sensing and related methods for data acquisition, storage, and processing are leading to immense amounts of data in media libraries and knowledge management systems in the Big Data environment. The underlying modern processing algorithms are often developed in a problem-oriented manner. Due to the enormous amounts of data, reliable statements about quality and applicability can only be made to a limited extent. Thus, the intellectual exploitation of large corpora is also difficult, as the data volume would have to be analyzed for valid statements, which requires specific expertise from the underlying data domain as well as a corresponding understanding of data handling and classification processes. In addition, there are separate requirements for hardware and software, which usually scale in a suboptimal manner while being developed and executed on multicore computers without provision for the required distribution. Consequently, there is a lack of mechanisms to ensure the transferability of the methods to other application domains. The focus of this work is the design and development of a distributed holistic infrastructure that enables the automated processing of multimedia data in terms of feature extraction, data fusion, and metadata search within a homogeneous and simultaneously distributed system. In this context, approaches from the areas of machine learning, distributed systems, data management, and virtualization are combined in order to be applicable on to large data sets followed by evaluation and optimization procedures. In particular, current technologies and frameworks for pattern recognition are to be analyzed and subjected to a performance evaluation so that a catalog of criteria can be derived. The criteria identified in this way form the basis for a requirements analysis and the conceptual design of the infrastructure required. This architecture builds the base for experiments in the Big Data environment in context-specific use cases from scientific evaluation campaigns, such as TRECVid. For this purpose, the generic applicability in the two task areas Instance Search and Activity in Extended Videos is elicited.:Abbildungsverzeichnis Tabellenverzeichnis 1 Motivation 2 Methoden und Strategien 3 Systemarchitektur 4 Instance Search 5 Activities in Extended Video 6 Zusammenfassung und Ausblick Anhang Literaturverzeichnis