Universität Stuttgart
Permanent URI for this communityhttps://elib.uni-stuttgart.de/handle/11682/1
Browse
82 results
Search Results
Item Open Access Spatial aware geographic Forwarding for mobile ad hoc networks(2002) Tian, Jing; Stepanov, Illya; Rothermel, KurtStateless greedy forwarding based on physical positions of nodes is considered to be more scalable than conventional topology-based routing. However, the stateless nature of geographic forwarding also prevents it from predicting holes in node distribution. Thus, frequent topology holes can significantly degrade the performance of geographic forwarding. So far the approaches mostly depend on excessive state maintenance at nodes to avoid forwarding failures at topology holes. In this paper, we propose and analyse spatial aware geographic forwarding (SAGF), a new approach that proactively avoids constant topology holes caused by spatial constraints while still preserving the advantage of stateless forwarding. Geographic source routes (GSR) based on intermediate locations are selected to bypass topology holes. Proactive route selection based on the spatial knowledge is a general approach, and thus can be used with any geographic forwarding algorithms. We evaluate our approach by extending greedy forwarding with spatial knowledge. Simulation results comparing with GPSR show that even simple spatial information can effectively improve the performance of geographic forwarding.Item Open Access Integration von Data Mining und Online Analytical Processing : eine Analyse von Datenschemata, Systemarchitekturen und Optimierungsstrategien(2003) Schwarz, Holger; Mitschang, Bernhard (Prof. Dr.-Ing. habil.)Die technischen Möglichkeiten, Daten zu erfassen und dauerhaft zu speichern, sind heute so ausgereift, dass insbesondere in Unternehmen und anderen Organisationen große Datenbestände verfügbar sind. In diesen Datenbeständen, häufig als Data Warehouse bezeichnet, sind alle relevanten Informationen zu den Organisationen selbst, den in ihnen ablaufenden Prozessen sowie deren Interaktion mit anderen Organisationen enthalten. Vielfach stellt die zielgerichtete Analyse der Datenbestände den entscheidenden Erfolgsfaktor für Organisationen dar. Zur Analyse der Daten in einem Data Warehouse sind verschiedenste Ansätze verfügbar und erprobt. Zwei der wichtigsten Vertreter sind das Online Analytical Processing (OLAP) und das Data Mining. Beide setzen unterschiedliche Schwerpunkte und werden bisher in der Regel weitgehend isoliert eingesetzt. In dieser Arbeit wird zunächst gezeigt, dass eine umfassende Analyse der Datenbestände in einem Data Warehouse nur durch den integrierten Einsatz beider Analyseansätze erzielt werden kann. Einzelne Fragestellungen, die sich aus diesem Integrationsbedarf ergeben werden ausführlich diskutiert. Zu den betrachteten Fragestellungen gehört die geeignete Modellierung der Daten in einem Data Warehouse. Bei der Bewertung gängiger Modellierungsansätze fließen insbesondere die Anforderungen ein, die sich durch den beschriebenen Integrationsansatz ergeben. Als Ergebnis wird ein konzeptuelles Datenmodell vorgestellt, das Informationen in einer Weise strukturiert, die für OLAP und Data Mining gleichermaßen geeignet ist. Im Bereich der logischen Modellierung werden schließlich diejenigen Schematypen identifiziert, die die Integration der Analyseansätze geeignet unterstützen. Im nächsten Schritt sind die für Data Mining und OLAP unterschiedlichen Systemarchitekturen Gegenstand dieser Arbeit. Deren umfassende Diskussion ergibt eine Reihe von Defiziten. Dies führt schließlich zu einer erweiterten Systemarchitektur, die die Schwachstellen beseitigt und die angestrebte Integration geeignet unterstützt. Die erweiterte Systemarchitektur weist eine Komponente zur anwendungsunabhängigen Optimierung unterschiedlicher Analyseanwendungen auf. Ein dritter Schwerpunkt dieser Arbeit besteht in der Identifikation geeigneter Optimierungsansätze hierfür. Die Bewertung der Ansätze wird einerseits qualitativ durchgeführt. Andererseits wird das Optimierungspotenzial der einzelnen Ansätze auch auf der Grundlage umfangreicher Messreihen gezeigt.Item Open Access System mechanisms for partial rollback of mobile agent execution(1999) Straßer, Markus; Rothermel, KurtMobile agent technology has been proposed for various fault-sensitive application areas, including electronic commerce, systems management and active messaging. Recently proposed protocols providing the exactly-once execution of mobile agents allow the usage of mobile agents in these application areas. Based on these protocols, a mechanism for the application-initiated partial rollback of the agent execution is presented in this paper. The rollback mechanism uses compensating operations to roll back the effects of the agent execution on the resources and uses a mixture of physical logging and compensating operations to rollback the state of the agent. The introduction of different types of compensating operations and the integration of an itinerary concept with the rollback mechanism allows performance improvements during the agent rollback as well as during the normal agent execution.Item 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.Item Open Access Das ASCEND-Modell zur Unterstützung kooperativer Prozesse(2002) Frank, Aiko; Mitschang, Bernhard (Prof. Dr.)Es wird eine neue Klasse von kooperativen Prozessen bestimmt und durch Beispiele betrachtet, deren Unterstützung durch das ASCEND Designflow Model(ADM) erfolgen soll. Diesen Prozessen ist der Bedarf nach Interaktion, Kooperation, kooperativer Nutzung gemeinsamer Ressourcen, Delegation von Teilar-beiten, strukturierten und weniger strukturierten Teilprozessen, Integration von Arbeitsergebnissen und Abstimmung von Aktionen gemein. Daraus wird die Forderung an eine geeignete Benutzerunterstützung abgeleitet, die den Nutzern die geeignete Unterstützung in Form entsprechend konfigurierbarer Dienste zur Verfügung stellt. Es werden Technologien vorgestellt und bewertet, die Teile der aufgestellten Forderungen erfüllen können. Der Schwerpunkt dieser Untersuchung betrifft CSCW und Workflow-Management. Eine weitere Klasse von Systemen zur Durchführung von Arbeiten sind CAD-Frameworks, die spezialisierte Dienste für den technischen Entwurf anbieten. Für die Realisierung der von uns gewünschten flexiblen Zugriffsregelung werden außerdem einige Aspekte der Agententechnologie betrachtet, insbesondere Verhandlungsprotokolle. Aufgrund der so gewonnenen Erkenntnisse wird ein Lösungsansatz präsentiert, der auf einer geeigneten Integration dieser Technologien basiert. Dieser Lösungsansatz wird durch das ASCEND Designflow Model umgesetzt. Dieses Modell verwendet drei wesentliche Aspekte: ein Aktivitätenmodell, einen Informationsraum und Interaktionsprotokolle. Workflow-Management stellt eine ideale Technologie für die Automatisierung der Steuerung von strukturierten Teilprozessen dar. Das Aktivitätenkonzept ist eine geeignete Basis zur Repräsentation von abhängigen Arbeitsschritten. Daher werden diese Konzepte weitgehend in das ADM integriert. Das Aktivitätenkonzept zur Modellierung und Durchführung abgegrenzter Arbeitsschritte hilft die Aufgabenverteilung und Vorgehensweise von Entwurfsprozessen, soweit möglich, zu strukturieren. Bspw. nutzt die Delegations-Beziehung des ADM Aktivitäten zur Spezifikation verschiedener Unteraufträge. Außerdem werden sogenannte Workflow-Aktivitäten eingeführt, die alle Eigenschaften eines Workflows übernehmen und innerhalb eines Entwurfsprozesses ausgeführt werden können. Dadurch wird eine geeignete Unterstützung gut strukturierter Teilprozesse erreicht. Weiterhin werden primitive Aktivitäten zum Kapseln von Werkzeuganwendungen und Groupware-Aktivitäten zur Durchführung von wenig strukturierten Teilarbeiten eingeführt. Eine Besonderheit stellen die Designflow-Aktivitäten dar, die durch sogenannte Design-Primitive eine erweiterte Funktionalität realisieren. So können anpaßbare Constraints angewendet werden, welche die Abhängigkeiten zwischen den in einer Designflow-Aktivität enthaltenen Ressourcen und Aktivitäten beschreiben. Durch die weitgehende Definierbarkeit solcher Constraints, besteht die Möglichkeit anwendungsspezifische Abhängigkeiten einzuführen und eine flexible Ablaufunterstützung zu erreichen. Aufgrund der Forderung nach frühem Austausch von gemeinsamen Ergebnissen, der Bearbeitung gemeinsamer Daten und der Abhängigkeiten bezüglich Daten und Ergebnissen, die in verschiedenen Teilprozessen erarbeitet werden, ist eine Abstimmung zwischen den am Prozeß teilnehmenden Personen notwendig. Dafür wird die gemeinsame Nutzung von Ressourcen im Rahmen eines gemeinsamen Informationsraums eingeführt. Dadurch können unvorherbestimmte Abläufe über die Objektzugriffe koordiniert werden. Zur Durchführung und Abstimmung der Nutzung gemeinsamer Objekte werden Protokolle in Konversationsmustern angewendet, die zum einen eine gewisse Weise des Zugriffs vorschreiben, aber auch die Möglichkeit zur Verhandlung anbieten. Diese Verhandlung, wie sie bei konkurrierenden Zugriffen oder bei der Durchführung des sogenannten Delegationsprotokolls auftreten, stellen ein mächtiges Werkzeug zur Interaktion zwischen allen Entitäten des ADM dar, d.h. zwischen Akteuren, Objekten und Aktivitäten. Die Effekte der Interaktionen werden komplett durch das zugrunde liegende System unterstützt, womit eine konsistente Behandlung ermöglicht ist. Die flexible Einsetzbarkeit, die Anpaßbarkeit und die Erweiterbarkeit der Protokolle ermöglicht einen hohen Grad der Anpassung des ADM an verschiedenste kooperative Prozesse. Damit unterstützt das ADM zum einen Entwurfsprozesse, die teilweise gut strukturiert sind. Zum anderen erlauben die eingeführten Entwurfskonstrukte (bspw. Delegation, Objektzugriffe und Constraints), auch schwächer strukturierte Teilprozesse und damit ein wesentliches Merkmal des Entwurfs bzw. der in dieser Arbeit anvisierten kooperativen Prozesse zu unterstützen. Somit wird erreicht, daß die passendste, unterstützende Technologie für den jeweiligen Teilprozeß verwendet werden kann. Dadurch werden die verschiedenen Anforderungen bezüglich koordinativer, wie auch kooperativer Zusammenarbeit erfüllt.Item Open Access Task allocation in distributed multimedia systems based on the host-satellite model(1998) Dermler, Gabriel; Iqbal, AshrafMultimedia applications require intermediate processing between media sources and sinks. In addition to end-user machines intermediate computers can be used for performing media processing. This possibility leads to the problem of allocating processing components on various computers. In this paper, we study this problem in the context of star-shaped application graphs which have to be allocated between given end-user machines (satellites) and a central computer (host). The problem is formulated in terms of best achievable bottleneck resource usage. Several approaches are considered including anapproximate scheme and two fast-heuristics. Performance measurements show the efficiency of the considered approaches. A discussion of our approach shows important differences to solutions provided for related problems of graph partitioning and mapping.Item 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.Item Open Access Contributions to low energy consumption in digital circuits(2000) Bühler, Markus; Baitinger, Utz G. (Prof. Dr.-Ing)After bipolar, static PMOS, and NMOS technologies have been widely replaced by static CMOS, static current has practically disappeared in digital circuits. Thus, the problem of power consumption was thought to be solved. However, with increasing integration densities and operation frequencies, combined with the advent of complex portable devices, design for low power has regained its importance as the third design goal, beside delay and area consumption. But in contrast to the past, today, dynamic power consumption is dominant by far. The domain of low power design can be divided into two major subdomains: power estimation and actual circuit design for low power, the latter including all efforts for power optimization and low power synthesis. In this thesis, specific aspects of both subdomains are treated on different levels. The design aspect is covered by an investigation of suitable circuit techniques for a novel, 3D, T-gate, SOI technology. It was found that DPL fits best the structural requirements of this technology but consumes 50 more power than static CMOS. The consequences are discussed in the text. The main focus of this thesis is put on power estimation techniques on gate level. A novel, set based simulation method is presented and extended for real delay gate models (RDM). Several further optimization methods are proposed. It is shown that the RDM extension can also be applied to bitparallel logic simulators. As a last extension the set based approach is combined with probabilistic simulation methods, thus making it possible to take into account signal correlations during probabilistic estimation.Item Open Access Interaktion und Koordination in Multiagentensystemen(2001) Muscholl, Klaus Matthias; Levi, Paul (Prof. Dr.)Das Zusichern von kohärentem Verhalten in Multiagentensystemen ist durch die inhärente Verteiltheit des Systems, als auch durch den unabhängigen Entwurf der Agenten bei offenen Systemen, ein weithin ungelöstes Problem. In der vorliegenden Dissertation wird ein entwurfstechnischer Ansatz vorgestellt, welcher mit Hilfe von Interaktionsverfahren Kohärenz sicherstellt. Interaktionsverfahren werden dabei durch das Interaktionsmodell beschrieben. Die Grundidee besteht darin, daß Agenten durch die Teilnahme an einer Interaktion einen Teil ihrer Autonomie an das die Interaktion beschreibende Verfahren und seine Entscheidungsmechanismen abtreten und sich ihm unterordnen. Dies wird dadurch erzielt, daß ein Interaktionsverfahren die Koordination der an ihn übertragenen Kompetenzen übernimmt. Ein Interaktionsverfahren ist somit gegenüber den teilnehmenden Agenten weisungsbefugt. Um an Interaktionsverfahren teilnehmen zu können, muß ein Agent eine Schnittstelle unterstützen, welche es dem Interaktionsverfahren ermöglicht, auf die an ihn übertragen Kompetenz zuzugreifen und die kollektiv getroffenen Entscheidungen im einzelnen durchzusetzen. Hierzu sind unabhängig von Interaktionsverfahren für einen Anwendungsbereich Dienstklassen definiert, welche Schnittstellen zu Fähigkeiten eines Agenten bilden. Ein Interaktionsverfahren definiert das Ablaufschema einer Interaktion. Das Ablaufschema abstrahiert von Agenten in Form von Rollen. Das Schema ist in einzelne Phasen strukturiert und definiert, wie die Rollen untereinander interagieren. Rollen sind die kleinsten aktiven Einheiten des Interaktionsmodells und nur innerhalb einer Phase gültig. Agenten, welche an einem Interaktionsverfahren teilnehmen, werden durch Rollen gesteuert, die ihnen in den jeweiligen Phasen zugewiesen werden. Die vorliegende Arbeit ist Bestandteil des Architekturkonzepts von Robotersystemen im Comros-Projekt.Item Open Access Algorithmische Aspekte der Fluid-Struktur-Wechselwirkung auf kartesischen Gittern(2007) Brenk, Markus; Bungartz, Hans-Joachim (Prof. Dr.)In vielen physikalischen Systemen und technischen Anwendungen spielen Fluid-Struktur-Wechselwirkungen eine wesentliche Rolle. Die Wechselwirkung von Fluiden und flexiblen Strukturen stellt ein gekoppeltes Problem dar, bei dem die Bewegung eines Fluides und einer Struktur über die so genannte nasse Oberfläche (Kopplungsoberfläche) der Struktur bidirektional gekoppelt sind. So sind Windlasten an Gebäuden und Brücken, das Aufblasen von Airbags, das Öffnen von Fallschirmen, der Blutfluss in einer Ader oder die Strömung zwischen den Lamellen eines Autoreifens Beispiele für diese Art der Kopplung. Bei der Untersuchung von Fluid-Struktur-Wechselwirkungen ist die numerische Simulation ein unerlässliches Hilfsmittel. Oft werden diese Simulationen durch so genannte partitionierte Ansätzen realisiert. Diese sind dadurch gekennzeichnet, dass getrennte und für die einzelnen Teilprobleme konzipierte und angepasste Programme zur Berechnung der Strömungen und der Strukturbewegungen bzw. -verformungen eingesetzt werden -- im Gegensatz zu so genannten monolithischen Ansätzen, bei denen alle Teilprobleme gemeinsam diskretisiert und in einem Programm behandelt werden. Bei partitionierten Ansätzen können Teile der Berechnungen mit bewährten und für den jeweiligen Teilaspekt am besten geeigneten Softwarelösungen erfolgen. Damit ist jedoch eine zusätzliche Programmkomponente erforderlich, die den Ablauf der gekoppelten Simulation steuert und den Austausch der Daten zwischen den Simulationsprogrammen ermöglicht und die somit einen integralen Bestandteil partitionierter Ansätze darstellt. Dies zeigt deutlich, dass sich bei der Simulation von Fluid-Struktur-Wechselwirkungen mit partitionierten Ansätzen, neben den ingenieurwissenschaftlichen Herausforderungen (wie bspw. dem Lösen konkreter Problemstellungen) und den mathematischen Herausforderungen (wie bspw. dem Sicherstellen von Konvergenz und Robustheit), insbesondere auch softwaretechnische und damit informatische Herausforderungen ergeben. Die vorliegende Arbeit befasst sich schwerpunktmäßig mit den resultierenden Fragestellungen zur Steuerung der Kopplung, zur Verknüpfung der in den Programmen unterschiedlichen geometrischen Darstellungen der nassen Oberfläche und zum Austausch der kopplungsrelevanten Daten. Die physikalische Beschreibung des Fluid-Struktur-Wechselwirkungsproblems fordert die Erfüllung von Gleichgewichtsbedingungen auf der Kopplungsoberfläche zu jedem Zeitpunkt. Für partitionierte Ansätze existieren je nach Anwendungsfall unterschiedliche Strategien und Methoden zum Austausch der Kopplungsdaten und zur Steuerung der Kopplung in der Zeit, um diese Gleichgewichte zwischen den getrennten Simulationen sicherzustellen. Dies erfordert eine Softwarelösung zur Kopplung der Simulationsprogramme, die neben einer einfachen und mit geringem Aufwand durchzuführenden Anpassung der Programme und einer flexiblen Möglichkeit zur Steuerung der Kopplung, eine Lösung zum Transfer der kopplungsrelevanten Daten -- zwischen den auf unterschiedlichen Diskretisierungen und Datenstrukturen aufbauenden Repräsentationen der Kopplungsober Fläche in den Simulationsprogrammen -- bietet. Dieser Transfer von Kopplungsdaten zwischen den verschiedenen Oberflächenrepräsentationen kann durch die Einbettung in eine übergeordnete Geometrierepräsentation wirkungsvoll unterstützt werden. Hierfür bieten sich insbesondere hierarchisch-strukturierte Zerlegungen des Raumes durch kartesische Volumenelemente (z. B. Oktalbäume) als laufzeit- und speichereffiziente Lösung an. Diesem Effizienz-Gedanken folgend, stellt sich die Frage, ob diese strukturierten kartesischen Zerlegungen des Raumes nicht direkt als Basis für die Diskretisierung des Strömungsgebietes bei der Simulation von Fluid-Struktur-Wechselwirkungen genutzt werden können. Die Untersuchung kartesischer Diskretisierungen im Kontext der Fluid-Struktur-Wechselwirkung bildet, neben den Fragestellungen der Realisierung der Kopplung den zweiten Schwerpunkt dieser Arbeit. Es werden entsprechende Methoden vorgestellt, untersucht und insbesondere durch die dreidimensionale Simulation des Transportes von Partikeln in Mikroströmungen validiert.