An Aeronautical Publish/Subscribe System Employing Imperfect Spatiotemporal Filters

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