DE69912172T2

DE69912172T2 - Verfahren und Vorrichtung zur Steuerung der Verkehrsflüsse in einem Paketvermittlungsnetz

Info

Publication number: DE69912172T2
Application number: DE69912172T
Authority: DE
Inventors: Anthony Nepean Hung; Hossain Ottawa Pezeshki-Esfahani; Tom Ottawa Davis
Original assignee: Alcatel Canada Inc
Current assignee: Nokia Canada Inc
Priority date: 1998-02-12
Filing date: 1999-02-11
Publication date: 2004-07-01
Anticipated expiration: 2019-02-12
Also published as: DE69912172D1; EP0936834A3; EP0936834B1; CA2229577A1; EP0936834A2; US6353618B1

Description

Die vorliegende Erfindung betrifft allgemein das Gebiet des Datenverkehrsmanagements und genauer ein Verfahren und eine Einrichtung zum Steuern von Datenverkehrsströmen in einem Paketvermittlungsnetz, insbesondere einem ATM Netz, um eine Dienstqualität mit konstanter Bitrate zur Verfügung zu stellen.
Technischer Hintergrund
Das Konzept eines "Traffic Contract" (= Verkehrslastabkommen) ist Fachleuten auf dem Gebiet des Telekommunikationsnetz- Engineering wohl bekannt. Im wesentlichen vereinbart ein Benutzerendgerät, Pakete mit bestimmten vorher definierten oder ausgehandelten Verkehrsparametern zu senden, und als Gegenleistung stellt das Netz eine bestimmte Dienstqualität zur Verfügung. Wenn jedoch der Verkehrsfluss vom Endgerät zum Netzwerk nicht den Verkehrsparametern entspricht, die in einem vorbestimmten Konformitätsalgorithmus festgelegt sind, muss das Netzwerk die angeforderte Dienstqualität nicht erbringen.
Die zu vereinbarenden Merkmale einer ATM Verbindung sind in ATM Verkehrsmanagementprotokollen festgelegt, z. B. in den ATM Forum Verkehrsmanagementspezifikationen, Version 4.0, Dokument Nr. af-tm-0056.000, April 1996, auf die hier ausdrücklich Bezug genommen wird.
Diese zu vereinbarenden Merkmale umfassen:

(a) die gewünschten Dienstkategorie- und QoS Parameter, wie Zellenverlustverhältnis und Zellenverzögerung;
(b) den Verkehrs- Descriptor, umfassend beispielsweise PCR und CDVT, die im einzelnen weiter unten beschrieben werden; und
(c) die Konformitätsdefinition, die die konformen Zellen der Verbindung unzweideutig festlegt.

Eine Dienstkategorie, die im ATM Verkehrsmanagementprotokoll definiert ist, ist ein Dienst mit konstanter Bitrate (CBR = Constant Bit Rate), der eine Verbindung mit statischer Bandbreite herstellt, die ununterbrochen während der gesamten Dauer der Verbindung zur Verfügung steht. Die angeforderte Bandbreite ist gekennzeichnet durch die Spitzenzellrate (PCR = Peak Cell Rate). Eine andere Dienstkategorie ist ein Dienst mit unspezifizierter Bitrate (UBR = Unspecified Bit Rate), bei dem es auch einen Wert PCR für die Spitzenzellrate gibt, das Netz kann versuchen, diese zu erreichen, garantiert aber nicht, diese einzuhalten. Die Spitzenzellrate PCR wird ausdrücklich für jede ATM Verbindungsanforderung angegeben. So schließt ein Setup Befehl für eine geschaltete virtuelle Verbindung (SVC = Switched Virtual Connection) ein Informationselement (IE = Information Element) ein, das den PCR Wert spezifiziert.
Die Zellenverzögerungsschwankung CDVT (= Cell Delay Variation Time) ist ein Maß für die maximal erlaubte Burstiness einer CBR Verbindung. Wenn Pakete oder Zellen von zwei oder mehr Verbindungen in einem Knoten gemultiplext werden, können Zellen aus einer gegebenen Verbindung verzögert werden, während Zellen einer anderen Verbindung am Ausgang des Multiplexers eingefügt werden. Ähnlich können einige Zellen verzögert sein, wenn Physical Layer Overhead Zellen eingefügt werden. Demzufolge kann es mit Bezug auf das Spitzenzellensendeintervall T, was der Kehrwert der vereinbarten PCR ist, einige Zufallsschwankungen bei den gegenseitigen Ankunftszeiten zwischen aufeinander folgenden Zellen einer Verbindung geben, betrachtet an der Schnittstelle zwischen Teilnehmer und Netz (UNI = User- to- Network Interface). Die obere Grenze des Grades zulässiger Zusammenballung oder Burstiness ist der CDVT Parameter. Gegenwärtig wird dieser Parameter nicht ausdrücklich ausgehandelt, wenn vom Netz eine Verbindungsanforderung empfangen wird, wird dagegen aber zum Zeitpunkt der Anmeldung implizit vereinbart.
Die ATM Konformitätsdefinition verwendet den Allgemeinen Zellenratenalgorithmus (GCRA = Generic Cell Rate Algorithm), der benutzt wird, um im betriebsbereiten Zustand das Verhältnis zwischen PCR und CDVT zu definieren. Der GCRA wird mit zwei Parametern bestimmt, dem Schritt (I = Increment) und dem Grenzwert (L = Limit). Für den CBR Dienst ist I = T = 1/PCR und L = CDVT. Der GCRA ermittelt für jede eingehende Zelle, ob die Zelle den Traffic Contract der Verbindung einhält. Der GCRA wird in 1 dargestellt (Originalquelle: Seite 63 der ATM Forum Verkehrsmanagementspezifikationen, Version 4.0, Dokument Nr. af-tm-0056.000, April 1996). Die GCRA ist äquivalent zu einem (LBC = Leaky Bucket Controller) Algorithmus. Ein Datenstrom ist im wesentlichen GCRA (I, L) konform, wenn er einer LBC mit einer Bucketgröße von σ = 1 + L/I und einer Tokenrate von ρ = 1/I entspricht. Es ist anzumerken, dass eine LBC Steuerung mit den Parametern (σ, p) sicherstellt, dass die höchste Anzahl von konformen Zellen zwischen zwei beliebigen Zeitpunkten t₁ und t₂ nie mehr als σ + p * (t₂ – t₁) ist.
Eine Endeinrichtung kann als Quelle für eine Vielzahl von Verkehrsverbindungen abgebildet werden. Zum Beispiel kann ein Weitverkehrsnetzwerk zwei lokale Netzwerke umfassen, die durch ein öffentliches ATM Netzwerk verbunden sind. Jedes lokale Netzwerk umfasst eine Anzahl von Computerarbeitsplätzen, die durch eine Konzentratoreinrichtung verbunden sind, die die Datenströme von den verschiedenen Computerarbeitsplätzen zur Übertragung über das ATM Netz multiplext. Weil aus Sicht des Benutzers der Endeinrichtung, z. B. des Konzentrators, ein Schlüsselelement des Traffic Contracts die Reihenfolge der Zellen ist, die ans Netz gesendet werden, wird die Endeinrichtung typischerweise eine Zuweisungseinrichtung oder eine virtuelle Shaping Einrichtung verwenden, die den multiplexten Quellendatenstrom so verarbeitet, dass der Ausgangsdatenstrom in Richtung Netzwerk die im Traffic Contract festgelegten Verkehrsparameter erfüllt.
Auf der Gegenseite der Benutzer – Netzwerkschnittstelle umfasst das Netzwerk normalerweise eine Verbindungssteuerungs- (CAC = Connection Admission Control)- Funktion, um festzustellen, ob eine Verbindungsanforderung erfüllt oder abgelehnt wird. Wie oben erläutert, definiert eine Verbindungsanforderung gewöhnlich die Quellverkehrsparameter und die angeforderte Dienstgüte oder Dienstqualitäts- (QoS = Quality of Service)- Klasse. Für eine geschaltete Verbindung, wie eine SVC tritt die Verbindungsanforderung zu der Rufursprungszeit ein, und bei einer Dauerverbindung, wie einer PVC, tritt die Verbindungsanforderung zu dem Zeitpunkt ein, an dem die Dauerverbindung eingerichtet wird. Die CAC wird nur unter der Voraussetzung eine Verbindungsanforderung annehmen dass die QoS für die bestehenden Verbindungen immer noch erfüllt werden, wenn die neue Anforderung akzeptiert wird. CAC wird normalerweise bei geschalteten Verbindungen auf der Basis Knoten für Knoten durchgeführt, und bei Dauerverbindungen von einem zentralen Bandbreitenmanagement- System. Für angenommene Verbindungsanforderungen bestimmt die CAC die Konfiguration des Verkehrskonformitätsalgorithmus, das Routing und Ressourcenzuordnung, einschließlich Leitungsbandbreite, Puffergröße und interne Ressourcen. Es ist selbstverständlich, dass zur Erreichung hoher Schaltfrequenzen die CAC einfach sein muss und sehr schnell arbeiten muss.
Wenn eine Verbindung akzeptiert wird, muss das Netzwerk normalerweise die Verbindung am Zugang der Endeinrichtung überwachen, um die Ressourcen des Netzwerks vor einem Verhalten zu schützen, das die QoS von schon bestehenden Verbindungen beeinträchtigen kann. Das wird erreicht durch Erkennen von Verstößen gegen ausgehandelte Parameter und das Ergreifen geeigneter Maßnahmen. In den ATM Standards wird diese Funktion allgemein als Anwenderparameterüberwachung (UPC = Usage Parameter Control) bezeichnet. Die UPC nutzt normalerweise den GCRA zur Überwachung der Verbindung. Es gibt jedoch Fälle, bei denen aus verschiedenen Gründen eine UPC an der Peripherie des Netzes nicht durchgeführt werden kann.
Netzwerkknotenelemente haben auch die Aufgabe, die Verkehrsflüsse zu beeinflussen. Das ist so, weil ein Netzwerkelement die Zeitablaufplanung für eingehende Pakete oder Zellen von einer Vielzahl von Verbindungen oder Warteschlangen in eine ausgehende Verbindung vorzunehmen hat, die den Anschluss an ein Netzwerkelement als Gegenstück herstellt. Die Zeitablaufplanung, der Entscheider oder die virtuelle Shaping- Einrichtung eines Netzwerkelements muss eine wirksame Dienstdisziplin anwenden, um die verschiedenen Stufen von QoS und Bandbreiteanforderungen zu erfüllen. Das empfangende Netzwerkelement kann beispielsweise nur einen bestimmten Grad von Paketzusammenballung oder Burstiness akzeptieren, d. h. eine bestimmte Paket- oder Zellenverzögerungstoleranz, andernfalls würden Puffer beim empfangenden Netzwerkelement überlaufen. Die Zeitablaufplanung, der Entscheider oder die virtuelle Shaping- Einrichtung eines Netzwerkelements soll Idealerweise sehr schnell arbeiten, um hohe Schaltfrequenzen zu erreichen. Ein Beispiel einer solchen Einrichtung ist in der EP 0 817 430 offenbart.
Zusammenfassung
Verallgemeinert ausgedrückt stellt die vorliegende Erfindung ein Verfahren und eine entsprechende Einrichtung für die zeitliche Ablaufplanung für Pakete auf eine nicht werkkonservierende Weise an einem Warteschlangenpunkt zur Verfügung, um die maximale Burstiness oder Jitter eines Paketstroms zu minimieren oder wenigstens zu beziffern.
Entsprechend einem ersten Aspekt der Erfindung wird ein Datenkommunikationsverfahren für die Anwendung in einem Paketvermittlungsnetz zur Verfügung gestellt. Das Verfahren umfasst:

(a) Empfang von Datenpaketen von einer Verkehrsquelle, wie einer Verbindung und Einreihen der Pakete in einem Speicher;
(b) Festlegung eines sich wiederholenden Ablaufrahmens mit einer Dauer von FD und insgesamt FL Zeitschlitzen;
(c) Aufrechterhalten einer geordneten Liste von freien Zeitschlitzen;
(d) Festlegung einer Anzahl N_new von Zeitschlitzen, die notwendig sind, um die Bandbreiteanforderung der Verkehrsquelle zu erfüllen;
(e) Ermittlung eines Satzes {I[0], I[1], I[2] ...I[N_new – 1]} von idealen Zeitschlitzpositionen zur Erfüllung der Bandbreitenanforderungen der Verkehrsquelle, die voneinander beabstandet sind mit einer Zeit, die im wesentlichen gleich einem Spitzenübertragungsintervall zwischen den Datenpaketen ist;
(f) Zuteilung eines Satzes {VC[0], VC[1], VC[2] ...VC[N_new – 1]} von freien Zeitschlitzen an die Verbindung, die die besagten idealen Zeitschlitzpositionen annähern oder erfüllen, wobei ein gegebener VC[i]: i ∊ {1, 2, ..., N_new – 1} als einer der freien Zeitschlitze ausgewählt wird, der das über alles betrachtete Burstverhältnis der besagten Verbindung nicht erhöht und falls ein solcher freier Zeitschlitz nicht existiert, ein Zeitschlitz als einer der freien Zeitschlitze ausgewählt wird, der das über alles betrachtete Burstverhältnis der Verbindung am geringsten erhöht; und
(f) Auslesen der aufgereihten Datenpakete aus dem Speicher und Übertragen der ausgelesenen Datenpakete nur zu den entsprechenden Zeitabschnitten, die den zugeteilten Zeitschlitzen entsprechen.

Bei dem bevorzugten Ausführungsbeispiel wird das über alles betrachtete Burstverhältnis der Verbindung definiert als die Größe (ME + ML) * FD/FL, wobei ME einer Maximalzeit entspricht, um die ein beliebiger zugeteilter Zeitschlitz VC[j] früher auftritt als ein entsprechender idealer Zeitschlitz I[j], j ∊ {0, 1, 2, ... N_new – 1}, und ML einer Maximalzeit entspricht, um die ein beliebiger zugeteilter Zeitschlitz VC[k] später auftritt als ein entsprechender idealer Zeitschlitz I[k], k ∊ {0, 1, 2, ... N_new – 1}. Bei dem bevorzugten Ausführungsbeispiel ist die Komplexität der Berechnung für die Ermittlung der Zeitschlitzzuordnung für eine neue Verbindung proportional zu FL, der Gesamtzahl der Zeitschlitze pro Rahmen.
Entsprechend einem weiteren Aspekt der Erfindung wird ein Verfahren angegeben, mit dem festgestellt werden kann, ob eine Verkehrsquelle, der ein Satz {VC[0], VC[1], ... VC[N_new – 1]} von Zeitschlitzen in einem FL, FL ≥ N_new Zeitschlitzzuordnungsrahmen mit der Dauer FD zugeteilt wurde, konform ist mit einem GCRA, der durch ein Spitzenpaketsendeintervall T und eine Paketverzögerungsschwankungszeit CDVT gekennzeichnet ist. Das Verfahren umfasst:

(a) Auswahl eines Satzes {I[0], I[1], ... I[N_new – 1]} von idealen Zeitschlitzpositionen für die Verkehrsquelle, wobei jeder Zeitschlitz I[j] vom Zeitschlitz I[j – 1], j ∊ {1, 2, ... N_new – 1}, beabstandet ist mit einer Zeit, die im wesentlichen gleich T ist;
(b) Auswahl eines Elements ME mit höchstem Wert aus dem Satz {I[k] – C[k]: k ∊ {0, 1, ... N_new– 1}} ; und wenn dies eine negative Zahl ist, ME auf null setzen;
(c) Auswahl eines Elements ML mit höchstem Wert aus dem Satz {C [k] – I[k]: k ∊ {0, 1, ... N_new – 1}} ; und wenn dies eine negative Zahl ist, ML auf null setzen; und
(d) Vergleich des Werts (ME + ML) * FD/FL mit CDVT und als Reaktion darauf Feststellung, ob die Verbindung den GCRA erfüllt.

Dieser Aspekt der Erfindung kann zusammen mit dem erwähnten ersten Aspekt der Erfindung benutzt werden, um iterativ zu ermitteln, ob die neue Verbindung GCRA konform sein wird, während die Zeitschlitze für eine neue Verkehrsquelle zugeordnet werden. Somit ermöglicht die Erfindung die Zulassung oder Zurückweisung von neuen Verkehrsquellen auf der Basis, ob die berechnete CDVT (Jitter) einen vorbestimmten Grenzwert überschreitet. Weiterhin wird, weil die Komplexität des Algorithmus proportional zu FL, der Gesamtzahl der Zeitschlitze pro Rahmen, ist, eine relativ schnelle Zugangskontrollentscheidung ermöglicht.
Ein weiterer Aspekt der Erfindung stellt ein Verfahren zur Zuteilung von Zeitschlitzen in einem TDMA Rahmen an eine Verkehrsquelle zur Verfügung, wobei der Rahmen die Dauer FD und eine Gesamtzahl von Zeitschlitzen FL hat. Das Verfahren umfasst:

(a) Festlegen einer Anzahl N_new von Zeitschlitzen, die benötigt werden, um die Bandbreiteanforderung der Verkehrsquelle zu erfüllen;
(b) Aufstellen einer Liste A[i]: i ∊ {0, 1, ..., N_new – 1} von bevorzugten Zeitschlitzpositionen;
(c) Auswahl einer Liste C[i]: i∊ {0, 1, ..., N_new – 1} von Zeitschlitzen aus einer vorbestimmten, sortierten Liste B von Zeitschlitzen für die Verkehrsquelle, die die bevorzugten Zeitschlitzpositionen annähern oder erfüllen, wobei C[i] ∀i als ein Zeitschlitz aus B ausgewählt wird, der das über alles betrachtete Burstverhältnis der besagten Verkehrsquelle nicht erhöht, und falls ein solcher Zeitschlitz nicht existiert, ein Zeitschlitz aus B ausgewählt wird, der das über alles betrachtete Burstverhältnis der Verkehrsquelle am geringsten erhöht; und
(d) Entfernen der Einträge C aus B.

Dieser Aspekt der Erfindung kann dazu benutzt werden, Zeitschlitze an eine bis dahin inaktive Verkehrsquelle zuzuteilen; d. h. an eine, der keine Zeitschlitze zugeteilt sind. In diesem Fall ist A eine Liste idealer Zeitschlitzpositionen für besagte Verkehrsquelle, die voneinander beabstandet sind mit einer Zeit, die im wesentlichen gleich einem Spitzenübertragungsintervall zwischen Datenpaketen von besagter Verkehrsquelle ist; und B ist eine sortierte Liste von freien Zeitschlitzen im Rahmen.
Dieser Aspekt der Erfindung kann auch dazu benutzt werden, Zeitschlitze an eine aktive Verkehrsquelle zuzuteilen; die eine Reduzierung der Bandbreite angefordert hat. In diesem Fall hat die Verkehrsquelle M ihr früher zugeteilte Zeitschlitze; und N_new < M. A ist eine Liste von idealen Zeitschlitzpositionen für die besagte Verkehrsquelle, die voneinander beabstandet sind mit einer Zeit, die im wesentlichen gleich einem Spitzenübertragungsintervall zwischen Datenpaketen von besagter Verkehrsquelle ist; und B ist eine liste der der Verkehrsquelle früher zugeteilten M Zeitschlitze. Dies beschränkt die zugeteilten Zeitschlitze auf die der Verkehrsquelle früher zugeteilten Zeitschlitze und kann hilfreich sein, Unterbrechungen zu minimieren.
Dieser Aspekt der Erfindung kann auch dazu benutzt werden, Zeitschlitze an eine aktive Verkehrsquelle zuzuteilen; die eine Erhöhung der Bandbreite angefordert hat. In diesem Fall hat die Verkehrsquelle M ihr früher zugeteilte Zeitschlitze; und N_new > M. Die Schritte (c)–(d) werden vorzugsweise zweimal ausgeführt. Beim ersten Durchlauf wird A als eine Liste P gesetzt für die M der Verkehrsquelle früher zugeteilten Zeitschlitze und B wird als eine Liste idealer Zeitschlitzpositionen I für die Verkehrsquelle gesetzt, die voneinander beabstandet sind mit einer Zeit, die im wesentlichen gleich einem Spitzenübertragungsintervall zwischen Datenpaketen von der Verkehrsquelle ist, um von I die idealen Zeitschlitzpositionen zu eliminieren, die am nächsten bei den entsprechenden Zeitschlitzpositionen in A liegen und eine Liste I zu erzeugen. Beim zweiten Durchlauf der Schritte (c) und (d) wird A auf I gesetzt und B wird als Liste von freien Zeitschlitzen gesetzt. Danach werden der Verkehrsquelle die in C aufgelisteten (beim zweiten Durchlauf ermittelten) Zeitschlitze und P zugeteilt. Somit sind die zugeteilten Zeitschlitze solche, die der Verkehrsquelle früher zugeteilt wurden plus einer Anzahl neuer Schlitze, die notwendig sind, um die Bandbreitenanforderung der Verkehrsquelle zu erfüllen.
Kurze Beschreibung der Zeichnungen
Die zuvor erwähnten und weitere Aspekte der Erfindung werden im folgenden mit Bezug auf die Zeichnungen verdeutlicht, diese dienen ausschließlich der Erläuterung und dürfen nicht als Beschränkung ausgelegt werden, wobei
1 ein Flussdiagramm des bekannten GCRA oder „Leaky Bucket" Algorithmus ist;
2 eine schematische Darstellung des Warteschlangen- Schiedsrichter- Problems ist, das eine Einrichtung zur Ablaufplanung, ein Entscheider oder „Virtual Shaper" zu bewerkstelligen hat,
3 in Form eines Pseudocodes ein Verfahren beschreibt, das eine Einrichtung zur Ablaufplanung nach dem ersten bevorzugten Ausführungsbeispiel ausführt, um einer neuen Verbindung Zeitschlitze in einem Planungsrahmen zuzuteilen;
4 ein Flussdiagramm des in 3 gezeigten Pseudocodes ist;
5 eine Übersicht ist, die anhand eines Beispieleingangssignals die verschiedenen Zustände der Variablen zeigt, die im Pseudocode von 3 verwendet werden;
6 ein Blockschaltbild eines Ausführungsbeispiels eines Netzwerkschalters ist, der die Ablaufplanung nach dem ersten bevorzugten Ausführungsbeispiel ausführt; und
7 ein Blockschaltbild eines weiteren Ausführungsbeispiels eines Netzwerkschalters ist, der eine drahtlose Nutzer- Netzwerk- Schnittstelle aufweist, und der die Ablaufplanung nach einem zweiten bevorzugten Ausführungsbeispiel ausführt, um Zeitschlitze in einem drahtlosen Zeitmultiplex- Zugangsrahmen (TDMA = Time Division Multiplexed Access) zuzuteilen, um ein Uplink von einem Endgerät zum Netz herzustellen.
Zusätzlich sind im Arihang "A" zwei Funktionen in Pseudocodeform dargestellt, die bei dem zweiten bevorzugten Ausführungsbeispiel verwendet werden, um die CDVT einer Verkehrsquelle zu berechnen und ihr eine Anzahl von Zeitschlitzen in einem TDMA Rahmen zuzuteilen.
Detaillierte Beschreibung von bevorzugten Ausführungsbeispielen
2 bis 6 beziehen sich auf ein erstes bevorzugtes Ausführungsbeispiel der Erfindung, bei dem jeder Eingangsdatenstrom aus Paketen oder Zellen, der in einen TDMA Rahmen gemultiplext wird, statische Bandbreitenanforderungen hat. Beispielsweise ist, wie im Folgenden erläutert wird, jeder Eingangsdatenstrom eine einzelne virtuelle Verbindung, die eine konstante Bitrate über ihre gesamte Lebensdauer erfordert. 7 und der Anhang "A" beziehen sich auf ein zweites bevorzugtes Ausführungsbeispiel der Erfindung, bei dem jeder Eingangsdatenstrom aus Paketen oder Zellen, der in einen TDMA Rahmen gemultiplext wird, dynamische Bandbreitenanforderungen hat. Beispielsweise besteht, wie im Folgenden erläutert wird, jeder Eingangsdatenstrom aus einer oder mehreren virtuellen gemultiplexten Verbindungen. Bei diesem Ausführungsbeispiel variiert die Bandbreite des Eingangsdatenstroms mit der Zeit, weil neue Verbindungen, die mit diesem Eingangsdatenstrom verknüpft sind, aufgebaut werden und existierende Verbindungen unterbrochen werden.
Im Zusammenhang mit der Diskussion des ersten bevorzugten Ausführungsbeispiels zeigt 2 das Wareschlangen- oder Verbindungsproblem, das eine Einrichtung zur Ablaufplanung, ein Entscheider oder „Virtual Shaper" (im folgenden als "Scheduler" bezeichnet) zu bewerkstelligen hat. Wie in 2 gezeigt, werden Pakete, wie ATM Zellen 14, aus einer Vielzahl von Verbindungen in eine Vielzahl von Verbindungswarteschlangen 12a, 12b, ... 12n eingereiht. Die Aufgabe des Schedulers 10 ist es, die Zellen 14 aus den verschiedenen Verbindungen auf eine abgehende Strecke 16 einzuteilen. Der Scheduler tut dies, indem er einen sich wiederholenden oder wiederholten TDMA oder Planungsrahmen 18 anwendet, der eine vorbestimmte Rahmendauer FD hat, die in eine feste Anzahl FL von Zeitschlitzen 20 mit im wesentlichen gleicher Dauer. Bei dem bevorzugten Ausführungsbeispiel arbeitet der Scheduler nicht werkerhaltend und kann deshalb als zur Klasse der leer laufenden "Weighted Rounded-Robin" (WRR) Scheduler gehörend bezeichnet werden. Einige der Zeitschlitze 20 sind als "frei" gekennzeichnet, d. h. der Scheduler 10 hat die betreffende Zeitperiode, die durch einen gegebenen Zeitschlitz 20 repräsentiert wird, nicht für die Übertragung von Zellen 14 aus einer der Warteschlangen 12 auf die abgehende Strecke 16 zugeteilt. Ähnlich können andere der Zeitschlitze 20 als "besetzt" gekennzeichnet werden, d. h. der Scheduler 10 hat die betreffende Zeitperiode, die durch einen gegebenen Zeitschlitz 20 repräsentiert wird, für die Übertragung von Zellen 14 aus einer bestimmten Warteschlange 12 auf die abgehende Strecke 16 zugeteilt.
Es wird jetzt eine Situation betrachtet, bei der eine neue Verbindung, repräsentiert durch die Warteschlange 13, über die abgehende Strecke 16 übertragen werden muss. Für einen Dienst mit konstanter Bitrate (CBR), gekennzeichnet durch einen Spitzenzellraten- Wert PCR, muss der Scheduler 10 der Verbindung eine Vielzahl von N_new freien Zeitschlitzen zuteilen. N_new kann mit Bezug auf die gewünschte Bandbreite β, normalisiert auf die Kanalrate CR der abgehenden Strecke 16 bestimmt werden, d. h.
Dementsprechend kann N_new wie folgt bestimmt werden: Nnew = rounddup (β * FL) (1)
Aus dem Vorstehenden wird deutlich, dass die tatsächliche (normalisierte) Bandbreite β_new, die der Scheduler 10 an die neue Verbindung 13 zuteilen muss, in den meisten Fällen größer sein wird als β, weil die Struktur des Planungsrahmens 18 so ist, dass nur ein diskreter oder quantisierter Bandbreitenbetrag (d. h. eine ganzzahlige Anzahl von Zeitschlitzen 20) über die Strecke 16 an eine gegebene Verbindung zugeteilt werden können. Der Wert β_new kann gefunden werden, wie durch Gleichung (2) gezeigt:
Im bevorzugten Ausführungsbeispiel teilt der Scheduler 10 N_new freie Zeitschlitze 20 im Planungsrahmen 18 an die neue Verbindung 13 zu.
Bei dem bevorzugten Ausführungsbeispiel werden auch ideale Zeitpunkte oder Zeitschlitzpositionen identifiziert, die, wenn sie der neuen Verbindung 13 zugeteilt würden, die gewünschte Bandbreite so zur Verfügung stellen, dass die Zeitschlitze einen gegenseitigen Abstand mit einer Zeit T_new haben, die im wesentlichen, wenn auch in den meisten Fällen nicht exakt, gleich dem Spitzenzellensendeintervall T = 1/PCR wie folgt:
Diese idealen Zeitpunkte oder Zeitschlitzpositionen würden, falls sie so zugeteilt würden, eine Zellenflussrate ergeben, die keine Zellenverzögerungsschwankungs- Zeit hat. Weil jedoch viele der tatsächlichen Planungsrahmen- Zeitschlitze 20, diesen idealen Zeitschlitzpositionen entsprechend, nicht für die neue Verbindung zur Verfügung stehen, z. B. weil sie bereits von einer bestehenden Verbindung 12 besetzt sind, bei dem bevorzugten Ausführungsbeispiel werden der neuen Verbindung 13 freie Zeitschlitze 20 zugeteilt, die die idealen Zeitschlitzpositionen wenigstens annähern. Das geschieht, um ein Zusammenballen von Zellen 14, die mit der neuen Verbindung 13 verknüpft sind, zu vermeiden und dementsprechend wird die Burstiness auf der abgehenden Strecke 16 reduziert.
Der Scheduler ermittelt wahlweise auch, ob die neue Verbindung die GCRA Merkmale, gekennzeichnet durch die Parameter I = T_new = 1/PCR und L = CDVT, d. h., ob die Verbindung GCRA(T_new, CDVT) konform ist oder nicht. Alternativ dazu stellt der Scheduler 10 einen Bestimmungsmechanismus zur Bildung eines Zellenstroms mit bekannter Zellenverzögerungsschwankung oder Jitter zur Verfügung.
Das vom Scheduler 10 angewendete Verfahren nach dem ersten bevorzugten Ausführungsbeispiel wird in Form eines Pseudocodes in 3 und entsprechend als Flussdiagramm in 4 gezeigt. Das bevorzugte Verfahren ist beispielhaft mit Bezug auf die 5A und 5B, die schematisch die Ausgangssituation eines hypothetischen 20- Schlitz-Planungsrahmens 18' (5A(i)), die wechselnden Zustände der Variablen, die im Pseudocode von 3 verwendet werden (5B), ideale Zeitschlitzpositionen für die neue Verbindung (5A(ii)) und den endgültigen Status des Planungsrahmens 18' (5A(iii)) zeigen.
Bezugnehmend auf diese Fig. wird in einem ersten Verfahrensschritt 30, der den Zeilen 100–117 des Pseudocodes entspricht, eine Anzahl von Konstanten und Datenstrukturen definiert, wie im Pseudocode angegeben. Die Beispielwerte für diese Konstanten und Datenstrukturen werden in Bezug auf das in 5A und 5B gezeigte Beispiel der Ausgangsbedingungen wie folgt festgelegt:
Ausgangsbedingungen
Aus dem vorstehenden wird deutlich, dass die neue Verbindung 13 im Beispiel fünf freie Zeitschlitze 20 benötigt.
Beim Schritt 32 des Flussdiagramms von 4, entsprechend der Pseudocodezeile 117, wird eine ideale Zeitschlitzposition I[i] ausgewählt. Vorzugsweise wird als erste ideale Zeitschlitzposition der erste freie Zeitschlitz F[0] festgelegt, wie das in Zeilen 112 und 115 des Pseudocodes angedeutet wird. Danach werden, wie in Zeile 117 des Pseudocodes gezeigt, weitere folgende ideale Zeitschlitzpositionen ermittelt im gegenseitigen Abstand von 1/β_new, der, wie aus Gleichung (3) ersichtlich, im wesentlichen gleich T, dem Spitzenzellensendeintervall der neuen Verbindung 13 ist. Beim vorliegenden Beispiel sind die idealen Zeitschlitzpositionen in einem gegenseitigen Abstand von
Zeitschlitzeinheiten angeordnet, wie das in 5A(ii) gezeigt wird. (Hier ist anzumerken, dass der Algorithmus das Festlegen eines idealen Zeitschlitzabstands als rationale Zahl erlaubt.) Bei den Schritten 34 und 36, die den Zeilen 120–132 des Pseudocodes entsprechen, werden die nächsten freien Zeitschlitze, die der der idealen, im Schritt 32 ausgewählten Zeitschlitzposition I[i] vorausgehen bezw. nachfolgen, identifiziert. So ist beispielsweise mit Bezug auf 5A(i) und 5A(ii) der Zeitpunkt, an dem der Zeitschlitz Nr. 5 beginnt, als ideale Zeitschlitzposition beim ersten Durchlauf der Schleife identifiziert, d. h. I[I] = 5. Es gibt keinen vorausgehenden freien Zeitschlitz (weil Zeitschlitz Nr. 1 bereits zugeteilt ist) und somit wird der Variablen a der Wert –∞ zugeordnet (siehe 5B). Der nächstliegende freie Zeitschlitz nach der idealen Zeitschlitzposition Nr. 5 ist der Zeitschlitz Nr. 6, und somit wird der Variablen b der Wert 6 zugeordnet (siehe 5B).
Beim Schritt 38, der den Pseudocodezeilen 133, 134, 136, 137, 138 und 140 entspricht, wird einer der freien Zeitschlitze, die bei den Schritten 34 und 36 identifiziert wurden, an die neue Verbindung 13 vergeben bezw. zugeteilt, der betreffende freie Zeitschlitz wird dann von der Liste oder dem Array der freien Zeitschlitze entfernt. Bei dem bevorzugten Verfahren kann, wenn beide freie Zeitschlitze, die in den Schritten 34 und 36 ausgewählt wurden, jeweils Abstände zu den idealen Zeitschlitzpositionen haben, die innerhalb von Grenzwerten oder der maximalen gegenseitigen Abstände, wie sie von dem oben beschriebenen jeweils zutreffenden ME- oder ML- Register definiert werden, liegen, einer der beiden Zeitschlitze der neuen Verbindung zugeteilt werden. Das stellt sicher, dass die über alles gesehene Burstiness der neuen Verbindung 13, die bei früheren Iterationen berechnet wurde, nicht erhöht wird. Wenn jedoch einer oder beide freien Zeitschlitze, die in den Schritten 34 und 36 gefunden wurden, nicht innerhalb der Rahmenwerte von ME oder ML liegen, wird der neuen Verbindung ein Zeitschlitz zugeordnet, der, wenn er so zugeteilt wird, den Wert ME + ML minimiert. Dies wird die über alles gesehene Burstiness der neuen Verbindung minimieren. Beispielsweise sind bei der zweiten Iteration der Schleife, d. h. bei i = 2, die ideale Zeitschlitzposition I[2] gleich 9, a = 8 und b = 16. Keiner der betrachteten nächsten freien Zeitschlitze a und b liegt innerhalb der durch ME und ML Register definierten Rahmenwere, weil jedoch der Zeitschlitz a einen kleineren ME + ML Wert ergibt als der Zeitschlitz b, wird der neuen Verbindung der Zeitschlitz a zugeteilt. Der Zeitschlitz a wird danach von dem Array F freier Zeitschlitze entfernt oder alternativ als nicht mehr zur Verfügung stehend markiert.
Beim Schritt 40 des Flussdiagramms von 4, der den Zeilen 135 und 139 des Pseudocodes entspricht, werden die Register ME bezw. ML aktualisiert, um die größte relative Distanz, um die ein gegebener VC[j] einer I[j], j∊ {0, 1, 2, ...N_new – 1} voreilt und die größte relative Distanz, um die ein gegebener VC[k] hinter einer I[k], k ∊ {0, 1, 2, ...N_new– 1} zurückbleibt, wiederzugeben. Die 5A(iii) zeigt schematisch die endgültigen Werte von ME und ML des vorliegenden Beispiels.
Beim Schritt 42, der der Zeile 142 des Pseudocodes entspricht, wird der Zähler für die Anzahl der freien Zeitschlitz Fn aktualisiert.
Beim Schritt 44 des Flussdiagramms von 4, der den Zeilen 143 bis 145 des Pseudocodes entspricht, wird der Wert (ME + ML)*FD/FL gegen CDVT abgeprüft. Dieser Vergleich, wie im einzelnen weiter unten beschrieben, wird durchgeführt, um auf iterativer oder globaler Basis festzustellen, ob die Zeitschlitzzuteilungen für die neue Verbindung 13 GCRA (T_new, CDVT) konform sind oder nicht. Wenn der Vergleich beim Schritt 44 "wahr" ist, wird beim Schritt 46 die neue Verbindung zurückgewiesen. Andernfalls wird beim Schritt 48 festgestellt, ob eine neue Iteration der Schritte 32–44 notwendig ist, um der neuen Verbindung 13 genügend Zeitschlitze zur Verfügung zu stellen.
Aus dem vorstehenden wird deutlich, dass bei dem bevorzugten Ausführungsbeispiel angestrebt wird, die Zeitschlitzzuteilungen für die neue Verbindung 13 so zu verteilen, die die Zellenverzögerungsschwankung oder Burstiness auf der abgehenden Strecke 16 reduziert. Bei dem bevorzugten Ausführungsbeispiel wird iterativ nach dem Satz von Zeitschlitzen N_new gesucht, wobei bei jeder Iteration angestrebt wird, die über alles betrachtete Burstiness der zugeteilten Zeitschlitze zu reduzieren. Das ist möglich, weil das bevorzugte Verfahren bei jeder Iteration die Burstiness, definiert als (ME + ML) FD / FL, für die bis zu diesem Punkt zugeordneten Zeitschlitze für jede Auswahl von Zeitschlitzzuordnungen berechnet. Somit kann das bevorzugte Verfahren intelligente Entscheidungen bei der Auswahl der nächsten Zeitschlitzposition treffen.
Unabhängig von irgendeiner Theorie wird der Vergleich von ME und ML gegen CDVT als ausreichend angesehen, ob die Verbindung GCRA (T_new, CDVT) konform ist auf Basis der folgenden mathematischen Analyse.
Analyse:
Einer Verbindung wird ein Strom von Zeitschlitzen zugeteilt, über die gesendet werden soll. Dabei sei d[i] i die geplante Zeit des i^ten Zeitschlitzes und I[i] sei der ideale Zeitpunkt für den i^ten Zeitschlitz: I[i] = d[1] + (i – 1)β–1 new i ∊ {1, 2, ...} (4) Weiterhin sei die nach GCRA theoretische Ankunftszeit (TAT = Theoretical Arrival Time), wie in 1 angedeutet, wie folgt definiert: TAT [i] = max {TAT [i – 1] + β–1 new , d [i]}, i ∊ {2, 3, ...} (5) TAT [I] = d [I]. (6)
Wegen dieser Definition ist d [i] ≤ TAT[i].
Dann sei j der kleinste i, so dass d [i] = TAT[i] und d [k] < TAT [k] für alle k > i, und ML sei = d [j] – I[j]. Damit ist für alle i ≥ j
Durch die Definition in der GCRA erfüllt die CDVT einer CBR Verbindung die Bedingung CDVT ≥ TAT [i] – d [i] für alle i. Man kann diese Grenze für TAT [i] – d [i] berechnen durch Einführen einer Variablen ME = max_i {I [i] – d [i]} und Anwendung von (9) für alle i ≥ j,
Somit ist L = ML + ME ≡ CDVT ausreichend für GCRA Konformität.
Der letzte Teil dieser Analyse zeigt, wie ML und ME berechnet werden können. Es ist anzumerken, dass die Planzeiten einem periodischen Muster folgen: d [i + Nnew] = d[i] + k × FL, i ∊ {1, 2, ...}, k ∊ {0, 1, 2, ...}. (12) So wird I[I + kNnew] = d[1 + kNnew]; (13) und d [i] – I [i] = d [i + kNnew] – I[i + kNnew] (14)
Schließlich kann man zuordnen
und CDVT ← (ME + ML) * FD/FL (17)
Deshalb können die Werte ML und ME gefunden werden durch Beobachten der größten Differenzen zwischen den idealen Zeitschlitzpositionen und den zugeteilten Zeitpunkten eines einzelnen Rahmens (dem ersten Rahmen).
6 zeigt die Architektur eines bevorzugten Netzwerkschalters 50, im Handel erhältlich unter der Modellbezeichnung 36170 MainStreet Xpress^TM Schalter von der Newbridge Network Corporations of Kanata, Ontario, Canada, der den Scheduler 10 enthält. Der Schalter umfasst ein Hochgeschwindigkeits- Schaltfeld 52 mit N Eingängen 56, die alle mit einem oder allen der N Ausgänge 58 verbunden werden können. Der Schalter 50 umfasst weiterhin ein oder mehrere Zubehör- oder Peripheriekarten 60 (von denen nur eine gezeigt ist), die eine Vielzahl von Universalkartensteckplätzen (UCS = Universal Card Slot) 62 aufweisen zur Aufnahme von Interfacekarten oder Systemkarten. Ein Beispiel einer Interfacekarte ist die Zellenrelaiskarte 64. Die Karte 64 umfasst ein Eingangsprozessormittel 66, um, falls notwendig, eingehende Daten von der Eingangsseite von Port 68 in ATM- kompatible Zellen zu konvertieren. Das Eingangsprozessormittel 66 überprüft auch das VPI/VCI Feld der ATM Zelle und fügt, basierend auf diesem Feld, zu den ATM Zellen eine interne Kennung oder einen Header hinzu, der dazu verwendet wird, eine interne Adresse zu identifizieren, zu der die ATM Zellen geroutet werden sollen. Die ATM Zelle einschließlich ihres Prioritätskennzeichens wird dann über einen "Add" Bus 70 zu dem Schaltfeld 52 geleitet.
Eine Netzknotenkarte 72, die einen Typ einer Systemkarte darstellt, multiplext eine Vielzahl von Add Bussen 70 von den verschiedenen Interfacekarten auf der Peripheriekarte 60 auf einen Hochgeschwindigkeits- "Intershelf Link" (ISL)- Bus 74, der die Peripheriekarte 60 mit dem Schalterfeld 52 verbindet. Die Netzknotenkarte ist auch Abschluss für die ISL Busleitung 74 vom Schalterfeld 52 und betreibt einen Multi- Drop Bus 76. Auf diese Weise kann jede Interface- oder Systemkarte mit jeder anderen Interface- oder Systemkarte kommunizieren.
Die Zellenrelaiskarte 64 umfasst ein Backplane oder ein Adressfiltermittel 78 zur Überwachung des Multi- Drop Bus 76 zum Kopieren oder Empfangen von Datenzellen auf diesem, die an die Karte 64 adressiert sind. Der Multi- Drop Bus 76 arbeitet mit relativ hoher Geschwindigkeit, z. B. 800 Mb/s und deshalb kann die Karte 64 mehr ATM Zellen empfangen als sie sofort bearbeiten kann. Um Zellenverlust zu vermeiden, enthält die Karte 64 ein Ausgangswarteschlangenmittel 80 zum Puffern von ausgehenden Zellen. Ein Ausgangsprozessormittel 82 stellt Zellen von den Warteschlangen, die das Ausgangswarteschlangenmittel 80 zusammengestellt hat, wieder her und überführt sie in das spezielle Format der Schnittstelle zur Übertragung auf der Ausgangsseite von Port 68. Weitere Details, die Architektur und die Arbeitsweise des Schalterfelds 10 betreffend, können aus der PCT Veröffentlichung WO 95/30318, die dem Inhaber der vorliegenden Anmeldung gehört, und die am 9. November 1995 veröffentlicht wurde und auf die hier ausdrücklich Bezug genommen wird, entnommen werden.
Das Schalterfeld 50 umfasst auch eine Systemsteuerkarte 84, die sich auf einem der UCS Steckplätze 62 befindet. Die Steuerkarte umfasst ein Verbindungs- und Zugangskontrollmittel (CAC = Connection and Admission Control) 86, wie aus dem Stand der Technik bekannt, zur Feststellung, ob eine neue Verbindung akzeptiert werden kann oder nicht. Deshalb wird, wenn die Karte 64 beispielsweise eine SVC Rufanforderungsmeldung empfängt, deren ATM Zellen an die Steuerkarte 84 zur CAC Verarbeitung geroutet.
In der Praxis wird der Scheduler 10 vorzugsweise von dem CAC Mittel 86 realisiert, immer dann wenn eine Anforderung für eine neue Verbindung eintrifft. Wie aus dem Vorstehenden hervorgeht, kann bei dem bevorzugten Verfahren auf iterativer Basis festgestellt werden, ob die neue Verbindung GCRA (T_new, CDVT konform ist oder nicht. Das erfordert eine Rechenkomplexität, die proportional zu FL, der Anzahl der Zeitschlitze im Planungsrahmen 18 ist. Gleichzeitig übernimmt das bevorzugte Verfahren die Zuteilung von Zeitschlitzen an die neue Verbindung. Diese Zeitschlitzzuteilungen verwendet das Ausgangsprozessormittel 82 zum Steuern der Datenzellen von dem Warteschlangenmittel 80 auf den Ausgangsport 68.
Zur Erläuterung des zweiten bevorzugten Ausführungsbeispiels zeigt 7 das Schalterfeld 50 konfiguriert für die Verwendung in einer drahtlosen Kommunikationsumgebung. Bei diesem Ausführungsbeispiel wird, wie in 7(i) gezeigt, einer der UCS Steckplätze 62 von einer ATM Funkschnittstellenkarte (ARIC = ATM Radio Interface Card) 90 belegt, die über einen Luftkanal mit einer Vielzahl von Netzschnittstelleneinheiten (NIU = Network Interface Unit) 92 kommuniziert. Die Übertragung vom ARIC 90 zu den NIUs 92 erfolgt in einem Funksendemodus. In der Gegenrichtung wird jedoch der Luftkanal den NIUs entsprechend einer TDMA Disziplin zur Verfügung gestellt, wie das in 7(ii) gezeigt wird. Jede NIU 92 ist Abschluss für eine Vielzahl von Verbindungen, wie T1 Datenströme, als Eingangssignale A, B, ... Y, Z gezeigt. Jede NIU umfasst ein Modul für Segmentierung und Wiederzusammenführung (SAR = Segmentation And Reassembly) 94, aus dem Stand der Technik bekannt zur Segmentierung der eingehenden Datenströme in ATM Zellen, die in einem Speicher 96 in einer Warteschlange zwischengespeichert werden und dann von einem Scheduler 10' in einen einzigen Zellendatenstrom gemultiplext werden. Der Scheduler 10' überträgt die Zellen dieses Datenstroms während der der NIU zugeteilten Zeitschlitze. Das System stellt demnach in Uplink- Richtung einen Zwei- Ebenen- Konzentrator dar. Es ist anzumerken, dass im Gegensatz zu der in Bezug zum ersten Ausführungsbeispiel beschriebenen Anwendung bei dieser Anwendung die Anzahl der Zeitschlitze, die für ein NIU erforderlich ist, nicht statischer Natur ist sondern recht dynamisch ist und zunimmt oder abnimmt, so wie Verbindungen zu der NIU aufgebaut oder beendet werden.
Bei dem zweiten bevorzugten Ausführungsbeispiel berechnet das CAC Mittel 86 die Zeitschlitzzuteilungen und die CDVT für jede NIU 92, die Bandbreite anfordert. Die CDVT wird mit einem vorbestimmten Grenzwert verglichen und die Bandbreitenanforderung wird akzeptiert oder zurückgewiesen. Wenn eine Anforderung akzeptiert wurde, werden die von der CAC vorgenommenen Zeitschlitzzuteilungen über die ARIC an die NIU übermittelt. Die TDMA Struktur wird anschließend eingesetzt, um sicherzustellen, dass alle Zellen GCRA konform sind, nachdem sie auf dem TDMA Rahmen übertragen werden, und der Netzwerkschalter 50 verwendet keine UPC Einrichtung zur Überwachung des Endgerätezugangs zum Netzwerk.
Der Anhang A listet zwei Funktionen in Pseudocodeform auf, die von dem System des zweiten Ausführungsbeispiels angewendet werden. Die Funktion calculate_CDVT() berechnet an und für sich die CDVT einer gegebenen Folge von Zeitschlitzen und ist nach der vorstehenden Diskussion leicht nachzuvollziehen. Die Funktion nearest() ist dem Algorithmus von 3 ähnlich, insbesondere bezüglich der Zeilen 70–104, aber umfasst Code bei den Zeilen 48–69 und 105–118, der, wie dort beschrieben wird, die Auswahl einer idealen Zeitschlitzposition, außer dem ersten freien Zeitschlitz eines TDMA Rahmens, erleichtert. Demnach ist der erste Zeitschlitz, der einer vorher inaktiven NIU zugeteilt wird, nicht notwendigerweise der erste freie Zeitschlitz. Dieses Merkmal hilft bei der Verteilung der Zeitschlitzzuordnungen für die verschiedenen NIUs über den TDMA Rahmen, was besonders nützlich ist, wenn die Bitraten ihrer Ausgangszellenströme in ähnlicher Größenordnung liegen.
Die bevorzugten Verfahren zur Zuteilung von Zeitschlitzen an eine inaktive NIU, das Entfernen von Zeitschlitzen einer aktiven NIU und das Hinzufügen von zusätzlichen Zeitschlitzen an eine aktive NIU werden im Folgenden beschrieben.
Zuteilen von Zeitschlitzen an eine bisher inaktive NIU
N ist die Anzahl der von der NIU angeforderten Zeitschlitze und F ist die Liste der freien Zeitschlitze.

1. Auswahl eines Index k aus der Liste der freien Zeitschlitze F, vorzugsweise durch gleichmäßige zufällige Auswahl im Bereich 0 ≤ k < length (F).
2. Bildung eines Arrays idealer Zeiten oder Zeitschlitzpositionen I wie folgt: for 0 ≤ i ≤ N
endfor Die Schritte 1 und 2 erleichtern die Verteilung der idealen Zeitschlitzpositionen und damit der zugeordneten Zeitschlitzpositionen, die versuchen, den idealen Zeitschlitzpositionen zu folgen, über den TDMA Rahmen.
3. Aufrufen: nearest (I, F, NULL, 0, 0, k), und setzen S ← C, wobei C der zurückgegebene Vektor ist, der die Zeitschlitzzuordnung spezifiziert. Wenn diese Funktion unter Verwendung der vorherigen Argumente aufgerufen wird, ist der Prozess sehr ähnlich dem Algorithmus, der in Verbindung mit dem ersten Ausführungsbeispiel diskutiert wurde. Insbesondere findet die Funktion solche freien Zeitschlitze in F, die am nächsten bei denen der Liste idealer Zeitschlitzpositionen 1 liegen.
4. Funktion aufrufen: calculate_CDVT (S, FL, FD). Die Funktion gibt ME und ML zurück und CDVT wird berechnet als

Entfernen von Zeitschlitzen von einer NIU
S sei der Vektor der gegenwärtig der NIU zugeteilten Zeitschlitze. M < length (S) sei die neue Anzahl der von der NIU benötigten Zeitschlitze. Dann:

1. Auswahl eines Index k aus S, vorzugsweise durch gleichmäßige zufällige Auswahl von k im Bereich 0 ≤ k < length (S).
2. Bildung eines Vektors idealer Zeiten I wie folgt: for 0 ≤ i < M
endfor
3. Funktionsaufruf: nearest (I, S, NULL, 0, 0, k). Dieser Schritt kann intuitiv verstanden werden, wenn man die Liste der Zeitschlitzzuteilungen S als "freie" Zeitschlitze betrachtet, von der eine reduzierte Anzahl bereits zugeteilter Zeitschlitze für die reduzierte Bandbreitenanforderung der NIU ausgewählt werden. Wenn die Funktion den Vektor zurückgibt, enthält S die bereits existierenden Zeitschlitze, die nicht länger benötigt werden, deshalb werden die Einträge von S zu der Liste von freien Zeitschlitzen zurückgegeben und der zurückgegebene Vektor S gespeichert: S ← C. Es ist verständlich, dass als alternatives Verfahren auch die Freigabe alter der NIU bereits zugeteilten Zeitschlitze und das erneute Ausführen des Verfahrens zum Hinzufügen von Zeitschlitzen in eine inaktive NIU in Frage kommt. Es wird jedoch vorgezogen, die Auswahl von Zeitschlitzen, die die ideale Position annähern, auf die Gruppe früher zugeteilter Zeitschlitze zu begrenzen, um Unterbrechungen zu minimieren, wenn einer NIU bereits früher eine Folge von Zeitschlitzen zugeteilt war.
4. Funktion aufrufen: calculate_CDVT (S, FL, FD) und speichern.

Hinzufügen von Zeitschlitzen in eine aktive NIU
S sei der Vektor der gegenwärtig der NIU zugeteilten Zeitschlitze. M < length (S) sei die neue Anzahl der von der NIU benötigten Zeitschlitze. Dann sind die folgenden Schritte:

1. Auswahl eines Index k aus S, vorzugsweise durch gleichmäßige zufällige Auswahl von k im Bereich 0 ≤ k < length (S).
2. Bildung eines Vektors idealer Zeiten I wie folgt: for 0 ≤ i < M
endfor
3. Funktionsaufruf: nearest (S, I, F, 0, 0, k) und den zurückgegebenen Vektor C verwerfen.
4. Auswahl eines Index j aus 1, (beispielsweise durch gleichmäßige zufällige Auswahl im Bereich 0 ≤ j < length (F)).
5. Aufsuchen eines k, so dass F[k] am nächsten bei I[j] liegt.
6. Funktionsaufruf: Unter Verwendung der Werte für ME und ML von Schritt 3: nearest (I, F, NULL, ML, ME, k). Der zurückgegebene Vektor C wird gespeichert. Das Vertauschen von ME und ML als Eingangswerte beim zweiten Aufruf von nearest () ist zu beachten.
7. Verbindung von C und S zu einem Vektor mit Einträgen in absteigender Reihenfolge und Ausgabe des Ergebnisvektors in S. Es ist anzumerken, dass dies möglich ist in einer Zeit, die proportional FL ist, weil die zu verbindenden Vektoren bereits sortiert sind.
8. Funktion aufrufen: calculate_CDVT (S, FL, FD) und speichern.

Es ist verständlich, dass als alternatives Verfahren auch die Freigabe aller der NIU bereits zugeteilten Zeitschlitze und das erneute Ausführen des Verfahrens zum Hinzufügen M von Zeitschlitzen in eine inaktive NIU in Frage kommt. Es wird jedoch aus den oben beschriebenen Gründen vorgezogen, die bereits zugeteilten Zeitschlitze nicht freizugeben. Das bevorzugte Verfahren erreicht das Ziel wie folgt. Bei den Schritten 1 und 2 wird eine Liste von M idealen Zeitschlitzpositionen für die neue erhöhte Bandbreitenanforderung erstellt. Bei Schritt 3 wird die Funktion nearest () zum ersten Mal aufgerufen. Es ist anzumerken, dass die Funktion nearest (A, B, ...) im Wesentlichen die Einträge im zweiten Argument B identifiziert, die am besten mit denen des ersten Arguments A übereinstimmen und entfernt diese Einträge aus B. Beim Hinzufügen von Zeitschlitzen zu einer aktiven NIU ist es notwendig, die Zeitschlitzzuordnungen auf M = N + m zu erhöhen, wobei N die Anzahl der bereits existierenden Zeitschlitzzuordnungen ist und m die Anzahl der zusätzlich erforderlichen Zeitschlitze. Weil gewünscht wird, die bereits existierenden Zeitschlitzzuordnungen nicht zu ändern, ist es notwendig, N Zeitschlitzpositionen aus der Liste der M idealen Zeitschlitzpositionen zu entfernen. Durch den Funktionsaufruf nearest (S, I, F, 0, 0, k), wobei der Vektor I als Argument B eingesetzt wird, werden die N idealen Zeikschlitzpositionen, die am nächsten bei den bereits existierenden Zeitschlitzen liegen, von der Liste der idealen Zeitschlitzpositionen gestrichen. Nachdem Schritt 3 ausgeführt ist, gibt es noch m Einträge in der Liste der idealen Zeitschlitzpositionen, die aus der Liste der freien Zeitschlitze ausgewählt werden müssen. Deshalb wird in Schritt 6 die Funktion nearest () ein zweites Mal ausgeführt, aber diesmal werden die Einträge aus der Liste der freien Zeitschlitzpositionen gelöscht.
Das oben beschriebene erste bevorzugte Ausführungsbeispiel hat den ersten freien Zeitschlitz in einem Planungsrahmen an eine neue Verbindung zugeteilt und auch den ersten freien Zeitschlitz als ideale Zeitschlitzposition identifiziert. Das zweite bevorzugte Ausführungsbeispiel erlaubt, dass der erste zugeteilte Zeitschlitz freizügiger aus der Liste der freien Zeitschlitze ausgewählt werden kann. Fachleute auf diesem Gebiet werden erkennen, dass diese Verfahren nicht notwendigerweise optimal arbeiten im Hinblick auf die Erzeugung eines Zellenstroms mit der kleinsten möglichen Zellenverzögerungsschwankung (d. h. ML + ME). Ein Weg, um die Arbeitsweise der bevorzugten Ausführungsbeispiele zu verbessern, ist, die bevorzugten Verfahren für die verschiedenen Auswahlmöglichkeiten mit verschiedenen Startzeitpunkten zu wiederholen und eine Vielzahl von Sätzen von Zeitschlitzzuordnungen zu erzeugen und daraus die Zuordnung auszuwählen, die die geringste Zellenverzögerungsschwankung aufweist. Insbesondere kann die Suche auf solche freien Zeitschlitze begrenzt werden, die innerhalb von roundup(β_new * FL) von F[0] liegen. Die Entscheidung, ob eine solche Abwandlung eingesetzt wird, hängt von den Real- Time-Processing- Beschränkungen bei der Rufverarbeitung und der Verbindungszugangskontrolle ab.
ANHANG "A"

Claims

Verfahren zum Zuordnen von Zeitschlitzen in einem TDMA – Rahmen zu einer Verkehrsquelle, wobei besagter Rahmen eine Zeitdauer FD hat und insgesamt FL Zeitschlitze aufweist und wobei besagtes Verfahren durch folgende Schritte gekennzeichnet ist: (a) Festlegen einer Anzahl N_new von besagten Zeitschlitzen, die benötigt werden, um die Bandbreitenanforderungen der besagten Verkehrsquelle zu erfüllen; (b) Aufstellen einer Liste A[i]: i∊ {0, 1, ..., N_new – 1} von bevorzugten Zeitschlitzpositionen; (c) Auswahl einer Liste C[i]: i∊ {0, 1, ..., N_new – 1} von Zeitschlitzen aus einer vorbestimmten, sortierten Liste B von Zeitschlitzen für besagte Verkehrsquelle, die die besagten bevorzugten Zeitschlitzpositionen annähern oder erfüllen, wobei C[i] ∀i als ein Zeitschlitz aus B ausgewählt wird, der das über alles betrachtete Burstverhältnis der besagten Verkehrsquelle nicht erhöht, und falls ein solcher Zeitschlitz nicht existiert, ein Zeitschlitz aus B ausgewählt wird, der das über alles betrachtete Burstverhältnis der besagten Verkehrsquelle am geringsten erhöht; und (d) Entfernen der Einträge C aus B.
Verfahren nach Anspruch 1, weiter gekennzeichnet dadurch, dass besagte Verkehrsquelle keine ihr früher zugeteilten Zeitschlitze hat; A eine Liste von idealen Zeitschlitzpositionen für die besagte Verkehrsquelle ist, die voneinander beabstandet sind mit einer Zeit, die im wesentlichen gleich einem Spitzenübertragungsintervall zwischen Datenpaketen von besagter Verkehrsquelle ist; und B eine sortierte Liste von freien Zeitschlitzen im Rahmen ist.
Verfahren nach Anspruch 1, weiter gekennzeichnet dadurch, dass besagte Verkehrsquelle M ihr früher zugeteilte Zeitschlitze hat; wobei N_new < M ist; A eine Liste von idealen Zeitschlitzpositionen für die besagte Verkehrsquelle ist, die voneinander beabstandet sind mit einer Zeit, die im wesentlichen gleich einem Spitzenübertragungsintervall zwischen Datenpaketen von besagter Verkehrsquelle ist; und B eine Liste der der Verkehrsquelle früher zugeteilten M Zeitschlitze ist.
Verfahren nach Anspruch 1, weiter gekennzeichnet dadurch, dass besagte Verkehrsquelle M ihr früher zugeteilte Zeitschlitze hat; wobei N_new > M ist und das Verfahren weiter umfasst: (a) Ausführen der Schritte 1(c)–1(d) ein erstes Mal, wobei A gleich einer Liste P der der Verkehrsquelle früher zugeteilten M Zeitschlitze gesetzt wird und B gleich einer Liste I von idealen Zeitschlitzpositionen für die besagte Verkehrsquelle ist, die voneinander beabstandet sind mit einer Zeit, die im wesentlichen gleich einem Spitzenübertragungsintervall zwischen Datenpaketen von besagter Verkehrsquelle ist, um von 1 diejenigen idealen Zeitschlitzpositionen zu entfernen, die am nächsten bei den Zeitschlitzpositionen aus A liegen und eine Liste I' zu erzeugen; (b) Ausführen der Schritte 1(c)–1(d) ein zweites Mal, wobei A gleich I' gesetzt wird und B eine Liste der freien Zeitschlitzpositionen F ist; und (c) Zuteilen der Zeitschlitze entsprechend Liste C an die Verkehrsquelle, wie im Schritt 4(b) ermittelt und Zuteilung von P.
Verfahren nach Anspruch 4, weiter gekennzeichnet dadurch, dass C[i] ∀i im Schritt 1(c) so gewählt wird, dass es entweder (a) der nächste Zeitschlitz in B ist, der 1[i] vorausgeht oder gleich ist oder (b) der nächste Zeitschlitz in B ist, der 1[i] nachfolgt, mit der Einschränkung, dass C[i] ausschließlich ∀i ist.
Datenkommunikationseinrichtung, die ein Eingangsmittel zum Empfangen von Datenpaketen von einer Verkehrsquelle und zum Einreihen dieser besagten Pakete in eine Warteschlange für einen Speicher aufweist, wobei die besagte Kommunikationseinrichtung dadurch gekennzeichnet ist, dass sie: Mittel zur Festlegung eines Zeitrahmens mit einer Zeitdauer FD und einer Gesamtzahl von FL Zeitschlitzen aufweist, um eine sortierte Liste von darin enthaltenen freien Zeitschlitzen aufrechtzuerhalten; Mittel zur Festlegung einer Anzahl N_new von Zeitschlitzen aufweist, die benötigt werden, um die Bandbreitenanforderungen der besagten Verkehrsquelle zu erfüllen; Mittel zur Ermittlung eines Satzes {I[0], I[1], I[2] ...I[N_new – 1]} von idealen Zeitschlitzpositionen zur Erfüllung der Bandbreitenanforderungen der besagten Verkehrsquelle, die voneinander beabstandet sind mit einer Zeit, die im wesentlichen gleich einem Spitzenübertragungsintervall zwischen besagten Datenpaketen ist; Mittel zur Zuteilung eines Satzes {VC[0], VC[1], VC[2] ... VC[N_new – 1]} von besagten freien Zeitschlitzen an die besagte Verkehrsquelle, die die besagten idealen Zeitschlitzpositionen annähern oder erfüllen, wobei ein gegebener VC[i]: i∊ {0, 1, ..., N_new – 1} als einer der freien Zeitschlitze ausgewählt wird, der das über alles betrachtete Burstverhältnis der besagten Verkehrsquelle nicht erhöht und falls ein solcher freier Zeitschlitz nicht existiert, ein Zeitschlitz als einer der freien Zeitschlitze ausgewählt wird, der das über alles betrachtete Burstverhältnis der besagten Verkehrsquelle am geringsten erhöht; und Ausgangsmittel zum Auslesen der aufgereihten Datenpakete von besagter Verkehrsquelle aus dem besagten Speicher und zum Übertragen der besagten ausgelesenen Datenpakete nur zu den entsprechenden Zeitabschnitten, die den besagten zugeteilten Zeitschlitzen entsprechen.
Einrichtung nach Anspruch 6, weiter gekennzeichnet dadurch, dass das besagte Burstverhältnis der besagten Verbindung definiert ist als eine Menge (ME + ML)*FD/FL, wobei ME eine Maximalzeit ist, um die irgendein zugeteilter Zeitschlitz VC [j] früher auftritt als der entsprechende ideale Zeitschlitz I[j], j ∊ {0, 1, 2 ..., N_new – 1} und ML eine Maximalzeit ist, um die irgendein zugeteilter Zeitschlitz VC [k] später auftritt als der entsprechende ideale Zeitschlitz I[k], k ∊ {0,1,2 ...,N_new – 1}.
Einrichtung nach Anspruch 6, weiter gekennzeichnet dadurch, dass sie Mittel zur Berechnung einer Menge (ME + ML) * FD/FL aufweist, wobei ME eine Maximalzeit ist, um die irgendein zugeteilter Zeitschlitz VC [j] früher auftritt als der entsprechende ideale Zeitschlitz I[j], j ∊ {0, 1, 2 ..., N_new – 1} und ML eine Maximalzeit ist, um die irgendein zugeteilter Zeitschlitz VC [k] später auftritt als der entsprechende ideale Zeitschlitz I[k], k ∊ {0, 1, 2 ..., N_new – 1} und wobei die besagte Menge (ME + ML) * FD/FL eine obere Grenze einer Paketverzögerungszeitvariation für die besagte Verkehrsquelle darstellt.
Verfahren zur Bestimmung, ob ein Paket – Datenstrom mit konstanter Bitrate, dem ein Satz von N Zeitschlitzen in einem FL, FL ≥ N, Zeitschlitzzuordnungsrahmen zugeteilt wurde, mit einem typischen Zellenratenalgorithmus (GCRA) übereinstimmt mit einem Spitzen – Paketsendeintervall T und einer Paketverzögerungszeitvariation CDVT, wobei das besagte Verfahren dadurch gekennzeichnet ist durch folgende Schritte: (a) Auswahl eines Satzes von idealen Zeitschlitzpositionen für besagten Paket – Datenstrom, wobei die idealen Zeitschlitzpositionen voneinander beabstandet sind mit einer Zeit, die im Wesentlichen gleich T ist; (b) Bestimmung einer Maximalzeitdauer ME, um die irgendein zugeteilter Zeitschlitz früher auftritt als die entsprechende ideale Zeitschlitzposition; (c) Bestimmung einer Maximalzeitdauer ML, um die irgendein zugeteilter Zeitschlitz später auftritt als die entsprechende ideale Zeitschlitzposition; und (d) Vergleich der Werte ME + ML gegen besagte CDVT und als Reaktion darauf Entscheidung, ob der besagte Paket – Datenstrom mit der besagten GCRA übereinstimmt.
Verfahren nach Anspruch 9, weiter gekennzeichnet dadurch, dass besagte Zeitschlitze feste identische Zeitdauern aufweisen und dass die besagten Pakete eine feste Länge haben.