-
Datenkommunikationswitches
empfangen Pakete auf einer Mehrzahl von Eingängen und übermitteln sie an eine Mehrzahl
von Ausgängen.
Manchmal treffen Pakete an zwei oder mehr Eingängen ein, die für den gleichen
Ausgang bestimmt sind. Um Kollisionen zwischen solchen Paketen zu
minimieren, wird die Bildung von Warteschlangen verwendet. Warteschlangen
zwischenspeichern einige Pakete, während andere die Bandbreite
verbrauchen, die zum Zustellen der Warteschlangenpakete an einen
Ausgang notwendig ist.
-
Die
Freigabe von Paketen aus Warteschlangen, die um Ausgangsbandbreite
konkurrieren, wird in der Regel durch einen Scheduler koordiniert.
Viele Scheduler folgen einer strengen Regel der Prioritätsverarbeitung,
d.h. den Warteschlangen werden verschiedene Prioritätsebenen
zugewiesen und den Schedulern, die mit relativ hohen Prioritätsebenen
verknüpft
sind, wird erlaubt, Pakete vor denjenigen freizugeben, die mit relativ
niedrigen Prioritätsebenen
verknüpft
sind. Strenge Prioritätsverarbeitung
ermöglicht
Flüssen,
die als relativ zeitkritisch bezeichnet worden sind, den Vorrang
vor denjenigen zu haben, die als relativ weniger zeitkritisch bezeichnet
worden sind.
-
Ungeachtet
ihrer allgemeinen Wirksamkeit ist die Prioritätsverarbeitung nicht frei von
Problemen. Ein unerwünschter
Effekt ist Prioritätsblockierung.
Prioritätsblockierung
tritt auf, wenn die Zustellung von Paketen von Warteschlangen relativ
niedriger Priorität
unter einer kontinuierlichen Verzögerung aufgrund der Bedienung
von Warteschlangen höherer
Priorität
leidet. Prioritätsblockierung
kann schließlich
bewirken, daß Pakete in
den blockierten Warteschlangen überschrieben
werden, während
die Freigabe erwartet wird, ein Zustand, der als Dropping bekannt
ist.
-
Dropping
unterbricht unerwünscht
die Flüsse,
auf die sich die verlorenen Pakete beziehen.
-
Während von
der Prioritätsverarbeitung
absichtlich erwartet wird, daß sie
einige Warteschlangen schneller bedient als andere, kann die Abweichung
von einer strengen Regel der Priorisierung in bestimmten Fällen gerechtfertigt
sein. Zum Beispiel kann die Prioritätsblockierung durch "Stopfen" einer einzelnen
Warteschlange auf der Prioritätsebene
verursacht sein, die einen Dienst mit nichtkritischem oder sogar
redundantem (z.B. im Fall eines nicht aufgelösten Spanning-Tree-Loop) Verkehr
empfängt.
Die strenge Einhaltung der Prioritätsverarbeitung würde diesem "Stopfen" erlauben, letztendlich
die gesamte Ausgangsbandbreitenbelegung auf Kosten der Warteschlangen
relativ niedriger Priorität
zu halten.
-
Die
US-Patentschrift 5,959,993 offenbart
einen Zellenscheduler für
eine verteilte Gemeinschaftsspeicher-Switcharchitektur, einschließlich eines
Controllers zum Scheduling der Übertragung
von Zellen von Ausgangswarteschlangen der Switchstruktur gemäß einem
von mehreren verschiedenen Schedulingmodi. Die innerhalb des Schedulers
angewendeten Schedulingreihenfolgen umfassen eine Schedulingreihenfolge
für Weighted-Fair-Queuing
(WFQ) und eine Schedulingreihenfolge für Round-Robin (RR).
-
Das
Dokument XP-002245023 offenbart den Leaky-Bucket-Algorithmus und den Token-Bucket-Algorithmus.
-
WO 99/46903 offenbart einen
eingangsgepufferten Multipoint-Switch
mit Eingangskanälen
und Ausgangskanälen,
die Mehrebenen-Anforderungspuffer, einen Datenwegmultiplexer und
einen Scheduler einschließen.
Der Switch weist einen eigenen Mehrebenen-Anforderungspufferspeicher
auf, der mit jedem Eingangskanal verbunden ist, und jeder Anforderungspufferspeicher
weist Mehrfachanforderungsregister zum Speichern der Datenzellen-Übertragungsanforderungen
verschiedener Prioritäten
auf. Die Mehrebenen-Anforderungsregister
sind parallel mit dem Scheduler verbunden, um Arbitrierung zwischen
Anforderungen von verschiedenen Eingangskanälen und verschiedenen Prioritätsebenen
zu ermöglichen.
Eine Mehrzahl von ebenenspezifischen Subschedulingeinheiten wird
bereitgestellt, um Anforderungen zu verarbeiten, die verschiedene
Prioritätsebenen
aufweisen.
-
Entsprechend
wird ein gekennzeichnetes Prioritätsverarbeitungsverfahren zum
Verringern der Prioritätsblockierung
durch Auferlegung angemessener Einschränkungen auf eine allgemeine
Priorisierungsrichtlinie benötigt.
Außerdem
wird effiziente Scheduling-Hardware benötigt, um die gekennzeichnete
Prioritätsverarbeitung
auszuführen.
-
KURZDARSTELLUNG DER ERFINDUNG
-
Die
vorliegende Erfindung stellt ein gekennzeichnetes Prioritätsverarbeitungsverfahren
und -einrichtung für
eine Datenwarteschlangenstruktur bereit, einschließlich einer
Mehrzahl von Gruppen von Warteschlangen, die um die Bandbreite eines
Ausgangs konkurrieren. Jede Gruppe hat mindestens eine Warteschlange
und ist mit einer verschiedenen Prioritätsebene verbunden. Außerdem ist
mindestens eine Warteschlange innerhalb mindestens einer Gruppe
eine eingeschränkte
Bandbreitenwarteschlange, d.h. hat einen Bandbreitenvertrag, der
nicht überschritten
werden kann.
-
Gemäß dem Warteschlangenverarbeitungsverfahren
wird eine Warteschlange innerhalb der Gruppe, die mit der aktuellen Prioritätsebene
verbunden ist, die (i) Daten zur Freigabe an den Ausgang aufweist,
(ii) verfügbare
Bandbreite aufweist, d.h. ihren Bandbreitenvertrag (falls vorhanden)
nicht verletzt hat, ausgewählt, um
Daten an den Ausgang freizugeben. Wenn eine Mehrzahl solcher Warteschlangen
vorhanden ist, bestimmt die Round-Robin-Reihenfolge, welche Warteschlange
in der Mehrzahl ausgewählt
wird. Die aktuelle Prioritätsebene
wird ursprünglich
auf der höchsten
Prioritätsebene
eingestellt und wird vermindert, bis eine Warteschlange ausgewählt wird
oder alle Prioritätsebenen
geprüft
worden sind, je nachdem was zuerst eintritt. Warteschlangen können eingeschränkte oder
uneingeschränkte
Bandbreite aufweisen. Warteschlangen mit uneingeschränkter Bandbreite
haben immer verfügbare
Bandbreite, wohingegen eingeschränkte
Warteschlangen verfügbare
Bandbreite nur aufweisen, wenn sie Kredit haben. Kredit wird eingeschränkten Warteschlangen
periodisch zugeteilt und gemäß der Länge der
freigegebenen Daten verringert. Daten werden in Quanten des Kredits
freigegeben.
-
Gemäß der Warteschlangen-Schedulingeinrichtung
ist ein Selektor zum Auswählen
einer Warteschlange aus der Mehrzahl der Warteschlangen als eine
Funktion einer Mehrzahl von Warteschlangenzustandsvariablen und
zum Übermitteln
der Warteschlangenauswahlinformationen angeordnet. Der Selektor umfaßt vorzugsweise
eine Mehrzahl von Bitmasken, die den Zustand bezüglich einer Warteschlangenzustandsvariable
der verschiedenen Warteschlangen darstellen, deren Masken in einer
bitweisen UND-Operation kombiniert werden, um zu ermitteln, welche
Warteschlangen zur Freigabe der Daten an den Ausgang auswählbar sind.
Der Selektor umfaßt
vorzugsweise außerdem
einen Arbiter zum Empfangen des Ergebnisses der Bestimmung, zum
Round-Robin-Auswählen
einer einzelnen Warteschlange aus den auswählbaren Warteschlangen und
zum Übermitteln
des Ergebnisses der Round-Robin-Auswahl an einen Treiber zur Freigabe aus
der ausgewählten
Warteschlange.
-
Diese
und andere Aspekte der vorliegenden Erfindung können durch Verweis auf die
folgende detaillierte Beschreibung, zusammen genommen mit den beigefügten Zeichnungen,
die unten kurz beschrieben sind, besser verstanden werden.
-
KURZBESCHREIBUNG DER ZEICHNUNGEN
-
1 ist
eine Darstellung der Richtlinienebenen einer beispielhaften Gemeinschaftsausgangs-Warteschlangenstruktur
mit Scheduling-Charakteristika;
-
2 ist
ein Blockdiagramm einer bevorzugten Schedulingeinrichtung für eine Gemeinschaftsausgangs-Warteschlangenstruktur
und eine zugeordnete Warteschlangenstruktur;
-
3 ist
ein Blockdiagramm des Mehrstufenselektors von 2;
-
4 ist
ein Blockdiagramm des Round-Robin-Arbiters von 2;
-
5 ist
ein Blockdiagramm der Statistik von 2;
-
6 ist
ein Flußdiagramm
der Schritte der Prioritätsbandbreiten-Warteschlangenauswahl;
-
7 ist
ein Flußdiagramm
der Schritte zur Auswahl der kennzeichnenden Warteschlange der Round-Robin-Arbitrierung;
und
-
8 ist
ein Flußdiagramm
der Schritte zur Auswahl der gewinnenden Warteschlange der Round-Robin-Arbitrierung.
-
DETAILLIERTE BESCHREIBUNG
DER BEVORZUGTEN AUSFÜHRUNGSFORM
-
Die
vorliegende Erfindung ist in erster Linie auf ein Verfahren und
eine Einrichtung zum Scheduling der Freigabe von Daten aus einer
Mehrzahl von Warteschlangen gerichtet, die um die Bandbreite eines
Ausgangs konkurrieren. In 1 ist eine
beispielhafte Gemeinschaftsausgangs-Warteschlangenstruktur mit Scheduling-Charakteristika
auf einer Richtlinienebene gezeigt. In der beispielhaften Struktur
sind fünf
Warteschlangen 10, 20, 30, 40, 50 vorhanden,
die um die Bandbreite des Ausgangs 60 konkurrieren. Die
Freigabe von Daten aus den Warteschlangen 10, 20, 30, 40, 50 ist
zeitlich festgelegt, d.h. zeitmultiplex, um Konkurrenz zu vermeiden.
Die Warteschlangen 10, 20, 30, 40, 50 sind
durch die Prioritätsebene
gekennzeichnet, einschließlich
Warteschlange 10 hoher Priorität, Warteschlangen 20, 30 mittlerer
Priorität
und Warteschlangen 40, 50 niedriger Priorität zur Freigabe
von Daten an Ausgang 60. Die Warteschlangen 10, 20, 30, 40, 50 sind
außerdem
durch den Bandbreitentyp zur Freigabe von Daten an Ausgang 60 gekennzeichnet.
Die alleinige Warteschlange 10 hoher Priorität ist eine
uneingeschränkte
Bandbreitenwarteschlange. Beide Warteschlangen 20, 30 mittlerer Priorität sind eingeschränkte Bandbreitenwarteschlangen.
Nur die Warteschlange 40 niedriger Priorität ist eine uneingeschränkte Bandbreitenwarteschlange,
wohingegen die andere Warteschlange 50 niedriger Priorität eine eingeschränkte Bandbreitenwarteschlange
ist. Die Warteschlangen 10, 20, 30, 40, 50 sind
außerdem durch
den Flußtyp
gekennzeichnet, d.h. unicast oder Flut. Jedoch hat der Flußtyp keinen
Einfluß auf
die Reihenfolge, in welcher Daten an Ausgang 60 freigegeben
werden. Natürlich
ist die in 1 dargestellte Gemeinschaftsausgangs-Warteschlangenstruktur
nur ein Beispiel solcher Struktur; Anzahl, Prioritätsebene
und Bandbreitentyp der Warteschlangen werden sich in anderen Gemeinschaftsausgangs-Warteschlangenstrukturen unterscheiden, die
gemäß der vorliegenden
Erfindung von den Richtlinien abhängig sind, die implementiert werden
sollen.
-
In
einem bevorzugten Schedulingverfahren für eine Gemeinschaftsausgangs-Warteschlangenstruktur wird
eine Warteschlange innerhalb der Gruppe, die mit der aktuellen Prioritätsebene
verbunden ist, die Daten zur Freigabe an den Ausgang aufweist und
verfügbare
Bandbreite aufweist, d.h. ihren Bandbreitenvertrag nicht verletzt
hat, falls vorhanden, ausgewählt,
um Daten an den Ausgang freizugeben. Wenn eine Mehrzahl solcher Warteschlangen
vorhanden ist, entscheidet die Round-Robin-Reihenfolge, welche Warteschlange
in der Mehrzahl ausgewählt
wird. Verschiedene Weiterentwicklungen dieses grundlegenden Schedulingverfahrens
sind möglich,
wie im folgenden beschrieben ist. Nichtsdestoweniger wird auf einem
Grundniveau angenommen, daß dieses
grundlegende Verfahren, ungeachtet seiner scheinbaren Einfachheit,
einen wichtigen Fortschritt gegenüber den Schedulingverfahren
des Standes der Technik bietet.
-
Durch
Anwenden des bevorzugten Schedulingverfahrens auf die beispielhafte
Gemeinschaftsausgangs-Warteschlangenstruktur, die in 1 dargestellt
ist, wenn die Warteschlange 10 uneingeschränkter Bandbreite
hoher Priorität
Daten zur Freigabe an Ausgang 60 hat, wird die Warteschlange 10 ausgewählt. Wenn
Warteschlange 10 nicht ausgewählt wird, werden die Warteschlangen 20, 30 beschränkter Bandbreite mittlerer
Priorität
geprüft.
Speziell wenn jede Warteschlange 20, 30 Daten
zur Freigabe an Ausgang 60 aufweist und jede verfügbare Bandbreite
aufweist, wird die nächste
anstehende der Warteschlangen 20, 30 in Round-Robin-Reihenfolge
ausgewählt.
Wenn jede Warteschlange 20, 30 Daten zur Freigabe
aufweist, aber nur eine der Warteschlangen 20, 30 verfügbare Bandbreite
aufweist, wird diese von den Warteschlangen 20, 30 mit
verfügbarer
Bandbreite ausgewählt.
Wenn nur eine der Warteschlangen 20, 30 Daten
zur Freigabe und verfügbare
Bandbreite aufweist, wird diese von den Warteschlangen 20, 30 ausgewählt. Wenn
keine der Warteschlangen 20, 30 ausgewählt wird,
werden die Warteschlangen 40, 50 niedriger Priorität geprüft. Speziell wenn
jede Warteschlange 40, 50 Daten zur Freigabe an
Ausgang 60 aufweist und die Warteschlange 50 beschränkter Bandbreite
niedriger Priorität
verfügbare
Bandbreite aufweist, wird die nächste
anstehende der Warteschlangen 40, 50 in Round-Robin-Reihenfolge
ausgewählt.
Wenn jede Warteschlange 40, 50 Daten zur Freigabe
aufweist, aber die Warteschlange 50 eingeschränkter Bandbreite
niedriger Priorität
keine verfügbare Bandbreite
aufweist, wird die Warteschlange 40 uneingeschränkter Bandbreite
niedriger Priorität
ausgewählt. Wenn
nur Warteschlange 40 Daten zur Freigabe aufweist, wird
die Warteschlange 40 ausgewählt. Wenn nur Warteschlange 50 Daten
zur Freigabe aufweist, wird Warteschlange 50 ausgewählt, wenn
Warteschlange 50 verfügbare
Bandbreite aufweist. Wenn keine der Warteschlangen 40, 50 ausgewählt wird,
werden keine Daten an Ausgang 60 freigegeben.
-
Mit
Verweis nun auf 2 wird eine bevorzugte Gemeinschaftsausgangs-Schedulingeinrichtung
auf einer Komponentenebene zusammen mit einer zugeordneten Warteschlangenstruktur
gezeigt. Die Warteschlangenstruktur 210 umfaßt Datenwarteschlangen
0 bis N zum Empfangen von Daten auf entsprechenden Eingängen 0 bis
N 212 und zur Freigabe von Daten an Ausgang 214.
Die Freigabe von Daten von Warteschlangenstruktur 210 wird
durch Scheduler 200 gesteuert. Der Scheduler 200 umfaßt Manager 220,
Mehrstufenselektor 230, Treiber 240 und Statistik 250.
Der Manager 220 ruft Daten von Statistik 250 ab
und aktualisiert Selektor 230 und Statistik 250.
Der Selektor 230 umfaßt
Auswahlmasken 232, Prioritäts-Bandbreiten-Selektor 234 und
Round-Robin-Arbiter 236 zum Erleichtern der Warteschlangenauswahl.
Der Selektor 230 wählt
die Datenwarteschlangen zur Freigabe von Daten an Ausgang 214 aus
und übermittelt
die Warteschlangenauswahlinformationen an Treiber 240.
Der Treiber 240 empfängt
Warteschlangenauswahlinformationen, ruft Daten von Statistik 250 ab,
aktualisiert Statistik 250 und steuert die Freigabe von
Daten aus den ausgewählten Warteschlangen.
-
Mit
Verweis nun auf 3 ist der Selektor 230 detaillierter
dargestellt. Selektor 230 weist Auswahlmasken 232 auf,
die Freigabemaske 312, Backlogmaske 314, Bandbreitenmaske 316 und
Prioritätsmasken 318 umfassen.
Jede Maske verwaltet ein Statusbit für jede Warteschlange 0 bis
N im Speicherelement 210. Die Freigabemaske 312 zeigt
an, welche unter den Warteschlangen 0 bis N zum Übermitteln von Daten an Ausgang 214 freigegeben
werden. Eine "1" in der für die Warteschlange
reservierten Bitstelle stellt Freigabe dar, wohingegen eine "0" die Nicht-Freigabe darstellt. Die Backlogmaske 314 zeigt
an, welche unter den Warteschlangen 0 bis N Daten aufweist, die
an Ausgang 214 übermittelt
werden sollen. Eine "1" in der für die Warteschlange
reservierten Bitstelle stellt die Anwesenheit von anstehenden Daten
dar, wohingegen eine "0" die Abwesenheit
von anstehenden Daten darstellt. Die Bandbreitenmaske 316 zeigt
an, welche unter den Warteschlangen 0 bis N Bandbreite zum Übermitteln
von Daten an Ausgang 214 hat. Eine "1" stellt
die Verfügbarkeit von
Bandbreite dar, wohingegen eine "0" die Nichtverfügbarkeit
von Bandbreite darstellt. Die Prioritätsmasken 318 zeigen
zusammen die Prioritätsebene
der Warteschlangen 0 bis N an. Eine separate Prioritätsmaske
wird für
jede Prioritätsebene
verwaltet. Eine "1" in der für die Warteschlange
reservierten Bitstelle in einer Prioritätsmaske zeigt die Zuweisung
der Warteschlange zu der Prioritätsebene
an, welche die Maske darstellt, wohingegen eine "0" die
Nicht-Zuweisung zu der Prioritätsebene
anzeigt. Die Masken 232 sind durch den Manager 220 konfigurierbar.
Die Backlogmaske 314 und die Bandbreitenmaske 316 werden
durch den Manager 220 als Antwort auf Informationen aktualisiert,
die von Statistik 250 abgerufen wurden.
-
Die
Auswahlmasken 232 sind an den Prioritäts-Bandbreiten-Selektor 234 gekoppelt.
Der Selektor 234 erleichtert die Warteschlangenauswahl
durch Reduzieren der Auswahl auf eine Round-Robin-Auswahl unter den
beteiligten Warteschlangen. Wenn die Teilnehmerauswahl aktiviert
ist, werden die Freigabemaske 312, Backlogmaske 314,
Bandbreitenmaske 316 und eine der Prioritätsmasken 318 auf
einmal dem Maskenvergleich 324 für eine bitweise UND-Operation
vorgelegt. Die eine der Prioritätsmasken 318,
die der bitweisen UND-Operation vorgelegt wurde, wird durch den
Prioritätszähler 328 ermittelt,
der den Multiplexer 322 anweist, eine der Prioritätsmasken 318 auf
der Basis des aktuellen Wertes des Zählers 328 freizugeben.
Für jede
Teilnehmerauswahlrunde wählt
der Zähler 328 zuerst
die Maske höchster
Priorität
aus und wählt
die Prioritätsmasken
von inkremental niedrigerer Priorität aus, bis die Gewinnerauswahlfreigabe
auf der aktuellen Prioritätsebene
angezeigt wird oder alle Prioritätsmasken
vorgelegt worden sind.
-
Das
Ergebnis der bitweisen UND-Operation, die durch Maskenvergleich 324 durchgeführt wurde,
ist eine Maske, die anzeigt, welche Warteschlangen auf der aktuellen
Prioritätsebene,
falls vorhanden, berechtigt sind, an der im Round-Robin-Arbiter 236 durchgeführten Gewinnerauswahl
teilzunehmen. Insbesondere weist die resultierende Maske eine "1" an allen Bitstellen auf, die für Warteschlangen
reserviert sind, die für
Ausgangsanschluß 214 freigegeben
sind, anstehende Daten haben, verfügbare Bandbreite aufweisen
und auf der aktuellen Prioritätsebene
sind, falls vorhanden, und weist eine "0" an
den anderen Bitstellen auf. Folglich zeigt die resultierende Maske
jede teilnehmende Warteschlangen durch eine "1" und
jede nichtteilnehmende Warteschlangen durch eine "0" an. Die resultierende Maske wird der Gewinnerauswahlfreigabe 326 für eine ODER-Operation
vorgelegt. Wenn mindestens eine Bitstelle in der resultierenden
Maske eine "1" aufweist, ergibt
die ODER-Operation eine "1" und die Gewinnerauswahl
wird auf der aktuellen Prioritätsebene
freigegeben. Andernfalls hat die ODER-Operation eine "0" zur Folge, die Gewinnerauswahl wird
auf der aktuellen Prioritätsebene
nicht freigegeben und die bitweise UND-Operation wird auf der nächsten Prioritätsebene,
falls vorhanden, durchgeführt.
Das Ergebnis der ODER-Operation wird als Rückkopplung an Zähler 328 geliefert, um
Zähler 328 zu
benachrichtigen, ob eine zusätzliche
Prioritätsmaskenauswahl
erforderlich ist. Man wird erkennen, daß, wenn sich eine "Null"-Maske aus der bitweisen
UND-Operation auf allen Prioritätsebenen
ergibt, die Gewinnerauswahl nicht freigegeben wird und die Round-Robin-Arbitrierung
nicht durchgeführt
wird.
-
Der
Prioritäts-Bandbreiten-Selektor 234 ist
mit dem Round-Robin-Arbiter 236 gekoppelt.
Der Round-Robin-Arbiter 236 entscheidet über eine
gewinnende Warteschlange, indem eine Round-Robin-Auswahl unter teilnehmenden
Warteschlangen durchgeführt
wird, wie durch Selektor 234 ermittelt wurde. Übergehend
zu 4 ist der Round-Robin-Arbiter 236 detaillierter
gezeigt. Wenn die Gewinnerauswahl freigegeben ist, wird die teilnehmende
Warteschlangenmaske, d.h. die Maske, die sich aus der im Selektor 234 durchgeführten bitweisen
UND-Operation ergibt, der Vorauswahlmatrix 410 für kennzeichnende
Warteschlangenbestimmungen vorgelegt. Insbesondere empfängt jedes
Vorauswahlelement in der Matrix 410 eine Teilmenge von
Bits von der teilnehmenden Warteschlangenmaske und wählt eine
einzelne kennzeichnende Warteschlange unter den teilnehmenden Warteschlangen
aus, falls vorhanden, die es darstellt. Speziell wählt das
Vorauswahlelement, dessen kennzeichnende Warteschlange als die gewinnende
Warteschlange durch die Endauswahl 420 in der letzen Round-Robin-Arbitrierung
ausgewählt
wurde, als eine kennzeichnende Warteschlange die nächste von
ihren teilnehmenden Warteschlangen in der Round-Robin-Reihenfolge
aus, falls vorhanden. Die anderen Vorauswahlelemente wählen als
eine kennzeichnende Warteschlange die erste von ihren entsprechenden
teilnehmenden Warteschlangen aus, falls vorhanden. Die kennzeichnenden
Warteschlangenauswahlen werden der Endauswahl 420 zusammen
mit jeder Mitteilung "kein
Kennzeichner" von
jedem Vorauswahlelement vorgelegt, die keine teilnehmenden Warteschlangen
darstellen. Außerdem,
wenn das Vorauswahlelement, dessen kennzeichnende Warteschlange
als die letzte gewinnende Warteschlange, die zyklisch umlaufen wurde,
d.h. von seiner letzten zur ersten Warteschlange in der Round-Robin-Reihenfolge
im Verlaufe des Treffens der Auswahl zurückgegeben wurde, sendet das
Vorauswahlelement eine Mitteilung des "zyklischen Umlaufs" an die Endauswahl 420. Die
Endauswahl 420 wählt
als eine gewinnende Warteschlange die kennzeichnende Warteschlange
von dem Vorauswahlelement aus, dessen kennzeichnende Warteschlange als
die letzte gewinnende Warteschlange ausgewählt wurde, es sei denn, daß das Vorauswahlelement
eine Mitteilung "kein
Kennzeichner" oder "zyklischer Umlauf" sendete. Wenn dieses
Vorelement eine Mitteilung "kein
Kennzeichner" oder "zyklischer Umlauf" sendete, wählt die
Endauswahl 420 als die gewinnende Warteschlange die kennzeichnende
Warteschlange von dem nächsten
der Vorauswahlelemente in Round-Robin-Reihenfolge aus, falls vorhanden.
Die Endauswahl 420 übermittelt
den Identifizierer der gewinnenden Warteschlange an den Warteschlangentreiber 240 zum
Abschluß der
Round-Robin-Arbitrierung.
Der Identifizierer der gewinnenden Warteschlange wird ebenfalls
als Rückkopplung
an Matrix 410 zur Verwendung durch Vorauswahlelemente in
anschließenden
kennzeichnenden Warteschlangenauswahlen geliefert.
-
Mit
Verweis nun auf 2 zusammen mit 5 als
Antwort auf den vom Selektor 230 empfangenen Identifizierer
der gewinnenden Warteschlange konsultiert der Treiber 240 die
Statistik 250, um Warteschlangenzustandsinformationen abzufragen
und steuert die Freigabe der Daten aus der gewinnenden Warteschlange
an Ausgang 214. Die Statistik 250 verwaltet Mehrfeldeinträge für jede Warteschlange
0 bis N innerhalb der Warteschlangenstruktur 210, die einen
Warteschlangenidentifizierer, einen Beginnzeiger, einen Endezeiger, Werte
für aktuelle
Tiefe, maximale Tiefe, aktuellen Kredit und Gesamtkredit umfaßt. Der
Identifizierer der gewinnenden Warteschlange wird verwendet, um
den entsprechenden Eintrag in Statistik 250 "nachzuschlagen". Ein vorgegebener
Teil des Kredits wird zum aktuellen Kreditwert für den entsprechenden Eintrag
addiert. Ein Teil kann vorteilhaft bezüglich der maximalen Länge eines
Pakets ausgewählt
werden, das gemäß einem
speziellen Protokoll formatiert ist, wie zum Beispiel 1518 Byte
für ein
Ethernet-Paket.
Der Treiber 240 steuert die Freigabe der Daten aus der
gewinnenden Warteschlange an Ausgang 214, beginnend mit
den Daten am Warteschlangenort, der durch den Beginnzeiger in dem
entsprechenden Eintrag angegeben ist, bis alle Daten aus der gewinnenden
Warteschlange freigegeben worden sind, der aktuelle Kredit verbraucht
worden ist oder, im Falle einer eingeschränkten Bandbreitenwarteschlange,
oder der Gesamtkredit verbraucht worden ist, je nachdem, was zuerst
eintritt. Der Treiber 240 aktualisiert den Beginnzeiger,
die aktuelle Tiefe, den Gesamtkreditwert und die aktuellen Kreditwerte
für den
entsprechenden Eintrag, wenn Daten freigegeben werden, um den sich ändernden
Warteschlangenzustand widerzuspiegeln. Der aktuelle Kreditwert wird "genullt", wenn alle Daten
freigegeben worden sind oder, im Falle einer eingeschränkten Bandbreitenwarteschlange,
der Gesamtkredit vor dem aktuellen Kredit verbraucht ist.
-
Der
Manager 220 konsultiert die Statistik 250, um
sicherzustellen, daß die
Auswahlmasken 232 die durch den Treiber 240 vorgenommenen Änderungen
des Warteschlangenzustands widerspiegeln. Die aktuellen Tiefenwerte
in Einträgen
werden konsultiert, um die Backlogmaske 312 aufzufrischen
und die Gesamtkreditwerte in Einträgen werden konsultiert, um
die Bandbreitenmaske 316 aufzufrischen. Der Manager 220 frischt
ebenfalls periodisch die Gesamtkreditwerte in den für eingeschränkte Bandbreitenwarteschlangen
verwalteten Einträgen
auf.
-
Zurückgehend
nun zu 6 ist ein Flußdiagramm
der Prioritätsbandbreiten-Warteschlangenauswahl gezeigt.
Die Teilnehmerauswahl ist freigegeben (610) und die höchste Priorität ist als
die aktuelle Priorität
ausgewählt
(620). Die teilnehmenden Warteschlangen bei der aktuellen
Priorität,
falls vorhanden, werden auf der Basis der Warteschlangenfreigabe,
des Backlogs und der Bandbreitenzustände und Priorität ermittelt
(630). Wenn mindestens eine teilnehmende Warteschlange
bei der aktuellen Priorität
vorhanden ist (640), wird die Gewinnerauswahl freigegeben
und der Round-Robin-Arbiter wird benachrichtigt (650).
Wenn nicht, wird die nächste
höchste
Priorität,
falls vorhanden, als die aktuelle Priorität ausgewählt (660). Wenn nicht
alle Prioritäten
geprüft
worden sind, geht der Fluß zu
Schritt 630 zurück;
andernfalls wird der Fluß verlassen
(670).
-
Zurückgehend
zu 7 ist ein Flußdiagramm
der kennzeichnenden Warteschlangenauswahl in der Round-Robin-Arbitrierung für ein repräsentatives
Vorauswahlelement gezeigt. Das Element empfängt Informationen für die Warteschlangen,
die das Element darstellt (710), und prüft, ob die letzte gewinnende
Warteschlange die letzte kennzeichnende Warteschlange des Elements
war (720). Wenn die letzte gewinnende Warteschlange die
letzte kennzeichnende Warteschlange des Elements ist, wählt das
Element die nächste
(teilnehmende oder nichtteilnehmende) Warteschlange, die das Element
in der Round-Robin-Reihenfolge darstellt (730). Wenn die
letzte gewinnende Warteschlange nicht die letzte kennzeichnende
Warteschlange des Elements ist, wählt das Element die erste (teilnehmende
oder nichtteilnehmende) Warteschlange, die das Element als die aktuelle
Warteschlange darstellt (740). In jedem Fall prüft das Element,
ob die aktuelle Warteschlange bereits auf Teilnahme an dieser Auswahlrunde überprüft worden
ist (750). Wenn die aktuelle Warteschlange bereits auf
Teilnahme überprüft worden
ist, hat das Element keine kennzeichnende Warteschlange in dieser Auswahlrunde
und der Endselektor wird benachrichtigt (755). Wenn die
aktuelle Warteschlange noch nicht auf Teilnahme überprüft worden ist, wird sie geprüft (760).
Wenn die aktuelle Warteschlange eine teilnehmende Warteschlange
ist, ist die aktuelle Warteschlange die kennzeichnende Warteschlange
und der Endselektor wird benachrichtigt (765). Wenn die
aktuelle Warteschlange keine teilnehmende Warteschlange ist, wird
eine weitere Prüfung
durchgeführt,
um zu ermitteln, ob die aktuelle Warteschlange die letzte Warteschlange
ist, die das Element darstellt (770). Wenn die aktuelle
Warteschlange die letzte dargestellte Warteschlange ist, umläuft das
Element zyklisch, wird der Endselektor benachrichtigt und der Fluß geht zurück zu Schritt 740.
Wenn die aktuelle Warteschlange nicht die letzte dargestellte Warteschlange
ist, geht der Fluß zurück zu Schritt 730.
-
Abschließend zurückgehend
zu 8 wird ein Flußdiagramm der Auswahl der gewinnenden
Warteschlange in der Round-Robin-Arbitrierung
gezeigt. Die kennzeichnenden Warteschlangen, Mitteilungen "kein Kennzeichner", falls vorhanden,
und Mitteilungen "zyklischer
Umlauf", falls vorhanden,
werden empfangen (810) und die Vorauswahl, deren kennzeichnende
Warteschlange die letzte Arbitrierung gewonnen hat, wird als das
aktuelle Element ausgewählt
(820). Eine Prüfung
erfolgt, ob das aktuelle Element eine kennzeichnende Warteschlange
in dieser Auswahlrunde aufweist (830). Wenn das aktuelle
Element eine kennzeichnende Warteschlange in dieser Auswahlrunde
aufweist, erfolgt eine weitere Prüfung, ob das aktuelle Element
zyklisch umlaufen ist (840). Wenn das aktuelle Element
zyklisch nicht umläuft,
ist die kennzeichnende Warteschlange von dem aktuellen Element die
gewinnende Warteschlange, der Warteschlangentreiber und die Elemente
werden benachrichtigt und der Fluß wird verlassen (850).
Wenn jedoch das aktuelle Element keine kennzeichnende Warteschlange
aufweist oder das aktuelle Element zyklisch umlaufen ist, wird das
nächste
Element in der Round-Robin-Reihenfolge als das aktuelle Element
ausgewählt
(860). Wenn das neue aktuelle Element in dieser Auswahlrunde
bereits geprüft
worden ist (870), wird das vorherige Element wieder als
das aktuelle Element genommen und der Fluß geht zu Schritt 850.
Wenn das neue aktuelle Element in dieser Auswahlrunde bereits geprüft worden
ist, geht der Fluß zurück zu Schritt 830.
-
Der
Fachmann wird erkennen, daß die
Erfindung in anderen spezifischen Formen ausgeführt sein kann, ohne vom Geltungsbereich
der Patentansprüche
abzuweichen. Die vorliegende Beschreibung wird daher in jeder Hinsicht
als veranschaulichend und nicht einschränkend angesehen. Der Geltungsbereich
der Erfindung ist durch die beigefügten Patentansprüche angegeben
und alle Änderungen,
die innerhalb der Bedeutung und des Bereichs von Äquivalenten
daraus entstehen, sollen darin eingeschlossen sein.
| Bezugszeichen | Englisch | Deutsch |
| | | |
| | FIGURE
1 | FIG.
1 |
| | HIGH
PRIORITY | HOHE
PRIORITÄT |
| | MEDIUM
PRIORITY | MITTLERE
PRIORITÄT |
| | LOW
PRIORITY | NIEDRIGE
PRIORITÄT |
| 10 | | UNICAST |
| 20 | | UNICAST |
| 30 | | UNICAST |
| 40 | | UNICAST |
| 50 | | FLUT |
| 60 | | AUSGANG |
| | RESTRICTED
BANDWIDTH | EINGESCHRÄNKTE BANDBREITE |
| | UNRESTRICTED
BANDWIDTH | UNEINGESCHRÄNKTE BANDBREITE |
| | | |
| | FIGURE
2 | FIG.
2 |
| | MULTI-STAGE
SELECT | MEHRSTUFENAUSWAHL |
| 220 | | MANAGER |
| 232 | | AUSWAHLMASKEN |
| 234 | | PRIORITÄTS-BANDBREITENAUSWAHL |
| 236 | | ROUND-ROBIN-ARBITER |
| 250 | | STATISTIK |
| 240 | | TREIBER |
| | SCHEDULER | SCHEDULER |
| | | |
| | FIGURE
3 | FIG.
3 |
| | QUEUE
ID | WARTESCHLANGEN-ID |
| 312 | | FREIGABEMASKE |
| 314 | | BACKLOGMASKE |
| 316 | | BANDBREITENMASKE |
| 318 | | PRIORITÄTSMASKEN |
| 324 | | MASKENVERGLEICH |
| 326 | | GEWINNERAUSWAHLFREIGABE |
| 328 | | PRIORITÄTSZÄHLER |
| | | |
| | FIGURE
4 | FIG.
4 |
| 410 | PRELIMINARY
SELECT | VORAUSWAHL |
| 420 | FINAL
SELECT | ENDAUSWAHL |
| | | |
| | FIGURE
5 | FIG.
5 |
| | QUEUE
ID | WARTESCHLANGEN-ID |
| | HERD | BEGINN |
| | TAIL | ENDE |
| | CURRENT
DEPTH | AKTUELLE
TIEFE |
| | MAX
DEPTH | MAX.
TIEFE |
| | CURRENT
CREDIT | AKTUELLER
KREDIT |
| | TOTAL
CREDIT | GESAMTKREDIT |
| | | |
| | FIGURE
6 | FIG.
6 |
| | ENTER | EINTRETEN |
| 610 | | TEILNEHMERAUSWAHL
FREIGEBEN |
| 620 | | HÖCHSTE PRIORITÄT AUSWÄHLEN |
| 630 | | TEILNEHMENDE
WARTESCHLANGEN AUF BASIS VON FREIGABE-, BACKLOG- UND BANDBREITENZUSTÄNDEN UND AKTUELLER PRIORITÄT ERMITTELN |
| 640 | | MINDESTENS
EINE TEILNEHMENDE WARTESCHLANGE? |
| | N | NEIN |
| | Y | JA |
| 650 | | GEWINNERAUSWAHL
FREIGEBEN; GEWINNERAUSWAHL ÜBER
WARTESCHLANGEN-INFORMATIONEN
BENACHRICHTIGEN |
| 710 | | GEHE
ZU 710 |
| 660 | | NÄCHSTE HÖHERE PRIORITÄT AUSWÄHLEN, FALLS
VORHANDEN |
| 670 | | ALLE
PRIORITÄTEN
GEPRÜFT? |
| | N | NEIN |
| | Y | JA |
| | EXIT | VERLASSEN |
| | | |
| | FIGURE
7 | FIG.
7 |
| 810 | | GEHE
ZU 810 |
| 810 | | GEHE
ZU 810 |
| 755 | | KEINE
KENNZEICHNENDE WARTESCHLANGE; ENDSELEKTOR BENACHRICHTIGEN |
| | Y | JA |
| 765 | | DAS
IST MEINE KENNZEICHNENDE WARTESCHLANGE; ENDSELEKTOR BENACHRICHTIGEN |
| | Y | JA |
| | FROM
650 | VON 650 |
| 710 | | MEINE
WARTESCHLANGEN-INFORMATIONEN
EMPFANGEN |
| 720 | | WAR
DIE LETZTE GEWINNENDE WARTESCHLANGE MEINE KENNZEICHNENDE WARTESCHLANGE? |
| | N | NEIN |
| | Y | JA |
| 730 | | MEINE
NÄCHSTE
WARTESCHLANGE AUSWÄHLEN |
| 750 | | IST
DIESE WARTESCHLANGE BEREITS GEPRÜFT
WORDEN? |
| | N | NEIN |
| 760 | | IST
DIESE WARTESCHLANGE EINE TEILNEHMENDE WARTESCHLANGE? |
| | N | NEIN |
| 770 | | IST
DIESE WARTESCHLANGE MEINE LETZTE WARTESCHLANGE? |
| | Y | JA |
| 780 | | ZYKLISCHER
UMLAUF; ENDSELEKTOR BENACHRICHTIGEN |
| 740 | | MEINE
ERSTE WARTESCHLANGE AUSWÄHLEN |
| | | |
| | FIGURE
8 | FIG.
8 |
| | FROM
755 | VON 755 |
| | FROM
765 | VON 765 |
| | N | NEIN |
| | Y | JA |
| 840 | | IST
DIESER SELEKTOR BEREITS GEPRÜFT
WORDEN? |
| | N | NEIN |
| | Y | JA |
| 860 | | NÄCHSTEN VORSELEKTOR AUSWÄHLEN |
| 880 | | ZUM
VORHERGEHENDEN VORSELEKTOR ZURÜCKGEHEN |
| 810 | | KENNZEICHNENDE
WARTESCHLANGEN EMPFANGEN; KEINE MITTEILUNGEN KENNZEICHNENDER WARTESCHLANGEN;
MITTEILUNGEN DES ZYKLISCHEN UMLAUFS |
| 820 | | LETZTEN
VORSELEKTOR AUSWÄHLEN |
| 830 | | HAT
DIESER SELEKTOR EINE KENNZEICHNENDE WARTESCHLANGE? |
| | Y | JA |
| 840 | | LÄUFT DIESER
SELEKTOR ZYKLISCH UM? |
| | N | NEIN |
| 850 | | DIE
KENNZEICHNENDE WARTESCHLANGE VON DIESEM SELEKTOR IST DIE GEWINNENDE
WARTESCHLANGE; WARTESCHLANGENTREIBER UND VORSELEKTOREN BENACHRICHTIGEN |
| | EXIT | VERLASSEN |
| | | |