Verteilte Constraint-basierte Eisenbahn-Simulation
Schlenker, Hans
Diese Arbeit entwirft und bewertet einen neuen Algorithmus zur Simulation von Eisenbahn-Netzen: Distributed Railway Simulation (DRS). DRS ist ein verteilter Meta-Algorithmus, der lokale, Constraint-basierte Simulationen koordiniert. Zur Analyse komplexer realer Systeme werden häufig Simulations-Verfahren verwendet. Eisenbahn-Gesellschaften, wie in Deutschland die Deutsche Bahn AG, setzen Simulations-Software ein, um ihre Bahnnetze und Fahrpläne zu untersuchen und bezüglich Kosten und Service-Qualität zu verbessern. Die vorliegende Arbeit fand im Rahmen eines BMBF Förderprojekts statt, in dem untersucht werden sollte, wie man mithilfe von Constraint-Propagation verschiedene Probleme existierender Simulationssysteme lösen kann. Fernziel des Projekts war die erstmalige mikroskopische Simulation des deutschen Eisenbahn-Netzes. Zur verteilten Simulation per DRS wird zunächst das Simulationsmodell anhand des Gleisnetzes in disjunkte Teile zerlegt, welche auf die verfügbaren Rechenknoten verteilt werden. DRS veranlasst dann alle lokalen Simulatoren, ihre Teile zu berechnen. Nach jeder lokalen Simulation vergleichen die Simulatoren ihre Ergebnisse an den Schnittstellen benachbarter Teile. Solange dort Inkonsistenzen bestehen, werden die lokalen Simulationen mit den Nachbardaten als zusätzliche neue Constraints wiederholt, um die Inkonsistenzen schließlich aufzuheben. Dieser Algorithmus ist hier detailliert formal beschrieben. Der entwickelte Formalismus ist so organisiert, dass damit zwei wichtige Eigenschaften gezeigt werden können: Terminierung (dass DRS in jeder denkbaren Konfiguration nach endlich vielen Schritten eine global konsistente Lösung berechnet) und Korrektheit (dass die berechnete Lösung ein korrektes Simulationsergebnis ist). DRS ist theoretisch fundiert, aber auch praktisch solide umgesetzt. Aus der aktuellen Literatur werden Anforderungen an ein solches verteiltes System abgeleitet. Anhand dieser Voraussetzungen wird das Design des Systems entwickelt und beschrieben unter Verwendung des Standards UML: Architektur des Gesamt-Systems, Aufbau der Komponenten, lokale und globale Abläufe. Außerdem wird genauer eingegangen auf die Steuerung des verteilten Algorithmus (inkl. Beweis der Korrektheit der Implementierung), auf den integrierten Entwicklungsprozess und auf die Möglichkeiten der Verwendung unterschiedlicher lokaler Simulatoren. Die empirischen Untersuchungen anhand der vorliegenden Fallstudie zeigen, dass der Algorithmus DRS und die Implementierung die angestrebten Ziele erfüllen. So können gegebene Eisenbahn-Netze bei Verwendung von DRS schneller simuliert werden als ohne. Das gilt schon für relativ kleine Netze und bei Verwendung nur eines Rechenknotens. Die Ergebnisse lassen aber auch den Schluss zu, dass damit sehr große Netze -- und damit das deutsche Bahnnetz -- in sehr kurzer Zeit simuliert werden können: Das Verfahren skaliert unter Verwendung vieler Rechenknoten. Neben den empirischen Ergebnissen ist die theoretische Fundierung ein herausragendes Merkmal dieser Arbeit. Das hier entwickelte Verfahren lässt sich für viele andere Anwendungen einsetzen und bietet Ansätze für einige theoretische und praktische Erweiterungen.
This work designs and evaluates a new algorithm for the simulation of railway systems: Distributed Railway Simulation (DRS). DRS is a distributed meta-algorithm, that conducts local, constraint-based simulators, to cooperatively compute a global simulation. For the analysis of complex real-world systems, often simulation approaches are used. Railway companies, like the German Deutsche Bahn AG, use simulation software to examine and test their rail networks and timetables, in order to improve costs and service quality. This work took place within a ministry funded research and development project, where it should be investigated how Constraint Propagation can help overcome certain drawbacks of existing simulating approaches. The long-term objective of the project was the first microscopic simulation of the German rail network. For a distributed simulation with DRS, first of all the simulation model has to be divided into a number of disjunctive parts. These parts are distributed among the available computing nodes. Then, DRS initiates on all these nodes a local simulation. After each node has completed its simulation computation, it compares its results with that of the neighboring nodes. As long as there exist some inconsistencies between neighbor's results, the local computations are repeated, now taking into account the results of the neighbors. This process is iterated until the global solution is consistent. This algorithm is described here formally in detail. Using the herein constructed formalism, I prove the two most important properties of the algorithm: termination (it distributedly computes a result after a finite number of steps, for all possible simulation models), and correctness (each distributed computation yields a correct simulation result). DRS has a well-founded theory, but has also been realized soundly. I derive requirements to the realization from state-of-the art literature. Based on the requirements, the design of the system is evaluated. The design is described using the UML standards: architecture of the overall system, structure of the components, local and global sequences. Additionally, I go into the controller of the distributed computation (incl. formal proof of correctness of the implementation), into the integrated development process, and into the possibilities of using heterogeneous local simulation engines. The empirical investigations based on the available case study show that the algorithm and the implementation fulfill the aimed goals: The simulation of given railway systems takes less time when using DRS. This even applies to rather small nets and on one computing node. But, the results even imply that DRS can simulate very large networks -- and therefore the German railway net -- in very short time: the system scales using a large number of computing nodes. In addition to the empirical results, the formal foundation is an outstanding property of this work. The presented approach can be used for a number of other applications and has propositions for some theoretical and practical extensions.
