DE69427618T2

DE69427618T2 - Verfahren für Kürzeststreckenweglenkung

Info

Publication number: DE69427618T2
Application number: DE69427618T
Authority: DE
Inventors: Kajamalai Gopalaswamy Ramakrishnan; Manoel Alberto Rodrigues
Original assignee: AT&T Corp
Current assignee: AT&T Corp
Priority date: 1993-06-28
Filing date: 1994-06-15
Publication date: 2002-05-29
Anticipated expiration: 2014-06-16
Also published as: EP0631413A3; US5596719A; EP0631413A2; DE69427618D1; JP3115769B2; EP0631413B1; CA2124974A1; CA2124974C; JPH07177143A

Description

Technisches Gebiet

Die Erfindung betrifft ein Verfahren und eine Vorrichtung zur verbesserten Wegelenkung in Datennetzen. Insbesondere beschreibt die Erfindung ein Verfahren und eine Vorrichtung zur Wegelenkung in Kürzester-Weg-Netzen, die eine zentralisierte Zuweisung von Streckenmetriken verwenden.

Allgemeiner Stand der Technik

1. Einführung

Computer- oder Datennetze, d. h. verbundene Ansammlungen autonomer Computer, liefern vielfältige Dienste, wie zum Beispiel Email und Datentransferdienste. Fig. 1 zeigt die Struktur eines typischen Computernetzes. Der erste Teil des Netzes umfaßt in der Regel eine Ansammlung von Maschinen 102, die als Hosts bezeichnet werden, auf denen Anwendungsprogramme ablaufen sollen. Das Netz enthält außerdem ein Kommunikationsteilnetz 104, das die Hosts verbindet. Die Aufgabe des Teilnetzes besteht darin, Nachrichten von Host zu Host zu führen. Das Teilnetz umfaßt in der Regel zwei grundlegende Komponenten: Router (die auch als Vermittlungselemente, Knoten oder Schnittstellennachrichtenprozessoren bezeichnet werden) 106 und Strecken (die auch als Übertragungsleitungen bezeichnet werden) 108. Jeder Host ist mit einem und manchmal mehreren Routern verbunden. Siehe im allgemeinen Andrew S. Tanenbaum, Computer Networks, Prentice Hall, Inc., Englewood Cliffs, NJ, 1981.
Die Rolle der Wegelenkung (Routing) besteht darin, für eine effiziente Ausnutzung von Netzdiensten und einen effizienten Datentransfer Wege zwischen Knoten des Netzes aufzubauen. Es gibt mehrere Klassen von Wegelenkungsproblemen, z. B. Wegelenkung in Netzen mit virtuellen Leitungen, Wegelenkung in Datagramm- Netzen und Wegelenkung in Kürzester-Weg-Netzen.

II. Klassen von Wegelenkungsproblemen in Datennetzen

A. Das allgemeine Wegelenkungsproblem

Es gibt sehr viel Literatur über das Problem der optimalen Wegelenkung in bezug auf eine gegebene Zielfunktion wie zum Beispiel die mittlere Verzögerung, unter Berücksichtigung bekannter Streckengeschwindigkeiten oder -kapazitäten und angebotenem Ursprung-Ziel- Verkehr (OD-Verkehr). Die meisten Bemühungen auf diesem Gebiet haben sich auf das allgemeine Wegelenkungsproblem konzentriert. D. G. Cantor und M. Gerla, "Optimal Routing in Packet Switched Computer Network", IEEE Transactions Computers, Band C-23, S. 1062-1069, Okt. 1974; Robert G. Gallager, "A Minimum Delay Routing Algorithm Using Distributed Computation", IEEE Transactions on Communications,. Band COM-25, Nr. 1, S. 73-85, Januar 1977; Thomas E. Stern, "A Class of Decentralized Routing Algorithms Using Relaxation", IEEE Transactions on Communications, Band COM-25, Nr. 10, S. 1092-1102, Oktober 1977. Eine grundlegende Annahme beim allgemeinen Wegelenkungsproblem besteht darin, daß der Fluß von einem Ursprung-Ziel-Paar (OD- Paar) (d. h. zwischen spezifischen Knoten in einem Netz) unter mehreren verschiedenen Wegen randomisiert werden kann, wodurch das Problem mathematisch angehbar wird, da die Flüsse auf Strecken zu kontinuierlichen Variablen werden. Obwohl das allgemeine Wegelenkungsproblem eine große Klasse von Flußproblemen darstellt, ist die Wegelenkung in Datennetzen in den meisten Fällen stärker eingeschränkt. Dessen ungeachtet ist die Lösung dieses Problems immer noch für eine große Klasse von Datennetzen nützlich, da sie eine Grenze bildet, d. h. keine Wegelenkstrategie kann besser als die Lösung des allgemeinen Wegelenkungsproblems arbeiten. Das allgemeine Wegelenkungsproblem besteht daraus, die beste Lösung für Flüsse in einem Netz zu finden, so daß die OD-Flußanforderungen und Kapazitätseinschränkungen erfüllt werden und die mittlere Netzverzögerung minimiert wird. Dieses Problem kann als ein nichtlineares Mehrfachrohstofflußproblem formuliert werden. H. Frank und W. Chou, "Routing in Computer Networks", Networks, Band 1, S. 99-122, 1971.

B. Das Datagramm-Wegelenkungsproblem

Das Problem der Datagramm-Wegelenkung ist angesichts der Vermehrung und des Wachstums verbindungsloser Datennetze (z. B. Internet) wichtig. Ein Datagramm-Netz besteht aus einer Menge von Hosts und einer Menge von Speicher-und-Weiterleitungs-Routern, die durch eine Menge von Strecken verbunden werden. Die Haupteigenschaft eines Datagramm-Netzes besteht darin, daß die Funktionen, die Wissen über eine "Sitzung" (z. B. Sitzungsdauer) oder Dienstanforderungen (z. B. zuverlässige Ablieferung von Paketen) erfordern, auf ein Ende-zu-Ende-Transportprotokoll relegiert werden, das zwischen den kommunizierenden Hosts eingerichtet wird. Dies hat die beiden Vorteile, daß Wegelenkentscheidungen knotenweise asynchron von den Vorgängen in einer Sitzung durchgeführt werden können, und daß der Wegelenkalgoritbmus verteilt sein kann. Auf jedem Router wird eine Funktion (Wegelenktabelle) benötigt, die ein ankommendes Paket einem abgehenden Port zuordnet, und ein Wegelenkalgorithmus, der die Wegelenktabelleneinträge so ausfüllt, daß die Ansammlung von Routern koordiniert arbeitet. Im Prinzip ist es möglich, die optimale Lösung für das allgemeine Wegelenkungsproblem in einem Routernetz zu erzielen. Es ist lediglich eine Funktion (Wegelenktabelle) erforderlich, die in der Lage ist, einen Eingangsfluß unter den abgehenden Ports paketweise zu randomisieren. In der Praxis ist die Wegelenktabelle jedoch eine deterministische Abbildung zwischen der Zieladresse des ankommenden Pakets und der Nummer des abgehenden Ports. Obwohl die Wegelenktabelle als Funktion der Zeit verändert werden kann, haben ihre Einträge ferner eine lange Lebenszeit. Diese praktischen Begrenzungen haben zwei wichtige Auswirkungen auf die Wegelenkung. Erstens übersetzt sich die deterministische Abbildung in eine Einzelweg-Wegelenkung: Dementsprechend kann der Fluß von einem Ursprungs-Ziel-Paar nicht unter mehreren Wegen randomisiert werden, was eine Einzelweg- Wegelenkung darstellt. Zweitens wird zur Bestimmung der Wegelenkung nur die Zieladresse verwendet. Sobald zwei Flüsse in Richtung eines gemeinsamen Ziels zusammenlaufen, können sie demzufolge danach nicht getrennt werden. Dies wird als zielgestützte Wegelenkung bezeichnet. Somit entspricht die Datagramm- Wegelenkung dem allgemeinen Wegelenkungsproblem mit den zusätzlichen Einschränkungen der Einzelweg-Wegelenkung und der zielgestützten Wegelenkung.

C. Das Kürzester-Weg-Wegelenkungsproblem

Das Konzept der Kürzester-Weg-Wegelenkung als ein verteilter Wegelenkalgorithmus ist eines der Ergebnisse des ARPANET-Projekts. Die Kürzester-Weg- Wegelenkung gleicht der Datagramm-Wegelenkung, wobei jedoch die zusätzliche Einschränkung besteht, daß alle Routen (d. h. Wegelenktabelleneinträge) auf der Grundlage einer "Abstands"-Metrik berechnet werden. In statischen oder quasistatischen Kürzester-Weg-Netzen (dynamische Wegelenkverfahren werden nicht betrachtet) wird eine "Abstands"- oder Streckenmetrik durch den Netzmanager jeder Strecke in dem Netz zugewiesen. Diese Streckenmetriken werden so zugewiesen, daß sich, durch ein Leistungsmaß bestimmt, eine gute Gesamt- Netzleistung ergibt. In manchen Fällen ist diese Metrikzuweisung verteilt, d. h. jeder Knoten weist seiner abgehenden Strecke eine Metrik zu. Die "Abstands"-Metriken werden dann unter allen Routern in dem Netz verteilt, und jeder Router berechnet die kürzesten Wege zu jedem anderen Router in dem Netz. Die resultierenden kürzesten Wege bestimmen die Wegelenktabelleneinträge. Die Kürzester-Weg-Einschränkung ist subtiler als die anderen und hat den Effekt, Einträge in der Wegelenktabelle zu "koppeln".
Es gibt zwei grundlegende Arten von Protokollen, die die Wegelenkinformationen in einem Netz von Routern verteilen: Streckenzustands- und Abstandsvektorprotokolle. Bei Streckenzustandsprotokollen tauschen die Router Informationen über die Topologie des Netzes selbst aus, darunter Informationen darüber, welche Strecken gerade betriebsfähig oder nicht betriebsfähig sind, und die jeder Strecke zugeordnete "Abstands"-Metrik. Siehe John Moy, "The OSPF Specification, Version 2", IETF Draft, Januar 1991; und ISO 10589 für detaillierte Informationen bezüglich verteilter Streckenzustandsprotokolle. Nachdem vollständige Informationen über die Netztopologie und Strecken-"Abstands"-Metriken empfangen wurden, berechnet jeder Router dann die kürzesten Wege zu jedem anderen Router in dem Netz. Somit enthalten die Wegelenktabellen aller Router in dem Netz Einträge, die in sich stimmig sind, und sie alle synthetisieren die Routen mit dem kürzesten Weg. Bei Abstandsvektorprotokollen tauschen die Router Information über den Abstand jedes anderen Knotens in dem Netz mit ihren Nachbarn aus. Die Wegelenkung in allen Routern in dem Netz konvergiert schließlich auf die Kürzester-Weg-Wegelenkung. Jeder Router erzielt dies dadurch, daß er eine Dreiecksungleichung zwischen seinen Abständen zu jedem Ziel und seinem Abstand zu jedem Nachbarn plus den Abstand des Nachbars zu jedem Ziel anwendet und immer den kürzesten Weg wählt.
Die Hauptvorteile der Kürzester-Weg-Wegelenkung in bezug auf die Datagramm-Wegelenkung bestehen darin, daß sie leichter zu verwalten ist und bei Ausfällen effektiver ist. Sie ist leichter zu verwalten, da der Netzmanager nur L (d. h. die Anzahl von Strecken in dem Netz) Werte verwalten muß, im Gegensatz zu N(N-1) Werten (d. h. die Anzahl von Routern mal die Anzahl von Einträgen auf jedem Router). Sie ist robuster gegenüber Konfigurationsfehlern, da, wenn der Netzmanager bei der Zuweisung einer "Abstands"-Metrik einen Fehler macht, die Wegelenkung in dem Netz möglicherweise nicht so optimal ist, wie sie sein könnte; wenn der Netzmanager andererseits bei der Zuweisung von Wegelenktabelleneinträgen einen Fehler macht, könnte sich dies sehr unterbrechend auf den Netzbetrieb auswirken (z. B. Schleifenbildung). Sie ist robuster bei Netzausfällen, da sie nicht von einem zentralisierten Eingriff abhängt, um Wegelenktabellen zu ändern; bei einem Netzkomponentenausfall (z. B. einem Strecken- oder Knotenausfall) werden die entsprechenden "Abstands"- Metriken auf unendlich gesetzt, und es werden automatisch neue kürzeste Wege berechnet, um die ausgefallenen Komponenten zu vermeiden.
Die bestehenden Verfahren zur Zuweisung von Streckenmetriken haben zwei Haupteigenschaften. Erstens ist die Zuweisung verteilt, d. h. jeder Knoten in dem Netz weist seiner abgehenden Strecke oder seinem abgehenden Datenweg die Streckenmetrik zu. Zweitens untersucht jeder Knoten die aktuelle Belastung in der Leitung, um eine Streckenmetrik zuzuweisen. Siehe J. M. McQuillan, G. Falk und I. Richter, "A Review of the Development and Performance of the ARPANET Routing Algorithm", IEEE Trans. Comm., S. 1802-1811, Dez. 1978; J. M. McQuillan, I. Rider und E. C. Rosen, "The New Routing Algorithm for the ARPANET", IEEE Trans. Comm., Band COM-28, Nr. 5, 711-719, Mai 1980; A. Khanna und J. Zinky, "The Revised ARPANET Routing Metric", Computer Comm. Review, SIGCOMM, Okt. 1989. Diese beiden Merkmale der derzeitigen Verfahren können jedoch zu Oszillationen in dem Netz führen, wodurch ein übermäßiges Overhead in dem Informationsaustausch zwischen Knoten und eine Suboptimalität bei der Netzleistung entstehen kann. Somit wird ein Verfahren zur Streckenmetrikzuweisung benötigt, das Netzoszillationen beseitigt, während eine zufriedenstellende Netzleistung bereitgestellt wird.

Kurze Darstellung der Erfindung

Die vorliegende Erfindung in typischer Ausführungsform betrifft ein Verfahren und eine Vorrichtung nach Anspruch 1 bzw. 7 zum Zuweisen von "Abstands"- oder Streckenmetriken in einem Kürzester- Weg-Wegelenknetz, durch die viele der Nachteile bisheriger Verfahren vermieden werden. Das Verfahren und die Vorrichtung weisen vorteilhafterweise Streckenmetriken auf eine zentralisierte Weise zu. Das Verfahren und die Vorrichtung weisen die Metriken so zu, daß die Netzleistung verbessert wird, z. B. die mittlere Netzverzögerung vermindert wird.

Kurze Beschreibung der Zeichnungen

Weitere Merkmale und Vorteile der Erfindung werden aus der folgenden ausführlichen Beschreibung in Verbindung mit den Zeichnungen deutlich. Es zeigen:
Fig. 1 ein Computernetz.
Fig. 2 eine Ausführungsform der Erfindung in einem Datennetz.
Fig. 3 die Schritte des Verfahrens zur Zuweisung von Abstandsmetriken zu Strecken in einem Netz.
Fig. 4 ein Beispiel für ein Datennetz.

Ausführliche Beschreibung

I. Übersicht

Fig. 2 zeigt eine beispielhafte Ausführungsform der Erfindung, bei der ein Netzmanagerprozessor 210 den Strecken in einem Kürzester-Weg-Wegelenkungs-Datennetz Abstands- oder Streckenmetriken zuweist. Das Datennetz, das Maschinen 202, ein Kommunikationsteilnetz 204, Router 206 und Strecken 208 umfaßt, gleicht dem in Fig. 1 gezeigten. Der Netzmanagerprozessor 210 verwendet eine quasistatische Streckenmetrikzuweisungsstrategie, bei der der Netzmanagerprozessor 210 zentral die Streckenmetrikzuweisungen bestimmt und Signale zu den Routern 206 sendet, die Informationen über die Zuweisungen enthalten. Insbesondere fragt der Netzmanagerprozessor 210 von den Routern 206 Informationen über Ursprungs-Ziel-Verkehr ab (d. h. Verkehr zwischen Paaren von Knoten in dem Netz). Der Netzmanagerprozessor 210 bestimmt dann erneut die Streckenmetriken für das Netz auf der Grundlage der Informationen und sendet Signale mit Informationen über die neu bestimmten Streckenmetriken zu den Routern 206. Abschnitt II zeigt eine Übersicht des allgemeinen Wegelenkungsproblems, das die Grundlage zur Charakterisierung und Messung der Leistung eines Kürzester-Weg- Wegelenkverfahrens bildet. Abschnitt III gibt eine ausführliche Beschreibung des vorgeschlagenen Verfahrens bzw. der vorgeschlagenen Vorrichtung zur Streckenmetrikzuweisung. Abschnitt IV zeigt die Verwendung des Verfahrens in einem Beispiel.

II. Das allgemeine Wegelenkungsproblem

A. Die N(N-1)-Rohstofformulierung

Das allgemeine Wegelenkungsproblem kann in Form eines nichtlinearen Mehrrohstoff-Flußproblems beschrieben werden. Es sei G = (N, L) ein verbundener gerichteter Graph mit der Knotenmenge N = {n&sub1;, n&sub2;, ..., nN} und der Streckenmenge L = {l&sub1;, l&sub2;,...,1L).., (4 und L bezeichnen die Kardinalitäten der Knotenmenge bzw. der Streckenmenge), wobei eine Inzidenzabbildung m : L → N · N besteht, die eine Strecke Li auf ein geordnetes Paar von Knoten m (li) = (fi1, ni2) abbildet. Eine Strecke wird austauschbar durch ihre Streckennummer 1 oder durch das geordnete Knotenpaar (oder Ursprungs-Ziel-Paar), das sie verbindet (n&sub1;, n&sub2;), identifiziert. Es sei C&sub1; die Kapazität der Strecke 1 L. Eine Eigenschaft typischer Graphen in Datennetzen besteht darin, daß eine gegebene gerichtete Strecke zwischen den Knoten nöl und nj2, es auch eine gerichtete Strecke in der entgegengesetzten Richtung (d. h. zwischen den Knoten ni2 und ni1) gibt. Es sei K = {k&sub1;, k&sub2;, ..., kx} die Menge von Rohstoffen, die durch dieses Netz geführt werden soll, die gewöhnlich gleich allen Ursprungs-Ziel-Paaren N(N-1) ist. Für jeden Rohstoff k K wird ein Paar von Knoten als das Ursprungs-Ziel-Paar (OD-Paar) mit dem erforderlichen Fluß λk dieses Rohstoffs ausgezeichnet. Es sei der Fluß für den Rohstoff k K durch die Strecke (i, j) L. Man nehme an, daß Pk die Menge aller einfachen Wege ist, die das OD-Paar verbinden. Dann kann eine mathematische Programmierungsformulierung für das allgemeine Wegelenkungsproblem in Form eines Mehrrohstoff-Flußproblems (MFP) folgendermaßen geschrieben werden:
Minimiere Z (f¹, f²,...,fk) (1) unter der Bedingung
wobei Z eine nichtlineare Zielfunktion von Flußvektoren fk = { (i,j) L} für Rohstoffe k K ist, H(i) = { (n,i) L} ist (Menge von Knoten, wobei Knoten i ein Nachbar ist), J(i) = {n N(i,n)L } (Menge von Knoten, die Nachbar des Knotens 1 sind) und (j) die Wegelenkungsvariable im Knoten i ist, die den Anteil des Flusses aus dem Rohstoff k bestimmt, der zu dem Nachbarn j gelenkt wird.
Die Netzleistung kann auf verschiedene Weise gemessen werden. Ein typisches Leistungsmaß kann auf Zielfunktionen basieren, deren Werte von den Flüssen nur durch den Gesamtfluß an jeder Strecke f&sub1; abhängen. Die Zielfunktion bzw. das Leistungsmaß ist gewöhnlich eine konvexe Funktion der Flüsse f&sub1;, wie zum Beispiel die mittlere Netzverzögerung:
wobei
Man beachte, daß, bei einer Summierung beider Seiten von (2) in bezug auf j J(i) und Einsetzen der Einschränkung (3) in die Gleichung, man die üblichen Flußerhaltungsgleichungen erhalten würde. H. Soroush und P. B. Mirchandani, "The Stochastic Multicommodity Flow Problem", Networks, Band 20, Nr. 2, S. 121-155, März 1990. Für einen gegebenen Knoten dEN und einen Rohstoff keK sollte die Differenz zwischen Bestand und Nachfrage nur dann von Null verschieden sein, wenn Knoten i entweder ein Ursprung (+λk) oder ein Ziel (-λk) des Rohstoffs k ist. Die Rolle der Einschränkung (3) besteht darin, genau anzugeben, wie Flüsse unter den Nachbarn des Knotens i aufgeteilt werden sollten. Obwohl sich diese zusätzliche Einschränkung nicht auf die Lösung des MFP auswirkt, ist sie eine wichtige Einschränkung, wenn das Problem mit zusätzlichen Einschränkungen betrachtet wird (z. B. der Einzelweg- Wegelenkung und der zielgestützten Wegelenkung).
Außerdem bestimmt eine Auf lösung auf (j) für alle i, j N die Flüsse fk für alle k K und umgekehrt.

B. Die N-Rohstoff-Formulierung

Eine effizientere Formulierung ergibt sich durch Verwendung einer zusätzlichen Einschränkung. Bei der vorliegenden neuen Formulierung entspricht jeder Rohstoff dem Fluß in Richtung des Zielknotens k. Diese zusätzliche Einschränkung soll hier als Einschränkung der zielgestützten Wegelenkung bezeichnet werden. Dieseneue Einschränkung kann folgendermaßen beschrieben werden: wenn zwei oder mehr Flüsse von einem beliebigen Ursprungsknoten, die in Richtung eines gemeinsamen Zielknotens k bestimmt sind, an einem Zwischenknoten i zusammenfließen, können diese Flüsse nicht unterschiedlich behandelt werden. Die neue Einschränkung kann in die obige Formulierung integriert werden, indem einfach gefordert wird, daß, wenn = gilt, (j) = (j), i N gilt. Es kann jedoch folgendermaßen eine komplaktere Formulierung erzielt werden. Als erstes wird der Rohstoffindex k dem Knotenindex k zugeordnet; d. h. es gibt N Rohstoffe in dem Netz. Als nächstes sei der erforderliche Fluß vom Knoten u zum Knoten k. Es sei der Fluß für den Rohstoff k K durch die Strecke 1 L. Danach kann die mathematische Programmierungsformulierung für das allgemeine Wegelenkungsproblem in Form eines N-Rohstoff-Mehrrohstoff-Flußproblems (MFP), N-Rohstoff, folgendermaßen geschrieben werden:
Minimiere Z(f&sub1;,f&sub2;, ...,f&sub2;) (7)
unter der Bedingung
wobei z eine nichtlineare Funktion der Flüsse f&sub1;, H(i) = {n N(n,i) L} und J(i) = {n N(i,n) L) ist.
Gleichung (8) ist die übliche Flußerhaltungseinschränkung in einem gegebenen Knoten i N für den Rohstoff k. Die Differenz zwischen Nachfrage und Bestand für einen gegebenen Rohstoff im Knoten i sollte gleich (-) dem aus dem Knoten i stammenden Fluß zum Knoten k (d. h. ) sein, oder, wenn i = k gilt (d. h. Knoten i ist der Zielknoten k), gleich dem Gesamtfluß für den Rohstoff k (d. h. ). Gleichung (9) ist die übliche Kapazitätseinschränkung in einer gegebenen Strecke 1. Die Summe aller Flüsse in einer gegebenen Strecke 1 muß kleiner als die Kapazität C&sub1; sein. Das wie oben formulierte Problem ist ein konvexes Programmierungsproblem mit linearer Einschränkung. Da die Zielfunktion konvex ist und der Raum machbarer Lösungen kompakt ist, existiert ein eindeutiges globales Minimum des Problems (7)-(10).
Man beachte, daß bei einer solchen Wahl der Zustandsvariablen (d. h. anstelle von wobei i den Ursprungsknoten bezeichnet) die zusätzliche Einschränkung der zielgestützten Wegelenkung in der Formulierung implizit ist. Für den Fall, daß Flüsse kontinuierliche Variablen sind, d. h. das allgemeine Wegelenkungsproblem, wirkt sich diese zusätzliche Einschränkung nicht auf die optimale Lösung aus und liefert eine einfachere Formulierung mit weniger Zustandsvariablen.

III. Das Kürzester-Weg-Wegelenkungsproblem

A. Übersicht

Wie oben besprochen, weist das Kürzester-Weg- Wegelenkungsproblem (SP-Wegelenkungsproblem) eine zielgestützte Wegelenkung auf. Im Gegensatz zu dem allgemeinen N-Rohstoff-Wegelenkungsproblem ist jedoch keine Randomisierung der Wegelenkung zulässig. Alle Daten von einer Quelle zu einem Ziel sollten demselben Weg folgen. Außerdem sollte der Weg, gemessen durch die Streckenmetriken, der kürzeste Weg zwischen dem Ursprungs- und dem Zielknoten sein.
Eine Formulierung des Kürzester-Weg-Wegelenkungsproblems in Form zusätzlicher Einschränkungen des allgemeinen N-Rohstoff-Wegelenkungsproblems ist schwierig. Eine notwendige Bedingung dafür, daß eine Lösung der Kürzester-Weg-Einschränkung entspricht, besteht darin, daß, wenn zwei Knoten (d. h. n&sub1; und n&sub2;) zu zwei (oder mehr) verschiedenen Wegen gehören (d. h. Weg a = i,..., n&sub1;,..., n&sub2;,..., j und Weg b = k,..., n&sub1;,..., n&sub2;,..., m), die beiden Wege (d.h. a und b) zwischen diesen beiden Knoten identisch sein müssen. Die Durchsetzung dieser neuen Einschränkung in einer Mehrrohstoff-Flußformulierung wäre jedoch schwierig, da das MFP über Wegvariablen umformuliert werden müßte, was zu einem bilinearen konvexen ganzzahligen Programm führen würde, dessen genaue Lösung bei großen Netzen sehr zeitaufwendig sein kann. Deshalb wird ein kombinatorischer Ansatz verwendet, um eine Näherungslösung zu erzielen.
Das Kürzester-Weg-Wegelenkungsproblem kann folgendermaßen formuliert werden: Definiere die Streckenmetriken für alle Strecken 1 L in bezug auf eine gegebene Menge von Anforderungen so, daß die resultierende Menge kürzester Wege die beste Gesamt- Netzleistung erzielt. Somit ist ein wesentliches Element des Problems die Zuweisung von Streckenmetriken.
Man betrachte den bereits definierten Graph G (N, L). Jeder Strecke 1 L sei eine reelle Zahl d&sub1; zugeordnet, die als der Abstandskoeffizient von 1 bezeichnet wird, und es sei D RL der Vektor (d&sub1;, d&sub2;, ..., dL). Es sei S die Menge des gesamten Flusses f, der durch die Lösung eines SP-Wegelenkungsverfahrens über die Werte D RL erzielbar ist. Hier ist die Menge machbarer Lösungen auf diejenigen Lösungen des MFP beschränkt, die im Abschnitt über das allgemeine Wegelenkungsproblem beschrieben werden, unter der Bedingung einer Einzelweg-Wegelenkung, der zielgestützten Wegelenkung und als Teilmenge von S.
Der Effekt der Kürzester-Weg-Wegelenkungseinschränkung besteht darin, daß eine Kopplung zwischen Wegen eingeführt wird. Diese Kopplung manifestiert sich zum Beispiel folgendermaßen: wenn sich zwei Wege an zwei Punkten überschneiden, müssen sie zwischen diesen beiden Punkten identisch sein. Die obige Eigenschaft kann als eine notwendige Bedingung für eine Menge von Routen betrachtet werden, die durch Kürzester-Weg-Algorithmen realisiert werden sollen (d. h. Längster-Weg- Algorithmen weisen diese Eigenschaft ebenfalls auf).

B. Ein Verfahren und eine Vorrichtung zum Zuweisen von Streckenmetriken

Fig. 3 zeigt die Schritte des Verfahrens zum Zuweisen von Streckenmetriken. Der Netzmanagerprozessor 110 in Fig. 2 kann dieses Verfahren vorteilhafterweise verwenden, um Signale mit Streckenmetrikzuweisungsinformationen zu Routern 206 zu senden. Die prinzipielle Idee des vorgeschlagenen Verfahrens besteht darin, eine lokale Suche in einer wohldefinierten Umgebung durchzuführen. Die hier betrachtete Umgebung ist die einer minimalen Routenänderung. Die Zielfunktion bzw. das Leistungsmaß ist die bzw. das von Gleichung (6).
Man betrachte einen Punkt P&sub0;, der eine Menge kürzester Wege bezeichnet, die aus einem gegebenen anfänglichen Abstandsstreckenmetrikvektor DOERL erhalten wird. Anfänglich können Abstandsstreckenmetrikwerte gewählt werden, die der Kehrwert der Streckenkapazität sind. Man definiere eine Umgebung oder eine Menge von Nachbarn von P&sub0; mit dem Namen divert folgendermaßen:
V(P&sub0;) = {P}, wobei {P} eine Menge von Punkten ist, wobei jeder Punkt eine Menge von kürzesten Wegen ist, so daß nur eine minimale Anzahl von Wegen in bezug auf P&sub0; als Folge einer Zunahme einer einzelnen Komponente von D&sub0; verändert wird.
Um lokal optimale Lösungen für einen Vorfall unseres Problems zu finden, definiere man die Funktion improve(P&sub0;) als die Funktion, die den Punkt oder Nachbarn in der Umgebung von P&sub0; zurückgibt, die die Zielfunktion bzw. das Leistungsmaß Z(f) am stärksten verbessert.
wobei f(Pi) dem Flußvektor entspricht, der sich aus der Berechnung von kürzesten Wegen Pi für den Streckenabstandszuweisungsvektor Di ergibt und Z(f(Pi)) die bei f(Pi) ausgewertete Zielfunktion ist.
Es wird der folgende Algorithmus zum Auffinden der lokal optimalen Lösung verwendet:
Man beachte, daß hier ein lokaler Suchalgorithmus über eine wohldefinierte Umgebung definiert wird. Somit bestehen die einzigen verbleibenden Schritte darin, tatsächlich die Umgebung und die Streckenabstandsmetrik zu finden, die jeden Punkt in der Umgebung realisiert.
Man betrachte eine bestimmte Strecke 1 und es sei pl die Menge von Urspruhgs-Ziel-Paaren (OD-Paaren), die Wege durch 1 aufweisen. Hier wird eine geeignete Zunahme des Abstands der Strecke 1 so gesucht, daß nur die minimale Anzahl von Wegen von der Strecke 1 umgelenkt wird. Dies wird erzielt, indem zunächst alle Wege, die durch diese Strecke verlaufen, umgelenkt werden (indem ihr Abstand auf unendlich gesetzt wird). Danach werden die OD-Paare in bezug auf die Differenz zwischen ihren Wegabständen nach und vor der Umlenkung aller Wege von der Strecke 1 in ansteigender Reihenfolge sortiert. Die Wege, bei denen die geringste Zunahme des Abstands auftrat, entsprechen den umzulenkenden, und die geeignete Zunahme δ¹ des Abstands der Strecke 1 ist ein beliebiger Wert, der größer als die kleinste Zunahme und die nächstkleinste Zunahme des Abstands ist, die bei diesen Wegen aufgetreten ist. Bei dem Verfahren kann typischerweise der Mittelpunkt zwischen diesen beiden Werten gewählt werden.
Man betrachte die Menge von OD-Paaren k p&sub1;. Es sei Δ die Differenz der Kosten zwischen dem kürzesten Weg für das OD-Paar k und dem neuen kürzesten Weg, nachdem die Strecke 1 aus dem Netz herausgenommen wurde. Somit entspricht ΔC dem Schwellenwert, bei dem, wenn die Kosten einer beliebigen Strecke, die zu dem kürzesten Weg des OD-Paars k gehört, um mehr als diesen Betrag vergrößert werden, garantiert ist, daß der kürzeste Weg aufhört, der kürzeste Weg zu sein. Dementsprechend gibt es für jede Strecke 1 ein OD-Paar (oder eine Menge von OD-Paaren) k dergestalt, daß Δ ≤ ΔCk k p&sub1;. Genauso gibt es ein anderes OD-Paar (oder eine andere Menge von OD-Paaren) k dergestalt, daß Δ ≤ ΔCk k p1 k≠k . Eine Zunahme der Streckenkosten in der Strecke 1 (ΔC¹), die ΔC , aber nicht ΔC überschreitet, würde somit die kleinste Anzahl umgelenkter kürzester Wege (d. h. einen Punkt in der Umgebung V) verursachen. Das heißt, bei dem Weg für das OD-Paar (oder die Menge von OD-Paaren) k werden ihre Wege umgelenkt.
Es kann gezeigt werden, daß das Verfahren in begrenzter Zeit konvergiert. Da es eine begrenzte Anzahl von Punkten P gibt, kann gezeigt werden, daß die Anzahl von Aufspannungsbäumen in dem Netz eine obere Grenze für die Kardinalität der Menge möglicher P ist. Das Verfahren besucht niemals einen Punkt P zweimal, da die Suche streng absteigend in Z(f) ist. Deshalb kann das Verfahren unmöglich mehr Iterationen als die Größe des Zustandsraums aufweisen, und somit konvergiert das Verfahren in begrenzter Zeit. Die Komplexität eines Schritts ist O( K L log N ) und wird durch die Komplexität des Findens der Umgebung V dominiert.
Da das SP-Wegelenkungsproblem NP-hart ist, ist nicht klar, ob das Verfahren mit seinem kombinatorischen Ansatz auf die global optimale Lösung konvergiert. Obwohl gezeigt werden kann, daß das Verfahren auf ein lokales Minimum konvergiert, kann nur abgeschätzt werden, wie gut das lokale Minimum ist. Für diese Abschätzung wird die folgende Strategie verwendet: löse das allgemeine N-Rohstoff- Wegelenkungsproblem und bestimme den Optimalwert der Netzleistung Z*. Es kann gezeigt werden, daß Z* eine untere Grenze für die optimale Netzleistung des SP- Wegelenkungsproblems ist. Man vergleiche somit Z* mit der Leistung Z der lokalen Minimallösung. Wenn die Differenz Z-Z* klein ist (d. h. kleiner als η), dann ist die Leistung zufriedenstellend. Wenn die Differenz groß ist, kann die Suche mit einem neuen Anfangspunkt wiederholt werden.

IV. Ein Beispiel

Die Prozedur zum Auffinden der Umgebung V wird mit einem Beispiel illustriert. Fig. 4 zeigt ein Netz mit fünf Knoten (A, B, C, D und E) und fünf Strecken (l&sub1;, l&sub2;, l&sub3;, l&sub4;, l&sub5;) mit jeweiligen Streckenkosten von D&sub0; = (1,5, 1,3, 2,4, 1,0, 1,0). Tabelle 1 zeigt alle OD-Paare, ihre Kürzester-Weg-Kosten und ihre Kürzester- Weg-Kosten, wenn jede einzelne der Strecken entfernt wird. Tabelle 2 zeigt alle Strecken, das OD-Paar k , das ΔC und das ΔC . Somit gibt es vier Nachbarn von P0, die sich jeweils aus Störungen von D&sub0; ergeben, nämlich (1,5 + ΔC¹, 1,3, 2,4, 1,0, 1,0), wobei 0,6 < ΔC¹ < 1,2,
(1,5, 1,3 + ΔC², 2,4, 1,0, 1,0), wobei 0,6 < ΔC² < 3,6, (1,5, 1,3, 2,4 + ΔC³, 1,0, 1,0), wobei 1,4 < ΔC³ < 2,8, (1,5, 1,3, 2,4, 1,0 + ΔC4, 1, 0), wobei 1,2 < ΔC&sup4; < 4,2 gilt. Obwohl die Streckenkosten eine kontinuierliche Variable sind, entsprechen alle Streckenkostenvektoren, die auf dieselbe Menge kürzester Wege abbilden, demselben diskreten Punkt in der Umgebung V. Man beachte, daß es keinen Nachbarn gibt, der sich aus einer Zunahme der 1&sub5;-Kosten ergibt, da von dort aus kein Weg umgelenkt werden kann (d. h. man wird zu einer Reduktion des Zustandsraums geführt).
Um zu entscheiden, welcher der vier Nachbarn gewählt werden soll, werte man die Zielfunktion an den vier Punkten aus und wähle denjenigen, der die größte Abnahme der Zielfunktion aufweist. Dies führt zu einer neuen Menge von Abstandsmetriken. Danach wiederhole man die obige Prozedur, bis die Zielfunktion sich nicht mehr verbessert (d. h. weniger als um einen Betrag &epsi; verbessert). An diesem Punkt wurde dann das lokale Minimum gefunden.
Die vorliegende Beschreibung betrifft ein Verfahren und eine Vorrichtung zur Streckenmetrikzuweisung in Kürzester-Weg-Netzen. Das Verfahren und die Vorrichtung wurden ohne Bezugnahme auf spezifische Hardware oder Software beschrieben. Stattdessen wurden das Verfahren und die Vorrichtung so beschrieben, daß Fachleute ohne weiteres solche Hardware und Software, die verfügbar oder für bestimmte Anwendungen vorzuziehen ist, anpassen können. Tabelle 1 Tabelle 2

Claims

1. Verfahren zum Zuweisen von Streckenmetriken in einem Netz, wobei das Netz durch Strecken verbundene Knoten umfaßt, mit den folgenden Schritten:

a. Zuweisen eines Anfangs-Streckenmetrikwerts zu jeder Strecke;

b. Bestimmen einer Anfangsmenge kürzester Wege zwischen jedem Knotenpaar in dem Netz;

c. Bestimmen der Anfangsleistung des Netzes mit den Anfangs-Streckenmetrikwerten gemäß einem Leistungsmaß;

d. Finden einer Umgebung für die Anfangsmenge kürzester Wege, wobei die Umgebung eine Menge von Nachbarn ist und wobei jeder Nachbar eine Menge kürzester Wege und zugeordneter Streckenmetriken ist, so daß als Folge einer Zunahme jeder Anfangs- Streckenmetrik nur eine minimale Anzahl von Wegen in bezug auf die Anfangsmenge kürzester Wege verändert wird;

e. Auswählen des Nachbars in der Umgebung, der gemäß einem Leistungsmaß die beste Leistung für das Netz ergibt; und

f. Zuweisen der dem ausgewählten Nachbar zugeordneten Streckenmetriken als Streckenmetriken für das Netz.

2. Verfahren nach Anspruch 1, wobei der Schritt des Findens einer Umgebung weiterhin die folgenden Schritte umfaßt:

a. für jede Strecke 1:

Bestimmen der kürzesten Wege zwischen jedem Knotenpaar bei herausgenommener Strecke 1;

Bestimmen einer Menge von Zunahmen des kürzesten Wegs über die Anfangsmenge von kürzesten Wegen;

Anordnen von Elementen der Menge von Zunahmen in aufsteigender Reihenfolge;

Definieren des Mittelwerts des ersten und zweiten positiven Minimalelements der Menge von Zunahmen als eine Perturbation für die Strecke 1;

Vergrößern der Streckenmetrik für die Strecke 1 um die Perturbation und Bestimmen einer neuen Menge von kürzesten Wegen;

Bestimmen der Leistung des Netzes gemäß dem Leistungsmaß für die neue Menge von kürzesten Wegen;

Rücksetzen der Streckenmetrik für die Strecke 1; und

b. Finden derjenigen Strecke, die die beste Leistung ergibt, und Vergrößern der Metrik der Strecke um die Perturbation für die Strecke.

3. Verfahren nach Anspruch 1, weiterhin mit dem Schritt des Sendens eines Signals zu den Knoten in dem Netz, wobei das Signal Informationen bezüglich der Streckenmetriken umfaßt.

4. Verfahren nach Anspruch 1, wobei die Anfangs- Streckenmetrik für jede Strecke in dem Netz anfänglich als der Kehrwert der Streckenkapazität für die Strecke gewählt wird.

5. Verfahren nach Anspruch 1, wobei das Leistungsmaß eine mittlere Netzverzögerung ist.

6. Verfahren nach Anspruch 1, wobei die Anfangs- Streckenmetrik auf einem über eine Zeitspanne hinweg gemessenen Maß von Verkehr zwischen Mengen von Knoten in dem Netz basiert.

7. System zum Zuweisen von Streckenmetriken in einem Netz, wobei das Netz durch Strecken (208) verbundene Knoten (202) umfaßt, wobei das System folgendes umfaßt:

a. ein Mittel (210) zum Zuweisen eines Anfangs- Streckenmetrikwerts zu jeder Strecke;

b. ein Mittel (210) zum Bestimmen einer Anfangsmenge kürzester Wege zwischen jedem Knotenpaar in dem Netz;

c. ein Mittel (210) zum Bestimmen der Anfangsleistung des Netzes mit den Anfangs- Streckenmetrikwerten gemäß einem Leistungsmaß;

d. ein Mittel (210) zum Finden einer Umgebung für die Anfangsmenge kürzester Wege, wobei die Umgebung eine Menge von Nachbarn ist und wobei jeder Nachbar eine Menge kürzester Wege und zugeordneter Streckenmetriken ist, so daß als Folge einer Zunahme jeder Anfangs-Streckenmetrik nur eine minimale Anzahl von Wegen in bezug auf die Anfangsmenge kürzester Wege verändert wird;

e. ein Mittel (210) zum Auswählen des Nachbars in der Umgebung, der gemäß einem Leistungsmaß die beste Leistung für das Netz ergibt; und

f. ein Mittel (210) zum Zuweisen der dem ausgewählten Nachbar zugeordneten Streckenmetriken als Streckenmetriken für das Netz.