Universität Stuttgart
Permanent URI for this communityhttps://elib.uni-stuttgart.de/handle/11682/1
Browse
Search Results
Item Open Access Average case considerations for Mergelnsertion(2018) Stober, FlorianThe MergeInsertion Algorithm, also known as Ford-Johnson Algorithm, is a sorting algorithm that was discovered by Ford and Johnson in 1959. It was later described by Knuth as MergeInsertion. The algorithm can be divided into three steps: First pairs of elements are compared. Then the larger half is sorted using MergeInsertion. And last the remaining elements are inserted. The most interesting property of this algorithm is the number of comparisons it requires, which is close to the information-theoretic lower bound. While the worst-case behavior is well understood, only little is known about the average-case. This thesis takes a closer look at the average case behavior. An upper bound of n log n − 1.4005n + o(n) is established. For small n the exact values are calculated. Furthermore the impact of different approaches to binary insertion on the number of comparisons is explored. To conclude we perform some experiments to evaluate different approaches on improving MergeInsertion.Item Open Access Generic templates for monitoring agents(2018) Weise, MarcThis thesis presents an agent-centric approach for monitoring IT resources, which enables the execution of preprocessing and aggregation steps directly on the target systems in order to limit data transfers to a central server and allow a local event detection and treatment. To keep the agent behavior definition as simple as possible, an extendable template model is introduced which can be used to define Monitoring Pipelines by chaining individual processing steps. Furthermore this work demonstrates how a graphical editor can be implemented which also allows non-experts in the field of monitoring to create and modify Monitoring Templates.Item Open Access Personenbezogene Daten im Data Lake(2018) Ebinger, FelixBig-Data-Analysen bieten Wettbewerbsvorteile, ermöglichen Innovationen und können zu einer höheren Qualität von Produkten oder Serviceleistungen beitragen. Insbesondere die Analyse von Kundendaten und des Kundenverhaltens eröffnet vielfältige Möglichkeiten, um dem Kunden auf ihn zugeschnittene Angebote zu unterbreiten und um so zu höheren Umsätzen und zu einer höheren Kundenzufriedenheit beizutragen. Für die dafür benötigten Daten werden geeignete Speichersysteme benötigt. Ein solches System stellt der Data Lake dar. Neben der gut skalierenden und günstigen Speicherung von Daten ist auch die Auswertung der Daten mittels explorativer Analysen bereits im Design angelegt. Gleichzeitig steht aber auch der Schutz, genauer der fehlende Schutz der Privatsphäre, des Einzelnen bei Big Data Verarbeitungen im Mittelpunkt der öffentlichen Aufmerksamkeit und Kritik. Insbesondere wird vor dem so entstehenden „gläsernen Menschen“ und den daraus resultierenden gesellschaftlichen Folgen gewarnt. Die sich daraus ergebenden Fragen, in welchem Umfang und auf welche Art personenbezogene Daten verarbeitet werden dürfen, bedürfen, neben einer ethisch-moralischen, vor allem einer rechtlichen Antwort. Die europäische Datenschutzgrundverordnung stellt hierzu den rechtlichen Rahmen dar, in dem personenbezogene Daten verarbeitet werden dürfen. In dieser Arbeit werden die gesetzlichen Anforderungen mit dem Konzept des Data Lakes abgeglichen und es wird aufgezeigt, wo Herausforderungen beim Design und bei der Implementierung eines Data Lakes entstehen (z.B. Transparenz, Zweckbindung, Recht auf Löschung). Zudem werden Lösungsansätze für diese Herausforderungen entwickelt und vorgestellt. Aus den einzelnen Lösungsansätzen werden zwei Lösungskonzepte für einige der identifizierten Herausforderungen entwickelt. Eines der Konzepte, ein Metadaten-Modell, wird dabei prototypisch umgesetzt und anhand von Use Cases beispielhaft getestet.Item Open Access Interactive ray tracing of solvent excluded surfaces(2018) Zahn, SebastianDomain experts in fields concerned with the behavior of molecules, for example biochemists, employ simulations to study a molecule’s individual properties and mutual interactions with other molecules. To obtain an intuitive spatial understanding of the returned data of the simulations, various visualization techniques such as molecular surfaces can be applied on the data. The solvent excluded surface depicts the boundary between the molecule’s and a solvent’s occupied space and therefore the molecules accessibility for the solvent. Insight about a molecule’s potential for interaction such as reactions can be gained by studying the surface’s shape visually. Current implementations for the visualization of the surface usually utilize GPU ray casting to achieve the performance required to allow interactivity such as viewpoint changing. However, this makes implementation of physically motivated effects like ambient occlusion or global illumination difficult. If compute resources do not contain GPUs, which is often the case in compute clusters, expensive software rasterization has to be employed instead. As CPUs offer less parallelism compared to GPUs, overhead introduced by the overdraw of thousands of primitives should be avoided. To mitigate these issues, CPU visualization approaches resurfaced again in recent times. In this work, the solvent excluded surface is visualized interactively using the classic ray tracing approach within the OSPRay CPU ray tracing framework. The described implementation is able to compute and visualize the solvent excluded surface for datasets composed of millions of atoms. Additionally, the surface supports transparency rendering, which allows implementation of a cavity visualization method that uses ambient occlusion.Item Open Access How to speed up BDD automated acceptance testing for safety-critical systems(2018) Degutis, Daniel RyanAn important aspect of developing safety-critical systems is testing, and in some cases an agile development and testing approach is desirable. To reflect and test safety requirements, a process based on Behavior Driven Development (BDD) is considered in this work. The goal is to have an as efficient as possible process for BDD automated acceptance testing. The original process for this, used in an earlier experiment, is examined and automatable parts are identified. Based on this, improvements to the process are proposed and implemented. This results in an updated process, that utilizes a newly implemented command line tool written for the purpose of producing test cases. These can then be used for the BDD automated acceptance testing process. Finally, an evaluation with students BDD acceptance testing a sample system is conducted, to determine the effectiveness of the improved process. The results of the evaluation show benefits in productivity when using the improved process.Item Open Access Operator latency in a Complex Event Processing application(2018) Hagenmayer, SimonComplex Event Processing often comes with an enormous amount of event data that needs to be processed. Hence, parallelization plays a significant role in handling high workload situations. The cost of an application however is often defined by the amount of used resources, like in Cloud computing, where the pay-as-you-go model applies. Still, one wants to have a working system that can handle traffic peaks within a given latency bound, so the resources-to-latency-proportion needs to be optimized. Previous work mostly focused on studying complex operator types in specific environments. In this thesis however, we want to get a general view, how parallelization degrees and types influence our CEP system, to be able to estimate what costs could arise. Therefore, a CEP application was created that simulates different system conditions with respect to workload, operator processing time and others, in order to test and analyze the latency properties of a wait operator. This work provides an overview over latency behavior of operators in an example Complex Event Processing application, which can provide a basis for future work in creating an optimized system, that not only keeps a certain latency threshold but also minimizes the costs and resources needed to achieve this goal.Item Open Access Design and implementation of a container-based architecture for real-time control applications(2018) Melcher, JanThe fourth industrial revolution and the advent of cyber-physical systems increase the flexibility and effectiveness in production, but they also change the role of software. Traditional monolithic systems need to split up in order to increase flexibility, maintainability and performance. There are existing approaches transforming traditional software towards a cloud-based infrastructure, but little work is done in applying this to real-time applications. This work proposes an architecture that uses containers to modularize real-time control applications, messaging for communication and a hardware abstraction layer to improve maintainability, reusability and flexibility. Using a prototypical implementation of the architecture, we validate the feasibility of this approach through a benchmark.Item Open Access Combining application layer and network layer filtering in Pub/Sub systems(2018) Sakkal, FadiContent-based Publish/Subscribe systems deliver notifications from publishers to subscribers based on the content of the notifications. Low latency and bandwidth efficiency are two major concerns in these systems. Hybrid Publish/Subscribe systems were developed to take advantage of the new trend of Software Defined Networking (SDN). In these systems, notifications can be filtered on two layers, namely the application-layer and the network-layer. Since each one of these two layers has advantages over the other, it was important to have a selection algorithm to decide on which layer a certain notification has to be filtered. When choosing to filter notifications on the application layer, notifications have to be sent to software filters (servers) located in the topology. The placement of these servers is important for the overall performance of the system. In this thesis, we propose three different placement algorithms, each of which considers a different aspect of the system and tries to place the servers in a way that improves this aspect. The K-Center placement algorithm aims at minimizing the maximum distance between the sending node and the destination server. This will give an upper bound on the worst-case scenario regarding the latency. TheK-Median placement algorithm is designed to minimize the average distance that the sent notifications have to pass to reach the server. The Utilitarian placement algorithm focuses on providing faster service to the packets which are intended for many subscribers, giving better overall service to the majority of the users at the expense of a worse service for some others. We have evaluated the proposed placement algorithms and compared them to each other according to different categories using two different topologies and two different distributions for the published notifications. As expected, the K-Center algorithm proved to be better in minimizing the maximum distance required for a notification to reach a server, while the K-Median and the Utilitarian algorithms showed similar results in most of the cases and were better in minimizing the average distance.Item Open Access Divide-and-conquer scheduling for time-sensitive networks(2018) Bansal, BharatThe advent of the Internet of Things(IoT) and Industry 4.0 coupled with the increase in the deployment of Cyber-physical systems(CPS), which includes industrial automation systems, has increased the urgency to deploy networking technologies with real-time guarantees. The IEEE 802.1Obv standard has recently emerged as a viable alternative for the future of real-time communication over Ethernet that has stringent end-to-end latency and jitter requirements after it has been recently standardized by the Time Sensitive Network Task Group. Scheduling in Time-Sensitive Network(TSN) has not been standardized by the Task Group to carry the scheduled traffic till now. In this paper, we address the scheduling problem for a Time-Sensitive Network(TSN) for large and complex networks. State-of-the-art scheduling algorithms take a centralized approach to compute transmission schedules for time-triggered traffic. Centralized approaches generally compute fairly optimum transmission schedules but the runtimes for the centralized approaches are high (order of days) for large and complex networks. The aim is to generate a scheduling algorithm having lower runtimes as compared to centralized approaches for large networks and having large time-triggered flows even if the computed scheduling has a worse optimum solution than the centralized algorithm. We present a divide-and-conquer approach that might be apter in these scenarios, as it may generate a schedule with lower runtimes as compared to the centralized approaches. In particular, we present an Integer Linear Program(ILP) based formulation and a simple heuristics for the divide-and-conquer approach. Moreover, we parallelize the problem in order to further reduce the runtimes. We evaluate the optimality, utilization, scalability of the different approaches. Furthermore, we evaluate the runtimes for different network configurations and discuss the trade-off between heuristics and ILP based formulation.Item Open Access Grafisches Clustering von OSCAR-Suchresultaten(2018) Makolli, SokolDie Suchergebnisse der Suchmaschine OSCAR sind häufig für den Benutzer wegen ihrer großen Menge unübersichtlich. Eine Strukturierung auf Clientseite liefert zwar für den Nutzer relevante Ergebnisse, jedoch ist der dabei entstehende Kommunikationsoverhead zu groß und die Strukturierung somit zu langsam. In dieser Arbeit wird eine Strukturierung auf Serverseite vorgestellt, die Ergebnisse mit zehn- bis zwanzigfacher und bei einer regionalen Strukturierung mit bis zu hundertfacher Geschwindigkeit liefert.