direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

There is no English translation for this web page.

Thema:
Background Optimization In Networks With Adavance Reservation
Bearbeiter:
Stephan Schmidt
Aufgabenstellung:
In dieser Diplomarbeit wird ein Framework für Computernetzwerke mit Vorausreservierungen
vorgestellt, welches durch kontinuierliche Reoptimierung zur Umverteilung der Netzwerklast eine höhere durchschnittliche Ausnutzung der
Netzwerkkapazität gegenüber ausschließlich auf Standard-Routingverfahren basierenden
Architekturen erreicht.
Falls eine bestimmte Dienstgüte (Quality of Service, QoS) für eine Verbindung erforderlich ist, im Mindestfall eine garantierte verfügbare Bandbreite über einen gewissen Zeitraum, ist es sinnvoll, die benötigten Ressourcen einen
längeren Zeitraum vor dem eigentlichen Start der Übertragung zu reservieren.
Dies ist zwar mit einem höheren administrativen Aufwand verbunden, jedoch bietet das Konzept der Vorausreservierung auch verschiedene Vorteile: einerseits
erhöht sich bei ausreichend früher Reservierung die Wahrscheinlichkeit, dass die Verbindung erfolgreich eingerichtet werden kann, andererseits können im Falle einer Ablehnung die erforderlichen Maßnahmen in die Wege geleitet werden, um die Verbindung auf eine alternative Weise, beispielsweise über einen anderen Dienstanbieter, herzustellen. Der Dienstanbieter kann seinerseits aus den eingehenden Vorausreservierungsanfragen die zukünftig entstehende Netzwerklast berechnen und entscheiden, welche Anfragen hinsichtlich der Profitmaximierung angenommen und welche abgelehnt werden. Die Gewährleistung von Dienstgüte für Verbindungen hinsichtlich verschiedener qualitativer Parameter wie Übertragungsverzögerung, Paketverlustrate oder Jitter (Standardabweichungsrate
in der Paketankunftszeit) hängt ebenfalls in entscheidendem Maße von der verfügbaren Bandbreite innerhalb eines Netzwerks ab.
In dieser Diplomarbeit wird untersucht, wie sich der Durchsatz von Netzwerken, in denen Vorausreservierungen möglich sind, durch eine vorteilhafte Umverteilung der Netzwerklast steigern lässt. Eine gleichmäßige Lastverteilung kann unter anderem erreicht werden, indem eintreffende Verbindungen entlang Pfaden geroutet werden, die den übrigen Netzwerkverkehr in möglichst geringem Maße beeinträchtigen, um so die Entstehung von Engpässen zu verhindern.
Dieser Ansatz weist jedoch einige Schwachpunkte auf. Einerseits erfordert ein Algorithmus, der eine solche Pfadauswahl für jede eingehende Anfrage vornimmt, erheblich höheren Rechenaufwand als ein einfacher Standard-Routing-Algorithmus, was sich je nach dessen Komplexität bei steigender Anzahl von Anfragen negativ auf die Skalierbarkeit auswirkt; andererseits kann aufgrund fehlender Informationen bezüglich des zukünftigen Anfragemusters eine global optimale Pfadauswahl nicht garantiert werden.
Aus diesem Grund haben wir uns entschieden, eingehende Reservierungsanfragen einem einfachen Min-Hop-Routingalgorithmus zu unterwerfen und die
Pfadoptimierung im Hintergrund durchzuführen. Zu diesem Zweck kommt ein Algorithmus zum Einsatz, der den Fluss innerhalb des Netzwerkes so umverteilt, dass nach der Optimierung das Verhältnis der zur Verfügung stehende Bandbreite und der Bandbreite der erwarteten Anfragen für alle Sender-Empfänger-Paare innerhalb des Netzwerkes maximal ist; da es nicht möglich ist, das zu erwartende Verkehrsmuster vorherzusagen, wird es aus dem zum Zeitpunkt der Optimierung vorliegenden Muster abgeleitet.
Dieses Optimierungskriterium entspricht dem aus der Netzwerkflusstheorie  bekannten Maximum Concurrent Flow Problem. Um exorbitante Laufzeiten auszuschließen
verwenden wir zur Lösung dieses Problems einen von Garg und Könemann [9] entworfenen und von Fleischer [7] weiterentwickelten approximativen Algorithmus, der in polynomialer Laufzeit eine Lösung bestimmt, die höchstens um ein frei wählbares Fehlerintervall o von der Optimallösung abweicht. Aufgrund seiner zentralen Bedeutung für die vorliegende Arbeit wird der Algorithmus zusammen mit allen für das vorliegende Vorausreservierungsszenario nötigen Anpassungen ausführlich vorgestellt.
Eine Vorausreservierung kann innerhalb einer festen zukünftigen Zeitspanne vorgenommen werden. Diese Zeitspanne wird in Abschnitte gleicher Länge, sogenannte Slots, eingeteilt; die Granularität liegt dabei im Ermessen des Dienstanbieters. Reservierungen sind für eine feste Anzahl aufeinanderfolgender Slots möglich, was bedeutet, dass sich der Netzwerkfluss innerhalb eines Slots nicht ändert. Der oben genannte Algorithmus wird daher fortlaufend auf die einzelnen Slots angewendet, wobei bereits angenommene Vorausreservierungen von den
zuvor zugewiesenen auf optimalere Pfade umgelegt werden. Die Auswahl des jeweils nächsten zu optimierenden Slots erfolgt dabei nicht chronologisch sondern aufgrund heuristischer Überlegungen, wodurch ineffektive Optimierungsvorgänge verhindert werden.
Während der Betriebszeit des Netzwerks werden Reservierungsanfragen, für
die zum Zeitpunkt ihres Eintreffens keine ausreichende Bandbreite verfügbar ist, in eine Warteschlange aufgenommen. Sie können dort so lange vorgehalten
werden, bis die Zeitspanne, innerhalb derer der Anfrager über Annahme oder Ablehnung unterrichtet werden muss, abgelaufen ist. Innerhalb dieser Zeitspanne kann mittels Optimierung der Durchsatz für die betreffenden Slots erhöht werden, so dass die Anfrage eventuell positiv beschieden werden kann.
Die Simulationsergebnisse für das vorgestellte Framework zeigen, dass eine durchgehend höhere Annahmerate für Reservierungen erzielt werden kann wenn die Optimierung im Hintergrund durchgeführt wird als wenn dies nicht
der Fall ist. Die Steigerung, die auf diese Weise erzielt werden kann, hängt von den gewählten frameworkspezifischen Einstellungen und dem gewählten Anfragemuster ab. Zusätzlich kann die maximale Ablehnungsrate für alle Sender-Empfänger-Paare innerhalb des Netzwerks deutlich gesenkt werden. Dies bedeutet,
dass aufgrund der höheren Wahrscheinlichkeit, eingehende Verbindungsanfragen erfolgreich herzustellen, eine größere Benutzerakzeptanz erreicht werden
kann. Gleichzeitig ist es möglich, aufgrund der höheren durchschnittlich für jede Verbindung zur Verfügung stehenden Bandbreite eine höhere Dienstgüte zu
gewährleisten.

Das Dateilinks-Plugin steht nicht mehr zur Verfügung. Bitte verwenden Sie statt dessen das Plugin TUB Downloadliste.
Für die Löschung des alten Inhaltselements wenden Sie sich bitte an webmaster unter Nennung des Direktzugangs.

Zusatzinformationen / Extras

Quick Access:

Schnellnavigation zur Seite über Nummerneingabe

Auxiliary Functions