SPINE: Stochastic Performance Bounds for Information-Centric Communication Networks
Final Report Abstract
Die Integration von Caching- und Paketweiterleitungsfunktionalitäten ist ein neuer, evolutionärer Schritt in Kommunikationsnetzen, der eine Folge der Veränderung der Kommunikation von einem Punkt-zu-Punkt verbindungsorientierten Datenaustausch zu inhaltsbasierten Mehrpunktverbindungen ist. In diesem Projekt wurden integrierte Caching und Kommunikationsnetze untersucht. In einem Schwerpunkt dieses Projekt wurde die Zuweisung von Anfragen in großen, heterogenen Clustern von Servern mit endlichen Puffern untersucht. Dieses Scheduling-Problem tritt in den heutigen Kommunikations- und Caching-Systemen wie Network Service Function Chains und Stream Processing, auf. Ankommende Anfragen werden einem Server/Cache zugewiesen, wobei ein Verfahren zum Lastausgleich angewendet wird, das ein Leistungskriterium wie die Bearbeitungszeit einer Anfrage optimiert. Ein Beitrag dieses Projektes ist ein randomisiertes kostenbasiertes Scheduling-Verfahren, bei dem die Zuweisung von Anfragen durch Wertfunktionen des Füllstands der Serverwarteschlangen gesteuert wird. Neben bestehenden Verfahren wie dem Join-the-shortest-Queue (JSQ), “Power-of-d” oder dem SQ(d) Verfahren führt der neue Ansatz dieses Projekts zu anwendungsspezifischen Scheduling-Verfahren. Da heutige Cluster eine sehr große Anzahl von Servern haben, ist eine genaue Analyse des kostenbasierten Verfahrens mühsam. Ein Ergebnis dieses Projekts ist die Herleitung eines Skalierungsresultats, wenn die Anzahl der Server groß wird, welches das transiente und stationäre Verhalten des kostenbasierten Scheduling-Verfahrens widerspiegelt. Als Nebenprodukt dieser Herleitung ergibt sich das Verhältnis zwischen den Füllungsgraden der Serverwarteschlangen und den Puffergrößen der Server, das sich nicht aus klassischen unendlichen Puffermodellen ableiten lässt. Abschließend zeigen umfangreiche numerische Auswertungen die Schedulingperformanz einschließlich für mehrstufiger, hierarchische Systeme. In einem weiteren Schwerpunkt dieses Projekts wurden baumbasierte Cache-Hierarchien mit zufälligen Netzverzögerungen beim Abrufen von Objekten untersucht. Ein Ergebnis dieses Projekts ist eine exakte Analyse der entsprechenden Objekttrefferwahrscheinlichkeit unter zufälligen Netzverzögerungen. Diese Analyse ermöglicht es, die Auswirkungen von stochastisch modellierten Übertragungslatenzen und der Cache-intrinsischen Parameter der Speicherungsdauer pro Objekt (die sogenannte Time-to-Live) auf Cache-Metriken für eine breite Klasse von stochastischen Anfragestrommodellen zu verstehen. Eine eigens hierfür entwickelte Metrik wird als delay impairment der Objekttrefferwahrscheinlichkeit bezeichnet. Darüber hinaus wurden moderne Approximationen der Objekttrefferwahrscheinlichkeit so erweitert, um die zufälligen Netzverzögerung zu berücksichtigen. Numerische und simulationsbasierte Evaluierungsergebnisse zeigen, dass größere TTLs die nachteiligen Auswirkungen von Netzverzögerungen nicht effizient kompensieren. Die Ergebnisse des Projekts zeigen auch, dass im Gegensatz zum hier verfolgten exakten Ansatz die gängigen Approximationen die Auswirkungen der Netzverzögerung nicht gut erfassen, insbesondere bei mehrstufigen Cache-Hierarchien. Ein unerwartetes Ergebnis zeigt, dass die Auswirkung der Netzverzögerung auf die Objekttrefferwahrscheinlichkeit nicht monoton ist, sondern von den probabilistischen Eigenschaften des Anfragestroms sowie der Objekt Time-to-Live abhängt.
Publications
- Generalized Cost-Based Job Scheduling in Very Large Heterogeneous Cluster Systems. IEEE Trans. Parallel Distributed Syst. 31(11): 2594-2604 (2020)
Wasiur R. KhudaBukhsh, Sounak Kar, Bastian Alt, Amr Rizk, Heinz Koeppl
(See online at https://doi.org/10.1109/TPDS.2020.2997771) - Decentralized Low-Latency Task Scheduling for Ad-Hoc Computing. IEEE International Parallel and Distributed Processing Symposium (IPDPS) 2021: 776-785
Janick Edinger, Martin Breitbach, Niklas Gabrisch, Dominik Schäfer, Christian Becker, Amr Rizk
(See online at https://doi.org/10.1109/IPDPS49936.2021.00087) - On the Impact of Network Delays on Time-to-Live Caching. Technical Report (2022)
Karim Elsayed, Amr Rizk
(See online at https://doi.org/10.48550/arXiv.2201.11577)
