Am 11. April 2007 werden in der Europäischen Union neue Vorschriften bezüglich der Lenk- und Ruhezeiten im Straßengütertransport in Kraft treten. Den neuen Vorschriften zufolge können Spediteure und Verlader für Verstöße der Fahrer haftbar gemacht werden. Da zudem Lenk- und Ruhezeiten einen signifikanten Einfluss auf Reisezeiten haben, ist eine Berücksichtigung der entsprechenden Regelungen bei der Tourenplanung unumgänglich. In diesem Beitrag wird gezeigt wie die neuen EU-Vorschriften in die Tourenplanung eingebracht werden können und das Vehicle Routing Problem mit Lenk- und Ruhezeiten (VRPLR) vorgestellt.

Diese Forschungsarbeit beschreibt alle Aspekte der Entwicklung eines neuartigen, autonomen Quadrokopters, genannt AQopterI8, zur Innenraumerkundung. Dank seiner einzigartigen modularen Komposition von Soft- und Hardware ist der AQopterI8 in der Lage auch unter widrigen Umweltbedingungen autonom zu agieren und unterschiedliche Anforderungen zu erfüllen. Die Arbeit behandelt sowohl theoretische Fragestellungen unter dem Schwerpunkt der einfachen Realisierbarkeit als auch Aspekte der praktischen Umsetzung, womit sie Themen aus den Gebieten Signalverarbeitung, Regelungstechnik, Elektrotechnik, Modellbau, Robotik und Informatik behandelt. Kernaspekt der Arbeit sind Lösungen zur Autonomie, Hinderniserkennung und Kollisionsvermeidung. Das System verwendet IMUs (Inertial Measurement Unit, inertiale Messeinheit) zur Orientierungsbestimmung und Lageregelung und kann unterschiedliche Sensormodelle automatisch detektieren. Ultraschall-, Infrarot- und Luftdrucksensoren in Kombination mit der IMU werden zur Höhenbestimmung und Höhenregelung eingesetzt. Darüber hinaus werden bildgebende Sensoren (Videokamera, PMD), ein Laser-Scanner sowie Ultraschall- und Infrarotsensoren zur Hindernis-erkennung und Kollisionsvermeidung (Abstandsregelung) verwendet. Mit Hilfe optischer Sensoren kann der Quadrokopter basierend auf Prinzipien der Bildverarbeitung Objekte erkennen sowie seine Position im Raum bestimmen. Die genannten Subsysteme im Zusammenspiel erlauben es dem AQopterI8 ein Objekt in einem unbekannten Raum autonom, d.h. völlig ohne jedes externe Hilfsmittel, zu suchen und dessen Position auf einer Karte anzugeben. Das System kann Kollisionen mit Wänden vermeiden und Personen autonom ausweichen. Dabei verwendet der AQopterI8 Hardware, die deutlich günstiger und Dank der Redundanz gleichzeitig erheblich verlässlicher ist als vergleichbare Mono-Sensor-Systeme (z.B. Kamera- oder Laser-Scanner-basierte Systeme). Neben dem Zweck als Forschungsarbeit (Dissertation) dient die vorliegende Arbeit auch als Dokumentation des Gesamtprojektes AQopterI8, dessen Ziel die Erforschung und Entwicklung neuartiger autonomer Quadrokopter zur Innenraumerkundung ist. Darüber hinaus wird das System zum Zweck der Lehre und Forschung an der Universität Würzburg, der Fachhochschule Brandenburg sowie der Fachhochschule Würzburg-Schweinfurt eingesetzt. Darunter fallen Laborübungen und 31 vom Autor dieser Arbeit betreute studentische Bachelor- und Masterarbeiten. Das Projekt wurde ausgezeichnet vom Universitätsbund und der IHK Würzburg-Mainfranken mit dem Universitätsförderpreis der Mainfränkischen Wirtschaft und wird gefördert unter den Bezeichnungen „Lebensretter mit Propellern“ und „Rettungshelfer mit Propellern“. Außerdem wurde die Arbeit für den Gips-Schüle-Preis nominiert. Absicht dieser Projekte ist die Entwicklung einer Rettungsdrohne. In den Medien Zeitung, Fernsehen und Radio wurde über den AQopterI8 schon mehrfach berichtet. Die Evaluierung zeigt, dass das System in der Lage ist, voll autonom in Innenräumen zu fliegen, Kollisionen mit Objekten zu vermeiden (Abstandsregelung), eine Suche durchzuführen, Objekte zu erkennen, zu lokalisieren und zu zählen. Da nur wenige Forschungsarbeiten diesen Grad an Autonomie erreichen, gleichzeitig aber keine Arbeit die gestellten Anforderungen vergleichbar erfüllt, erweitert die Arbeit den Stand der Forschung. / The following scientific work describes entirely the development of an innovative autonomous quadrotor, called AQopterI8, for indoor exploration and object search describing solutions in the fields of signal processing, control theory, software and hardware. The main topics are autonomy, collision avoidance and obstacle detection. The AQopterI8 uses an IMU (inertial measurement unit) for attitude control and together with ultrasonic, infrared and pressure sensors for height control. Furthermore ultrasonic, infrared, stereo vision, pmd (photonic mixing device) and laser sensors enable the quadrotor to fly autonomously, detect obstacles and avoid collisions (distance control). All ressources are on-Board and the quadrotor requires no external system such as GPS or OTS (optical tracking system) cameras. The evaluation shows, that the AQopterI8 can control its distance to moving obstacles such as persons, can fly through corridors and search, localize and count autonmously target objects. The work was marked with the university promotion prize from the chamber of commerce (IHK Mainfranken) and has been many times in the media such as newspaper, radio and television.

The attitude and orbit control system of pico- and nano-satellites to date is one of the bottle necks for future scientific and commercial applications. A performance increase while keeping with the satellites’ restrictions will enable new space missions especially for the smallest of the CubeSat classes. This work addresses methods to measure and improve the satellite’s attitude pointing and orbit control performance based on advanced sensor data analysis and optimized on-board software concepts. These methods are applied to spaceborne satellites and future CubeSat missions to demonstrate their validity. An in-orbit calibration procedure for a typical CubeSat attitude sensor suite is developed and applied to the UWE-3 satellite in space. Subsequently, a method to estimate the attitude determination accuracy without the help of an external reference sensor is developed. Using this method, it is shown that the UWE-3 satellite achieves an in-orbit attitude determination accuracy of about 2°. An advanced data analysis of the attitude motion of a miniature satellite is used in order to estimate the main attitude disturbance torque in orbit. It is shown, that the magnetic disturbance is by far the most significant contribution for miniature satellites and a method to estimate the residual magnetic dipole moment of a satellite is developed. Its application to three CubeSats currently in orbit reveals that magnetic disturbances are a common issue for this class of satellites. The dipole moments measured are between 23.1mAm² and 137.2mAm². In order to autonomously estimate and counteract this disturbance in future missions an on-board magnetic dipole estimation algorithm is developed. The autonomous neutralization of such disturbance torques together with the simplification of attitude control for the satellite operator is the focus of a novel on-board attitude control software architecture. It incorporates disturbance torques acting on the satellite and automatically optimizes the control output. Its application is demonstrated in space on board of the UWE-3 satellite through various attitude control experiments of which the results are presented here. The integration of a miniaturized electric propulsion system will enable CubeSats to perform orbit control and, thus, open up new application scenarios. The in-orbit characterization, however, poses the problem of precisely measuring very low thrust levels in the order of µN. A method to measure this thrust based on the attitude dynamics of the satellite is developed and evaluated in simulation. It is shown, that the demonstrator mission UWE-4 will be able to measure these thrust levels with a high accuracy of 1% for thrust levels higher than 1µN. The orbit control capabilities of UWE-4 using its electric propulsion system are evaluated and a hybrid attitude control system making use of the satellite’s magnetorquers and the electric propulsion system is developed. It is based on the flexible attitude control architecture mentioned before and thrust vector pointing accuracies of better than 2° can be achieved. This results in a thrust delivery of more than 99% of the desired acceleration in the target direction. / Eine präzise Lage- und Orbitregelung stellt derzeit eine der größten Limitierungen der Einsatzmöglichkeiten von Kleinstsatelliten dar. Um zukünftige wissenschaftliche und kommerzielle Missionen auch mit dieser Klasse von Satelliten erfolgreich durchführen zu können, ist eine Leistungssteigerung bei gleichbleibender Größe und Masse nötig. Die vorliegende Arbeit beschäftigt sich mit der Verbesserung des Lageregelungssystems, der Vermessung der Ausrichtgenauigkeit im Orbit und der Herstellung von Orbitregelungskapazitäten mithilfe von fortschrittlicher Sensordatenanalyse und optimierter on-board Software. Die hier entwickelten Methoden wurden an im Orbit befindlichen Satelliten demonstriert und deren Gültigkeit gezeigt. Neben einer Methode um die typische CubeSat Lageerkennungssensorik im Orbit zu kalibrieren wurde ein Verfahren entwickelt, um die Ausrichtgenauigkeit ohne die Zuhilfenahme eines externen Referenzsensors zu bestimmen. Beide Verfahren wurden mithilfe des UWE-3 Satelliten im Orbit demonstriert. Die genaue Analyse der Dynamik eines Satelliten gibt Aufschluss über die vorwiegend herrschenden Störmomente. Für Kleinstsatelliten im erdnahen Orbit kann gezeigt werden, dass Störungen aufgrund von statischen magnetischen Verunreinigungen bei Weitem am meisten Einfluss auf die Dynamik des Satelliten haben. In dieser Arbeit wird eine Methode präsentiert, die Daten der Lageerkennung nutzt um das magnetische Dipolmoment eines Kleinstsatelliten zu bestimmen. Mithilfe dieses Verfahrens konnte das Dipolmoment von drei unterschiedlichen CubeSats im Bereicht von 23.1mAm² bis 137.2mAm² präzise bestimmt werden. Um die Lageregelungsgenauigkeit zu steigern wird ein Software Konzept präsentiert, welches die bekannten Störungen der Satellitendynamik inherent und energieoptimiert kompensiert. Die Anwendung dieser on-board Software wurde mit UWE-3 in einer Vielzahl von Lageregelungsexperimenten im Orbit demonstriert. Die Integration von elektrischen Antrieben wird zukünftigen Kleinstsatelliten die Möglichkeit zur Orbitkontrolle geben und damit viele neue Anwendungsszenarien eröffnen. Die Qualifizierung und Vermessung der Triebwerke im Orbit stellt jedoch eine technische Schwierigkeit dar, da Schübe im Bereich von µN gemessen werden müssen. Ein Verfahren zur genauen Bestimmung des Schubs eines solchen Triebwerks basierend auf dessen Auswirkung auf die Satellitendynamik wurde entwickelt und wird hier mit Hilfe von Simulationen für die UWE-4 Mission demonstriert. Es wird gezeigt, dass mit Hilfe von UWE-4 der Schub der Triebwerke mit einer hohen Genauigkeit von 1% Fehler für Schübe größer 1µN gemessen werden können. Eine magnetische Lageregelung unter Zuhilfenahme der elektischen Antriebe stellt das Konzept der hybriden Lage- und Orbitregelung für UWE-4 dar. Die damit erzielbare Leistung hinsichtlich der Ausrichtgenauigkeit sowie Orbitregelung wurde untersucht und ist hier für verschiedene Szenarien gezeigt.

Miniaturized satellites on a nanosatellite scale below 10kg of total mass contribute most to the number of launched satellites into Low Earth Orbit today. This results from the potential to design, integrate and launch these space missions within months at very low costs. In the past decade, the reliability in the fields of system design, communication, and attitude control have matured to allow for competitive applications in Earth observation, communication services, and science missions. The capability of orbit control is an important next step in this development, enabling operators to adjust orbits according to current mission needs and small satellite formation flight, which promotes new measurements in various fields of space science. Moreover, this ability makes missions with altitudes above the ISS comply with planned regulations regarding collision avoidance maneuvering. This dissertation presents the successful implementation of orbit control capabilities on the pico-satellite class for the first time. This pioneering achievement is demonstrated on the 1U CubeSat UWE–4. A focus is on the integration and operation of an electric propulsion system on miniaturized satellites. Besides limitations in size, mass, and power of a pico-satellite, the choice of a suitable electric propulsion system was driven by electromagnetic cleanliness and the use as a combined attitude and orbit control system. Moreover, the integration of the propulsion system leaves the valuable space at the outer faces of the CubeSat structure unoccupied for future use by payloads. The used NanoFEEP propulsion system consists of four thruster heads, two neutralizers and two Power Processing Units (PPUs). The thrusters can be used continuously for 50 minutes per orbit after the liquefaction of the propellant by dedicated heaters. The power consumption of a PPU with one activated thruster, its heater and a neutralizer at emitter current levels of 30-60μA or thrust levels of 2.6-5.5μN, respectively, is in the range of 430-1050mW. Two thruster heads were activated within the scope of in-orbit experiments. The thrust direction was determined using a novel algorithm within 15.7° and 13.2° of the mounting direction. Despite limited controllability of the remaining thrusters, thrust vector pointing was achieved using the magnetic actuators of the Attitude and Orbit Control System. In mid 2020, several orbit control maneuvers changed the altitude of UWE–4, a first for pico-satellites. During the orbit lowering scenario with a duration of ten days, a single thruster head was activated in 78 orbits for 5:40 minutes per orbit. This resulted in a reduction of the orbit altitude by about 98.3m and applied a Delta v of 5.4cm/s to UWE–4. The same thruster was activated in another experiment during 44 orbits within five days for an average duration of 7:00 minutes per orbit. The altitude of UWE–4 was increased by about 81.2m and a Delta v of 4.4cm/s was applied. Additionally, a collision avoidance maneuver was executed in July 2020, which increased the distance of closest approach to the object by more than 5000m. / Heutzutage werden überwiegend Kleinstsatelliten in niedrige Erdumlaufbahnen befördert, da dies schnell und sehr kostengünstig möglich ist. Von der Planung bis zum Raketenstart vergehen oft nur wenige Monate. Im vergangenen Jahrzehnt haben sich Kleinstsatelliten bezüglich Systemgestaltung, Kommunikation und Lageregelung dahingehend weiterentwickelt, dass diese in den Anwendungsbereichen Erdbeobachtung, Kommunikationsdienstleistungen und wissenschaftlichen Missionen mit herkömmlichen Satelliten konkurrieren können. Ein weiterer wichtiger Entwicklungsschritt für Kleinstsatelliten wäre die Möglichkeit der Orbitkontrolle. Diese würde die Betreiber befähigen, die Flugbahn der Satelliten entsprechend den aktuellen Zielen der Mission anzupassen und Formationsflug von Kleinstsatelliten durchzuführen, um neue wissenschaftliche Erkenntnisse in vielen Bereichen der Weltraumforschung zu fördern. Gleichzeitig würden Kleinstsatelliten den aktuell geplanten Vorschriften Rechnung tragen, nach denen Satelliten mit Flughöhen oberhalb der ISS manövrierfähig sein müssen, um Kollisionen zu vermeiden. Die vorliegende Dissertation präsentiert die erste erfolgreiche Orbitkontrolle auf einem Piko-Satelliten. Diese Pionierleistung wird auf dem 1U CubeSat UWE–4 demonstriert. Ein Schwerpunkt dieser Arbeit liegt dabei auf der Integration und dem Betrieb eines elektrischen Antriebssystems auf Kleinstsatelliten. Diese Integration des Antriebssystems hält den wertvollen Platz an den Außenflächen des CubeSats für zukünftige Nutzlasten frei und ermöglicht dessen Anwendung als Lage- und Orbitregelungsaktuator. Das verwendete NanoFEEP Antriebssystem beinhaltet vier Triebwerke, zwei Neutralisatoren und zwei Platinen zur Steuerung. Nach der Verflüssigung des Treibstoffs durch dedizierte Heizer können die Triebwerke pro Erdumrundung für 50 Minuten kontinuierlich genutzt werden. Der Stromverbrauch einer Steuerplatine mit einem aktiven Triebwerk, seinem Heizer und einem Neutralisator bei Emitterströmen von 30-60μA bzw. Schüben von 2.6-5.5μN liegt im Bereich von 430-1050mW. Im Rahmen von In- Orbit Experimenten wurden zwei Triebwerke aktiviert. Die Schubrichtungen der aktiven Triebwerke konnten mit einem neuartigen Algorithmus in einem Winkel von 15.7° bzw. 13.2° bezüglich ihrer Einbaurichtung bestimmt werden. Trotz mangelnder Steuerbarkeit der verbleibenden Triebwerke konnte eine Ausrichtung des Schubvektors unter Zuhilfenahme der magnetischen Aktuatoren des Lageregelungssystems erreicht werden. Mehrere Orbitregelungsexperimente zur Veränderung der Flughöhe konnten Mitte 2020 zum ersten Mal auf einem Piko-Satelliten gezeigt werden. Um die Flughöhe zu verringern, wurde ein Triebwerk über einen Zeitraum von zehn Tagen während 78 Orbits gefeuert, wobei dieses pro Erdumrundung für durchschnittlich 5:40 Minuten aktiviert wurde. Hierdurch wurde die Flughöhe von UWE–4 um 98m reduziert und seine Geschwindigkeit um ein Delta v von 7.2cm/s erhöht. In einem anderen Experiment wurde dasselbe Triebwerk während 44 Orbits in einem Zeitraum von fünf Tagen für durchschnittlich 7:00 Minuten aktiviert, wodurch die Flughöhe des Kleinstsatelliten um 74.2m angehoben und seine Geschwindigkeit um ein Delta v von 4.0cm/s verringert wurde. Zudem wurde ein Manöver zur Kollisionsvermeidung durchgeführt, das den Abstand zwischen UWE–4 und dem Objekt auf Kollisionskurs zum Zeitpunkt der kleinsten Annäherung um mehr als 5000m vergrößert hat.

Although of particular importance for many reallife applications, restrictions to drivers’ working hours have only received very little attention in the vehicle routing literature. Regulations regarding drivers’ working hours often have a big impact on total travel times, i.e. the time required for driving, breaks, and rest periods. In this paper we describe the regulations for drivers’ working hours in the European Union. We present the Vehicle Routing Problem with Drivers’ Working Hours (VRPDWH) which generalises the well-known Vehicle Routing Problem with Time Windows. We present a Large Neighbourhood Search algorithm and test cases for the VRPDWH and conclude this paper with computational experiments.

Real-life vehicle routing problems encounter a number of complexities that are not considered by the classical models found in the vehicle routing literature. In this paper we consider a dynamic real-life vehicle routing problem which is a combined load acceptance and generalised vehicle routing problem incorporating a diversity of practical complexities. Among those are time window restrictions, a heterogeneous vehicle fleet with different travel times, travel costs and capacity, multi-dimensional capacity constraints, order/vehicle compatibility constraints, orders with multiple pickup, delivery and service locations, different start and end locations for vehicles, route restrictions associated to orders and vehicles, and drivers’ working hours. We propose iterative improvement approaches based on Large Neighborhood Search. Our algorithms are characterised by very fast response times and thus, can be used within dynamic routing systems where input data can change at any time.

In this paper we consider a rich vehicle routing problem where transportation requests are characterised by multiple pickup and delivery locations. The problem is a combined load acceptance and generalised vehicle routing problem incorporating a diversity of practical complexities. Among those are time window restrictions, a heterogeneous vehicle fleet with different travel times, travel costs and capacity, multi-dimensional capacity constraints, order/vehicle compatibility constraints, and different start and end locations for vehicles. We propose iterative improvement approaches based on Large Neighborhood Search and a relatedness measure for transportation requests with multiple pickup and delivery locations. Our algorithms are characterised by very fast response times and thus, can be used within dynamic routing systems where input data can change at any time.

Enterprise applications in virtualized data centers are often subject to time-varying workloads, i.e., the load intensity and request mix change over time, due to seasonal patterns and trends, or unpredictable bursts in user requests. Varying workloads result in frequently changing resource demands to the underlying hardware infrastructure. Virtualization technologies enable sharing and on-demand allocation of hardware resources between multiple applications. In this context, the resource allocations to virtualized applications should be continuously adapted in an elastic fashion, so that "at each point in time the available resources match the current demand as closely as possible" (Herbst el al., 2013). Autonomic approaches to resource management promise significant increases in resource efficiency while avoiding violations of performance and availability requirements during peak workloads. Traditional approaches for autonomic resource management use threshold-based rules (e.g., Amazon EC2) that execute pre-defined reconfiguration actions when a metric reaches a certain threshold (e.g., high resource utilization or load imbalance). However, many business-critical applications are subject to Service-Level-Objectives defined on an application performance metric (e.g., response time or throughput). To determine thresholds so that the end-to-end application SLO is fulfilled poses a major challenge due to the complex relationship between the resource allocation to an application and the application performance. Furthermore, threshold-based approaches are inherently prone to an oscillating behavior resulting in unnecessary reconfigurations. In order to overcome the deficiencies of threshold-based approaches and enable a fully automated approach to dynamically control the resource allocations of virtualized applications, model-based approaches are required that can predict the impact of a reconfiguration on the application performance in advance. However, existing model-based approaches are severely limited in their learning capabilities. They either require complete performance models of the application as input, or use a pre-identified model structure and only learn certain model parameters from empirical data at run-time. The former requires high manual efforts and deep system knowledge to create the performance models. The latter does not provide the flexibility to capture the specifics of complex and heterogeneous system architectures. This thesis presents a self-aware approach to the resource management in virtualized data centers. In this context, self-aware means that it automatically learns performance models of the application and the virtualized infrastructure and reasons based on these models to autonomically adapt the resource allocations in accordance with given application SLOs. Learning a performance model requires the extraction of the model structure representing the system architecture as well as the estimation of model parameters, such as resource demands. The estimation of resource demands is a key challenge as they cannot be observed directly in most systems. The major scientific contributions of this thesis are: - A reference architecture for online model learning in virtualized systems. Our reference architecture is based on a set of model extraction agents. Each agent focuses on specific tasks to automatically create and update model skeletons capturing its local knowledge of the system and collaborates with other agents to extract the structural parts of a global performance model of the system. We define different agent roles in the reference architecture and propose a model-based collaboration mechanism for the agents. The agents may be bundled within virtual appliances and may be tailored to include knowledge about the software stack deployed in a specific virtual appliance. - An online method for the statistical estimation of resource demands. For a given request processed by an application, the resource time consumed for a specified resource within the system (e.g., CPU or I/O device), referred to as resource demand, is the total average time the resource is busy processing the request. A request could be any unit of work (e.g., web page request, database transaction, batch job) processed by the system. We provide a systematization of existing statistical approaches to resource demand estimation and conduct an extensive experimental comparison to evaluate the accuracy of these approaches. We propose a novel method to automatically select estimation approaches and demonstrate that it increases the robustness and accuracy of the estimated resource demands significantly. - Model-based controllers for autonomic vertical scaling of virtualized applications. We design two controllers based on online model-based reasoning techniques in order to vertically scale applications at run-time in accordance with application SLOs. The controllers exploit the knowledge from the automatically extracted performance models when determining necessary reconfigurations. The first controller adds and removes virtual CPUs to an application depending on the current demand. It uses a layered performance model to also consider the physical resource contention when determining the required resources. The second controller adapts the resource allocations proactively to ensure the availability of the application during workload peaks and avoid reconfiguration during phases of high workload. We demonstrate the applicability of our approach in current virtualized environments and show its effectiveness leading to significant increases in resource efficiency and improvements of the application performance and availability under time-varying workloads. The evaluation of our approach is based on two case studies representative of widely used enterprise applications in virtualized data centers. In our case studies, we were able to reduce the amount of required CPU resources by up to 23% and the number of reconfigurations by up to 95% compared to a rule-based approach while ensuring full compliance with application SLO. Furthermore, using workload forecasting techniques we were able to schedule expensive reconfigurations (e.g., changes to the memory size) during phases of load load and thus were able to reduce their impact on application availability by over 80% while significantly improving application performance compared to a reactive controller. The methods and techniques for resource demand estimation and vertical application scaling were developed and evaluated in close collaboration with VMware and Google. / Unternehmensanwendungen in virtualisierten Rechenzentren unterliegen häufig zeitabhängigen Arbeitslasten, d.h. die Lastintensität und der Anfragemix ändern sich mit der Zeit wegen saisonalen Mustern und Trends, sowie unvorhergesehenen Lastspitzen bei den Nutzeranfragen. Variierende Arbeitslasten führen dazu, dass sich die Ressourcenanforderungen an die darunterliegende Hardware-Infrastruktur häufig ändern. Virtualisierungstechniken erlauben die gemeinsame Nutzung und bedarfsgesteuerte Zuteilung von Hardware-Ressourcen zwischen mehreren Anwendungen. In diesem Zusammenhang sollte die Zuteilung von Ressourcen an virtualisierte Anwendungen fortwährend in einer elastischen Art und Weise angepasst werden, um sicherzustellen, dass "zu jedem Zeitpunkt die verfügbaren Ressourcen dem derzeitigen Bedarf möglichst genau entsprechen" (Herbst et al., 2013). Autonome Ansätze zur Ressourcenverwaltung versprechen eine deutliche Steigerung der Ressourceneffizienz wobei Verletzungen der Anforderungen hinsichtlich Performanz und Verfügbarkeit bei Lastspitzen vermieden werden. Herkömmliche Ansätze zur autonomen Ressourcenverwaltung nutzen feste Regeln (z.B., Amazon EC2), die vordefinierte Rekonfigurationen durchführen sobald eine Metrik einen bestimmten Schwellwert erreicht (z.B., hohe Ressourcenauslastung oder ungleichmäßige Lastverteilung). Viele geschäftskritische Anwendungen unterliegen jedoch Zielvorgaben hinsichtlich der Dienstgüte (SLO, engl. Service Level Objectives), die auf Performanzmetriken der Anwendung definiert sind (z.B., Antwortzeit oder Durchsatz). Die Bestimmung von Schwellwerten, sodass die Ende-zu-Ende Anwendungs-SLOs erfüllt werden, stellt aufgrund des komplexen Zusammenspiels zwischen der Ressourcenzuteilung und der Performanz einer Anwendung eine bedeutende Herausforderung dar. Des Weiteren sind Ansätze basierend auf Schwellwerten inhärent anfällig für Oszillationen, die zu überflüssigen Rekonfigurationen führen können. Um die Schwächen schwellwertbasierter Ansätze zu lösen und einen vollständig automatisierten Ansatz zur dynamischen Steuerung von Ressourcenzuteilungen virtualisierter Anwendungen zu ermöglichen, bedarf es modellbasierter Ansätze, die den Einfluss einer Rekonfiguration auf die Performanz einer Anwendung im Voraus vorhersagen können. Bestehende modellbasierte Ansätze sind jedoch stark eingeschränkt hinsichtlich ihrer Lernfähigkeiten. Sie erfordern entweder vollständige Performanzmodelle der Anwendung als Eingabe oder nutzen vorbestimmte Modellstrukturen und lernen nur bestimmte Modellparameter auf Basis von empirischen Daten zur Laufzeit. Erstere erfordern hohe manuelle Aufwände und eine tiefe Systemkenntnis um die Performanzmodelle zu erstellen. Letztere bieten nur eingeschränkte Möglichkeiten um die Besonderheiten von komplexen und heterogenen Systemarchitekturen zu erfassen. Diese Arbeit stellt einen selbstwahrnehmenden (engl. self-aware) Ansatz zur Ressourcenverwaltung in virtualisierten Rechenzentren vor. In diesem Zusammenhang bedeutet Selbstwahrnehmung, dass der Ansatz automatisch Performanzmodelle der Anwendung und der virtualisierten Infrastruktur lernt Basierend auf diesen Modellen entscheidet er autonom wie die Ressourcenzuteilungen angepasst werden, um die Anwendungs-SLOs zu erfüllen. Das Lernen von Performanzmodellen erfordert sowohl die Extraktion der Modellstruktur, die die Systemarchitektur abbildet, als auch die Schätzung von Modellparametern, wie zum Beispiel der Ressourcenverbräuche einzelner Funktionen. Die Schätzung der Ressourcenverbräuche stellt hier eine zentrale Herausforderung dar, da diese in den meisten Systemen nicht direkt gemessen werden können. Die wissenschaftlichen Hauptbeiträge dieser Arbeit sind wie folgt: - Eine Referenzarchitektur, die das Lernen von Modellen in virtualisierten Systemen während des Betriebs ermöglicht. Unsere Referenzarchitektur basiert auf einer Menge von Modellextraktionsagenten. Jeder Agent fokussiert sich auf bestimmte Aufgaben um automatisch ein Modellskeleton, das sein lokales Wissen über das System erfasst, zu erstellen und zu aktualisieren. Jeder Agent arbeitet mit anderen Agenten zusammen um die strukturellen Teile eines globalen Performanzmodells des Systems zu extrahieren. Die Rereferenzarchitektur definiert unterschiedliche Agentenrollen und beinhaltet einen modellbasierten Mechanismus, der die Kooperation unterschiedlicher Agenten ermöglicht. Die Agenten können als Teil virtuellen Appliances gebündelt werden und können dabei maßgeschneidertes Wissen über die Software-Strukturen in dieser virtuellen Appliance beinhalten. - Eine Methode zur fortwährenden statistischen Schätzung von Ressourcenverbräuchen. Der Ressourcenverbrauch (engl. resource demand) einer Anfrage, die von einer Anwendung verarbeitet wird, entspricht der Zeit, die an einer spezifischen Ressource im System (z.B., CPU oder I/O-Gerät) verbraucht wird. Eine Anfrage kann dabei eine beliebige Arbeitseinheit, die von einem System verarbeitet wird, darstellen (z.B. eine Webseitenanfrage, eine Datenbanktransaktion, oder ein Stapelverarbeitungsauftrag). Die vorliegende Arbeit bietet eine Systematisierung existierender Ansätze zur statistischen Schätzung von Ressourcenverbräuchen und führt einen umfangreichen, auf Experimenten aufbauenden Vergleich zur Bewertung der Genauigkeit dieser Ansätze durch. Es wird eine neuartige Methode zur automatischen Auswahl eines Schätzverfahrens vorgeschlagen und gezeigt, dass diese die Robustheit und Genauigkeit der geschätzten Ressourcenverbräuche maßgeblich verbessert. - Modellbasierte Regler für das autonome, vertikale Skalieren von virtualisierten Anwendungen. Es werden zwei Regler entworfen, die auf modellbasierten Entscheidungstechniken basieren, um Anwendungen zur Laufzeit vertikal in Übereinstimmung mit Anwendungs-SLOs zu skalieren. Die Regler nutzen das Wissen aus automatisch extrahierten Performanzmodellen bei der Bestimmung notwendiger Rekonfigurationen. Der erste Regler fügt virtuelle CPUs zu Anwendungen hinzu und entfernt sie wieder in Abhängigkeit vom aktuellen Bedarf. Er nutzt ein geschichtetes Performanzmodell, um bei der Bestimmung der benötigten Ressourcen die Konkurrenzsituation der physikalischen Ressourcen zu beachten. Der zweite Regler passt Ressourcenzuteilungen proaktiv an, um die Verfügbarkeit einer Anwendung während Lastspitzen sicherzustellen und Rekonfigurationen unter großer Last zu vermeiden. Die Arbeit demonstriert die Anwendbarkeit unseres Ansatzes in aktuellen virtualisierten Umgebungen und zeigt seine Effektivität bei der Erhöhung der Ressourceneffizienz und der Verbesserung der Anwendungsperformanz und -verfügbarkeit unter zeitabhängigen Arbeitslasten. Die Evaluation des Ansatzes basiert auf zwei Fallstudien, die repräsentativ für gängige Unternehmensanwendungen in virtualisierten Rechenzentren sind. In den Fallstudien wurde eine Reduzierung der benötigten CPU-Ressourcen von bis zu 23% und der Anzahl der Rekonfigurationen von bis zu 95% im Vergleich zu regel-basierten Ansätzen erreicht, bei gleichzeitiger Erfüllung der Anwendungs-SLOs. Mit Hilfe von Vorhersagetechniken für die Arbeitslast konnten außerdem aufwändige Rekonfigurationen (z.B., Änderungen bei der Menge an zugewiesenem Arbeitsspeicher) so geplant werden, dass sie in Phasen geringer Last durchgeführt werden. Dadurch konnten deren Auswirkungen auf die Verfügbarkeit der Anwendung um mehr als 80% verringert werden bei gleichzeitiger Verbesserung der Anwendungsperformanz verglichen mit einem reaktiven Regler. Die Methoden und Techniken zur Schätzung von Ressourcenverbräuchen und zur vertikalen Skalierung von Anwendungen wurden in enger Zusammenarbeit mit VMware und Google entwickelt und evaluiert.

This technical report publishes the proceedings of the 19th Prague Workshop, which was held from 27th to 28. November 2015. The workshop offers a possibility for young scientists to present their current research work in the fields of computer graphics, human-computer-interaction, robotics and usability. The works is meant as a platform to bring together researchers from both the Czech Technical University in Prague (CTU) and the University of Applied Sciences Dresden (HTW). The German Academic Exchange Service offers its financial support to allow student participants the bilateral exchange between Prague and Dresden.

This technical report publishes the proceedings of the 20th Prague Workshop, which was held from 25th to 26th November 2016 The workshop offers a possibility for young scientists to present their current research work in the fields of computer graphics, human-computer-interaction, robotics and usability. The works is meant as a platform to bring together researchers from both the Czech Technical University in Prague (CTU) and the University of Applied Sciences Dresden (HTW). The German Academic Exchange Service offers its financial support to allow student participants the bilateral exchange between Prague and Dresden.