Browsing by Author "Schneefuss, Patrick"

Now showing 1 - 2 of 2

Open Access
Desychronization algorithms for fast ILP solutions of TDMA schedules in IEEE Time-Sensitive Networks
(2021) Schneefuss, Patrick
Time-Sensitive Networking (TSN) is extending standard IEEE 802.3 Ethernet with deterministic real-time capabilities, which are essential for many networked real-time systems. It does so by implementing a time-division multiple access (TDMA) scheme. To operate correctly, this requires the presence of a global schedule to manage access times. However, the methods and algorithms to compute such schedules are not part of the TSN standard. The calculation of a schedule for the TDMA scheme of Time-Sensitive Networks is generally NP-hard. A popular method to solve such optimization problems is to formulate them as an integer linear program (ILP). State-of-the-art ILP solvers can solve the problem to proven optimality at the expense of very high runtimes. To combat the latter, some ILP solvers provide the user with the possibility to specify an initial set of hints for the variables of the ILP. Existing ILP-based approaches for TSN did not exploit this method so far. Therefore, it is an open research question whether and how much TSN scheduling could be improved by providing hints to the ILP solver. In this work, we thus propose to split up the solution process. First, we generate a set of hints. Afterwards, we supply the hints to the ILP solver, which is then executed on the original scheduling problem. The essential question in this process is now, how a good heuristic to calculate hints that support the ILP solution looks like. The generated hints should approximate a feasible solution of the scheduling problem; however, their calculation must be fast to speed up the overall process. To this end, we transfer the primitive of desynchronization, which originally had been proposed for wireless ad-hoc networks, to the TSN domain. Intuitively, to avoid collisions of transmitted packets as required by a valid TDMA schedule, we space out the transmission times of network traffic by adapting the sending times. In this thesis, we present a total of five different desynchronization algorithms for Time-Sensitive Networks. Our results show that by supplying initial desynchronization hints to the ILP solver, the runtime to compute a first feasible solution to the scheduling problem is sped up by at least a factor of six compared to an execution without any provided hints.
Open Access
Umsetzung von Event-basiertem Hardwarefiltering unter Nutzung von P4
(2018) Schneefuss, Patrick
Publish/Subscribe Systeme gewinnen durch ihre Flexibilität gegenüber wechselnden Netzwerktopologien ein immer höheres Ansehen. Ein Empfänger von Daten wird hier Abonnent genannt. Dieser kann sein Interesse an bestimmten Paketinhalten aussprechen, und wird folglich auch nur solche Pakete erhalten. Um dies zu erreichen, müssen Pakete auf ihrem Weg durch das Netzwerk gefiltert und je nach Inhalt über die entsprechenden Links weitergeleitet werden. Das Filtern in Software erfüllt strikte Anforderungen an die Latenz solcher Systeme kaum. Diese Arbeit wird zunächst auf Systeme eingehen, die diesen Filtervorgang bereits auf Hardwareebene durchführen. Hierdurch entstehen allerdings in all diesen Systemen gewisse Ungenauigkeiten, wie zum Beispiel das gelegentliche Weiterleiten von Events an Abonnenten, die kein Interesse an deren Informationen verkündet haben. Ziel dieser Arbeit ist es also, ein Publish/Subscribe System zu entwerfen, welches den Filtervorgang auf Hardwareebene durchführt, diese Ungenauigkeiten aber komplett vermeidet. Dies wird vor allem durch das Programmieren der Datenebene eines softwaredefinierten Netzwerkes anhand der Programmiersprache P4 ermöglicht. Hierdurch können nun statt nur diversen vordefinierten Headerfelder alle Daten eines Paketes für dieses Filtervorgang in Betracht gezogen werden. Die Kernpunkte dieser Arbeit sind somit sowohl der Entwurf eines geeigneten P4 Programmes, sowie der Logik eines Controllers, welcher die Filter auf Hardwareebene unter sich ändernden Abonnements dynamisch aktualisiert. Untersucht wird hierbei vor allem, wie sich diese neuen Ansätze auf die Skalierbarkeit und Performanz dieses Systems auswirken.