DE602005005463T2 - Ein verfahren zur ermittlung von verzögerungen in einem optischen adaptivwegnetz - Google Patents

Description

• Die vorliegende Erfindung betrifft ein Verfahren zur Verzögerungsbestimmung in einem Ende-zu-Ende-Weg eines optischen Adaptivwegnetzes (APON).
• APON-Netze können Internet-Protokoll-(IP-)Pakete während des Verlaufs zwischen aufeinanderfolgenden Bursts senden. Dadurch können Randknoten ihre Aggregationspuffer beim Senden von IP-Paketen zwischen Bursts leeren. Folglich dauert die Bildung eines Bursts länger, das heißt Bursts werden mit einer niedrigeren Frequenz gesendet. Dies hat eine niedrigere mittlere Streckenauslastung zur Folge, und aus diesem Grund zeigen APON-Netze im Vergleich zu Netzen mit optischer Burst-Vermittlung (OBS) oder λ-Vermittlung eine bessere Leistungsfähigkeit. Es ist wünschenswert, daß ein Entwurf enthalten werden kann, der das Netz in Bezug auf den erforderlichen Leistungsgrad optimiert.
• YOO M et al.; "New Optical Burst Switching Protocol for Supporting Quality of Service", proceedings of the SPIE, SPIE, Bellingham, VA, US, Bd. 3531, November 1998 (1998-11), S. 396–405, XP000950072 ISSN:0277-786X, beschreibt ein priorisiertes optisches Burst-Vermittlungsprotokoll zur Verringerung der Blockierwahrscheinlichkeit von Echtzeitverkehr durch Verwendung einer zusätzlichen Offsetzeit.
• Außerdem gibt CHEN Y et al.: "Proportional QoS over OBS networks", Globecom '01. 2001 IEEE Global Telecommunications Conference: San Antonio, TX, 25.–29.11.2001, IEEE Global Telecommunications Conference, New York, NY: IEEE, US, Bd. 3 von 6, 25.11.2001 ("2001-11-25), S. 1510–1514, XP001054831 ISBN: 0-7803-7206-9 und QIAO C et al.: "Choices, features and issues in optical burst switching" Optical NEtworks magazine, SPIE, Bellingham, WA, US, Bd. 1, Nr. 2, April 2000 (2000-04), S. 36–44, XP000969814 ISSN:1388-6916, Einsichten in die optische Burst-Vermittlung.
• Gemäß der vorliegenden Erfindung ist ein Verfahren zur Bestimmung der mittleren IP-Paketverzögerung in einem Ende-zu-Ende-Weg eines optischen Adaptivwegnetzes unter Verwendung von optischen Burstvermittlungsnetzen dadurch gekennzeichnet, daß das Verfahren die folgenden Schritte umfaßt: Ableiten der mittleren IP-Paketverzögerung aus dem Produkt der mittleren Streckenauslastung von IP-Paketen in dem Netz, die in Bursts gesendet werden, und der Verzögerung in bidirektionalen optischen Reservierungs-Burst-Vermittlungsnetzen, wobei die mittlere Streckenauslastung in dem Netz, die in Bursts gesendet wird, das Verhältnis des in Bursts gesendeten mittleren Durchsatzes in Bit pro Sekunde zu der Kapazität an einer Engpaßstrecke in dem Ende-zu-Ende-Weg in dem Netz ist.
• Die vorliegende Erfindung bestimmt die Verzögerung in einem APON-Netz für jeden Ende-zu-Ende-Weg dergestalt, daß der Netzentwurf optimiert werden kann, um gewünschten Minimalverzögerungsanforderungen zu genügen. Die mittlere Verzögerung in einem Ende-zu-Ende-Weg eines APON hängt nur von der mittleren Streckenauslastung der IP-Pakete ab, die in Bursts, nicht dem λ-Vermittlungsregime, gesendet werden.
• Vorzugsweise umfaßt der mittlere in Bursts gesendete Durchsatz das Produkt der Burst-Ankunftsrate in der Engpaßstrecke und der mittleren Burstgröße.
• Vorzugsweise ist die mittlere Streckenauslastung in der Engpaßstrecke des Ende-zu-Ende-Wegs in dem Netz, die in Bursts gesendet wird, das Verhältnis der Summe von 1 bis N des Produkts des mittleren Durchsatzes zu dem Randknoten i und der Wahrscheinlichkeit, daß der Burst durch das Netz gesendet wird, ohne blockiert zu werden, minus der Summe von 1 bis N des Produkts des mittleren Durchsatzes zu dem Randknoten i und der Wahrscheinlichkeit, daß ein IP-Paket oder Burst, der durch die Engpaßstrecke gesendet wird, von dem Randknoten i kommt; zu der Kapazität minus der Summe von 1 bis N des Produkts der mittleren Auslastung zu dem Randknoten i und der Wahrscheinlichkeit, daß ein IP-Paket oder Burst, der durch die Engpaßstrecke gesendet wird, von dem Randknoten i kommt.
• Der mittlere Durchsatz und die mittlere IP-Paketverzögerung in dem Ende-zu-Ende-Weg hängen allein von der mittleren Streckenlast der Engpaßstrecke des Ende-zu-Ende-Wegs ab. Der Rest der Strecken in diesem Weg beeinflußt die Leistungsfähigkeit des APON nicht.
• Ein Beispiel für ein Verfahren zur Verzögerungsbestimmung in einem Ende-zu-Ende-Weg eines optischen Adaptivwegnetzes gemäß der vorliegenden Erfindung wird nun mit die beigefügten Zeichnungen beschrieben. Es zeigen:
• 1 ein analytisches Modell eines Ende-zu-Ende-Wegs in einem optischen Adaptivwegnetz, auf das das Verfahren der vorliegenden Erfindung angewandt werden kann;
• 2 die Bandbreitenauslastung der Engpaßstrecke des Ende-zu-Ende-Wegs von 1;
• 3 einen Vergleich des Auslastungsfaktors in der Engpaßstrecke eines Ende-zu-Ende-Wegs in einem optischen Adaptivwegnetz im Vergleich mit einem OBS-Netz und
• 4 die mittlere IP-Paketverzögerung in einem Ende-zu-Ende-Weg als Funktion der Streckenlast in dieser Engpaßstrecke für OBS-, bidirektionale Reservierungs-(2WR-)OBS- und APON-Netzen.
• 1 ist ein analytisches Modell eines Ende-zu-Ende-Wegs in einem APON-Netz, bei dem Quellenrandknoten 1, 2, von denen von 1 bis N vorliegen können, durch Netze 5, 6 über Kernknoten 7, 8 und eine Engpaßstrecke 9 der Kapaziät C mit entsprechenden Zielknoten 3, 4 verbunden sind. Die Engpaßstrecke eines Ende-zu-Ende-Wegs ist definiert als die Strecke in diesem Weg mit der höchsten mittleren Streckenauslastung. Diese Strecke wirkt sich stark auf die Netzwerkleistungsfähigkeit aus, da sie zu der höchsten Blockierwahrscheinlichkeit in dem Weg führt und für den größten Teil der Verzögerung verantwortlich sein wird, die die durch den Weg gesendeten IP-Pakete (oder Bursts) erfahren. Aus diesem Grund wurde diese Strecke als Bezug für einen Leistungsfähigkeitsvergleich in dem entsprechenden Ende-zu-Ende-Weg gewählt und es wird die mittlere Streckenauslastung in der Engpaßstrecke 9 berechnet. Die Blockierung in einem Ende-zu-Ende-Weg eines bidirektionalen Reservierungsnetzes, wie zum Beispiel APON, findet in den Quellenrandknoten 1, 2 immer dann statt, wenn sie ein nicht-Bestätigungs-(NACK-)Signal als Antwort auf ihre Wegaufbauanforderung von den Zielrandknoten 3, 4 empfangen.
• Diese Blockierung kann einfach mit einer bestimmten Blockierwahrscheinlichkeit Pb_i in dem Quellenrandknoten 1, 2 modelliert werden. Um die Notation zu vereinfachen, wird die Wahrscheinlichkeit, daß ein Burst durch den Weg gesendet wird, ohne blockiert zu werden (Pp_i) gegeben als Pp_i = 1 – Pb_i. Der ankommende mittlere IP-Paketdurchsatz durch den Randknoten i beträgt b_i in Bit pro Sekunde. Wenn λ_IPi die mittlere IP-Paketankunftsrate und μ die mittlere IP-Paketgröße ist (für alle Verbindungen gleich), lautet die Gleichung für den Randknoten i folgendermaßen: bi = λIPi·μ = λi·Bi + λioffered·(1 – Ppi)·Bi Gleichung 1
• Dabei ist λ_i die mittlere Burstankunftsrate in der optischen Strecke, B_i die mittlere Burstgröße für diese Verkehrsquelle, ^λioffered die der optischen Strecke gebotene mittlere Burst-Ankunftsrate und (1 – Pp_i) ist der Anteil der in dem Randknoten blockierten Bursts. Die Interpretation dieser Gleichung ist, daß was in einen Randknoten hineinkommt, herausgehen muß, da in dem Knoten keine Informationen erzeugt oder vernichtet werden. Die linke Seite von Gleichung 1 beschreibt den in den Randknoten kommenden mittleren IP-Paketdurchsatz. Dieser Durchsatz muß gleich dem sein, das auf der anderen Seite den Knoten verläßt, was durch die rechte Seite dieser Gleichung beschrieben wird. Die rechte Seite ist die Summe zweier Terme, wobei der erste dieser den mittleren Durchsatz der IP-Pakete repräsentiert, die bereits in Bursts transformiert wurden und dem optischen Netz geboten werden, und der zweite Term den mittleren Durchsatz von IP-Paketen repräsentiert, die blockiert und weggeworfen wurden.
• Nur die Bursts, die nicht blockiert wurden, haben Zugang zu der optischen Strecke, so daß λ_i = λ_ioffered + Pp_i gilt.
• In APON-Netzen wird die gesamte Bandbreite der Engpaßstrecke in einem Ende-zu-Ende-Weg benutzt, da IP-Pakete während des Verlaufs zwischen aufeinanderfolgenden Bursts gesendet werden. 2 stellt dies dar. Der Ausdruck 1/λ repräsentiert die mittlere Burst-Zwischen-Ankunftszeit, d. h. die vergangene Zeit zwischen der Ankunft zweier aufeinanderfolgender Bursts. Diese Zeit wird mit der Übertragungszeit eines Bursts B gefüllt, der in einer Strecke der Kapazität C B/C Sekunden dauert, und mit einer Übertragungszeit t von IP-Paketen auf dem λ-Vermittlungsregime, bei dem IP-Pakete während des Verlaufs gesendet werden.
• Die Zeit t kann in t_i, iε(1, ..., N) eingeteilt werden, wodurch der Anteil der Zeit in dem λ-Vermittlungsregime repräsentiert wird, in dem IP-Pakete aus der Quelle i während des Verlaufs gesendet werden. Um dies zu erreichen, ist es notwendig, p_i, iε(1, ..., N) einzuführen, wodurch die Wahrscheinlichkeit repräsentiert wird, daß ein IP-Paket oder ein Burst, der durch die Engpaßstrecke gesendet wird, aus der Verkehrsquelle i kommt. Dies kann auf der Basis der mitleren Ankunftsraten der Bursts von jeder Verkehrsquelle λi als p_i = λ_i/λ berechnet werden, wobei λ die mittlere Burst-Ankunftsrate an der Strecke ist.
• Je mehr IP-Pakete eine Verkehrsquelle sendet, desto wahrscheinlicher ist es, daß ein bestimmtes im λ-Vermittlungsregime in der Engpaßstrecke gesendetes IP-Paket zu dieser Quelle gehört. Die Wahrscheinlichkeit p_i, daß ein IP-Paket in der Engpaßstrecke durch den Randknoten i gesendet wurde, bestimmt deshalb die mittlere Länge t_i für das λ-Vermittlungsregime dieser Quelle. Insbesondere gilt t_i = p_i·t, wobei t die gesamte mittlere Länge des λ-Vermittlungsregimes wie in 2 gezeigt ist.
• Im λ-Vermittlungsregime leitet ein Randknoten den ankommenden mittleren IP-Paketdurchsatz b_i zu dem Netz weiter. Die Menge an aus jeder Verkehrsquelle i in seinem λ-Vermittlungsregime der Länge t_i Sekunden transferierten Bit beträgt deshalb t_i·b_i = p_i·t·b_i, wobei b_i der an der Verkehrsquelle i ankommende mittlere IP-Paketdurchsatz ist.
• Analog zu dem mit t Durchgeführten kann b auch mit Hilfe der Wahrscheinlichkeiten p_i folgendermaßen in b_i zerlegt werden:

  
• Das heißt, die mittlere Burstgröße ist die mittlere Burstgröße des ersten Quellenrandknotens mit einer Wahrscheinlichkeit p₁, des zweiten Quellenrandknotens mit einer Wahrscheinlichkeit p₂ usw.
• Demzufolge und gemäß 2 kann der mittlere Durchsatz b in dem Engpaß folgendermaßen formuliert werden:

  
• Dabei repräsentiert der erste Term der Addition die Menge an in Bursts für alle Verkehrsquellen gesendeten Bit und der zweite Term die Summe der Menge an in dem λ-Vermittlungsregime für jeden der N Verkehrsknoten gesendeten Bit.
• Gemäß 2 kann die Länge t des λ-Vermittlungsregimes folgendermaßen ausgedrückt werden

  
• So daß der mittlere Durchsatz b folgendermaßen umformuliert werden kann:

  
• Durch Auflösen nach λ_i, der mittleren Burst-Ankunftsrate in der Engpaßstrecke erhält man:

  
• Dieser Ausdruck hängt von Eingangsparametern auf der IP-Paketebene ab, mit Ausnahme der mittleren Burstgröße in dem Engpaß B. Diese Größe ist jedoch exakt dieselbe wie im OBS-Fall, da das Ein- oder Ausschalten von APON-Funktionalitäten in einem OBS-Netz nicht ändert, wie Bursts aus der Aggregation von IP-Paketen gebildet werden. Das heißt, die Bursts-Aggregationsstrategien bleiben gleich und deshalb auch die Burstgrößen. Die mittlere Burstgröße B kann also gemäß Gleichung 2 als Funktion der pro Verkehrsquelle B_i erzeugten mittleren Burstgröße berechnet werden. Die von jeder Verkehrsquelle erzeugte mittlere Burstgröße B_i kann gemäß der in jedem Randknoten verwendeten entsprechenden Aggregationsstrategie aus dem IP-Verkehrsparametern berechnet werden.
• Um einen Verzögerungsausdruck für APON-Netz zu erhalten, ist es notwendig, die mittlere Streckenauslastung ρ_APON in zwei Terme aufzuteilen. Der erste dieser ist die mittlere Streckenauslastung von IP-Paketen, die im λ-Vermittlungsregime gesendet werden, und der zweite die mittlere Streckenauslastung von IP-Paketen, die in Bursts gesendet werden. Der erste wird als ρ_{APON_A-switching} und der zweite als ρ_{APON_OBS} bezeichnet. Die Definitionen jedes Streckenauslastungsfaktors sind wie folgt:

  
• Dieser Ausdruck kommt von der rechten Seite von Gleichung 3.
• 
• Dieser Ausdruck kommt von der linken Seite von Gleichung 3.
• Gleichung 8 wird benötigt, um die mittlere IP-Paketverzögerung in APON-Netzen zu berechnen, so daß sie als Funktion der Eingangs-IP-Verkehrsparameter ausgedrückt wird:

  
• Für die Berechnung der mittleren IP-Paketverzögerung in APON-Netzen kann die Verzögerung, die ein IP-Paket in OBS-Netzen erfährt, als Addition zweier Terme ausgedrückt werden. Diese sind die Zeit, die das Paket in dem Randknoten verbringt (t_edge), während der Burst gebildet wird, und die erfahrene Verzögerung, während die Vermittlungen auf dem Weg konfiguriert werden (t_setup)
• Demzufolge beträgt die mittlere IP-Paketverzögerung in 2WR-OBS-Netzen:

  
• Wobei t_RTT die mittlere Gesamtlaufzeit für ein Kopfpaket aufgrund der bidirektionalen Reservierung ist.
• Sobald die Leitungen in einem statischen λ-Vermittlungsnetz hergestellt wurden, erfahren die Pakete keine Verzögerung und kein Verzögerungs-Jitter, nur die gewöhnliche Laufzeit, wenn sie durch das Netz übertragen werden. Deshalb ist die Paketverzögerung (und das Verzögerungs-Jitter) während des Betriebs eines λ-Vermittlungsnetzes null. E[Delayλ-switching] = 0 Gleichung 11
• APON-Netze weisen eine niedrigere Verzögerung als 2WR-OBS-Netze auf, weil im λ-Vermittlungsregime übertragene Pakete keine Verzögerung (und kein Verzögerungs-Jitter) erfahren. Die Netzlast bestimmt den Anteil der im λ-Vermittlungsregime transferierten IP-Pakete, wodurch bestimmt wird, ob die gesamte mittlere Verzögerung sich der Verzögerung in λ-Vermittlungsnetzen (Verzögerung null) oder der Verzögerung in 2WR-OBS-Netzen nähert. Wenn ρ_{APON-A-switching} die mittlere Streckenlast von im λ-Vermittlungsregime gesendeten IP-Paketen und ρ_APON-OBS die mittlere Streckenlast von IP-Paketen ist, die in Bursts in der Engpaßstrecke eines gegebenen Ende-zu-Ende-Wegs gesendet werden, kann die mittlere Verzögerung in diesem Weg des APON-Netzes folgendermaßen berechnet werden: E[VerzögerungAOPN] = ρAPON-λ-switching·E⎣Verzögerungλ-switching⎦ + ρAPON-OBS·E[Verzögerung2WR-OBS] Gleichung 12
• Da die Verzögerung in λ-Vermittlungsnetzen null ist, kann die Gleichung folgendermaßen vereinfacht werden: E[VerzögerungAOPN] = ρAPON-OBS·E[Verzögerung2WR-OBS] Gleichung 13
• Da die Streckenauslastung ρ immer kleiner als 1 ist, zeigt die obige Gleichung, daß die Verzögerung in APON-Netzen kleiner als die in 2WR-OBS-Netzen ist. Für Streckenauslastungslasten in der Nähe von null tendiert die Verzögerung zu null, wodurch die Tatsache ausgedrückt wird, daß in diesem Fall der größte Teil der IP-Pakete durch den Weg im λ-Vermittlungsregime und nicht in Bursts gesendet wird. Bei hohen Auslastungslasten (in der Nähe von eins) tendiert die Verzögerung zu der Verzögerung in 2WR-OBS-Netzen, wodurch die Tatsache ausgedrückt wird, daß in diesem Fall der größte Teil der IP-Pakete in Bursts gesendet wird. Die abgeleitete mathematische Formel von Gleichung 9 ermöglicht die Berechnung des Streckenauslastungsfaktors in APON-Netzen sowie die Verwendung dieser Formel als Grundlage für die APON-Verzögerungsformel von Gleichung 13.
• Vorteile des Verfahrens der vorliegenden Erfindung sind etwa die Tatsache, daß es ein exaktes Verfahren ist, da keinerlei Approximationen erfolgen; es ist für jede beliebige Art von Verkehrsstatistik gültig, wie etwa Poisson-Verkehr oder selbstähnlicher Verkehr, wodurch das Modell sowohl in Zugangs- als auch in Kernnetzen verwendet werden kann; und es ist gültig für jede beliebige APON-Netztopologie. Das Verfahren ist leicht zu implementieren und zu berechnen, wodurch es für seine Implementierung in APON-Randknoten, APON-Kernknoten oder in Planungswerkzeugen geeignet wird; und es ermöglicht einen Vergleich der Leistungsfähigkeit-, OBS- und λ-Vermittlungsnetzen im Hinblick auf Verzögerung.
• Die Graphen von 3 und 4 zeigen ein Beispiel für Streckenauslastung und für Verzögerung als Funktion der Netzlast, die sich mit dem Verfahren der vorliegenden Erfindung erhalten läßt. Aus 3 ist ersichtlich, daß die mittlere Streckenauslastung in APON-Netzen 20 immer kleiner als die mittlere Streckenauslastung in OBS-Netzen 21 ist, mit Ausnahme der unrealistischen Streckenauslastungswerte 0 und 1. Aus diesem Grund ist die Leistungsfähigkeit von APON-Netzen im Hinblick auf Blockierwahrscheinlichkeit und Verzögerung immer höher. Bei mittel bis stark belasteten Netzen, d. h. für eine Streckenauslastung zwischen 0,4 und 0,8, befindet sich die Reduktion der Streckenauslastung in APON-Netzen im Vergleich zu OBS-Netzen auf ihrem Maximum. Dadurch wird sie zu einem sehr attraktiven Arbeitsbereich für jedes optische Netz.
• In 4 ist gezeigt, daß die Verzögerung in APON-Netzen 22 weitaus kleiner als die Verzögerung in OBS-Netzes 23 bei 1 × 10^–3 und bei 2WR-OBS-Netzen 24 bei 1,5 × 10^–3 ist. Dies gilt für Streckenauslastungen unter 0,9. Dieses wäre der ideale Arbeitsbereich für jedes beliebige optische Netz. Die Leistungsfähigkeitszunahme im Hinblick auf Verzögerung von APON-Netzen ist bei niedrigeren Streckenauslastungen höher.
• Die vorliegende Erfindung schafft ein Verfahren zur Bestimmung der mittleren Verzögerung in einem optischen Adaptivwegnetz. Dies umfaßt die Berechnung der Streckenauslastung in APON-Netzen auf eine Weise, die für jede beliebige Burstgrößen verteilung und jede beliebige Zwischen-Ankunfts-Zeitverteilung zwischen Bursts, d. h. nicht nur für Poisson-Verkehr exakt und gültig ist. Die abgeleitete Verzögerungsformel für APON-Netze basiert auf der neuen Streckenauslastungsberechnung. Mit der Verzögerungsformel kann man die mittlere IP-Paketverzögerung in jedem beliebigen APON-Netz berechnen. Diese Formel hat mehrere Anwendungen, wie etwa Verwendung als Planungswerkzeug zum Entwurf von APON-Netzen, die eine bestimmte maximal zulässige Verzögerung erfüllen, Verwendung in APON-Randknoten als Kern eines Zulassungssteuermechanismus, der Bursts abhängig davon, ob durch die zusätzliche Last die mittlere Netzverzögerung eine bestimmte Grenze übersteigt oder nicht annimmt oder zurückweist; Verwendung als Hilfe für einen Routing-Algorithmus zum Ausgleich einer Last, so daß alle Ende-zu-Ende-Wege ungefähr dieselbe mittlere Verzögerung aufweisen; und Verwendung als Hilfe für einen Dienstgüte (QoS-)Routing-Algorithmus zum Routen von Bursts mit hoher Priorität durch Wege mit niedriger Verzögerung.

Claims (3)

1. Verfahren zum Bestimmen der mittleren IP-Paketverzögerung in einem Ende-zu-Ende-Weg eines optischen Adaptivwegnetzes, das optische Netze mit optischer Burstvermittlung verwendet, dadurch gekennzeichnet, daß das Verfahren den folgenden Schritt umfaßt: Ableiten einer mittleren IP-Paketverzögerung aus dem Produkt der mittleren Streckenauslastung von IP-Paketen in dem Netz, die in Bursts gesendet werden, und der Verzögerung in bidirektionalen optischen Burstvermittlungsnetzen mit Reservierung, wobei die mittlere Streckenauslastung in dem Netz, die in Bursts gesendet wird, das Verhältnis des in Bursts gesendeten mittleren Durchsatzes in Bit pro Sekunde der Kapazität einer Engpaßstrecke in dem Ende-zu-Ende-Weg in dem Netz ist.
2. Verfahren nach Anspruch 1, wobei der in Burst gesendete mittlere Durchsatz das Produkt der Burstankunftsrate in der Engpaßstrecke und der mittleren Burstgröße umfaßt.
3. Verfahren nach Anspruch 1, wobei die mittlere Streckenauslastung in der Engpaßstrecke des Ende-zu-Ende-Weges in dem Netz, die in Bursts gesendet wird, das Verhältnis der Summe von 1 bis N des Produkts des mittleren Durchsatzes zu dem Randknoten i und der Wahrscheinlichkeit, daß der Burst durch das Netz gesendet wird, ohne blockiert zu werden, minus der Summe von 1 bis N des Produkts des mittleren Durchsatzes zu dem Randknoten i und der Wahrscheinlichkeit, daß ein IP-Paket oder Burst, der durch die Engpaßstrecke gesendet wird, aus dem Randknoten i kommt; zu der Kapazität minus der Summe von 1 bis N des Produkts des mittleren Durchsatzes zu dem Randknoten i und der Wahrscheinlichkeit, daß ein IP-Paket oder Burst, der durch die Engpaßstrecke gesendet wird, aus dem Randknoten i kommt, ist.