DE69736623T2

DE69736623T2 - Paketvermitteltes Kommunikationssystem und Verfahren zur Verkehrsformung

Info

Publication number: DE69736623T2
Application number: DE69736623T
Authority: DE
Inventors: Joseph B. Mountain View Lyles
Original assignee: Xerox Corp
Current assignee: Xerox Corp
Priority date: 1996-06-27
Filing date: 1997-06-27
Publication date: 2006-12-21
Anticipated expiration: 2017-06-28
Also published as: EP0817433A2; EP0817433B1; EP0817433A3; DE69736623D1

Description

Die vorliegende Erfindung betrifft paketvermittelte Kommunikationssysteme und im Speziellen das Traffic-Shaping, so dass zeitmultiplexierte Paketströme an Warteschlangen-Punkten innerhalb solcher Systeme oder Systemelemente veranlasst werden, sich speziellen Traffic-Deskriptoren anzupassen.
A. Traffic-Contracts/Definitionen
Ein solches System wird beispielsweise in „Feedback control of multiloop ABR traffic in presence of CBR/ABR traffic transmission", IEEE International Conference on Communications, 23.–27. Juni 1996, Dallas, Tx, USA, S. 1717–1721 dargelegt.
Die meisten Anwendungen, die aktuell auf paketvermittelten Kommunikationsnetzwerken laufen, funktionieren unabhängig von der Bandbreite, die sie erhalten, akzeptabel, da sie „elastische" Bandbreitenanforderungen haben. Die Dienstklassen, die diese Anwendungen unterstützen, sind innerhalb der Internetgemeinschaft als „Best Efforts" Service und in der Breitband-ISDN/ATM-Gemeinschaft als „Available Bit Rate" (ABR) bekannt.
Es besteht jedoch eine wachsende Nachfrage nach Netzwerkdiensten, die Verzögerungsvarianzen bereitstellen (im ATM-Kontext oft als Zellverzögerungsschwankung bezeichnet). Diese Art des Dienstes ist zum Beispiel für Echtzeitanwendungen wie Circuit-Emulation und Video erforderlich. Es ist unklar, ob und wie die Internetgemeinschaft auf diese Anforderung reagieren wird, aber die Breitband-ISDN/ATM-Gemeinschaft hat mit der Einführung der Idee eines zwischen dem Teilnehmer und dem Netz vermittelten Traffic-Contracts reagiert.
Bekanntermaßen wird ein Teilnehmer-Netzwerk-ATM-Contract durch einen Traffic-Deskriptor definiert, der Traffic-Parameter, Toleranzen und Dienstgüteanforderungen einschließt. Für jeden der relevanten Traffic-Parameter wird eine Konformitätsdefinition festgelegt. ATM-Dienste können diese Traffic-Parameter und deren zugehörige Konformitätsspezifikationen entsprechend verwenden, um verschiedene Kombinationen der Dienstgüteziele und Multiplexierungsmodelle zu unterstützen. Der Sektor für Telekommunikationsstandardisierung der International Telecommunications Union (ITU-T) und das ATM-Forum haben sich teilweise überschneidende Gruppen von ATM-Traffic-Klassen definiert. In einigen Fällen wurden Traffic-Klassen mit grundsätzlich identischen Attributen von den beiden Gruppen verschiedene Bezeichnungen zugewiesen, daher führt die folgende Tabelle bestehende übereinstimmende Entsprechungen an:
Ein ATM-Dienstvertrag für eine virtuelle ATM-Kanal-Verbindung (VCC – Virtual Circuit Connection) oder eine virtuelle ATM-Pfad-Verbindung (VPC – Virtual Path Connection) kann mehrere Parameter enthalten, die die Service Rate der Verbindung beschreiben. Diese beinhalten maximale Zellenrate (PCR – Peak Cell Rate), mittlere Zellenrate (SCR – Sustainable Cell Rate), Intrinsic Burst Tolerance (IBT) und minimale Zellenrate (MCR – Minimum Cell Rate). Nicht alle dieser Parameter sind für jede Verbindung oder jede Dienstklasse relevant, sind sie jedoch implizierte oder speziell festgelegte Elemente des Dienstvertrages, müssen sie eingehalten werden. Im Mittelpunkt der folgenden Beschreibung stehen virtuelle ATM-Kanal-Verbindungen, es wird jedoch ersichtlich sein, dass virtuelle ATM-Pfad-Verbindungen ebenso spezifiziert werden können. Die Datentransporteinheit für eine ATM-Verbindung wird normalerweise als Zelle" bezeichnet. In dieser Beschreibung wird jedoch in Bezug auf die Datentransporteinheit gelegentlich der Begriff Paket" verwendet, da sich diese allgemeinere Terminologie in Einklang mit den weit gefassteren Aspekten der Innovationen befindet.
Der in der ITU-T-Empfehlung 1.371 festgelegte Generic Cell Rate Algorithm (GCRA) ist für das Testen eines Paket- oder Zellenstroms auf Konformität mit einem Traffic-Deskriptor gut geeignet. Zum Ausführen eines solchen Testes benötigt der GRCA die Spezifikation eines Emissionsintervalls (das heißt, die Reziproke eines Durchflusses) und eine Toleranz τ. In der Praxis kann diese Toleranz von einer Reihe Faktoren ab hängen, einschließlich der Verbindung, Parametern der Verbindungseinstellung oder der Dienstklasse. Es wird ersichtlich, dass der GCRA als Boolsche Funktion verwendet werden, wobei der GRCA (Emissionsintervall, Toleranz) für einen Strom von Paketen oder Zellen mit fester Größe falsch ist, wenn der Strom mit einer maximalen Rate übereinstimmt, oder wahr ist, wenn der Strom mit einer minimalen Rate übereinstimmt. So stimmt beispielsweise eine Quelle von Zellen mit einer PCR überein, wenn GCRA (1/PCR, τ_PCR) falsch ist. Demzufolge stimmt eine Verbindung oder ein Strom mit einer MCR überein, wenn GCRA (1/MCR,τ_MCR) falsch ist. Es wird erkannt werden, dass das „Emissionsintervall" die Reziproke der „Zellenrate" ist.
Ein DBR-Traffic-Contract eignet sich für eine Quelle, die eine Verbindung in Erwartung der Verfügbarkeit eines statischen Bandbreitenbetrags für die Verbindung während der gesamten Standzeit aufbaut. Daher ist die Bandbreite, die das Netzwerk einer DBR-Verbindung zur Verfügung stellt, durch den PCR-Wert charakterisiert. Des Weitern entspricht der Zellen- oder Paketstrom in einer solchen Verbindung dem Traffic-Contract, wenn der mit GCRA (1/PCR, τ_PCR) übereinstimmt. Auf der anderen Seite ist ein SBR-Traffic-Contract für eine Anwendung mit bekannten Traffic-Eigenschaften geeignet, die eine sachkundige Auswahl einer SCR und τ_IBT sowie einer PCR und τ_PCR ermöglicht. Ein SBR- oder rt-SBR-Strom entspricht seinem Traffic-Contract, wenn der Strom nicht nur mit GCRA (1/PCR, τ_PCR) sondern auch mit GCRA (1/SCR, τ_IBT) übereinstimmt.
Wie bereits angedeutet, eignet sich ein ABR-Traffic-Contract für Anwendungen, die die dynamischen Schwankungen der Informationstransferrate tolerieren können, die aus der Verwendung einer nicht reservierten Bandbreite resultieren. Eine PCR und eine MCR sind durch die Quelle spezifiziert, die eine solche Verbindung aufbaut, und diese Parameter können Aushandlungen mit dem Netzwerk unterliegen. Daher ist die in einer ABR-Verbindung verfügbare Bandbreite die Summe der MCR (die 0 sein kann) und einer variablen Zellenrate, die aus einer Mitbenutzung nicht reservierter Bandbreite unter den ABR-Verbindungen über ein definiertes Zuweisungsverfahren resultiert (das heißt, die Bandbreite, die eine Quelle über ihre spezifizierte MCR hinaus empfängt, ist nicht nur von der ausgehandelten PCR sondern auch von der Netzwerkstrategie abhängig). Durch Rückmeldung des Netzwerkes kann die Quellanwendung die Rate, mit der sie Zellen oder Pakete in die ABR-Verbindung einspeist, dynamisch anpassen. Ein ABR-Strom entspricht immer seinem Traffic-Contract, wenn er mit GCRA (1/MCR, τ_MCR) kon form ist, und entspricht diesem immer dann nicht, wenn er mit GCRA (1/PCR, τ_PCR) nicht-konform ist. Konformität im Bereich zwischen MCR und PCR ist abhängig von der ABR-Rückmeldung und wird somit dynamisch bestimmt.
Ein UBR-Traffic-Contract ähnelt einem ABR-Contract, außer dass der UBR-Contract die Spezifikation einer MCR nicht anpasst und keine dynamische Konformitätsdefinition besitzt. Somit entspricht ein UBR-Strom seinem Traffic-Contract, wenn er mit GCRA (1/PCR, τ_PCR) übereinstimmt.
B. Traffic-Shaping
Die ITU-T-Empfehlung 1.371 befasst sich folgendermaßen mit der Möglichkeit des Umformens von Traffic an einem Netzwerkelement, um den Traffic in Übereinstimmung mit einem Traffic-Deskriptor zu bringen:
„Traffic-Shaping ist ein Verfahren, das die Traffic-Eigenschaften eines Zellenstroms auf einer VCC oder einer VPC ändert, um eine gewünschte Modifizierung dieser Traffic-Eigenschaften zu erzielen, damit eine bessere Netzwerkeffizienz unter Einhaltung der QoS-Ziele erreicht wird, oder um Konformität an einer nachfolgenden Schnittstelle sicherzustellen. Traffic-Shaping muss die Zellenreihenfolge (CSI – Cell Sequence Integrity) an einer ATM-Verbindung aufrecht erhalten. Shaping modifiziert die Traffic-Eigenschaften eines Zellenstroms, wodurch die durchschnittliche Zellenverzögerung erhöht wird.
Beispiele für Traffic-Shaping sind Reduzierung der maximalen Zellenrate, Begrenzung der Burst-Length, Verringerung der Zellenverzögerungsschwankung (CDV) durch entsprechende Spationierung von Zellen in Zeit- und Warteschlangenplänen.
Der Netzwerkbetreiber entscheidet, ob und wo Traffic-Shaping durchgeführt wird. Ein Netzwerkbetreiber kann zum Beispiel Traffic-Shaping in Verbindung mit passenden UPC/NPC-Funktionen durchführen.
Außerdem kann der Betreiber wählen, ob er Traffic-Shaping an einzelnen oder gesamten Zellenströmen durchführt.
Folglich kann jede ATM-Verbindung Traffic-Shaping unterliegen.
Folgende Optionen stehen dem Netzwerbetreiber/Dienstanbieter zur Verfügung:
a. Kein Shaping
Dimensionieren des Netzwerks, um jeden Strom übereinstimmender Zellen am Netzwerkzugang zu bedienen, während die Konformität am Netzwerkausgang ohne jegliches Shaping sichergestellt wird.
b. Shaping
Dimensionieren und Betreiben des Netzwerks, so dass jeder Strom übereinstimmender Zellen am Zugang von dem Netzwerk oder Netzwerksegment übermittelt wird, während QoS-Ziele eingehalten werden, und Anwenden der Ausgabe auf das Shaping des Traffic, um mit Konformitätstests am Ausgang zu entsprechen.
Shaping des Traffics am Eingang des Netzwerks oder des Netzwerkssegments und Zuordnen von Ressourcen entsprechend der durch Shaping erzielten Traffic-Eigenschaften, während QoS-Ziele und nachfolgende Konformitätstests am Netzwerk- oder Netzwerksegmentausgang eingehalten werden. Traffic-Shaping kann auch innerhalb der Kundenausstattung oder an der Quelle ausgeführt werden, um sicherzustellen, dass die von der Quelle oder an der UNI erzeugten Zellen mit dem ausgehandelten Traffic-Contract übereinstimmen, der für die verwendete ATC relevant sind (siehe Abschnitt 5.5)." ITU-T-Empfehlung 1.371, Abschnitt 6.2.5.
C. Planung für Echtzeit- und Nicht-Echtzeit-Verbindungen/Vorhandene Werkzeuge und Techniken
Es ist bekannt, dass durch „ungerechte" Aufteilung der Bandbreite zwischen Anwendungen, die „Best Efforts" Internetdienste oder ABR-ATM-Dienste verwenden, zahlreiche unerwünschte Phänomene auftreten können. Siehe Lefelhocz, Lyles, Shenker und Zhang, „Congestion Control for Best-Effort Service: Why we need a new paradigm," IEEE Network, Januar/Februar 1996, zu weiteren Details über Mechanismen für Best-Effort/ABR-Traffic.
Die meisten ATM-Switches werden momentan mit FIFO-Queuing ausgeführt. FIFO-Queuing zeigt unangemessene Verhaltensweisen, wenn es für ABR-Traffic verwendet wird (siehe „On Traffic Phase Effects in Packet-Switched Gateways", Sally Floyd und Van Jacobson, Internetworking: Research and Experience, Vol. 3, S. 115–156 (1992), und „Observations on the Dynamics of a Congestion Control Algorithm: The effects of Two-Way Traffic", Lixia Zhang, Scott Shenker, und David Clark, ACM Sigcomm 91 Conference. September 3–6, 1991, Zürich, Schweiz, S. 133–148.). Außerdem ist FIFO nicht in der Lage, sich korrekt verhaltende Benutzer vor sich unkorrekt verhaltenden Benutzern zu schützen (es bietet keine Isolierung). Resultierend aus diesen Defiziten werden oft nicht-FIFO-Queuing-Verfahren wie Weighted Fair Queuing (gewichtetes faires Einreihen) (siehe beispielsweise A. Demers, S. Keshave und S. Shenker, „Analysis and Simulation of a Fair Queuing Algorithm," Proceedings of ACM SigComm. Seiten 1–12, September 1989; und A.K. Parekh „A Generalized Processor Sharing Approach to Flow Control in Integrated Service Networks," Ph.D. Thesis, Department of Electrical Engineering and Computer Science, MIT, 1992.) oder Annäherungen an Fair Queuing wie Rundlauf (Ellen L. Hahne, „Round-robin Scheduling for Max-Min Fairness in Data Networks," IEEE Journal on Selected Areas in Communications. Vol. 9, S. 1024–1039, Sept. 1991.) vorgeschlagen.
Dienstklassen mit nicht elastischen Bandbreitenanforderungen erfordern oft, dass Daten mit begrenzten Verzögerungsvarianzen (Bounded Jitter) über das Netzwerk übertragen werden (das heißt, begrenzte Zellen- oder Paketverzögerungsvarianzen). Wie in dem oben zitierten Aufsatz von Parekh dargestellt, kann Weighted Fair Queuing (gewichtetes faires Einreihen) verwendet werden, um Bounded Jitter für Echtzeitströme bereitzustellen. Des Weiteren wurden Parekhs Erkenntnisse kürzlich (Pawan Goyal, Simon S. Lam und Harrick M. Vin, „Determining End-to-End Delay Bounds in Heterogeneous Networks," Proceedings of The 5th International Workshop on Network and Operating System Support for Digital Audio and Video (NOSSDAV). Durham, N.H., April 18–22, 1995.) erweitert, um unter Verwendung eng verwandter Verfahren des Virtual Clock Algorithmus (Lixia Zhang, „Virtual Clock: A New Traffic Control Algorithm for Packet Switching Networks," Proceedings of ACM SigComm. Seiten 19–29, August 1990.) und des Self- clocked Fair Queuing (S.J. Golestani, „A Self-Clocked Fair Queuing Scheme for High Speed Applications," Proceedings of INFOCOM. S. 636–646, 1994) Verzögerungsgrenzen für Systeme zu beweisen.
Daher ist bekannt, dass sowohl elastische (Best Effort/ABR) als auch nicht elastische (oder Echtzeit) Dienste von der Verwendung des Fair Queuing und verwandter Algorithmen profitieren können.
1. Weighted Fair Queuing und Virtual Clock
Fair Queuing und verwandte Algorithmen (beispielsweise Frame-basiertes Fair Queuing, Deficit Round Robin und so weiter) arbeiten mit Paketsequenzen oder anderen Datentransporteinheiten (beispielsweise ist eine ATM-Zelle zum Zweck dieser Darstellung ein Paket). Für ATM werden diese Sequenzen entweder durch die VCI oder die VPI identifiziert, während diese Identifizierung in der Internet-Protokoll-Suite basierend auf <IP-Adresse, Protokoll, Port> Triplets (IPv4) oder Stromidentifikatoren (IPv6) stattfindet. Sowohl bei Self-Clocked Weighted Fair Queuing als auch Virtual Clock werden Pakete von Timestamps angefordert (sortiert) (Modelle wie Rundlauf stellen Annäherungen an das Anfordern von Paketen durch Timestamps bereit). Diese Timestamps stellen die virtuelle Beendigungszeit (oder entsprechend die virtuelle Startzeit) für das Paket dar und werden berechnet, indem ein Startzeitwert mit einem Offset addiert wird, der durch Multiplizieren der Länge des Paketes mit einem Gewichtfaktor, der den Anteil der speziellen Paketsequenz an der Bandbreite darstellt, erhalten wird.
Im Speziellen wird die virtuelle Beendigungszeit für die Virtual Clock berechnet als: VT(f,0) = 0 VT(f, j + 1) = max{Arrival(f, j + 1), VT(f, j)} + Length(f, j + 1)/Rate(f) (1)wobei: VT(f;j) die virtuelle Beendigungszeit in Verbindung mit Paket j des Stromes (virtuellen Kanals) f ist;
Arrival(f;j) die Ankunftszeit des Pakets j des Stromes f ist; und
Length(f;j) die Länge des Pakets j des Stromes f ist. Self-Clocked Weighted Fair Queuing weißt virtuelle Beendigungszeiten entsprechend folgender Formel zu: VT(f,0) = 0 VT(f, j + 1) = max{SystemVirtualTime, VT(f, j)} + Length(f, j + 1)·weight(f) (2)wobei: SystemVirtualTime die virtuelle Zeit in Verbindung mit dem bedienten (ausgegebenen) Paket zum Zeitpunkt der Ankunft des Pakets(f,j + 1) ist.
Für ATM ist die Paketlänge konstant, da die Zellen eine feste Größe haben (das heißt, sie sind 53 Bytes lang). Demzufolge wird der am weitesten rechts stehende Ausdruck sowohl in Gleichung (1) als auch in Gleichung (2) zu einer Pro-Strom-Konstante. Für Virtual Clock ist die vereinfachte Gleichung: VT(f, j + 1) = max{Arrival(f, j + 1), VT(f, j)} + constant(f) (3)
Andererseits lautet die vereinfachte Gleichung für Self-Clocked Weighted Fair Queuing: VT(f, j + 1) = max{SystemVirtualTime, VT(f, j)} + constant(f) (4)
Anders ausgedrückt führt ein ATM-Warteschlangen-Punkt, der entweder Virtual Clock oder Self-Clocked Weighted Fair Queuing ausführt, folgende Schritte durch:

1) Berechnen des Höchstwertes (a) der aktuellen virtuellen Zeit für VC und (b) entweder i) der Ankunftszeit der Zelle oder ii) der virtuellen Zeit des Systems.
2)
3) Addieren einer Pro-VC-Konstante, die den Anteil dieser VC an der Bandbreite darstellt, zu den Ergebnissen aus Schritt 1.
4)
5) Bedienen (Senden) der Zellen in der Reihenfolge aufsteigender Werte der in den Schritten 1 und 2 zugewiesenen virtuellen Timestamps.

2. Priorität
Das Zuweisen einer Priorität für eine Traffic-Klasse gegenüber einer anderen bedeutet, dass für den Fall, dass die Traffic-Klasse mit höherer Priorität Zellen zum Senden hat, diese Zellen immer bevorzugt gegenüber Zellen der Traffic-Klasse mit geringerer Priorität gesendet werden.
Prioritätsverfahren können entweder preemptiv oder non-preemptiv sein. Diese Terminologie entstammt der Literatur über Betriebssysteme. Ein non-preemptives Prioritätsverfahren weist einem Objekt (in der Welt der Betriebssysteme einem Prozess, in der ATM-Welt einer VC) zum Zeitpunkt der Planung eine Priorität zu und das Objekt behält diese Priorität, bis es bedient wurde. Preemptive Prioritätsverfahren dagegen können die Priorität der Objekte ändern, während diese auf Bedienung warten. In einem preemptiven System könnte zum Beispiel festgelegt werden „plane diese VC mit Priorität 3, ist sie jedoch nicht innerhalb von 200 Mikrosekunden bedient, dann erhöhe die Priorität auf 2."
3. Work-Conserving- und Non-Work-Conserving-Queuing
Kleinrock, Queuing Systems. Vol. 2: Computer Applications. John Wiley & Sons, N.Y., N.Y. 1996, S. 113 verwendet die Terminologie „Work Conserving" zum Bezeichnen eines Queuing-Systems, in dem Arbeit weder erzeugt noch zerstört wird. In Übereinstimmung mit dieser Terminologie ist ein Switch, der, wenn er Zellen in Warteschlange erhält, Zellen immer an die ausgehende Verbindung sendet, ein „Work Conserving Switch". Switches, die eine reine FIFO, Weighted-Fair-Queuing oder Virtual-Clock-Planung verwenden, sind alle work conserving (arbeiterhaltend). Im Gegensatz dazu kann ein Non-Work-Conserving-Switch entscheiden, dass Zellen nicht gesendet werden, selbst wenn Zellen für die Übertragung in der Warteschlange sind. Es wird gezeigt werden, dass ein Verfahren zur Umsetzung dessen dann besteht, den Switch so zu programmieren, dass er wartet, bis die aktuelle Zeit gleich oder größer als der mit einer bestimmten Zelle verbundene Timestamp ist, bevor er diese Zelle sendet.
Work-Conserving-Switches versuchen, die Übertragungsverbindung komplett auszunutzen, entfernen oder verhindern jedoch Bursts nicht zwingend. Im Gegensatz dazu kön nen Non-Work-Conserving-Switches Zellen strategisch verzögern, damit Traffic umgeformt wird und ein strengerer Konformitätstest (das heißt, ein GCRA mit einem kleineren τ) bestanden wird. Zusätzlich kann ein Non-Work-Conserving-Switch, in dem einer bestimmten Verbindung nur ein festgelegter Pufferwert zugeordnet ist, eine kontrollierende Funktion (mit ITU-Worten eine UPC/NPC) durchführen, indem Zellen, die den zugewiesenen Pufferplatz überlaufen lassen, verworfen oder erfasst werden. Ein Beispiel eines Non-Work-Conserving-Queuing-Systems ist die Stalled Virtual Clock (Sugih Jamin, „Stalled Virtual Clock" Arbeitsnotiz, Institut für Informatik, UCLA, März 21, 1994), welche eine Anpassung des Virtual-Clock-Algorithmus von Lixia Zhang ist, wobei virtuelle Zeit nicht schneller vergehen kann (sie bleibt stehen oder wird nichtarbeitserhaltend) als Echtzeit. Siehe auch die Arbeiten von Scott Shenker, die über FTP unter FTP.PARC.XEROX.com zur Verfügung stehen.
4. Kalender-Warteschlangen
Eine Kalender-Warteschlange ist eine nach Zeit geordnete Liste von Aktionen, von denen jede dann entfernt und ausgeführt wird, wenn die Echtzeit gleich oder größer als die mit dieser Aktion verbundene Zeit ist. Kalender-Warteschlangen mit begrenzten Zeitintervallen können als lineare Anordnung dargestellt werden, die als „Zeitrad" oder „Zeitlinie" bekannt ist. Zeiträder weisen Buckets Ereignisse relativ zu einem Zeiger zu, wobei der Bucket-Index mittels eines arithmetischen Moduls von der Größe des Rades errechnet wird. Diese Datenstrukturen sind in der Literatur als Queuing-Verfahren bekannt. In einem Zeitrad wird die absolute Zeit als ein Offset relativ zur aktuellen Zeit („Echtzeit") dargestellt und jedes Element in der Anordnung ist ein Bucket, der eine oder mehrere Aktionen enthält (typischerweise in der Form verlinkter Listen), die zu der Zeit ausgeführt werden sollten, die dem Bucket, in dem sie sich befinden, zugewiesen ist. Jeder der Buckets eines solchen Zeitrades kann leer sein, das heißt, keine mit ihm verknüpften Ereignisse haben.
Für jedes Zeitrad gibt es zwei Zeiten, die von Interesse sind: t_earliest, und t_latest, die den Start- und End-Pointern für die aktiven Einträge in der Anordnung entsprechen; wobei t_earliest, die Zeit des nächsten zu bedienenden Eintrags (zum Beispiel Paket oder Zelle) ist und t_latest die mit dem letzten (zeitlich am weitesten entfernten) Bucket, der ein geplantes Ereignis enthält, verknüpfte Zeit ist. Der Unterschied zwischen t_earliest und t_latest kann nicht größer sein als die Länge des Zeitrades, b, minus 1. Das kann sichergestellt werden, indem die Zeit als modulo b betrachtet wird, und indem dann sichergestellt wird, dass kein Offset (die Paketlänge multipliziert entweder jeweils mit der Rate oder der Gewichtung in der Virtual Clock oder dem Weighted-Fair-Queuing) größer als b-1 ist. Für eine ATM-Verbindung mit OC-3 Geschwindigkeiten (149,76 mbps – der SONET-Nutzdatenrate) gibt es etwa 353208 Zellen/Sekunde in der Verbindung. Sind entsprechend 46 Kbps (Voice-Telefonie-Raten) Ströme (etwa 174 Zellen/Sekunde, wenn AAL Typ 1 verwendet wird) die zu unterstützenden Verbindungen mit der niedrigsten Geschwindigkeit, dann ist das Verhältnis der höchsten unterstützten Rate zur niedrigsten Rate 2029, was sich auf 2¹¹ aufrunden lässt. Dieses Verhältnis ist der maximale Offset, der während der Berechnung virtueller Zeiten addiert wird. Daher ist ein Zeitrad der Länge 2030 (2048, um das Aufrunden auf eine Potenz von zwei zu ermöglichen) ausreichend, um virtuelle Zeiten in Verbindung mit Kanälen zu kodieren, deren Raten von 64 Kbps bis zur kompletten OC-3 Linkrate reichen.
Die Länge einer Zeitradanordnung kann verringert werden, indem es einem Anordnungselement ermöglicht wird, mehr als einen Zeit-Offset zu enthalten. Wird zum Beispiel das oben beschriebene Zeitrad von 2048 Elementen auf 256 Elemente verringert, dann hätte jeder Bucket acht Zeit-Offsets eingetragen. Aktionen innerhalb eines einzigen Buckets, der mehrere Offsets umfasst, können außerhalb der Reihenfolge ausgeführt werden, doch zwischen den Buckets bleiben die Aktionen in Reihenfolge. Dadurch wird die Speichermenge, die einem solchen Zeitrad zugewiesen werden muss, auf Kosten der Genauigkeit der Aktionsanforderung in der Kalender-Warteschlange reduziert.
D. Traffic-Shaping für zeitmultiplexierte Ströme auf multiplen Ausgabekanälen
Vorzugsweise wird jegliches Traffic-Shaping, das benötigt wird, um zeitmultiplexierte Paket- oder Zellenströme mit ihren Traffic-Contracts in Übereinstimmung zu bringen, nach Beendigung aller Vermittlungs- oder Routing-Vorgänge, die das Separieren von Strömen für verschiedene Ausgabekanäle erfordern, durchgeführt. Dadurch wird die Durchsatzeffizienz des Datenüberträgers optimiert.
Die ATM-Switches in Warteschlange des Stands der Technik verwenden jedoch normalerweise FIFO (First In – First Out) Ausgabepuffer. Diese Puffer können sich nicht an ei ner kontrollierten Umformung der durch sie durchlaufenden Ströme beteiligen. Statt dessen sind die von diesen Puffern ausgegebenen Pro-VC zeitmultiplexierte Ströme hauptsächlich zeitmultiplexierte Zusammensetzungen der eingegebenen Ströme, die in sie hineingeladen werden. Natürlich werden diese Ausgabeströme relativ zu den Eingabeströmen auf Grund der inhärenten Latenzzeit dieser Puffer zeitverzögert. Des Weiteren kann die Zellverzögerungsschwankung (CDV – Cell Delay Variation) eines oder mehrerer dieser Ausgabeströme erhöht werden, wenn Planungskonflikte bei den Datentransportbeschränkungen der verschiedenen Ströme auftreten, da diese Konflikte so genannte „Sendekollisionen" verursachen.
Es wird erkannt werden, dass erhöhte CDV besonders für Traffic wie DBR-Traffic, der im Allgemeinen eine ziemlich niedrige Toleranz hat, problematisch ist. Wenn jeder Sprung zwischen einer Quelle und einem Ziel eine einfache FIFO-Ausgabewarteschlange der oben beschriebenen Art enthält, kann es daher notwendig sein, die Anzahl der Sprünge, die dieser CDV-empfindliche Traffic durchführen darf, zu begrenzen, um die Übereinstimmung mit seiner festgelegten Toleranz zu sichern.
Demzufolge ist es offensichtlich, dass es einen Bedarf an effizienteren und effektiveren Traffic-Shaping-Verfahren und -Abläufen für ATM-Switches und andere Router gibt, die Traffic von mehreren Eingaben an mehrere Ausgaben zeitmultiplexierte Ausgabeemissionen routen.
Die vorliegende Erfindung kommt diesem Bedarf entgegen, indem sie Raten-Shaping in Pro-Strom-Routing-Verfahren in Warteschlange für ABR-Dienste in Netzwerken mit segmentierten ABR-Regelkreisen bereitstellt. Die vorliegende Erfindung wird in den beiliegenden Patentansprüchen offen gelegt.
Die vorliegende Erfindung wird an Hand von Beispielen mit Bezug auf die beiliegenden Zeichnungen detaillierter beschrieben, wobei:
1 ein vereinfachtes Blockdiagramm eines ATM-Switches ist, in dem die vorliegende Erfindung vorteilhaft eingesetzt werden kann;
2 die verschiedenen Formen verfolgt, die eine ATM-Zelle entsprechend annehmen kann, während der in 1 gezeigte Switch durchlaufen wird;
3 ein detaillierteres Blockdiagramm eines repräsentativen Kanals auf der Ausgabe oder Sendeseite des in 1 gezeigten Chips ist;
4 eine Umsetzung einer Stalled-Virtual-Clock-Kalender-Warteschlange der vorliegenden Erfindung schematisch darstellt;
5 eine Umsetzung einer anderen Stalled-Virtual-Clock-Kalender-Warteschlange der Erfindung schematisch darstellt;
6 eine Umsetzung einer weiteren Stalled-Virtual-Clock-Kalender-Warteschlange dieser Erfindung schematisch darstellt;
7 eine ABR-Verbindung mit einem Quelle-zu-Ziel-Regelkreis schematisch darstellt; und 8 eine ABR-Verbindung mit einem segmentierten Regelkreis schematisch darstellt.
A. Eine repräsentative Umgebung
Bezug nehmend auf die Zeichnungen, und hier im Speziellen auf 1, sind die Eingabe- und Ausgabe-Ports eines ATM-Switches 21 normalerweise mit einer oder mehreren physischen Schichten über jeweilige Utopia-2-Interfaces und mit einem Switch-Steuerprozessormodul 22 über ein zweites passendes Interface verbunden. Dadurch kann Switch 21 Daten austauschen und Zellen mit allen physischen Schichten, die mit ihnen verbunden sind, steuern, und außerdem Steuerzellen mit dem Steuerprozessormodul 22 austauschen. In Übereinstimmung mit Standardpraktiken sind die Kommunikationskanäle unidirektional, so dass für bidirektionale Kommunikationen zwei Kanäle erforderlich sind.
Der Switch 21 umfasst ein Switching Fabric 24, Fabric-Steuermodul 25 und einen Reservierungsring 26 zum Daten-Switching und Steuern der Zellen von Eingabe-Warteschlangen an Pro-VC-Ausgabe-Warteschlangen. Die Zellen in diesen Warte schlangen werden im Datenpfad im Datenspeicher 27 gespeichert und diese Eingabe- und Ausgabe-Warteschlangen werden von einem Warteschlangen-Steuermodul 28 verwaltet. Normalerweise ist der Datenspeicher 27 so groß, dass er bis zu 12000 Zellen speichern kann. Verbindungsdatensätze für die Daten- und Steuerzellenströme werden im Steuerpfad im Steuerspeicher 29 zusammen mit bestimmten Arten von Steuerzellen gespeichert, die von ratenbasierten Vorrichtung und einem Traffic-Multiplexer 31 zum Routen an das Steuerprozessormodul 22 abgefangen werden. Die Interaktion des Steuerprozessormoduls 22 mit dem Switch 21 liegt außerhalb des Bereiches der vorliegenden Erfindung und daher hier nicht beschrieben. Diejenigen, die mit dem Aufbau von ATM-Switches vertraut sind, werden jedoch verstehen, dass der Steuerprozessor vorrangig für die Durchführung des Verbindungsaufbaus und der -beendigung, sowie für OAM-(Durchführung- und Verwaltungs-) Funktionen verantwortlich ist.
Der Datenpfad des Switches 21 wird bei einer vorgegebenen Rate von beispielsweise 40 MHz (mittels nicht gezeigter Einrichtungen) synchron getaktet. Im Einklang mit herkömmlichen synchronen Pipeline-Verfahren wird jedoch die Phase dieses Clock-Signals (mittels ebenfalls nicht gezeigter Einrichtungen) um verschiedene Werte an verschiedenen Punkten entlang des Datenpfades verzögert, um den Daten ausreichend Zeit einzuräumen, sich vor dem Senden von einer Pipeline-Stufe zur nächsten auszugleichen.
In Übereinstimmung mit Standardpraktiken initiiert eine Quelle, die mit einem Ziel kommunizieren möchte, Verhandlungen mit dem ATM-Netzwerk, innerhalb dessen sich der Switch 21 befindet, indem sie eine SETUP-Nachricht an das Netzwerk sendet. Diese Nachricht identifiziert das Ziel und spezifiziert alle der relevanten Traffic-Parameter für die angeforderte Verbindung explizit oder implizit. Wenn das Netzwerk darauf vorbereitet ist, den Traffic-Contract, der durch diese Traffic-Parameter (oder eine modifizierte Version der Parameter, die die Quelle akzeptieren kann) definiert ist, anzunehmen, leitet das Netzwerk die SETUP-Nachricht an das Ziel weiter. Wenn das Ziel dann für den Empfang des Nachrichten-Traffic von der Quelle in Übereinstimmung mit den Bedingungen des Traffic-Contracts bereit ist, senden das Ziel eine CONNECT-Nachricht an die Quelle zurück. Diese CONNECT-Nachricht bestätigt, dass eine Verbindung auf einem festgelegten virtuellen ATM-Kanal (VC) innerhalb eines festgelegten virtuellen ATM-Pfades (VP) für einen Zellenstrom in Übereinstimmung mit dem Traffic-Contract aufgebaut wurde. Siehe dazu die ITU-T-Empfehlung 0.2391 und die ATM Forum UNI 4.0 Spezifikation. „Permanente" virtuelle Verbindungen können auf Vorrat aufgebaut werden, ohne diese Signalisierungsprotokolle aufzurufen.
Nach dem Aufbau der Verbindung beginnen Datenzellen zu fließen. Wie in 2 gezeigt ändert sich die Form der Zellen, wenn sie durch den Switch 21 fließen, auf Grund der vom Switch ausgeführten Abläufe. Zellen können innerhalb des Switches 21 zum Zweck des Multicastings (Rundsendens) repliziert werden, die folgende Beschreibung geschränkt sich jedoch auf Unicast-Abläufe (Punkt-zu-Punkt-Abläufe), um unnötige Komplexität zu vermeiden.
Wie in 2 bei 41 gezeigt hat jede eingehende Zelle, die der Switch 21 empfängt, einen Header mit einem VP-Index und einem VC-Index. Diese Indizes werden kombiniert, um eine einzigartige Adresse für einen Sprung der Verbindung festzulegen. Eine Verbindung kann aus mehreren Sprüngen bestehen, daher werden die VP- und VC-Indizes für den nächsten Sprung in den Header der Zelle geschrieben, wenn diese wie in 2 gezeigt den Switch 21 passiert.
Der Switch 21 verwendet die VP- und VC-Indizes der eingehenden Zelle (2 bei 41), um die Adresse zu berechnen, an der sich der Verbindungsdatensatz für den zugeordneten Strom innerhalb des Steuer-RAM 29 befindet. Normalerweise beinhaltet dieser Verbindungsdatensatz einen Bit-Vektor zum Identifizieren des Ausgabe-Ports (das heißt, des „Ziels" auf Switch-Ebene) an dem der Strom den Switch 21 verlässt, einen Prioritätsindex zum Identifizieren der relativen Priorität des Stroms auf einer groben Prioritätsskala sowie einen Schaltkreis-Index („Circuit Index"), der den Strom innerhalb des Switches 21 eindeutig identifiziert. Wie in 2 bei 43 gezeigt werden diese Verbindungsparameter in den Zellen-Header geschrieben. Dann werden alle Zellen in den Daten-RAM-Speicher 29 geschrieben, während ein Pointer auf die Zelle mit einer entsprechenden der Vielfalt der FIFO-Eingabe-Warteschlangen verbunden wird, wo die Auswahl der Warteschlange auf der Priorität des zugehörigen Stroms basiert.
Die relativen Prioritäten der Zellen des Warteschlangenkopfes innerhalb dieser Eingabe-Warteschlangen werden während jeder Zellenzeit untersucht und die Zelle des Warteschlangenkopfes mit der höchsten Priorität wird für die Entscheidung während der nächsten Entscheidungsphase ausgewählt. Des Weiteren wird die Priorität jeder Zelle des Warteschlangenkopfes mit niedrigerer Priorität (das heißt, jede nicht ausgewählte Zelle des Warteschlangenkopfes) schrittweise erhöht (mittels nicht gezeigter Einrichtungen), wodurch sich die Wahrscheinlichkeit, dass diese Zelle während der nächsten Entscheidungsphase für die Entscheidung ausgewählt wird, erhöht. Obwohl die Eingabe-Warteschlangen mit hoher Priorität einen größeren Durchsatz pro Einheitszeit haben als Warteschlangen mit niedrigerer Priorität, haben die Warteschlangen mit niedrigerer Priorität begrenzte Verzögerungen, da sich die Priorität ihrer Zellen des Warteschlangenkopfes als eine Funktion der Zeit erhöht.
Jeder Entscheidungszyklus erfordert eine Zellenzeit des Switches 21, so dass die Routing-Informationen der für die Entscheidung ausgewählten Zellen in den Reservierungsring 26 eingegeben werden, eine Zellenzeit bevor die Nutzdaten der Zelle oder Zellen, die für die Entscheidung ausgewählt wurden, in das Switching Fabric 24 freigegeben werden. Anders ausgedrückt bestehen wie in 2 bei 44 gezeigt die Zellen, die von dem Reservierungsring 31 und dem Switching Fabric 32 empfangen werden, aus den Headern der Zellen für den nächsten Entscheidungszyklus (das heißt, die „aktuellen Zellen"), gefolgt von den Bodys oder Nutzdaten der Zellen, die während des vorangegangenen Entscheidungszyklus' erfolgreich entschieden wurden (das heißt, die „vorherigen Zellen"). Daher ist das Fabric, wenn die Zellen-Bodys das Fabric 32 erreichen, bereits von der Fabric-Steuerung 33 so konfiguriert, um diese Zellen zu ihrem entsprechenden Ausgabeportziel zu routen. Zu weiteren Informationen über den Reservierungsring 31 und die von ihm durchgeführte Entscheidung siehe: Cisneros, A., „Large Packet Switch and Contention Resolution Device," Proceedings of the XIII International Switching Symposium. 1990, paper 14, Vol. III, S. 77–83 und Lyles U.S.P. 5,519,698, ausgefertigt am 21. Mai 1996.
In das dargestellten Ausführungsbeispiel werden Zellen zur Entscheidung und zum Routing in vier Bit breite Halbbytes zerlegt. Danach werden die Zellen (mit Ausnahme der „untätigen Zellen", die zum Testen der Switching-Prozesse bereitgestellt werden können) wieder zusammengesetzt und in den Datenpfad, den Steuerpfad oder beide eingegeben (a) für einen zeitlich geplanten Transfer an die entsprechenden Ausgabeports des Switches 21 und/oder (b) zum Transfer an das Steuerprozessormodul 22. Der zeitlich geplante Transfer von Zellen an die Ausgabeports des Switches 21 ist ein zentraler Bestandteil dieser Erfindung, so dass dieses Thema untenstehend detaillierter ausge führt wird. Auf der anderen Seite sind das Zerlegen und wieder Zusammensetzen der Zellen, die Testprozesse und die Interaktion des Steuerprozessors 22 mit RM-(Ressourcen-Management-) und OAM-(Betriebs- und Wartungs-) Zellen sind nebensächliche Themen, die nicht tiefgehend behandelt werden müssen.
Bezug nehmend auf 3 wird ersichtlich, dass sich der Switch 21 auf der Ausgabe- oder Sendeseite des Switching-Fabric 24 auffächert. Daher wird ersichtlich, obwohl lediglich ein Ausgabekanal des Switches 21 gezeigt wurde, dass dieser Kanal im Allgemeinen repräsentativ für die anderen Kanäle ist.
Wie gezeigt befindet sich dort passenderweise ein Füllzellenmodul 51 zum Akzeptieren von Zellenbodys und ihren zugehörigen Schalkreis-Indizes von dem Switching-Fabric 24. Die „effektive Zellenzeit" auf der Ausgabeseite des Switching-Fabric 24 wird vom Verhältnis der Nominalzellenzeit zum Beschleunigungsfaktor „k" bestimmt. Ist daher beispielsweise die Nominalzellenzeit 113 Uhrzyklen/Zelle, dann ist die effektive Zellenzeit auf der Ausgabeseite des Switching Fabric 25 gleich 56,5 Zyklen/Zelle, wenn k = 2.
Wird eine gültige Zelle empfangen, dann verwendet das Füllzellenmodul 51 normalerweise Zellenstrukturen von einer verknüpften und nummerierten freien Liste 52 mit solchen Datenstrukturen zum Schreiben der Zelle in den Datenspeicher 27. Zu diesem Zweck beinhaltet das Füllzellenmodul passenderweise einen Zustandsabrufautomat 53 zum Abrufen von Zellstrukturen vom Anfang der freien Liste 52 bei Bedarf. Dadurch kann das Füllzellenmodul 51 den Schaltkreis-Index für die Zelle und einen Pointer auf den Speicherort der Zelle im Datenspeicher 27 in eine „Ankunfts-Nachricht" einfügen, die gesendet wird, um eine Zellenstrom-Steuereinheit 55 über die Ankunft der Zelle zu benachrichtigen. Mit dem Schaltkreis-Index kann die Stromsteuereinheit 55 den VC oder Strom, zu dem die Zelle gehört, aus dem Verbindungsdatensatz im Steuerspeicher 29 bestimmen. Dadurch kann die Zellenstrom-Steuereinheit 55 wiederum den Traffic-Shaping-Status des Stroms prüfen. Ein OAM/RM-Erkenner 57 ist zweckmäßigerweise bereitgestellt, damit die Strom-Steuereinheit 55 diese Steuerzellen identifizieren und bestimmen kann, ob diese in den Datenpfad, den Steuerpfad oder beide eingegeben werden sollen.
Die Speicher-Pointer für Zellen von Strömen, die mit dem Traffic-Contract konform sind, werden als Antwort auf „addCell"-Nachrichten in Pro-VC-Warteschlangen eingegeben, die die Zellenstrom-Steuereinheit 55 an eine Warteschlangen-Steuereinheit 58 sendet. Jede addCell-Nachricht identifiziert die Zelle, zu der diese gehört, und den Schaltkreis-Index für den dazugehörigen Strom oder VC. Des Weiteren zeigt die addCell-Nachricht auch an, ob die Zelle in den Datenpfad, den Steuerpfad oder beide eingegeben werden soll. Wurde die Zellen entsprechend eingegeben, sendet die Wartenschlangen-Steuereinheit 58 eine „added"-Nachricht an die Zellenstrom-Steuereinheit 55, um die Strom-Steuereinheit 55 darüber zu benachrichtigen, dass die neu eingefügte Zelle in zukünftige Raten-Shaping-Berechnung in dem VC, zu dem sie gehört, einbezogen werden muss.
Zweckmäßigerweise überwacht die Warteschlangen-Steuereinheit 58 die Länge der Pro-VC-Warteschlangen in Bezug auf die Tiefensteuergrenzen, die in den jeweiligen Warteschlangen eingerichtet sind. Dadurch kann die Steuereinheit 58 die Verstopfungssteueraktion an ABR-Strömen initiieren, wenn ihre Pro-VC-Warteschlangen übermäßig lang werden. Es ermöglicht außerdem der Steuereinheit 58 die Identifizierung von Strömen, die ihren Traffic-Contract überschreiten, so dass eine entsprechende Kontrollfunktion (nicht gezeigt) aufgerufen werden kann, um Zellen solch nicht-konformer Ströme fallen zu lassen oder zu loggen.
Ein Durchlass-Controller 61 überwacht die „added^„-Nachrichten, die von der Warteschlangen-Steuereinheit 58 zurück gesendet werden, um den Planer 62 zu veranlassen, die Zellen des Warteschlangenkopfes für die nicht-leeren Pro-VC-Warteschlangen auf einer Kalender-Warteschlange 63 für das Senden zu geplanten Zeiten zu planen. Passenderweise verwendet der Planer 62 eine Pro-VC-Virtual-Clock, um diese Zellen des Warteschlangenkopfes auf der Kalender-Warteschlange 63 in Übereinstimmung mit den jeweiligen virtuellen Beendungszeiten, VT(f, j + 1), zu planen, die der Planer 62 für diese berechnet (oder alternativ „virtuelle Startzeiten"). Beachten Sie auch den obenstehenden Abschnitt III.C.1.
Die Kalender-Warteschlange 63 verfolgt die „Echtzeit" oder „aktuelle Zeit" des Systems, um zu verhindern, dass geplante Zellen vor ihrer geplanten Zeit für das Senden freigegeben werden. Anders ausgedrückt implementieren der Planer 62 und die Kalender- Warteschlange 63 eine Stalled Virtual Clock, so dass die Zellen, die für das Senden geplant sind, nur dann zum Senden freigegeben werden, wenn die Echtzeit des Systems mindestens ihre entsprechenden geplanten Sendezeiten erreicht hat. Wie gezeigt werden Verbindungen mit Zellen, die von der Kalender-Warteschlange 63 zum Senden freigegeben wurden, in eine Verbindungsliste mit Verbindungen verknüpft, die auf einer Sendeliste 65 Zellen haben, die zum Senden bereit sind.
Die Kalender-Warteschlange 63 informiert die Strom-Steuereinheit 55 darüber, ob sie eine Zelle zum Senden an eine gegebene Verbindung freigibt. Die Strom-Steuereinheit 55 fordert wiederum auf der Pro-VC-Warteschlange für die gegebene Verbindung die Referenz zur nächsten Zelle an (das heißt, die neue Zelle des Warteschlangenkopfes), wenn vorhanden, und benachrichtigt den Durchlass-Controller 61, dass er diese Referenz zur Planung an den Planer 62 zulassen soll. Somit beteiligt sich der Durchlass-Kontroller 61 effektiv an den Closed-Loop-Kommunikationen mit der Kalender-Warteschlange 63 um sicherzustellen, dass die Zellen des Warteschlangenkopfes, die er darauf zur Planung zulässt, unter Ausschluss aller anderen Zellen in den Pro-VC-Warteschlangen zugelassen werden. Somit kann die Kalender-Warteschlange 63 umgesetzt werden, indem ein oder mehrere Zeiträder oder „Zeitlinien", 66. Beachten Sie auch den obenstehenden Abschnitt III.C.4. Die Zeitspanne dieser Zeiträder muss mindestens so lang sein wie der Zeitraum der Ströme mit der niedrigsten Frequenz, die das System unterstützen kann, um durch Zeitumbruch hervorgerufene Ambiguitäten zu verhindern, und ist vorzugsweise doppelt so lang, so dass relative Zeiten mittels Zweierkomplementberechnung verglichen werden können.
B. Shaping von Strömen mit Datentransportlimits fester Bit-Längen zu festgelegten maximalen Stromraten
Bezug nehmend auf 4 wird deutlich, das die Sendesteuerung der Stalled Virtual Clock zum Shaping zeitmultiplexierter Ströme mit Datentransporteinheit fester Bit-Länge, wie ATM-Zellen, von einem Routing-Mechanismus mit Ausgabe-Warteschlange an spezielle Stromraten mit maximalen Dateneinheiten, wie beispielsweise PCR für DBR/CBR ATM-Dienste, gut geeignet ist. Wie zuvor beschrieben werden die Datentransporteinheiten der Ströme, die an einen gegebenen Ausgabeport geroutet werden, nach dem Routen in Pro-Strom-Warteschlangen eingegeben. Die Datentransporteinhei ten an den Köpfen dieser Warteschlangen werden dann von einem Durchlass-Controller 61 durchgelassen (unter Ausschluss aller anderen Transporteinheiten) zum Planen an einer Zeitlinien-Kalender-Warteschlange 63 durch einen Planer 62. Der Planer 62 führt wiederum an diesen Transporteinheiten der Warteschlangenköpfe Pro-Strom-Virtual-Clock-Berechnungen durch, um sie für die Freigabe aus der Kalender-Warteschlange 63 in Übereinstimmung mit ihren jeweiligen theoretischen Beendungszeiten, VT(f, j + 1), oder ihren jeweiligen theoretischen Startzeiten zu planen. Beachten Sie auch den obenstehenden Abschnitt III.C.4.
Echtzeit wird zweckmäßigerweise auf der Zeitlinie 63 mit einer Rate inkrementiert, die es dem geformten zeitmultiplexierten Ausgabe-Traffic ermöglicht, die Bandbreite der Ausgabeverbindung 71 tatsächlich zu füllen. Die Höchstzahl zerlegbarer Zeitslots, in die der Planer 62 die Elemente des Warteschlangenkopfes der jeweiligen Ströme eintragen kann, basiert auf dem Verhältnis der maximal zulässigen Frequenz zur minimal zulässigen Frequenz dieser Ströme. Somit die Rate, mit der Echtzeit von Bucket-zu-Bucket erhöht mit einem rationalen Vielfachen der Zellrate wird.
Datentransporteinheiten, die sich in den Zeitslots befinden, die Zeiten früher oder gleich mit der aktuellen echten Referenzzeit für die Zeitlinie 63 haben, kommen für das Senden in Frage und werden daher in eine Transportliste 65 wir zuvor beschrieben verknüpft. Diese Datentransporteinheiten, die sich in den Zeitslots befinden, die mit den späteren Zeitslots der Zeitlinie 63 verbunden sind, bleiben jedoch in einem Schwebezustand, bis die Echtzeit des Systems ausreichend vorangeschritten ist, um diese Zeitslots zu erreichen. Zur Vermeidung von Überlappungsambiguitäten ist die Zeitlinie 63 so eingerichtet, dass alle Referenzen auf früher geplante Datentransportlimits aus jedem Zeitslot entfernt werden, bevor jegliche Referenzen auf später geplante Transporteinheiten in Erwartung des nächsten Scans dann eingefügt werden.
Während die obenstehend beschriebene Anordnung übereinstimmende DBR/CBR ATM-Ströme an den von ihren Traffic-Contracts festgelegten PCR umformt, hilft sie nicht dabei, die Zellenverzögerungsschwankungen (CDV – Cell Delay Variation) dieser Ströme in Konformität mit den τ_PCR Parametern ihrer Traffic-Contracts zu bringen.
C. Multiple Prioritätsebenen zum Minimieren relativer Variationskoeffizienten
In Übereinstimmung mit der vorliegenden Erfindung werden Datentransporteinheiten, die von Strömen mit unterschiedlichen Frequenzen an einen Multiplexierungs-Punkt, wie einen Ausgabe-Port eines ATM-Switches, geliefert werden, bevorzugt behandelt, so dass die Datentransporteinheiten der Ströme mit höheren Frequenzen eine Sendepriorität erhalten, die über alles anderen Datentransporteinheiten der Ströme mit niedrigeren Frequenzen liegt, sollten sie mit diesen kollidieren. Wie in 3 gezeigt kann diese Sendepriorität durch die Lenkung der Datentransporteinheiten, die für das Planen durch den Stalled-Virtual-Clock-Planungsmechanismus 63 oder ähnliches freigegeben sind, zu einer oder einer anderen Vielzahl von Zeitlinien mit geordneten Prioritätsrängen 66a–66e oder Ausgabe-FIFO-Warteschlangen basierend auf den Frequenzen der Ströme, zu denen diese entsprechenden Datentransporteinheiten gehören, umgesetzt werden. Zum Beispiel könnte es für einen ATM-Switch ratsam sein, in der Reihenfolge fünf verschiedener Frequenz abhängiger/Dienstklassen abhängiger Ausgabeprioritäten umzusetzen, einschließlich (1) einer Top-Priorität für Zellen aus Strömen, die Ausgaberaten von mindestens 1/16 der kompletten Rate der Ausgabeverbindung (das heißt, seiner gesamten Bandbreite) verhandelt haben, (2) einer zweiten Priorität für Zellen aus Strömen, die Ausgaberaten von 1/16 bis 1/256 der Ausgabeverbindungsrate verhandelt haben, und (3) eine dritte Priorität für Zellen aus Strömen, die Ausgaberaten von 1/256 bis 1/4096 der Verbindungsrate verhandelt haben. Die unteren beiden Prioritäten werden dann passenderweise für ABR-Verbindungen festgelegt, die verhandelte MCR-Raten von nicht Null haben, und für UBR-Verbindungen und ABR-Verbindungen, die jeweils MCR-Raten von 0 haben.
Es wird erkannt werden, dass die vorliegende Erfindung die CDV der Ströme mit höheren Frequenzen effizient reduziert, ohne die CDV der Ströme mit niedrigeren Frequenzen wesentlich zu erhöhen. Als allgemeine Regel ist eine tolerierbare CDV eine Funktion der verhandelten Rate für einen Strom. Ein CDV von 100 Zellzeiten ist zum Beispiel in Bezug auf ein erwartetes Emissionsintervall von einer Zelle aller 10 Zellen sehr groß, jedoch im Allgemeinen nicht signifikant, wenn das verhandelte Emissionsintervall nur eine Zelle aller 2029 Zellen ist.
Wenn zum Planen der Datentransporteinheiten oder Ströme mit verschiedenen Frequenzen zum Senden ein Kalender-Warteschlangen-Mechanismus verwendet wird, müssen die Ströme mit hoher Frequenz und hoher Priorität mit der Genauigkeit einer einzigen Zellzeit aufgelöst werden, während sie zum Erreichen eines akzeptabel niedrigen CDV geplant werden, aber die Ströme mit niedriger Frequenz/niedriger Priorität können grober aufgelöst werden mit einer Genauigkeit von beispielsweise 16 Zellzeiten. Das bedeutet, dass die Anzahl der Zeitslots auf der Kalender-Warteschlange 63 verringert werden kann. Dadurch kann der Speicherbedarf verringert werden, der zum Umsetzen der Kalender-Warteschlange 63 benötigt wird, zu Lasten des Verlustes einer normalerweise unnötigen Genauigkeit in der Planung der Zellen des Warteschlangenkopfes von Strömen mit niedriger Frequenz.
Es sollte verständlich werden, dass die Frequenz-basierte Priorisierungstechnik, die die vorliegende Erfindung für das Auflösen von Sendekonflikten an Multiplexierungs-Punkten unter Strömen verschiedener normalerweise fester Frequenzen bereitstellt, in vielen verschiedenen Anwendungen zur Reduzierung der relativen Schwankungen der Ströme angewandt werden kann, einschließlich in Anwendungen mit Work-Conserving-Pro-Strom-Ausgabe-Warteschlangen zum Eingeben von Zellen oder anderen Datentransporteinheiten in solch einen Multiplexierungs-Punkt.
D. Traffic-Shaping an MCR- und PCR-Parameter für ABR-Dienste in Netzwerken mit Quelle-zu-Ziel-ABR-Steuerloops
Der ABR-Traffic-Contract betrachten festgelegte PCR- und MCR-Parameter explizit oder implizit, wobei MCR gleich 0 sein kann. Ein ABR-Strom, der mit diesen GCRA (1/MCR, τ_MCR) ist gültig und hat Anspruch auf den Dienst, aber unter Umständen stellt das Netzwerk dem Strom nicht die Bandbreite zur Verfügung, auf die er Anspruch hat. Im Gegensatz dazu ist ein Strom, der seine GCRA (1/PCR, τ_PCR) verletzt, fehlerhaft. Daher sind ABR-Verbindungen oder -Ströme, die an die Ausgabe eines Netzwerks oder Netzwerkelements wie beispielsweise durch den ATM-Switch 21 geroutet werden, vorzugsweise geformt um sicherzustellen: (1) dass der ABR-Strom mit MCR-Garantien von nicht Null adäquate Ausgabebandbreite erhalten, damit diese Garantien effektiv erfüllt werden; und (2) dass keiner der ABR-Ströme seine PCR-Verpflichtung bei einer solchen Ausgabe verletzt. In Netzwerken mit mehreren Multiplexierungs-Punkten ist es hilfreich, dieses Shaping an jedem der Multiplexierungs-Punkte durchzuführen.
4 zeigt eine Technik für das Shaping von ABR-Strömen oder virtuellen ATM-Kanal-Verbindungen (VC-Verbindungen), um diese an einer Ausgabe eines Netzwerkes oder Netzwerkelements mit ihren Traffic-Contracts in Übereinstimmung zu bringen. Wie gezeigt, werden die Raten, mit denen die entsprechenden Ströme Ausgabedienste anfordern, überwacht; zunächst um bei 85 zu bestimmen, ob die Ströme GCRA (1/MCR, τ_MCR) konform sind oder nicht, und dann um bei 86 zu bestimmen ob die GCRA (1/MCR, τ_MCR) nicht-konformen Ströme GCRA (1/PCR, τ_PCR) konform sind oder nicht. Steuersignale, die die Ergebnisse dieser stufenförmigen Tests 85 und 86 wiedergeben, werden in den Planer 62 und seine verknüpfte Lenkungslogik 87 eingespeist, um entsprechende Raten-Shaping-Anpassungen an den Raten zuzulassen, mit denen die Datentransporteinrichtungen (zum Beispiel Zellen) der jeweiligen Ströme in die Ausgabe eingespeist werden. Es wird erkannt werden, dass der gewünschte Zustand für alle der ABR-Ströme GCRA (1/MCR, τ_MCR) nicht-konform (oder gerade so entsprechend) und GCRA (1/PCR, τ_PCR) falsch/konform ist, da diese Algorithmen jeweils auf minimal oder maximal akzeptable Stromraten testen.
Im Speziellen können GCRA (1/MCR, τ_MCR) konforme Ströme nicht die Ausgabebandbreite erhalten, die sie benötigen, um ihre MCR-Garantien zu erfüllen. Wird daher solch ein Strom bei 85 identifiziert, sind der Planer 62 und seine Lenkungslogik 87 so eingerichtet, dass nachfolgend empfangene Referenzen auf Datentransporteinheiten (beispielsweise Zellen) dieses Stroms in einer Stalled-Virtual-Clock-Kalender-Warteschlange mit hoher Priorität 88 zur Ausgabe mit einer Rate geplant werden, die leicht über seiner garantierten MCR liegt. Zum Beispiel werden diese nachfolgend empfangenen Zellen- oder Paketreferenzen passenderweise auf der Kalender-Warteschlange 88 für die Ausgabe mit einer Rate geplant, die durch Multiplizieren des MCR für den Strom mit einem vorgegebenen Beschleunigungsfaktor bestimmt wird. Das veranlasst das Netzwerk diesen zusätzlich potentiell „zögernden" Strömen die zusätzliche Ausgabebandbreite zu geben, die diese benötigen, um ihre MCR-Garantien zu erfüllen.
ABR-Ströme, die mit GCRA (1/MCR, τ_MCR) nicht konform sind, werden bei 86 weiter getestet um festzustellen, ob sie Ausgabedienste mit jeweils akzeptabel niedrigen oder inakzeptabel hohen GCRA (1/PCR, τ_PCR) kompatiblen oder nicht kompatiblen Raten anfordern. Die Ergebnisse dieses Tests werden von einem anderen Steuersignal erfasst, das zurück in den Planer 62 und seine Lenkungslogik 87 eingespeist wird, um sie für Raten-sensitives Einreihen der nachfolgend empfangenen Referenzen zu diesen GCRA (1/MCR, τ_MCR) nicht-kompatiblen Strömen auf einer Warteschlange mit niedrigerer Priorität 89 einzurichten. Im Speziellen werden die nachfolgend empfangenen Referenzen zu einem Strom, der bei 86 als GCRA (1/PCR, τ_PCR) kompatibel beurteilt wurde, an das Ende der Sendeliste für die ABR-Ströme mit MCR-Garantien angehängt, da er in Rundlaufreihenfolge bedient wird. Im Gegensatz dazu werden, wenn ein Strom bei 86 als GCRA (1/PCR, τ_PCR) nicht-kompatibel beurteilt wird, die nachfolgend empfangenen Referenzen für diesen Strom vom Planer 62 auf einer Non-Work-Conserving, Stalled-Virtual-Clock-Kalender-Warteschlange 89 in Übereinstimmung mit der PCR für diesen Strom geplant, wobei diesem Strom ein PCR-Limit auferlegt wird.
Allgemeiner wird deutlich, dass das Ausführungsbeispiel der 4 folgenden ABR-Traffic-Shaping-Algorithmus umsetzt:
Wenn GCRA (1/MCR, τ_MCR) kompatibel, dann in Warteschlange mit hoher Priorität bei Rate MCR·speedup einreihen
sonst wenn GCRA (1/PCR, τ_PCR) kompatibel, dann in Work-Conserving-Warteschlange mit niedriger Priorität einreihen
sonst in Non-Work-Conserving-Warteschlange mit niedriger Priorität basierend auf PCR-Emissionsintervall einreihen.
Alternativen, die auf ähnlichen oder unterschiedlichen Prinzipien basieren, drängen sich von selbst auf.
Wie beispielsweise in 5 gezeigt, besteht eine mögliche Alternative dann, die Referenzen zu den Datentransporteinheiten oder Zellen von Flüssen, die bei 85 und 86 ( 4) jeweils als GCRA (1/MCR, τ_MCR) nicht-kompatibel und GCRA (1/PCR, τ_PCR) kompatibel eingestuft wurden, sowohl in (1) der Kalender-Warteschlange mit hoher Priorität 88 bei einem MCR-Planungsintervall und (2) dem Work-Conserving-Bereich der Warteschlange mit niedriger Priorität einzuordnen. Dadurch wird eine „Wettbewerbs-" Bedingung erzeugt, da immer dann, wenn eine Instanz einer solchen dual eingereihten Refe renz in einer der Warteschlangen für die Bedienung bereit ist, ein Entknüpfer 91 die andere Instanz dieser Referenz aus der anderen Warteschlange entfernt. Das bedeutet, dass an der Toleranz τ eine engere Begrenzung unterhalten werden kann. Der Traffic-Shaping-Algorithmus dieses geänderten Ausführungsbeispiels lautet:
Beim Einreihen:
Reihe in Warteschlange mit hoher Priorität mit Rate MCR ein;
wenn GCRA (1/PCR, τ_PCR) kompatibel, dann in Work-Conserving-Warteschlange mit niedriger Priorität einreihen;
sonst in Non-Work-Conserving-Warteschlange mit niedriger Priorität basierend auf PCR-Emissionsintervall einreihen;
Beim Entfernen:
wenn Entfernen aus Warteschlange mit hoher Priorität, dann entknüpfe aus Warteschlange mit niedriger Priorität, sonst entknüpfe aus Warteschlange mit hoher Priorität.
6 zeigt eine weitere Alternative für das Shaping von ABR-Verbindungen oder – Strömen. In diesem Ausführungsbeispiel wird die Ausgabebandbreite, die für jeden MCR nicht-kompatiblen ABR-Strom mit einer MCR-Garantie von nicht Null bereitgestellt wird, dynamisch angepasst basierend auf dem durchschnittlichen Abstand zwischen ABR-Zellen auf der Ausgabeverbindung (das heißt, auf der Sendeseite einer Leitungsschnittstelle) und der aktuellen Länge der ABR bereiten Warteschlange". Die aktuelle Länge Len dieser ABR bereiten Warteschlange" wird in geeigneter Weise durch Messen der Länge der Work-Conserving-Warteschlange auf den ABR-Sendelisten 65e und 65f wie bei 93 bestimmt. Auf der anderen Seite kann der durchschnittliche Abstand S zwischen ABR-Zellen auf der Kalender-Warteschlange bei 94 in Prozent bestimmt werden, indem die für ABR-Ströme verfügbare Bandbreite unter Berücksichtigung der Nicht-ABR-Ströme geteilt wird. Die für diese Nicht-ABR-Ströme benötigte Bandbreite wird passenderweise bei 94 durch Berechnen der gesamten Bandbreite bestimmt, die für das Bedienen der Einträge in der Sendeliste 65 für die Nicht-ABR-Ströme benötigt wird.
Wird beispielsweise bei 94 festgestellt, dass 50% der Bandbreite der Ausgabeverbindung für ABR-Ströme verfügbar ist, dann folgt, dass der durchschnittliche Abstand S zwischen ABR-Zellen oder Datentransporteinheiten auf der Ausgangsverbindung zwei Zellzeiten beträgt. Diese Informationen in Verbindung mit der errechneten Länge Len der ABR "bereiten Warteschlange" ermöglichen die Optimierung des Dienstes für MCR nicht kompatible ABR-Ströme, indem der Planer 62 veranlasst wird, die eingehenden Referenzen für diese Ströme auf der Non-Work-Conserving-Kalender-Warteschlange 89 bei entsprechenden Emissionsintervallen T_t zu planen von: Tt = Min (St, Max (Pt, R)) (3)Wobei: R = eine geschätzte Rundlauf-ABR
Dienstzeit (R = aktuelle Zeit + S·Len);
P_t = der früheste mit dem Service-Contract kompatible Start für die nächste Zelle dieses Stroms t (P₁ = aktuelle Zeit + 1/PCR); und
S_t = der späteste mit dem Service-Contract kompatible Start für die nächste Zelle dieses Stroms t (S₁ = aktuelle Zeit + 1/MCR).
E. Traffic-Shaping für segmentierte ABR-Verbindungen
Es ist bekannt, dass ABR-Verbindungen wie in 7 bei 101 gezeigt mit Quelle-zu-Ziel-Steuerloops arbeiten können, oder wie in 8 bei 102 gezeigt mit segmentierten Steuerloops. Werden segmentierte Steuerloops verwendet, fungiert jedes der getrennt gesteuerten Segmente als virtuelle Quelle, VS, für das nächste Segment. Somit wird jedes ABR-Steuersegment (außer das erste) von einer virtuellen Quelle bezogen, die das Verhalten eines ABR-Quellenendpunkts annimmt. Vorherige Ressourcen-Mangement-(RM) Zellen werden aus dem Steuerloop entfernt, wenn sie von einer virtuellen Quelle empfangen werden. Jede Quelle oder virtuelle Quelle kann jedoch eine Schätzung der verfügbaren Netzwerkbandbreite für ihr Ziel oder virtuelles Ziel (VD) basierend auf dieser Rückmeldung berechnen, was wiederum auf einer Pro-Segment-Basis als Erlaubte Zellenrate (ACR – Allowed Cell Rate) ausgedrückt werden kann. Daher wird ABR-Traffic-Shaping für diese ABR-Verbindungen mit segmentierten Steuerloops vorzugsweise Segment-für-Segment ausgeführt, indem eine maximal zulässige Pro-Strom-Datentransporteinheit oder Zellenrate von Max(MCR, Min(ACR, PCR) verwendet wird. Die Ausführungsbeispiele der 4–6 können solches Traffic-Shaping umsetzen, indem PCR' gleich Max(MCR, Min(ACR, PCR) gesetzt wird und dann in den Berechnungen PCR' anstelle von PCR verwendet wird.

Claims

Verfahren zum Formen zeitmultiplexierter serieller Ströme von Paketen zu entsprechenden ABR (available bit rate)-Netzwerk-Traffic-Contracts in einem Netzwerk mit einem segmentierten Regelkreis (102), der so konfiguriert ist, dass er segmentweise Überlastkontrolle für das Netzwerk bewirkt, wobei die Traffic-Contracts entsprechende minimale und maximale Paketemissionsraten für die Ströme und entsprechende Toleranzen für die Raten bestimmen und das Verfahren umfasst: Analysieren von Überlastkontroll-Aktivität in den entsprechenden Segmenten des Regelkreises (102), um zu schätzen, wie viel Bandbreite die entsprechenden Segmente des Netzwerkes für Verkehr mit verfügbarer Bandbreite bereitstellen können; Verwenden der Bandbreiten-Schätzwerte, um zulässige Paketraten für die entsprechenden ABR-Ströme in den entsprechenden Segmenten des Netzwerks zu berechnen, Verfeinern der maximalen Paketemissionsraten für die entsprechenden Ströme in den entsprechenden Segmenten des Netzwerks, indem die Raten so eingestellt werden, dass sie den entsprechenden Grenzwerten annähernd gleich sind, ohne die Toleranzen für die Raten materiell zu ändern, wobei der Grenzwert für die verfeinerte maximale Paketrate für einen jeweiligen der Ströme in einem jeweiligen der Segmente eine Obergrenze, die der geringeren von der zugesicherten maximalen Paketrate für den Strom und der zulässigen Paketrate für den jeweiligen Strom in dem jeweiligen Segment des Netzwerkes annähernd gleich ist, und eine Untergrenze hat, die der zugesicherten minimalen Paketrate für den jeweiligen Strom annähernd gleich ist; Steuern der Raten, mit denen Pakete der jeweiligen Ströme in die jeweiligen Segmente der Netzwerke emittiert werden, indem die Pakete eines jeweiligen Stroms zur Emission in ein jeweiliges Segment des Netzwerkes selektiv (I) in eine Non- Work-Conserving-Kalender-Warteschlange eingereiht werden, wenn die Rate, mit der Pakete des jeweiligen Stroms in dem jeweiligen Segment des Netzwerkes fließen, mit dem Traffic-Contract für den jeweiligen Strom, der durch die verfeinerte maximale Paketrate modifiziert worden ist, nicht übereinstimmt, und (II) in eine Work-Conserving-Warteschlange, wenn die Rate mit dem Contract übereinstimmt.
Verfahren nach Anspruch 1, wobei Pakete des jeweiligen Stroms in eine erste Non-Work-Conserving-Kalender-Warteschlange zur Emission in das jeweilige Segment des Netzwerkes mit einer Rate eingegliedert werden, die über der zugesicherten minimalen Emissionsrate für den Strom liegt, wenn die Rate, mit der die Pakete in dem jeweiligen Netzwerk fließen, in Bezug auf die minimale Rate außerhalb der Toleranz liegt; Pakete des jeweiligen Stroms in eine zweite Non-Work-Conserving-Kalender-Warteschlange zur Emission in das Netzwerk-Segment mit einer Rate eingegliedert werden, die annähernd der verfeinerten maximalen Emissionsrate für den Strom in dem Segment entspricht, wenn die Rate, mit der die Pakete in dem Segment fließen, in Bezug auf die verfeinerte maximale Rate außerhalb der Toleranz liegt; die erste Non-Work-Conserving-Kalender-Warteschlange (88) eine höhere Priorität hat als die Work-Conserving-Warteschlange, um Planungskonflikte zwischen ihnen aufzuheben, und die zweite Non-Work-Conserving-Kalender-Warteschlange von unbestimmter Priorität relativ zu der ersten Warteschlage und der Work-Conserving-Warteschlange ist.
Verfahren nach Anspruch 2, wobei Pakete des jeweiligen Stroms auch in die Work-Conserving-Warteschlange eingereiht werden, wenn die Rate, mit der die Pakete in dem jeweiligen Segment fließen, in Bezug auf die minimale Rate außerhalb der Toleranz liegt; Pakete, die sowohl in die erste Kalender-Warteschlange als auch die Work-Conserving-Warteschlange eingereiht werden, von einer dieser Warteschlangen gelöst werden, wenn sie aus der anderen entfernt werden, um so die Wettlaufsituationen (race conditions) aufzuheben, die durch derartiges Einreihen geschaffen werden.
Verfahren nach den Ansprüchen 2 oder 3, wobei die erste und die zweite Kalender-Warteschlange entsprechende verknüpfte, in Echtzeit indexierte Datenstrukturen sind.
Verfahren nach Anspruch 4, wobei die zweite Kalender-Warteschlange und die Work-Conserving-Warteschlange dynamisch neu zugeordnete Segmente einer der Datenstrukturen sind und die Neuzuordnung derartiger Datenstruktur-Segmente von einem Zeiger gesteuert wird, der die Datenstrukturen als eine Funktion von Echtzeit zyklisch durchläuft.
Verfahren nach Anspruch 5, wobei die Pakete eine einheitliche feste Bitlänge haben.
Verfahren nach Anspruch 6, wobei Pakete aus der Work-Conserving-Warteschlange gemäß einer Strategie entfernt werden, die annähernd Rundlauf (Round Robin)-Service für Pakete ermöglicht, die in die Work-Conserving-Warteschlange eingereiht sind.
Verfahren nach Anspruch 7, wobei die Pakete Zellen fester Bitlänge für ATM-Verbindungen sind.
Verfahren nach einem der Ansprüche 1 bis 8, wobei das Verfahren in einem paketvermittelten Kommunikationssystem eingesetzt wird.