TU Darmstadt / ULB / TUprints

An Aeronautical Publish/Subscribe System Employing Imperfect Spatiotemporal Filters

Grothe, Christian (2010)
An Aeronautical Publish/Subscribe System Employing Imperfect Spatiotemporal Filters.
Technische Universität
Ph.D. Thesis, Primary publication

[img]
Preview
Dissertation Christian Grothe - PDF
DissertationChristianGrothe.pdf
Copyright Information: In Copyright.

Download (7MB) | Preview
Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: An Aeronautical Publish/Subscribe System Employing Imperfect Spatiotemporal Filters
Language: English
Referees: Buchmann, Prof. Alejandro ; Klingauf, Prof. Uwe
Date: 31 August 2010
Place of Publication: Darmstadt
Date of oral examination: 30 August 2010
Abstract:

The permanent growth of air traffic volume, being a main contributor to economic growth, is reaching the limits of what current Air Traffic Management (ATM) systems are capable to handle. Fundamental changes in ATM operations are required to cope with the expected increase in the next decades. On one hand, the bottleneck of centralized control of air space operations has been identified as a core limitation, and the two large development programmes for the future ATM systems, which are underway in Europe and North America, SESAR and NextGen, both envision a much stronger inclusion of all ATM stakeholders, from the airport operators to the individual pilot, into decision making processes, thus decentralizing ATM coordination effort. A fundamental requirement and key enabler of this relocation and sharing of control is the availability of all information necessary for making subsystem-level decisions that enhance the flow in the ATM supersystem, i.e., the decentralized availability of static and dynamic ATM data. The traditional ATM information distribution systems on the other hand are currently undergoing a paradigm change as well, being mainly determined by a transition from paper-based, product-oriented to data-based, concept-oriented operations. The development of the Aeronautical Information Exchange Model version 5 (AIXM 5) has pioneered this movement, enabling the Aeronautical Information domain to be the first of the ATM data domains to implement the paradigm shift. The integration of the Aeronautical Information domain with the various other ATM data domains is supported by the definition of a superordinate model system of constitutive information concepts, in which basic concepts such as space and time, are modeled in a generic, yet ATM-specific way. Such models of aeronautical spatiality and temporal dependency of aeronautical processes are presented and discussed in this thesis as AIXM 5 concepts. Both these topics, the required reorganization of information distribution systems and the explicit modeling of ATM data domain information including generic models for basic information aspects, are in the scope of the SWIM concept: the approach to System Wide Information Management in the future ATM system envisioned in SESAR and NextGen. SWIM defines a high-level distributed system model for information exchange between ATM stakeholder subsystems acting as Providers or Users of information. Among the specified SWIM core communication services is publish/subscribe, a communication paradigm closely related to event-based interaction models, in which Providers can publish event notifications, and a notification service component, which inherently decouples the communicating parties, is solely responsible for mediating the notifications to affected Users who have previously expressed interest in some sort of event notifications by registering a subscription with the service. While various subscription and event models have been proposed in the literature and have been implemented in publish/subscribe systems, none exists that provides the means to subscribe to, and efficiently disseminate, event notifiations based on spatial and temporal aspects. In this thesis, such a subscription model for spatial and temporal aspects of event notifications for publish/subscribe systems is presented. It is derived from an initial analysis of the specific requirements of the Aeronautical Information domain with respect to spatial data and the implications from Aeronautical Information processes for a model of temporal data, and is intended to provide SWIM Users with the means to subscribe to notifications for events affecting the trajectory of a (planned or currently conducted) flight. The subscription model is based on two basic types of filters, of which subscriptions are composed and which are used in the notification service nodes for routing decisions: spatial filters and interval filters. These filter types are formally introduced, and required operations (notification matching and filter relationships) are defined. The ``2.5-dimensional'' aeronautical spatial model requires the adjustment of algorithms from the field of Computational Geometry to work with geometries, in which different interpolation methods for lines are used, accounting for different types of flight paths common in air navigation, namely loxodrome (rhumb line) and orthodrome (great circle track) routes. Past research in distributed content-based publish/subscribe systems has yielded advanced routing algorithms that exploit equality and inclusion relations of subscriptions to reduce filter handling overhead in the distributed nodes of the notification service. In the given context though, these traditional approaches are uneffective due to lack of appropriate subscription relationships because the 4D trajectories of two different flights never assume the same spacetime nor is one trajectory's spacetime covered by another trajectory's one. Nevertheless, their spacetime may be close enough such that the flights are affected by the same events, in which case the respective subscriptions could be united, thus reducing filter handling overhead throughout the distributed nodes of the system. The main challenge of such an approach of merging similar subscriptions is to decide if filters are ``similar enough'' to be merged. The problem of (imperfectly) merging filters is based on a trade-off between filtering quality and filter numbers, and a formal approach to describing filter similarity and filtering quality is required to sensibly balance this trade-off. Such a formal discussion is presented in this thesis, and heuristical algorithms are proposed that integrate with merging-based routing algorithms. The proposed approaches are based on quantitatively estimating the reduction of filtering quality involved in creating a filter merger. This merger quality estimation takes into account simple filter metrics (size and distance) defined for this purpose, and returns the estimation as numeric value. By defining a merger quality threshold value, the trade-off of reduction (of the number of filters) against precision (filtering quality) can be easily adjusted as required by the application by means of a single numeric value. The proposed size-based and distance-based approaches to merger quality estimation were evaluated in filter merging experiments, and the results show that an approach based on normalized filter distance outperforms the others with respect to achieved filtering quality. Furthermore, the impact of other factors such as filter and notification size, distance and distribution characteristics (clustered or uniformly distributed) as well as filter and notification numbers was examined, and it is found that higher filter and notification density in the filter space, which is the representation of similar interests of Users and event hotspots, generally allows for better filtering quality when applying imperfect filter merging. Algorithms for the filter handling operations of a broker node in a distributed publish/subscribe system are presented that employ filter merging aiming to increase system scalability by reducing routing table size and filter forwarding overhead at the cost of unnecessarily forwarded notifications that result from the reduction of filtering quality. The scalability benefits of the approach are evaluated, firstly, by formally describing the effects of the presented filter handling scheme and investigating the propagation of the effects throughout the broker network, and secondly, in experiments using realistic flight subscriptions derived by extrapolating real historic flight data. The analysis of the results shows that very specific conditions have to be met for the overall approach to reduce subscription forwarding overhead more than increase notification forwarding overhead compared to a simple routing approach. Nevertheless, statements are derived on the conditions for filter and notification characteristics that must be met for the approaches to be effective.

Alternative Abstract:
Alternative AbstractLanguage

Das permanente Wachstum des Luftverkehrsaufkommens, das einen wesentlichen Beitrag zu wirtschaftlichem Wachstum liefert, erreicht die Grenze dessen, was aktuelle Air Traffic Management (ATM) Systeme bewältigen können. Grundlegende änderungen im ATM-Betrieb sind notwendig, um die für die nächsten Jahrzehnte erwartete Steigerung bewältigen zu können. Auf der einen Seite wurde der Flaschenhals der zentralisierten Steuerung von Luftraumbetrieb als eine essenzielle Beschränkung identifiziert, und die beiden großen Entwicklungsprogramme, die in Europa und Nordamerika im Gange sind, SESAR und NextGen, sehen beide eine viel stärkere Einbindung aller ATM-Beteiligten in Entscheidungsfindungsprozesse vor, um so den Aufwand für ATM-Koordination zu dezentralisieren. Eine wesentliche Anforderung und ein Treiber für diese Steuerungsverlagerung und -verteilung ist die Verfügbarkeit aller Informationen für auf Subsystem-Ebene zu treffenden Entscheidungen, die den Fluss im ATM-Supersystem verbessern, also die dezentrale Verfügbarkeit von statischen und dynamischen ATM-Daten. Auf der anderen Seite findet in den traditionellen ATM-Informationsverteilungssystemen gerade ein Paradigmenwechsel statt, der im Wesentlichen bestimmt wird durch einen übergang von Papier-basierten, Produkt-orientierten Abläufen zu Daten-basierten, Konzept-orientierten. Die Entwicklung des "Aeronautical Information Exchange Model version 5" (AIXM 5) hat dieser Bewegung den Weg bereitet und es damit dem Bereich der aeronautischen Informationen ermöglicht, die erste ATM-Daten-Domäne zu sein, die den Paradigmenwechsel umsetzt. Die Integration der Domäne aeronautischer Informationen mit den verschiedenen anderen ATM-Daten-Domänen wird unterstützt durch die Definition eines übergeordneten Modellsystems grundlegender Informationskonzepte, dem "ATM Information Reference model". In diesem sind elementare Konzepte wie Raum und Zeit generisch, aber dennoch ATM-spezifisch modelliert. Solche Modelle aeronautischer Räumlichkeit und zeitlicher Abhängigkeit aeronautischer Prozesse werden in dieser Arbeit als Konzepte von AIXM 5 vorgestellt und diskutiert. Beide Themen, die benötigte Reorganisation der Informationsverteilungssysteme und die explizite Modellierung von Information in ATM-Daten-Domänen unter Einbeziehung generischer Modelle für elementare Informationsaspekte, sind Bestandteile des "SWIM"-Konzepts: der Ansatz zu "System Wide Information Management" in den von SESAR und NextGen vorgesehenen zukünftigen ATM-Systemen. SWIM definiert ein abstraktes Modell eines verteilten Systems für Informationsaustausch zwischen den Subsystemen der ATM-Beteiligten, die als "Provider" und "User" von Information agieren. Einer der fundamentalen SWIM-Kommunikationsdienste ist Publish/Subscribe (Pub/Sub): ein Kommunikationsparadigma, das in enger Beziehung zu ereignisbasierten Interaktionsmodellen steht. In Pub/Sub können Provider Ereignismeldungen ("event notifications") publizieren. Ein Benachrichtigungsdienst, der die Kommunikationsparteien inhärent entkoppelt, ist alleine verantwortlich für die Vermittlung der Meldungen an betroffene User, die vorher ihr Interesse an einer bestimmten Art von Ereignismeldungen ausgedrückt haben, indem sie bei dem Dienst eine Subskription angemeldet haben. Obwohl diverse Subskriptions- und Ereignismodelle in der Literatur vorgeschlagen und in Pub/Sub-Systemen implementiert worden sind, gibt es keines, das die Mittel bereitstellt, Subskriptionen auf der Basis von räumlichen und zeitlichen Aspekten von Ereignissen auszudrücken, und auf der selben Grundlage Ereignismeldungen effizient zu verteilen. In dieser Arbeit wird solch ein Subskriptionsmodell für räumliche und zeitliche Aspekte von Ereignismeldungen vorgestellt. Es leitet sich ab aus einer initialen Analyse der speziellen Anforderungen der Domäne aeronautischer Informationen bezüglich räumlicher Daten und den Implikationen aus den Abläufen in dieser Domäne für ein Modell temporaler Daten und verfolgt das Ziel, die Mittel zur Verfügung zu stellen, sich für Meldungen über Ereignisse zu subskribieren, die sich auf die Trajektorie eines (geplanten oder in Durchführung befindlichen) Fluges auswirken. Das Subskriptionsmodell basiert auf zwei elementaren Arten von Filtern, aus denen Subskriptionen zusammengesetzt werden und die im Benachrichtigungsdienst für Routing-Entscheidungen benutzt werden: räumliche Filter und Intervall-Filter. Diese Filtertypen werden formal eingeführt, und benötigte Operationen werden definiert, nämlich das Anwenden von Filtern auf Meldungen ("notification matching") und Beziehungen zwischen Filtern. Das "2,5-dimensionale" aeronautische Raum-Modell erfordert die Anpassung von Algorithmen aus dem Bereich der Algorithmischen Geometrie, um auf Geometrien angewendet werden zu können, bei denen unterschiedliche Interpolationsverfahren für Linien zur Anwendung kommen. Dies ist notwendig aufgrund der verschiedenen Arten von in der Flugnavigation gebräuchlichen Pfaden, nämlich Loxodrome- ("rhumb line") und Orthodrome-(Großkreis-)Routen. Forschung an verteilten inhaltsbasierten Pub/Sub-Systemen hat in der Vergangenheit fortgeschrittene Routing-Algorithmen hervorgebracht, die Gleichheits- und überdeckungsbeziehungen zwischen Subskriptionen ausnutzen, um den Mehraufwand für den Umgang mit Filtern ("filter handling overhead") zu reduzieren, der in den verteilten Knoten des Benachrichtigungsdienstes anfällt. Im hier gegebenen Kontext allerdings sind diese traditionellen Ansätze wirkungslos, da die Subskriptionen die entsprechenden Beziehungen nicht aufweisen, denn die 4D-Trajektorien zweier Flüge nehmen niemals die gleiche Raumzeit ein. Ebenso kann die Raumzeit einer der Trajektorien nie von der der anderen überdeckt sein. Nichtsdestotrotz können die jeweiligen Raumzeiten nahe genug beieinander sein, so dass die Flüge von den gleichen Ereignissen betroffen sind. In diesem Fall könnten die jeweiligen Subskriptionen vereinigt werden, um so den "filter handling overhead" über alle verteilten Knoten des Systems zu reduzieren. Die zentrale Herausforderung solch eines Ansatzes zum Zusammenfügen ("merging") ähnlicher Subskriptionen ist die Entscheidung, ob Filter "ähnlich genug" sind, um zusammengefügt zu werden. Dem Problem des unvollkommenen Zusammenfügens ("imperfect merging") von Filtern liegt ein Trade-off zugrunde, nämlich zwischen Filterungsqualität und der Anzahl von Filtern. Ein formaler Ansatz zur Beschreibung von Filter-ähnlichkeit und Filterungsqualität ist notwendig, um diesen Trade-off sinnvoll auszutarieren. Solch eine formale Diskussion wird in dieser Arbeit präsentiert, und heuristische Algorithmen werden vorgeschlagen, die in auf "filter merging" basierenden Routing-Algorithmen eingesetzt werden können. Die vorgeschlagenen Verfahren gründen darauf, die Abnahme der Filterungsqualität durch "filter merging" quantitativ abzuschätzen. Die Schätzung der Qualität eines zusammengefügten Filters ("filter merger") basiert auf einfachen, für diesen Zweck definierten Filter-Metriken (Größe und Distanz) und liefert als Ergebnis die Schätzung als Zahlenwert. Indem ein Grenzwert für die Qualität von "filter mergers" definiert wird, kann der Trade-off zwischen "Reduktion" (der Filter-Anzahl) und "Präzision" (Filterungsqualität) einfach nach den Anforderungen der Anwendung anhand eines einfachen Zahlenwerts ausgeregelt werden. Die vorgeschlagenen Größe- und Distanz-basierten Ansätze zur Qualitätsschätzung von "filter mergers" wurden in Experimenten getestet, deren Ergebnisse zeigen, dass ein auf normalisierter Filterdistanz basierender Ansatz den anderen im Hinblick auf erreichte Filterungsqualität überlegen ist. Darüber hinaus wurde der Einfluss anderer Faktoren untersucht, wie der Größe von Filtern und Ereignismeldungen, ihrer Distanz und der Verteilungscharakteristik (gehäuft/"clustered" oder gleichverteilt) sowie der Anzahl von Filtern und Ereignismeldungen. Es zeigt sich, dass eine höhere Dichte von Filtern und Ereignismeldungen im Filterraum (welche eine Abbildung ähnlicher Interessen der User und von Ereignis-Hotspots darstellt) generell eine höhere Filterungsqualität ermöglicht, wenn "imperfect merging" angewendet wird. Weiterhin werden in dieser Arbeit Algorithmen für die Filter-Verarbeitung eines Vermittler-Knotens in einem verteilten Pub/Sub-System vorgestellt, die "filter merging" mit dem Ziel anwenden, die Skalierbarkeit des Systems zu erhöhen, indem die Größe der Routing-Tabellen und der Mehraufwand für das Weiterleiten von Filtern reduziert wird unter Inkaufnahme von unnötigerweise weitergeleiteten Ereignismeldungen durch die Abnahme der Filterungsqualität. Die Vorteile für die Skalierbarkeit des Ansatzes werden in dieser Arbeit auf zwei Arten untersucht und beurteilt: zunächst durch die formale Beschreibung der Auswirkungen des vorgestellten Schemas zur Filter-Verarbeitung und die Untersuchung der Fortpflanzung der Auswirkungen durch das Vermittler-Netzwerk, dann in Experimenten mit realistischen Flug-Subskriptionen, die durch Extrapolation von Daten realer, vergangener Flüge erzeugt wurden. Die Analyse der Ergebnisse zeigt, dass sehr spezifische Bedingungen erfüllt sein müssen, damit der Gesamtansatz die Anzahl von Filter-Operationen (Verarbeitung und Weiterleitung) stärker reduziert als er die Anzahl entsprechender Ereignismeldung-Operationen erhöht. Nichtsdestotrotz gelingt es, Aussagen aus den Ergebnissen über die Bedingungen abzuleiten, die erfüllt sein müssen, damit das Verfahren erfolgreich ist.

German
URN: urn:nbn:de:tuda-tuprints-22706
Classification DDC: 600 Technology, medicine, applied sciences > 620 Engineering and machine engineering
000 Generalities, computers, information > 004 Computer science
Divisions: 20 Department of Computer Science > Databases and Distributed Systems
16 Department of Mechanical Engineering > Institute of Flight Systems and Automatic Control (FSR)
Date Deposited: 11 Oct 2010 11:30
Last Modified: 08 Jul 2020 23:47
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/2270
PPN: 228514797
Export:
Actions (login required)
View Item View Item