05 Fakultät Informatik, Elektrotechnik und Informationstechnik

Permanent URI for this collectionhttps://elib.uni-stuttgart.de/handle/11682/6

Browse

Search Results

Now showing 1 - 10 of 28

Open Access
Emulation von Rechnernetzen zur Leistungsanalyse von verteilten Anwendungen und Netzprotokollen
(2005) Herrscher, Daniel J.; Rothermel, Kurt (Prof. Dr. rer. nat. Dr. h. c)
Um die Leistung von verteilten Anwendungen und Netzprotokollen in Abhängigkeit von den Eigenschaften der verwendeten Rechnernetze zu analysieren, wird eine Testumgebung benötigt, die Netzeigenschaften zuverlässig nachbilden ("emulieren") kann. Eine solche Testumgebung wird Emulationssystem genannt. Bisher existierende Emulationssysteme sind aufgrund ihrer Architektur entweder nur für sehr kleine Szenarien geeignet, oder sie können nur unabhängige Netzverbindungen nachbilden, und schließen damit alle Netztechnologien mit gemeinsamen Medien aus. In dieser Arbeit werden zunächst verschiedene Architekturvarianten für die Realisierung eines Emulationssystems vorgestellt und bewertet. Für die Variante mit zentraler Steuerung und verteilten Emulationswerkzeugen wird dann detailliert die Funktionalität eines Emulationssystems mit seinen wesentlichen Komponenten beschrieben. Das in dieser Arbeit entwickelte Emulationsverfahren greift auf der logischen Ebene der Sicherungsschicht in den Kommunikationsstapel ein. Auf dieser Ebene werden die beiden Basiseffekte Rahmenverlust und Verzögerung durch verteilte Emulationswerkzeuge nachgebildet. Alle anderen Netzeigenschaften können auf diese Basiseffekte zurückgeführt werden. Um Netztechnologien mit gemeinsamen Medien durch verteilte Werkzeuge nachbilden zu können, wird zusätzlich das Konzept des virtuellen Trägersignals eingeführt. Hierbei werden die Eigenschaften eines Rundsendemediums nachgebildet, indem kooperative Emulationswerkzeuge Rundsendungen zur Signalisierung eines Trägersignals benutzen. Somit kann jedeWerkzeuginstanz lokal ein aktuelles Modell des emulierten gemeinsamen Mediums halten. Auf dieser Basis kann auch das Verhalten von Medienzugriffsprotokollen nachgebildet werden. Die Arbeit deckt auch die wesentlichen Realisierungsaspekte eines Emulationssytems ab. Mit ausführlichen Messungen wird gezeigt, dass das entwickelte System für die Nachbildung von Netzszenarien sehr gut geeignet ist, selbst wenn die nachzubildenden Parameter sich dynamisch ändern. Die entwickelten Werkzeuge sind in der Lage, Netzeigenschaften in einem weiten Parameterbereich realistisch nachzubilden. Mit diesem System steht nun eine ideale Testumgebung für Leistungsmessungen von verteilten Anwendungen und Netzprotokollen in Abhängigkeit von Netzeigenschaften zur Verfügung.
Open Access
Simulation and optimized scheduling of pedestrian traffic : from geometric modeling to pedestrian navigation
(2007) Narasimhan, Srihari; Bungartz, Hans-Joachim (Prof. Dr. rer. nat.)
Today, more and more simulation tasks with a traditionally non-geometric background need to be embedded into some geometric context, in order to provide spatial context to non-spatial data. This holds especially true for graph-based applications in some location-aware context. As an example, one might think of a theme park or a large commercial center, where the customers shall be provided with some navigation and scheduling information such as where to go and when - either a priori or even in real time via some mobile device. This can be done by analyzing the pedestrian traffic and waiting time situation by simulating the pedestrian movement and using the simulation data to optimally navigate and schedule the tasks that are to be executed by the customer. The main issues addressed in this thesis are as follows. Initially, a flexible simulation framework is built to simulate the pedestrian movement in a 3D scenario, for example, a commercial building. Since the pedestrians strongly interact with the environment surrounding them, the geometry is taken into account. Architectural data such as paths, type and capacity of the paths, destinations and its properties, etc., is extracted from the CAD-model and are organized in a graph structure. The movement of the pedestrians and the waiting queues at the destinations are modeled as queuing systems using the discrete event simulation technique. These queuing systems are then embedded into the geometry model. The necessary input modeling parameters are also defined. The resulting scenario, when simulated, gives an overview of congestions and waiting times across the scenario for different time stages. Apart from the simulation, the geometry data - or here the graph - is hierarchically organized in an octree structure. An octree-based model is chosen since octrees have the natural property of hierarchically storing 3D data. The octree data is used to identify the position of the pedestrian within the scenario. The potential destinations in the neighborhood that can be visited by the customer are also identified using neighbor search algorithms. Combining the simulation data with the octree modeling, the customer is navigated to the optimal destination. Furthermore, when visiting several destinations, combinatorial optimization methods are used to optimally schedule the set of tasks to be executed by the customer. The optimization methods take into account the congestion information obtained from the simulation data, and the octree structure for navigation. This approach results in an effective pedestrian navigation system.
Open Access
Consistent data replication in mobile ad hoc networks
(2007) Hähner, Jörg; Rothermel, Kurt (Prof. Dr.)
Mobile ad-hoc networks (MANETs) are used in situations where networks need to be deployed immediately but no network infrastructure is available. If MANET nodes have sensing capabilities, they can capture and communicate the state of their surroundings, including environmental conditions or objects in their proximity. If the sensed state information is propagated to a database to build a consistent model of the real world, a variety of promising context aware applications becomes possible. The models and concepts proposed in this dissertation can be applied to cooperatively maintain a model of the state of physical world objects on devices in MANETs. State information may be updated by independent observers either sequentially or concurrently. Applications that read the state of any object from the model multiple times can rely on the guarantee that every successive read operation will read either the same state information or newer state information that has been reported by an observer after the previously read information. The first contribution of this dissertation formalizes these requirements and defines a novel consistency model called update-linearizability. Secondly, it introduces a new class of data replication algorithms that provably guarantees update-linearizability in MANETs without using synchronized clocks on any pair of nodes in the system. The presented algorithms allow executing read and write operations at any time, which provides high availability of data. These properties are even maintained in networks that are temporarily partitioned and where nodes are highly mobile. Finally the dissertation provides a proof that all replicas held in the system eventually converge towards the most recent state information of the physical world objects which they represent.
Open Access
System support for adaptive pervasive applications
(2009) Handte, Marcus; Rothermel, Kurt (Prof. Dr. rer. nat. Dr. h. c.)
Driven by the ongoing miniaturization of computer technology as well as the proliferation of wireless communication technology, Pervasive Computing envisions seamless and distraction-free task support by distributed applications that are executed on computers embedded in everyday objects. As such, this vision is equally appealing to the computer industry and the user. Induced by various factors such as invisible integration, user mobility and computer failures, the resulting computer systems are heterogeneous, highly dynamic and evolving. As a consequence, applications that are executed in these systems need to adapt continuously to their ever-changing execution environment. Without further precautions, the need for adaptation can complicate application development and utilization which hinders the realization of the basic vision. As solution to this dilemma, this dissertation describes the design of system software for Pervasive Computing that simplifies the development of adaptive applications. As opposed to shifting the responsibility for adapting an application to the user or the application developer, the system software introduces a component-based application model that can be configured and adapted automatically. To enable automation at the system level, the application developer specifies the dependencies on components and resources in an abstract manner using contracts. Upon application startup, the system uses the contractual descriptions to compute and execute valid configurations. At runtime, it detects changes to the configuration that require adaptation and it reconfigures the application. To compute valid configurations upon application startup, the dissertation identifies the requirements for configuration algorithms. Based on an analysis of the problem complexity, the dissertation classifies possible algorithmic solutions and it presents an integrated approach for configuration based on a parallel backtracking algorithm. Besides from scenario specific modifications, retrofitting the backtracking algorithm requires a problem mapping from configuration to constraint satisfaction which can be computed on-the-fly at runtime. The resulting approach for configuration is then extended to support the optimization of a cost function that captures the most relevant cost factors during adaptation. This enables the use of the approach for configuration upon startup and reconfiguration during runtime adaptation. As basis for the evaluation of the system software and the algorithm, the dissertation outlines a prototypical implementation. The prototypical implementation is used for a thorough evaluation of the presented concepts and algorithms by means of real world measurements and a number of simulations. The evaluation results suggest that the presented system software can indeed simplify the development of distributed applications that compensate the heterogeneity, dynamics and evolution of the underlying system. Furthermore, they indicate that the algorithm for configuration and the extensions for adaptation provide a sufficiently high performance in typical applications scenarios. Moreover, the results also suggest that they are preferable over of alternative solutions. To position the presented solution within the space of possible and existing solutions, the dissertation discusses major representatives of existing systems and it proposes a classification of the relevant aspects. The relevant aspects are the underlying conceptual model of the system and the distribution of the responsibility for configuration and adaptation. The classification underlines that in contrast to other solutions, the presented solution provides a higher degree of automation without relying on the availability of a powerful computer. Thus, it simplifies the task of the application developer without distracting the user while being applicable to a broader range of scenarios. After discussing the related approaches and clarifying similarities and differences, the dissertation concludes with a short summary and an outlook on future work.
Open Access
Investigating dynamics by multilevel phase space discretization
(2006) Fundinger, Danny Georg; Levi, Paul (Prof. Dr.)
The subject of the thesis is the numerical investigation of dynamical systems. The aim is to provide approaches for the localization of several topological structures which are of vital importance for the global analysis of dynamical systems, namely, periodic orbits, the chain recurrent set, repellers, attractors and their domains of attraction as well as stable, unstable and connecting manifolds. The techniques introduced do not require any a priori knowledge about a system, and are also not restricted by the stability of the solution. Furthermore, they can generally be applied to a wide range of dynamical systems. Two theoretical concepts are considered to be at the center of the research - symbolic analysis and the RIM method. The underlying basic approach for both of them is multilevel phase space discretization. This means that a part of the phase space, the area of investigation, is subdivided in a finite number of sets. Then, instead of each point of the phase space, only these sets are subject of further analysis. The main target of every method proposed is to find those sets which contain parts of the solution and subdivide them into smaller parts until a desired accuracy is reached. In case of symbolic analysis, a directed graph is constructed which represents the structure of the state space for the investigated dynamical system. This graph is called the symbolic image of the focused system and can be seen as an approximation of the system flow. The theoretical background regarding the symbolic image graph as well as the constructive methods applied on it were already described in a series of works by G. Osipenko. In this work, strategies are introduced for a practical application. This requires the extension of the theoretical concepts and the development of appropriate algorithms and data structures. In practice, it turned out that these aspects are essential cornerstones for the usability of the discussed methods. Also some sophisticated tunings of the basic methods are proposed in order to extent the field of practical investigation. Although symbolic analysis can be seen as the main stimulation of this work, the investigation was not limited to it. Indeed, several shortcomings regarding the solution of some problems can be observed if the method is applied in practice. This led to the development of the RIM method. The core intention of the method is to solve the root finding problem. The standard approach toward this task is the application of an iteration scheme based on the Newton method. However, it has shown that such Newton schemes have several structural disadvantages which are especially crucial in the context of the fields of investigation which are relevant to this work. The RIM method proposes an alternative approach which does not require the application of any Newton-like method. Numerical case studies revealed that in several nontrivial scenarios the RIM method provides better results than both, symbolic analysis as well as Newton-based methods. Two applications of the RIM method for the investigation of dynamical systems are provided. One of them is the detection of periodic points. The other is the computation of stable manifolds. The proposed methods contribute not only to the direct investigation and simulation of specific dynamical processes but also to the research in the field of dynamical system theory in general. This is due to the fact that progress in theory depends to a large extent on the observation and investigation of phenomenons. These phenomenons can often only be revealed, analyzed and verified by numerical experiments. The presented numerical case studies give some concrete examples for the application of the methods. Hereby, the dynamical models are taken from different fields of scientific research, like geography, biology, meteorology, or physics.
Open Access
Reduktion von Verzögerungsunterschieden bei der Gruppenkommunikation im Internet
(2007) Klöcking, Jens-Uwe; Rothermel, Kurt (Prof. Dr.)
Eine Vielzahl neuer Anwendungsgebiete des Internets basiert auf der effizienten Übertragung einer Nachricht an eine Gruppe von Empfängern, der so genannten Gruppenkommunikation. Beispiele für derartige Anwendungen sind Nachrichten- und Softwareverteilung, verteilte Berechnungen, Videokonferenzen, Fernunterricht sowie Spiele. Die Netzwerkressourcen werden durch Gruppenkommunikation sehr effizient genutzt, denn das einmalige Senden einer Nachricht reicht aus, um von allen Teilnehmern einer Gruppe empfangen zu werden. Einige Einschränkungen der Dienstqualität derzeitiger Gruppenkommunikationslösungen im Internet behindern jedoch ihre generelle Nutzung. Hiervon betroffen ist unter anderem die Fairness bezüglich der Verzögerung der Nachrichtenauslieferung. Dieser spezielle Parameter der Gruppenkommunikation bezeichnet die Zeitspanne zwischen dem ersten und letzten Eintreffen einer Nachricht bei einer Gruppe von Empfängern. Messungen mittels eines dafür entwickelten passiven Verfahrens zeigen für einige Anwendungen nicht tolerierbare Verzögerungsunterschiede auf. Das Ziel der Arbeit besteht darin, die Verzögerungsunterschiede zu minimieren, um einen fairen Dienst für nicht kooperative Anwendungen der Gruppenkommunikation im Internet, wie z. B. Informationsdienste und elektronische Märkte bereitzustellen. Zur Lösung des Problems wurden drei Ansätze erarbeitet. Durch den Einsatz von Servern konnten Verzögerungsunterschiede der Nachrichten ausgeglichen werden. Die in der Anwendungsschicht angesiedelten Ansätze stellen keine besonderen Anforderungen an die Netzkomponenten und können daher schrittweise eingeführt werden. Darüber hinaus berücksichtigen sie die aktuelle Netzwerklast und sind so in der Lage, die Gesamtverzögerung der Nachrichtenauslieferung gering zu halten. In einem der Ansätze überwacht sichere Hardware in Form von Smart Cards direkt bei den Empfängern den Auslieferungszeitpunkt der Nachrichten. Hierfür wurden drei Protokolle entwickelt, die die Synchronisation der Smart-Card-Uhren, die Auslieferung der Daten und eine Rückmeldung der tatsächlichen Verzögerung ermöglichen. Mittels Analyse und Simulationen wurde eine signifikante Reduktion der Verzögerungsunterschiede der Nachrichten zwischen den Empfängern nachgewiesen. Ein Prototyp wurde implementiert, um die mit gegenwärtiger Smart-Card-Hardware erreichbare Reduktion von Verzögerungsunterschieden zu ermitteln und die Tragfähigkeit des Ansatzes zu demonstrieren.
Open Access
Laws for rewriting queries containing division operators
(2005) Rantzau, Ralf; Mangold, Christoph
Relational division, also known as small divide, is a derived operator of the relational algebra that realizes a many-to-one set containment test, where a set is represented as a group of tuples: Small divide discovers which sets in a dividend relation contain all elements of the set stored in a divisor relation. The great divide operator extends small divide by realizing many-to-many set containment tests. It is also similar to the set containment join operator for schemas that are not in first normal form. Neither small nor great divide has been implemented in commercial relational database systems although the operators solve important problems and many efficient algorithms for them exist. We present algebraic laws that allow rewriting expressions containing small or great divide, illustrate their importance for query optimization, and discuss the use of great divide for frequent itemset discovery, an important data mining primitive. A recent theoretic result shows that small divide must be implemented by special purpose algorithms and not be simulated by pure relational algebra expressions to achieve efficiency. Consequently, an efficient implementation requires that the optimizer treats small divide as a first-class operator and possesses powerful algebraic laws for query rewriting.
Open Access
Analytical and numerical investigations of form-finding methods for tensegrity structures
(2007) Gomez Estrada, Giovani; Bungartz, Hans-Joachim (Prof. Dr.)
The analysis of statically indeterminate structures requires the calculation of an initial equilibrium geometry. Tensegrity structures are one of such statically indeterminate structures, with the additional constraint of holding their equilibrium configuration with the action of internal forces and without any anchorage point or external forces. The only source of balance is the state of self-stress held among tensile and compression forces. Tensegrity structures are thus statically indeterminate structures in a stable state of self-stressed self-equilibrium. The basic problem with the modelling of statically indeterminate structures is that there is no unique solution for the forces or geometry that equilibrate a structure. This is where form-finding comes into play. The process of determining their three-dimensional equilibrium shape is commonly called form-finding. This dissertation presents two investigations, one analytical and one numerical on the form-finding of tensegrity structures. Both are in fact complementary. The main results from these investigations appear in [77, 78, 79, 80]. The analytical form-finding for a class of highly symmetric structures with cylindrical shape is first presented, while the numerical procedure for general structures is given in the second part. A thorough analysis of tensegrity cylinders, e.g., the triplex and the quadruplex, is presented in analytical form. Moreover, the numerical procedure here presented is able to reproduce the results obtained with other form-finding methods with great accuracy. The versatility of the novel numerical form-finding procedure is nonetheless demonstrated by solving not only cylindrical and spherical but also new tensegrity structures.
Open Access
A cross-layer framework for sensor networks
(2008) Lachenmann, Andreas; Rothermel, Kurt (Prof. Dr.)
Cross-layer interactions are often used in wireless sensor networks. They help to optimize energy consumption, deal with memory limitations, and consider the special properties of wireless communication. However, cross-layer interactions have the disadvantage of negatively affecting desirable properties of the software design like modularity and reusability. In the extreme, applications consist of a monolithic piece of code that is hard to develop and impossible to maintain. Therefore, this thesis investigates different approaches to address the negative side-effects of cross-layer interactions. In particular, it develops a framework that pursues three different strategies. First, it tries to preserve modularity and increase reusability by decoupling components that exchange data. This strategy is realized by TinyXXL, a programming abstraction for cross-layer data exchange. This part of the framework has been created based on an analysis of cross-layer interactions in existing applications. With some compile-time optimizations TinyXXL can reduce both energy and memory consumption compared to an application built from reusable components. Using Neidas, a novel neighborhood data sharing algorithm, it offers a comprehensive system for data exchange among the layers of a single node and with neighboring nodes. Second, the framework relaxes one of the constraints that often lead to cross-layer interactions and, thus, reduces the need to apply them. Specifically, it includes ViMem, a flash-based virtual memory system that helps to reduce memory limitations and tries to optimize the memory layout. Finally, the third strategy is to partially move energy concerns into the system software. For this purpose the framework includes Levels, an abstraction to specify optional functionality which allows to accurately meet a user-defined lifetime goal. If necessary, Levels deactivates functionality in order to reach that target lifetime. Furthermore, it includes a distributed algorithm that helps to provide a constant application quality over the total network lifetime.
Open Access
Vorabübertragung schwach strukturierter Informationen in ortsbasierten mobilen Systemen
(2007) Bürklen, Susanne Gudrun; Mitschang, Bernhard (Prof. Dr.)
Die rasant fortschreitende Entwicklung der Mobilkommunikation in Verbindung mit immer leistungsfähigeren mobilen Endgeräten weckt den Wunsch, an jedem Ort und zu jeder Zeit auf entfernte Informationen zugreifen zu können. Drahtlose Weitverkehrsnetze wie die Mobilfunknetze der zweiten oder dritten Generation bieten zwar nahezu überall eine Netzverbindung, weisen jedoch negative Eigenschaften wie eine hohe Latenz, hohe monetäre Kosten und unzuverlässige Verbindungen auf, die teilweise zum entkoppelten Betrieb führen können. Eine hohe Latenz führt dazu, dass auf Grund der hieraus entstehenden langen Übertragungszeiten der Informationen der Energieverbrauch der Funkschnittstelle ansteigt, was in Anbetracht der geringen Energieressourcen mobiler Endgeräte nicht wünschenswert ist. Um diesen Nachteilen entgegen zu wirken, wurden zugriffsoptimierende Methoden wie beispielsweise Caching oder die Vorabübertragung entwickelt, die jedoch unterschiedlichen Zielsetzungen folgen. Eine solche Methode ist die Vorabübertragung von Informationen an solchen Orten, an denen eine breitbandige und kostengünstige Verbindung zur Verfügung steht. In dieser Dissertation wird zur Optimierung des mobilen Informationszugriffs ein generisches Verfahren zur Vorabübertragung von beliebigen schwach strukturierten Informationen in ortsbasierten Anwendungen vorgestellt, das neben einer Verringerung der Latenz den entkoppelten Betrieb unterstützt. Für die Selektion der vorab zu übertragenden Informationen werden je nach Art der Informationen unterschiedliche Methoden angeboten. Als Basis wird eine Infrastruktur von so genannten Infostationen benötigt, an denen mobilen Benutzern mittels drahtloser lokaler Netze ein breitbandiger und kostengünstiger Zugriff auf Informationen ermöglicht wird. Sie sind in Gebieten verteilt, an denen sonst keine oder nur eine Kommunikation mit der maximalen Datenrate eines drahtlosen Weitverkehrsnetzes, wie beispielsweise GSM, GPRS oder UMTS möglich ist. Eine Infostation selektiert die in ihrem Dienstgebiet für einen Benutzer relevanten Informationen und überträgt sie vorab auf dessen mobiles Endgerät. Zukünftige Informationsanfragen können somit lokal aus dem Cache beantwortet werden, was jedoch eine gute Vorhersage voraussetzt. Um eine hohe Relevanz der vorab geladenen Informationen zu erreichen, werden als Selektionskriterium neben der Ortsabhängigkeit von Informationszugriffen auch Beziehungen zwischen den Informationen ausgewertet. Eine Infostation beobachtet das typische Zugriffsverhalten aller Benutzer, die sich in ihrem Dienstgebiet aufhalten und benutzt dieses Wissen zur Vorhersage der Informationen. Das Beobachten des kollektiven Zugriffsverhaltens hat den Vorteil, dass überwiegend diejenigen Informationen vorab geladen werden, die in einem Dienstgebiet zum aktuellen Zeitpunkt populär sind. Dieses Verfahren unterstützt somit auch solche Benutzer, die sich zum ersten Mal in diesem Gebiet aufhalten. Bisweilen können Informationen derart stark zusammenhängen, dass sie für einen Benutzer nur als Gruppe interessant sind und es keinen Sinn ergibt, einzelne Objekte dieser Gruppe isoliert von den anderen zu übertragen. In einem solchen Fall müssen Gruppen (Cluster) gebildet werden, die vollständig vorab übertragen werden. Des Weiteren resultiert die Auswertung des Zugriffsverhaltens einer Menge von Benutzern nicht immer in einer optimalen Entscheidung für einen individuellen Benutzer. Dieser Effekt kann jedoch verringert werden, wenn Nutzungsprofile in die Übertragungsentscheidung mit einbezogen werden. Das generische Vorabübertragungsverfahren wurde für den mobilen Zugriff auf das Web spezialisiert und evaluiert. Zur systematischen Leistungsbewertung wurde ein Modell für das Navigationsverhalten von Benutzern im Web entwickelt und implementiert, das Sequenzen von synthetischen Zugriffen auf das Web erzeugt. Mit dem clusterbasierten Auswahlverfahren konnten Trefferraten erzielt werden, die andere Ansätze um mehr als das Dreifache übertreffen. Schließlich ist der Energiebedarf der Funkschnittstelle ein nicht zu vernachlässigender Faktor für die Lebensdauer der Batterie, so dass die Zeit zum Senden und Empfangen von Daten möglichst gering gehalten werden sollte. In einem drahtlosen lokalen Netz steht eine um mindestens eine Größenordnung höhere Bandbreite als in drahtlosen Weitverkehrsnetzen zur Verfügung, wodurch die Übertragungszeit von Informationen deutlich verkürzt wird. Eine Analyse des Leistungsbedarfs von Funkschnittstellen beider Technologien hat gezeigt, dass durch den Einsatz des vorgestellten Verfahrens zur Vorabübertragung von Informationen in jedem Fall Energieeinsparungen möglich sind. Bei Kenntnis der zu erzielenden Trefferrate kann somit die Größe des Caches bestimmt werden, die den Energieverbrauch beim Laden der Informationen minimiert.

05 Fakultät Informatik, Elektrotechnik und Informationstechnik

Browse

Filters

Settings

Sort By

Results per page

Search Results