DE602004005405T2

DE602004005405T2 - Verfahren zur Verkehrsplanung eines Virtual Private LAN Dienstes (VPLS)

Info

Publication number: DE602004005405T2
Application number: DE602004005405T
Authority: DE
Inventors: Kamakshi Sridhar; Maher Ali
Original assignee: Alcatel Lucent SAS
Current assignee: Alcatel Lucent SAS
Priority date: 2003-12-05
Filing date: 2004-11-17
Publication date: 2007-11-29
Anticipated expiration: 2024-11-18
Also published as: ATE357796T1; US20050132088A1; US7484010B2; DE602004005405D1; EP1538789B1; EP1538789A1

Description

Hintergrund der Erfindung
Die vorliegende Erfindung bezieht sich auf Computernetze, und insbesondere auf ein Verfahren zur Verkehrsplanung in einem Virtual Private LAN-Dienst eines Metro Ethernet-Netzes. Insbesondere bezieht sich die vorliegende Erfindung auf ein Computerprogramm gemäß Anspruch 1.
Ethernet-Netze sind in zahlreichen Anwendungen in der Netzwerkbranche aus verschiedenen Gründen beliebt. Beispielsweise ist das Ethernet ein weit verbreitetes und kostengünstiges Medium mit zahlreichen Schnittstellen, das Verbindungen und verschiedene Geschwindigkeiten bis in den Gbps-Bereich hinein bieten kann. Ethernet-Netze können zur Einrichtung eines Metro Ethernet-Netzes („MEN") eingesetzt werden, bei dem es sich im Allgemeinen um ein öffentlich zugängliches Netz handelt, das einen Großstadtbereich umfasst, typischerweise unter der Kontrolle eines einzelnen Administrators, wie beispielsweise einem Internet Service Provider („ISP"). Ein MEN wird typischerweise eingesetzt, um die Verbindung zwischen einem Teilnehmernetz und einem Kernnetz zu gewährleisten. Das Teilnehmernetz umfasst typischerweise private oder Endnutzer, die die Connectivity zum Netz herstellen. Das Kernnetz wird eingesetzt, um die Verbindung zu anderen Metro Ethernet-Netzen herzustellen, und das Kernnetz übernimmt in erster Linie eine Paketvermittlungsfunktion.
Ein MEN besteht typischerweise aus einer Reihe von Provider Edge („PE")-Knoten, die vor einer Verbindung für den Paketverkehr für die Kommunikation untereinander identifiziert und konfiguriert werden. Die PE-Knoten sind im Punkt-zu-Punkt-Verfahren miteinander verbunden, jeder PE-Knoten ist über einen emulierten und bidirektionalen virtuellen Knoten mit einem anderen PE-Knoten verbunden, wobei jede dieser Verbindungen über einen Label Switched Path („LSP") hergestellt wird. Ein LSP wird manchmal informell auch als Link bezeichnet. Somit kann jeder PE-Knoten mit einem benachbarten PE-Knoten kommunizieren und Pakete von diesem empfangen. Des Weiteren sind in jedem LSP, zwischen benachbarten PE-Knoten, häufig eine Reihe von Provider-Knoten („P") angeordnet. Die P-Knoten pflegen keine Statusinformationen und übernehmen hauptsächlich Routingfunktionen, sie sind daher so konzipiert, dass sie die Punkt-zu-Punkt-Verbindung zwischen den PE-Knoten des MEN nicht stören, bei denen es sich um intelligentere Geräte handelt. Eine unterschiedliche Anzahl an P-Knoten kann in einer Verbindungsrichtung zwischen zwei benachbarten PE-Knoten angeschlossen sein, im Vergleich zur umgekehrten Verbindungsrichtung zwischen diesen zwei benachbarten PE-Knoten.
PE-Knoten im MEN sind ebenfalls mit einem oder mehreren Customer Edge („CE")-Knoten verbunden, wobei diese Knoten damit die Schnittstelle zwischen dem MEN und einem benachbarten Teilnehmernetz darstellen. Häufig erfolgt die Verbindung zwischen einem PE-Knoten und einem CE-Knoten beim gegenwärtigen Stand der Technik über einen Zwischenknoten zwischen dem PE-Knoten und dem CE-Knoten, wobei dieser Zwischenknoten als Layer 2 Provider Edge („L2PE")-Knoten bezeichnet wird. Die Connectivity zwischen einem L2PE-Knoten und zusätzlichen PE-Knoten im MEN wird normalerweise als Homing bezeichnet. Genauer gesagt wird die Verbindung als Singlehome-Verbindung bezeichnet, wenn der L2PE-Knoten mit einem einzelnen PE-Knoten verbunden ist, ist der L2PE-Knoten dagegen mit mehr als einem PE-Knoten verbunden, wird die Verbindung als Multihome-Verbindung bezeichnet. Während L2PE-Knoten multihomed (d.h. mit mehr als einem anderen PE-Knoten verbunden) sein können, ist dies bei den CE-Knoten eines benachbarten Teilnehmernetzes nicht möglich, d.h. jeder CE-Knoten kann nur mit einem einzigen L2PE-Knoten verbunden sein.
Bei der Ausarbeitung der MEN-Architektur wurden außerdem zusätzliche Topologien in Verbindung mit einem solchen Netz entwickelt. Ein Beispiel, das sich auf die im Folgenden beschriebenen, bevorzugten Ausführungsvarianten bezieht, ist der Virtual Private LAN-Dienst („VPLS"). Ein VPLS bildet ein emuliertes Local Area Network („LAN")-Segment für eine gegebene Anzahl an Knoten in einem MEN. Das VPLS bietet eine ISO Layer 2-Broadcast Domain, die vollständig in der Lage ist, Ethernet MAC-Adressen zu erfassen und weiterzuleiten, die einer bestimmten Anzahl an Knoten vorbehalten sind. Mit dem VPLS können daher Pakete an alle Knoten im VPLS gesendet werden. VPLS kann auch in den oben beschriebenen Rahmen integriert werden, der PE- und L2PE-Knoten umfasst und verschiedenen Beschränkungen unterliegt. Erstens kann mehr als ein VPLS in ein einzelnes MEN integriert werden, und daher können bestimmte PE-Knoten dieses MEN Bestandteil von mehr als einem VPLS sein. Zweitens kann ein L2PE-Knoten in einem MEN mit mehreren VPLS mehr als ein VPLS unterstützen, wobei jedes dieser VPLS ein eigenes Homing aufweist, d.h. für jeden VPLS weist dieser L2PE eine Verbindung zu einem (und nur einem) PE-Knoten in dem MEN auf.
Aufgrund der verschiedenen, oben beschriebenen und dem Fachmann bekannten Knoten, Attribute sowie der Connectivity entstehen komplexe Vorgaben für die Verkehrsplanung mit diesen Parametern, d.h. bei der Herstellung von Netzwerkverbindungen, der entsprechenden Anzahl von VPLSs, der Connectivity und dem effizienten Einsatz der Bandbreite. Diese komplexen Vorgaben entstehen sowohl bei der ersten Einrichtung dieser Parameter für ein neues Netz, als auch bei der Änderung dieses Netzes, wenn sich ein oder mehrere Faktoren im Lauf der Zeit ändern, z.B. wenn ein neuer VPLS hinzugefügt wird. Diese komplexen Vorgaben werden durch den Wunsch weiter verschärft, einen 1 + 1-Schutz in dem Netz zu gewährleisten, wobei ein erster Parameter-Satz vorgegeben wird, manchmal auch als primäres Netz bezeichnet, der jedoch durch einen zweiten Parameter-Satz ergänzt wird, manchmal auch als sekundäres oder Backup-Netz bezeichnet, das eingesetzt wird, falls das erste Netz ausfällt.
Angesichts der oben stehenden Erläuterungen bieten die bevorzugten Ausführungsvarianten ein Gerät (z.B. einen Netzknoten) mit ausreichender Verarbeitungskapazität, das entsprechend programmiert ist, um die Verkehrsplanung eines VPLS-Netzes mit Multi-Homing, Unicast- und Multicast-Verkehr und mit 1 + 1-Schutz zu gewährleisten, wie im Folgenden erläutert wird.
Der gegenwärtige Stand der Technik wird in den Patenten US-B-6 584 071 1 und WO 03/079614 A beschrieben.
KURZE ZUSAMMENFASSUNG DER ERFINDUNG
Die oben genannten Probleme werden durch das Computerprogramm gemäß Anspruch 1 gelöst.
In der bevorzugten Ausführungsvariante ist eine Verarbeitungsvorrichtung entsprechend programmiert, um Homing-Pfade für eine Vielzahl von Virtual Private LAN-Diensten in einem Ethernet-Netz, das aus einer Vielzahl von PE-Knoten besteht, festzulegen. Die Verarbeitungsvorrichtung ist entsprechend programmiert, um die Schritte zur Berechnung einer Vielzahl von Sätzen mit unterschiedlichen Homing-Konfigurationen, zur Berechnung einer Kostenfunktion für jeden Satz mit unterschiedlichen Homing-Konfigurationen aus der Vielzahl von Sätzen mit unterschiedlichen Homing-Konfigurationen und zur Auswahl eines Satzes einer Homing-Konfiguration aus der Vielzahl von Sätzen mit unterschiedlichen Homing-Konfigurationen als Antwort auf eine entsprechende Kostenberechnungsfunktion auszuführen. Jede Homing-Konfiguration in jedem Satz mit unterschiedlichen Homing-Konfigurationen wird durch eine entsprechende Iteration aus Schritten berechnet, wobei jeder Schritt jeweils einem Virtual Private LAN-Dienst aus der Vielzahl von Virtual Private LAN-Diensten sowie jeweils einem ausgewählten Layer 2 Provider Edge-Knoten im Ethernet-Netz entspricht. Jede Iteration umfasst die Schritte zur Auswahl eines PE-Eingangsknotens und eines PE-Ausgangsknotens, zur Festlegung der Bandbreite in den PE-Eingangsknoten, zur Festlegung der Bandbreite aus dem PE-Ausgangsknoten und zur Spezifikation eines ersten Pfades zur Datenübertragung von dem PE-Ausgangsknoten an den PE-Eingangsknoten und eines zweiten Pfades zur Datenübertragung von dem PE-Eingangsknoten zum PE-Ausgangsknoten, wobei jeder Pfad unter dem ersten und dem zweiten Pfad mindestens einen P-Knoten umfasst.
Weitere Aspekte werden ebenfalls beschrieben und in den Ansprüchen formuliert.
KURZE BESCHREIBUNG DER VERSCHIEDENEN ZEICHNUNGEN
1 stellt ein Netzsystem gemäß der bevorzugten Ausführungsvariante und mit der entsprechenden Connectivity dar, das von einem zentralen Manager im Netzsystem ebenfalls gemäß der bevorzugten Ausführungsvariante konfiguriert werden kann.
2 stellt ein Ablaufdiagramm des Verfahrens des zentralen Managers gemäß der bevorzugten Ausführungsvariante zur Festlegung der VPLS-Connectivity im Netz dar.
DETAILLIERTE BESCHREIBUNG DER ERFINDUNG
Anhand der Darstellung einer bevorzugten Ausführungsvariante der Erfindung stellt 1 ein Netzsystem dar, das allgemein mit der Referenz 10 bezeichnet wird. Das Netzsystem 10 umfasst in den bevorzugten Ausführungsvarianten ein Metro Ethernet-Netz („MEN"), das einen Virtual Private LAN-Dienst („VPLS") umfasst. Wie in 1 dargestellt, zeigt das System 10 ein solches Netz mit verschiedenen Aspekten, die dem Fachmann allgemein bekannt sind, wobei die Abbildung aufgenommen wurde, um verschiedene Konzepte und Konventionen vorzustellen, und weil sie gemäß den bevorzugten Ausführungsvarianten erstellt und geändert wurde, wie dies im Folgenden noch näher erläutert wird.
Als Beispiel umfasst das MEN des Systems 10 fünf Provider Edge („PE")-Knoten PE₁, PE₂, PE₃, PE₄ und PE₅, wobei die Anzahl fünf nur als Beispiel dient und es für den Fachmann sicherlich offensichtlich ist, dass eine beliebige Anzahl dieser Knoten vorhanden sein kann. Es ist tatsächlich darauf hinzuweisen, dass ein MEN häufig wesentlich mehr als fünf PE-Knoten umfasst. Jeder PE-Knoten kann von einem Fachmann als Verarbeitungsvorrichtung konzipiert sein, unter Verwendung unterschiedlicher Hardware, Software und Programmierungen, um die in dem vorliegenden Dokument beschriebenen und dem Fachmann bekannten Funktionen auszuführen. Außerdem versteht es sich von selbst, dass in einem MEN-System, wie dies zwar hier nicht dargestellt ist, jedoch weiter oben im Abschnitt „Hintergrund der Erfindung" in diesem Dokument erläutert wurde, zwischen benachbarten PE-Knoten eine Reihe von Provider („P")-Knoten angeordnet sein kann. Im MEN des Systems 10 ist das Netz vorzugsweise vollständig vermascht, d.h. dass jeder PE-Knoten PE_x mit jedem anderen PE-Knoten im System verbunden ist, wobei jede Verbindung über den jeweiligen Label Switched Path („LSP") erfolgt und in 1 mit einem Pfeil gekennzeichnet ist. Aus Gründen der Referenz in dem vorliegenden Dokument erfolgt die bidirektionale Verbindung zwischen zwei Knoten außerdem über zwei LSPs mit umgekehrter Bewegungsrichtung, d.h. über ein LSP-Paar („LSPP"), das einen LSP für Datenübertragungen in einer Richtung von einem ersten PE-Knoten an einen zweiten Knoten sowie einen anderen LSP für Datenübertragungen in umgekehrter Richtung umfasst, d.h. von dem zweiten PE-Knoten an den ersten PE-Knoten. Beispielsweise ist der PE-Knoten PE₁ über die vier jeweiligen LSPPs mit jedem der PE-Knoten PE₂, PE₃, PE₄ und PE₅ verbunden. Entsprechend der Konvention kennzeichnet das für jedes LSPP in 1 verwendete Label die beiden PE-Knoten, zwischen denen das LSPP angeschlossen ist. Zwischen den PE-Knoten PE₁ und PE₂ ist beispielsweise das LSPP_1A2 angeordnet; als weiteres Beispiel ist zwischen den PE-Knoten PE₃ und PE₄ das LSPP_3A4 angeordnet. Um 1 zu vereinfachen, sind nur ein paar dieser LSPPs auf diese Weise gekennzeichnet. Aufgrund der Connectivity des Systems 10 kann jeder PE-Knoten als Quelle Daten direkt über einen LSP an jeden anderen PE-Knoten als Ziel übertragen, wobei dieser PE-Zielknoten Daten über einen anderen LSP (allerdings über einen anderen Satz P-Knoten) in umgekehrter Richtung zurück an den PE-Quellknoten übertragen kann. Eine einzelne Datenübertragung zwischen zwei PE-Knoten in einer Richtung und auf diese Weise wird in der Fachwelt als Unicast-Übertragung bezeichnet und somit definieren die verschiedenen LSPPs des Systems 10 in 1 die Punkt-zu-Punkt-Schnittstellen, über die der Unicast-Verkehr übertragen werden kann. Versucht dagegen ein einzelner PE-Knoten, ein Datenpaket an mehr als einen PE-Zielknoten zu übertragen, wird eine solche Datenübertragung in der Fachwelt als Multicast-Übertragung bezeichnet.
Wiederum in Bezug auf das MEN aus dem System 10 in 1, umfasst dies auch eine Reihe von Layer 2 PE-Knoten („L2PE-Knoten") L2PE₁, L2PE₂, L2PE₃, L2PE₄ und L2PE₅, wobei die Zahl fünf nur als Beispiel dient und es für den Fachmann sicherlich offensichtlich ist, dass eine beliebige Anzahl solcher Knoten integriert werden kann. Jeder L2PE ist außerdem mit mindestens einem PE-Knoten im MEN verbunden. Genauer gesagt unterstützt jeder L2PE eine oder mehrere logische Einheiten, die einem oder mehreren VPLSs entsprechen, und jede dieser logischen VPLS-Einheiten verfügt über eine einzelne LSPP-Verbindung mit nur einem PE-Knoten im MEN; um die Darstellung zu vereinfachen, ist jede einzelne LSPP-Verbindung mit einer gestrichelten Linie dargestellt, obwohl es sich von selbst versteht, dass zwei LSPs auf die gleiche Weise wie die anderen PE-Knoten-zu-PE-Knoten-Verbindungen in 1 vorliegen müssen. Als Beispiel in Bezug auf den L2PE-Knoten L2PE₁ weist dieser eine logische VPLS-Einheit VPLS₁ auf, die mit dem PE-Knoten PE₂ verbunden ist, eine logische VPLS-Einheit VPLS₂, die mit dem PE-Knoten PE₁ verbunden ist, und eine logische VPLS-Einheit VPLS₃, die mit dem PE-Knoten PE₅ verbunden ist. Jede logische VPLS-Einheit ist Bestandteil eines allgemeinen VPLS; beispielsweise ist die logische VPLS-Einheit VPLS₁ im L2PE₁ Bestandteil von VPLS₁, der ebenfalls von L2PE₃ und L2PE₄ unterstützt wird. Zudem ist darauf hinzuweisen, dass es sich bei dem L2PE-Knoten L2PE₁ um einen Multihome-Knoten handelt, d.h. er ist mit mehr als einem PE-Knoten verbunden; im Gegensatz dazu ist der L2PE-Knoten L2PE₅ ein Singlehome-Knoten, da er nur eine einzige logische VPLS-Einheit (d.h. VPLS₃) unterstützt und nur mit einem einzigen PE-Knoten PE₁ verbunden ist.
Ungeachtet des Singlehoming des L2PE-Knotens L2PE₅ wird das Netzsystem 10 als Multihome-System betrachtet, da es ein oder mehrere andere L2PE-Multihome-Knoten umfasst. Per Definition bietet ein L2PE-Knoten außerdem eine Schnittstelle zwischen dem MEN und einem Teilnehmernetz, das Kundenknoten umfasst, wobei jeder L2PE-Knoten an dieser Schnittstelle mit einer oder mehreren Customer Edge („CE")-Knoten verbunden ist; typischerweise ist ein einzelner L2PE-Knoten nämlich für jede logische VPLS-Einheit in diesem L2PE-Knoten mit einem CE-Knoten verbunden, d.h. jeder CE-Knoten ist einer entsprechenden logischen VPLS-Einheit im L2PE-Knoten zugeordnet. Um diese Aspekte darzustellen und als Beispiel in Bezug auf den L2PE-Knoten L2PE₁ ist dieser mit drei CE-Knoten CE_1.1, CE_1.2 und CE_1.3 verbunden, die seinen drei logischen VPLS-Einheiten VPLS₁, VPLS₂ und VPLS₃ entsprechen. Eine ähnliche Connectivity ist für alle anderen L2PE-Knoten L2PE_x im System 10 dargestellt, die jeweils mit mehreren CE-Knoten verbunden sind; wenn zum Beispiel jeder L2PE-Knoten über V logische VPLS-Einheiten verfügt, so ist der L2PE-Knoten mit V CE-Knoten verbunden.
In Anbetracht der Connectivity in 1 ist es für den Fachmann ersichtlich, dass in dem Beispiel drei verschiedene VPLSs beschrieben werden, wobei das Homing zwischen jedem L2PE und seinen entsprechenden PE-Knoten in der folgenden Tabelle 1 zusammengefasst wird:
Tabelle 1
Aus Tabelle 1 und 1 ist ersichtlich, dass unterschiedliche logische VPLS-Einheiten im gleichen L2PE-Knoten mit dem gleichen PE-Knoten verbunden sein können, wie dies als Beispiel für den L2PE-Knoten L2PE₄ dargestellt ist, der sowohl die logische VPLS-Einheit VPLS₂ als auch die logische VPLS-Einheit VPLS₃ unterstützt, die beide mit dem gleichen PE-Knoten PE₄ verbunden sind. Außerdem kann eine Reihe von PE-Knoten, die jeweils mit einer VPLS verbunden sind, gemäß der folgenden Tabelle 2 zusammengefasst werden:
Tabelle 2
In Tabelle 2 sind also die PE-Knoten aufgeführt, die zum jeweiligen VPLS gehören; beispielsweise gehören nur die PE-Knoten PE₂, PE₃ und PE₅ zu VPLS₁ usw. für die anderen beiden VPLSs mit ihren entsprechenden PE-Knoten. Somit sind für den Fachmann aufgrund der Darstellung in 1 sowie aufgrund von Tabelle 1 und 2 sicherlich die drei verschiedenen VPLSs und die PE-Knoten, die über einen solchen VPLS miteinander verbunden sind, ersichtlich.
Aufgrund der Beschreibung von 1 ist es außerdem offensichtlich, dass nur eine erste Einheit an Verbindungen für ein erstes oder primäres Netz dargestellt wird. Mit anderen Worten ist für jede logische VPLS-Einheit, die von dem jeweiligen L2PE-Knoten unterstützt wird, für diese logische VPLS-Einheit nur die Verbindung mit einem einzigen PE-Knoten dargestellt; es versteht sich jedoch von selbst, dass 1 mit einer anderen Connectivity gezeichnet werden kann, um ein zweites oder Backup-Netz darzustellen, wobei jede logische VPLS-Einheit, die von dem entsprechenden L2PE unterstützt wird, im Vergleich zur Darstellung in 1 mit einem anderen PE-Knoten verbunden ist. Bei der Kombination von primärem und Backup-Netz ist es für den Fachmann sicher offensichtlich, dass dadurch ein so genannter 1 + 1-Schutz geboten werden soll, so dass, wenn in einem Netz (z.B. im „primären" Netz) ein Verbindungsausfall auftritt, der Verkehr alternativ über das zweite oder Backup-Netz hergestellt werden kann. Schließlich ist noch darauf hinzuweisen, dass der PE-Knoten PE₁ in der Darstellung aus 1 einen Block umfasst, der einen zentralen Manager CM darstellt. In der bevorzugten Ausführungsvariante soll der zentrale Manager CM eine allgemeine Verarbeitungsfunktion darstellen, die die Verkehrsplanung in dem Multihome-Netzsystem 10 durchführt. Diese Funktion kann in einen der PE-Knoten integriert werden, wie in 1 dargestellt, alternativ dazu kann der zentrale Manager auch in einem separaten Knoten oder einer Berechnungsvorrichtung angeordnet werden, der/die kein PE-Knoten im Netz ist. In jedem Fall stellt der zentrale Manager CM eine Verarbeitungsvorrichtung mit ausreichenden Kenntnissen des Netzstatus dar, mit dem sie verbunden ist, um die übrigen, im vorliegenden Dokument beschriebenen Funktionen zu gewährleisten. Die tatsächlich eingesetzte Hardware, Software und Programmierung zur Umsetzung einer solchen Vorrichtung sind aufgrund der Funktionsbeschreibung in diesem Dokument für den Fachmann sicherlich offensichtlich.
2 stellt ein Ablaufdiagramm eines Verfahrens 20 mit Schritten dar, die von dem zentralen Manager CM aus 1 ausgeführt werden, um die oben genannte Verkehrsplanung umzusetzen, d.h. der zentrale Manager CM ist entsprechend programmiert, um diese Schritte mit den im Folgenden beschriebenen Ergebnissen durchzuführen. Als zusätzliche Hintergrundinformationen zum Verfahren 20 ist allgemein darauf hinzuweisen, dass das Verfahren 20 auf iterative Weise arbeitet, um eine Kostenfunktion zu optimieren, die nach ihrer Optimierung neben den LSPs primäre und Backup-Homes im Netzsystem 10 bietet. Im Allgemeinen ist die bevorzugte Ausführung von Homes für die verschiedenen VPLSs und die Konzeption des primären und des Backup-Pfads dergestalt, dass der Verkehr über die verschiedenen PE- und P-Knoten und Links im Netz optimiert und der 1 + 1-Schutz im Fall eines Knoten- oder Linkausfalls gewährleistet ist. Zudem werden hauptsächlich der Unicast- und Multicast-Verkehr betrachtet. Auch kann die bevorzugte Ausführungsvariante im Hinblick auf einen entkoppelten VPLS oder einen hierarchischen VPLS umgesetzt werden. In einem entkoppelten VPLS wird Multihoming unterstützt, mit einem Home für jeden VPLS innerhalb eines L2PE-Knotens L2PE_x, wie in 1 dargestellt. In einem hierarchischen VPLS wird nur ein duales Homing unterstützt, wobei es sich bei einem Home um das primäre Home und bei dem anderen Home um das Backup-Home handelt. Auf jeden Fall geht man aus Gründen der Vereinfachung in der folgenden Besprechung von einem entkoppelten VPLS aus, wie in 1 dargestellt, wobei für den Fachmann die vergleichbaren Aspekte bei der Anwendung auf einen hierarchischen VPLS sicherlich offensichtlich sind. Außerdem wird der Leser für weitere Details in Bezug auf den entkoppelten VPLS auf K. Kompella et al., Decoupled Virtual Private LAN Services, IETF Draft, „draftkompella-ppvpn-dtls-02.txt" verwiesen. Gleichermaßen findet der Leser weitere Einzelheiten zu einem hierarchischen VPLS in M. Lasserre, V. Kompella et al., Virtual Private LAN Services over MPLS, IETF Draft, „draft-lasserre-vkompella-ppvpn-vpls-03.txt".
Im Folgenden wird das Verfahren 20, das mit dem Schritt 30 beginnt, im Detail beschrieben. In Schritt 30 erfährt der zentrale Manager CM die physische Topologie des Netzsystems 10 sowie die verfügbare Bandbreite des Systems 10. Dieser Schritt 30 dient daher der Darstellung, dass dem zentralen Manager CM unterschiedliche Informationen über Topologie und Bandbreite zur Verfügung gestellt werden. Die Art und Weise der Übermittlung dieser Informationen an den zentralen Manager CM kann in mancher Hinsicht automatisiert werden, beispielsweise dadurch, dass die verschiedenen Knoten in dem System 10 Signalisierungen an den zentralen Manager CM vornehmen, um die Topologie-Informationen zu übermitteln. Alternativ dazu können einige oder sämtliche Informationen manuell an den zentralen Manager übertragen werden. Wird das Verfahren 20 durchgeführt, um die Verkehrsplanung in einem bereits konfigurierten Netz zu aktualisieren, können bestimmte Topologie-Informationen zudem auf elektronischem Wege von einem oder mehreren Knoten im Netzsystem 10 übermittelt werden. Auf jeden Fall umfassen die Topologie-Informationen in der bevorzugten Ausführungsvariante die gesamte Anzahl aller P-Knoten, aller PE-Knoten und aller L2PE-Knoten im MEN; in dem Beispiel aus 1 umfassen die Topologie-Informationen die PE-Knoten PE₁ bis PE₅, die P-Knoten (nicht abgebildet, jedoch oben beschrieben) und die L2PE-Knoten L2PE₁ bis L2PE₅. Zusätzlich umfassen die Topologie-Informationen vorzugsweise alle physischen Links, wobei es sich bei einem Link, auch als Verbindungseinrichtung bezeichnet, um die Verbindungseinrichtung e = (a, b) handelt, wobei a oder b zu allen Knoten gehören, und es sich bei der Verbindungseinrichtung daher um eine Verbindung zwischen zwei solcher Knoten handelt. Zusätzlich wird der zentrale Manager CM über die Netz-Bandbreite entsprechend der physischen Topologie informiert. Genauer gesagt umfasst die Bandbreite die Bandbreitenkapazität zwischen jedem benachbarten P-Knoten P₁ und P_j innerhalb des MEN. Zusätzlich umfasst die Bandbreite die Bandbreitenkapazität zwischen jedem L2PE-Knoten L2PE_i und jedem PE-Knoten PE_j. Schließlich umfasst die Bandbreite den erwarteten Verkehr zwischen verschiedenen CEs für verschiedene VPLSs, d.h. für alle CEs, die zu einem VPLS gehören, wobei der Verkehr, der von dem CE-Knoten CE_i zu CE_j übertragen wird, gegeben ist. Es ist darauf hinzuweisen, dass dieser erwartete Verkehr in der bevorzugten Ausführungsvariante in Form einer zweidimensionalen Matrix dargestellt werden kann, die Bandbreiten-Prognosen für den Unicast- und Multicast-Verkehr umfasst; eine solche Matrix für den Unicast- und Multicast-Verkehr kann beispielsweise die Informationen enthalten, die in der folgenden Tabelle 3 aufgeführt sind.
Tabelle 3
In Tabelle 3 sollen die Begriffe Eingang und Ausgang die Datenverkehrsrichtung für einen gegebenen CE-Knoten bezeichnen, der den Datenverkehr in Bezug auf das MEN überträgt. Der CE-Eingangsknoten CE_n ist daher ein Knoten, der Datenverkehr empfängt, der in das MEN gelangt, und der CE-Ausgangsknoten CE_n ist der Knoten, der den Datenverkehr empfängt, der das MEN verlässt. Wiederum in Schritt 30 und in Bezug auf die Bandbreiteninformation im Hinblick auf einen CE-Knoten und seinen entsprechenden VPLS, wird der zentrale Manager CM über die gewünschten VPLSs für jeden L2PE-Knoten informiert; wie im Folgenden noch erläutert wird, wird das gewünschte Ergebnis jedoch nicht zwangsläufig in einer optimalen Connectivity-Konfiguration erreicht, diese Information steht jedoch zur Verfügung und bietet tatsächlich teilweise eine Basis, von der ausgehend die bevorzugte Ausführungsvariante die Connectivity innerhalb des Netzsystems 10 festlegt. Auf jeden Fall geht das Verfahren 20 von Schritt 30 zu Schritt 32 über, sobald dem zentralen Manager CM in Schritt 30 die physische Topologie, die Bandbreite und die VPLS-Informationen zur Verfügung gestellt werden.
Beginnend mit Schritt 32 führt der zentrale Manager CM verschiedene Operationen in Bezug auf einen gegebenen VPLS-Knoten des Netzsystems 10 aus, wobei die ersten Operationen in einer beispielhaften Ausführungsvariante für einen ersten VPLS in einem ersten L2PE-Knoten durchgeführt werden, gefolgt von Operationen für den ersten VPLS in einem zweiten L2PE-Knoten und so weiter, bis alle L2PE-Knoten berücksichtigt wurden. Anschließend werden die Schritte für einen zweiten VPLS im ersten L2PE-Knoten wiederholt, gefolgt von Operationen für den zweiten VPLS im zweiten L2PE-Knoten und so weiter, bis schließlich die verschiedenen Connectivity-Konfigurationen für alle gewünschten VPLSs sämtlicher L2PE-Knoten des MEN geprüft wurden, wie dies aus der folgenden Beschreibung ersichtlich wird.
Im Folgenden wird Schritt 32 detaillierter erläutert, in dem der zentrale Manager CM das durchführt, was als die drei allgemeinen Operationen in Bezug auf einen gegebenen VPSL betrachtet werden kann. Betrachtet man nur einen ersten L2PE-Knoten (z.B. den L2PE-Knoten L2PE₁ in 1), besteht die erste der drei Operationen aus Schritt 32 in der Auswahl eines primären Eingangsknotens, im Folgenden als PE-Knoten PE_pi bezeichnet, und eines primären PE-Ausgangsknotens, im Folgenden als PE-Knoten PE_pe bezeichnet, wobei in beiden Fällen die Bezeichnung „primär" für diese PE-Knoten darauf hinweisen soll, dass diese als primärer Anteil der 1 + 1-Konfiguration zu berücksichtigen sind, im Gegensatz zum Backup-(oder sekundären) Anteil der gleichen Konfiguration. Daher können in dieser ersten Operation in dem Beispiel aus 1 der PE-Knoten PE₂ als PE-Knoten PE_pi und der PE-Knoten PE₅ als PE-Knoten PE_pe gewählt werden. In einer zweiten Operation legt der zentrale Manager CM die Bandbreite fest, die dem primären Eingangsknoten PE_pi zur Verfügung gestellt werden soll; in der bevorzugten Ausführungsvariante kann diese Festlegung unter Bezug auf die zweidimensionale Bandbreitentabelle aus Schritt 30 erfolgen, wie in Tabelle 3 beispielhaft dargestellt, da diese Tabelle die Bandbreite von CE-Knoten zu CE-Knoten vorgibt, und diese Connectivity erfolgt anhand der PE-Knoten im System 10. In einer dritten Operation legt der zentrale Manager CM die Bandbreite fest, die ausgangs des primären Ausgangsknotens PE_pe zur Verfügung gestellt werden soll; in der bevorzugten Ausführungsvariante kann diese Festlegung ebenfalls unter Bezug auf die zweidimensionale Bandbreitentabelle aus Schritt 30 erfolgen, wie anhand eines Beispiels in Tabelle 3 dargestellt. Anschließend geht das Verfahren von Schritt 32 zu Schritt 34 über.
In Schritt 34 geht der zentrale Manager CM auf vergleichbare Weise wie in Schritt 32 vor, allerdings mit dem Unterschied, dass die PE-Knoten ausgangs von Schritt 34 für die Backup-(oder sekundäre) Connectivity in der 1 + 1-Schutzkonfiguration vorgesehen sind. Daher besteht Schritt 34 ebenfalls aus dem, was als drei Operationen betrachtet werden kann. Zunächst wählt der zentrale Manager CM einen sekundären Eingangsknoten, im Folgenden als PE-Knoten PE_si bezeichnet, und einen sekundären PE-Ausgangsknoten aus, im Folgenden als PE-Knoten PE_se bezeichnet, wobei die Bezeichnung „sekundär" in beiden Fällen darauf hinweisen soll, dass diese als sekundärer Anteil der 1 + 1-Konfiguration zu betrachten sind. In einer zweiten Operation legt der zentrale Manager CM die Bandbreite fest, die dem sekundären Eingangsknoten PE_si zur Verfügung gestellt werden soll, und in einer dritten Operation legt der zentrale Manager CM die Bandbreite fest, die ausgangs des sekundären Ausgangsknotens PE_se zur Verfügung gestellt werden soll. Es sei nochmals daran erinnert, dass in oben genanntem Schritt 32 die Bandbreite in und aus den PE-Knoten PE_pi bzw. PE_pe festgelegt wurde; in Schritt 34 werden die gleichen Bandbreiten-Werte für die PE-Knoten PE_si bzw. PE_se verwendet, damit die gleiche Bandbreite für die primären und sekundären Strecken zur Verfügung gestellt wird. Anschließend geht das Verfahren von Schritt 34 zu Schritt 36 über.
In Schritt 36 erstellt der zentrale Manager CM LSPPs zwischen den PE-Knoten PE_pi und PE_pe, d.h. für die primäre Strecke. In der bevorzugten Ausführungsvariante erfolgt die Auswahl der LSPPs durch Auswahl der P-Knoten, die diese LSPPs bilden sollen, und wie später erläutert wird, unterliegt diese Auswahl ebenfalls verschiedenen Beschränkungen. Des Weiteren basieren die Kriterien für die Auswahl in Schritt 36 vorzugsweise entweder auf der Verteilung der Auslastung auf alle P-Knoten im LSPP oder alternativ dazu auf der geringsten Anzahl von P-Knoten im LSPP. Im Fall einer Verteilung der Auslastung kann es für einen LSP akzeptabel sein, zahlreiche P-Knoten-Hops zu durchlaufen, solange ein bestimmter P-Hop im Vergleich zu anderen P-Knoten-Hops nicht deutlich mehr ausgelastet ist; daher kann ein bestimmter Prozentanteil oder ein Toleranzgrenzwert vorgegeben werden, wobei die jeweilige Hop-Auslastung innerhalb eines bestimmten Prozentbereichs der Gesamtauslastung aller anderen Hops in dem LSP liegt. Für den Fall einer Minimierung der Anzahl an P-Knoten im LSPP wird die bevorzugte Methode im Folgenden erläutert. Bei einer gegebenen Anzahl von P-Knoten und den PE-Knoten PE_pi und PE_pe wird die Verbindungseinrichtung zwischen den P-Knoten mit einem Wert von eins gekennzeichnet, wenn Bandbreite zur Verfügung steht, oder mit dem Wert unendlich, wenn keine Bandbreite zur Verfügung steht. Anschließend lässt man in der bevorzugten Ausführungsvariante einen Dijkstra-Algorithmus und Abfragen laufen, ob der resultierende LSP zwischen den PE-Knoten PE_pi und PE_pe die Laufzeit-Vorgaben erfüllt und über ausreichend Bandbreite verfügt, um den Verkehr zu übertragen. Diese Schritte werden wiederholt, bis ein optimaler LSP in beiden Richtungen zwischen den PE-Knoten PE_pi und PE_pe gefunden wird. Anschließend geht das Verfahren 20 von Schritt 36 zu Schritt 38 über.
In Schritt 38 erstellt der zentrale Manager LSPPs zwischen den PE-Knoten PE_si und PE_se, d.h. für die sekundäre Strecke. In der bevorzugten Ausführungsvariante erfolgt die Auswahl dieser LSPPs auf die gleiche Weise wie für die LSPPs der primären Strecke, die in Bezug auf Schritt 36 erläutert wurde (z.B. die geringste Anzahl an P-Knoten-Hops oder gleichmäßige oder praktisch gleichmäßige Verteilung der Auslastung auf alle P-Knoten im LSP). Zudem sind die für die Auswahl in Schritt 36 verwendeten P-Knoten jedoch von einer Berücksichtigung bei der Auswahl in Schritt 38 ausgeschlossen. Dies gewährleistet, dass die Backup-LSPs physisch von den LSPs der primären Strecke getrennt sind, während gleichzeitig ausreichend Bandbreite für einen 1 + 1-Schutz zur Verfügung gestellt wird. Anschließend geht das Verfahren von Schritt 38 zu Schritt 40 über.
In Schritt 40 legt der zentrale Manager CM fest, ob die bis dahin erstellte Konfiguration (z.B. PE-Knoten-Connectivity und primäre und Backup-LSPs) irgendwelche Vorgaben aus dem festgelegten Vorgabensatz verletzt. In der bevorzugten Ausführungsvariante können die Vorgaben eine oder mehrere der im Folgenden aufgeführten Bedingungen beinhalten, und zwar werden die Vorgaben, die sich auf die Strecken beziehen, für jede Richtung spezifiziert, d.h. für jeden LSP in einem LSPP. Als erste Vorgabe kann ein gegebener L2PE-Knoten das Multi-Homing nur für diejenigen PE-Knoten in einer bestimmten geographischen Nähe bieten; beispielsweise kann diese Einschränkung in einer Größenordnung von 10 km liegen, allerdings unter Berücksichtigung der Tatsache, dass Anzahl oder Bereich von der jeweiligen Implementierung abhängig sein können. Als zweite Vorgabe kann eine logische VPLS-Einheit an einem gegebenen L2PE-Knoten nur eine Verbindung mit einem PE-Knoten herstellen. Als dritte Vorgabe darf die Bandbreite an einem Knoten einen bestimmten Grenzwert nicht überschreiten, in Abhängigkeit von der Verarbeitungskapazität dieses Knotens, d.h. unterschiedliche Knoten können unterschiedliche Verarbeitungskapazitäten aufweisen (z.B. kann der PE-Knoten PE₁ insgesamt 10G verarbeiten, während der PE-Knoten PE₂ nur 5G verarbeiten kann usw.; Gleiches gilt für P-Knoten). Als vierte Vorgabe bezieht sich, bzw. umfasst ein VPLS, der aus den logischen VPLS-Einheiten innerhalb verschiedener L2PEs besteht, zahlreiche PE-Knoten. Als fünfte Vorgabe sollte der Datenverkehr zwischen einer logischen VPLS-Einheit und einem PE-Knoten PE_x kleiner oder gleich der verfügbaren Bandbreite in der Verbindung zwischen dieser logischen VPLS-Einheit und dem PE-Knoten PE_x sein. Als sechste Vorgabe kann ein PE-Knoten für jeden VPLS nur mit einer bestimmten Anzahl an P-Knoten eine Verbindung herstellen, d.h. dass unter allen verfügbaren P-Knoten einige nicht für die Connectivity mit einem gegebenen VPLS in Frage kommen. Als siebte Vorgabe sollte die Bandbreite ausglichen sein, d.h. dass die Summe der Bandbreiten, die in einen PE-Knoten PE_x gelangt (möglichst von mehreren L2PE-Knoten) plus der Summe der Bandbreiten, die in diesen PE-Knoten PE_x von den P-Knoten gelangt, gleich der Bandbreite sein soll, die diesen PE-Knoten PE_x verlässt (in Richtung eines oder mehrerer L2PE-Knoten) plus der Summe der Bandbreiten, die aus diesem PE-Knoten PE_x in Richtung beliebiger P-Knoten verlässt. Als achte Vorgabe muss die Summe der Bandbreiten, die in diesen P-Knoten gelangt, in einem P-Knoten kleiner oder gleich der Summe der Bandbreitenkapazität in der Ausgangsverbindung zwischen diesem P-Knoten und seinen benachbarten P-Knoten sein. Als neunte Vorgabe muss die Summe der Bandbreiten, die in alle PE-Knoten gelangt, gleich der Summe der Bandbreiten sein, die alle PE-Knoten verlässt (um zu gewährleisten, dass der Datenverkehr nicht zirkuliert). Als letzte Vorgabe können Grenzwerte für die Streckenlaufzeit für einen oder mehrere Pfade vorgegeben werden (z.B. können bestimmte Pfade TDM-Verkehr übertragen, der Laufzeit-empfindlich ist), und diese Laufzeit-Grenzwerte müssen eingehalten werden. In Abhängigkeit von einer bestimmten Anzahl aller oder einiger dieser verschiedenen Vorgaben wird in Schritt 40 ermittelt, ob eine festgelegte Vorgabe verletzt wurde; ist dies der Fall, streicht das Verfahren 20 den vorliegenden Satz an Verbindungen, die sich aus den unmittelbar vorhergehenden Schritten 36 und 38 ergeben haben, und geht von Schritt 40 zurück zu Schritt 36, so dass ein neues LSPP für die primäre Konfiguration erstellt, und anschließend in Schritt 38 ein neues LSPP für die Backup-Konfiguration erstellt wird, die dann beide anhand der Vorgaben in Schritt 40 überprüft werden. Schließlich wird Schritt 40 in vielen Fällen erfüllt, d.h. es wird keine Vorgabe verletzt, und anschließend geht das Verfahren 20 von Schritt 40 zu Schritt 42 über. Es ist jedoch darauf hinzuweisen, dass alternativ dazu in bestimmten Fällen im Verfahren zur Verkehrsplanung ein Fall auftreten kann, wo es nach zahlreichen Schleifen mit den Schritten 36, 38 und 40 einen Punkt geben kann, an dem kein Satz ermittelt werden kann, der die in Verbindung mit Schritt 40 aufgeführten Vorgaben erfüllen kann; zu diesem Zweck kann vom Fachmann eine geeignete heuristische Methode entwickelt werden, um festzustellen, wann dieser Punkt erreicht ist, um entsprechend entweder durch eine Änderung im Ablaufdiagramm des Verfahrens 20, einen Interrupt oder eine andere geeignete Maßnahme reagieren zu können, um mit dem Ablauf fortzufahren und dabei gleichzeitig eine ausreichende Anzahl an Iterationen zu beachten, die durchgeführt werden, um eine möglichst optimale Lösung zu erreichen.
In Schritt 42 speichert der zentrale Manager CM die Connectivity-Informationen, die er in den vorhergehenden Schritten entwickelt hat, und die die Vorgaben in Bezug auf Schritt 40 erfüllt haben; so wird für einen Fall, in dem die Schritte 32 bis 40 zunächst in Bezug auf einen ersten VPLS und einen ersten L2PE-Knoten durchgeführt wurden, die entsprechende Connectivity gespeichert. Anschließend geht das Verfahren 20 von Schritt 42 zu Schritt 44 über.
In Schritt 44 legt der zentrale Manager CM fest, ob das MEN weitere L2PE-Knoten umfasst, die noch nicht berücksichtigt wurden und für die in den in Schritt 30 übermittelten Informationen angegeben wurde, dass sie möglichst in den vorliegenden VPLS zu berücksichtigen sind. In Bezug auf 1 beispielsweise, wenn die Schritte 32 bis 42 zunächst in Bezug auf VPLS₁ und im Hinblick auf den L2PE-Knoten L2PE₁ abgeschlossen wurden, legt Schritt 44 fest, dass VPLS₁ außerdem in Bezug auf den L2PE-Knoten L2PE₃ betrachtet werden sollte. Muss daher ein zusätzlicher L2PE-Knoten berücksichtigt werden, geht Schritt 44 weiter zu Schritt 46, der die Betrachtung auf diesen nächsten L2PE-Knoten (z.B. L2PE₃) ausdehnt, und der Ablauf kehrt wieder zurück zu Schritt 32. Wenn jedoch alle L2PE-Knoten in Bezug auf die vorliegenden VPLS (z.B. VPLS₁) berücksichtigt wurden, geht das Verfahren 20 von Schritt 44 weiter zu Schritt 48.
In Schritt 48 ermittelt der zentrale Manager CM, ob das MEN einen weiteren VPLS umfasst, der noch nicht berücksichtigt wurde und der in den in Schritt 30 übermittelten Informationen aufgeführt ist. Wiederum in Bezug auf 1, wenn die Schritte 32 bis 44 zunächst in Bezug auf VPLS₁ ausgeführt wurden, wird in Schritt 48 ermittelt, dass auch VPLS₂ in Bezug auf das MEN berücksichtigt werden sollte. Wenn daher weitere VPLS berücksichtigt werden sollen, geht Schritt 48 weiter zu Schritt 50, der diesen nächsten VPLS-Knoten (z.B. VPLS₂) berücksichtigt, anschließend geht das Verfahren zurück zu Schritt 32. Wenn jedoch sämtliche VPLSs berücksichtigt wurden, geht das Verfahren 20 von Schritt 48 weiter zu Schritt 50.
In Schritt 52 ermittelt der zentrale Manager CM eine Kostenfunktion für die gespeicherte Connectivity in Bezug auf alle VPLSs für die L2PE-Knoten, deren VPLSs in den vorangegangenen Schritten 32 bis 42 ermittelt wurden. Mit anderen Worten ist darauf zu achten, dass nach dem Erreichen von Schritt 52 ein Satz verschiedener Homing-Konfigurationen ermittelt wurde, wobei dieser Satz eine unterschiedliche Homing-Konfiguration für jede oben beschriebene Iteration umfasst, d.h. es kann jeweils eine unterschiedliche Homing-Konfiguration für die Iteration in Bezug auf VPLS₁ in L2PE₁, für die Iteration in Bezug auf VPLS₁ in L2PE₂, ..., für die Iteration in Bezug auf VPLS₁ in L2PE₅, für die Iteration in Bezug auf VPLS₂ in L2PE₁, für die Iteration in Bezug auf VPLS₂ in L2PE₂, ..., für die Iteration in Bezug auf VPLS₂ in L2PE₅ usw. bis zur Iteration in Bezug auf VPLS₃ in L2PE₅ geben. Gemeinsam ergeben diese Iterationen und die entsprechenden Konfigurationen einen kompletten Satz an Homing-Konfigurationen, die in diesem Beispiel die Konfigurationen für VPLS₁ in L2PE₁, ..., VPLS₃ in L2PE₅ umfassen. Daher ermittelt der zentrale Manager CM in Schritt 52 die Kostenfunktion für diesen Satz an Homing-Konfigurationen. Der Fachmann kann zahlreiche, unterschiedliche Kostenfunktionen ermitteln, die für Schritt 42 berechnet werden können. Als ein Beispiel ist die Kostenfunktion in der bevorzugten Ausführungsvariante gleich der Gesamtanzahl an VPLS-Verbindungen (oder logischen VPLS-Einheiten), die in der gespeicherten Connectivity für das MEN-System 10 enthalten sind. Wenn die gespeicherte Connectivity beispielsweise der Darstellung in 1 entspricht, wird in Schritt 52 eine Gesamtanzahl von zehn VPLS-Verbindungen ermittelt, mit drei VPLS-Verbindungen im L2PE-Knoten L2PE₁, einer VPLS-Verbindung im L2PE-Knoten L2PE₂, zwei VPLS-Verbindungen im L2PE-Knoten L2PE₃, drei VPLS-Verbindungen im L2PE-Knoten L2PE₄ und einer VPLS-Verbindung im L2PE- Knoten L2PE₅. Anschließend geht das Verfahren 20 von Schritt 52 weiter zu Schritt 54.
In Schritt 54 ermittelt der zentrale Manager CM, ob eine ausreichende Anzahl an Iterationen der oben angeführten Schritte durchgeführt wurde; es ist darauf hinzuweisen, dass diese Ermittlung in Bezug auf die anwendbare Kostenfunktion erfolgen kann, d.h. ob eine ausreichende Diversität von Kostenfunktionen gefunden wurde, die den jeweiligen, unterschiedlichen Homing-Konfigurationen entsprechen (wobei daran erinnert wird, dass in Schritt 52 für jede Homing-Konfiguration eine Kostenfunktion ermittelt wird, die in Bezug auf diese Konfiguration funktioniert).
Alternativ dazu kann Schritt 54 auf einem Vergleich der Anzahl an Iterationen mit einem bestimmten Grenzwert basieren, wobei ein Zähler für diese Iterationen geführt wird. Die allgemeine Verkehrsplanung in einem Multi-homed VPLS-Netz weist daher gemäß den Urhebern der vorliegenden Erfindung ein so genanntes NP-Hard Problem auf, d.h. es gibt hier aufgrund der Unmöglichkeit der vollständigen Untersuchung der vorhergehenden Alternativen keinen absolut besten Fall; insbesondere im vorliegenden Kontext, da jede Connectivity-Konfiguration für einen VPLS festgelegt wird, liegt die Komplexität darin, diese in Bezug auf die bereits festgelegten Connectivity-Konfigurationen sowohl für diesen VPLS als auch für die anderen VPLSs zu bewerten. Aufgrund dieser Eigenschaft kann es sein, dass eine absolute Anzahl an Iterationen angenommen werden kann, um eine optimale, oder zumindest akzeptable Lösung zu finden. Auf jeden Fall fährt das Verfahren 20 bei Schritt 54 fort, wenn die Bedingung(en) aus Schritt 54 vorgeben, dass weitere Iterationen erforderlich sind, und geht zu Schritt 56 über, der den Ablauf zum ersten VPLS (z.B. VPLS₁) zurückführt, anschließend geht der Ablauf zurück zu Schritt 32; daher muss für dieses Beispiel in Schritt 32 ff. ein neuer Satz an Homing-Konfigurationen ermittelt werden, zuerst für den ersten VPLS im ersten L2PE-Knoten, anschließend von diesem ersten VPLS in einem zweiten L2PE-Knoten, wiederum bis die Connectivity für alle vorgesehenen L2PE-Knoten und anschließend für alle anderen VPLSs in allen gewünschten L2PE-Knoten berücksichtigt wurde. Alternativ dazu kann das Verfahren 20, wenn die Bedingung(en) aus Schritt 54 vorgeben, dass keine weiteren Iterationen erforderlich sind, von Schritt 54 weiter zu Schritt 58 gehen.
In Schritt 58, der erreicht wird, nachdem eine Reihe unterschiedlicher Sätze mit Homing-Konfigurationen in den vorhergehenden Schritten festgelegt wurden, wählt der zentrale Manager CM den Satz mit Homing-Konfigurationen aus, der unter diesen Konfigurationen die beste Kostenfunktion aufweist. In dem Fall beispielsweise, in dem die Kostenfunktion der Anzahl an VPLSs entspricht, die oben in Bezug auf Schritt 52 beschrieben wurden, kann Schritt 58 den Satz mit Homing-Konfigurationen auswählen, die die größte Anzahl an logischen VPLS-Einheiten für das MEN aufweisen, und wenn mehr als eine Connectivity-Konfiguration mit der gleichen maximalen Anzahl an logischen VPLS-Einheiten vorliegt, kann der Fachmann zusätzliche Untersuchungen der Kostenfunktion vornehmen, um eine dieser Connectivity-Konfigurationen auszuwählen.
Die beste Kostenfunktion ist somit einer Ausgangsconnectivity-Konfiguration zugeordnet, die die Anzahl und die Auswahl an PE-Knoten-Homes, LSPs und die Anzahl an logischen VPLS-Einheiten umfasst. Diese Auswahl hat zur Folge, dass diese Connectivity anschließend in der tatsächlichen Konfiguration des MEN-Systems 10 eingesetzt wird. Falls der zentrale Manager CM Bestandteil dieses Systems 10 ist, werden diese Informationen später genutzt, um den verschiedenen Knoten mitzuteilen, dass diese Connectivity zu implementieren ist. Nach Schritt 58 fährt das Verfahren 20 schließlich mit Schritt 60 fort, anschließend ist das Verfahren 20 abgeschlossen, wie aus dem Abschlussstatus 60 ersichtlich ist. Somit verfügt der zentrale Manager CM nach dem Abschlussschritt 58 oder als Teil dessen über eine optimale Connectivity-Konfiguration für ein Multihome Mehrfach-VPLS-System im Netz 10, und diese Connectivity-Konfiguration kann vom zentralen Manager CM an jeden Knoten übertragen werden, um diese Connectivity umzusetzen.
Die vorangehende Beschreibung des Verfahrens 20 und seiner verschiedenen Schritte bietet eine optimale Connectivity-Konfiguration für ein Multihome Mehrfach-VPLS-System, die implementiert werden kann, wenn ein MEN erstmals konfiguriert wird. In den bevorzugten Ausführungsvarianten wird jedoch auch berücksichtigt, dass das Verfahren 20 auf ein bereits bestehendes MEN angewandt werden kann, wobei entweder neuer Datenverkehr und/oder neue VPLSs in das Netz aufgenommen werden. Insbesondere in diesen Fällen legt die bevorzugte Ausführungsvariante fest, welcher PE-Knoten für einen neu hinzugekommenen VPLS in Frage kommt und/oder fügt einem PE-Knoten möglicherweise ein neues Home hinzu, wenn die Blockierung überschritten wird. Auf jeden Fall kann diese zusätzliche Connectivity erreicht werden, indem das Verfahren 20 durchgeführt wird, während die Schritte 32 und 34 ausgelassen werden; anstelle dieser Schritte wird die gewünschte Connectivity für den neu hinzugekommenen Verkehr/VPLS aus den bereits bestehenden LSPPs ausgewählt, während alle anderen Schritte des Verfahrens 20 ausgeführt werden. Auf diese Weise werden der bestehende Verkehr und der entsprechende Aufbau dadurch nicht beeinträchtigt.
Die folgenden Merkmale und/oder Kombinationen von Merkmalen können ebenfalls vorteilhafte Ausführungsvarianten der beschriebenen und/oder in den Ansprüchen aufgeführten Erfindung darstellen:

– Die beschriebene und/oder in den Ansprüchen aufgeführte Verarbeitungsvorrichtung, wobei der Schritt zur Spezifikation eines dritten Pfads und eines vierten Pfads als Reaktion auf die Aufteilung der Bandbreitenauslastung in einer Reihe von P-Knoten-Hops im dritten Pfad und im vierten Pfad erfolgt, so dass die Bandbreitenauslastung zwischen jedem aufeinander folgenden Hop zwischen aufeinander folgenden P-Knoten innerhalb der Toleranz der Bandbreitenauslastung zwischen jedem aufeinander folgendem Hop zwischen aufeinander folgenden P-Knoten im gleichen Pfad liegt.
– Die beschriebene und/oder in den Ansprüchen aufgeführte Verarbeitungsvorrichtung, wobei der Schritt zur Spezifikation eines ersten Pfads und eines zweiten Pfads als Reaktion auf die Anzahl an P-Knoten-Hops in dem ersten Pfad und in dem zweiten Pfad erfolgt.
– Die beschriebene und/oder in den Ansprüchen aufgeführte Verarbeitungsvorrichtung, wobei der Schritt zur Spezifikation eines ersten Pfads und eines zweiten Pfads als Reaktion auf die Verteilung der Bandbreitenauslastung in einer Reihe von P-Knoten-Hops im ersten Pfad und im zweiten Pfad erfolgt, so dass die Bandbreitenauslastung zwischen jedem aufeinander folgenden Hop zwischen aufeinander folgenden P-Knoten innerhalb der Toleranz für die Bandbreitenauslastung zwischen jedem aufeinander folgenden Hop zwischen aufeinander folgenden P-Knoten im gleichen Pfad liegt.
– Die beschriebene und/oder in den Ansprüchen aufgeführte Verarbeitungsvorrichtung, wobei der Schritt zur Berechung einer Kostenfunktion für jeden Satz mit unterschiedlichen Homing-Konfigurationen aus der Vielzahl von Sätzen mit unterschiedlichen Homing-Konfigurationen die Berechnung der Gesamtanzahl an Virtual Private LAN-Dienstverbindungen umfasst, die in jedem Satz mit unterschiedlichen Homing-Konfigurationen enthalten sind.
– Die beschriebene und/oder in den Ansprüchen aufgeführte Verarbeitungsvorrichtung, wobei der Schritt zur Auswahl eines Satzes mit Homing-Konfigurationen die Auswahl eines Satzes mit Homing-Konfigurationen mit einer maximalen Gesamtanzahl an Virtual Private LAN-Dienstverbindungen umfasst, die in dem ausgewählten Satz mit Homing-Konfigurationen enthalten sind.
– Die beschriebene und/oder in den Ansprüchen enthaltene Verarbeitungsvorrichtung, wobei der Schritt zur Berechnung einer Kostenfunktion für jeden Satz mit unterschiedlichen Homing-Konfigurationen aus der Vielzahl an Sätzen mit unterschiedlichen Homing-Konfigurationen die Berechnung einer Gesamtanzahl an Virtual Privat LAN-Dienstverbindungen umfasst, die in jedem Satz mit unterschiedlichen Homing-Konfigurationen enthalten sind.
– Die beschriebene und/oder in den Ansprüchen enthaltene Verarbeitungsvorrichtung, wobei der Schritt zur Auswahl eines Satzes mit Homing-Konfigurationen die Auswahl eines Satzes mit Homing-Konfigurationen umfasst, der eine maximale Gesamtanzahl an Virtual Private LAN-Dienstverbindungen aufweist, die in dem ausgewählten Satz mit Homing-Konfigurationen enthalten sind.
– Die beschriebene und/oder in den Ansprüchen enthaltene Verarbeitungsvorrichtung, wobei das Netz ein Metro Ethernet-Netz umfasst.
– Die beschriebene und/oder in den Ansprüchen enthaltene Verarbeitungsvorrichtung, wobei ein Knoten aus der Vielzahl an Knoten die Verarbeitungsvorrichtung umfasst.
– Die beschriebene und/oder in den Ansprüchen enthaltene Verarbeitungsvorrichtung, die außerdem entsprechend programmiert ist, um den Schritt zur Übermittlung der Informationen an die PE-Knoten im Ethernet-Netz, die die Informationen empfangen, durchzuführen, wobei die Informationen als Reaktion auf den ausgewählten Satz mit Homing-Konfigurationen erfolgen.
– Ein Verfahren zur elektronischen Ermittlung von Homing-Pfaden für eine Vielzahl von Virtual Private LAN-Diensten in einem Ethernet-Netz, das eine Vielzahl von PE-Knoten umfasst, das aus den folgenden Schritten besteht: Ermittlung einer Vielzahl von Sätzen mit unterschiedlichen Homing-Konfigurationen, wobei jede Homing-Konfiguration in jedem Satz mit unterschiedlichen Homing-Konfigurationen durch eine entsprechende Iteration von Schritten berechnet wird; wobei jede Iteration dem jeweiligen Virtual Private LAN-Dienst aus der Vielzahl von Virtual Private LAN-Diensten entspricht und für den entsprechenden, ausgewählten Layer 2 Provider Egde-Knoten im Ethernet-Netz erfolgt; und wobei jede Iteration die folgenden Schritte umfasst: Auswahl eines PE-Eingangsknotens und eines PE-Ausgangsknotens; Festlegung der Bandbreite in den PE-Eingangsknoten; Festlegung der Bandbreite aus dem PE-Ausgangsknoten; Spezifikation eines ersten Pfades für die Verbindung von dem PE-Eingangsknoten zum PE-Ausgangsknoten sowie eines zweiten Pfades zur Verbindung von dem PE-Ausgangsknoten zum PE-Eingangsknoten, wobei jeder Pfad aus dem ersten und zweiten Pfad mindestens einen P-Knoten umfasst; Ermittlung einer Kostenfunktion für jeden Satz mit unterschiedlichen Homing-Konfigurationen aus der Vielzahl von Sätzen mit unterschiedlichen Homing-Konfigurationen; und Auswahl eines Satzes mit Homing-Konfigurationen aus der Vielzahl von Sätzen mit unterschiedlichen Homing-Konfigurationen als Reaktion auf die jeweilige, berechnete Kostenfunktion.

Aus den oben angeführten Darstellungen und Beschreibungen ist es für den Fachmann sicherlich offensichtlich, dass die bevorzugten Ausführungsvarianten ein Verfahren zur Verkehrsplanung in einem Multihomed VPLS-Computernetz bieten. Die beschriebenen, bevorzugten Ausführungsvarianten bieten zahlreiche Vorteile. Ein Vorteil besteht darin, dass die bevorzugten Ausführungsvarianten Betrachtungen zur Connectivity mit Multihoming, Schutz und Multicast-Datenverkehr in den Optimierungsprozess einbeziehen. Ein weiterer Vorteil besteht darin, dass die bevorzugten Ausführungsvarianten die dynamische Zuordnung von Homes (d.h. Verbindungen) in Echtzeit gewährleisten, wenn neue VPLSs erstellt werden, wobei nicht jedes Mal der vollständige Optimierungsprozess wiederholt werden muss, wenn ein neuer VPLS eingerichtet wird. Ein weiterer Vorteil besteht darin, dass die bevorzugten Ausführungsvarianten keine Umleitung des bestehenden Verkehrsflusses erfordern, wenn neue VPLSs eingerichtet werden. Ein weiterer Vorteil besteht darin, dass die bevorzugten Ausführungsvarianten zentralisiert sind und daher im Vergleich zu einem verteilten Algorithmus mit Routing-Protokollen wie z.B. PIM-SM und Ähnlichem wahrscheinlich einen besseren Einsatz der Netzressourcen ermöglichen. Ein weiterer Vorteil besteht darin, dass die bevorzugten Ausführungsvarianten die Einbindung von QoS-Betrachtungen in den Optimierungsprozess ermöglichen. Noch ein weiterer Vorteil besteht darin, dass die bevorzugten Ausführungsvarianten eine Lösung bieten, die sich gut an eine Erhöhung der Anzahl an Knoten anpasst. Ein letzter Vorteil besteht darin, dass trotz der detaillierten Beschreibung der bevorzugten Ausführungsvarianten verschiedene Ersetzungen, Modifikationen oder Änderungen an den oben angeführten Beschreibungen vorgenommen werden können, ohne vom Umfang der Erfindung abzuweichen, der in den folgenden Ansprüchen definiert wird.

Claims

Ein Computerprogramm, das Computerprogrammcode-Einrichtungen umfasst, die geeignet sind, Schritte des Programmcodes auszuführen, wenn das genannte Computerprogramm auf einem Computer läuft, wobei das genannte Computerprogramm geeignet ist, die Homing-Konfigurationen für eine Vielzahl von Virtual Private LAN-Diensten, VPLSs, in einem Ethernet-Netz (10) festzulegen; wobei das genannte Ethernet-Netz eine Vielzahl von Provider Edge-Knoten, PE-Knoten, umfasst; wobei die genannten PE-Knoten über Layer 2 Provider Edge-Knoten, L2PE-Knoten, mit einer Vielzahl von Customer Edge-Knoten, CE-Knoten, verbunden sind; wobei die genannten VPLSs von den genannten L2PE-Knoten unterstützt werden, wobei jede der genannten Homing-Konfigurationen Pfade von einem der L2PE-Knoten zu einem der PE-Knoten für jeden VPLS sowie Pfade zwischen den PE-Knoten für jeden VPLS und für jeden L2PE-Knoten repräsentiert; und wobei das genannte Computerprogramm geeignet ist, die folgenden Schritte auszuführen: Berechnung einer Vielzahl von Sätzen mit unterschiedlichen Homing-Konfigurationen; wobei jede Homing-Konfiguration in jedem Satz mit unterschiedlichen Homing-Konfigurationen durch eine entsprechende Iteration von Schritten berechnet wird; wobei jede Iteration dem jeweiligen VPLS aus der Vielzahl von VPLSs und dem entsprechenden, ausgewählten L2PE-Knoten im Ethernet-Netz entspricht; und wobei jede Iteration die folgenden Schritte umfasst: Auswahl (32) eines PE-Eingangsknotens, der den Verkehr empfängt, der anschließend in das Ethernet-Netz gelangt, und eines PE-Ausgangsknotens, der den Verkehr empfängt, der anschließend das Ethernet-Netz verlässt; Festlegung (32) der Bandbreite im PE-Eingangsknoten; Festlegung (32) der Bandbreite aus dem PE-Ausgangsknoten; Spezifikation (36), auf der Basis der festgelegten Bandbreiten, eines ersten Pfades zur Verbindung vom PE-Eingangsknoten zum PE-Ausgangsknoten und eines zweiten Pfades zur Verbindung vom PE-Ausgangsknoten zum PE-Eingangsknoten, wobei jeder Pfad aus dem ersten und zweiten Pfad mindestens einen Provider-Knoten, P-Knoten, umfasst; Berechnung (52) einer Kostenfunktion für jeden Satz mit unterschiedlichen Homing-Konfigurationen aus der Vielzahl von Sätzen mit unterschiedlichen Homing-Konfigurationen; und Auswahl (58) eines Satzes mit Homing-Konfigurationen aus der Vielzahl von Sätzen mit unterschiedlichen Homing-Konfigurationen als Reaktion auf die jeweilige, berechnete Kostenfunktion.
Das Computerprogramm gemäß Anspruch 1: wobei jede Homing-Konfiguration primäre Homing-Pfade und sekundäre Homing-Pfade umfasst; wobei die primären Homing-Pfade den ersten und den zweiten Pfad umfassen; und wobei das Computerprogramm außerdem geeignet ist, die sekundären Homing-Pfade für jede Homing-Konfiguration festzulegen, wobei jede Iteration außerdem die folgenden Schritte umfasst: Auswahl (34) eines sekundären PE-Eingangsknotens und eines sekundären PE-Ausgangsknotens; Festlegung (34) der Bandbreite im sekundären PE-Eingangsknoten; und Festlegung (34) der Bandbreite aus dem sekundären PE-Ausgangsknoten; Spezifikation (38) eines dritten Pfades für die Verbindung vom sekundären PE-Eingangsknoten zum sekundären PE-Ausgangsknoten sowie eines vierten Pfades für die Verbindung vom sekundären PE-Ausgangsknoten zum sekundären PE-Eingangsknoten, wobei jeder Pfad aus dem dritten und vierten Pfad mindestens einen P-Knoten umfasst.
Das Computerprogramm gemäß Anspruch 2, wobei jede Iteration außerdem die folgenden Schritte umfasst: Ermittlung (40), ob der erste Pfad oder der zweite Pfad einen Satz mit Vorgaben verletzt, der zumindest eine Vorgabe umfasst; und Ermittlung (40), ob der dritte Pfad oder der vierte Pfad den Satz mit Vorgaben verletzt.
Das Computerprogramm gemäß Anspruch 3, wobei der Satz mit Vorgaben eine Vorgabe in Bezug auf die Bandbreite in dem ersten und zweiten Pfad umfasst.
Das Computerprogramm gemäß Anspruch 3, wobei der Satz mit Vorgaben eine ausgewählte Vorgabe aus einem Satz enthält, der folgende Vorgaben umfasst: eine erste Vorgabe, wobei ein Layer 2 Provider Edge-Knoten nur für die PE-Knoten ein Multihoming bieten kann, die sich in einer vordefinierten, geographischen Nähe zu dem Layer 2 Provider Edge-Knoten befinden; eine zweite Vorgabe, wobei eine logische VPLS-Einheit nur mit einem PE-Knoten verbunden werden kann; eine dritte Vorgabe, wobei der Verkehr zwischen einer logischen VPLS-Einheit und einem PE-Knoten unter oder gleich der verfügbaren Bandbreite in der Verbindung zwischen der logischen VPLS-Einheit und dem PE-Knoten liegen muss; eine vierte Vorgabe, wobei die Bandbreite ausgeglichen sein muss, indem die Summe der Bandbreiten, die in einen PE-Knoten gelangen, plus der Summe der Bandbreiten, die von den P-Knoten in diesen PE-Knoten gelangen, gleich der Summe der Bandbreiten ist, die diesen PE-Knoten verlassen, plus der Summe der Bandbreiten, die diesen PE-Knoten in Richtung der P-Knoten verlassen; eine fünfte Vorgabe, wobei in einem P-Knoten die Summe der Bandbreiten, die in diesen P-Knoten gelangen, unter oder gleich der Summe der Bandbreitenkapazität in der Ausgangsverbindung zwischen diesem P-Knoten und einem angrenzenden P-Knoten betragen muss; eine sechste Vorgabe, wobei die Summe der Bandbreiten, die in alle PE-Knoten gelangen, gleich der Summe der Bandbreiten sein muss, die alle PE-Knoten verlassen; eine siebte Vorgabe, wobei die Bandbreite in einem PE-Knoten einen bestimmten Grenzwert, der von der Verarbeitungskapazität dieses PE-Knotens bestimmt wird, nicht überschreiten darf; und eine achte Vorgabe, wobei die Grenzwerte für die Streckenlaufzeit für einen oder mehrere Pfade vorgegeben sind.
Das Computerprogramm gemäß Anspruch 2, wobei die Vielzahl von PE-Knoten vollständig vermaschte PE-Knoten umfasst.
Das Computerprogramm gemäß Anspruch 2, das außerdem geeignet ist, vor dem Berechnungsschritt folgende Schritte auszuführen: Eingabe eines Satzes mit P-Knoten in das Ethernet-Netz; und Eingabe der Bandbreitenkapazität zwischen jedem P-Knoten aus dem Satz mit P-Knoten und einem angrenzenden P-Knoten aus dem Satz mit P-Knoten.
Das Computerprogramm gemäß Anspruch 7, das außerdem geeignet ist, vor dem Berechnungsschritt folgende Schritte auszuführen: Eingabe eines Satzes mit L2PE-Knoten in das Ethernet-Netz; und Eingabe der Bandbreitenkapazität zwischen jedem L2PE-Knoten aus dem Satz mit L2PE-Knoten und jedem PE-Knoten aus der Vielzahl von PE-Knoten.
Das Computerprogramm gemäß Anspruch 8, das außerdem entsprechend programmiert ist, um vor dem Berechnungsschritt den Schritt zur Eingabe von Informationen zur Bandbreitenanforderung zwischen jedem CE-Knoten, der mit dem Ethernet-Netz verbunden ist, und jedem anderen CE-Knoten, der mit dem Ethernet-Netz verbunden ist, auszuführen.
Das Computerprogramm gemäß Anspruch 2, wobei der Schritt zur Spezifikation eines dritten Pfades und eines vierten Pfades als Reaktion auf die Anzahl an P-Knoten-Hops in dem dritten Pfad und dem vierten Pfad erfolgt.