On consistency and distribution in software-defined networking

Software-defined Networking (SDN) is an emerging networking paradigm promising flexible programmability and simplified management. Over the last years, SDN has built up huge momentum in academia that has led to huge practical impact through the large-scale adoption of big industrial players like Google, Facebook, and Microsoft driving cloud computing, data center networks, and their interconnection in SDN-based wide-area networks. SDN is a key enabler for high dynamics in terms of network reconfiguration and innovation, allowing the deployment of new network protocols and substantially expanding the networking paradigm by moving applications into the network, both at unprecedented pace and ease. The SDN paradigm is centered around the separation of the data plane from the logically centralized but typically physically distributed control plane that programs the forwarding behaviour of the network devices in the data plane based on a global view. Especially requirements on correctness, scalability, availability, and resiliency raised through practical adoption at scale have put a strong emphasis on consistency and distribution in the SDN paradigm. This thesis addresses various challenges regarding consistency and distribution in Software-defined Networking. More specifically, it focusses and contributes to the research areas of update consistency, flexibility in control plane distribution, and data plane implementation of a distributed application. Reconfiguring an SDN-based network inevitably requires to update the rules that determine the forwarding behaviour of the devices in its data plane. Updating these rules, which are situated on the inherently distributed data plane devices, is an asynchronous process. Hence, packets traversing the network may be processed according to a mixture of new and old rules during the update process. Consequently arising inconsistency effects can severely degrade the network performance and can break stipulated network invariants for instance on connectivity or security. We introduce a general architecture for network management under awareness of expectable update-induced inconsistency effects, which allows for an appropriate selection of an update mechanism and its parameters in order to prevent those effects. We thoroughly analyze update consistency for the case of multicast networks, show crucial particularities and present mechanisms for the prevention and mitigation of multicast-specific inconsistency effects. Observing that on the one hand SDN's separation of control has been deemed rather strict, moving any control ``intelligence'' from the data plane devices to remote controller entities hence increasing control latency while on the other hand the coupling between controller and data plane devices is quite tight hence hindering free distribution of control logic, we present a controller architecture enabling flexible and full-range distribution of network control. The architecture is based on decoupling through an event abstraction and a flexible dissemination scheme for those events based on the content-based publish/subscribe paradigm. This lightweight design allows to push down control logic back onto data plane devices. Thus, we expand SDN's control paradigm and enable the full range from fully decentralized control, over local control still profiting from global view up to fully centralized control. This scheme allows to trade-off scope of state data, consistency semantics and synchronization overhead, control latency, and quality of control decisions. Furthermore, our implementation covers a large set of mechanisms for improving control plane consistency and scalability, such as inherent load-balancing, fast autonomous control decision making, detection of policy conflicts, and a feedback mechanism for data plane updates. In a last area, we focus on the implementation of a distributed application from the domain of message-oriented middleware in the data plane. We implement Complex Event Processing (CEP) on top of programmable network devices employing data plane programming, a recent big trend in SDN, or more specifically, using the P4 language. We discuss challenges entailed in the distributed data plane processing and address aspects of distribution and consistency in particular regarding consistency in stateful data plane programming, where internal state that determines how packets are processed is changed within this very processing, in turn changing the processing of subsequent packets. Since packet processing is executed in parallel on different execution units on the same device sharing the same state data, strong consistency semantics are required in order to ensure application correctness. Enabled by P4's flexible and powerful programming model, our data plane implementation of CEP yields greatly reduced latency and increased throughput. It comprises a compiler that compiles patterns for the detection of complex events specified in our rule specification language to P4 programs, consisting of a state machine and operators that process so-called windows containing historic events.Softwaredefinierte Netzwerke (SDN) verkörpern ein neues Netzwerkparadigma mit dem Ziel einer flexibleren Netzwerkprogrammierung und eines vereinfachten Netzwerkmanagements. Dabei hat SDN über die letzten Jahre sehr stark an Bedeutung gewonnen, sowohl in der Forschung als auch in der Industrie, wo bedeutende Firmen wie Google, Facebook und Microsoft SDN verbreitet zum Betrieb ihrer Cloudumgebungen, ihrer Rechenzentrumsnetzwerke als auch für die die Rechenzentren verbindenden Weitverkehrsnetzwerke einsetzen. SDN ist eine Schlüsselkomponente sowohl für den Umgang mit hoher Netzdynamik im Sinne von Netzrekonfiguration als auch für eine bislang unerreicht schnelle und unkomplizierte Umsetzung von Innovationen im Netzwerkbereich etwa durch neue Protokolle oder durch das Erweitern des gesamten Netzwerkparadigmas durch das Abbilden von Anwendungen im Netzwerk selbst. Das SDN-Paradigma basiert auf einer Trennung der Datenebene von der logischen zentralisierten, typischerweise aber physisch verteilten Kontrollebene, die das Weiterleitungsverhalten der Netzkomponenten in der Datenebene programmiert, wobei sie auf eine globale Netzsicht zurückgreifen kann. Insbesondere Anforderungen an Korrektheit, Skalierbarkeit, Verfügbarkeit und Resilienz, die sich durch den Einsatz in der Praxis im großen Maßstab ergeben, messen Konsistenz und Verteilung im SDN-Paradigma eine hohe Bedeutung bei. Die vorliegende Arbeit behandelt verschiedene Herausforderungen bezüglich Konsistenz und Verteilung in softwaredefinierten Netzwerken und bezieht sich dabei insbesondere auf die Forschungsbereiche Updatekonsistenz, Flexibilität bei der Verteilung der Kontrollebene, sowie der Implementierung einer verteilten Anwendung in der Datenebene und den damit einhergehenden Konsistenzgesichtspunkten. Die Rekonfiguration eines SDN-basierten Netzwerks erfordert unausweichlich eine Aktualisierung der Regeln die das Weiterleitungsverhalten der Netzkomponenten in der Datenebene steuern. Das Aktualisieren dieser sich auf den inhärent verteilten Datenebenenkomponenten befindlichen Weiterleitungsregeln stellt einen asynchronen Prozess dar. Dies kann dazu führen, dass Pakete in der Datenebene nach einer Mischung aus alten und neuen Regeln verarbeitet werden. Die dadurch auftretenden Inkonsistenzeffekte können die Netzwerkperformanz erheblich einschränken und verletzen oft festgelegte Netzeigenschaften, etwa damit festgelegte Verbindungs- oder Sicherheitseigenschaften. In der vorliegenden Arbeit wird daher eine generische Architektur für Netzwerkmanagement eingeführt die sich dadurch auszeichnet Kenntnis über zu erwartende Inkonsistenzeffekte zu haben und diese dadurch in Kontrollentscheidungen miteinbeziehen zu können. Somit wird die Auswahl eines angemessenen Updatemechanismus mitsamt zugehöriger Parameter ermöglicht, um das Auftreten dieser Inkonsistenzeffekte zu verhindern. Des Weiteren wird eine vollständige Analyse von Updatekonsistenz für Multicastnetzwerke durchgeführt. Dabei werden signifikante multicastspezifische Eigenheiten aufgezeigt, sowie Mechanismen zur Verhinderung bzw. Abmilderung von multicastspezifischen Inkonsistenzeffekten präsentiert. Motiviert durch die Beobachtung, dass die Trennung von Kontrolle in SDN im Allgemeinen sehr strikt umgesetzt wird, wodurch sämtliche Kontrollfunktionalität von der Datenebene zu entfernten Einheiten der Kontrollebene verschoben wird, was die Kontrolllatenz erhöht, und andererseits eine enge Kopplung zwischen Kontrolleinheiten und Datenebenenkomponenten besteht, was die freie Verteilung von Kontrolllogik einschränkt, wird in der Arbeit eine Kontrollarchitektur vorgestellt, die eine flexible und vollumfängliche Verteilung von Kontrolllogik ermöglicht. Diese Architektur basiert auf einer durch eine Eventabstraktion erreichten Entkopplung in Kombination mit einem flexiblen Eventverbreitungsschema basierend auf dem inhaltsbasiertem Publish/Subscribe-Paradigma. Das leichtgewichtige Design ermöglicht die Rückverlagerung von Kontrolllogik auf die Datenebenenkomponenten, was das Kontrollparadigma von SDN erheblich ausweitet und die ganze Spanne von vollständig dezentralisierter Kontrolle über lokale Kontrolle unter Miteinbezug der globalen Netzsicht bis hin zur vollständig zentralisierten Kontrolle, auf die das SDN-Paradigma ursprünglich beschränkt war, ermöglicht. Dieses Kontrollschema ermöglicht eine Abwägung zwischen Umfang der Zustandsdaten (globale Sicht bis ausschließlich lokale Sicht), Konsistenzsemantiken und Synchronisationsaufwand, sowie Kontrolllatenz und Qualität der Kontrollentscheidungen. Des Weiteren deckt der vorgestellte Ansatz einen breiten Bereich an Mechanismen zur Erhöhung der Kontrollebenenkonsistenz und der Skalierbarkeit ab, etwa durch inhärente Lastverteilung, schnellen autonomen Kontrollentscheidungen, Erkennung von Konflikten in Netzrichtlinien, sowie durch einen Feedbackmechanismus für Regelaktualisierungen auf der Datenebene. Ein letzter Bereich der vorliegenden Arbeit behandelt die Implementierung einer verteilten Anwendung aus dem Bereich der kommunikationsorientierten Diensteschicht ("Middleware") in der Datenebene. Darin wird eine komplexe Ereignisverarbeitung, oder "Complex Event Processing" (CEP), auf programmierbaren Netzgeräten unter Verwendung von Datenebenenprogrammierung, einem neuen und mächtigen Schritt in der Evolution des SDN-Paradigmas, mit der spezifischen Programmiersprache P4 umgesetzt. In diesem Zuge werden die mit einer verteilten Verarbeitung in der Datenebene einhergehenden Herausforderungen herausgearbeitet, insbesondere bezüglich Verteilung und Konsistenz in zustandsbasierter Datenebenenprogrammierung, in welcher interner Zustand, der die Verarbeitung von Paketen bestimmt, durch eben jene Verarbeitung verändert wird, was wiederum die Verarbeitung von nachfolgenden Paketen beeinflusst. Da Paketverarbeitung typischerweise auf hochparallel ausgelegten Verarbeitungseinheiten auf dem selben Gerät unter Nutzung des selben Zustandsspeichers ausgeführt wird, sind strikte Konsistenzsemantiken zur Sicherstellung der Korrektheit der Anwendung unerlässlich. Durch die Paketverarbeitung auf Hardware, welche durch das flexible und mächtige Programmiermodell von P4 ermöglicht wird, konnte der Durchsatz und die Latenz der vorgestellten Datenebenenimplementierung von CEP stark erhöht, bzw. verringert werden. Die Implementierung beinhaltet einen Compiler, der Regeln die in einer eigenen Regelspezifikationssprache verfasst sind in ein P4-Programm übersetzt. Das P4-Programm wiederum besteht aus einem Zustandsautomaten zur Eventerkennung und einer Verarbeitungseinheit für in einem sogenannten Fenster gespeicherte historische Ereignisse