LS 04 Praktische Informatik

Permanent URI for this collection

http://hdl.handle.net/2003/67

Browse

Now showing 1 - 20 of 20

Load-optimization in reconfigurable data-center networks: algorithms and complexity of flow routing
(2023-07-18) Dai, Wenkai; Foerster, Klaus-Tycho; Fuchssteiner, David; Schmid, Stefan
Emerging reconfigurable data centers introduce unprecedented flexibility in how the physical layer can be programmed to adapt to current traffic demands. These reconfigurable topologies are commonly hybrid, consisting of static and reconfigurable links, enabled by e.g., an Optical Circuit Switch (OCS) connected to top-of-rack switches in Clos networks. Even though prior work has showcased the practical benefits of hybrid networks, several crucial performance aspects are not well understood. For example, many systems enforce artificial segregation of the hybrid network parts, leaving money on the table. In this article, we study the algorithmic problem of how to jointly optimize topology and routing in reconfigurable data centers, in order to optimize a most fundamental metric, maximum link load. The complexity of reconfiguration mechanisms in this space is unexplored at large, especially for the following cross-layer network-design problem: given a hybrid network and a traffic matrix, jointly design the physical layer and the flow routing in order to minimize the maximum link load. We chart the corresponding algorithmic landscape in our work, investigating both un-/splittable flows and (non-)segregated routing policies. A topological complexity classification of the problem reveals NP-hardness in general for network topologies that are trees of depth at least two, in contrast to the tractability on trees of depth one. We moreover prove that the problem is not submodular for all these routing policies, even in multi-layer trees. However, networks that can be abstracted by a single packet switch (e.g., nonblocking Fat-Tree topologies) can be optimized efficiently, and we present optimal polynomial-time algorithms accordingly. We complement our theoretical results with trace-driven simulation studies, where our algorithms can significantly improve the network load in comparison to the state-of-the-art.
Modellbasierte Regelung dezentraler Systeme in unbekannten Umgebungen
(2023) Puzicha, Alexander; Buchholz, Peter; Chen, Jian-Jia
Diese Arbeit beschreibt ein Konzept eines Autonomiesystems für autonome Roboterschwärme in Katastrophengebieten. Die Realisierung des Konzeptes und die Integration dieses in einen Prototypen wird ebenfalls dargelegt. Autonome Roboterschwärme können künftig für eine Vielzahl an Katastropheneinsätzen eingesetzt werden. Typische Aufgaben sind die Erkundung eines Gebietes, die Eskortierung von Konvois, der Objekttransport oder der Aufbau von Netzwerken, wenn die Infrastruktur zusammenbricht. Die autonome Regelung der Roboter ist eine anspruchsvolle Aufgabe, vor allem unter schwierigen Umweltbedingungen, die die Kommunikation einschränken. Folglich muss die Regelungssoftware der Roboterschwärme sorgfältig getestet werden, bevor die Roboter in Katastrophengebieten eingesetzt werden. Da Feldtests aufwändig, teuer und teilweise nicht möglich sind, ergeben Simulationen die einzige brauchbare Alternative. Der Test der Software mit Echtzeitanforderungen muss jedoch in einer Echtzeitumgebung durchgeführt werden, wodurch strenge Anforderungen an die Simulationssoftware gestellt werden. Die Regelung muss Teil des Simulators sein, die Dynamik der Roboter muss realistisch simuliert werden, die Umgebungsbedingungen beschrieben werden und die mobile Kommunikation muss modelliert werden, einschließlich der begrenzten Kommunikationsreichweiten und Paketverluste. Dies sollte benutzerfreundlich und effizient implementiert sein, um die Simulation von größeren Schwärmen, wie sie in der Praxis eingesetzt werden, zu ermöglichen. Da zu diesem Zeitpunkt kein System, mit den geforderten Funktionen bekannt ist, werden alle notwendigen Hard- und Softwarekomponenten sowie Protokolle eigenständig entwickelt oder integriert. Dazu wird ein stützstellenbasierter modellprädiktiver Regler für die mobile Robotik adaptiert und weiterentwickelt. Dieser erzielt eine sehr hohe, empirisch nachweisbare Regelgüte im Vergleich zu einer Auswahl an Optimierungsalgorithmen in umfangreichen Tests. Dabei wird eine Zeitschranke von 300ms für einen 30s langen Planungshorizont gewahrt. Dies wird durch eine exponentielle Zerlegung des Horizontes erreicht. Die theoretische Stabilität ist jedoch aufgrund der Kostenfunktionsfreiheit und der exponentiellen Verteilung nicht beweisbar. Um mit Hilfe eines Schwarms ein Netzwerk für Rettungskräfte aufzubauen und um die Agenten in weitläufigem, infrastrukturlosem Gebiet von bis zu 25km² zu betreiben, werden Netzwerkqualitätsprädiktionen und kostengünstige Knotenpunktnetzwerke mit großer Reichweite und geringer Übertragungsrate vorgestellt. Die geringe Übertragungsrate erzwingt die Entwicklung einer anwendungsspezifischen Datenkompression innerhalb des Autonomiesystems. Dieser besteht aus C++ Bibliotheken mit baumartiger Abhängigkeitsstruktur, die vollständig plattform- und prozessorarchitekturunabhängig sowie modular nutzbar sind. Das System ermöglicht den Betrieb autonomer Bodenfahrzeuge sowie die Simulation großer Schwärme mit bis zu 70 Agenten. Dabei können diese rein virtuell, aus emulierter Hardware oder auch aus realen Komponenten aufgebaut sein. Die Realzeitsimulation kann gemischt zentral und dezentral berechnet werden und unterstützt eine Verschmelzung von Simulation und Realdaten bis hin zur Emulation. Der Entwurf des Systems ermöglicht eine einfache Integration in verschiedene Visualisierungssysteme wie Cocos2d-X, CryEngine und Unity. Somit lassen sich sowohl realzeitfähige Anwendungen ohne Oberfläche oder mit einfacher zweidimensionaler Darstellung als auch fotorealistische Anwendungen in der virtuellen Realität erstellen. Der Umfang von über 16 Missionen, den die Agenten bieten, basiert auf einer erweiterten Potenzialfeldtechnik. Aufgrund der durch den Optimierer gebotenen Freiheit, existieren keine Beschränkungen bezüglich der Stetigkeit oder Differenzierbarkeit der zugrundeliegenden Funktionen. Weiterhin wird durch die Freiheit der Akkumulation, Faltung und Verkettung der Funktionen ein modularer Ansatz geboten. Mit diesem lassen sich auch Verhaltensbaumverfahren oder separierte lokale und globale Planer abbilden. Dabei reichen die Missionen von klassischer Wegpunktnavigation über Überwachungsaufgaben bis zu komplexen, dezentralen Schwarmtransporten und Rendezvous. Auch die Störsenderdetektion sowie ein Energiemanagement sind implementiert. Zur Validierung des gesamten Softwaresystems wird ein realer Prototyp für Außeneinsätze unter starken Ressourcenbeschränkungen entwickelt und realisiert. Ergänzend dazu wird zur schnelleren Testdurchführung der Software eine Hardwaresimulation mit der entwickelten Simulation verknüpft, wodurch eine dezentrale Multilevelsimulation erreicht wird. Die Fähigkeit, sich zum einen mit Hardwaresimulatoren für einzelne Roboter und zum anderen mit verschiedenen Visualisierern zu verbinden, ist nur aufgrund der hohen Modularität und der effizienten Implementierung in C++ möglich. Folglich wird ein einheitliches Autonomiesystem entworfen, das den gesamten Einsatzbereich von großen Schwarmsimulationen bis hin zur Regelung einzelner realer Agenten in unbekannten Umgebungen abdeckt.
Rechtzeitigkeit und Dienstgüteförderung vernetzter gerätebasierter Systeme
(2021) Brümmer, Henning; Krumm, Heiko; Ulbrich, Peter
Hochzuverlässige Systeme müssen sorgfältig entwickelt und gründlich geprüft werden. Sie erbringen sicherheitskritische Funktionen und unterliegen erhöhten Zuverlässigkeitsanforderungen. Eine statische Konfiguration und dedizierte Hardware machen die Verlässlichkeit dieser Systeme möglich. Man spricht auch von sogenannten Insellösungen; d.h. die Systeme sind in sich geschlossen und werden für einen ganz bestimmten Zweck entwickelt. Medizingeräte bilden zum Beispiel solche Systeme. Da diese Systeme für ihre Umgebung aber geschlossen sind, ist eine Fernüberwachung oder eine Automatisierung der Gerätekonfiguration in der Regel nicht möglich. Dies wäre aus Sicht der Verlässlichkeit auch eine potenzielle Gefahrenstelle. Eine ganz andere Systemklasse bilden die vernetzen gerätebasierten Systeme. Diese sind hochdynamisch und können durch die Vielfalt von Geräten, Sensoren, Kommunikationsdiensten, Cloud-Infrastrukturen und Big-Data-Analyseverfahren einen hohen Funktionsumfang anbieten. Sie unterliegen in der Regel jedoch einer begrenzten Verlässlichkeit. Die Fitnessbranche zum Beispiel sammelt und überwacht mittels IoT-Geräten wie Smartphones, Smartwatches und intelligenter Waagen die Gesundheitsparameter ihrer Anwender. Die Frage, die sich nun in der immer stärker wachsenden Welt der vernetzten Systeme stellt, ist, wie Informationen und neu gewonnene Erkenntnisse aus den unverlässlichen vernetzten Systemen auch im Umfeld der zuverlässigen Systeme genutzt werden können. Die vorliegende Dissertation untersucht die systematische und effiziente Entwicklung von Big Dependable Systems (BDS) als Zusammenführung von nicht verlässlichen vernetzten Systemen und verlässlichen Systemen. Im Rahmen dieser Arbeit wird ein Lösungsansatz entwickelt, der die Verlässlichkeit von BDS unter der Verwendung von unzuverlässigen vernetzten Konsumergeräten weiterhin gewährleistet. Als wichtigste Verlässlichkeitsanforderungen gelten die Funktionssicherheit sowie die Rechtzeitigkeit von BDS. Schwerpunkt der Untersuchung war das Einhalten der Rechtzeitigkeit und Dienstgüte in solch vernetzten gerätebasierten Systemen.
A multi-objective approach for PH-graphs with applications to stochastic shortest paths
(2020-10-24) Buchholz, Peter; Dohndorf, Iryna
Stochastic shortest path problems (SSPPs) have many applications in practice and are subject of ongoing research for many years. This paper considers a variant of SSPPs where times or costs to pass an edge in a graph are, possibly correlated, random variables. There are two general goals one can aim for, the minimization of the expected costs to reach the destination or the maximization of the probability to reach the destination within a given budget. Often one is interested in policies that build a compromise between different goals which results in multi-objective problems. In this paper, an algorithm to compute the convex hull of Pareto optimal policies that consider expected costs and probabilities of falling below given budgets is developed. The approach uses the recently published class of PH-graphs that allow one to map SSPPs, even with generally distributed and correlated costs associated to edges, on Markov decision processes (MDPs) and apply the available techniques for MDPs to compute optimal policies.
Einheitliches Management serviceorientierter Systeme in einer Multi-Provider-Umgebung
(2019) Fiehe, Christoph; Krumm, Heiko; Geihs, Kurt
Die zunehmende Digitalisierung der Geschäfts- und Alltagswelt stellt die heutige Unternehmens-IT vor immer größer werdende Herausforderungen. Die Unternehmen sind gezwungen, ihre Prozesse kontinuierlich zu optimieren und an veränderte Rahmen- und Marktbedingungen anzupassen. Die IT muss mit diesem Wandel Schritt halten. Als ein strategisches IT-Konzept bietet das Cloud-Computing die Möglichkeit, die IT-Landschaft bedarfsorientiert nach dem Baukastenprinzip zusammenzustellen. In den seltensten Fällen wird aber ein einzelner Anbieter über ein passendes Leistungsangebot verfügen, das sämtliche funktionalen und nicht-funktionalen Anforderungen abdeckt. Der Weg hin zu einer Multi-Provider-Umgebung ist somit vorgezeichnet und bereits durch Trends belegt. Allerdings stellt das einheitliche Management einer Multi-Provider-Umgebung, die neben cloudbasierten auch virtuelle und physikalische Umgebungen umfasst, eine Herausforderung dar. Die anforderungsgerechte Bereitstellung und der gütegesicherte Betrieb von Services erfordern den flexiblen Einsatz aller am Verbund beteiligten Ausführungsumgebungen. Im Rahmen dieser Arbeit wird dafür eine Lösung entwickelt. Die Grundlage bildet ein Informationsmodell, das managementrelevante Ressourcen durch Managementobjekte einheitlich repräsentiert. Dazu werden Managementobjektklassen und ihre Beziehungen untereinander festgelegt. Managementobjektklassen verfügen über öffentliche Eigenschaften, die in Form von Managementvariablen modelliert werden. Mit Hilfe von Statusvariablen kann sich der Manager über den Ressourcenzustand informieren, und mit Hilfe von Konfigurationsvariablen kann er auf den Ressourcenzustand einwirken. Das Management einer Multi-Provider-Umgebung erfordert den Einsatz eines Managementsystems, das den fehlerfreien Servicebetrieb sicherstellt. Dazu gilt es, die vom Informationsmodell festgelegten Managementobjekte zur Laufzeit bereitzustellen und zu verwalten. Die Umsetzung wird dadurch erschwert, dass nicht nur eine einzelne Managementarchitektur zum Einsatz kommt, sondern zumeist mehrere. Dies setzt den Einsatz einer Datenstruktur voraus, die zur Informationsintegration verschiedenste Datenquellen anbinden kann. Dadurch lässt sich die Heterogenität überwinden und eine einheitliche Sicht auf die Managementinformationen erzeugen. Zur Gewährleistung der nicht-funktionalen Eigenschaften bedarf es neben der kontinuierlichen Überprüfung der Zieleinhaltung auch des Einsatzes adaptiver Maßnahmen, um den sich abzeichnenden Zielverfehlungen entgegenzuwirken. Hierfür kommen Policy-Regeln zum Einsatz, die die Multi-Provider-Umgebung überwachen und steuern. Im Rahmen eines Anwendungsfalls wird der experimentelle Nachweis erbracht, dass sich nicht-interaktive Services auf Basis des Informationsmodells und der Policy-Regeln in einem Verbund von heterogenen Ausführungsumgebungen flexibel bereitstellen und gütegesichert erbringen lassen.
Policy-based management of medical devices and applications
(2018) Litvina, Anna; Krumm, Heiko; Hein, Andreas
Die Arbeit präsentiert einen erweiterten Ansatz zum autonomen technischen Management, der das innovative Modell-basierte Management mit dem etablierten Policy-basierten Management kombiniert. Zur Planung des Systems wird ein umfassendes Modell des Management- und des zu verwaltenden Systems entworfen. Beide Systeme werden auf drei Abstraktionsschichten („Use Cases“, „Services“, „Components“) modelliert. Auf Basis der vorgestellten Ableitungsmuster (Evaluierungs-, Kontroll- und Verfeinerungsmuster) und der Zwischenschichtassoziationen wird der Prozess der Ableitung der Management-Policies automatisiert mit Hilfe eines Modellierungstools durchgeführt. Am Ende werden die zur Laufzeit vom Management ausführbaren Policies generiert. Der Ansatz wird im Rahmen des medizinischen Anwendungsfeldes erprobt. Es wird gezeigt, dass der Ansatz die Entwicklung und Verlässlichkeit sowie den Betrieb des medizinischen Geräte- und Anwendungsensembles unterstützt.
Markov decision processes with uncertain parameters
(2018) Scheftelowitsch, Dimitri; Buchholz, Peter; Hermanns, Holger
Markov decision processes model stochastic uncertainty in systems and allow one to construct strategies which optimize the behaviour of a system with respect to some reward function. However, the parameters for this uncertainty, that is, the probabilities inside a Markov decision model, are derived from empirical or expert knowledge and are themselves subject to uncertainties such as measurement errors or limited expertise. This work considers second-order uncertainty models for Markov decision processes and derives theoretical and practical results. Among other models, this work considers two main forms of uncertainty. One form is a set of discrete scenarios with a prior probability distribution and the task to maximize the expected reward under the given probability distribution. Another form of uncertainty is a continuous uncertainty set of scenarios and the task to compute a policy that optimizes the rewards in the optimistic and pessimistic cases. The work provides two kinds of results. First, we establish complexity-theoretic hardness results for the considered optimization problems. Second, we design heuristics for some of the problems and evaluate them empirically. In the first class of results, we show that additional model uncertainty makes the optimization problems harder to solve, as they add an additional party with own optimization goals. In the second class of results, we show that even if the discussed problems are hard to solve in theory, we can come up with efficient heuristics that can solve them adequately well for practical applications.
Stochastic graph models with phase type distributed edge weights
(2017) Dohndorf, Iryna; Buchholz, Peter; Haverkort, Boudewijn R.
Most stochastic shortest path problems include an assumption of independent weights at edges. For many practical problems, however, this assumption is often violated indicating an increased number of applications with stochastic graphs where edge weights follow a distribution that has a possible correlation with weights at adjacent edges. Real-world information in conjunction with existing dependencies in networks can significantly contribute to the computation of the optimal solution to stochastic shortest path problems. For example, the knowledge of a congestion arising on the current road results in a better traveler's choice of an alternative route. Markov dependability models describing the correlation in the length of availability and unavailability intervals of technical components could support optimal decisions to avoid high maintenance costs. In this thesis, an innovative model class for stochastic graphs with correlated weights at the edges is introduced. In the developed model edge weights are modeled by PH distributions and correlations between them can be encoded using transfer matrices for PH distributions of adjacent edge weights. Stochastic graph models including correlations are important to describe many practical situations where the knowledge about system parameters like traveling times and costs is incomplete or changes over time. Based on PH-Graphs efficient solution methods for Stochastic Shortest Path Problems with correlations can be developed. Competing paths from origin to destination in a PH-Graph can be interpreted as CTMDPs. Optimal solutions to different shortest path problems can be obtained from finding an optimal policy in a CTMDP. For example, the problem of finding the reliable shortest path to maximize the probability of arriving on time under realistic assumptions can be efficiently treated. Formulations of shortest path problems with correlations as well as solution methods from the CTMDP field are presented. We address the parameterization of PH-Graphs based on measured data from simulated systems. Fitting methods for parameterization of transfer matrices are adopted from MAP fitting approaches. Also similarity transformations for order 2 acyclic PHDs in composition are considered. Our experiments and examples show that correlation has a significant impact on shortest paths in stochastic weighted networks and that our solution methods are effective and usable in online decision senarios.
Flexible Kommunikation in effizient entwickelten adaptiven vernetzten Dienste- und Gerätesystemen
(2016) Dohndorf, Oliver; Krumm, Heiko; Timmermann, Dirk
Die fortschreitende Miniaturisierung der IT-Landschaft und die zunehmende Mobilität durch die Ausbreitung von Funkstandards schufen Voraussetzungen um im Sinne des Internet der Dinge Geräte des Alltags miteinander zu vernetzen und so IT-basierte Systeme zu erschaffen, die unterstützend in Situationen des menschlichen Lebens eingreifen. Diese Umgebungen werden im allgemeinen als ambiente Systeme bezeichnet. Für die Integration von Geräten und Diensten unterschiedlicher Hersteller und Anwendungsgebiete werden Domänen übergreifende Frameworks benötigt, die dem Nutzer unabhängig von der Hardware das komfortable und effiziente Entwickeln ambienter Systeme ermöglicht. Die vorliegende Arbeit beschreibt dafür die wichtigsten Anforderungen und stellt einige existierende Frameworks vor. Für den Ansatz der OSGi Remote Services wird die vom Autor realisierte Middleware Comoros vorgestellt, die den Standard mit dem Devices Profile for Web Services kombiniert. Dadurch entsteht eine standardkonforme Lösung, welche die Dynamik der OSGi-Plattform mit der Webservice basierten Kommunikation für Kleinstgeräte kombiniert. Von dieser Lösung ausgehend wurde Comoros um Bereiche erweitert, die für die Entwicklung verteilter ambienter Systeme notwendig sind. Neben einem dynamischen und komfortablen Ansatz für das Daten-Marshaling umfasst die Comoros-Erweiterung auch eine Event-basierte Kommunikation und eine umfassende und einfache Integration von Altsystemen. Weiterhin wird die Hersteller unabhängige Integration von Geräten in die Service-Plattform beschrieben, die für den Einsatz im IoT-Umfeld eine besondere Bedeutung hat. Um auf wechselnde Anforderungen dynamisch reagieren zu können setzt Comoros zudem etablierte Management-Standards um und kann so an die jeweils gültige Anforderung adaptiert werden. Um die Umsetzung der definierten Anforderungen von Comoros zu belegen wurde eine umfangreiche Evaluierung durchgeführt. Der Fokus dieser Evaluierung liegt dabei auf der Vermessung der Effizienz und Leistungsfähigkeit der Middleware, Eigenschaften, die bei einem Einsatz in Ressourcen beschränkten Umgebungen von besonderem Interesse sind. Zusätzlich wurde auch der Entwicklungskomfort vermessen, der Indikator für eine hohe Benutzerakzeptanz ist.
SLA Calculus
(2014) Vastag, Sebastian; Buchholz, Peter; German, Reinhard
For modeling Service-Oriented Architectures (SOAs) and validating worst-case performance guarantees a deterministic modeling method with efficient analysis is presented. Upper and lower bounds for delay and workload in systems are used to describe performance contracts. The SLA Calculus allows one to combine model descriptions for single systems and to derive bounds for reaction time and capacity of composed systems with analytic means. The intended, but not exclusive modeling domain for SLA Calculus are distributed software systems with reaction time constraints. SOAs are a system design paradigm that encapsulate software functions in service applications. Due to their standardized interfaces and accessibility via networks, large systems can be composed from smaller services and presented as services again. A well-known implementation of the service paradigm are Web Services that allow applications with components connected by the Internet. Own services and those rented from providers can be transparently combined by users. Performance guarantees for SOAs gain importance with more complex systems and applications in business environments When a service is rented by a customer the provider agrees upon a Service Level Agreement (SLA) with conditions concerning interface, pricing and performance. Service reaction time in form of delay is an important part in many SLAs and subject to performance models discussed in this work. With SLAs providers implicate a maximum delay for their products when the customer limits the workload to their systems. Hence customers expect the contracted service provider to deliver the performance figures unless the workload exceeds the SLA. Since contract penalties could apply, providers have a natural interest in dimensioning their service in regard to the SLA. Even for maximum workloads specified in the contracts the worst-case delay has to hold. Moreover, due to the compositional nature of Web Services, customers become providers themselves when they offer their service compositions to others. Again, worst-case performance bounds are of major interest here. Analyzing models of SOAs is an option to plan, dimension and validate service performance. For system modeling and analysis many methods exist. Queueing Systems and simulation are two well-known approaches in computer science. They provide average and thus long-term performance numbers quite easily using, probabilistic workload and service process descriptions. Deriving system behavior in worst-case situations for performance guarantees is elaborative and can be impossible for more complex systems. Receiving delay bounds usable in SLAs for SOAs by model analysis is still a research issue. A promising candidate to model SOA with SLAs is Network Calculus, an analytical method to derive performance bounds for network components. Given deterministic descriptions for arrival to and service in a network node hard bounds for network delay and the required buffer memory in routers are computed. A fine-granular separation between short- and long-term goals is possible. Network Calculus models also feature composition of elements and fast analytical analysis. When applied to SOAs with SLAs the problem arises that SLAs are not suitable as a system description and information source for Network Calculus models. Especially the internal service capacity is not exposed by SLAs, since providers consider them as a business secret. Without service process descriptions Network Calculus models cannot be analyzed. The SLA Calculus is presented as a solution to this problem. As a novel contribution for deterministic model analysis for SOAs, SLA Calculus is an extension to Network Calculus. Instead of service process descriptions, it uses information on latency to characterize a system. Delay of services is not a scalar analysis result anymore, it becomes a process over time that is bound with Network Calculus-style curves, the delay curves. Together with arrival curves the performance contracts in SLAs are formalized by so-called SLA Delay Properties (SDPs) as a description for the service performance in worst-case. Service composition can be modeled by serial and parallel combination of SDPs. The necessary theorems for the resulting worst-case bounds are given and proved. We will present a method to transfer these performance figures to the missing service process description again. Apart from basic theory we will also consider solutions for practical modeling situations. An algorithm to extract arrival and delay curves from measurements, enables the modeler to include already existing systems without given SLAs as model elements. Finally, we will sketch a selection method in form of an optimization problem for services to support the dynamic service selection in SOAs with a Service Broker. SLA Calculus model analysis will deliver deterministic upper and lower bounds for workload capacities and response times. For upper bounds the worst-case is assumed, thus bounds are pessimistic. The advantage of SLA Calculus is the ability to compute these bounds very fast and to give system modelers a quick overview on system characteristics considering extreme situations. In other modeling methods a lengthy transient analysis would be required. The strict perspective towards worst-case brought up another analysis target: Until now, relatively little attention was paid to contract conformance between subsequent services within service compositions. When services offer different workload capacities the arrival rate to the system needs to be adjusted to avoid bottlenecks. Additionally, for service compositions no response time contract can be guaranteed without internal buffering to enforce a common arrival rate. SLA Calculus unveils the necessary buffer delays and is able to bound them.
Fitting simulation input models for correlated traffic data
(2012-02-15) Kriege, Jan; Buchholz, Peter; Weihs, Claus
The adequate representation of input models is an important step in building valid simulation models. Modeling independent and identically distributed data is well established in simulation, but for some application areas like computer and communication networks it is known, that the assumption of independent and identically distributed data is violated in practice and that for example interarrival times or packet sizes exhibit autocorrelation over a large number of lags. Moreover, it is known that negligence of these correlations can result in a serious loss of validity of the simulation model. Although different stochastic processes, which can model these autocorrelations, like e.g. Autoregressive-To-Anything (ARTA) processes and Markovian Arrival Processes (MAPs), have been proposed in the past and more recently fitting algorithms to set the parameters of these processes such that they resemble the behavior of observations from a real system have been developed, the integration of correlated processes into simulation models is still a challenge. In this work ARTA processes are extended in several ways to account for the requirements when simulating models of computer and communication systems. In a first step ARTA processes are extended to use an Autoregressive Moving Average (ARMA) process instead of a pure Autoregressive (AR) base process to be able to capture a large number of autocorrelation lags, while keeping the model size small. In a second step they are enabled to use the flexible class of acyclic Phase-type distributions as marginal distribution. To support the usage of these novel processes in simulation models a fitting algorithm is presented, software for fitting and simulating these processes is developed and the tools are integrated into the toolkit ProFiDo, which provides a complete framework for fitting and analyzing different stochastic processes. By means of synthetically generated and real network traces it is shown that the presented stochastic processes are able to provide a good approximation of the marginal distribution as well as the correlation structure of the different traces and result in a compact process description.
Anpassungen von Suchheuristiken für ereignisdiskrete Modelle
(2010-12-08) Müller, Dennis; Buchholz, Peter; Rudolph, Günter
Ereignisdiskrete Modelle ermöglichen die Abbildung einer Vielzahl von Systemen. Eine wichtige Fragestellung bei der Betrachtung dieser Modelle ist die Bestimmung einer für einen bestimmten Zweck optimalen Modellvariante. In der Regel besteht die Aufgabe darin, eine optimale Konfiguration aus einer Menge möglicher Konfigurationen auszuwählen und anschließend umzusetzen. Die systematische Untersuchung, Bewertung und Modifikation solcher Modelle ist ein zeitintensiver Prozess, da zum einen die Menge der möglichen Konfigurationen in der Regel sehr groß und der Analyseaufwand sehr hoch ist. Daher werden Optimierungsverfahren und Suchheuristiken benötigt, um diesen Prozess zu unterstützen. In dieser Arbeit werden vor allem Kriging Metamodell basierte Verfahren auf ihre Einsetzbarkeit in diesem Gebiet untersucht und entsprechend der Anforderungen von ereignisdiskreten Modellen und deren Analysemethoden angepasst. Insbesondere werden hierarchische Kriging Metamodelle zur Reduktion der Rechenzeit und zur Erhöhung der Approximationsgenauigkeit entwickelt. Weitere Untersuchungen befassen sich mit der Kombination von Kriging Metamodell basierten Verfahren mit lokalen Suchheuristiken sowie "Ranking and Selection"-Verfahren.
Korrekte Steuerungssoftware
(2010-05-31T09:29:46Z) Graw, Günter; Krumm, Heiko; Herrmann, Peter
Integrated formal modeling and automated analysis of computer network attacks
(2007-03-19T12:47:59Z) Rothmaier, Gerrit; Krumm, Heiko; Biskup, Joachim
Die vorhandenen Ansätze zur formalen Modellierung und Analyse von Computernetzwerksicherheit sind entweder auf eine Protokoll-, Knoten-, oder Netzwerksicht ausgerichtet. Meist beschränken sie sich sogar auf einen speziellen Teilbereich einer dieser Sichten (z.B. eine bestimmte Art von Protokollen, die Interaktion zwischen den lokalen Komponenten eines Knotens, oder die Ausbreitung vordefininierter Verletzlichkeiten). Insgesamt wird von jedem Ansatz jeweils nur ein kleiner Teil der Aspekte, die in praktischen Computernetzwerkangriffsszenarien vorkommen, abgedeckt. Hinzu kommen oft weitere Einschränkungen in Bezug auf Unterstützung dynamischer Änderungen, modellier- und untersuchbare Eigenschaften, benötigte Unterstützung der Analyse durch den Benutzer, usw. Um eine vollständigere Sicht auf Computernetzwerkangriffsszenarien zu erhalten, müssen daher mehrere Ansätze, und damit auch Modelle, Formalismen und Werkzeuge, eingesetzt werden. Sowohl die Modellierungs- als auch die Analysearbeit fallen damit mehrfach an und Konsistenz zwischen den verschiedenen Modellen und Analyseergebnissen lässt sich nur sehr schwer erreichen. In dieser Arbeit wird ein neuartiger Ansatz vorgestellt, der die Protokoll-, Knoten und Netzwerksicht auf mittlerer Detailebene übergreifend integriert. Die Modelle sind ausdrucksstark genug, um dynamische Änderungen zu beinhalten. Vielfältige Eigenschaften können über unterschiedliche Mechanismen spezifiziert werden. Da integrierte Modelle deutlich komplexer als eingeschränkte Modelle für einen Teilbereich sind, ist die Analyse besonders schwierig. Im Allgemeinen schlagen Ansätze zur automatischen Analyse schnell durch Zustandsraumexplosion fehl. Durch eine intelligente Modellierung, die Berücksichtigung von Optimierungsmöglichkeiten auf allen Ebenen, die Modellierung mit einer objektorientieren und kompositionalen, aber trotzdem auf einer einfachen Struktur basierenden Sprache, und dem Einsatz eines dem aktuellen Stand der Forschung entsprechenden Analysewerkzeuges sind wir trotzdem in der Lage, erfolgreich automatisiert zu analysieren. Unser Ansatz basiert auf der Spezifikationshochsprache CTLA 2003, einem Framework zur Modellierung von Computernetzwerkangriffsszenarien, einem Übersetzungsschema von CTLA 2003 nach PROMELA, dem CTLA2PC Übersetzungs- und Optimierungswerkzeug, und dem mächtigen Modellchecker SPIN. Die Durchführbarkeit unseres Ansatzes wird durch die Modellierung und Analyse von drei dynamischen Netzwerkszenarien zunehmender Komplexität aufgezeigt. In diesen Szenarien werden konkrete Angriffsfolgen als Verletzungen vorgegebener Sicherheitseigenschaften automatisch aufgedeckt.
Measurement techniques and case studies for the characterization of Internet applications
(2006-07-13T10:33:41Z) Klemm, Alexander; Lindemann, Christoph; Krumm, Heiko
This thesis characterizes the two current killer applications of the Internet: World Wide Web (WWW) and Peer-to-Peer (P2P) file sharing. With the advances in network technology and radical cost reduction for Internet connectivity the Internet grows at an awesome speed in terms of number of users, available content and network traffic. Due to the huge amount of available data, developing algorithms to efficiently locate desired information is a difficult research task. Thus, the characterization of the two most popular Internet applications, which enables the design and evaluation of novel search algorithms, constitutes the two key contributions of this work. As first contribution, this thesis provides a synthetic workload model for the query behavior of peers in P2P file sharing systems which can be used for evaluating new P2P system designs. Whereas previous work has solely focused on aggregate workload statistics, this thesis presents a characterization of individual peer behavior in a form that can be used for constructing representative synthetic workloads. The characterization is based on a comprehensive 40 days measurement study in the Gnutella P2P file sharing system comprising more than 10 GBytes of trace data. As a key feature, the characterization distinguishes between user behavior and queries that are automatically generated by the client software. The analysis of the measured data exposes heterogeneous behavior that occurs on different days, in different geographical regions or at different periods of the day. Moreover, the consideration of additional correlations among the workload measures allows the generation of realistic workloads. As second contribution, this thesis characterizes and models the structural properties of German Web sites for enabling their automated classification. These structural properties encompass the size, the organization, the composition of URLs, and the link structure of Web sites. In fact, the approach is independent of the content of Web pages. Opposed to previous work, this thesis characterizes structural properties of entire Web sites instead of individual Web pages. The measurement study is based upon more than 2,300 Web sites comprising 11 million crawled pages categorized into five major classes: Brochure, Listing, Blog, Institution, and Personal. As a key insight which can be exploited for improving Internet search engines and Web directories, this thesis reveals significant correlations between the structural properties and the class of a Web site.
Approximative Verfahren auf erweiterten Fork/Join-Warteschlangennetzen zur Analyse von Logistiknetzen
(2006-03-13T06:34:14Z) Arns, Markus; Beilner, Heinz; Buchholz, Peter
Die Modellierung und Analyse Diskreter Ereignisorientierter Dynamischer Systeme (DEDS) ist in der Informatik seit langer Zeit ein wichtiger Themenschwerpunkt. In diesem Kontext haben sich Warteschlangennetze insbesondere im Anwendungsgebiet Computer und Kommunikationssysteme aufgrund der Verfügbarkeit sehr zeit– und platzeffizienter analytisch–algebraischer Analyseverfahren als adäquater Modellformalismus bewährt. Die Verfügbarkeit dieser Methoden in integrierten Modellierungs– und Analysewerkzeugen einerseits und die Interpretation alternativer Anwendungsfäalle als DEDS andererseits legen den Wunsch nahe, das Warteschlangeninstrumentarium auf weitere Anwendungsgebiete anzupassen. Speziell in der Logistik kommt der optimalen Planung, Steuerung und Optimierung von Systemen und damit deren Modellierung und Analyse eine entscheidende Bedeutung zu, da der Erfolg vieler Industrieunternehmen in zunehmendem Maße von der optimalen Auslegung ihrer Logistik beeinflußt wird. Das Warteschlangeninstrumentarium läßt sich häufig zur Analyse sehr grober logistischer Prozeßketten einsetzen, es versagt jedoch für detaillierte Modelle, da die effizienten algebraischen Analyseverfahren einigen typischen Eigenschaften logistischer Systeme nicht zugänglich sind. Mit dieser Motivation liegt das Ziel der vorliegenden Dissertation darin, einen Beitrag hinsichtlich der Anpassung der effizienten Analyseverfahren für Warteschlangennetze auf Prozeßketten zu leisten. Spezielles Augenmerk wird auf den Aspekt der Synchronisation komplexer paralleler Abläufe gelegt, der essentieller Bestandteil vieler logistischer Systeme ist. Aufgrund seiner hohen Flexibilität wird zur Analyse von Prozeßketten das Dekompositionsverfahren nach Kühn/Whitt herangezogen. Diese Methode ist ein approximatives Verfahren zur stationären Analyse einer recht allgemeinen Klasse offener Warteschlangennetze. Die Idee dieses Verfahrens liegt in der Zerlegung eines Warteschlangennetzes in Teilnetze, die isoliert voneinander analysiert werden. Die Interaktion der Teilnetze untereinander wird über das Input/Output–Verhalten hergestellt. Durch die Beschreibung der Netzlast durch sog. Phasenverteilungen wird die Analyse der isolierten Stationen auf die Betrachtung sog. Quasi–Birth–and–Death Prozesse zurückgeführt, die sich anhand Matrix–geometrischer Methoden effizient analysieren lassen. Zur Berücksichtigung paralleler Abläufe wird das Dekompositionsverfahren zunächst um die Analyse eines sehr einfachen Typs sog. Fork/Join–Netze angereichert. Die isolierte Analyse einfacher Fork/Join–Netze basiert auf einem von Balsamo vorgestellten approximativen Modell (Upper-Bound Modell). Im Zentrum der Arbeit steht die Entwicklung einer neuen umgebungsabhägigen Aggregierungstechnik, die es erlaubt, die Analyse komplexer, erweiterter Fork/Join–Netze auf die Analyse einfacher Fork/Join–Netze zurückzuführen. Die Aggregate haben die Eigenschaft, daß sie komplexe Warteschlangennetze hinsichtlich der ersten beiden Momente der Durchlaufzeitverteilung exakt durch FCFS–Single-Server Stationen ersetzen. Die erarbeitete Technik zur Analyse erweiterter Fork/Join–Warteschlangennetze wird anhand zweier Beispiele aus dem Anwendungskontext Logistik und anhand einer Internet–basierten Meta–Suchmaschine erprobt. Zur Beurteilung der Approximationsgüte werden die erzielten Analyseresultate mit Simulationsergebnissen verglichen. Dabei werden fallweise sehr zufriedenstellende Approximationsgüten erreicht.
Parallele numerische Verfahren zur quantitativen Analyse logistischer Systeme
(2006-02-27T14:37:36Z) Fischer, Markus; Beilner, Heinz; Buchholz, Peter
In der vorliegenden Arbeit wird ein numerisches Verfahren zur Lösung sehr großer Markov- Ketten vorgestellt und seine prinzipielle Eignung und Performance experimentell untersucht. Das Verfahren basiert auf hierarchischen und asynchronen Iterationen, nutzt eine hierarchische Kronecker-Darstellung zur Darstellung der Markov-Kette und ist auf einer parallelen Rechenarchitektur mit verteiltem Speicher implementiert. Die Arbeit dokumentiert die Lösung von Markov-Ketten mit bis zu 900 Millionen Zuständen, die aus dem Anwendungsfeld der Logistik resultieren.
Design and quantitative analysis of protocols for epidemic information dissemination in mobile ad hoc networks
(2005-11-29T12:47:35Z) Waldhorst, Oliver P.; Lindemann, Christoph; Buchholz, Peter
This thesis explores the field of protocols for epidemic information dissemination (EID) that constitute a novel way to implement peer-to-peer communication in Mobile Ad Hoc Networks (MANET). Such protocols exploit device mobility and transmit information when mobile devices encounter, similar to the spread of an infectious disease among individuals. The contribution of this thesis is three-fold. As first contribution, a general-purpose distributed lookup service for MANET is presented. The lookup service, denoted as Passive Distributed Indexing (PDI), builds upon epidemic dissemination of index information. It differs from previously proposed EID systems in three major aspects: (1) PDI can be employed for key-to-value lookups in arbitrary mobile applications. (2) PDI explicitly considers the limited availability of memory resources on mobile devices by using buffers of finite capacity and employing Least Recently Used (LRU) replacement when the buffer capacity is exceeded. (3) PDI provides consistency mechanisms for ensuring coherence of disseminated information. A comprehensive simulation study illustrates that PDI is well-suited to implement consistent lookup operations in various mobile applications. As second contribution, this thesis presents a design study of mechanisms for disseminating frequently changing presence information in a mobile instant messaging system. The study extends previous work in three major aspects: (1) It introduces sustained consistency as a novel measure for the coherence of the disseminated presence information. (2) It evaluates different alternative approaches for disseminating presence information with respect to sustained consistency and control traffic and identifies an epidemic approach as the method of choice. (3) It proposes the System for Presence information Exchange by Epidemic Dissemination (SPEED). As illustrated in a comprehensive performance study, SPEED outperforms an approach based on optimized flooding of presence information with respect to sustained consistency and control traffic. As third contribution, this thesis presents a novel stochastic modeling approach for EID systems in MANET that differs from previous approaches in three major aspects: (1) It explicitly considers the spread of multiple data items as well as buffers with finite capacity and LRU replacement. (2) The approach conducts steady-state analysis rather than transient analysis. (3) The approach does not require offline simulations to determine model parameters. It is shown that an EID system with finite buffer can be modeled by discrete-time Markov chains with a state space that grows exponentially with the number of nodes and data items in the EID system. Since a numerical steady-state solution with state-of-the-art methods is computationally infeasible, an approximate solution approach is presented and applied for modeling the Seven Degrees of Separation (7DS) EID system. A comparison of the approximate results to the results of a detailed simulation study shows an excellent agreement. Furthermore, a comprehensive performance study provides key insight into the steady-state behavior of 7DS.
Online QoS/Revenue Management for Third Generation Mobile Communication Networks
(Universität Dortmund, 2004-07-13) Lohmann, Marco; Lindemann, Christoph; Krumm, Heiko
This thesis shows how online management of both quality of service (QoS) and provider revenue can be performed in third generation (3G) mobile networks by adaptive control of system parameters to changing traffic conditions. As a main result, this approach is based on a novel call admission control and bandwidth degradation scheme for real-time traffic. The admission controller considers real-time calls with two priority levels: calls of high priority have a guaranteed bit-rate, whereas calls of low priority can be temporarily degraded to a lower bit-rate in order to reduce forced termination of calls due to a handover failure. A second contribution constitutes the development of a Markov model for the admission controller that incorporates important features of 3G mobile networks, such as code division multiple access (CDMA) intra- and inter-cell interference and soft handover. Online evaluation of the Markov model enables a periodical adjustment of the threshold for maximal call degradation according to the currently measured traffic in the radio access network and a predefined goal for optimization. Using distinct optimization goals, this allows optimization of both QoS and provider revenue. Performance studies illustrate the effectiveness of the proposed approach and show that QoS and provider revenue can be increased significantly with a moderate degradation of low-priority calls. Compared with existing admission control policies, the overall utilization of cell capacity is significantly improved using the proposed degradation scheme, which can be considered as an 'on demand' reservation of cell capacity.To enable online QoS/revenue management of both real-time and non real-time services, accurate analytical traffic models for non real-time services are required. This thesis identifies the batch Markovian arrival process (BMAP) as the analytically tractable model of choice for the joint characterization of packet arrivals and packet lengths. As a key idea, the BMAP is customized such that different packet lengths are represented by batch sizes of arrivals. Thus, the BMAP enables the 'two-dimensional', i.e., joint, characterization of packet arrivals and packet lengths, and is able to capture correlations between the packet arrival process and the packet length process. A novel expectation maximization (EM) algorithm is developed, and it is shown how to utilize the randomization technique and a stable calculation of Poisson jump probabilities effectively for computing time-dependent conditional expectations of a continuous-time Markov chain required by the expectation step of the EM algorithm. This methodological work enables the EM algorithm to be both efficient and numerical robust and constitutes an important step towards effective, analytically/numerically tractable traffic models. Case studies of measured IP traffic with different degrees of traffic burstiness evidently demonstrate the advantages of the BMAP modeling approach over other widely used analytically tractable models and show that the joint characterization of packet arrivals and packet lengths is decisively for realistic traffic modeling at packet level.
stochastic modeling and analysis of 3g mobile communication systems
(Universität Dortmund, 2003-08-11) Thümmler, Axel; Lindemann, Christoph; Beilner, Heinz
Third-generation (3G) mobile communication systems are currently one of the key communication technologies in research and development due to the high market demand for advanced wireless communication. The current evolution is primarily characterized by a transition from circuit-switched voice-oriented networks to integrated multi-service all IP networks. To effectively design complex mobile communication systems, the design process should be accompanied by stochastic modeling and quantitative evaluation of different design alternatives. The most popular language for model specification used in industrial projects is the Unified Modeling Language (UML). Although conceived as a general-purpose modeling language, the current version of the UML does not contain building blocks for introducing stochastic timing into UML diagrams.The first part of this thesis presents new results for numerical quantitative analysis of discrete-event stochastic systems specified in Petri net notation or as UML diagrams. An efficient algorithm for the state space generation out of an UML state diagram or activity diagram that allows quantitative analysis by means of the underlying stochastic process is presented. Furthermore, this thesis considers new methodological results for the effective numerical analysis of finite-state generalized semi-Markov processes with exponential and deterministic events by an embedded general state space Markov chain (GSSMC). Key contributions constitute (i) the observation that elements of the transition kernel of the GSSMC can always be computed by appropriate summation of transient state probabilities of continuous-time Markov chains and (ii) the derivation of conditions under which kernel elements are constant. To provide automated tool support, the presented algorithms are included in the software package DSPNexpress-NG available for download on the Web.The support of multimedia services over wireless channels presents a number of technical challenges. One of the major challenges is to effectively utilize the scarce radio bandwidth in the access network by adaptive control of system parameters. The second part of this thesis is devoted to this topic. A Markov model representing the sharing of radio channels by circuit-switched connections and packet-switched sessions under a dynamic channel allocation scheme is evaluated. Closing the loop between network operation and network control, a framework for the adaptive quality of service management for 3G mobile networks is introduced. Building on this framework, a novel call admission control and bandwidth reservation scheme for the optimization of quality of service for mobile subscribers is presented. The performance of the solutions proposed in this thesis is investigated experimentally based on numerical quantitative analysis and discrete-event simulation.

Browse

Recent Submissions