DE60000396T2

DE60000396T2 - "multicommodity flow"-Verfahren zur Verteilung des Verkehrs in einem Packetnetz mit mehreren Diensten

Info

Publication number: DE60000396T2
Application number: DE60000396T
Authority: DE
Inventors: Mitra Debasis; Gopalaswamy Ramakris Kajamalai
Original assignee: Lucent Technologies Inc
Current assignee: Nokia of America Corp
Priority date: 1999-08-09
Filing date: 2000-07-31
Publication date: 2003-05-22
Anticipated expiration: 2020-08-01
Also published as: JP4567160B2; JP2001077848A; CA2314944C; EP1076472B1; DE60000396D1; US6721270B1; EP1076472A1; CA2314944A1

Description

Gebiet der Erfindung

Diese Erfindung betrifft Verfahren zur Verteilung von Verkehr unter Leitwegen in paketierten Kommunikationsnetzen.

Stand der Technik

Kommunikationsnetze befördern Informationen zwischen Endkommunikationsgeräten, wie Computerendgeräten, Telefonen, Telefaxmaschinen und Computerdatenservern. Ein typisches Netz enthält Vermittlungsknoten, wie die Knoten 10.1 bis 10.8 in Fig. 1, die durch Verbindungsstrecken zusammengeschaltet sind, wie die Verbindungsstrecken 15.1 bis 15.10 der Figur. Im Allgemeinen ist jedes Endgerät (nicht dargestellt) einem der Knoten zugeteilt.
In vielen modernen Netzen werden die Informationen, die von einem Ursprungsknoten zu einem Zielknoten befördert werden sollen, in Pakete oder Zellen unterteilt. Gemäß zum Beispiel den Asynchronous Transfer Mode- ("asynchroner Übertragungsmodus" - ATM) Protokollen oder dem Internetprotokoll (IP) strömen diese z. B. Pakete unabhängig vom Ursprungsknoten zum Zielknoten durch das Netz. Bei jedem Knoten, auf den sie auf ihrem Weg treffen, wird ein Paket in die eine oder andere Verbindungsstrecke gelenkt, abhängig von der Anfangsblockinformation, die dieses Paket trägt. Jedes dieser Netze wird hierin als "paketiertes" Netz bezeichnet.
Einige kommunikative Transaktionen, wie Telefonverbindungen, sind gegenüber der zeitlichen Abstimmung des Eintreffens der Pakete an ihrem Ziel sehr empfindlich. Wenn signifikante absolute oder relative Verzögerungen auftreten oder wenn die Pakete nicht in ihrer Reihenfolge eintreffen, kann die Qualität der Verbindung als unannehmbar erachtet werden. Zur Erhaltung der Qualität von Transaktionen dieser Art ist es wünschenswert, einen vollständigen Leitweg vom Ursprung bis zum Ziel für die gesamte Dauer der Transaktion aufrecht zu erhalten. (Diese kommunikativen Transaktionen werden hierin allgemein als "Verbindungen" bezeichnet, selbst wenn sie die Übertragung von Faxbildern, Daten usw. beinhalten.)
In allen außer den einfachsten Netzen ist im Allgemeinen mehr als ein Leitweg von einem gegebenen Ursprung zu einem gegebenen Ziel verfügbar. Zum Beispiel geht aus Fig. 1 hervor, dass vom Knoten 10.3 zum Knoten 10.4 fünf mögliche Leitwege vorhanden sind. Es ist jedoch nicht immer wünschenswert, jeden möglichen Leitweg für ein gegebenes Ursprung-Ziel-Paar verfügbar zu machen. Zum Beispiel können einige Leitwege durch eine übermäßige Zahl von Verbindungsstrecken gehen (d. h., sie haben viele "Abschnitte"), die eine unannehmbare kumulative Verzögerung hinzufügen. Das Problem wird durch die Tatsache erschwert, dass jede Verbindungsstrecke einen begrenzten Betrag an Bandbreite hat. Daher kann das Leitweglenken einer Verbindung zwischen nahen Knoten über eine weit entfernte Verbindungsstrecke einen Teil des Verkehrs zwischen Knoten ausschließen, die nahe dieser Verbindungsstrecke liegen. Das Ergebnis könnte sein, dass ein Teil des Verkehrs ebenfalls auf unerwünscht lange Leitwege gedrängt wird.
Die Disziplin, die als "Verkehrstechnik" bezeichnet wird, beschäftigt sich unter anderem mit dem Problem, wie Verkehr unter zulässigen Leitwegen zu verteilen ist. Diese Verteilung erfolgt vorzugsweise in einer Weise, die auf einen gewünschten Wert der Netzleistung ausgerichtet ist. Verkehrstechnische Probleme werden weiter kompliziert, wenn das Netz mehr als eine Dienstklasse durchführen soll. Zum Beispiel kann von demselben Netz verlangt werden, Sprach-, Bild-, Fax- und E-Mail-Übertragungen durchzuführen. Jeder dieser Dienste hat seine eigenen Anforderungen an die Bandbreite und jeder hat seine eigenen Anforderungen bezüglich des Ausmaßes der tolerierbaren Verzögerung. Jeder kann auch seine eigenen Anforderungen bezüglich des Ausmaßes der tolerierbaren Verbindungsblockierung haben. Ein Netz, das mehr als eine Dienstklasse überträgt, wird hierin als "Mehrdienstnetz" bezeichnet.
Der Netzverkehr kann grob in zwei Kategorien unterteilt werden: den Quality-of-Service- (QoS; Dienstgüte) Verkehr und den Best-Effort- (BE) Verkehr.
Der Dienstgüteverkehr ist ein Verkehr, der kritischen Anforderungen gerecht werden muss, um für Kunden annehmbar zu sein. Solche Anforderungen beziehen sich für gewöhnlich auf die maximal annehmbare Verzögerung. Sie können jedoch andere Leistungsparameter beinhalten. Zum Beispiel könnten Parameter, die das Blockieren betreffen, wichtig sein. Zu Parametern dieser Art zählen das Verbindungsverlust-Verhältnis und das Paketverlust-Verhältnis. Es kommt häufig vor, dass zur Erfüllung der Dienstgüteanforderungen der entsprechende Verkehr auf bestimmte Mengen zulässiger Leitwege beschränkt sein muss. Dieser Begriff zulässiger Leitwegmengen macht es möglich, bequem innerhalb der Dienstgütemethodologien zulässige Leitwegmengen festzulegen, die beschränkt sind, so dass sie Verfahrenseinschränkungen unterschiedlicher Arten gerecht werden.
Der Dienstgüteverkehr kann weiter in Echtzeitverkehr und Nicht-Echtzeitverkehr unterteilt werden. Echtzeitverkehr, der z. B. Sprach- und Bildverkehr beinhaltet, soll vom Kunden genutzt werden, sobald der Verkehr eintrifft. Jede Verzögerung, die vom Kunden als Unterbrechung des kontinuierlichen Stroms empfangener Daten empfunden wird, ist allgemein unannehmbar. Nicht- Echtzeitverkehr, der z. B. Verkehr von und zu Faxgeräten beinhaltet, ist gegenüber einer Verzögerung toleranter, muss aber dennoch die Erwartungen des Kunden hinsichtlich einer raschen und relativ reibungslosen Zustellung erfüllen. Insbesondere könnte Premium- Datenverkehr kritische Einschränkungen hinsichtlich des Verbindungsverlust-Verhältnisses und des Paketverlust- Verhältnisses aufweisen.
BE-Verkehr, der z. B. World Wide Web-Verkehr, E-Mail und FTP beinhaltet, ist hinsichtlich einer Verzögerung wie auch einer Verbindungsblockierung noch toleranter. Der Benutzer ist im Allgemeinen zufrieden, wenn er Minuten, oder in einigen Fällen sogar Stunden, warten muss, um eine vollständige Nachricht zu erhalten. Daher wird von dem Netzdienstanbieter nicht erwartet, etwaige bestimmte Grenzen für die maximale Verzögerung zu garantieren. Stattdessen ist es im Allgemeinen für das Netz ausreichend, eine Bandbreite zu verwenden, wenn sie verfügbar wird, die entbehrt werden kann, ohne lukrativeren Dienstgüteverkehr zu blockieren.
Damit Netzdienstanbieter ihre Mehrdienstnetze möglichst vollständig nutzen, ist für sie wünschenswert, ihren Kunden Garantien anzubieten, dass Grenzwerte hinsichtlich z. B. des Ausmaßes der Verzögerung, die für verschiedene Dienstklassen unterschiedlich festgelegt sind, eingehalten werden. Es ist jedoch schwierig, ein Netz zu schaffen, das solche Garantien beachtet, ohne ein übermäßiges Maß an Verkehr zu blockieren. Wenn zum Beispiel Sprachverkehr auf bestimmten Verbindungsstrecken konzentriert ist, da sie für die kürzeste Leitweglenkung von Sprechverbindungen wesentlich sind, könnten Faxübertragungen aus diesen Verbindungsstrecken ausgeschlossen sein. Wenn diese Verbindungsstrecken für die Leitweglenkung von Faxübertragungen notwendig sind, ist das Ergebnis ein Besetztsignal, sobald ein Versuch unternommen wird, ein Fax zu senden.
Eine Methode der Verkehrstechnik in Mehrdienstnetzen ist in D. Mitra, et al., "ATM Network Design and Optimization: A Multirate Loss Network Framework", IEEE/ACM Transactions an Networking 4 (August 1996) 531-543 beschrieben. Dieser Artikel beschreibt ein Software-Paket, das als TALISMAN bezeichnet ist. Unter anderem löst TALISMAN ein Gemeinschaftsleitweglenkungsproblem in Mehrdienst-ATM-Netzen, so dass ein Leistungsmaß maximiert wird, das als langfristige Durchschnittseinnahmen für das Netz charakterisiert werden kann. (Ein Gemeinschafts-Leitweglenkungsproblem ist eines, das gemeinschaftlich alle entsprechenden Ursprung-Ziel-Paare behandelt.) In dem TALISMAN-Modell wird eine Einnahmezahl für jeden Dienst-Leitweg (d. h., einen Leitweg in Verbindung mit einer gegebenen Dienstklasse) als Produkt eines Dienst-Leitweg- Einnahmeparameters mal der Stärke des auf diesem Dienst-Leitweg angenommenen Verkehrs erhalten. Die Verkehrsstärke ist als die Ankunftsrate von Verbindungen mal der mittleren Haltezeit pro Verbindung definiert. Diese Einnahmezahlen werden über alle Ströme und für jeden Strom über alle Dienst-Leitwege summiert, um die gesamten Netzeinnahmen zu erhalten. Ein Strom ist als ein Ursprung-Ziel-Paar in Verbindung mit einer gegebenen Dienstklasse definiert.
TALISMAN ist auch in EP-A-0 773 698 beschrieben. TALISMAN behandelt Verkehrsprozesse für gewöhnlich als stochastisch. Wie in EP-A-0 773 698 besprochen, kann TALISMAN jedoch die optimierten Netzeinnahmezahlen kalibrieren, die durch einen Vergleich mit oberen Grenzen erhalten werden, die durch Lösen eines Flussproblems mehrfacher Leistungsmerkmale auf der Grundlage eines deterministischen Verkehrsmodells erhalten werden.
D. Mitra, et al., "Virtual Private Networks: Joint Resource Allocation and Routing Design", Proc. IEEE INFOCOM, IEEE, New York, 21. März 1999, S. 480-490, beschreibt ein Verfahren zur Zuteilung einer Bandbreitenkapazität auf den Verbindungsstrecken des zu Grunde liegenden Netzes an virtuelle private Netze (VPN), so dass, wenn Verkehr optimal über die entsprechenden VPNs geleitet wird, die Einnahmen oder ein anderes Maß der Netzleistung optimiert wird. Das Verfahren, das von D. Mitra et al. beschrieben ist, kann so gestaltet werden, dass es im Betrieb TALISMAN als Unterprogramm aufruft.
Es besteht ein zunehmender Bedarf an Mehrdienstnetzen, in welchen die Leitwegmengen, die für verschiedene Dienstklassen verfügbar sind, unterschiedliche Verfahrensanforderungen erfüllen müssen. Zusätzlich zu den traditionellen Anforderungen, die sich z. B. auf die Bandbreite und Verzögerung beziehen, gibt es weitere Anforderungen, die mit virtuellen privaten Netzdiensten in Zusammenhang stehen, die auch zunehmend nachgefragt werden.
Da die Größe und Komplexität von Netzen allgemein zunimmt, verlängert sich auch die zur Lösung verkehrstechnischer Probleme erforderliche Zeit. Für die effizienteste Nutzung eines Netzes angesichts sich ändernder Verkehrsmuster ist es wünschenswert, On-Line- Lösungen verkehrstechnischer Probleme durchzuführen; das heißt, Lösungen, die auf tatsächliche Bedingungen reagieren, wenn diese eintreten. Selbst mit Hilfe von Hilfsmitteln wie TALISMAN ist dies für Netze, die groß oder komplex sind, nicht immer machbar.

Zusammenfassung der Erfindung

Es wurde ein Verfahren zur Lösung verkehrstechnischer Probleme in einem Netz gefunden, das mindestens eine Dienstgüte-Dienstklasse und mindestens eine Dienstklasse aufweist, die keine Dienstgüteklasse ist. Die rechnerische Komplexität unseres Verfahrens ist polynom, so dass es durchführbare Lösungen selbst für Netze mit Hunderten von Knoten und vielen Dienstklassen gibt. Bei einer Anwendung bei Netzen üblicher Größe ist unser Verfahren in vielen Fällen für eine On-Line- Ausführung schnell genug.
Gemäß unserem Verfahren wird eine Bandbreite entsprechenden Dienst-Leitwegen in wenigstens einer Dienstgüte-Dienstklasse zugeteilt. Der Begriff "Dienstgüte" wird hierin in einem weiten Sinn verwendet, um jede Dienstklasse einzuschließen, die eine Prioritätsbehandlung erfährt. In diesem Zusammenhang kann sowohl verzögerungsempfindlicher als auch verzögerungsunempfindlicher Verkehr ein Dienstgüteverkehr sein. Die Bandbreitenzuteilung erfolgt als Reaktion auf eine gegebene Bedarfsmenge für die Bandbreite in der Dienstgüteklasse zwischen jedem Ursprung-Ziel-Paar. Lineare Programmierverfahren, wie Multicommodity Flow- (MCF; Fluss mehrfacher Leistungsmerkmale) Techniken, werden zur Durchführung dieser Zuteilung derart verwendet, dass eine geeignete Gütezahl, wie die Netzeinnahmen, optimiert wird.
Dann werden lineare Programmierverfahren wieder zur Durchführung einer neuen Zuteilung verwendet, welche die Nutzung des Netzes minimiert, ohne sich von dem optimalen Wert der Gütezahl zu entfernen. Anschließend wird ein Restnetz identifiziert. Das Restnetz besteht aus jener Bandbreite, die nicht zugeteilt wurde, auf jeder Verbindungsstrecke des Netzes.
Dann wird ein Leitweglenkungsproblem für wenigstens eine Nicht-Dienstgüte-Dienstklasse gelöst. Ohne Einschränkung werden alle diese Dienstklassen hierin als BE-Klassen bezeichnet. Das Leitweglenkungsproblem wird gelöst, um für alle Flüsse in der BE-Dienstklasse Leitwegmengen zu finden und den entsprechenden Dienst- Leitwegen in jeder dieser Leitwegmengen eine Bandbreite zuzuteilen. Dieses Problem wird unter Verwendung linearer Programmiertechniken derart gelöst, dass eine geeignete Gütezahl, wie die Netzeinnahmen aus dem Best- Effort-Verkehr, optimiert wird.
Die Priorität der Dienstgüteklassen wird durch die Leitweglenkung des Dienstgütebedarfs vor und ohne Rücksichtnahme auf den BE-Bedarf verstärkt. Für gewöhnlich sind die effektiven Bandbreiten, die den Dienstgüte-Diensten zugeordnet sind, größer als jene der BE-Klassen. Diese beiden Faktoren führen im Allgemeinen zu einer geringeren Verzögerung und zu geringeren Raten einer Verbindungsblockierung und eines Paketverlustes im Dienstgüteverkehr in Bezug auf den BE-Verkehr.
In bevorzugten Ausführungsbeispielen der Erfindung wird das Leitweglenkungsproblem für die Dienstgüteklassen unter Verwendung einer leitwegbasierenden Formel gelöst, so dass Spezifikationen begrenzter zulässiger Leitwegmengen leicht entsprochen wird. Im Gegensatz dazu wird das Leitweglenkungsproblem für die BE-Klassen vorzugsweise unter Verwendung einer streckenbasierenden Formel gelöst. (Eine solche Formel wird manchmal als "kantenbasierend" bezeichnet.) Eine streckenbasierende Formel stellt eine verbesserte Geschwindigkeit bereit, wenn Probleme bei stark verbundenen Netzen gelöst werden. Die streckenbasierende Formel alleine führt jedoch nicht zu einer vollständigen Lösung. In einer gegebenen Dienstklasse führt sie zu einer Zuteilung einer Bandbreite von Verbindungsstrecke zu Verbindungsstrecke, die entsprechenden Ursprung-Ziel-Paaren zugeordnet sind, sorgt aber für keine Zuteilung nach dem Dienst-Leitweg. Ein weiteres Verfahren, das als Leitwegzerlegung bezeichnet wird, wird verwendet, um eine Bandbreitenzuteilung nach dem Dienst-Leitweg aus der streckenbasierenden Lösung zu konstruieren.
In einem weiteren Aspekt beinhaltet die Erfindung die Verwendung linearer Programmiertechniken, wie zuvor beschrieben, um eine Bandbreite unter Dienst-Leitwegen als Reaktion auf eine Bedarfsmenge in jeder entsprechenden Dienstklasse zuzuteilen. Von Bedeutung ist, dass der Bedarf so berechnet wird, dass eine effektive Bandbreite, die der entsprechenden Dienstklasse zugeordnet ist, berücksichtigt wird, und dass das stochastische Verhalten des Verkehrsbedarfs, der in der Praxis auftritt, in Betracht gezogen wird.
Es sollte festgehalten werden, dass das verkehrstechnische Problem, das durch die Erfindung in jedem Aspekt gelöst wird, ein kombiniertes Problem aus Leitweglenkung und Zugangssteuerung ist. Der Leitwegaspekt findet explizit statt, wenn ein Bedarf zwischen einem gegebenen Ursprung-Ziel-Paar in einer gegebenen Dienstklasse unter den zulässigen Leitwegen zugeteilt wird. Der Zugangssteuerungsaspekt findet implizit statt, wenn eine solche optimale Zuteilung eine Zuteilung von weniger als dem gesamten Bedarf ist. Einfach gesagt, die Zugangssteuerung arbeitet, wenn der Verkehr abgezweigt wird, um z. B. die Einnahmen zu maximieren.

Kurze Beschreibung der Zeichnung

Fig. 1 ist ein schematisches Diagramm eines beispielhaften Kommunikationsnetzes mit Verbindungsstrecken und Knoten.
Fig. 2 ist ein Flussdiagramm einer verkehrstechnischen Prozedur gemäß der Erfindung in einem sehr illustrativen Ausführungsbeispiel.
Fig. 3 ist ein Flussdiagramm einer Flusszerlegungsprozedur, die für die Ausführung der Erfindung in einigen Ausführungsbeispielen nützlich ist.
Fig. 4 ist ein Flussdiagramm einer Erweiterung der Prozedur von Fig. 2, die zu Bandbreitenzuteilungen führt, welche die stochastische Eigenschaft von Netzverkehr berücksichtigen.
Fig. 5 ist ein Flussdiagramm einer verkehrstechnischen Prozedur, die sich auf den Dienstgüteverkehr bezieht und, Bewertungs- und Einstellprozesse beinhaltet.

Symbol- und Terminologieglossar

Ein Netz hat N Knoten und L Verbindungsstrecken. Jeder Verbindungsstrecke ist ein entsprechender Wert mit dem Index 1 zugeordnet.
Eine Dienstklasse wird mit s bezeichnet.
Ein Ursprung-Ziel-Paar wird mit σ bezeichnet.
Ein Strom (s, σ) ist ein Ursprung-Ziel-Paar in Verbindung mit einer bestimmten Dienstklasse.
Jeder Leitweg (zwischen einem Ursprung-Ziel-Paar) ist durch einen Index r identifiziert.
Die Menge zulässiger Leitwege für einen gegebenen Strom (s, σ) ist als R(s, σ) bezeichnet.
Ein Dienst-Leitweg (s, r) ist ein Leitweg r in Verbindung mit einer bestimmten Dienstklasse s.
Die Bedarfsmatrix Ts ist die NxN-Matrix des Bandbreitenbedarfs Ts,σ zwischen Ursprung-Ziel-Paaren σ in der Dienstklasse s. Die Einträge der Bedarfsmatrix beruhen für gewöhnlich auf Verkehrsmessungen oder auf Vorhersagemodellen. Es gibt eine Bedarfsmatrix für jede Dienstgüte-Dienstklasse und es gibt auch eine Bedarfsmatrix TBE für den Best-Effort-Verkehr.
Cl ist die Bandbreite oder Kapazität der Verbindungsstrecke l.
Der Dienstgüte-Einnahmeparameter esr ist der Gewinn pro Einheit beförderter Bandbreite auf einem gegebenen Dienstgüte-Dienst-Leitweg.
Der Best-Effort-Einnahmeparameter eBE,σ ist der Gewinn pro Einheit beförderter Bandbreite des gesamten BE-Verkehrs zwischen einem gegebenen Ursprung-Ziel- Paar. Der Einfachheit halber wird hier angenommen, dass diese Gewinnrate von der Wahl des Leitweges unabhängig ist. Verallgemeinerungen auf Fälle von leitwegabhängigen Gewinnen sind leicht zu machen und fallen auch in den Schutzumfang der vorliegenden Erfindung.
Xsr ist der Fluss oder die beförderte Bandbreite auf einem gegebenen Dienst-Leitweg.
Fσ ist der gesamte BE-Fluss oder die beförderte Bandbreite zwischen einem gegebenen Ursprung-Ziel-Paar.
WQoS sind sie gesamten Netzeinnahmen für alle Dienstgüte-Dienstklassen. Diese werden berechnet durch Summieren des Produktes esrXsr über alle Dienstgüte- Dienstklassen, über alle Ursprung-Ziel-Paare und für jeden entsprechenden Strom über die Leitwegmenge (d. h., die Menge zulässiger Leitwege) für diesen Strom:
WBE sind die gesamten Netzeinnahmen für den BE-Verkehr. Sie werden durch Summieren des Produktes eBE,σFσ über alle Ursprung-Ziel-Paare berechnet:
In Gleichung 2 wird der Einfachheit halber angenommen, dass es nur eine BE-Dienstklasse gibt. Verallgemeinerungen auf Fälle mit mehrfachen BE-Klassen sind leicht zu machen und fallen auch in den Umfang der vorliegenden Erfindung.

Ausführliche Beschreibung

Gemäß dem veranschaulichenden Ausführungsbeispiel der Erfindung, das in Fig. 2 dargestellt ist, wird ein Flussproblem mehrfacher Leistungsmerkmale ("multicommodity flow" - MCF) gelöst, wie bei Block 20 angezeigt, um die Flüsse Xsr auf entsprechenden Dienst- Leitwegen zu finden, welche die Netzdienstgüteeinnahmen maximieren. Die Eingaben in das Problem sind die Dienstgüte-Bedarfsmatrizen, die Streckenkapazitäten, die Leitwegmenge für jeden Dienstgütestrom und die Einnahmeparameter für die verschiedenen Dienstgüte- Dienst-Leitwege. Die Maximierung wird mit den Einschränkungen ausgeführt, dass: (i) für einen gegebenen Strom die Summe aller Flüsse Xsr über die Leitwegmenge für diesen Strom den Bedarf Ts,σ nicht übersteigen darf, der mit diesem Strom verbunden ist; (ii) die Flüsse Xsr alle nicht negativ sein müssen; und (iii) die Summe aller Flüsse, die über eine gegebene Verbindungsstrecke geleitet werden, die Kapazität dieser Verbindungsstrecke nicht übersteigen darf.
Mathematisch wird das MCF-Problem von Block 20 angegeben durch:
unterliegt:
für alle Dienstgüte-Dienstklassen s und für alle σ,
Xsr ≥ 0 für alle r R(s, σ), für alle Dienstgüte- Dienstklassen s und für alle σ, und
für alle l.
In Bezug auf die erste der obengenannten Einschränkungen sollte festgehalten werden, dass wenigstens für einige Ströme die Möglichkeit besteht, dass die Summe aller Flüsse über die entsprechende Leitwegmenge kleiner als der zugehörige Bedarf sein kann. Das heißt, die Zugangssteuerung kann so arbeiten, dass ein Teil der verlangten Bandbreite verweigert wird. Für einen gegebenen Strom (s, σ) kann ein entsprechendes Verlustverhältnis Lsσ definiert werden durch:
Das MCF-Problem von Block 20 wird gelöst, um W*QoS zu bestimmen, das ein optimaler Wert der gesamten Dienstgüte-Netzeinnahmen ist. Es sollte festgehalten werden, dass eine andere Gütezahl, wie der gesamte beförderte Dienstgüteverkehr, im MCF-Problem einfach für die Dienstgüte-Netzeinnahmen eingesetzt wird.
Im Block 25 wird ein zweites MCF-Problem gelöst. Alle Eingaben in das erste MCF-Problem sind auch Eingaben in dieses zweite MCF-Problem. Zusätzlich wird der Wert von W*QoS der aus der Lösung des vorangehenden MCF-Problems erhalten wurde, nun als Einschränkung angewendet. Das heißt, das MCF-Problem von Block 25 muss so gelöst werden, dass die Gesamtnetzeinnahmen (oder die andere Gütezahl) nicht kleiner als W*QoS ist, oder nicht kleiner als eine Zahl, die von W*QoS abgeleitet ist. Ein Beispiel für eine solche abgeleitete Zahl ist ein Bruchwert von W*QoS, kleiner als aber nahe dem Wert W*QoS. Die Aufgabe des MCF-Problems von Block 25 ist die Minimierung der gesamten Betriebsmittelnutzung, die durch Summieren von Bandbreiten-Abschnitten des Dienstgüteverkehrs gelöst wird. Die gesamte Betriebsmittelnutzung UQoS durch den Dienstgüteverkehr wird mathematisch ausgedrückt durch die Gleichung:
wobei die erste Summierung über Verbindungsstrecken vorgenommen wird, die zweite über Ströme und die dritte über Leitwege in der entsprechenden Leitwegmenge, aber nur jene Leitwege, die eine gegebene Verbindungsstrecke l enthalten. UQoS ist die Zielfunktion, die zu minimieren ist, abhängig von der Einnahmebeschränkung.
In alternativen Methoden können verschiedene Maße der Effizienz einer Betriebsmittelnutzung optimiert werden. Zum Beispiel wäre eine alternative Methode die Minimierung der Nutzung der am stärksten benutzten Verbindungsstrecke.
In anderen alternativen Methoden wird eine Einschränkung auferlegt, um eine Sättigung der am stärksten benutzten Verbindungsstrecken zu verhindern. Eine solche Einschränkung wäre z. B. die Unterbrechung der Nutzung einer gegebenen Verbindungsstrecke bei einem festgelegten Bruchteil der gesamten Streckenkapazität.
Der Ausgang von Block 25 enthält die Menge {Xsr} von Flussparametern auf allen der Dienst-Leitwege, die UQoS minimieren. Bei Block 30 ist die Kapazität Cl jeder Verbindungsstrecke l durch jeden Fluss Xsr verringert, der über diese Verbindungsstrecke gelenkt wird. Die übrige Kapazität ist als C'l bezeichnet. Die Menge {C'l} aller übrigen Kapazitäten C'l wird als "Restnetz" bezeichnet.
Bei Block 35 wird ein weiteres MCF-Problem gelöst, um die gesamten Netzeinnahmen (oder andere Gütezahl) aus dem Best-Effort-Verkehr zu maximieren. Zur Lösung dieses MCF-Problems ist das Netz als das Restnetz {C'l} definiert. Somit sind die Eingaben in Block 35 die Best-Effort-Bedarfsmatrix TBE, die Menge {C'l} und die Menge von Gewinnparametern {eBE,σ}.
Es sollte festgehalten werden, dass in der vorangehenden Diskussion die MCF-Probleme von Blöcken 20 und 25 als leitwegbasierende Probleme formuliert wurden. Das heißt, die Entscheidungsvariablen Xsr beziehen sich auf den Fluss auf gegebenen Dienst- Leitwegen, sind aber nicht separat für einzelne Verbindungsstrecken spezifiziert. Es ist wohlbekannt, dass eine alternative Formel für MCF-Probleme die sogenannte streckenbasierende (oder kantenbasierende) Formel ist, in welcher jede Entscheidungsvariable Yσl den Strom zwischen einem gegebenen Ursprung-Ziel-Paar σ auf einer gegebenen Verbindungsstrecke l ausdrückt.
Die leitwegbasierende Formel ist zur Behandlung des Dienstgüteverkehrs vorteilhaft, da sie bequem ermöglicht, dass unterschiedliche Verfahrenseinschränkungen wie auch Einschränkungen im Zusammenhang mit einer Verzögerung bei den Leitwegen für verschiedene Ursprung-Ziel-Paare und verschiedene Dienstklassen angewendet werden können. Diese Einschränkungen können zum Beispiel Grenzwerte des insgesamt zulässigen Abschnitt-Zählwerts enthalten. Solche Einschränkungen sind nützlich, um zu garantieren, dass die Gesamtverzögerung oder ein anderes Qualitätsmaß innerhalb gewünschter Grenzen bleibt. Von Bedeutung ist, dass Verfahrenseinschränkungen und andere Einschränkungen dazu neigen, die Anzahl zulässiger Leitwege für ein gegebenes Ursprung-Ziel-Paar und eine gegebene Dienstklasse zu begrenzen.
In einem stark verbundenen Netz mit vielen zulässigen Leitwegen in jeder Leitwegmenge neigt die leitwegbasierende Formel jedoch dazu, sehr komplex zu werden. In einem solchen Fall kann die Lösung des MCF- Problems in der leitwegbasierenden Formel im praktischen Sinn schwer zu bearbeiten sein. Andererseits ist die Komplexität der streckenbasierenden Formel von der Anzahl von Leitwegen unabhängig und hängt nur von der Anzahl von Verbindungsstrecken und Knoten ab. Somit kann die streckenbasierende Formel vorteilhaft sein, wenn die Leitwegmengen groß sind.
Im Gegensatz zum Dienstgüteverkehr ist der Best-Effort- Verkehr für gewöhnlich keinen Verfahrenseinschränkungen unterworfen, wie einer oberen Grenze für die zulässige Anzahl von Abschnitten in einem Leitweg. Daher können innerhalb der Einschränkungen des Restnetzes die Leitwegmengen für den Best-Effort-Verkehr ziemlich groß sein und sind wenigstens in einigen Fällen frei von a priori-Einschränkungen. Folglich nehmen wir an, dass es allgemein bevorzugt ist, das MCF-Problem von Block 35 für den Best-Effort-Verkehr unter Verwendung der streckenbasierenden Formel zu lösen.
Die Aufgabe des MCF-Problems von Block 35 ist die Bestimmung der Menge {Yσl} von Best-Effort- Flussparametern, welche die gesamten Best-Effort- Netzeinnahmen WBE maximieren, die den Einschränkungen unterliegen, dass: (i) der Gesamtfluss Fσ zwischen jedem Ursprung-Ziel-Paar σ nicht negativ und nicht größer als der entsprechende Best-Effort-Bedarf TBE,σ sein muss; (ii) für jedes Ursprung-Ziel-Paar die Summe der Flussparameter Yσl, die über Verbindungsstrecken ermittelt wird, die in einen gegebenen Knoten eintreten, gleich der Summe sein muss, die über Verbindungsstrecken ermittelt wird, die den gegebenen Knoten verlassen, wenn der Knoten nicht ein Ursprung oder ein Ziel ist, wobei sich in diesem Fall die beiden Summen um +1 (wenn er ein Ziel ist) oder -1 (wenn er ein Ursprung ist) mal dem Gesamtfluss Fσ unterscheiden;
(iii) alle Flussparameter nicht negativ sein müssen; und (iv) für jede Verbindungsstrecke l die Summe über alle Ursprung-Ziel-Paare σ der Flussparameter Yσl die Streckenkapazität Cl nicht überschreiten darf.
Für den Fachmann ist offensichtlich, dass die Formel für dieses Problem, das hier beschrieben wird, die sogenannte "N²L"-Formel ist. Wenigstens in einigen Fällen bietet eine alternative Formel, die als die "N- Leistungsmerkmal"-Formel bekannt ist, den Vorteil einer höheren Recheneffizienz. Eine Beschreibung dieser alternativen Formel findet sich z. B. in US-Patent Nr. 5,596,719, erteilt am 21. Januar 1997 und gemeinschaftlich hiermit übertragen, beginnend in Spalte 5, Zeile 60.
Ähnlich dem Fall des Dienstgüteverkehrs kann ein Best- Effort-Verlustverhältnis aufgrund der Zugangssteuerung als TBE,σ - Fσ/TBE,σ definiert werden.
Zur Anwendung der Ergebnisse von Block 35 ist es notwendig, aus der optimalen Menge {Yσl} eine entsprechende Menge {X } aus leitwegbasierenden Best- Effort-Flussparametern zu gewinnen. Die Prozedur, um dies zu erreichen, wird als Flusszerlegung bezeichnet. In Block 40 wird eine Flusszerlegung ausgeführt, um die Menge {X } aus der Eingabemenge {Fσ} der gesamten Flüsse für die entsprechenden Ursprung-Ziel-Paare und aus der Eingabemenge {Yσl} der streckenbasierenden Flussparameter abzuleiten.
Verfahren zur Ausführung einer Flusszerlegung sind in der Technik wohlbekannt. Ein beispielhaftes Verfahren ist in Fig. 3 dargestellt und wird nun beschrieben.
In Block 45 werden die Mengen {C'l}, {Fσ} und {Yσl} als Eingang angenommen. In Block 50 wird ein anfängliches Ursprung-Ziel-Paar σ zur Verarbeitung erhalten. Jedes Ursprung-Ziel-Paar wird verarbeitet, bis wiederum keines mehr übrig ist, wie durch die Blöcke 80 und 85 angezeigt ist.
In Block 55 wird ein reduzierter Graph G(σ) generiert, indem aus dem Restnetz jede Verbindungsstrecke gelöscht wird, die keinen Fluss zwischen dem momentanen Ursprung-Ziel-Paar σ befördert. In Block 60 wird ein Leitweg r verfolgt, der das momentane Ursprung-Ziel- Paar verbindet. In Block 65 wird dem leitwegbasierenden Best-Effort-Flussparameter XBE,r für den momentanen Leitweg ein Wert zugeordnet, der gleich dem kleinsten streckenbasierendem Flussparameter auf einer beliebigen Verbindungsstrecke des momentanen Leitweges ist. Das heißt, ihm wird der Wert Yσl zugeordnet. Auch in Block 65 wird der Gesamtflusswert Fσ für das momentane Ursprung-Ziel-Paar um die Größe XBE,r reduziert.
Wie festgehalten wurde, wurde in Block 60 ein bestimmter Leitweg r in G(σ) verfolgt, der das momentane Ursprung-Ziel-Paar verbindet. In Block 70 wird der streckenbasierende Flussparameter Yσl auf jeder Verbindungsstrecke dieses Leitweges r um die Größe XBE,r reduziert.
Wie in Block 75 angegeben, werden die Prozeduren der Blöcke 55 bis 70 für das momentane Ursprung-Ziel-Paar wiederholt, bis der Gesamtflusswert Fσ für dieses Ursprung-Ziel-Paar auf Null reduziert ist; das heißt, bis der gesamte Fluss zwischen dem Paar von Knoten Leitwegen zugeordnet ist. Dann wird, wie in den Blöcken 75 bis 85 angezeigt ist, ein neues Ursprung-Ziel-Paar erhalten, und die Prozedur der Blöcke 55 bis 70 wird wiederholt. Die gesamte Prozedur wird für jedes verbleibende Ursprung-Ziel-Paar wiederholt, bis kein unverarbeitetes Ursprung-Ziel-Paar mehr übrig ist.
Es sollte festgehalten werden, dass bei jeder Wiederholung von Block 55 (für ein gegebenes Ursprung- Ziel-Paar σ) der reduzierte Graph G(σ) weiter von seinem Zustand in der vorangehenden Wiederholung verringert wird. Wenn jedoch ein neues Ursprung-Ziel- Paar erhalten wird, ist der Anfangsgraph G(σ) wieder das gesamte Restnetz.
Nach dem Erhalt der leitwegbasierenden Flussparametermengen {Xsr} und {X } können diese verwendet werden, um den angebotenen Verkehr in jedem Strom unter den zulässigen Leitwegen in der Leitwegmenge für diesen Strom zuzuteilen. In einem beispielhaften Zuteilungsschema ist der Anteil des einem gegebenen Leitweg angebotenen Verkehrs etwa gleich Xsr für diesen Leitweg, dividiert durch die Summe der Xsr-Werte über alle Leitwege in der Leitwegmenge. Für den Fachmann ist offensichtlich, dass ein solches Schema bereits z. B. durch proportionale Leitweglenkung am Ursprungsknoten in Verbindung mit einer gewichteten fairen Warteschlangenbildung an den verschiedenen Knoten des Netzes ausgeführt wird.
Proportionale Leitweglenkung und gewichtete faire Warteschlangenbildung sind in der Technik wohlbekannt und müssen hier nicht ausführlich beschrieben werden. Aus pädagogischen Gründen jedoch folgt nun eine kurze Beschreibung einer proportionalen Leitweglenkung. Jeder Knoten ist ein angehender Ursprungsknoten für jedes N - 1-Ursprung-Ziel-Paar in jeder der S-Dienstklassen und somit ein angehender Ursprungsknoten für jeden von S(N - 1)-Strömen. Mehrere Leitwege können jedem dieser Ströme entsprechen, wobei jeder Leitweg einen relativen Anteil Xsr/Tsσ des Verkehrsbedarfs Tsσ hat. In diesem Fall wird das Abzweigen einer Verbindung auch als Leitwegzuteilung (an einen Phantomleitweg) mit einem solchen relativen Anteil behandelt. In dem Router an jedem Knoten sind S(N - 1)-Tabellen geladen, eine für jeden Strom. In jeder Tabelle sind die Werte der Brüche Xsr/Tsσ für die entsprechenden Dienst-Leitwege aufgelistet. Ein Verbindungsbedarf wird unter diesen Dienst- Leitwegen zugeteilt, einschließlich des Phantomleitweges, im Verhältnis zu den Brüchen Xsr/Tsσ.
In einigen Ausführungsformen des Verfahrens, das mit Bezugnahme auf Fig. 2 beschrieben wurde, stellt der Verkehrsbedarf Ts,σ Mittelwerte dar, die durch Messung oder durch Projektion von einem Verkehrsmodell erhalten wurden. Wenn für diesen Zweck ein Verkehrsmodell verwendet wird, ist es vorzugsweise ein stochastisches Modell, da ein solches Modell dem statistischen Wesen von Kommunikationsverkehr genauer Rechnung trägt.
Eine solche Verwendung von Mittelwerten kann jedoch zu unerwünschten Verlustraten führen. Dies ist genau gesagt so, weil der Kommunikationsverkehr von Natur aus statistisch ist. In der Praxis tritt ein Bedarf nicht gleichmäßig auf, sondern neigt dazu, in Bündeln aufzutreten, die durch Perioden verhältnismäßig geringer Aktivität getrennt sind. Wenn angenommen wird, dass ein Bedarf gleichmäßig auftritt, könnte die daraus resultierende Verkehrstechnik versagen, ausreichende Kapazität bereitzustellen, um die Perioden verhältnismäßig hoher Aktivität zu bewältigen, wenn der Bedarf in Bündeln eintrifft, Folglich müssten Verkehrsangebote an bestimmte Leitwege zurückgewiesen werden, da die Kapazität auf einer oder mehreren Verbindungsstrecken solcher Leitwege ungenügend ist. Eine solche Zurückweisung hätte den Verlust einer Verbindung zur Folge.
Wir haben eine Methode entwickelt, die verspricht, die Verlustrate durch Berücksichtigung der Stochastizität eintreffender Verbindungen zu verringern, während die Berechenbarkeit selbst für große Netze aufrecht erhalten bleibt. Es wird nun diese Methode in einer Anwendung bei Dienstgüteverkehr beschrieben. Wahlweise kann sie auch bei Best-Effort-Verkehr angewendet werden.
Unsere Methode beinhaltet gewisse Größen, die mit dem stochastischen Modell von Kommunikationsnetzen zusammenhängen. Diese sind in der Folge zusammengefasst:
Die mittlere Ankunftsrate von Verbindungen eines gegebenen Stroms (s, σ), zum Beispiel in einem Poisson- Prozess, wird als Λsσ bezeichnet.
Die mittlere Halteperiode einer Verbindung des gegebenen Stroms wird als 1/usσ bezeichnet.
Die Belastung oder Verkehrsstärke des gegebenen Stroms wird als sσ bezeichnet. Diese Größe ist gleich Λsσ/usσ.
Die Größen Λsσ, 1/usσ und die effektiven Bandbreiten ds werden allgemein als Eingaben in das stochastische Modell des Netzes betrachtet. Die effektive Bandbreite ist ein Parameter, der die Effekte der Paketebenenvariabilität, des Pufferspeicherüberlaufs, der Pufferspeicherverzögerung und anderer Dienstgüteempfindlichen Effekte auf Paketebene und Beschreiber des Verkehrsverhaltens subsumxniert.
Die Entwicklungsprozedur, die in der Folge besprochen wird, führt zu einer weiteren Größe ρsr. Dies ist die Belastung oder Verkehrsstärke auf einem gegebenen Dienst-Leitweg (s, r). Die Größen ρsr sind analog den Flussparametern Xsr, die zuvor besprochen wurden. Sobald sie erhalten worden sind, können die Größen ρsr in einer Verkehrstechnikprozedur verwendet werden. Eine solche Prozedur ist zum Beispiel analog der zuvor beschriebenen Prozedur, in welcher die Flussparameter Xsr verwendet werden, um Verkehr über die entsprechende Leitwegmenge zuzuteilen.
Fig. 4, auf die nun Bezug genommen wird, zeigt eine Prozedur, die wiederum für jeden Strom wiederholt wird, bis keine weiteren Ströme verbleiben. In Block 90 wird der erste Strom erhalten. In Block 95 wird das Element Ts,σ der Bedarfsmatrix Ts aus dem folgenden Ausdruck erhalten:
In Gleichung 6 ist die Größe α ein nicht negativer, einstellbarer Parameter, der als Kompensationsparameter bezeichnet wird. Umso variabler der Verbindungsankunftsprozess ist, desto größer ist der Bedarf an einer Kompensation, und desto größer ist somit der Wert von α, der wünschenswert ist. Zum Beispiel hat sich in theoretischen Analysen gezeigt, dass ein Wert für α von etwa 0,5 für die Poissonverteilten Verbindungsankünfte, exponential verteilten Verbindungshaltezeiten und die kritische Belastung des Netzes zweckdienlich ist.
In Block 100 wird die flussbasierende Entwicklungsprozedur von Fig. 2, Blöcke 20 und 25, ausgeführt, um die Flussparameter Xsr zu erhalten. Die Elemente Ts,σ, die in Block 95 erhalten werden, werden als Eingabe in die flussbasierende Entwicklungsprozedur verwendet.
In Block 105 wird die Belastung ρsr für jeden Leitweg in der Leitwegmenge des momentanen Stroms aus dem folgenden Ausdruck erhalten:
ρsr/ρsσ = Xsr/Tsσ. (Gleichung 7)
Wie in den Blöcken 110 und 115 angegeben ist, werden wiederum die Prozeduren der Blöcke 95 bis 105 für jeden Strom wiederholt, bis keine übrig sind. Dann kann, wie in Block 120 angegeben ist, eine Auswertung der erwarteten Netzleistung zum Beispiel unter Verwendung bekannter Verfahren ausgeführt werden, die auf dem stochastischen Netzmodell beruhen, um die Verlustwahrscheinlichkeit auf jedem Dienst-Leitweg zu berechnen. Wenn eine dieser vorhergesagten Verlustwahrscheinlichkeiten zu hoch ist, können Einstellungen beim Kompensationsparameter α oder anderen Parametern, die in den zuvor beschriebenen Verfahren verwendet werden, vorgenommen werden.
Fig. 5 fasst die verkehrstechnische Prozedur für den Dienstgüteverkehr zusammen. Die Blöcke 125 und 130 sind analog zu den Blöcken 20 und 25 von Fig. 2, können aber die stochastisch basierenden Verfeinerungen enthalten, die hier mit Bezugnahme auf Fig. 4 beschrieben sind. In Block 135 wird eine theoretische Verlustrate für jeden Dienst-Leitweg berechnet. In Block 140 wird eine Angabe gemacht, ob die vorhergesagte Verlustrate in einer beliebigen Dienstklasse zu hoch ist.
Die Blöcke 145 und 150 stellen alternative, beispielhafte Pfade zur Überarbeitung der verkehrstechnischen Konstruktion dar, um unerwünschte Verluste zu verringern. In Block 145 werden die Einnahmeparameter esr, die in das MCF-Problem eingegeben werden, überarbeitet. Da die Netzeinnahmen in dem ersten MCF- Problem maximiert und bei dem optimalen Wert im zweiten MCF-Problem gehalten werden, neigt eine Zunahme in den Gewinnen, die einem gegebenen Strom zuzuschreiben ist, dazu, die Verkehrsblockierung für diesen Strom zu verringern.
In Block 150 werden dem MCF-Problem von Block 130 zusätzliche Einschränkungen hinzugefügt. Die Eigenschaft dieser Einschränkungen ist die Begrenzung der Nutzung auf bestimmten, stark benutzten Verbindungsstrecken auf einen gewissen Bruchteil der Gesamtkapazität. Somit ist die Aufgabe dieses MCF- Problems nun, ein Minimalmaß an Betriebsmittelnutzung zu finden, das mit der Einnahmeeinschränkung und den Begrenzungen der Nutzung bestimmter Verbindungsstrecken im Einklang steht. Durch Reservierung einer gewissen Kapazität in diesen Verbindungsstrecken ist es möglich, deren Überlastung in Perioden verhältnismäßig hoher Aktivität zu vermeiden.
Ein Punkt in der Netzkonstruktion, der zunehmend an Bedeutung gewinnt, ist jener von virtuellen privaten Netzen (VPN). Ein VPN ist ein logisch definiertes Netz, das aus einer Bandbreite auf jeder von verschiedenen Verbindungsstrecken besteht, die einem bestimmten Kunden zugeteilt ist. Wenn die hier beschriebenen Verkehrstechniken bei einem Netz angewendet werden, das ein oder mehrere VPNs unterstützt, kann das Problem entstehen, wie den Bandbreitenanforderungen der VPNs entsprochen werden kann.
Wir haben eine Lösung dieses Problems in Betracht gezogen, die wenigstens in einigen Fällen zweckdienlich sein könnte. Gemäß unserer Lösung werden Anforderungen zwischen einem gegebenen Ursprung-Ziel-Paar in einer gegebenen Dienstklasse gesammelt behandelt, selbst wenn einige von diesen Anforderungen für verschiedene VPNs gekennzeichnet sind. Nachdem die Flussparameter Xsr oder Belastungen ρsr erhalten wurden, werden dann diese Größen unter den VPNs und dem Nicht-VPN-Verkehr zugeteilt.
Die Auflösung findet in zwei Schritten statt. Zunächst wird der gesamte Fluss auf jedem Leitweg (für einen gegebenen Strom) zwischen dem Nicht-VPN-Verkehr und dem VPN-Verkehr in direktem Verhältnis zu den Beiträgen aufgeteilt, die der Nicht-VPN-Bedarf und der VPN-Bedarf im Gesamtbedarf bilden. Dann wird der gesammelte VPN- Fluss unter den verschiedenen VPNs in Übereinstimmung mit ihren entsprechenden Anteilen aufgeteilt.
Es wurden zwei beispielhafte Prozeduren zur Bestimmung der entsprechenden Anteile der verschiedenen VPNs überlegt. Gemäß einer Prozedur steht der Anteil jedes VPN in direktem Verhältnis zu dem Beitrag dieses VPN zu dem Gesamtbedarf. Gemäß einer zweiten Prozedur wird das wohlbekannte Verfahren des heuristischen Bin Packing zur Bestimmung des Anteils jedes VPN angewendet. Diese zweite Prozedur ist besonders nützlich, wenn es ein Ziel ist, jeden VPN-Bedarf auf einem einzigen Leitweg zu leiten.
Kurz gesagt, das heuristische Bin Packing beginnt damit, die VPNs in absteigender Reihenfolge nach der Größe ihres entsprechenden Bedarfs zu ordnen. Der Bedarf, der mit dem ersten VPN verbunden ist, wird einem Leitweg mit ausreichender Kapazität zugeordnet. Wenn kein Leitweg ausreichende Kapazität hat, wird das größtmögliche Bedarfsmaß einem einzigen Leitweg zugeordnet und das VPN nimmt einen neuen Platz in der Reihung ein, der durch die Größe des verbleibenden, nicht zugeordneten Bedarfs bestimmt wird. Die Prozedur wiederholt dann die Leitweglenkung des Bedarfs, der mit dem neuen VPN verbunden ist, welches das erste in der Reihenfolge ist.

Beispiel

Es wurden theoretische Analysen auf der Basis des Netzes von Fig. 1 durchgeführt. Jede der Verbindungsstrecken 15.1-15.10 ist eigentlich ein Paar gerichteter Verbindungsstrecken, eine in jede Richtung. Jede gerichtete Verbindungsstrecke hat eine Bandbreite von 155 Mbit/s, die hier als eine OC3-Einheit bezeichnet wird, mit der Ausnahme, dass die Verbindungsstrecken 15.3 und 15.8 in jede Richtung Kapazitäten von zwei OC3-Einheiten haben. Die Dienstklassen sind Sprache (Klasse 1), Bild (Klasse 2), Premium-Daten (Klasse 3) und Best-Effort (Klasse 4). Die Leitwegmengen für die Klassen 1 und 2 sind auf Leitwege mit den wenigsten Abschnitten begrenzt. Die Leitwegmenge für die Klasse 3 ist auf Leitwege mit 4 Abschnitten oder weniger begrenzt. Die Leitwegmenge für die Best-Effort-Klasse ist unbegrenzt. Die Bedarfsmatrizen für die vier Dienstklassen werden durch Multiplizieren der Matrix von Tabelle 1 mit 0,4, 0,1, 0,25 bzw. 0,25 erhalten. Der Gesamtbedarf für die vier Dienstklassen ist 563,5, 140,9, 352,2, bzw. 352,2. Tabelle 1
Die Prozeduren von Fig. 2, Blöcke 20 und 25 wurden ausgeführt. In der erhaltenen Lösung wurde der gesamte Bandbreitenbedarf befördert. Dann wurde die vollständige Prozedur von Fig. 2 ausgeführt. In der erhaltenen Lösung war die gesamte beförderte Best- Effort-Bandbreite 279,4 Mbit/s. Somit gingen 20,5% der Best-Effort-Bandbreite verloren.
Die Minimierung der Dienstgüte-Betriebsmittelnutzung in Block 25 von Fig. 2 führte zu einer Gesamtbetriebsmittelnutzung durch Dienstgüteklassen von 2120 Mbit/s- Abschnitten. Die entsprechende Kapazität des Restnetzes war 10,3 OC3-Einheiten. Zum Vergleich wurde die Dienstgüte-Betriebsmittelnutzung ebenfalls maximiert. Die gesamte maximierte Nutzung war 2668 Mbit/s-Abschnitte, entsprechend einer Kapazität in dem Restnetz von 2,85 OC3-Einheiten.
Es wurden auch die stochastische Verfeinerung von Fig. 4 und die berechneten Verlustwahrscheinlichkeiten in dem stochastischen Modell angewandt. Für diesen Zweck war die effektive Bandbreite einzelner Verbindungen in den Dienstklassen 1, 2 und 3 16 Kbit/s, 640 Kbit/s bzw. 384 Kbit/s.
Für eine Nullkompensation war der Gesamtbandbreitenbedarf
1056,3 Mbit/s, die gesamte beförderte Dienstgütegarantierte Bandbreite
war 1042,2 Mbit/s, und die netzweite Verlustwahrscheinlichkeit war 0,0134. In dem vorangehenden Ausdruck für die beförderte Bandbreite ist die Größe Lsr die Verlustwahrscheinlichkeit für den Dienst-Leitweg (s, r).
Für α = 0,5 war der gesamte Bandbreitenbedarf 978,8 Mbit/s, die gesamte beförderte Dienstgütegarantierte Bandbreite war 976,0 Mbit/s und die netzweite Verlustwahrscheinlichkeit war 0,003.
Für α = 1,0 war der gesamte Bandbreitenbedarf 901,3 Mbit/s, die gesamte beförderte Dienstgütegarantierte Bandbreite war 901,2 und die netzweite Verlustwahrscheinlichkeit war 0,0001.

Claims

1. Verfahren zum Zuteilen von Bandbreite zu Leitwegen durch ein paketiertes Kommunikationsnetz, das durch Verbindungsstrecken zusammengeschaltete Knoten umfasst und das eine oder mehrere als Dienstgüteklassen zu bezeichnende Dienstklassen s unterstützt, wobei jeder Leitweg einen Ursprungsknoten mit einem Zielknoten verbindet, mit folgenden Schritten:

a) Lösen von mindestens einem linearen Programmierproblem zur Bestimmung einer Erstzuteilung von mindestens irgendeiner verlangten Bandbreite in einer oder mehreren Dienstgüteklassen oder zulässigen Leitwegen, so dass die Erstzuteilung eine Gütezahl W der Netzleistung optimiert, wobei der optimierte Wert als W* zu bezeichnen ist; gekennzeichnet durch folgendes:

b) für jede der einen oder mehreren Dienstgüteklassen Lösen mindestens eines linearen Programmierproblems zur Bestimmung einer weiteren Zuteilung von mindestens irgendeiner verlangten Bandbreite unter zulässigen Leitwegen, wobei: (i) die weitere Zuteilung so zu treffen ist, dass sie ein Kriterium zum Begrenzen der Betriebsmittelnutzung durch das Netz erfüllt und dabei die Gütezahl W auf oder nahe an ihrem optimierten Wert W* aufrechterhält, und (ii) die weitere Zuteilung zu einer Menge Flussparameter Xsr führt, wobei jeder Flussparameter einen Betrag an Bandbreite in der einem entsprechenden Leitweg r zugeteilten Dienstgüteklasse s darstellt;

c) Identifizieren etwaiger nicht zugeteilter Bandbreitenkapazität auf jeder Verbindungsstrecke des Netzes, wobei die nichtzugeteilten Streckenkapazitäten als Sammelbegriff als ein Restnetz zu bezeichnen sind; und

d) für mindestens eine weitere, als eine BE-Klasse zu bezeichnende Dienstklasse, Lösen von mindestens einem linearen Programmierproblem zur Bestimmung einer Zuteilung von mindestens irgendeiner verlangten Bandbreite unter einer Menge von Leitwegen, so dass diese Zuteilung eine weitere Gütezahl WBE von Netzleistung optimiert.

2. Verfahren nach Anspruch 1, wobei der Schritt des Findens einer weiteren Zuteilung verlangter Bandbreite das Lösen eines linearen Programmierproblems umfasst, das das Minimieren eines Maßes an Betriebsmittelnutzung durch das Netz zum Ziel hat.

3. Verfahren nach Anspruch 2, wobei die linearen Programmierprobleme der Schritte (a) und (b) Flussprobleme mehrfacher Leistungsmerkmale sind.

4. Verfahren nach Anspruch 2, wobei die Gütezahl W Netzeinnahmen aus Dienstgüte-Dienst sind.

5. Verfahren nach Anspruch 2, wobei die Gütezahl WBE Netzeinnahmen aus BE-Dienst sind.

6. Verfahren nach Anspruch 2, wobei der Schritt (d) folgendes umfasst:

Lösen eines streckenbasierenden Flussproblems mehrfacher Leistungsmerkmale, um dadurch für jedes entsprechende, aus einem Ursprungsknoten und einem Zielknoten bestehende Paar Bandbreitenzuteilungen auf einzelnen Verbindungsstrecken zu bestimmen; und

Durchführen einer Flusszerlegung, um dadurch Bandbreitenzuteilungen auf entsprechenden, jedes der entsprechenden Paare verbindenden Leitwegen zu bestimmen.

7. Verfahren nach Anspruch 2, wobei:

für mindestens eine Dienstgüteklasse die zulässigen Leitwege in Schritten (a) und (b) eine vorbestimmte richtige Teilmenge aller möglichen Leitwege sind; und

der Schritt (d) ohne a priori-Einschränkung zulässiger Leitwege ausgeführt wird.

6. Verfahren nach Anspruch 2, weiterhin mit Berechnen vor dem Schritt (a) eines Bandbreitenbedarfs Tsσ in jeder Dienstgüteklasse s für jedes entsprechende, aus einem Ursprungsknoten und einem Zielknoten bestehende Paar.

9. Verfahren nach Anspruch 8, wobei jeder Bedarf TSσ aus mindestens einem Wert einer effektiven Bandbreite und aus einem Mittelwert sσ von Stromverkehrsstärke in der entsprechenden Dienstgüteklasse zwischen dem entsprechenden Ursprung-Ziel-Paar σ berechnet wird.

10. Verfahren nach Anspruch 9, wobei jeder Bedarf TSσ so berechnet wird, dass er das Verhältnis

erfüllt, wobei ds eine effektive Bandbreite in der entsprechenden Dienstgüteklasse und σ ein nicht negativer Parameter ist.

11. Verfahren nach Anspruch 10, weiterhin mit dem Berechnen eines Dienst-Leitweg-Verkehrsstärkewertes Xsr für jeden Leitweg r in jeder Dienstgüteklasse s aus entsprechenden Werten des Flussparameters Xsr, des Bedarfs Tsσ und der mittleren Stromverkehrsstärke sσ.

12. Verfahren nach Anspruch 12, wobei jeder Dienst- Leitweg-Verkehrsstärkewert ρsr so berechnet wird, dass er ein Verhältnis der Form ρsr/ρsσ = Xsr/Tsσ erfüllt.

13. Verfahren nach Anspruch 11, weiterhin mit folgendem:

für jeden Leitweg r in jeder Dienstgüteklasse s, Anwenden eines stochastischen Verkehrsmodells zum Vorhersagen einer Rate, mit der einem derartigen Leitweg angebotene Verbindungen aufgrund ungenügender Streckenkapazität blockiert werden;

Identifizieren etwaiger Leitwege, für die die Blockierungsrate unannehmbar hoch ist;

für jeden Leitweg r in einer gegebenen Dienstklasse s, die eine unannehmbar hohe Blockierungsrate aufweist, Einstellen des Wertes eines Parameters esr, der den Beitrag eines derartigen Leitweges in einer derartigen Dienstklasse zur Gütezahl W der Netzleistung ausdrückt, wobei diese Einstellung mindestens einmal ausgeführt wird und so ausgeführt wird, dass sie die entsprechende Blockierungsrate verringert; und

mindestens einmaliges Wiederholen der Schritte (a) und (b) unter Verwendung der eingestellten Werte der Parameter esr.

14. Verfahren nach Anspruch 11, weiterhin mit folgendem:

für jeden Leitweg r in einer gegebenen Dienstklasse s, die eine unannehmbar hohe Blockierungsrate aufweist, Auswählen einer Begrenzung des Gesamtbetrags an Bandbreite, der im Schritt (b) auf dem Leitweg r in der Dienstgüteklasse s zugeteilt werden kann, wobei diese Auswahl mindestens einmal ausgeführt wird und so ausgeführt wird, dass sie die entsprechende Blockierungsrate verringert; und

mindestens einmaliges Wiederholen des Schritts (b) in Abhängigkeit von der ausgewählten Begrenzung.

15. Verfahren nach Anspruch 11, wobei:

das Verfahren weiterhin das Empfangen von Anforderungen zur Leitweglenkung von Verbindungen zwischen gegebenen Ursprung-Ziel-Paaren σ in einer oder mehreren gegebenen Dienstgüteklassen s umfasst, wobei jedes derartige Paar σ im Zusammenhang mit einer entsprechenden Dienstgüteklasse als ein Strom (s, σ) zu bezeichnen ist;

jeder Strom (s, σ) eine entsprechende Menge R(s, σ) zulässiger Leitwege aufweist;

für jeden Strom (s, σ) eine Menge Flussparameter Xsr und eine Menge Dienst-Leitweg-Verkehrsstärkenwerte ρsr für entsprechende Leitwege r in der entsprechenden Leitwegmenge R(s, σ) bestimmt werden; und

das Verfahren weiterhin das Anbieten von Verbindungen an die Leitwege in R(s, σ) entsprechend der verlangten Bandbreite im Verhältnis zu den entsprechenden Dienst- Leitweg-Verkehrsstärkewerten ρsr umfasst.

16. Verfahren nach Anspruch 15, wobei der Schritt des Anbietens von Verbindungen an die Leitwege in R(s, σ) das Setzen von Gewichtskoeffizienten in einem Router mit gewichteter fairer Warteschlangenbildung umfasst und für jeden Strom (s, σ) die Gewichtskoeffizienten proportional zu den entsprechenden Dienst-Leitweg- Verkehrsstärkewerten ρsr gemacht werden.

17. Verfahren nach Anspruch 2, wobei das Verfahren weiterhin das Empfangen von Anforderungen zur Leitweglenkung von Verbindungen zwischen gegebenen Ursprung-Ziel-Paaren σ in einer oder mehreren gegebenen Dienstgüteklassen s umfasst, wobei jedes derartige Paar σ im Zusammenhang mit einer entsprechenden Dienstgüteklasse als ein Strom (s, σ) zu bezeichnen ist;

für jeden Strom (s, σ) eine Menge Flussparameter Xsr für entsprechende Leitwege r in der entsprechenden Leitwegmenge R(s, σ) bestimmt wird; und

das Verfahren weiterhin das Anbieten von Verbindungen an die Leitwege in R (s, σ) entsprechend der verlangten Bandbreite im Verhältnis zu den entsprechenden Flussparametern Xsr umfasst.

18. Verfahren nach Anspruch 17, wobei der Schritt des Anbietens von Verbindungen an die Leitwege in R(s, σ) das Setzen von Gewichtskoeffizienten in einem Router mit gewichteter fairer Warteschlangenbildung umfasst und für jeden Strom die Gewichtskoeffizienten proportional zu den entsprechenden Flussparametern Xsr gemacht werden.

19. Verfahren nach Anspruch 1, wobei für mindestens eine Dienstklasse s das Kommunikationsnetz ein oder mehrere virtuelle Privatnetze (VPN) unterstützt, wobei die verlangte Bandbreite Anforderungen in Bezug auf mindestens ein VPN enthält, die Zuteilung der verlangten Bandbreite zu Leitwegen in der Dienstklasse s anfänglich an einer Ansammlung von VPN-bezogenen Anforderungen und nicht-VPN-bezogenen Anforderungen ausgeführt wird; und das Verfahren weiterhin folgendes umfasst:

Einteilen der zugeteilten Bandbreite auf jedem zulässigen Leitweg in der Dienstklasse s in einen Anteil für VPN-Verkehr und einen Anteil für Nicht-VPN- Verkehr entsprechend den entsprechenden Beiträgen von VPN-bezogenem Bedarf und nicht-VPN-bezogenem Bedarf in Bezug auf den Gesamtbedarf zwischen den entsprechenden Ursprungs- und Zielknoten in der Dienstklasse s.

20. Verfahren nach Anspruch 19, weiterhin mit dem Verteilen des VPN-Verkehrsanteils der zugeordneten Bandbreite unter zwei oder mehreren VPN.

21. Verfahren nach Anspruch 20, wobei die zugeteilte Bandbreite im Verhältnis zu dem Bruchteil des mit jedem VPN verbundenen Gesamtbedarf unter VPN verteilt wird.

22. Verfahren nach Anspruch 20, wobei die zugeteilte Bandbreite durch heuristisches Bin Packing unter den VPN verteilt wird.