DE69706790T2

DE69706790T2 - Verfahren zur wiederverhandlung der vereinbarten verkehrsparameter während einer verbindung in einem atm-netz

Info

Publication number: DE69706790T2
Application number: DE69706790T
Authority: DE
Inventors: Samy Bengio; Fabrice Clerot; Daniel Collobert; Annie Gravey
Original assignee: France Telecom SA
Current assignee: Gula Consulting LLC
Priority date: 1996-02-23
Filing date: 1997-02-21
Publication date: 2002-05-29
Anticipated expiration: 2017-02-22
Also published as: JPH11504493A; JP3840265B2; DE69706790D1; WO1997031456A1; EP0827660B1; US6018517A; EP0827660A1; FR2745455B1; FR2745455A1

Description

Die vorliegende Erfindung betrifft ein Verfahren zum erneuten Aushandeln der Parameter eines Verkehrsvertrags eines ATM-Netzes während der Kommunikation.
Ein ATM(Asynchronous Transfer Mode)-Netz ist ein Netz, dessen Übertragung der Informationen auf der asynchronen zeitlichen Multiplexierung von Pakten von Informationen, Zellen genannt, mit fester Länge basiert. Es ist möglich auf einem solchen Netz irgendeinen Dienst, wie einen Audio-, Video- oder Datenübertragungsdienst, unabhängig von den zugehörigen Eigenschaften dieses, wie beispielsweise der Impulsrate, seinen Qualitätseigenschaften oder seiner sporadischen Beschaffenheit, zu transportieren. Aus diesen Gründen wurde diese Technik zur Übertragung von Zellen durch asynchrone Zeitmultiplexierung als Übertragungsmodus für die breitbandigen Digitalnetze mit Diensteintegration, BISDN-Netze genannt, beibehalten.
Um die Qualität des Dienstes zu gewährleisten und die von den Anwendungen geforderte Bandbreite bereitzustellen, hat es sich dennoch als notwendig erwiesen, verschiedene Kontrollen bzw. Steuerungen vorzusehen. Dies erweist sich als besonders wahr für den Verkehr mit sehr sporadischen Durchsätzen, wie denjenigen, die durch Verbindungen von lokalen Netzen untereinander verursacht werden.
Diese Kontrollen bzw. Steuerungen betreffen einerseits die Kontrollen bzw. Steuerungen der Parameter des Netzes oder die Kontrollen bzw. Steuerungen der Nutzungsparameter, die die Gesamtheit der vom Netz durchgeführten Aktionen, um den Verkehr auf einer ATM-Verbindung zu überwachen und zu steuern. Die Erfindung ist nicht von diesem Typ von Kontrollen bzw. Steuerungen betroffen. Sie betreffen andererseits die Kontrolle bzw. Steuerung der Zulassung einer Verbindung, welche darauf abzielt eine Verbindung bei der Anforderung ihres Aufbaus anzunehmen oder zurückzuweisen, je nachdem ob die Menge der verfügbaren Ressourcen den Transport der neuen Verbindung durch das gesamte Netz mit der erforderlichen Qualität des Dienstes gestattet oder nicht gestattet.
Beim Aufbau einer Verbindung wird so zwischen dem Nutzer und dem Netz ein Verkehrsvertrag abgeschlossen, der einerseits aus einem Verkehrsdeskriptor der betroffenen Verbindung und andererseits aus der erforderlichen Dienstequalitätsklasse QoS besteht. Diese Informationen werden vom Nutzer zum Zeitpunkt des Aufbaus der Verbindung beispielsweise mittells der Signalisierung bereitgestellt.
Der Verkehrsdeskriptor der im Aufbau befindlichen Verbindung kann die folgenden vier Verkehrsparameter umfassen: die maximale Zellenrate oder Spitzenrate (PCR, Peak Cell Rate), die Toleranz für die Änderung der Verzögerung der Zellen oder Jittertoleranz toPCR und eventuell die geplante Zellenrate (SCR, Sustainable Cell Rate) und ihre zugehörige Toleranz toSCR. Durch den abgeschlossenen Vertrag verpflichtet sich der Nutzer dazu, dass der Verkehr, den er sendet, dem entspricht, der durch die Parameter des Vertrags definiert ist, so wie das Netz eine Einhaltung der Rate und der Jittertoleranz sobald diese Konformität verwirklicht ist. Die Verpflichtung des Verkehrs seinem Vertrag zu entsprechen schützt so das Netz vor Stößen bzw. Anhäufungen mit unkontrolliertem Volumen und gestattet im Netz die Ressourcen zu reservieren, die für es nötig sind, um die geforderte Dienstequalität zu gewährleisten. Ausgehend von den oben genannten Verkehrsparametern wurden vier Verkehrsvertragsdefinitionen vorgeschlagen, die als Modus mit deterministischer Bitrate DBR (Deterministic Bit Rate), Modus mit statistischer Bitrate SBR (Statistica) Bit Rate), Modus mit Übertragung von ATM-Blöcken ABT (ATM Block Transfer) und Modus mit verfügbarer Datenrate ABR (Available Bit Rate) bezeichnet werden. Eine Übersicht dieser vier Definitionen ist in dem Artikel von J. Mignault, A. Gravey und C. Rosenberg mit dem Titel "A survey of straightforward multiplexing models for ATM networks" in ATM Expert RACE Symposium, 1995, gegeben. Sie bilden auch den Gegenstand der Empfehlung 1.371 von PITU-T.
Im DBR-Modus gibt die Quelle oder Nutzer zum Zeitpunkt der Verbindung einfach die maximale Zellenraten PCR an, die er während der gesamten Dauer der Kommunikation einhalten will. Die Reservierung der Ressourcen des Netzes erfolgt dann auf der Basis dieser maximalen Rate, während die Garantien der Qualität QoS in Begriffen von Verzögerung und Zellenverlustrate gegeben sind. Dieser Modus ist im Wesentlichen für Verbindungen mit konstanter Bitrate (CBR, Constant Bit Rate) bestimmt.
Für Verbindungen, die Dienste mit variabler Bitrate VBR (Variable Bit Rate) übernehmen, kann die Quelle oder der Nutzer im SE3R genannten Modus außer der Spitzenrate PCR eine unterstützte Rate SCR (Sustainable Cell Rate) angeben.
Ausgehend von den beim Vertrag ausgehandelten Verkehrsparametern ist es möglich, eine äquivalente Bandbreite des Verkehrs der betroffenen Verbindung in Abhängigkeit von der Rate der Verbindungsglieder, den im Netz verfügbaren Ressourcen und der erforderlichen Dienstequalität abzuschätzen. Die Reservierung von Ressourcen erfolgt somit im Petz auf der Basis dieser geschätzten Bandbreite.
Der ABT-Modus zielt darauf, die Dienstequalität eher bei den Rahmen als bei den Zellen zu schützen. In diesem Modus handelt die Quelle für die Dauer des Anrufs eine maximale Spitzenrate PCRmax aus und verwendet eine Aushandlung im Band. Die Reservierung der Ressourcen erfolgt dann auf der Basis des kleinsten der Werte der Spitzenrate PCR und der maximalen Spitzenrate PCRmax.
Was den ABR-Modus betrifft, ist er für Datenquellen bestimmt.
Die Konformität einer Zelle mit dem vom Nutzer abgeschlossenen Verkehrsvertrag ist mittels eines Algorithmus, wie dem Algorithmus des "löcherigen Kübels" (LB, Leaky Bucket) oder seinem Äquivalent, dem Algorithmus VS (Virtual Scheduling), definiert.
Im DBR-Modus ist der Verkehr einer Verbindung gemäß diesen Algorithmen konform, solange die Länge einer Warteschlancle, die vom Verkehr der betrachteten Verbindung gespeist und mit der ausgehandelten Spitzenrate PCR geleert wird, nicht eine maximale Länge Lmax übersteigt, die ausgehend von der angegebenen Jittertoleranz topcr mittels der folgenden Beziehung definiert ist:
Lmax = PCR x topcr.
Im SBR-Modus ist die algorithmische Definition der unterstützten Rate SCR analog zu der der Spitzenrate PCR, wenn diese nicht mit einer größeren Jittertoleranz toscr verbunden ist.
Diese Verkehrsverträge sind im allgemeinen für die gesamte Dauer der Kommunikation definiert, was die optimale Nutzung der Ressourcen des Netzes schwierig macht, vor allem im Falle von sporadischem Verkehr, der in Begriffen der Bandbreite über die gesamte Dauer einer Kommunikation schlecht definiert ist. Die Verkehrsparameter sind somit schließlich schwer über die gesamte Dauer einer Kommunikation zu definieren. Daraus ergibt sich, dass die Reservierungen von Ressourcen für eine Spitzenrate, die für die gesamte Dauer der Kommunikation gelten, unvermeidlich eine Ressourcenverschwendung bewirken, die in Begriffen der Bandbreite berechnet wird.
Ziel der Erfindung ist es, die erneute Aushandlung der Parameter der Verkehrsverträge dynamisch während der aufgebauten Kommunikation vorzusehen.
In dem Artikel mit dem Titel "A reservation principle with applications to the ATM traffic control", erschienen in COMPUTER NETWORKS AND ISDN SYSTEMS, Bd. 24, Nr. 4 vom 15. Mai 1992 beschreiben Boyer P.E, and all eine Prozedur zur Ratenreservierung, bei welcher eine Steuereinheit FRP (Fast Reservation Protocol) vom Verkehrsverwalter eines Netzes eine Reservierungsanforderungszelle (Reservation Requested Cell) empfängt, die dieser Anforderung entsprechende Rate zu reservieren versucht und je nach FaN eine Ratenannahme- (Reservation Accepted Cell) oder im Gegenteil Verweigerungszelle (Reservation Denied Cell) zurückschickt. Dieses Verfahren zur Ratenreservierung unter Ersuchen kann zum Zeitpunkt des Anrufs oder während einer Kommunikation zur Modifikation, sogar während einer Kommunikation einen Augenblick im Voraus stattfinden, wenn der anfordernde Teilnehmer für das Netz weiß, dass es zu einem gegebenen Zeitpunkt einen zu übertragenden Ratenpeak gibt.
In dieser Druckschrift ist die Grundlage der Reservierung ein Ersuchen des anfordernden Netzes. Nun aber ist das Ziel der vorliegenden Erfindung vorzuschlagen, dass die Grundlage dieser erneuten Aushandlung der Verkehr selbst ist, was das Problem der Vorhersage der Bedürfnisse der Quelle für die Geltungsdauer des oder der zukünftigen Verträge stellt.
In einem Artikel, der in Computer communications, Bd. 18, vom 8. August 1995 erschienen ist und den Titel "Traffic prediction and dynamic bandwidth allocation over ATM: a neural network approach" trägt, beschreiben Moh and all die Verwendung von Neuronennetzen, um die Bandbreite vorherzusagen, die zum Zeitpunkt der erneuten Aushandlung und Zuweisung der vorhergesagten Bandbreite erforderlich ist. Nun wird in diesem Artikel aber nicht die Tatsache berücksichtigt, dass sich die erneute Aushandlung nicht die Bandbreite sondern die oben erwähnten Verkehrsparameter betrifft.
Ziel der Erfindung ist es somit, die erneute Aushandlung der Parameter der Verkehrsverträge dynamisch während der aufgebauten Kommunikation unter Berücksichtigung der Tatsache vorzusehen, dass sich diese erneute Aushandlung auf die Verkehrsparameter bezieht.
Um diese Ziele zu erreichen, schlägt die Erfindung ein Verfahren zur erneuten Aushandlung gemäß den Merkmalen des Anspruchs 1 vor.
Ein Verfahren zur erneuten Aushandlung der Parameter des eine Kommunikation auf einem ATM-Netz betreffenden Verkehrsvertrages während dieser Kommunikation gemäß der Erfindung besteht darin:
a) für einen vorher bestimmten Zeitraum zwischen zwei aufeinanderfolgenden erneuten Aushandlungen die maximale Länge vorherzusagen, die eine durch den Verkehr dieser Kommunikation gespeiste virtuelle Schlange für wenigstens eine gegebene Ausgangsrate dieser Schlange erreicht,
b) aus der maximalen Länge einen neuen oder neue Parameter des Verkehrsvertrags herzuleiten, und
c) mit dem Netz auf der Basis des oder der Verkehrsparameter für den Zeitraum erneut zu verhandeln.
Gemäß einer vorteilhaften Variante besteht es darin:
a) für einen vorher bestimmten Zeitraum zwischen zwei aufeinanderfolgenden erneuten Aushandlungen die Gesamtheit der Maximalwerte der Länge vorherzusagen, die eine durch den Verkehr der Kommunikation gespeiste virtuelle Schlange für eine Gesamtheit der konstanten Werte der Ausgangsrate dieser Schlange erreicht,
b) aus diesen Werten der Länge der Schlange und diesen entsprechenden Ratenwerten einen neuen oder neue Parameter des Verkehrsvertrags herzuleiten, und
c) mit dem Netz auf der Basis des oder der Verkehrsparameter für den Zeitraum erneut zu verhandeln.
Gemäß einem weiteren Merkmal der Erfindung wird der Herleitungsschritt des Schritts b) für neue Parameter des Verkehrsvertrages in Abhängigkeit von im Verkehrsvertrag mit dem Netz angegebenen Werten der Jittertoleranz auf dem Verkehr durchgeführt.
So kann die erneute Aushandlung des Schrittes c) in einem Modus erfolgen, in dem der einzige erneut auszuhandelnde Parameter des Verkehrsvertrags die Zellenspitzenrate PCR ist. Für die Herleitung des Schrittes b) wird dann die Spitzenrate mit Hilfe der folgenden Beziehung bestimmt:
Lmax (PCR) = toPCR x PCR
in welcher toPCR die Jittertoleranz in diesem Modus und Lmax (PCR) der vorhergesagte Maximalwert der Länge der virtuellen Schlange für den Wert der Ausgangsrate gleich PCR darstellt.
Die erneute Aushandlung des Schrittes c) kann auch in einem Modus erfolgen, in dem die Parameter des Verkehrsvertrages einerseits die Zellenspitzenrate PCR und andererseits die geplante Zellenrate SCR sind . In diesem Fall wird für die Herleitung des Schrittes b) die Spitzenrate mit Hilfe der folgenden Beziehung:
Lmax (PCR) = toPCR x PCR
und die geplante Rate mit Hilfe der folgenden Beziehung bestimmt:
Lmax (SCR) = toSCR x SCR
in welchem topcR die Jittertoleranz für die Rate PCR in diesem Modus, toSCR die Jittertoleranz für die Rate SCR in diesem Modus, Lmax (PCR) den vorhergesagten Maximalwert der Länge der virtuellen Schlange für den Wert der Ausgangsrate gleich PCR und Lmax (SCR) den vorhergesagten Maximalwert der Länge der virtuellen Schlange für den Wert der Ausgangsrate gleich SCR darstellt.
Die erneute Aushandlung des Schritts c) kann noch in einem Modus erfolgen, in dem die Parameter des Verkehrsvertrages die Spitzenrate PCR und die maximale Spitzenrate PCRmax umfassen, wobei der kleinste Wert unter den beiden Werten der Raten als Basis für die erneute Aushandlung dient.
Der Schritt a) der Vorhersage kann ausgehend von dem Wert, der von der Länge der virtuellen Schlange zum Zeitpunkt der erneuten Aushandlung angenommen wird, von dem Wert, der von der Ausgangsrate der Schlange in dem Zeitraum angenommen wird, der dem Zeitpunkt der erneuten Aushandlung vorhergeht, und von Informationen durchgeführt werden, die den Verkehr in wenigstens dem Zeitraum charakterisieren, der dem Zeitpunkt der erneuten Aushandlung vorhergeht.
Diese den Verkehr charakterisierenden Informationen werden beispielsweise erhalten, indem eine vorher bestimmte Anzahl von aufeinanderfolgenden Zeitintervallen berücksichtigt wird, die dem Zeitpunkt der erneuten Aushandlung vorhergehen, und indem in jedem Zeitintervall der von wenigstens einer charakteristischen Größe des Verkehrs angenommene Wert bestimmt wird, wobei die Gesamtheit der so erhaltenen Werte die Informationen bilden.
Bei einer Ausführungsvariante wird die zeitliche Folge betrachtet, die von der Gesamtheit der von der oder den charakteristischen Größen des Verkehrs in den Zeitintervallen angenommenen Werte gebildet wird, und werden die ersten Momente der zeitlichen Folge bestimmt, wobei diese Momente dann die den Verkehr charakterisierenden Informationen bilden. Die Momente der zeitlichen Folge, die verwendet werden, sind beispielsweise der Mittelwert und die Varianz.
Die charakteristische(n) Größe oder Größen des Verkehrs können die Anzahl der Bits oder der Zellen des Verkehrs in jedem Zeitintervall sein oder umfassen. Sie können auch die Ankunftszeit zwischen zwei aufeinanderfolgenden Zellen des Verkehrs sein oder umfassen.
Für den Vorhersageschritt wird vorteilhafterweise ein Neuronennetz verwenden, das eine Lernzelle aufweist, die dazu bestimmt ist, ihm die Gewichtungen jeder seiner Neuronen nach Bestimmung dieser Gewichtungen zur Verfügung zu stellen, wobei diese Bestimmung über eine vorher bestimmte Dauer ausgehend vom. Verkehr der betroffenen Verbindung erfolgt.
Die oben genannten Merkmale der Erfindung sowie weitere erscheinen deutlicher beim Lesen der nachfolgenden Beschreibung eines Ausführungsbeispiels, wobei die Beschreibung in Verbindung mit den beigefügten Zeichnungen gegeben wird, unter denen:
Fig. 1a und 1b Blockdiagramme sind, die die verschiedenen Modi der Durchführung eines erfindungsgemäßen Verfahrens zur erneuten Aushandlung darstellen,
Fig. 2 eine Kurve ist, die die Entwicklung der Länge einer vom Verkehr gespeisten Schlange in Abhängigkeit von der Zeit zeigt,
Fig. 3 eine Kurve ist, die die Bestimmung der Verkehrsparameter zeigt,
Fig. 4 ein Graf ist, der zwei Kurven zeigt, die durch Durchführung eines erfindungsgemäßen Verfahrens bzw. eines Verfahrens mit "Orakel" erhalten wurden, wobei diese Kurven für eine erneute Aushandlung im DBR-Modus erhalten wurden,
Fig. 5a und 5b Kurven sind, die unter ähnlichen Bedingungen wie denjenigen von Fig. 4 aber für eine erneute Aushandlung im SBR-Modus gezeichnet wurden, und
Fig. 6 eine Tabelle ist, die den Nutzen der erneuten Aushandlung während der Kommunikation darstellt.
In Fig. 1a wurde ein Blockdiagramm dargestellt, das das Verfahren der Erfindung darstellt. In dieser Fig. 1a ist eine einem Algorithmus des "löcherigen Kübels" oder Leaky Bucket entsprechende virtuelle Warteschlange 10 zu sehen, die während der Verarbeitung vom Verkehr Trc der Verbindung gespeist wird und deren Ausgangsrate R ist.
Bei einer Ausführungsform der Erfindung ist die Länge der Schlange 10 nicht übergeordnet eingeschränkt. So fällt keine Zelle durch Überlaufen dieser Schlange weg.
Im Folgenden der Beschreibung wird Zeit t&sub0; die Zeit genannt, zu der jede erneute Aushandlung der Verkehrsparameter stattfindet und dies für den Zeitraum, der sich somit von t&sub0; bis t&sub0; + T erstreckt, wobei T der Zeitraum zwischen zwei aufeinanderfolgenden erneuten Aushandlungen ist. Dieser Zeitraum T beträgt beispielsweise zehn Sekunden.
Zum Zeitpunkt t&sub0; der erneuten Aushandlung liefert die Schlange 10 den Wert der Schlangenlänge X(t&sub0;) sowie den Wert der Ausgangsrate R(t&sub0;&supmin;). Der Wert R(t&sub0;&supmin;) ist der Wert der Rate am Ausgang der Schlange 10 zum Zeitpunkt t&sub0; aber bevor die erneute Aushandlung stattfindet.
Die beiden Werte X(t&sub0;) und R(t&sub0;&supmin;) werden zwei entsprechenden Eingängen eines Prediktors 20 zur Verfügung gestellt, von dem ein dritter Eingang eine Information empfängt, die den Verkehr vor dem Zeitpunkt t&sub0; charakterisiert und die von einem Element 30 bereitgestellt wird. Um diese Information liefern zu können, empfängt das Element 30 auf seinem Eingang den Verkehr Trc der Verbindung während der Verarbeitung.
Gemäß einer Ausführungsform der Erfindung wird zur Durchführung der Funktion des Elements 30 jedes Zeitintervall (t&sub0;, t&sub0; + T) zwischen zwei aufeinanderfolgenden Aushandlungen zeitlich in mehrere gleiche aufeinanderfolgende Zeit-Unterintervalle zerschnitten und für jedes der Zeit- Unterintervalle der von wenigstens einer charakteristischen Größe des Verkehrs Trc, wie beispielsweise die Bitzahl N dieses Verkehrs, die Laufzeit t zwischen zwei Zellen, usw., angenommene Wert bestimmt. Wenn G der von dieser Größe oder diese Vereinigung von Größen (G = {N, t, ..., }) angenommene Wert genannt wird, wird so eine zeitliche Folge S des Verkehrs Trc, die gleich {G(J), G(2), ..., G(i), ..., G(n)} ist, worin die Indices i = 1 bis n die laufende Nummer der Zeit = Unterintervalle darstellen.
Als Beispiel wurde jedes Zeitintervall von 10 Sekunden in hundert Zeit- Unterintervalle zerschnitten und als charakteristische Größe des Verkehrs die Bitanzahl in jedem dieser Zeit-Unterintervalle betrachtet.
Bei einer ersten Ausführungsform der Erfindung wird dann dem Prädiktor 20 direkt die zeitliche Folge S zur Verfügung gestellt.
Bei einer zweiten Ausführungsform werden anstatt der Lieferung der zeitlichen Folge 5 nur die ersten Momente der zeitlichen Folge, nämlich der Mittelwert und die Varianz, geliefert. Diese Lösung ist gegenüber der vorhergehenden vorteilhaft, weil sie die Anzahl der Eingänge des Prädiktors 20 uns somit seine Komplexität begrenzt.
Bei weiteren Ausführung formen werden außer den beiden ersten Momenten der zeitlichen Folge S die Momente höherer Ordnung geliefert.
Der Ausgang des Prädiktors 20 liefert eine Gesamtheit von vorhergesagten Werten Lmax (R) der maximalen Länge, die die Schlange erreicht, wenn sie während des Zeitraums (t&sub0;, t&sub0; + T), der dem Zeitpunkt t&sub0; folgt, mit verschiedenen konstanten Werten ihrer Ausgangsrate R geleert wird.
Fig. 1c stellt ein Verfahren der Erfindung ähnlich demjenigen dar, das in Verbindung mit Fig. 1a und 1b beschrieben ist, aber dessen Prädiktor ein Neuronennetz 20', beispielsweise vom Mehrschicht-Perceptron-Typ, insbesondere mit drei Schichten ist: einer Eingangsschicht, einer verborgenen Schicht und einer Ausgangsschicht, die in an sich bekannter Weise durch Synapsen verbunden sind. Dieses Neuronennetz weist drei Eingänge, einen einzigen Ausgang auf und die Anzahl von Neuronen auf der verborgenen Schicht kann zwischen 5 und 10 variieren.
Zum Lernen weist das Neuronennetz 20' eine Lernzelle 50 mit drei Eingängen auf, die die Rate R(t&sub0;&supmin;) zum Zeitpunkt t&sub0;&supmin;, die Länge X(t&sub0;) der Schlange 10 zum Zeitpunkt t&sub0; bzw. eine Information empfangen, die den Verkehr vor dem Zeitpunkt t&sub0; charakterisiert und die von einem mit dem Element 30 identischen Element 60 bereitgestellt wird. Um diese Information liefern zu können, empfängt das Element 60 auf seinem Eingang den Verkehr Trc der Verbindung während der Verarbeitung, Es weist noch ein Rechenelement 70 für die maximale Länge Lmax (R) der Schlange 10 in Abhängigkeit von der Rate R auf. Dieses Rechenelement 70 ist mit der Lernzelle 50 verbunden.
Die Lernzelle 50 ist beispielsweise wird beispielsweise in einem Algorithmus zum Lernen durch Rückausbreitung des Fehlers betrieben.
Die Lernzelle 50 bestimmt nach Empfang der Elemente, die ihr an ihren Eingängen zur Verfügung gestellt werden, zu jedem Zeitpunkt % die Gewichtungen w&sub1; jedes Neurons des Neuronennetzes 20' und dies während einer vorher bestimmten Dauer und gibt sie nach dieser vorher bestimmten Dauer in das Netz 20 ab. Es handelt sich dabei um den Lernvorgang.
Dieser Vorgang der Schätzung der Gewichtungen des Netzes durch Lernen kann sehr lange dauern, wobei das Problem NP-vollständig (NP-complet) ist. Aber es können dennoch suboptimale Parameter in polymonen Zeiten (temps polymoniaux) gefunden werden.
Es wird bemerkt, dass der Lernvorgang auf dem Verkehr Trc aber nicht in Echtzeit betrieben wird.
Die Gesamtheit von vorhergesagten Werten (R), die vom Prädiktor 20 oder dem Neuronennetz 20' geliefert wird, wird einer Einheit 40 zur Bestimmung der Verkehrsparameter zur Verfügung gestellt, die in Abhängigkeit von den zum Zeitpunkt des Aufbaus der Verbindung festgesetzten Parametern, die die angegebene Jittertoleranz tOPCR bzw. die geplante Jittertoleranz toSCR sind, die die Qualität QoS der Verbindung definieren, die Werte der Parameter liefert, die den Gegenstand der erneuten Aushandlung des Verkehrsvertrags für den sich von t&sub0; bis t&sub0; + T erstreckenden Zeitraum bilden. Diese Vertragsparameter sind die Spitzenrate PCR im Modus mit deterministischer Bitrate DBR bzw. im Modus mit statistischer Bitrate SBR die Spitzenrate FCR und die geplante Räte SCR. Im Modus mit Übertragung von ATM-Blöcken ABT wird auch die maximale Spitzenrate PCRmax hinzugefügt.
Es wird bemerkt, dass im ABT-Modus der Zeitraum für die erneute Aushandlung des Verkehrsparameters PCR kürzer als derjenige für den Parameter PCRmax ist. Wenn beispielsweise der Zeitraum für die Bestimmung des Parameters PCRmax zehn Sekunden beträgt, beträgt er für die Bestimmung des Parameters PCR nur eine Sekunde. Es wird daran erinnert, dass die erneute Aushandlung auf dem kleinsten der beiden Werte, nämlich min(PCR, PCRmax), erfolgt.
In Fig. 2 und 3 wird der Schritt des Verfahrens der Erfindung veranschaulicht, der von der Einheit 30 durchgeführt wird.
In Fig. 2 sieht man die Kurve, die die Variation der Länge X der Schlange 10 in Abhängigkeit von der Zeit darstellt. Bis zum Zeitpunkt t&sub0; der erneuten Aushandlung ist die Kurve in durchgezogener Linie, um zu zeigen, dass dies die Länge wie sie war ist, die dargestellt ist. Nach dem Zeitpunkt t&sub0; unterteilt sich die Kurve in zwei Kurven für zwei Raten am Ausgang der Schlange 10, die die konstanten Werte R1 bzw. R2 annehmen. Diese beiden Kurventeile sind in punktierten Linien gezeichnet, um zu zeigen, dass es sich um die Länge der Schlange handelt, wie sie tatsächlich nach der Zeit t&sub0; für Ausgangsraten R1 bzw. R2 wäre: So ist der Beobachter an den Zeitpunkt t&sub0; gesetzt. Was den Prädiktor 20 oder 20' angeht, kann er für jede Rate R die maximalen Schlangenlängen Lmax (R) vorhersagen. Es wurden die vorhergesagten maximalen Schlangenlängen Lmax (R1) und Lmax (R2) dargestellt.
In Fig. 3 ist eine Kurve dargestellt, die die maximale Länge Lmax (R) der Schlange zeigt, die die Schlange 10 während des Zeitraums t&sub0; + T erreichen kann, und dies in Abhängigkeit von der Rate R am Ausgang der Schlange 10. Als Beispiel wurden die Punkte angebracht, die den Raten R1 und R2 von Fig. 2 entsprechen.
Die Werte der Spitzenrate PCR und der geplanten Rate SCR sind die durch die Rate am Schnittpunkt der die Funktion Lmax (R) darstellenden Kurve mit einerseits der Geraden der Gleichung Lmax - R x topcr bzw. andererseits der Geraden der Gleichung Lmax = R x toscr genommenen Werte. So ist der Wert der Spitzenrate PCR der Wert von R, der die Beziehung bestätigt:
Lmax (R) = R x topcr. (1)
Ebenso ist der Wert der Spitzenrate SCR der Wert von R, der die Beziehung bestätigt:
Lmax (R) = R x toscr. (2)
Wie festgestellt werden kann, stellten diese Werte PCR und SCR im Netz sicher, dass die Verbindung mit dem Verkehrsvertrag konform ist, da ja diese Konformität genau durch die Beziehungen (1) und (2) oben definiert ist.
Was dennoch voraussetzt, dass die Vorhersage richtig ist. Im Folgenden der Beschreibung wird gezeigt, dass sie es tatsächlich ist.
Unten werden die Simulationsergebnisse der erneuten Aushandlung von Verkehrsverträgen gegeben, die das erfindungsgemäße Verfahren ausführen. Diese Simulationen wurden ausgehend von einer Spur wirklichen Verkehrs durchgeführt, die in einer Aufzeichnung von zwei Stunden des Verkehrs TCP am Gateway des Lawrence Berkeley Laboratory zum Netz Internet besteht. Diese Spur bildet den Gegenstand einer Studie, die in der Zeitschrift Proc.Sigcomm '94, Computer Communication Review, 24 (1994), auf den Seiten 257-268 in einem Artikel mit dem Titel "Wide area traffic the failure of Poisson modelung" von V. Paxson und 5. Floyd veröffentlicht wurde. Diese Spur wurde aus dem Grund gewählt, weil sie den Verkehr gut darstellt, mit dem im Rahmen der Verbindung von lokalen Netzen untereinander gerechnet werden muss.
Für den Algorithmus des virtuellen Abstands wurden die folgenden Jitterparameter verwendet: toPCR = 0,1 s und toSCR = 1 s.
Im Falle des Modus mit deterministischer Bitrate DBR wird die Zellenspitzenrate PCR zu jeder Zeit t&sub0; für den nächsten Zeitraum mit einer Dauer von 10 s vorhergesagt. Wie bereits erwähnt erfolgt die Reservierung der Ressourcen zum Zeitpunkt der erneuten Aushandlung auf der Basis dieser Spitzenrate PCR. Im Folgenden der Beschreibung wird dieser erneut ausgehandelte Vertrag DBR-10 s genannt.
Im ABT-Modus wird die maximale Spitzenrate PCRmaX für den nächsten Zeitraum von 10 s sowie die Spitzenrate PCR alle Sekunden vorhergesagt. Die Reservierung wird auf Basis des kleinsten Wertes unter PCR und PCRmax vorgenommen. Dieser Vertrag wird ABT-10 s genannt.
Beim Modus mit statistischer Bitrate SBR werden die Spitzenrate PCR und die unterstützte Rate SCR zu jeder Zeit t&sub0; für den nächsten Zeitraum von 10 s vorhergesagt. Unter Berücksichtigung einer zulässigen Zellenverlustrate CLR von 10&supmin;&sup9;, einer Größe der Schlange B von 1 Mbit und einer Verbindungsgliedrate R von 155 Mbit/s wird durch Berechnung ausgehend von den Raten PCR und SCR das äquivalente Band hergeleitet und erfolgt die Reservierung auf der Basis dieses Bandes. Dieser Vertrag wird SBR-10 s genannt.
Im Folgenden der Beschreibung werden bei jedem der oben genannten Modi die Leistungen des Verfahrens der Erfindung mit der vom Prädiktor 20 oder 20' durchgeführten Vorhersage mit denjenigen eines "Orakels" verglichen, das das gleiche Verfahren mit Ausnahme der Bestimmung der Länge Lmax(R) durchführt, die nicht vorhergesagt sondern ausgehend von wirklichen Daten der nächsten Zeiträume, die er bereits empfangen hat, erhalten wird.
In Fig. 4 wurden zwei Kurven im selben Grafen dargestellt, die entsprechend die Entwicklungen der in Megabits pro Sekunde ausgedrückten Raten mit einer erneuten Aushandlung im DBR-Modus, die einerseits, in durchgezogener Linie, gemäß dem Verfahren der Erfindung mit Vorhersage bei zehn Sekunden und andererseits, in Punktierungen, mit "dem Orakel", das mit wirklichen Daten arbeitet, durchgeführt wurde, in Abhängigkeit von der Zeit zeigt. Diese Kurve wurde in einem Teil der oben genannten Spur gezeichnet, der der sporadischste ist.
Wie festgestellt werden kann liegen die Werte der erwarteten Raten und die Kurvendynamiken, die mit Vorhersage bzw. mit dem Orakel erhalten werden, obwohl sie sich punktuell unterscheiden, sehr nahe beieinander. Es kann somit geschlossen werden, dass es möglich ist bei einem Horizont von 10 Sekunden ausreichend genaue Vorhersagen zu treffen, um einen Vertrag vom DBR-Typ erneut auszuhandeln.
In Fig. 5a wurden zwei Kurven dargestellt, die eine irr durchgezogener Linie, die andere in punktierter Linie, die den beiden Kurven von Fig. 4 ähnlich sind, aber für eine erneute Aushandlung im SBR-Modus, und dies für denselben Teil derselben Spur. Fig. 5b zeigt auch die entsprechenden beiden Kurven der Entwicklungen der Länge der virtuellen Schlange in Abhängigkeit von der Zeit mit Vorhersage bzw. mit dem Orakel.
Es kann festgestellt werden, dass das Verfahren mit Vorhersage ausgezeichnete Ergebnisse erhält, was die Mittelwerte betrifft, aber dass diese Ergebnisse für die angenommenen Maximalwerte etwas weniger gut sind. Es wird jedoch bemerkt, dass die Dynamiken der äquivalenten Bänder, die mit dem Orakel und dem Prädiktor erhalten werden, dennoch sehr nahe beieinander liegen. Es kann somit geschlossen werden, dass tatsächlich bei einem Horizont von 10 Sekunden ausreichend genaue Vorhersagen getroffen werden können, um einen Vertrag im SBR-Modus erneut auszuhandeln.
Fig. 6 zeigt eine Tabelle, die einerseits in einem DBR-10 s genannten Modus und andererseits in einem DBR-Modus ohne erneute Aushandlung für eine gegebene mittlere Rate Rmean die notwendige maximale Länge der Schlange, umgekehrt für eine gewünschte gegebene mittlere Länge Lmean die erhaltene mittlere Rate Rmean und für eine gewünschte maximale Länge Lmaxie erhaltene mittlere Rate Rmean erfasst.
Diese Tabelle stellt den Nutzen dar, den es beim erneuten Aushandeln eines Vertrags im Falle von sporadischem Verkehr gibt. Es kann in der Tat festgestellt werden, dass die erneute Aushandlung eine Einsparung für die Ressourcen gestattet.
Es wird bemerkt, dass die Anwendung des Verfahrens der Erfindung nicht auf die Nutzerschnittstelle (auf Englisch: User Network Interface UNI) beschränkt ist, sondern bei allen Schnittstellen des Netzes, wie beispielsweise der Zwischennetzschnittstelle (NNI Network Node Interface), üblich sein kann.

Claims

1. Verfahren zur erneuten Aushandlung der Parameter des eine Kommunikation auf einem ATM-Netz betreffenden Verkehrsvertrages während dieser Kommunikation, dadurch gekennzeichnet, dass es darin besteht:

a) für einen vorher bestimmten Zeitraum zwischen zwei aufeinanderfolgenden erneuten Aushandlungen die Gesamtheit der Maximalwerte der Länge vorherzusagen, die eine durch den Verkehr der Kommunikation gespeiste virtuelle Schlange für eine Gesamtheit der konstanten Werte der Ausgangsrate dieser Schlange erreicht,

b) aus den Werten der Schlangenlänge und den Werten der entsprechenden Rate in Abhängigkeit von den Parametern der im Verkehrsvertrag mit dem Netz angegebenen und/oder geplanten Jittertoleranz neue Vertragsparameter, wie die Spitzenrate, die geplante Rate und/oder die maximale Spitzenrate gemäß dem Modus des Vertrages herzuleiten, und

c) mit dem Netz auf der Basis des oder der Parameter des Verkehrsvertrags für den Zeitraum erneut zu verhandeln.

2. Verfahren zur erneuten Aushandlung nach Anspruch 1, dadurch gekennzeichnet, dass es im Schritt a) darin besteht nur den Wert der Länge, den eine vom Verkehr der Kommunikation gespeiste virtuelle Schlange erreicht, für eine einzige gegebene Ausgangsrate der Schlange vorauszusagen.

3. Verfahren zur erneuten Aushandlung nach Anspruch 1 oder 2, dadurch gekennzeichnet, dass die erneute Aushandlung des Schritts c) in einem Modus durchgeführt wird, bei dem der einzige erneut auszuhandelnde Parameter des Verkehrsvertrages die Zellenspitzenrate PCR ist und dass für die Herleitung des Schrittes b) die Spitzenrate mit Hilfe der folgenden Beziehung bestimmt wird:

Lmax (PCR) = toPCR x PCR

in welcher toPCR die Jittertoleranz in diesem Modus und Lmax (PCR) der vorhergesagte Maximalwert der Länge der virtuellen Schlange für den Wert der Ausgangsrate gleich PCR darstellt.

4. Verfahren zur erneuten Aushandlung nach Anspruch 1 oder 2, dadurch gekennzeichnet, dass die erneute Aushandlung des Schnitts c) in einem Modus durchgeführt wird, bei dem die Parameter des Verkehrsvertrages einerseits die Zellenspitzenrate PCR und andererseits die geplante Zellenrate SCR sind, und dass für die Herleitung des Schrittes b) die Spitzenrate mit Hilfe der folgenden Beziehung bestimmt wird:

Lmax (PCR) = toPCR x PCR

und die geplante Rate mit Hilfe der folgenden Beziehung bestimmt wird:

Lmax (SCR) = toSCR · SCR

in welchem toPCR die Jittertoleranz für die Rate PCR in diesem Modus, toSCR die Jittertoleranz für die Rate SCR in diesem Modus, Lmax (PCR) den vorhergesagten Maximalwert der Länge der virtuellen Schlange für den Wert der Ausgangsrate gleich PCR und Lmax (SCR) den vorhergesagten Maximalwert der Länge der virtuellen Schlange für den Wert der Ausgangsrate gleich SCR darstellt.

5. Verfahren zur erneuten Aushandlung nach Anspruch 3 oder 4, dadurch gekennzeichnet, dass die erneute Aushandlung des Schritts c) in einem Modus erfolgt, in dem die Parameter des Verkehrsvertrages die Spitzenrate PCR und die maximale Spitzenrate PCRmax umfassen, wobei der kleinste Wert unter den beiden Werten der Raten als Basis für die erneute Aushandlung dient.

6. Verfahren zur erneuten Aushandlung nach einem der vorhergehenden Ansprüche, dadurch gekennzeichnet, dass der Schritt a) der Vorhersage ausgehend von dem Wert, der von der Länge der virtuellen Schlange zum Zeitpunkt der erneuten Aushandlung angenommen wird, von dem Wert, der von der Rate am Ausgang der Schlange in dem Zeitraum angenommen wird, der dem Zeitpunkt der erneuten Aushandlung vorhergeht, und von Informationen durchgeführt wird, die den Verkehr in wenigstens dem Zeitraum charakterisieren, der dem Zeitpunkt der erneuten Aushandlung vorhergeht.

7. Verfahren zur erneuten Aushandlung nach Anspruch 6, dadurch gekennzeichnet, dass die den Verkehr charakterisierenden Informationen erhalten werden, indem eine vorher bestimmte Anzahl von aufeinanderfolgenden Zeitintervallen berücksichtigt wird, die dem Zeitpunkt der erneuten Aushandlung vorhergehen, und indem in jedem Zeitintervall der von wenigstens einer charakteristischen Größe des Verkehrs angenommene Wert bestimmt wird, wobei die Gesamtheit der so erhaltenen Werte die Informationen bildet.

8. Verfahren zur erneuten Aushandlung nach Anspruch 6, dadurch gekennzeichnet, dass die den Verkehr charakterisierenden Informationen erhalten werden, indem eine vorher bestimmte Anzahl von aufeinanderfolgenden Zeitintervallen berücksichtigt wird, die dem Zeitpunkt der erneuten Aushandlung vorhergehen, indem in jedem Zeitintervall der von wenigstens einer charakteristischen Größe des Verkehrs angenommene Wert bestimmt wird, wobei die Gesamtheit der so erhaltenen Werte eine zeitliche Folge bildet und indem die ersten Momente der zeitlichen Folge bestimmt werden, die dann die Informationen bilden.

9. Verfahren nach Anspruch 8, dadurch gekennzeichnet, dass die Momente der zeitlichen Folge, die verwendet werden, der Mittelwert und die Varianz sind.

10. Verfahren zur erneuten Aushandlung nach Anspruch 7, 8 oder 9, dadurch gekennzeichnet, dass die charakteristische(n) Größe oder Größen des Verkehrs die Anzahl der Bits oder der Zellen des Verkehrs in jedem Zeitintervall ist oder umfasst.

11. Verfahren zur erneuten Aushandlung nach Anspruch 9 oder 10, dadurch gekennzeichnet, dass die charakteristische(n) Größe oder Größen des Verkehrs die Laufzeit zwischen zwei aufeinanderfolgenden Zellen des Verkehrs ist oder umfasst.

12. Verfahren nach einem der vorhergehenden Ansprüche, dadurch gekennzeichnet, dass für den Vorhersageschritt wird ein Neuronennetz verwendet wird, wobei das Neuronennetz eine Lernzelle aufweist, die dazu bestimmt ist, ihm die Gewichtungen jeder seiner Neuronen nach Bestimmung dieser Gewichtungen zur Verfügung zu stellen, wobei diese Bestimmung über eine vorher bestimmte Dauer ausgehend vom Verkehr der betroffenen Verbindung erfolgt.