Dynamische Partitionierung zur effizienten verteilten Simulation Mobiler Ad-Hoc-Netze
Final Report Abstract
Die Leistungsbewertung von Mechanismen und Protokollen für Mobile Ad-Hoc-Netze (MANETs) erfolgt häufig durch Simulation. Aufgrund der häufig auftretenden langen Simulationslaufzeiten bieten sich parallele und verteilte Ansätze zur Beschleunigung der Simulation an, die das Simulationsszenario auf mehrere Prozessorkerne, CPUs oder Rechner verteilen. MANETs stellen jedoch aufgrund ihrer Dynamik und der hohen Interaktion der Netzteilnehmer (Knoten) über das drahtlose Medium besonders hohe Anforderungen an eine parallele und verteilte Simulation. Die erforderliche Synchronisation der beteiligten Komponenten kann die Vorteile durch Parallelität komplett zunichte machen. Das Ziel des Projekts “Dynamische Partitionierung zur effizienten verteilten Simulation Mobiler Ad-Hoc-Netze” war es daher, neue algorithmische Lösungen für eine effiziente parallele und verteilte Simulation von MANETs zu entwickeln. Im Projekt wurde zunächst ein Grundmodell zur MANET-Simulation entwickelt, bestehend aus einem typischen Protokoll-Stack aus Simulationsmodulen, der u. a. ein detailliertes Modell von IEEE 802.11 und realistische physikalische Modelle für Signalausbreitung und Interferenz umfasst. Bei der Implementierung des Grundmodells wurde sehr stark auf mögliche Optimierungen geachtet, um in der Folge eine geeignete Referenz für die parallelen Verfahren zu haben. Die sequentielle Laufzeit unseres Simulators ist sogar minimal kürzer als die Laufzeit des als sehr effizient bekannten Simulators JiST/SWANS. Basierend auf dem Grundmodell wurde ein komplettes Verfahren zur parallelen MANET-Simulation etabliert. Das Gesamtkonzept hat sich aus einer schrittweisen Abstimmung der beteiligten Komponenten für Partitionierung, Ereignisaustausch und Synchronisation ergeben und als äußerst erfolgreich erwiesen. Die Parallelisierung des Modells erfolgt durch eine Knotenpartitionierung, d. h. einer strengen Zuordnung von Knoten an die parallelen Logischen Prozesse (LPs). Jeder LP übernimmt dezentral alle nötigen Berechnungen für seine Knoten, wodurch Rechenlast parallelisiert wird. Der Ereignisaustausch zwischen LPs findet in Form einer geschickten Ereignisbündelung statt. Die Synchronisation der LPs geschieht mit einer effizienten Barrierenoperation kombiniert mit geschickten Methoden zur Lookahead-Gewinnung. Umfassende Auswertungen haben gezeigt, dass unser paralleles Verfahren bereits in praxisrelevanten Szenarien mit nur wenigen Hundert Knoten superlineare Speedups gegenüber der sequentiellen Simulation liefern kann. In großen Szenarien mit 2000 Knoten wird je nach Konfiguration sogar auf 16 Prozessorkernen noch ein superlinearer Speedup von 17,5 erzielt. Dabei ist zu betonen, dass unser Verfahren die hohen Speedups nicht durch Einbußen beim Realismus der Simulation erkauft. Diese Ergebnisse wurden auf handelsüblichen Multiprozessor-Servern und Multicore-Computern erzielt. Vergleichbare Erfolge wurden in der MANET-Simulations-Community noch nicht publiziert. Im nächsten Schritt wurde das parallele Verfahren mit einer bekannten Klasse von sequentiellen Optimierungsverfahren, den Lazy-Verfahren, zusammengeführt. Wir haben hierfür ein Lazy-Verfahren entworfen, das zusätzliche Ereignis- und Rechenlast einspart, dabei aber erneut den Realismus der Simulation nicht beeinträchtigt. In unseren Experimenten haben wir nachgewiesen, dass eine gemeinsame Nutzung der Verfahren zu einer weiteren spürbaren Beschleunigung von MANET-Simulationen führen kann. Zum Abschluss des Projekts schließlich haben wir das parallele Verfahren für die verteilte Simulation auf vernetzten Rechnern erweitert. Realisiert wurde dabei ein zweistufiges Verfahren, bei dem das parallele und das verteilte Verfahren zusammenwirken und so eine MANET-Simulation auf Rechenclustern ermöglicht wird. Auf diese Weise können Szenarien ausgewertet werden, die zu groß für die Simulation auf einem einzelnen Rechner sind. Allerdings werden wegen der notwendigen Kommunikation schlechtere Laufzeiten als bei der rein parallelen Simulation erzielt. Während der Projektlaufzeit wurden alle entwickelten Verfahren prototypisch in einem neuen Simulator HiPWiNS (“High Performance Wireless Network Simulator”) umgesetzt. Wir haben HiPWiNS quelloffen als Software-Paket im Internet verfügbar gemacht, so dass die Simulations-Community von den Ergebnissen dieses Projekts auch in der Praxis profitieren kann. Ebenfalls quelloffen haben wir unsere Implementierung der effizienten Barrierenoperationen als eigene Bibliothek veröffentlicht, so dass diese von beliebigen parallelen Java-Anwendungen genutzt werden kann.
Publications
- Interval Branching. In: PADS ’08: Proceedings of the 22nd ACM/IEEE/SCS Workshop on Principles of Advanced and Distributed Simulation, IEEE Computer Society, 2008
Peschlow, Patrick; Martini, Peter; Liu, Jason
- Logical Process based Sequential Simulation Cloning. In: ANSS ’08: Proceedings of the 41st IEEE Annual Simulation Symposium, IEEE Computer Society, 2008
Peschlow, Patrick; Geuer, Martin; Martini, Peter
- Good News for Parallel Wireless Network Simulations. In: MSWIM ’09: Proceedings of the 12th ACM International Conference on Modeling, Analysis and Simulation of Wireless and Mobile Systems, 2009
Peschlow, Patrick; Voss, Andreas; Martini, Peter
