Efficient on-line routing strategies of bandwidth guaranteed paths with traffic engineering

Abstract

Das kontinuierliche Wachstum von Internet-Multimediaanwendungen zwingt Internet-Diensteanbieter neue Konzepte und Paradigmen in der effizienten Wegeauswahl mit Dienstgüte zu erforschen. Um mit Bandbreite- und anderen Dienstgüteanforderungen für Multimediaanwendungen Schritt halten zu können, sind neue, skalierbare Techniken (wie z.B. intelligente Wegeauswahlverfahren, leistungsfähige Router, Hochgeschwindigkeitsverbindungen) an den Übergängen zum Kernnetz erforderlich. Der beachtenswerte Technologiefortschritt im optischen Bereich, Bereitstellung von größeren Kapazitäten und Übertragungsgeschwindigkeiten, kann die Dienstgüte signifikant verbessern. Auf der anderen Seite ist jedoch die Bearbeitungsgeschwindigkeit bzw. Leistungsfähigkeit von heutigen Routern begrenzt. Folglich sind geringe Komplexität (was eine rasche Wegeauswahl impliziert), sowie Berücksichtigung von Dienstgüte die wichtigsten Anforderungen an zukünftige Wegeauswahlverfahren.<br />Verschiedene Wegeauswahlverfahren, die explizite Pfade (d.h. nach bestimmten Kriterien gesteuerte Pfade) bereitstellen, sind kürzlich vorgestellt und intensiv untersucht worden. Ein gutes Verfahren soll Rückweisungen zukünftiger Verbindungswünsche minimieren, während gleichzeitig der gesamte Netzdurchsatz und -qualität (z.B. begrenzte Verzögerung, geringer Jitter, geringe Verlustrate oder hoher Durchsatz) verbessert werden. Darüber hinaus soll das Verfahren eine schnelle Pfadberechnung zur Verfügung stellen, um eine kurze Reaktionszeit zu erzielen, weil der Internetverkehr von Natur aus stoßartig auftritt und die Zugangsrouter unter hoher Verkehrslast arbeiten.<br />Wegeauswahlverfahren die keinen voraussichtlichen Verlauf einer zukünftigen Entwicklung ermöglichen, sind gewöhnlich schnell aber auch "greedy" (=gierig, machtgierig, habgierig, habsüchtig, gefräßig). Dies bedeutet, es wird ein Pfad gesucht, der eine bestimmte Nebenbedingung erfüllt, jedoch wird nicht auf seine netzinternen Auswirkungen geachtet. Folglich können hohe Rückweisungen von zukünftigen Verbindungswünschen entstehen.<br />Andererseits jedoch sind "non-greedy" (=nicht gierig, etc.) Wegeauswahlverfahren berechnungsintensiv und weisen eine hohe Pfadberechnungszeit auf, infolgedessen sind sie nicht skalierbar.<br />In dieser Arbeit werden deshalb zwei generische Ansätze für die bedarfsorientierte Bereitstellung von Ende-zu-Ende Pfaden mit Nebenbedingungen vorgeschlagen. Unser erster Vorschlag basiert auf "aktueller Netz- und Leitungskapazität" und stellt ein neues Gewichtungsschema für Leitungen zur Verfügung. Dieses Gewichtungsschema kombiniert drei Kriterien: Einsparung von aktueller Leitungskapazität, optimale Verwendung der vorhandenen Netzressourcen und Minimierung der Pfadlängen. Der zweite Vorschlag kombiniert erfolgreich die beiden oben beschriebenen Ziele (d.h. voraussichtlichen Verlauf einer zukünftigen Entwicklung ermöglichen und schnelle Pfadberechnung) und mehrfache Nebenbedingungen (wie z.B. einen gegenseitigen Beeinflussungsfaktor basierend auf dem Wissen über die Verteilung der Kommunikationspartner und aktuelle Netz- und Leitungskapazität des ersten Ansatzes) in einem neuartigen Gewichtungsschema für Leitungen.<br />Die hier vorgestellten Heuristiken umgehen das grundlegende Problem der Wegeauswahl mit mehrfachen Nebenbedingungen NP-komplett), indem sie Netzparameter in einer linearen Kostenfunktion erfolgreich kombinieren.<br />Umfangreiche Simulationen (9 010 143 s entsprechen ca. 105 Tage auf einem Intel Xeon 2.4 GHz Rechner mit 1 GByte RAM and 512 KByte Cache-Speicher) zeigen, dass diese zwei neuen online Wegeauswahlverfahren, vor kurzem vorgeschlagene online Verfahren, besonders in Bezug auf erreichbaren Durchsatz, Blockierungswahrscheinlichkeit und der Umleitung von bestehenden Verbindungen, an Leistung übertreffen und dabei noch schneller und skalierbar sind. Infolgedessen sind sie für Verkehrsleitsysteme (d.h.<br />Traffic Engineering = "den vorliegenden Verkehr ingenieurmäßig zu bearbeiten") bestens geeignet.<br />

The continuous growth of Internet multimedia applications is forcing Internet service providers (ISPs) to investigate new concepts and paradigms in high-performance QoS (Quality-of-Service) routing. In order to keep pace with the bandwidth and other QoS requirements for multimedia applications, new scalable techniques (e.g., intelligent routing algorithms, fast routers, high-speed links) are needed at edges of backbone networks. Remarkable technology advances in the optical area, providing greater capacity and link speed, can significantly improve service quality. On the other hand the computing power of contemporary routers is limited. Therefore, major issues for next-generation routing algorithms are to be "high-speed" as well as "QoS-capable".<br />Several routing algorithms that provide explicit routes (e.g., label switched path) have been introduced and intensively studied in recent time. A good routing algorithm should minimize the rejection rate of future requests, while improving the overall network performance and quality (e.g., bounded delay, low jitter, small loss rate or high throughput). Further, it should provide a fast path computation to achieve short response time, because the Internet traffic is inherently bursty and edge routers usually operate under heavy traffic conditions. Routing algorithms that do not provide a predictive nature are typically fast but "greedy" in the sense that they try to find a path that meets a certain constraint, however, without considering network-wide implications. Thus, they might result in a high rejection rate of future connections. On the other hand, "non-greedy" routing algorithms are computation intensive and usually show a high path computation time, consequently they are not scalable.<br />Therefore, in this work we propose two generic approaches for on-demand provisioning of constraint-based end-to-end paths. Our first approach is based on "residual network and link capacity" and provides a new link weight function, which combines three criteria: saving of residual link bandwidth, optimal usage of network capacity, and minimization of path lengths. The second approach successfully combines both above described targets (i.e., predictive nature and fast path computation) and multiple constraints (i.e., interference values based on the knowledge of ingress-egress pairs and residual network capacity and residual link capacity of our first approach) in a novel link weight computation scheme.<br />The heuristics presented here evade the fundamental problem of multi-constraint routing (NP-complete) by successfully combining network parameters in a linear cost function. Extensive simulations (9 010 143 s equivalent to approximately 105 d on an Intel Xeon 2.4 GHz computer with 1 GByte RAM and 512 KByte cache size) exhibit that these two new on-line routing algorithms outperform recently proposed on-line routing schemes, especially in terms of achievable throughput, blocking probability, and rerouting performance while being faster and scalable, consequently best suited for traffic engineering.