DE69626181T2

DE69626181T2 - Verfahren zur Zulassungssteuerung und Leitweglenkung von virtuellen Verbindungen

Info

Publication number: DE69626181T2
Application number: DE69626181T
Authority: DE
Inventors: Rainer Gawlick; Anil P. Kamath; Serge Plotkin; Kajamalai Gopalaswamy Ramakrishnan
Original assignee: Lucent Technologies Inc
Current assignee: Nokia of America Corp
Priority date: 1995-11-30
Filing date: 1996-11-19
Publication date: 2003-11-27
Anticipated expiration: 2016-11-20
Also published as: DE69635092T2; EP0777362B1; US6175870B1; JP3159927B2; CA2187242C; EP1235461B1; CA2187242A1; JPH09294128A; EP0777362A1; EP1235461A2; DE69635092D1; EP1235461A3; DE69626181D1

Description

Ein Netzwerk ist ein Mittel für den Austausch oder Transfer von Informationen (z. B. Signalen, die Daten, Sprache, Text, Video darstellen) zwischen Endpunkten (z. B. Hostmaschinen, Faxmaschinen oder Endgeräten), die mit dem Netzwerk verbunden sind. Das Netzwerk umfaßt Knoten, die durch Strecken miteinander und mit den Endpunkten verbunden sind. In der Regel ist jede Strecke bidirektional (d. h. Informationen können in der Vorwärts- und in der Rückwärtsrichtung übermittelt werden), und jede Strecke ist in jeder Richtung durch Parameter wie zum Beispiel eine Bandbreite oder Kapazität, gekennzeichnet. Die Knoten umfassen vorteilhafterweise Puffer. Wenn eine Strecke nicht über ausreichende Kapazität zum Behandeln von in einem Knoten empfangenen Informationen aufweist, kann ein Puffer in dem Knoten zur Speicherung der empfangenen Informationen verwendet werden, bis die Strecke ausreichende Kapazität besitzt.
Netzwerke werden zunehmend zur zuverlässigen und schnellen Übertragung von Informationen in digitalem Format zwischen Endpunkten über große Flächen verwendet. Diese erhöhte Verwendung bringt große Änderungen an Netzdiensten und an dem Architektur- /Infrastrukturentwurf mit sich. Insbesondere wird erwartet, daß ein großes Spektrum neuer Kundendienste, wie zum Beispiel Abrufvideo und Videokonferenzen auf BISDN-Netzwerken (Broadband Integrated Services Digital Networks) bereitgestellt wird. Die Haupttechnik zur Übertragung in BISDN wird als Asynchroner Transfermodus (ATM) bezeichnet. Siehe S. E. Minzer, "Broadband ISDN and Asynchronous Transfer Mode, "IEEE Comm. Mag., S. 17-24, September 1989.
Wenn Informationen zwischen zwei Endpunkten (einem einleitenden Endpunkt und einem Zielendpunkt) ausgetauscht werden sollen, fordert der einleitende Endpunkt an, daß ein bidirektionaler Weg (d. h. eine Knoten und Strecken umfassende Verbindung) in dem Netzwerk zwischen den beiden Endpunkten hergestellt wird. Bei einem ATM-Netzwerk ist der hergestellte Weg eine sogenannte "virtuelle Leitung" (VC), womit gemeint ist, daß der den Austausch einleitende Endpunkt einfach den Zielendpunkt angibt und das Netzwerk die Informationen so von dem einleitenden Endpunkt zu dem Zielendpunkt abliefert, als ob sie durch eine direkte Leitung verbunden wären. Die Anzahl von "Sprüngen" in dem Weg der VC ist gleich der Anzahl von Strecken in dem Weg oder eins weniger als die Anzahl von Knoten in dem Weg.
Ein wichtiger Gesichtspunkt beim Betrieb eines Netzwerkes ist, ob neue VCs in das Netzwerk hinein gelassen werden sollen, und wie zugelassene VCs durch das Netzwerk geroutet werden sollen. Bei der Bestimmung, ob Anforderungen von VCs von diesen Endpunkten zugelassen und wie diese zu routen sind, muß ein Netzzulassungs- und Wegelenkverfahren Betriebsmittel reservieren (z. B. Bandbreite auf den die VC umfassenden Strecken). Betriebsmittelreservierung ist notwendig, um etwaige von dem Netzwerk gegebene Dienstqualitätsgarantien (QOS-Garantien) zu erfüllen, z. B. Anforderungen bezüglich einer maximalen Informationsverlustsrate oder einer maximalen Verzögerung beim Empfangen von Informationen. Aus der Betriebsmittelreservierung folgt wiederum die Notwendigkeit einer Zulassungssteuerung, um sicherzustellen, daß Betriebsmittel nicht über die verfügbaren Betriebsmittel hinaus auf den Strecken und in den Knoten reserviert werden.
Im allgemeinen ist die Aufgabe von Wegelenk- und Zulassungssteuerverfahren die Maximierung der Ausnutzung der Netzbetriebsmittel, ohne Betriebsmitteleinschränkungen zu verletzen und unter gleichzeitiger Erfüllung etwaiger QOS-Garantien oder -Anforderungen. Viele Faktoren verkomplizieren Wegelenk- und Zulassungssteuerentscheidungen. Erstens müssen die Entscheidungen möglicherweise "online" erfolgen, d. h. ohne Kenntnis darüber, welche Auswirkung zukünftige Wegelenkanforderungen auf die Netzbetriebsmittel haben werden. Obwohl dieses Problem durch Techniken der sogenannten "dynamischen Umlenkung" gelöst werden könnte, wirken sich diese Techniken in der Regel nachteilig auf die Qualität des Benutzern des Netzwerkes gebotenen Dienstes aus. Zweitens ist der aktuelle Zustand des Netzwerkes (d. h. die Netztopologie und die aktuelle Zuteilung von Netzbetriebsmitteln) möglicherweise nicht verfügbar, wie zum Beispiel, wenn Informationen über kürzlich zugeteilte Betriebsmittel noch nicht im Netzwerkzustand wiedergegeben werden. In einem solchen Fall kann die Wegelenk- und Zulassungsentscheidung auf statischen oder ungenauen Zustandsinformationen basieren. Drittens müssen die Zulassungs- und Wegelenkentscheidungen häufig in Echtzeit durchgeführt werden, d. h. innerhalb eines Intervalls, das durch das VC-Aufbauprotokoll festgelegt wird, das die Zeitdauer spezifiziert, die für einen Versuch zugeteilt wird, eine VC herzustellen oder aufzubauen, und sie spezifiziert, wieviel Versuche, eine VC aufzubauen, zugelassen sind.
Von Zulassungssteuer- und Wegelenkverfahren werden in der Regel angeforderte VCs auf gewählten Wegen zugelassen und geroutet, um so eine bestimmte Kostenfunktion zu minimieren, die die Menge an von dem gewählten Weg erforderten Netzbetriebsmitteln wiedergibt. Obwohl vielfältige Kostenfunktionen verwendet werden können, sind Kostenfunktionen in der Regel Funktionen von Parametern, die mit dem aktuellen Netzzustand, der Verzögerung durch das Netzwerk, zusammenhängen.
Wie das Zulassungs- und Wegelenkproblem für angeforderte virtuelle Leitungen behandelt wird, basiert in der Regel auf Faktoren wie zum Beispiel, ob das Routen mit vollständigen oder unvollständigen Informationen erfolgt und ob die VCs permanent oder vermittelt sind. Insbesondere sind solche Faktoren in der Regel zum Spezifizieren der Parameter der Kostenfunktion nützlich. Das Routen mit unvollständigen Informationen bedeutet einfach, daß der Zustand des Netzwerkes nicht bekannt ist, oder, wenn der Zustand bekannt ist, daß die Zustandsinformationen veraltet sind, z. B. daß die verfügbaren Zustandsinformationen keine Informationen bezüglich Netzbetriebsmitteln enthalten, die den zu allerletzt gerouteten VCs zugeteilt werden. Umgekehrt bedeutet Routen mit vollständigen Informationen, daß die Zustandsinformationen vollständig bekannt sind und daß die Zustandsinformationen aktuell sind. Von großen Netzwerken (z. B. Netzwerken, die in der Größenordnung von 100 Knoten über ein geographisches Gebiet der Größe der Vereinigten Staaten umfassen) kann aufgrund der Ausbreitungsverzögerungen bei dem Weiterleiten von Informationen von Knoten zu Knoten nicht erwartet werden, daß sie in jedem Knoten, der mit einem Ursprungsendknoten verbunden ist, genaue oder vollständige Zustandsinformationen aufweisen. Folglich müssen solche Netzwerke entweder alle Wegelenkentscheidungen auf der Grundlage vollständiger Informationen an einem zentralen Standort (der Zugang zu allen Knoten hat) treffen oder das Netzwerk muß Wegelenkentscheidungen lokal (d. h. auf verteilte Weise) auf der Grundlage statischer oder ungenauer Zustandsinformationen treffen. Permanente VCs sind Wege für den Informationstransfer zwischen Endpunkten, die so ausgelegt sind, daß sie für lange Zeiträume, vielleicht in der Größenordnung von Jahren, betrieben werden und hergestellt bleiben. Vermittelte VCs sind für einen Betrieb für Stunden oder Tage ausgelegt.
Ein Zulassungsschema, das für permanente VCs und für vermittelte VCs vorgeschlagen wurde (wobei die vermittelten VCs für bekannte Zeiträume hergestellt werden sollen) verwendet eine Exponentialfunktion der Streckenlast zur Auswertung der Kosten des Routens von Informationen auf einem beliebigen gegebenen Weg in dem Netzwerk. Siehe B. Awerbuch et al. "Throughput- Competitive On-Line Routing", 34th Annual Symp. on Foundations of Comp. Sci., Palo Alto, CA, November 1993. Der auf exponentiellen Kosten basierende Algorhytmus von Awerbuch et al., supra, wird hier als das "AAP"-Verfahren bezeichnet.
Das AAP-Verfahren basiert auf einer Kostenschwelle, die als Funktion einer zulässigen Schwelle und einer exponentiellen Kostenmetrik für jede Strecke in dem Netzwerk bestimmt wird. Das AAP- Verfahren bestimmt für eine angeforderte VC eine Menge von Wegen, auf denen die angeforderte VC geroutet werden kann, wobei die Kosten des Routens auf den Strecken in jedem gegebenen Weg in der Menge von Wegen unter der Kostenschwelle liegen. Jede Anforderung, deren Kosten des Routens durch das Netzwerk über der Kostenschwelle liegen, wird zurückgewiesen. Das AAP- Verfahren hat jedoch mehrere Unzulänglichkeiten. Erstens gibt das AAP-Verfahren nicht an, welcher bestimmte Weg in der Menge von Wegen zum Routen der angeforderten VC verwendet werden soll (d. h. das AAP- Verfahren führt ausschließlich eine Zulassungssteuerung durch und wählt keine bestimmten Wege für angeforderte VCs aus oder routet diese). Außerdem geben Awerbuch et al. nicht an, wie das AAP-Verfahren im Fall vermittelter VCs anzuwenden ist, die für unbekannte Zeiträume hergestellt werden sollen. Andere Aspekte des AAP-Verfahrens und insbesondere der exponentiellen Kostenfunktion des AAP-Verfahrens werden in den nachfolgenden Abschnitten untersucht.
Tabelle 1 zeigt Pseudokode, der einen Teil des auf AAP-Exponentialkosten basierenden Verfahrens implementiert. Jede Zeile des Pseudokodes von Tabelle 1 wird nachfolgend erläutert. Es sei n die Anzahl von Knoten in dem Netzwerk. Die jeder Strecke e in dem Netzwerk zugewiesene Kapazität u(e) stellt auf dieser Strecke verfügbare Bandbreite dar. Nach dem Empfang einer j-ten Anforderung von einem Ursprungsendpunkt für eine VC zu einem Zielendpunkt (Zeile 1 des Pseudokodes), wobei die Anforderung durch (sj, tj, rj, Tsj, Tfj) dargestellt wird, versucht das AAP- Verfahren, einen Weg der Kapazität rj von dem Ursprungsknoten sj (der direkt mit dem Ursprungsendpunkt verbunden ist) zu dem Zielknoten tj (der direkt mit dem Zielendpunkt verbunden ist), beginnend zum Zeitpunkt Tjs und endend zum Zeitpunkt Tjf, zuzuteilen. Der Einfachheit halber soll angenommen werden, daß das Routen zum Zeitpunkt Tsj geschieht. Das Ziel des AAP- Verfahrens besteht darin, den Durchsatz des Netzwerkes, d. h. die durch das Netzwerk über ein gegebenes Zeitintervall geführte Informationsmenge, zu maximieren. Es sei Tj = Tfj - Tsj die Haltezeit oder Dauer der Leitung, T das maximal mögliche Tj, und r die maximale Anforderungsbandbreite (Rate) rj. Die Kostenschwelle für das AAP-Verfahren sei das Produkt von n, r und T.
(1) ROUTER (sj, tj, Tsj, Tfj, rj):
(2) τ, e E : ce (τ, j) ← u(e)(uλ,(τ,j) - 1);*
(3)Wenn Pfad P in G(V, E) von sj bis rj s.t.
(5) Die angeforderte Leitung auf P routen und folgendes setzen:
(6) e P, Tsj ≤ τ ≤ Tfj,
(7) λe (τ, j+ 1) ← λe(τ, j) + rj/u(e)
(8) sonst die Verbindung zurückweisen

Tabelle 1

Bei dem AAP-Verfahren basiert die Wegelenkentscheidung auf den Informationen über die aktuelle Auslastung (den aktuellen Bedarf) und über den zukünftigen Bedarf an Betriebsmitteln auf den Strecken (oder Rändern) des Netzwerkes, d. h. die Wegelenkentscheidung berücksichtigt den Bedarf für Anforderungen von VCs, die während der Haltezeit der j-ten VC geroutet werden können. Die Auslastung wird relativ zu der Randkapazität u(e) gemessen. Es sei Pi die Route, mit der die i-te Anforderung erfüllt wird. Die Last auf dem Rand e zum Zeitpunkt τ, gesehen durch das Wegelenkverfahren beim Routen der j-ten Leitung, ist folgendermaßen definiert:
Gleichung (1) gibt einen Stau oder eine Auslastung auf der Strecke e zum Zeitpunkt τ aufgrund anderer auf der Strecke e gerouteter Anforderungen an. Nach der Berechnung der Auslastung ist der nächste Schritt die Berechnung der exponentiellen Kosten, wie in Zeile 2 von Tabelle 1. Bei dem AAP-Verfahren sind die Kosten des Randes e zum Zeitpunkt τ, ce (τ. j), beim Routen der j-ten Leitung definiert durch
(2) ce(τ, j) = u(e)(uλ,(τ.j) - 1).
wobei λe die Auslastung auf der Strecke e (d. h. der Prozentsatz der benutzten Streckenkapazität) zum Zeitpunkt τ beim Versuch, die j-ten VC zu routen, u(e) die Kapazität der Strecke e und u ein Parameter ist. Der Parameter u hängt mit folgendem zusammen: n, der Anzahl von Knoten in dem Netzwerk, r, dem maximalen möglichen Wert von rj; und T dem maximalen möglichen Wert von Tj. Wenn es eine Menge von Wegen gibt, für die die Kosten des Routens der angeforderten VC auf einem beliebigen Weg in der Menge unter der Schwelle liegen, wird die Anforderung angenommen (Zeilen 3-5). In den Zeilen 6-7 von Tabelle 1 werden die von der gerouteten Anforderung benötigten Betriebsmittel in einem aktualisierten Netzzustand wiedergegeben. Wenn die Menge von Wegen die leere Menge ist, wird die Anforderung zurückgewiesen.
Awerbuch et al. schlagen vor, u als 2nTr/(rmin + 1) auszuwählen (wobei min die kleinste Bandbreite ist, die eine beliebige VC anfordert). Der Wert von u kann bei einem mäßig großen Netzwerk in der Größenordnung von 100 000 liegen. Die richtige Auswahl hoher Werte für den Parameter u garantiert ein Routen einer Gesamtzahl von Anforderungen für VCs innerhalb eines Faktors (in der Größenordnung von log u) der Anzahl von Anforderungen, die von einem optimalen, Off- Line-Wegelenkschema, d. h. einem Schema, das über Informationen über alle Anforderungen im voraus verfügt, geroutet werden können.
Obwohl das AAP-Verfahren ausreichend Betriebsmittel zum Routen zugelassener VC-Anforderungen garantiert, hat das Verfahren insofern eine weitere Unzulänglichkeit, als es beim Zulassen von VCs zu vorsichtig ist und deshalb Netzbetriebsmittel nicht voll ausnutzt. Ein einfaches Reduzieren des Werte von u bewirkt jedoch, daß das AAP-Verfahren mehr Anforderungen annimmt, als verfügbare Netzbetriebsmittel vorhanden sind, was nachteilig ist, da es bedeuten kann, daß das Netzwerk nicht in der Lage ist, Netzbenutzern garantierte QOS-Anforderungen zu erfüllen. Außerdem erfordert das AAP-Verfahren Kenntnis von Streckenlasten sowohl zu aktuellen als auch zukünftigen Zeiten. Diese Kenntnis kann möglicherweise nicht verfügbar sein und kann auf veralteten Informationen basieren oder zuviel Speicher zur Speicherung erfordern.
Somit wird ein verbessertes Verfahren zur Wegelenkung und Zulassungssteuerung von VCs benötigt, das die Ausnutzung von Netzbetriebsmitteln vergrößert, während QOS-Anforderungen erfüllt werden, wobei das Verfahren in Netzwerken vermittelter VCs verwendet werden kann, bei denen die Dauer oder Haltezeit der VCs unbekannt ist.
EP-A-0674459 beschreibt ein Verfahren für das On- Line-Routen permanenter virtueller Leitungen in Kommunikationsnetzen. Das Routen wird erreicht, indem aus mehreren möglichen Alternativen ein Weg mit geringsten Kosten ausgewählt wird. Die Kosten jedes Weges werden durch Summieren einer Kostenfunktion über die Strecken des Weges ausgewertet. Die Kostenfunktion kann eine Exponentialfunktion der gerade benutzten Streckenkapazität und der angeforderten Streckenkapazität sein.
EP-A-0660589 beschreibt ein Wegelenkverfahren zur Verwendung in einem Paketnetz. Das Routen wird durch einen Wegauswahlprozess erreicht, der sowohl Sprungzählwerte als auch Niveaus der Streckenausnutzung auf Kandidatenwegen berücksichtigt.
Gemäß der vorliegenden Erfindung wird ein Verfahren nach Anspruch 1 bereitgestellt.
Es wird anerkannt, daß die Kosten des Routens einer angeforderten virtuellen Leitung auf Strecken in einem Weg durch ein Netzwerk mit einer Menge von Strecken auf der Grundlage eines Parameters bestimmt werden können, der mit der Anzahl von Sprüngen in einer Teilmenge der Menge aller zuvor in dem Netzwerk hergestellten virtuellen Leitungen zusammenhängt. Das erfindungsgemäße Verfahren bestimmt die Kosten für das Routen einer angeforderten virtuellen Leitung auf einem Weg durch: Empfangen einer Anforderung, eine virtuelle Leitung auf einem Weg zwischen einem Ursprungsknoten und einem Zielknoten zu routen, Bestimmen der Auslastung auf jeder Strecke in einer Teilmenge der Menge von Strecken in dem Netzwerk und Bestimmen jeweiliger Kosten für das Routen der Anforderung über mögliche Wege in dem Netzwerk zwischen dem Ursprungsknoten und dem Zielknoten, wobei die möglichen Wege Strecken in der Teilmenge der Menge von Strecken umfassen und wobei die Kosten eine Funktion eines Netzwerkzustandes und eines Parameters sind, der mit der Anzahl von Sprüngen für die Teilmenge der Menge aller virtuellen Leitungen, die zuvor durch das Netzwerk geroutet wurden, zusammenhängt. Dann wird aus diesen Wegen ein Weg ausgewählt, der sowohl 1) Kosten unter einer Schwelle als auch 2) Strecken mit ausreichender Kapazität zur Ermöglichung der Anforderung aufweist. Das erfindungsgemäße Verfahren kann entweder in zentralisierten oder verteilten Systemen verwendet werden und kann zum Routen entweder permanenter oder vermittelter virtueller Leitungen bekannter oder unbekannter Haltezeiten dienen.

Kurze Beschreibung der Zeichnungen

Andere Merkmale und Vorteile der Erfindung werden aus der folgenden ausführlichen Beschreibung in Verbindung mit den Zeichnungen deutlich. Es zeigen:
Fig. 1 ein zentralisiertes Wegelenknetz, in dem die Erfindung ausgeübt werden kann.
Fig. 2 ein Flußdiagramm von Schritten in dem erfindungsgemäßen Verfahren, das in dem Netzwerk von Fig. 1 verwendet wird.
Fig. 3 ein Flußdiagramm von Schritten bei dem erfindungsgemäßen Verfahren zur Bestimmung einer Menge von Wegen, auf denen eine angeforderte VC geroutet werden kann.
Fig. 4 ein verteiltes Wegelenknetz, in dem die Erfindung ausgeübt werden kann.
Fig. 5 ein Flußdiagramm von Schritten in dem erfindungsgemäßen Verfahren, das mit dem Netzwerk von Fig. 4 verwendet wird.

Ausführliche Beschreibung

Fig. 1 zeigt die Struktur des Netzwerkes 106, in dem die Erfindung ausgeübt werden kann. Endpunkte 102- i, i = 1, 2, ... ., tauschen Informationen über das Netzwerk 106 aus. Das Netzwerk 106 umfaßt Strecken 110- k, k = 1, 2, ... ., die Knoten 108-j, j = 1, 2, ... . miteinander und mit den Endknoten 102-i verbinden. Zwei Knoten können durch eine oder mehrere Strecken verbunden werden.
Das Netzwerk 106 in Fig. 1 ist insofern ein zentralisiertes Wegelenksystem, als das Netzwerk 106 vollständige Informationen zur Wegelenkung durch Verwendung des zentralisierten Wegelenkanforderungsprozessors 111 ausnutzt. Der Anforderungsprozessor 111 ist mit den Knoten 108-j verbunden. Da alle Anforderungen von VCs in dem Anforderungsprozessor 111 verarbeitet werden, hat der Anforderungsprozessor 111 vollständige Kenntnis über den Netzwerkzustand, z. B. bestimmt der Anforderungsprozessor die Ausnutzung der Kapazität jeder Strecke und den in dem Puffer in jedem Knoten im Netzwerk verfügbaren Pufferplatz. Die Kosten für einen beliebigen Weg (d. h. die für einen beliebigen Weg erforderlichen zusätzlichen Netzbetriebsmittel) durch das Netzwerk können also genau bestimmt werden.
Fig. 2 zeigt Schritte in dem erfindungsgemäßen Verfahren zum Routen von VCs durch ein Netzwerk, wobei das Verfahren vorteilhafterweise von dem Anforderungsprozessor 111 benutzt werden kann. Im Schritt 210 wird eine (als die j-te Anforderung identifizierte) Anforderung einer VC von einem Ursprungs-Endpunkt empfangen. Die Anforderung umfaßt in der Regel Parameter, die einen Ursprungsknoten (sj), einen Zielknoten (tj), eine angeforderte Bandbreite (rj), eine Startzeit für die VC (Tsj) und eine Endzeit für die VC (Tfj) spezifizieren. Die Anforderung wird als (sj, tj, rj, Tsj, Tfj) spezifiziert. Schritt 220 beschreibt das erfindungsgemäße Verfahren zur Bestimmung einer Menge von Wegen, auf denen die angeforderte VC geroutet werden kann. Wie im Schritt 220 angegeben, wird die Menge von Wegen gemäß einem ersten Kriterium bestimmt, d. h. so, daß die Kosten jedes Weges in der Menge von Wegen unter einer Schwelle liegt, und so, daß jede der Strecken und jeder der Knoten in jedem Weg in der Menge von Wegen ausreichend verfügbare Betriebsmittel zur Ermöglichung der Anforderung aufweist.
Fig. 3 zeigt den Schritt 220 ausführlicher. Im Schritt 310 wird die Auslastung λ auf jeder Strecke e in dem Netzwerk 106 zum Zeitpunkt τ (Tsj ≤ τ ≤ Tfj) vorteilhafterweise unter Verwendung der obigen Gleichung (1) bestimmt. In Schritt 320 werden die Kosten für das Routen der j-ten Anforderung über jede Strecke e in dem Netzwerk zum Zeitpunkt τ gemäß einer modifizierten Kostenfunktion c'e(τ, j) bestimmt:
(3) τ, e E : für(λe(τ, j) + rj/u(e)) ≥ 1 gilt c'e(τ, j) ← ∞ oder c'e(τ, j) ← ce(τ, j)
wobei ce(τ, j) vorteilhafterweise unter Verwendung der obigen Gleichung (2) bestimmt wird. In Gleichung (2) prüft das Verfahren, ob die Kapazität der Strecke e überschritten wird, wenn die j-te Anforderung durch diese Strecke geroutet wird. Wenn die Kapazität überschritten wird, werden die Kosten auf eine sehr hohe Zahl gesetzt, sodaß das Verfahren nicht einen diese Strecke umfassenden Weg als Weg, auf dem die Anforderung geroutet werden kann, auswählt. Wenn die Kapazität auf der Strecke e nicht überschritten wird, wird die Kostenfunktion vorteilhafterweise unter Verwendung von Gleichung (2) berechnet. Die Kostenfunktion bei dem erfindungsgemäßen Verfahren ist wie bei dem AAP-Verfahren vorteilhafterweise eine nicht lineare Funktion, die so ausgelegt ist, daß ein Kompromiß zwischen der Zulassung zu einem Netzwerk auf der Grundlage von Wegen, die eine große Anzahl wenig oder mäßig ausgenutzter Strecken umfassen, und einer kleinen Anzahl relativ stark benutzter Strecken stattfindet. Wie nachfolgend beschrieben, wird der bei der Bestimmung von ce(τ, j) bei dem erfindungsgemäßen Verfahren verwendete Parameter u jedoch auf der Grundlage von anderen Parametern als bei dem AAP- Verfahren ausgewählt. Im Schritt 330 werden mögliche Wege zwischen dem Ursprungs- und Zielknoten in dem Netzwerk, eine Menge von Wegen, bei der die Kosten des Routens der Anforderung während der Haltezeit der angeforderten VC unter einer Schwelle liegen, identifiziert. Diese Wege werden als potentielle Wegelenkwege bezeichnet. Im Schritt 340 werden Strecken in jedem entsprechenden potentiellen Wegelenkweg geprüft, um sicherzustellen, daß die Strecken ausreichend verfügbare Kapazität zur Ermöglichung der angeforderten VC aufweisen (d. h. um sicherzustellen, daß die Strecke nicht "gesättigt" wird). Diejenigen potentiellen Wegelenkwege, deren Strecken für die Dauer der Haltezeit der angeforderten VC aus der Menge von Wegelenkwegen im Schritt 220 ausreichend Kapazität aufweisen.
Man beachte, daß die Prozedur im Schritt 120 durch Variieren der Reihenfolge der Schritte in Fig. 3 erreicht werden kann. Wenn zum Beispiel die Auslastung die Strecken zuerst bestimmt wird, kann das Verfahren dann die Strecken mit unzureichender Kapazität zur Abwicklung der Anforderung aus der Betrachtung beseitigen. Auf der Grundlage der übrigen Strecken können dann potentielle Wege zwischen den Ursprungs- und Zielknoten bestimmt werden, und dann können die Kosten des Routens über die potentiellen Wege bestimmt werden. Die potentiellen Wege mit ausreichend niedrigen Kosten bilden dann die Menge von Wegelenkwegen.
Wieder mit Bezug auf Fig. 2 wird im Schritt 225 die Menge von Wegelenkwegen untersucht. Wenn die im Schritt 220 bestimmte Menge von Wegelenkwegen eine leere Menge ist, wird die Anforderung im Schritt 230 zurückgewiesen. Wenn die Menge von Wegelenkwegen dagegen nicht leer ist, wird im Schritt 240 aus der Menge von Wegelenkwegen gemäß einem Auswahlkriterium ein Weg ausgewählt, auf dem die angeforderte VC geroutet wird.
Das Auswahlkriterium im Schritt 240 wird vorteilhafterweise als der Minimalsprungweg gewählt, d. h. der Weg, der durch die kleinste Anzahl von Knoten verläuft. Für Fachleute ist erkennbar, daß andere Kriterien verwendet werden können, z. B. kann das Kriterium darin bestehen, den Weg mit den geringsten Kosten auszuwählen.
Im Schritt 250 wird die angeforderte VC auf dem gewählten Weg geroutet. Im Schritt 260 aktualisiert der Anforderungsprozessor 111 den Netzwerkzustand, um die Benutzung von Netzbetriebsmitteln durch die geroutete VC wiederzugeben.
Obwohl das erfindungsgemäße Verfahren mit dem auf exponentiellen Kosten basierenden Algorhithmus von Awerbuch et al., supra, verwandt ist, verbessert das erfindungsgemäße Verfahren das AAP-Verfahren auf mehrere Weisen. Erstens verwendet das erfindungsgemäße Verfahren andere Parameter zur Bestimmung des Wertes von u, der in Gleichung (2) verwendet werden soll. Genauer gesagt ist der Parameter u eine Funktion der Anzahl von Sprüngen (d. h. der Anzahl von Strecken in einem Weg) für eine Teilmenge der Menge aller VCs, die zuvor durch das Netzwerk geroutet wurden. Im allgemeinen wird u vorteilhafterweise als Funktion von L gewählt, wobei L die mittlere Anzahl von Sprüngen oder Strecken einer Teilmenge der Menge aller VCs, die zuvor durch das Netzwerk geroutet wurden, ist. Zum Beispiel ist eine Auswahl dergestalt, daß log u eine Funktion von L ist, wie zum Beispiel log u in der Größenordnung von log L. In der Regel liegt u ungefähr zwischen 2 und 4. Also wird der Wert von u in der Regel von seinem Wert gemäß dem AAP-Verfahren reduziert. Ein reduzierter Wert von u führt wiederum dazu, daß das erfindungsgemäße Verfahren in der Regel eine größere Menge potentieller Wegelenkwege erzeugt, auf denen eine angeforderte VC geroutet werden kann. Also ist das erfindungsgemäße Verfahren nicht zu vorsichtig bei der Erzeugung einer Menge potentieller Wegelenkwege. Das erfindungsgemäße Verfahren kann jedoch, indem es weniger vorsichtig ist, in der Menge potentieller Wegelenkwege einige Wege enthalten, die Strecken umfassen, die nicht genug Kapazität zur Abwicklung der Anforderung aufweisen. Im Gegensatz zu dem AAP- Verfahren wählt das erfindungsgemäße Verfahren folglich aus der Menge potentieller Wegelenkwege nur die Wege mit Strecken aus, die genug Kapazität zur Ermöglichung der Anforderung aufweisen. Diese Wege umfassen dann die Menge von Wegelenkwegen im Schritt 220 von Fig. 2. Außerdem verwendet das erfindungsgemäße Verfahren im Gegensatz zu dem AAP-Verfahren vorteilhafterweise ein Auswahlkriterium zur Auswahl eines Weges, auf dem die Anforderung geroutet werden soll. Das erfindungsgemäße Verfahren findet somit eine Menge von Wegelenkwegen, die ein Anfangskriterium erfüllt, z. B. wobei jeder Weg in der Menge von Wegelenkwegen die angeforderte VC mit Kosten routen könnte, die unter einer bestimmten Kostenschwelle liegen. Das Verfahren wählt dann vorteilhafterweise einen Weg aus der Menge auf der Grundlage eines Auswahlkriteriums aus, z. B. den Minimalsprungweg. Man beachte, daß das erfindungsgemäße Verfahren für jeden beliebigen Wert von u legale Wegelenkentscheidungen produziert (d. h. es wird immer ausreichend Kapazität zur Ermöglichung der Anforderung geben). Das erfindungsgemäße Verfahren führt somit im Gegensatz zu dem AAP-Verfahren sowohl die Zulassungssteuerung als auch die Wegelenkaufgabe durch.
Schließlich sollte beachtet werden, daß das erfindungsgemäße Verfahren in Fällen verwendet werden kann, in denen die Dauer oder Haltezeit einer angeforderten VC nicht bekannt ist. Zum Beispiel nimmt das erfindungsgemäße Verfahren sowohl in zentralisierten als auch in verteilten Netzwerken vorteilhafterweise an, daß die Dauer der virtuellen Leitung im voraus bekannt ist. Obwohl dies für viele Anwendungen, wie zum Beispiel Spielfilme, eine vernünftige Annahme ist, gibt es eine große Klasse von Anwendungen, wie zum Beispiel Ferngespräche, für die dies keine vernünftige Annahme ist. Es sind jedoch für viele Anwendungen, bei denen die Dauer nicht im voraus bekannt ist, statistische Beschreibungen der Dauer verfügbar. Telefongespräche sind ein gutes Beispiel, und die statistischen Dauerinformationen über die durch angeforderte virtuelle Leitungen zu führenden Ferngespräche können bei Wegelenk- und Zulassungssteuerentscheidungen verwendet werden. Ähnlich kann das erfindungsgemäße Verfahren zum Routen permanenter VCs verwendet werden, indem der Parameter Tfj in der Anforderung der VC auf eine große Zahl gesetzt wird, oder indem die Zeitsummierung in dem Kode von Tabelle 1 entfernt wird.
Das erfindungsgemäße Verfahren kann auch in Systemen verwendet werden, in denen lokale (dezentralisierte) Wegelenkentscheidungen, anstatt zentralisierte Wegelenkentscheidungen, getroffen werden. Mehrere Betrachtungen motivieren die Verwendung eines dezentralisierten Systemes. Erstens kommt es bei einem zentralisierten Wegelenkschema wahrscheinlicher zu Zuverlässigkeitsproblemen als bei einem dezentralisierten System, da ein zentralisiertes Wegelenksystem einen einzigen Ausfallpunkt (d. h. den Anforderungsprozessor) aufweist. Zweitens haben zentralisierte Wegelenksysteme in der Regel Schwierigkeiten beim Betrieb oder bei der Kommunikation mit anderen zentralisierten Wegelenksystemen, da jedes der Systeme in der Regel keine Informationen über den Zustand des anderen Systemes besitzt. Somit sind zusätzliche Protokolle zur Arbitrierung und Kommunikation zwischen zentralisierten Netzwerken erforderlich. Da jeder Knoten in einem zentralisierten Wegelenksystem zuerst mit einer Einrichtung (wie zum Beispiel dem Anforderungsprozessor 111 von Fig. 1) kommunizieren muß, vergrößert die Ausbreitungsverzögerung für die Kommunikation mit einer solchen Einrichtung die Aufbauzeit zur Herstellung einer VC über die in der Regel in verteilten Systemen erforderliche Aufbauzeit hinaus.
Fig. 4 zeigt die Struktur eines verteilten Netzwerkes 416 mit Knoten 418-m und Strecken 420-n, in dem das erfindungsgemäße Verfahren ausgeübt werden kann. Das Netzwerk 416 ist insofern ein verteiltes Wegelenksystem, als jeder Knoten 418-m periodisch Zustandsinformationen mit benachbarten Knoten austauscht. Die Zustandsinformationen geben wieder, wieviel Netzbetriebsmittel auf einer Strecke von einem Knoten zu jedem benachbarten Knoten verfügbar oder benutzt sind. Somit können die Kosten für einen beliebigen Weg durch das Netzwerk durch einen Knoten bestimmt werden. Solange sich die Zustandsinformationen nicht relativ zu der Geschwindigkeit, mit der VCs hergestellt und abgebaut werden, schnell ausbreiten, sind die Informationen jedoch unvollständig (z. B. veraltet). Also kann jeder Knoten eine verschiedene Beschreibung oder lokale Ansicht des Netzwerkzustandes besitzen. Diese Beschreibung wird als der lokale Netzwerkzustand bezeichnet.
Fig. 5 zeigt ein Flußdiagramm zur Verwendung des erfindungsgemäßen Verfahrens in einem verteilten Wegelenksystem, in dem unvollständige Zustandsinformationen verwendet werden. In dem System und Verfahren von Fig. 4 und 5 hält jeder Knoten eine lokale Ansicht des Netzwerkzustandes aufrecht. Diese Ansicht wird aus dem Zustand der mit jedem Knoten verbundenen Strecken und aus Informationen bezüglich anderer Strecken, die auf nachfolgend beschriebene Weise während des VC-Aufbaus gesammelt werden, konstruiert. Wenn eine Anforderung einer virtuellen Leitung ankommt, wird das erfindungsgemäße Verfahren aufgerufen. Auf der Grundlage lokaler Informationen wird das erfindungsgemäße Verfahren die Anforderung entweder zurückweisen oder einen Weg auswählen, und in diesem Fall wird versucht, den gewählten Weg zum Routen der Leitung zu verwenden. Während versucht wird, die Anforderung zu routen, sammelt das erfindungsgemäße Verfahren vorteilhafterweise Zustandsinformationen für Strecken und Knoten entlang dem gewählten Weg. Diese gesammelten Zustandsinformationen sind in bezug auf die Betriebsmittel, die in jedem Knoten und jeder Strecke entlang dem Weg verwendet werden, genau. Also kann man mit den gesammelten Zustandsinformationen den lokalen Netzwerkzustand im Ursprungsknoten aktualisieren. Die Zustandsinformationen können vorteilhafterweise in Zeichengabenachrichten integriert werden, die während eines VC-Aufbaus verwendet werden, sodaß das Overhead verringert wird.
Nunmehr mit Bezug auf Fig. 5 wird im Schritt 505 ein Zähler, mit dem die Anzahl von Versuchen, eine Anforderung zu routen, begrenzt wird, zum Beispiel auf Null initialisiert. Im Schritt 510 wird eine Anforderung einer VC vorteilhafterweise in einem Ursprungsknoten von einem Ursprungsendpunkt in dem Netzwerk von Fig. 4 empfangen. Wie zuvor kann die Anforderung als (sj, tj, rj, Tsj, Tfj) mit den oben definierten Anforderungsparametern spezifiziert werden. Im Schritt 515 dient das erfindungsgemäße Verfahren zur Bestimmung einer Menge von Wegelenkwegen, auf denen die angeforderte VC geroutet werden kann. Die Operation des Schrittes 515 gleicht der Operation des Schrittes 220 in Fig. 2, mit der Ausnahme, daß die Kosten für jeden Weg auf der Grundlage des lokalen Netzwerkzustandes des Ursprungsknotens bestimmt werden. Wenn die Menge von Wegelenkwegen leer ist, wird die Anforderung zurückgewiesen (Schritte 520 und 525). Wenn die Menge von Wegelenkwegen jedoch nicht leer ist, wird im Schritt 530 gemäß einem zweiten Kriterium ein Weg aus der Menge ausgewählt. Das zweite Kriterium ist vorteilhafterweise wie bei dem in Fig. 2 beschriebenen Verfahren der Minimalsprungweg. Für Fachleute ist jedoch erkennbar, daß andere Kriterien (z. B. der Weg geringster Kosten) verwendet werden können.
Im Schritt 535 versucht das erfindungsgemäße Verfahren, die Anforderung auf dem gewählten Weg zu routen, d. h. es werden entsprechende VC- Aufbauprotokolle aufgerufen. Beim Aufruf der VC- Aufbauprotokolle kann das erfindungsgemäße Verfahren vorteilhafterweise exakte Informationen über den Status der Strecke und Knoten entlang dem gewählten Weg erhalten. Kurz gefaßt, weiß das erfindungsgemäße Verfahren genau, mit welcher Kapazität der Bandbreite und des Pufferraumes die Strecken und Knoten entlang dem gewählten Weg arbeiten. Das erfindungsgemäße Verfahren kann dann vorteilhafterweise und wahlweise den lokalen Netzwerkzustand im Ursprungsknoten aktualisieren (Schritt 540) und auch in den anderen Knoten entlang dem gewählten Weg (Schritt 545).
Im Schritt 550 prüft das erfindungsgemäße Verfahren, ob das Routen erfolgreich war. Im Gegensatz zu dem zentralisierten System von Fig. 2 besteht keine Garantie, daß das Routen in dem Verfahren von Fig. 5 erfolgreich ist. Der Grund dafür besteht darin, daß der gewählte Weg auf der Grundlage eines lokalen Netzwerkzustandes gewählt wurde. Also werden möglicherweise andere Netzbetriebsmittel, die in anderen Knoten und Strecken zugeteilt wurden, in dem lokalen Netzwerkzustand nicht wiedergegeben. Betriebsmittel, von denen auf der Grundlage des lokalen Zustandes erwartet wurde, daß sie verfügbar sind, sind folglich möglicherweise tatsächlich nicht verfügbar, und in diesem Fall ist das Routen nicht erfolgreich. Wenn das Routen erfolgreich war, endet das Verfahren. Wenn das Routen nicht erfolgreich war, wird der Zähler im Schritt 555 erhöht. Wenn der Zähler seine Grenze überschritten hat (auf der Grundlage einer zulässigen Anzahl von Versuchen beim Versuch, VC zu routen), wird die Anforderung schließlich zurückgewiesen. Wenn der Zähler seine Grenze nicht überschritten hat, kann das Verfahren dann entweder zum Schritt 515 zurückkehren (über den Verbinder 1 in Fig. 5) und eine weitere Menge von Wegelenkwegen finden und weiter nachfolgende Schritte in dem Flußdiagramm ausführen, oder alternativ zu dem Schritt 527 gehen (über den Verbinder 1' in Fig. 5). Im Schritt 527 wird aus der zuvor bestimmten Menge von Wegelenkwegen ein neuer und anderer Weg ausgewählt, und das Verfahren versucht dann, in den Schritten 535-560 auf dem neugewählten Weg zu routen.
Man beachte, daß das VC-Aufbauprotokoll vorteilhafterweise ein Bestätigungspaket benutzen kann, um den Ursprungsknoten darüber zu informieren, ob die Leitung tatsächlich geroutet wurde oder nicht, und um die aktuellen Zustandsinformationen jeder Strecke entlang dem Weg der Leitung zu sammeln. Mit diesen aktuellen Zustandsinformationen wird die lokale Ansicht des Netzwerkes im Ursprungsknoten aktualisiert. Wenn das Bestätigungspaket angegeben hat, daß die Leitung aufgrund unzureichender verfügbarer Kapazität nicht geroutet wurde, versucht das Verfahren die Leitung nochmals so zu routen, als ob sie eine neue Anforderung wäre.
Das hier offengelegte Verfahren wurde ohne Bezugnahme auf spezifische Hardware oder Software beschrieben. Stattdessen wurde das Verfahren so beschrieben, daß Fachleute solche Hardware und Software, die für bestimmte Anwendungen verfügbar oder vorzuziehen sein kann, ohne weiteres anpassen können. Um die Anwendbarkeit des erfingungsgemäßen Verfahrens auf vielfältige Systemumgebungen sicherzustellen, enthält das erfindungsgemäße Verfahren außerdem nicht unbedingt jede beliebige Art von periodischem Zustandsinformationsaustausch zwischen Knoten, obwohl solche Austausche vorgenommen und in das erfindungsgemäße Verfahren integriert werden können.

Claims

1. Verfahren zum Betrieb eines Netzwerks mit einer Menge von Knoten (102-1-102-6, 108-1-108-5), die durch eine Menge von Strecken (110-1-110-12) verbunden sind, wobei das Netzwerk einen Netzwerkzustand aufweist und eine Menge von virtuellen Leitungen zuvor durch das Netzwerk hindurch geroutet wurde, mit den folgenden Schritten:

Empfangen (210) einer Anforderung, eine virtuelle Leitung auf einem Weg durch das Netzwerk zwischen einem Ursprungsknoten und einem Zielknoten zu routen,

Bestimmen (310) der Auslastung auf jeder Strecke in einer Teilmenge der Menge von Strecken in dem Netzwerk aufgrund der Anforderung und

Bestimmen (320) jeweiliger Kosten für das Routen der Anforderung über mögliche Wege zwischen dem Ursprungsknoten und dem Zielknoten, wobei die Kosten Funktion des Netzwerkzustands sind, wobei die möglichen Wege Strecken in der Teilmenge der Menge von Strecken umfassen;

dadurch gekennzeichnet, daß der Schritt des Bestimmens von Kosten für das Routen für jeden möglichen Weg die folgenden Schritte umfaßt:

(a) Erhalten einer Zahl L, die teilweise durch Zählen der Strecken in mindestens bestimmten der virtuellen Leitungen, die bereits geroutet worden sind, abgeleitet wird;

(b) Verwenden von L zum Bestimmen des Werts eines Streckenkostenparameters u; und

(c) Auswerten eines jeweiligen Kostenfaktors für jede Strecke des aktuellen Weges, wobei der Kostenfaktor eine Funktion von u ist.

2. Verfahren nach Anspruch 1, wobei jeder Knoten in der Menge von Knoten und jede Strecke in der Menge von Strecken zugeordnete Betriebsmittel aufweist, und mit den folgenden Schritten:

Wählen (330), als potentielle Wege in einer Menge von potentiellen Wegen für das Routen, derjenigen möglichen Wege, deren jeweilige Kosten unter einer Schwelle liegen, und

Wählen (340), als Wege für das Routen in einer Menge von Wegen für das Routen, derjenigen potentiellen Wege für das Routen, die Knoten und Strecken mit genug zugeordneten Betriebsmitteln zum Routen der Anforderung besitzen.

3. Verfahren nach Anspruch 2, mit dem Schritt des Wählens (240) eines Weges aus der Menge von Wegen für das Routen gemäß einem Kriterium.

4. Verfahren nach Anspruch 3, wobei das Kriterium ein Minimal-Sprung-Kriterium für das Routen ist.

5. Verfahren nach Anspruch 3, wobei das Netzwerk ein zentralisiertes Netzwerk ist.

6. Verfahren nach Anspruch 3, wobei die Anforderung in einem Anforderungsprozessor empfangen wird.

7. Verfahren nach Anspruch 3, mit den folgenden Schritten:

Routen (250) der Anforderung auf dem gewählten Weg und

Aktualisieren (260) des Netzwerkzustands auf der Grundlage des gerouteten gewählten Weges.

8. Verfahren nach Anspruch 3, wobei die Anforderung in dem Ursprungsknoten empfangen wird, der Netzwerkzustand ein lokaler Netzwerkzustand in dem Ursprungsknoten ist und das Netzwerk ein dezentralisiertes Netzwerk ist.

9. Verfahren nach Anspruch 8, mit dem Schritt des Bestimmens (515), ob in Knoten und Strecken des gewählten Weges genug Betriebsmittel zum Routen der Anforderung verfügbar sind, wobei das Bestimmen auf lokalen Zustandsinformationen in Knoten längs des gewählten Weges basiert.

10. Verfahren nach Anspruch 9, mit dem Schritt des Aktualisierens (540) von lokalen Zustandsinformationen in dem Ursprungsknoten auf der Grundlage von lokalen Informationen in Knoten längs des gewählten Weges.

11. Verfahren nach Anspruch 9, mit dem Schritt des Aktualisierens (545) von lokalen Zustandsinformationen in einem Knoten längs des gewählten Weges auf der Grundlage von lokalen Informationen in anderen Knoten längs des gewählten Weges.

12. Verfahren nach Anspruch 9, mit den folgenden Schritten: Routen der Anforderung auf dem gewählten Weg, wenn genug Betriebsmittel verfügbar sind, und

Bestimmen einer anderen Menge von Wegen für das Routen, wenn nicht genug Betriebsmittel verfügbar sind.

13. Verfahren nach Anspruch 9, mit den folgenden Schritten:

Routen der Anforderung auf dem gewählten Weg, wenn genug Betriebsmittel verfügbar sind, und

Wählen (527) eines anderen Weges für das Routen aus der Menge von Wegen für das Routen, wenn nicht genug Betriebsmittel verfügbar sind.

14. Verfahren nach Anspruch 1, wobei die Anforderung einer virtuellen Leitung eine Anforderung einer vermittelten virtuellen Leitung ist und die Anforderung eine Belegungsdauer für die angeforderte virtuelle Leitung angibt.

15. Verfahren nach Anspruch 14, wobei die Kostenfunktion Funktion der Belegungsdauer für die angeforderte virtuelle Leitung ist.