Routing und Wellenlängenzuweisung – Wikipedia

Posted on December 30, 2020 by lordneo

before-content-x4

Das Routing und Wellenlängenzuweisung (RWA) Problem ist ein optisches Netzwerkproblem mit dem Ziel, die Anzahl der optischen Verbindungen zu maximieren.

Table of Contents

Definition[edit]

Das allgemeine Ziel des RWA-Problems besteht darin, die Anzahl der hergestellten Verbindungen zu maximieren. Jede Verbindungsanforderung muss eine Route und eine Wellenlänge erhalten. Die Wellenlänge muss für den gesamten Pfad konsistent sein, es sei denn, die Verwendung von Wellenlängenkonvertern wird angenommen. Zwei Verbindungsanforderungen können dieselbe optische Verbindung verwenden, sofern eine andere Wellenlänge verwendet wird.

Das RWA-Problem kann formal in einem ganzzahligen linearen Programm (ILP) definiert werden. Die hier angegebene ILP-Formulierung stammt aus.^[1]

Maximieren:

{ displaystyle C_ {0} ( rho, q) = sum _ {i = 1} ^ {N_ {sd}} m_ {i}}

vorbehaltlich

{ displaystyle m_ {i} geq 0, Ganzzahl, i = 1,2, …, N_ {sd}}

{ displaystyle c_ {ij} in {0,1}, i = 1,2, …, P, j = 1,2, …, W}

{ displaystyle C ^ {T} B leq l_ {W times L}}

{ displaystyle m leq 1_ {W} C ^ {T} A}

{ displaystyle m_ {i} leq q_ {i} rho, i = 1,2, …, N_ {sd}}

{ displaystyle N_ {sd}}

${ displaystyle N_ {sd}}$ ist die Anzahl der Quelle-Ziel-Paare, während

{ displaystyle m_ {i}}

$m_ {i}$ ist die Anzahl der Verbindungen, die für jedes Quelle-Ziel-Paar hergestellt wurden.

{ displaystyle L}

$L.$ ist die Anzahl der Links und

{ displaystyle W}

$W.$ ist die Anzahl der Wellenlängen.

{ displaystyle P}

$P.$ ist der Satz von Pfaden zum Weiterleiten von Verbindungen.

{ displaystyle A: P times N_ {sd}}

${ displaystyle A: P times N_ {sd}}$ ist eine Matrix, die zeigt, welche Quelle-Ziel-Paare aktiv sind.

{ displaystyle B: P times L}

${ displaystyle B: P times L}$ ist eine Matrix, die zeigt, welche Links aktiv sind, und

{ displaystyle C: P times W}

${ displaystyle C: P times W}$ ist eine Routen- und Wellenlängenzuweisungsmatrix.

Es ist zu beachten, dass die obige Formulierung voraussetzt, dass die Verkehrsanforderungen bekannt sind a priori. Diese Art von Problem wird als Static Lightpath Establishment (SLE) bezeichnet. Die obige Formulierung berücksichtigt auch nicht die Signalqualität.

Es wurde gezeigt, dass das SLE RWA-Problem in NP-vollständig ist.^[2] Der Beweis beinhaltet eine Reduzierung auf die

{ displaystyle n}

$n$ -graph Färbbarkeitsproblem. Mit anderen Worten, das Lösen des SLE RWA-Problems ist so komplex wie das Ermitteln der chromatischen Zahl eines allgemeinen Graphen. Da die dynamische RWA komplexer ist als die statische RWA, muss die dynamische RWA auch NP-vollständig sein.

Ein weiterer NP-vollständiger Beweis ist in gegeben.^[3] Dieser Beweis beinhaltet eine Reduzierung des Multi-Commodity-Flow-Problems.

Das RWA-Problem wird durch die Notwendigkeit, die Signalqualität zu berücksichtigen, weiter kompliziert. Viele der optischen Beeinträchtigungen sind nichtlinear, daher kann ein Standardalgorithmus für kürzeste Wege nicht verwendet werden, um sie optimal zu lösen, selbst wenn wir den genauen Zustand des Netzwerks kennen. Dies ist normalerweise keine sichere Annahme, daher müssen Lösungen effizient sein und nur begrenzte Netzwerkinformationen verwenden.

Methodik[edit]

Angesichts der Komplexität von RWA gibt es zwei allgemeine Methoden zur Lösung des Problems:

Die erste Methode besteht darin, zuerst den Routing-Teil zu lösen und dann eine zweite Wellenlänge zuzuweisen. Drei Arten der Routenauswahl sind Festpfad-Routing, Festes Alternatives Routing und Adaptives Routing.
Der zweite Ansatz besteht darin, sowohl die Routenauswahl als auch die Wellenlängenzuweisung gemeinsam zu berücksichtigen.

Erst Routing, dann Wellenlängenzuweisung[edit]

Routing-Algorithmen[edit]

Feste Pfadführung[edit]

Das Routing mit festen Pfaden ist der einfachste Ansatz, um einen Lichtweg zu finden. Es wird immer dieselbe feste Route für ein bestimmtes Quell- und Zielpaar verwendet. In der Regel wird dieser Pfad im Voraus mit einem Algorithmus für kürzeste Pfade wie dem Dijkstra-Algorithmus berechnet. Obwohl dieser Ansatz sehr einfach ist, reicht die Leistung normalerweise nicht aus. Wenn Ressourcen entlang des festen Pfads verwendet werden, werden zukünftige Verbindungsanforderungen blockiert, obwohl möglicherweise andere Pfade vorhanden sind.

Der SP-1-Algorithmus (Shortest Path, 1 Probe) ist ein Beispiel für eine Routing-Lösung mit festem Pfad. Dieser Algorithmus berechnet den kürzesten Weg unter Verwendung der Anzahl der optischen Router als Kostenfunktion. Eine einzelne Sonde wird verwendet, um die Verbindung auf dem kürzesten Weg herzustellen. Die Laufzeit sind die Kosten des Dijkstra-Algorithmus:

{ displaystyle O (m + n log n)}

${ displaystyle O (m + n log n)}$ , wo

{ displaystyle m}

$m$ ist die Anzahl der Kanten und

{ displaystyle n}

$n$ ist die Anzahl der Router. Die Laufzeit ist nur eine Konstante, wenn ein vorgegebener Pfad verwendet wird.

Diese Definition von SP-1 verwendet die Sprungzahl als Kostenfunktion. Der SP-1-Algorithmus könnte erweitert werden, um verschiedene Kostenfunktionen wie die Anzahl der EDFAs zu verwenden.

Alternatives Routing behoben[edit]

Das feste alternative Routing ist eine Erweiterung des festen Pfadroutings. Anstatt nur eine feste Route für ein bestimmtes Quell- und Zielpaar zu haben, werden mehrere Routen gespeichert. Die Sonden können seriell oder parallel gesendet werden. Für jede Verbindungsanforderung versucht der Quellknoten, auf jedem der Pfade eine Verbindung zu finden. Wenn alle Pfade fehlschlagen, wird die Verbindung blockiert. Wenn mehrere Pfade verfügbar sind, wird nur einer davon verwendet.

Die SP-

{ displaystyle p}

$p$ (Kürzester Weg,

{ displaystyle p}

$p$ Sonden,

{ displaystyle p> 1}

$p> 1″/></span>) Algorithmus ist ein Beispiel für festes alternatives Routing. Dieser Algorithmus berechnet die <span class=$

{ displaystyle p}

$p$ kürzeste Wege unter Verwendung der Anzahl der optischen Router als Kostenfunktion. Die Laufzeit mit dem Yen-Algorithmus ^[4] ist

{ displaystyle O (pn (m + n log n))}

${ displaystyle O (pn (m + n log n))}$ wo

{ displaystyle m}

$m$ ist die Anzahl der Kanten,

{ displaystyle n}

$n$ ist die Anzahl der Router und

{ displaystyle p}

$p$ ist die Anzahl der Pfade. Die Laufzeit ist ein konstanter Faktor, wenn die Pfade vorberechnet werden.

Adaptives Routing[edit]

Das Hauptproblem sowohl beim Festpfad-Routing als auch beim festen alternativen Routing besteht darin, dass keiner der Algorithmen den aktuellen Status des Netzwerks berücksichtigt. Wenn die vorgegebenen Pfade nicht verfügbar sind, wird die Verbindungsanforderung blockiert, obwohl möglicherweise andere Pfade vorhanden sind. Fixed Path Routing und Fixed Alternate Routing sind beide nicht qualitätsbewusst. Aus diesen Gründen findet der größte Teil der Forschung in RWA derzeit in adaptiven Algorithmen statt. Fünf Beispiele für adaptives Routing sind LORA, PABR, IA-BF, IA-FF und AQoS.

Adaptive Algorithmen lassen sich in zwei Kategorien einteilen: traditionell und physikalisch bewusst. Herkömmliche adaptive Algorithmen berücksichtigen die Signalqualität nicht, physikalisch bewusste adaptive Algorithmen jedoch.

Traditionelle adaptive RWA[edit]

Der lexikografische Routing-Algorithmus (LORA) wurde in vorgeschlagen.^[5] Die Hauptidee hinter LORA besteht darin, Verbindungsanfragen von überlasteten Bereichen des Netzwerks wegzuleiten, wodurch die Wahrscheinlichkeit erhöht wird, dass Verbindungsanfragen akzeptiert werden. Dies wird erreicht, indem die Kosten für jede Verbindung festgelegt werden

{ displaystyle cost (l) = beta ^ {usage (l)}}

${ displaystyle cost (l) = beta ^ {usage (l)}}$ wo

{ displaystyle beta}

$Beta$ ist ein Parameter, der dynamisch an die Verkehrslast angepasst werden kann und

{ displaystyle usage (l)}

${ displaystyle usage (l)}$ ist die Anzahl der Wellenlängen, die bei der Verbindung verwendet werden

{ displaystyle l}

$l$ . Ein Standardalgorithmus für den kürzesten Pfad kann dann verwendet werden, um den Pfad zu finden. Dies erfordert, dass jeder optische Schalter regelmäßig aktuelle Nutzungsinformationen sendet. Beachten Sie, dass LORA keine körperlichen Beeinträchtigungen berücksichtigt.

Wann

{ displaystyle beta}

$Beta$ gleich eins ist, ist der LORA-Algorithmus identisch mit dem SP-Algorithmus. Den Wert von erhöhen

{ displaystyle beta}

$Beta$ erhöht die Tendenz zu weniger genutzten Routen. Der optimale Wert von

{ displaystyle beta}

$Beta$ kann mit dem bekannten Bergsteigeralgorithmus berechnet werden. Die optimalen Werte von

{ displaystyle beta}

$Beta$ waren zwischen 1,1 und 1,2 im Vorschlag.

Physisch bewusste adaptive RWA[edit]

Der physikalisch bewusste Rückwärtsreservierungsalgorithmus (PABR) ist eine Erweiterung von LORA. PABR kann die Leistung auf zwei Arten verbessern: unter Berücksichtigung physikalischer Beeinträchtigungen und verbesserter Wellenlängenauswahl. Während PABR nach einem optischen Pfad sucht, werden Pfade mit einer aufgrund linearer Beeinträchtigungen nicht akzeptablen Signalqualität beschnitten. Mit anderen Worten, PABR ist LORA mit einer zusätzlichen Qualitätsbeschränkung.

Beachten Sie, dass PABR nur lineare Beeinträchtigungen berücksichtigen kann. Die nichtlinearen Beeinträchtigungen wären dagegen in einer verteilten Umgebung aufgrund ihres Erfordernisses globaler Verkehrskenntnisse nicht abschätzbar.

PABR berücksichtigt auch die Signalqualität bei der Wellenlängenauswahl. Dies wird erreicht, indem alle Wellenlängen mit einem nicht akzeptablen Signalqualitätsniveau aus der Betrachtung entfernt werden. Der Ansatz heißt Quality First Fit und wird im folgenden Abschnitt erläutert.

Sowohl LORA als auch PABR können entweder mit Einzel- oder Mehrfachprüfung implementiert werden. Die maximale Anzahl von Sonden

{ displaystyle p}

$p$ wird als LORA- bezeichnet

{ displaystyle p}

$p$ oder PABR-

{ displaystyle p}

$p$ . Bei der Einzelprüfung wird bei der Routenauswahl nur ein Pfad ausgewählt. Bei der Mehrfachprüfung werden mehrere Pfade parallel versucht, was die Wahrscheinlichkeit eines Verbindungserfolgs erhöht.

Andere Routing-Ansätze[edit]

IA-BF – Der IA-BF-Algorithmus (Impairment Aware Best Fit) wurde in vorgeschlagen.^[6] Dieser Algorithmus ist ein verteilter Ansatz, der von einer großen Menge an Kommunikation abhängig ist, um mithilfe globaler Informationen immer den kürzesten verfügbaren Pfad und die kürzeste Wellenlänge auszuwählen. Dies wird durch die Verwendung von seriellem Multi-Probing erreicht. Der kürzeste verfügbare Pfad und die kürzeste Wellenlänge werden zuerst versucht, und bei einem Fehler wird der zweitkürzeste verfügbare Pfad und die zweitlängste Wellenlänge versucht. Dieser Prozess wird fortgesetzt, bis ein erfolgreicher Pfad und eine erfolgreiche Wellenlänge gefunden wurden oder alle Wellenlängen versucht wurden.

Der Multi-Probing-Ansatz ermöglicht es IA-BF, sowohl PABR-1 als auch LORA-1 zu übertreffen. Mit zunehmender Anzahl von Sonden ist die Leistung der Algorithmen jedoch ähnlich.

IA-FF – Impairment Aware First Fit (IA-FF) ist eine einfache Erweiterung von IA-BF. Anstatt die Wellenlängen im Hinblick auf die minimalen Kosten auszuwählen, werden die Wellenlängen in der Reihenfolge ihres Index ausgewählt. IA-BF tendiert in den meisten Szenarien dazu, IA-FF zu übertreffen.

AQoS – Adaptive Quality of Service (AQoS) wurde in vorgeschlagen.^[7] Dieser Algorithmus ist in vielerlei Hinsicht einzigartig. Erstens verwaltet jeder Knoten zwei Zähler:

{ displaystyle N_ {BER}}

${ displaystyle N_ {BER}}$ und

{ displaystyle N_ {wave}}

${ displaystyle N_ {wave}}$ . Der Zweck jedes Zählers besteht darin, zu bestimmen, welches Problem ein größerer Faktor beim Blockieren ist: Pfad- und Wellenlängenverfügbarkeit oder Qualitätsanforderungen. Der Algorithmus wählt Routen basierend auf dem größeren Problem unterschiedlich aus.

Ein weiterer Unterschied besteht darin, dass AQoS den Q-Faktor als Verbindungskosten verwendet. Die Kosten für die

{ displaystyle i_ {th}}

$i _ {{th}}$ Link wird nach dieser Formel berechnet

{ displaystyle D_ {i} = { frac { sum _ {j = 1} ^ {N_ {i}} 10 log[Q_{i,j}^{(s)}/Q_{i,j}^{(d)}]} {N_ {i}}}}

${ displaystyle D_ {i} = { frac { sum _ {j = 1} ^ {N_ {i}} 10 log[Q_{i,j}^{(s)}/Q_{i,j}^{(d)}]} {N_ {i}}}}$ wo

{ displaystyle N_ {i}}

$N_ {i}$ ist die Anzahl der Lichtwege auf dem

{ displaystyle i_ {th}}

$i _ {{th}}$ Verknüpfung,

{ displaystyle Q_ {i, j} ^ {(s)}}

${ displaystyle Q_ {i, j} ^ {(s)}}$ und

{ displaystyle Q_ {i, j} ^ {(d)}}

${ displaystyle Q_ {i, j} ^ {(d)}}$ sind die Qualitätsfaktormessungen der

{ displaystyle j_ {th}}

$j _ {{th}}$ Lichtweg an den Quell- und Zielknoten des

{ displaystyle i_ {th}}

$i _ {{th}}$ Link. Die wiederholten Schätzungen des Qualitätsfaktors sind rechenintensiv.

Dieser Algorithmus ist ein Single-Probing-Ansatz. Der Multi-Probing-Ansatz, den das Papier ALT-AQoS (Alternate AQoS) nennt, ist eine einfache Erweiterung derselben Grundidee.

Wellenlängenzuordnung[edit]

Zwei der gebräuchlichsten Methoden zur Wellenlängenzuweisung sind First Fit und Random Fit. First Fit wählt die verfügbare Wellenlänge mit dem niedrigsten Index. Random Fit bestimmt, welche Wellenlängen verfügbar sind, und wählt dann zufällig aus. Die Komplexität beider Algorithmen ist

{ displaystyle O (w)}

${ displaystyle O (w)}$ , wo

{ displaystyle w}

$w$ ist die Anzahl der Wellenlängen. First Fit übertrifft Random Fit.

Eine Erweiterung auf First Fit und Random Fit wurde in vorgeschlagen ^[5] Signalqualität zu berücksichtigen. Quality First Fit und Quality Random Fit eliminieren Wellenlängen, die eine nicht akzeptable Signalqualität aufweisen. Die Komplexität dieser Algorithmen ist jedoch höher als bis zu

{ displaystyle w}

$w$ Aufrufe zur Schätzung des Q-Faktors sind erforderlich.

Es gibt mehrere andere Wellenlängenzuweisungsalgorithmen: Am wenigsten verwendet, Am häufigsten verwendet, Min. Produkt, Am wenigsten geladen, Max. Summe,^[8] und relativer Kapazitätsverlust.^[9] Die meisten Verwendungszwecke übertreffen die am wenigsten Verwendeten deutlich und übertreffen First Fit geringfügig. Min Product, Least Loaded, Max Sum und Relative Capacity Loss versuchen alle, eine Wellenlänge zu wählen, die die Wahrscheinlichkeit minimiert, dass zukünftige Anforderungen blockiert werden.

Ein wesentlicher Nachteil dieser Algorithmen besteht darin, dass sie einen erheblichen Kommunikationsaufwand erfordern und daher nur dann unpraktisch zu implementieren sind, wenn Sie über eine zentralisierte Netzwerkstruktur verfügen.

Gemeinsames Routing und Wellenlängenzuweisung[edit]

Ein alternativer Ansatz zur getrennten Auswahl einer Route und einer Wellenlänge besteht darin, sie gemeinsam zu betrachten. Diese Ansätze sind eher theoretisch und wenig praktisch. Da es sich um ein NP-vollständiges Problem handelt, ist eine genaue Lösung wahrscheinlich nicht möglich. Die Approximationstechniken sind normalerweise auch nicht sehr nützlich, da sie eine zentrale Steuerung und normalerweise vordefinierte Verkehrsanforderungen erfordern. Zwei gemeinsame Ansätze sind ILP-Formulierung und Island Hopping.

Die oben aufgeführte ILP-Formulierung kann unter Verwendung eines herkömmlichen ILP-Lösers gelöst werden. Dies geschieht normalerweise, indem die ganzzahligen Einschränkungen vorübergehend gelockert, das Problem optimal gelöst und die reale Lösung in eine ganzzahlige Lösung konvertiert werden. Zusätzliche Einschränkungen können hinzugefügt und der Prozess unter Verwendung eines Verzweigungs- und gebundenen Ansatzes unbegrenzt wiederholt werden.

Im ^[10] Die Autoren berichten über den Algorithmus, mit dem ein eingeschränktes RWA-Problem effizient und optimal gelöst werden kann. Die Autoren untersuchen ein RSA-Problem (Constrained Routing and Spectrum Assignment), das durch Anfordern eines Slice auf ein eingeschränktes RWA-Problem reduziert werden kann. Die Verengung begrenzt die Weglänge.

Im ^[11] Die Autoren berichten über den verallgemeinerten Dijkstra-Algorithmus, mit dem die Probleme mit RWA, RSA und Routing, Modulation und Spektrumzuweisung (RMSA) effizient und optimal gelöst werden können, ohne die Pfadlänge zu begrenzen.

Verweise[edit]

^ H. Zang, J. Jue und B. Mukherjee, “Eine Überprüfung der Routing- und Wellenlängenzuweisungsansätze für optische WDM-Netzwerke mit Wellenlängenrouting,” { it Optical Networks Magazine}, Januar 2000.
^ I. Chlamtac, A. Ganz und G. Karmi, “Lichtwegkommunikation: Ein Ansatz für optische WANs mit hoher Bandbreite,” { it IEEE Transactions on Communications}, Band 40, Nr. 7, S. 1171–1182, Juli 1992.
^ S. Evan, A. Itai und A. Shamir, “Zur Komplexität von Zeitplan- und Multicommodity-Flow-Problemen,” SIAM Journal on Computing, Bd. 5, S. 691-703, 1976
^ M. Pascoal und E. Martins. “Eine neue Implementierung des Algorithmus für rundenlose Pfadpfade von Yen.” 4OR – Quarterly Journal der belgischen, französischen und italienischen Operations Research Societies, 2003
^ ^ein ^b W. Lin, “Physisch bewusste agile optische Netzwerke,” Ph.D. Dissertation, Montana State University, Bozeman, Juli 2008.
^ Y. Huang, J. Heritage und B. Mukherjee, “Verbindungsbereitstellung mit Berücksichtigung von Übertragungsstörungen in optischen WDM-Netzwerken mit Hochgeschwindigkeitskanälen,” Journal of Lightwave Technology, Band 23, Nr. 3, März 2005.
^ T. Deng und S. Subramaniam, “Adaptives QoS-Routing in dynamischen optischen Netzwerken mit Wellenlängenrouting,” Broadband Networks 2005, S. 184-193, 2005
^ R. Barry und S. Subramaniam, “Der MAX-SUM-Wellenlängenzuweisungsalgorithmus für WDM-Ringnetzwerke,” Proceedings of Optical Fibre Conference, Februar 1997.
^ X. Zhang und C. Qiao, “Wellenlängenzuweisung für dynamischen Verkehr in Multi-Fibre-WDM-Netzwerken,” Proceedings of International Conference on Communications, Band 1, S. 406-410, Juni 1997.
^ Ireneusz Szcześniak und Bożena Woźna-Szcześniak, “Angepasste und eingeschränkte Dijkstra für elastische optische Netzwerke“, Tagungsband der 20. Konferenz für Design und Modellierung optischer Netzwerke, Cartagena, Spanien, Mai 2016
^ Ireneusz Szcześniak, Andrzej Jajszczyk und Bożena Woźna-Szcześniak, “Generische Dijkstra für optische Netzwerke“, Oktober 2018

after-content-x4