DE60314205T2

DE60314205T2 - Arbiter für ein Vermittlungssystem mit Eingangspuffer

Info

Publication number: DE60314205T2
Application number: DE60314205T
Authority: DE
Inventors: Vishnu Petaluma Meenaradchagan
Original assignee: Calix Networks Inc
Current assignee: Calix Inc
Priority date: 2002-07-19
Filing date: 2003-07-17
Publication date: 2008-01-31
Anticipated expiration: 2023-07-18
Also published as: DE60314205D1; ATE364278T1; EP1383287B1; US20040017804A1; US6954811B2; EP1383287A1

Description

Die US 10/199,996 , deren Priorität die vorliegende Anmeldung beansprucht, wurde mit einem Anhang A eingereicht, der Dateien enthält, die Quellcode von Computerprogrammen für eine illustrative Ausgestaltung der vorliegenden Erfindung bilden, einschließlich Computerbefehlen in der Sprache C++ zum Beschreiben des Verhaltens einer Ausgestaltung eines Zuteilers, der Flüsse von zwei Prioritäten durch ein Crossconnect und Definitionen von verschiedenen Konstanten und Datenstrukturen unterstützt, die von den Computerbefehlen im Computer verwendet werden. Aus der nachfolgenden Beschreibung wird für die Fachperson jedoch klar werden, wie die Erfindung mit geeignetem Quellcode umgesetzt werden kann.
URHEBERRECHTSHINWEIS
Ein Teil der Offenbarung des vorliegenden Patentdokuments enthält Material, das urheberrechtlich geschützt ist. Der Urheberrechtsinhaber hat keine Einwände gegen eine Telefaxvervielfältigung des Patentdokuments oder der Patentoffenbarung, wie sie in den Patentunterlagen des Patent- und Warenzeichenamts erscheinen, behält sich aber ansonsten alle Urheberrechte vor.
HINTERGRUND
Man betrachte das Problem des Bauens eines Kommunikationsswitch mit N Eingangsports und N Ausgangsports. Wenn wir die Puffer an den Ausgangsports platzieren, dann brauchen wir Speicher mit einer Bandbreite, die gleich der Summe der Bandbreiten der Eingangsports ist. Dies kann mit Hilfe eines schnellen statischen Speichers mit sehr breiten Speicherbussen erfolgen. Mit derzeitiger Speichertechnologie ist diese Lösung nur dann rentabel, wenn die Gesamtbandbreite des Switch weniger als 50 Gbit/sec beträgt. Daher ist eine VOQ-(Virtual Output Queued)-Architektur eine attraktive Option zum Bauen von Switches mit höherer Gesamtbandbreite. Da jedoch die Hardware-Komplexität des Zuteilers O(N²) beträgt, sind die VOQ-Switches nur für Switches mit einer mäßigen Zahl von Switch-Ports (z.B. N ≤ 32) praktisch. Man beachte, dass die Zahl der Switch-Ports gleich der Zahl der Leitungskarten ist. Die tatsächliche Zahl der Switch-Ports kann höher sein, da mehrere Ports durch die Leitungskarten multiplexiert/demultiplexiert werden können. In einem Switch mit der VOQ-Architektur ist die Speicherschreibbandbreite gleich der Eingangsportbandbreite und die Lesebandbreite ist gleich der Switch-Bandbreite. Die Bandbreite eines Crossconnect (1A) ist um einen Beschleunigungsfaktor höher als die maximale Portbandbreite. Der Zuteiler muss auf oder über der maximalen Portbandbreite arbeiten. Die Ausgangspuffer brauchen lediglich eine Lesebandbreite zu haben, die gleich der Ausgangsportbandbreite ist, und eine Schreibbandbreite, die gleich der Bandbreite der Switch-Fabric ist.
Umfangreiche Arbeiten an dem Problem des Erhöhens des Durchsatzes von eingangsgepufferten Switches wurden von N. W. McKeown in einem Artikel mit dem Titel „The iSLIP scheduling algorithm for input-queued switches", IEEE/ACM Transactions an Networking, Bd. 7, Nr. 2, April 1999, und von N. W. McKeown, M. Izzard, A. Mekkittikul, W. Ellersick und M. Horowitz in einem anderen Artikel mit dem Titel „The tiny tera: A packet switch core", in Hot Interconnects V, August 1996, beschrieben. Das Zuteilungsproblem ist äquivalent mit einem zweiteiligen Anpassungsproblem, für das der bestbekannte Algorithmus eine Zeitkomplexität in der Größenordnung von n^n/2 hat, wie von J. E. Hopcroft und R. M. Karp in einem Artikel mit dem Titel „An n^5/2 algorithm for maximum matchings for bipartitle graphs" im SIAM Journal an Computing, Bd. 2, Nr. 4, S. 225-231, 1973, beschrieben wurde.
Ein Hardware-Zuteiler muss Zuteilungsentscheidungen innerhalb eines Zellintervalls der Switch-Fabric machen. Dies kann nur mit Hilfe von Parallelismus und sorgfältigen Methoden zum Minimieren der Wahrscheinlichkeit einer „Synchronisation" von Entscheidungen durch unabhängige, parallel arbeitende Module erzielt werden. Eine Möglichkeit, einen Zuteiler zu bauen, besteht darin, zwei Sätze von N unabhängigen Schedulern zu verwenden, wie in 1B gezeigt ist. Der j-te Scheduler im ersten Satz entspricht dem j-ten Ausgangsport, und der i-te Scheduler im zweiten Satz entspricht dem i-ten Eingangsport. Der j-te Ausgangsport-Scheduler wählt einen Eingangsport aus dem Satz von Eingangsports aus, die eine Zellenankunft am j-ten Ausgangsport angezeigt haben. Und der i-te Eingangsport-Scheduler wählt einen Ausgangsport aus dem Satz von Ausgangsports aus, die den i-ten Eingangsport im ersten Schritt gewählt hatten. Eventuelle nicht übereinstimmende Ein- und Ausgangsports werden in der/den nachfolgenden Iteration(en) abgestimmt. Ein mit PIM-(Parallel Iterative Matching)-Zuteilungsalgorithmus bezeichnetes Verfahren des Standes der Technik arbeitet mit Zufallsschedulern: Ein anfordernder Port wird mit gleichförmiger Wahrscheinlichkeit ausgewählt. Dieser Algorithmus wird von T. Anderson, S. Owicki, J. Saxe und C. Thacker in einem Artikel mit dem Titel „High speed switch scheduling for local area networks", ACM Transactions an Computer Systems, Bd. 11, Nr. 4, S. 319-352, November 1993, näher beschrieben.
Ein weiteres Verfahren, nämlich der in dem Artikel mit dem Titel „The iSLIP scheduling algorithm for input-queued switches" beschriebene iSLIP-Zuteilungsalgorithmus, arbeitet mit Round-Robin-Schedulern. Im Falle von iSLIP sind die Scheduler nicht wirklich unabhängig: Der Round-Robin-Scheduler in der Eingabeeinheit wird nur dann weitergeschaltet, wenn seine Auswahl vom Round-Robin-Scheduler an der Ausgabeeinheit akzeptiert wird. In kommerziellen Switches werden verschiedene gewichtete Versionen der Round-Robin-Scheduler verwendet. Es ist jedoch zu bemerken, dass ein einfacher gewichteter Round-Robin-Ansatz nicht geeignet ist, da er die Wahrscheinlichkeit einer „Synchronisation" erhöht. „Synchronisation" tritt dann auf, wenn mehr als ein Scheduler wiederholt denselben Port auswählt und somit den Switch-Durchsatz reduziert. McKeown schlug die Verwendung von kreisförmigen Planungslisten zum Implementieren gewichteter iSLIP-Zuteiler vor. Es werden jedoch sehr große Planungslisten benötigt und die Programmierung dieser Listen beim Addieren und Wegnehmen von Verbindungen ist kein triviales Problem. Die beiden Sätze von Schedulern verwenden zudem zwei Gewichtungssätze und es scheint keine einfache Beziehung zwischen den Gewichtungen und der den Flüssen zugeordneten Bandbreite zu geben. Der Hauptnachteil davon, dass die Zuteiler zwei Sätze von Schedulern verwenden, ist jedoch, dass diese Zuteiler keine Fairness des Typs bieten, der von D. Cavendish, M. Goudreau und A. Ishii in einem Artikel mit dem Titel „On the fairness of scheduling algorithms for input-queued switches" im International Teletraffic Congress vom Dezember 2001 in Bd. 4 auf den Seiten 829-841 beschrieben ist. Die US 6 389 031 beschreibt ein Verfahren der vorliegenden Erfindung zum Adressieren einer hierarchischen Suche. Das heißt, m₀ höchstwertige Bits der Zeitstempeladresse werden auf Level 0 verwendet. Dann wird auf Level 1 die komplette auf dem oberen Level (1-1) verwendete Adresse zum Finden des richtigen g₁ Bitwortes in seinem g₁ M_1-1 Speicher verwendet. Weitere log₂g₁ Bits nach den vorherigen m_1-1 Bits werden aus der Zeitstempeladresse extrahiert, die zum Finden des richtigen Bits im g₁ Bitwort verwendet wird, das soeben identifiziert wurde. Somit ist die Suchzeit von der Zahl der Level L abhängig. So kann ein Scheduler das Setzen großer Datenverkehrsflusszahlen auf eine schnelle Datenlink planen (d.h. mit einem kleinen Zeitfenster). Ein zwei- (2) dimensionaler Former arbeitet mit einer ähnlichen hierarchischen Such- und Adressiertechnik. Schließlich wird jeder Überlauf von binär codierten Zeitstempel- und Systempotentialwerten verfolgt, so dass Zeitstempelalterung keine Probleme verursacht.
ZUSAMMENFASSUNG
Gemäß der Erfindung wird ein Verfahren zum Übertragen von Datenverkehr durch einen Switch mit einer Mehrzahl von Eingangsports und einem Ausgangsport bereitgestellt, wobei das Verfahren die folgenden Schritte beinhaltet: Inkrementieren eines Paares von Zählern für einen Datenverkehrsfluss von einem Eingangsport zu einem Ausgangsport als Reaktion auf den Empfang von Datenverkehr am Eingangsport; Dekrementieren eines Zählers (nachfolgend „erster Zähler" genannt) in dem Paar Zählern für jeden Fluss, wenn der erste Zähler ungleich null ist; Auswählen eines Eingangsports (nachfolgend „Siegereingangsport" genannt) wenigstens teilweise auf der Basis von Werten von Zählern in dem Paar für wenigstens einen Fluss von dem Eingangsport; und Erzeugen eines Signals zum Übertragen einer Datenverkehrsmenge von dem Siegereingangsport, dadurch gekennzeichnet, dass eine Differenz zwischen der Rate, mit der Datenverkehr tatsächlich übertragen wird, angezeigt durch den zweiten Zähler in dem Paar, und der Rate ermittelt wird, mit der Datenverkehr idealerweise übertragen werden sollte, angezeigt durch den ersten Zähler in dem Paar, wobei die genannte Differenz zum Identifizieren eines Siegerflusses verwendet wird.
So führt ein Zuteiler für einen Kommunikationsswitch ein Paar Zähler für jeden Datenverkehrsfluss an jedem Eingangsport: ein Zähler (auch „erster Zähler" genannt) zum Anzeigen eines idealen Datenverkehrstransfers, ein weiterer Zähler (auch „zweiter Zähler" genannt) zum Anzeigen des tatsächlichen Datenverkehrstransfers. Beide Zähler werden inkrementiert, wenn Datenverkehr vom Eingangsport empfangen wird, aber die beiden Zähler werden auf unterschiedliche Weisen dekrementiert, wie nachfolgend beschrieben wird.
Der zweite Zähler wird dekrementiert, wenn eine Verkehrseinheit (wie z.B. eine Zelle oder ein Paket) für die Übertragung durch den Eingangsport zu einem Zielausgangsport zugelassen wird. Der Betrag der Dekrementierung ist proportional zur Größe der Datenverkehrseinheit, die übertragen wird. Daher zeigt der Wert im zweiten Zähler jedes Eingangsports die Menge an Datenverkehr an, die am Eingangsport angekommen ist und die den Transfer durch den Kommunikationsswitch nicht beendet hat, unabhängig von Datenverkehrsbedingungen an anderen Ports. Der erste Zähler wird auf stückweise (relativ zur Datenverkehrseinheit) dekrementiert, wenn eine Datenverkehrsfraktion in einer aktuellen Periode übertragen werden kann. Der Wert im ersten Zähler hängt von der am Port verfügbaren Bandbreite und von Datenverkehrsbedingungen an anderen Ports ab.
Es wird auch eine entsprechende Vorrichtung bereitgestellt.
In bestimmten Ausgestaltungen wählt der Zuteiler einen der Ausgangsports (nachfolgend „Siegerausgangsport" genannt) wenigstens teilweise auf der Basis von Werten der beiden Zähler für jeden Fluss vom Eingangsport zu einem der Ausgangsports, und erzeugt ein Signal (nachfolgend „Grant-Signal" genannt) zum Zulassen von Datenverkehrsübertragungen vom Eingangsport zum Siegerausgangsport.
In mehreren Ausgestaltungen ist der oben beschriebene Fluss einer aus einer Reihe von Flüssen für Datenverkehr mit unterschiedlichen Prioritäten, der zwischen dem Eingangsport und dem Ausgangsport übertragen werden soll, und jeder Fluss ist mit wenigstens dem ersten und dem zweiten Zähler assoziiert. Das Dekrementieren des ersten Zählers für jeden Hochprioritätsfluss erfolgt automatisch periodisch, es sei denn, dass der erste Zähler null ist. Wenn der erste Zähler eines Hochprioritätsflusses kleiner ist als eine Bandbreitenanforderung (auch „Gewichtung" genannt) des Hochprioritätsflusses, dann ist der Dekrementierbetrag gleich dem ersten Zähler, sonst ist der Dekrementierbetrag gleich der Bandbreitenanforderung.
In mehreren Ausgestaltungen kann eventuelle Restbandbreite von der Übertragung von Hochprioritätsdatenverkehr bei der Übertragung von Datenverkehr in einem oder mehreren Niederprioritätsflüssen auf der Basis eines mit jedem Eingangsport und jedem Ausgangsport assoziierten zusätzlichen Zählers verwendet werden. Speziell, bestimmte Ausgestaltungen des Zuteilers führen einen Zähler (nachfolgend „benutzte Eingangsportbandbreite" genannt) für jeden Eingangsport, der die Gesamtdekremente im ersten Zähler jedes Flusses zwischen dem Eingangsport und allen Ausgangsports anzeigt, und führen auch einen Zähler (nachfolgend „benutzte Ausgangsportbandbreite" genannt) für jeden Ausgangsport, der eine Summe von Dekrementen im ersten Zähler jedes Flusses zwischen dem Ausgangsport und allen Eingangsports anzeigt. Die Differenz zwischen der benutzten Eingangsportbandbreite und einer vorbestimmten Eingangsportbandbreite repräsentiert die an jedem Eingangsport für die Übertragung von Niederprioritätsverkehr zur Verfügung stehende Restbandbreite. Ebenso repräsentiert die Differenz zwischen der benutzten Ausgangsportbandbreite und der maximalen Ausgangsportbandbreite die an jedem Ausgangsport für die Übertragung von Niederprioritätsverkehr verfügbare Restbandbreite.
In einigen Ausgestaltungen werden die soeben beschriebenen Restbandbreiten auf iterative Weise von den Eingangseinheiten des Zuteilers den Ausgangseinheiten des Zuteilers zugewiesen, bis ein Fluss von einer Eingangseinheit zu einer Ausgangseinheit gesättigt ist, und zu diesem Zeitpunkt wird der gesättigte Fluss aus der Iteration herausgenommen. Ein Fluss ist dann gesättigt, wenn die Bandbreitenzuweisung für den Fluss aufgrund von Portbandbreitenbeschränkungen oder deshalb nicht erhöht werden kann, weil die für den Fluss zugewiesene Bandbreite die Bandbreite einer Quelle des Flusses erreicht hat. Die Portbandbreitenbeschränkung wird dann erreicht, wenn die Bandbreitensumme aller Flüsse durch einen Port die von dem Port unterstützte maximale Bandbreite übersteigt. Die Iteration kann eine feste Anzahl von Malen (z.B. zweimal) oder alternativ so lange durchgeführt werden, bis alle Flüsse gesättigt sind.
KURZBESCHREIBUNG DER ZEICHNUNGEN
1A illustriert einen Crosspoint-Switch des Standes der Technik.
1B illustriert in einem Blockdiagramm einen iSLIP-Zuteiler des Standes der Technik, der durch eine Reihe von Eingangseinheiten und Ausgangseinheiten ausgeführt wird, die durch zwei unidirektionale serielle Leitungen miteinander verbunden sind.
2A illustriert in einem Blockdiagramm einen Zuteiler gemäß der Erfindung, der ein Paar Zähler für jeden Eingangsport führt.
2B und 2C illustrieren in einem Fließschema in zwei Ausgestaltungen ausgeführte Verfahren zum Führen der Zähler von 2A und die Erzeugung eines Grant-Signals zum Zulassen der Übertragung von Datenverkehr von jedem Eingangsport zu einem Siegerausgangsport.
3A und 3B illustrieren alternative Ausgestaltungen des Zuteilers und des Verfahrens, die jeweils in 2A und 2B illustriert sind.
4 illustriert in einem Blockdiagramm den Zuteiler von 2A in einer Ausführung, die eine Eingangseinheit für jeden Eingangsport und eine Ausgangseinheit für jeden Ausgangsport enthält.
5A und 5B illustrieren in Blockdiagrammen jeweils die Schnittstellen des Ein- und des Ausgangsports in einer Ausführung der Ausgestaltung von 4.
6A und 6B illustrieren in Blockdiagrammen auf einer Zwischenebene Zähler, die im Ein- und im Ausgangsport der 5A und 5B enthalten sind.
7A-7E illustrieren in Low-Level-Blockdiagrammen Teile der Eingangseinheitslogik 605 (von 6A) in einer speziellen Ausführung.
8A-8C illustrieren in Low-Level-Blockdiagrammen Teile der Ausgangseinheitslogik 615 (von 6B) in einer speziellen Ausführung.
9A illustriert in einem Timing-Diagramm die Reihenfolge, in der Steuersignale von einer Ausgestaltung eines Zuteilers für die Verwendung mit der in den 7A-7E und 8A-8C illustrierten Schaltungsanordung erzeugt werden.
9B illustriert in einem Low-Level-Blockdiagramm die Schaltungsanordnung zum Erzeugen der Steuersignale von 9A.
AUSFÜHRLICHE BESCHREIBUNG
In bestimmten Ausgestaltungen der Erfindung ist ein Netzwerkelement so strukturiert, dass es einen VOQ-(Virtual Output Queue = Virtuelle Ausgangswarteschlange)-Switch und einen Zuteiler 120 (2A) verwendet, der ein Paar Zähler für jeden Fluss (in einer virtuellen Ausgangswarteschlange gepuffert) an jedem Eingangsport führt. So wird beispielsweise ein Paar Zähler 121AA und 122AA (gemeinsam als Zähler 123AA bezeichnet) für einen ersten Fluss „A" (in 2A nicht dargestellt oder bezeichnet) durch einen ersten Eingangsport 102A geführt. Auf ähnliche Weise werden Zähler 123AI für den i-ten Fluss durch den ersten Eingangsport 102A geführt und Zähler 123AN werden für den N-ten Fluss durch den ersten Eingangsport 102A geführt. Ferner werden Zähler 123IA für den ersten Fluss im i-ten Eingangsport 102I geführt, usw.
Von den zwei Zählern 123IJ, die für jeden Datenverkehrsfluss geführt werden, zeigt ein Zähler (auch „erster Zähler" genannt) einen idealen Transfer von Datenverkehr unabhängig von den diskreten Größen der einzelnen Datenverkehrseinheiten an, und ein weiterer Zähler (auch „zweiter Zähler" genannt) verfolgt den tatsächlichen Transfer von Datenverkehr. Aus diesem Grund hat der erste Zähler in einigen Ausgestaltungen eine höhere Auflösung als der zweite Zähler, so kann der erste Zähler z.B. ein 32-Bit-Zähler sein, während der zweite Zähler ein 8-Bit-Zähler ist, oder alternativ kann der erste Zähler ein Gleitpunktzähler und der zweite Zähler ein Ganzzahlenzähler sein. Jedes Paar Zähler 123IJ wird nach der Ankunft von für den jeweiligen Ausgangsport 103J bestimmtem Datenverkehr am jeweiligen Eingangsport 102I inkrementiert (wie durch Schritt 141 in 2B illustriert).
Die Ankunft von Datenverkehr in einer der virtuellen Ausgangswarteschlangen (VOQs) an einem Eingangsport 102I kann dem Zuteiler 120 über ein Signal („Datenverkehrsankunft” genannt) angezeigt werden, das vom jeweiligen Eingangsport des Netzwerkelementes erzeugt wird. Man beachte, dass der Datenverkehr in Form von Paketen variabler Länge, Zellen fester Länge oder einer Kombination davon vorliegen kann, obwohl der Datenverkehr in bestimmten Ausgestaltungen in Form von Zellen fester Länge vorliegt, und in solchen Ausgestaltungen wird das Datenverkehrsankunftssignal als Zellenankunft bezeichnet.
In der in 2A illustrierten Ausgestaltung bewirkt das Datenverkehrsankunftssignal automatisch ein Weiterschalten des jeweiligen Zählerpaares, aber in einer alternativen Ausgestaltung wird ein solches Signal durch eine Logik 125 (nachfolgend „Zuteilungslogik" genannt) empfangen, die die Zähler (gemäß Schritt 141) dann inkrementiert. Daher ist zu verstehen, dass Ausgestaltungen sich im Hinblick auf den Gebrauch von spezieller Hardware unterscheiden können, die beliebige der Schritte 141-145 von Methode 140 ausführt. Darüber hinaus können solche Schritte in einer beliebigen Reihenfolge ausgeführt werden (einschließlich gleichzeitig), obwohl eine spezielle Reihenfolge als in einigen Ausgestaltungen verwendet illustriert wurde.
Zum Anzeigen eines idealen Transfers von Datenverkehr dekrementiert (gemäß Schritt 142 in 2B) die Zuteilungslogik 125 in jeder Periode automatisch den ersten Zähler für jeden Fluss, wenn der erste Zähler ungleich null ist. Als Nächstes wählt die Zuteilungslogik 125 (gemäß Schritt 143 in 2B) null oder einen Fluss an jedem Eingangsport (auch „Siegerfluss" genannt) wenigstens teilweise auf der Basis von Werten von Zählern in dem Paar für jeden Fluss vom Eingangsport zu einem der Ausgangsports aus. Wie in 2A illustriert, können die Zähler von der Zuteilungslogik 125 über Busse 128A-128N gelesen werden, die mit den jeweiligen Zählern 123A-123N verbunden sind.
Die beim Auswählen eines Siegerflusses (und somit eines Ausgangsports, der auch „Siegerausgangsport" genannt wird) verwendeten besonderen Kriterien hängen von der Ausgestaltung ab. In einigen Ausgestaltungen erfolgt die Auswahl auf der Basis der relativen Werte der beiden Zähler jedes Flusses in Verbindung mit dem Eingangsport. In einer speziellen Ausgestaltung wählt die Zuteilungslogik 125 (in einem Beispiel von Schritt 143 in 2B) den Fluss aus, der die größte Differenz zwischen Zählern unter allen Flüssen in Verbindung mit dem Eingangsport hat, dessen erster Zähler gleich oder kleiner als der zweite Zähler ist. Unabhängig davon, wie die Auswahl erfolgt, wenn ein Siegerfluss gewählt wird, dann erzeugt eine Zuteilungslogik 125 ein Signal (auch „Grant" (= Gewährung)-Signal genannt) auf einem Bus 124I zum Eingangsport 102I (siehe 2A), um den Transfer von Datenverkehr vom Eingangsport zum Siegerausgangsport des Eingangsports zuzulassen, wie durch Schritt 144 in 2B illustriert wird.
Als Reaktion auf das Grant-Signal überträgt jeder Eingangsport den Datenverkehr des Siegerflusses (von einer virtuellen Ausgangswarteschlange) zum Kommunikationsswitch 130, der in bestimmten Ausgestaltungen als Crossconnect implementiert werden kann, obwohl auch andere Strukturen (wie z.B. ein mehrstufiger Switch, z.B. ein Butterfly-Switch, ein Batcher-Banyan-Switch oder ein Clos-Switch) in anderen Ausgestaltungen zum Einsatz kommen können. So kann beispielsweise Datenverkehr von einem Eingangsport 102N über einen Bus 131N zum Switch 130 übertragen werden, der wiederum zum Übertragen des Datenverkehrs zum Zielausgangsport, z.B. Port 103N, über den Bus 132N programmiert ist. Der Deutlichkeit halber wurden in 2A nicht alle solche Busse dargestellt, obwohl zu verstehen ist, dass jeder Port im Netzwerkelement 100 mit Switch 130 verbunden ist.
Ferner ist der Zuteiler 120 in bestimmten Ausgestaltungen mit dem Switch 130 gekoppelt, um davon ein Überlastung darin anzeigendes Signal zu empfangen, für die Verwendung beim Abbremsen oder Stoppen der Ausgabe von Grant-Signalen zu einem oder mehreren für die Überlastung verantwortlichen Ports. In mehreren solchen Ausgestaltungen wird der Switch 130 mit einer Reihe von FIFO-(First-In-First-Out)-Warteschlangen an den Ein- und Ausgängen von Switch 130 erweitert, und jeder Ausgang von Switch 130 hat einen unabhängigen Scheduler, der Eingangsports für den Empfang von Datenverkehr davon auf eine Round-Robin-Weise auswählt.
An irgendeinem Punkt danach wird der zweite Zähler des Siegerflusses durch die Zuteilungslogik 125 (z.B. über den Bus 128I) dekrementiert, um den tatsächlichen Transfer von Datenverkehr (gemäß Schritt 145 in 2B) zu verfolgen. Je nach Situation können ein oder mehrere der oben beschriebenen Schritte 141-145 in der nächsten Periode wiederholt werden (jede Periode wird durch die Zeit definiert, die zum Übertragen des Datenverkehrs als Reaktion auf das Grant-Signal erforderlich ist, und die Periode kann durch die Geschwindigkeit der Backplane festgelegt werden (z.B. Geschwindigkeit der Busse 131N und 132N). Wenn beispielsweise in der nächsten Periode zusätzlicher Datenverkehr empfangen wird, dann wird Schritt 141 wiederholt, gefolgt von der Ausführung der Schritte 142-145 (z.B. wenn nur ein Fluss im gesamten Netzwerkelement aktiv ist).
Ferner können die Schritte 143-145 selbst in der aktuellen Periode für jeden Eingangsport (gemäß Zweig 147) wiederholt oder alternativ auch gleichzeitig ausgeführt werden. Ferner kann Schritt 142 wie von Zweig 148 illustriert wiederholt werden, z.B. dann, wenn kein zusätzlicher Datenverkehr in der nächsten Periode empfangen wird und wenn keiner der Flüsse am Eingangsport zur Auswahl freigegeben ist (die Freigabe eines Flusses ist in einigen Ausgestaltungen vor der Auswahl erforderlich, wie nachfolgend erörtert wird).
Speziell, in einigen Ausgestaltungen führt die Zuteilungslogik 125 vor dem Auswählen gemäß Schritt 147 (2C) einen Schritt 146 (2C) aus, um null oder mehr Flüsse am Eingangsport auf der Basis eines vorbestimmten Kriteriums zuzulassen. Je nach Ausgestaltung kann das vorbestimmte Kriterium so ausgelegt werden, dass die Wahrscheinlichkeit einer Synchronisation beim Auswählen desselben Ausgangsports durch mehr als einen Eingangsport reduziert wird. In einigen Ausgestaltungen wird ein vorbestimmtes Kriterium so ausgelegt, dass ein Fluss an einem Eingangsport 102I auf der Basis des Wertes I ermöglicht wird, z.B. dann, wenn der zweite Zähler um wenigstens (R/N)·I größer ist als der erste Zähler, wobei I die Flussidentität, R die Auflösung und N die Anzahl der Flüsse sind. Ein solcher Gebrauch von Identität I führt zu einem gestaffelten Freigeben der Flüsse für jeden Eingangsport relativ zum Anfang der Periode.
In mehreren Ausgestaltungen ist der oben beschriebene Datenverkehrsfluss einer aus einer Reihe von Flüssen für Datenverkehr mit unterschiedlichen Prioritäten, der zwischen dem Eingangsport und dem Ausgangsport übertragen werden soll, und jeder Fluss (unabhängig von der Priorität) ist mit wenigstens dem ersten und zweiten Zähler wie in 3A illustriert assoziiert. So beinhalten beispielsweise Zähler 123A zwei Paare von Zählern, nämlich Zähler 121AAH und 122AAH, die ein Paar für einen Hochprioritätsfluss im ersten Eingangsport 102A bilden, und Zähler 121AAL und 122AAL, die ein weiteres Paar für einen Niederprioritätsfluss im ersten Eingangsport 102A bilden. In 3A ist zwar nur ein Satz von Zählern 123AA für ein Paar Hoch- und Niederprioritätsflüsse illustriert, aber es ist zu verstehen, dass es für jeden Eingangsport so viele Flüsse (und somit so viele Sätze von Zählern) wie Ausgangsports geben kann, so dass eine VOQ-(Virtual Output Queue)-Architektur implementiert wird.
Solche Ausgestaltungen führen ein Verfahren 150 (3B) mit den Schritten 151, 152 sowie 154-156 aus, die den entsprechenden, oben mit Bezug auf die 2B und 2C beschriebenen Schritten 141, 142 sowie 144-147 ähnlich oder damit identisch sind, mit der Ausnahme, dass die Flüsse für das Führen von Hochprioritäts- oder Niederprioritätsdatenverkehr spezifisch sind. In solchen Ausgestaltungen erfolgt die Dekrementierung des ersten Zählers für jeden Hochprioritätsfluss automatisch periodisch, es sei denn, dass der erste Zähler null ist. Wenn der erste Zähler eines Hochprioritätsflusses kleiner ist als eine Bandbreitenanforderung (auch „Gewichtung" genannt) des Hochprioritätsflusses, dann ist der Dekrementierbetrag gleich dem ersten Zähler, sonst ist der Dekrementierbetrag gleich der Bandbreitenanforderung.
In solchen Ausgestaltungen prüft ferner die Zuteilungslogik 125 vor den Freigabe- und Auswahlschritten (gemäß den Schritten 156 und 157), ob es nach der Zuordnung von Bandbreite für Hochprioritätsflüsse (gemäß Schritt 152) an jedem Port Restbandbreite gibt (gemäß Schritt 160). Wenn ja, dann weist die Zuteilungslogik 125 solche Restbandbreite für die Übertragung von Niederprioritätsdatenverkehr zu. Wenn die Bandbreite Niederprioritätsdatenverkehr zugewiesen wird, dann dekrementiert die Zuteilungslogik 125 einen ersten Zähler für jeden Niederprioritätsfluss, dem Bandbreite zugewiesen wird (gemäß Schritt 160). Die Restbandbreite kann nur Flüssen zugewiesen werden, deren erster Zähler ungleich null ist, um dadurch zu gewährleisten, dass die Restbandbreite zum Übertragen von Datenverkehr benutzt wird. Bei Bedarf kann die Zuordnung von Restbandbreite jeweils in kleinen Bruchteilen über eine Reihe von Iterationen erfolgen, bis ein oder mehrere Flüsse gesättigt ist/sind. Die spezielle Zuweisung von Restbandbreite zu Niederprioritätsflüssen kann je nach Ausgestaltung anders erfolgen.
Speziell, mehrere Ausgestaltungen des Zuteilers führen einen Zähler (nachfolgend „benutzte Eingangsportbandbreite" genannt) für jeden Eingangsport, der die Gesamtdekremente während einer Periode im ersten Zähler jedes Flusses zwischen dem Eingangsport und allen Ausgangsports anzeigt, und führen auch einen Zähler (nachfolgend „benutzte Ausgangsportbandbreite" genannt) für jeden Ausgangsport, der eine Summe von Dekrementen im ersten Zähler jedes Flusses zwischen dem Ausgangsport und allen Eingangsports anzeigt. Die Differenz zwischen der benutzten Eingangsportbandbreite und einer vorbestimmten Eingangsportbandbreite repräsentiert die unbenutzte Bandbreite (auch „Eingangsportrestbandbreite" genannt), die an jedem Eingangsport für die Übertragung von Niederprioritätsverkehr zur Verfügung steht. Ebenso repräsentiert die Differenz zwischen der benutzten Ausgangsportbandbreite und der maximalen Ausgangsportbandbreite die unbenutzte Bandbreite (auch „Ausgangsportrestbandbreite" genannt), die an jedem Ausgangsport für die Übertragung von Niederprioritätsverkehr zur Verfügung steht.
In vielen Ausgestaltungen werden die soeben beschriebenen Restbandbreiten auf iterative Weise von den Eingangsports zu den Ausgangsports zugewiesen, bis ein Fluss vom Eingangsport zu einem Ausgangsport gesättigt ist, darauf wird der gesättigte Fluss aus der Iteration entfernt. Ein Fluss ist dann gesättigt, wenn die Bandbreitenzuweisung für den Fluss aufgrund einer Portbandbreitenbeschränkung oder deshalb nicht erhöht werden kann, weil die für den Fluss zugewiesene Bandbreite die Bandbreite eines Ursprungs des Flusses erreicht hat. Die Portbandbreitenbeschränkung ist dann erreicht, wenn die Bandbreitensumme aller Flüsse durch einen Port die von dem Port unterstützte maximale Bandbreite übersteigt. Die Iteration kann eine feste Anzahl von Malen (z.B. zweimal) oder alternativ so lange ausgeführt werden, bis alle Flüsse gesättigt sind.
Einige Ausgestaltungen des Zuteilers erzeugen Grant-Signale für die Übertragung von ATM-(Asynchronous Transfer Mode)-Zellen von den Eingangsports zu den Ausgangsports eines Crossconnect. Mehrere solcher Ausgestaltungen simulieren innerhalb des Zuteilers eine Reihe von Eingangsports, die Eingangsports des Crossconnect entsprechen, eine Reihe von Ausgangsports, die Ausgangsports des Crossconnect entsprechen, und eine Übertragung von Bruchteilen von Zellen (auch „Fluid" genannt) von jedem simulierten Eingangsport (auch „Eingangseinheit" genannt) zu jedem simulierten Ausgangsport (auch „Ausgangseinheit" genannt). Anstatt eine einzelne Zuteilungslogik 125 zu haben, wird die Logik daher zur Zuteilung unter allen simulierten Ports verteilt (d.h. unter Eingangseinheiten IU_1 bis UI_N und Ausgangseinheiten OU_1 bis OU_N, wie in 4 illustriert). Der Fluidtransfer zwischen den simulierten Eingangsports IU_1-IU_N und den simulierten Ausgangsports OU_1-OU_N erfolgt auf eine durch die diskrete Größe jeder Zelle unbeschränkte Weise, damit der Zuteiler 120 einen historischen Speicher der Bandbreiten führen kann, die jedem Fluss an jedem Eingangsport im Laufe der Zeit bereitgestellt werden.
In mehreren solchen Ausgestaltungen überträgt eine Eingangseinheit IU_i zu jeder Ausgangseinheit OU_j ein Signal (nachfolgend „Bereitschaftssignal" genannt) wie in 4 illustriert. Das Bereitschaftssignal zeigt die Bereitschaft eines Eingangsports IU_i zum Übertragen von Fluid an und wird nur dann erzeugt, wenn der erste Zähler des Niederprioritätsflusses ungleich null ist und wenn die Eingangsportrestbandbreite ungleich null ist. Solche Bereitschaftssignale von allen Eingangseinheiten IU_1-IU_N werden von einer Ausgangseinheit OU_j zum Ermitteln eines Betrags (nachfolgend „angeforderter Betrag" genannt) von Fluid von einem für die Ausgangseinheit OU_j bestimmten Niederprioritätsfluss von jeder Eingangseinheit IU_i wenigstens teilweise auf der Basis der Augangsportrestbandbreite berücksichtigt. Die angeforderten Beträge werden dann von einer Ausgangseinheit OU_j (über 8-Bit-Busse) denjenigen Eingangseinheiten IU_1-IU_N angezeigt, die Bereitschaft angezeigt haben.
Eine Reihe von Anforderungsbeträgen von einer entsprechenden Anzahl von simulierten Ausgangsports OU_1-OU_N werden von jedem simulierten Eingangsport IU_i beim Ermitteln eines Betrags (nachfolgend „bedienter Betrag" genannt) von Niederprioritätsfluid berücksichtigt, das vom simulierten Eingangsport IU_i zum simulierten Ausgangsport OU_j übertragen werden soll. Die bedienten Beträge werden dann zum Reduzieren der Eingangsportrestbandbreite an jeder bereiten Eingangseinheit IU_i benutzt und diese bedienten Beträge werden auch den Ausgangseinheiten gekennzeichnet, die die bedienten Beträge bereitgestellt haben. Die bedienten Beträge werden dann von jeder Ausgangseinheit zum Reduzieren der Ausgangsportrestbandbreite verwendet. Die soeben beschriebenen Schritte können iterativ, z.B. zweimal ausgeführt werden.
Man beachte, dass das Bereitschaftssignal, der angeforderte Betrag und der bediente Betrag in 4 zwar jeweils mit 1 Bit Breite, 8 Bit Breite und 8 Bit Breite illustriert sind, aber diese Größen sind lediglich illustrativ und es kann je nach Ausgestaltung jede beliebige Anzahl von Bits verwendet werden.
In der in 4 illustrierten Implementation beinhaltet der Zuteiler 120 einen Zähler 402 („Phasenzähler” genannt), der zu Beginn jeder Periode auf null gesetzt wird, und dieser wird eine vorbestimmte Anzahl von Malen (z.B. 10 Mal) während der Periode inkrementiert, je nach der Geschwindigkeit, mit der der Zuteiler 120 arbeitet. Der Zähler 402 teilt jeder der Eingangseinheiten IU_1-IU_N und Ausgangseinheiten OU_1-OU_N die aktuelle Phasennummer (z.B. die Taktzyklusnummer) mit. Ferner ist, wie in 4 illustriert, der Zuteiler 120 auch mit einem Mikroprozessor 401 verbunden (beinhaltet ihn aber nicht), der den Inhalt verschiedener Register in den Eingangseinheiten IU_1-IU_N und Ausgangseinheiten OU_1-OU_N liest und schreibt. In bestimmten Ausgestaltungen wird der Mikroprozessor 401 zum Initialisieren bestimmter Register benutzt, z.B. Gewichtungen, die je nach den durch den Switch 130 eingerichteten Verbindungen zugewiesen werden können.
In 4 ist das Datenverkehrsankunftssignal von einer VOQ für Datenverkehr an einem Eingangsport i, der für einen Ausgangsport j bestimmt ist, mit „hp_cell_arrival(i,j)" bezeichnet. In bestimmten Ausgestaltungen bilden die einzelnen, das Datenverkehrsankunftssignal führenden Leitungen einen parallelen Bus (mit einer Breite von 2N Bits zur Aufnahme von einem Bit für jede VOQ und einem Bit zum Anzeigen der Priorität des Datenverkehrs). Daten vom Bus werden bei der Übertragung über eine Backplane, die jeden Eingangsport 102I vom Zuteiler 120 trennt, in die serielle Form und nachfolgend für die Verwendung durch den Zuteiler 120 zurück in die parallele Form umgewandelt. Ferner ist ein vom Zuteiler 120 erzeugtes Grant-Signal mit „grant (i, winning_output, priority) bezeichnet, wobei „i" den Eingangsport IU_i, winning_output den für den Datenverkehrstransfer gewählten Ausgangsport OU_j und priority die Auswahl von Nieder- oder Hochprioritätsfluss anzeigt.
In den 5A und 5B sind interne Details jeweils der Ein- und der Ausgangseinheit nicht illustriert, weil eine solche Schaltungsanordnung je nach Ausgestaltung anders ist. Eine Ausgestaltung eines Zuteilers für die Verwendung mit einem langsamen Crossconnect beinhaltet einen Mikroprozessor mit Speicher (auch Microcontroller genannt), der ein Firmware-Programm abarbeitet, das die Funktionen der Eingangseinheit, der Ausgangseinheit und des Fluidstroms dazwischen ausführt. Unabhängig von der Schaltungsanordnung, die zum Implementieren einer Ein- und einer Ausgangseinheit verwendet wird, hat jede dieser Einheiten die in den 5A und 5B illustrierte Signalschnittstelle. Speziell, jede Eingangseinheit IU_i empfangt von einer Steuerung jeder Hochprioritäts-VOQ (virtuelle Ausgangswarteschlange) im Eingangsport i das Signal hp_cell_arrival (i,j) für jeden Hochprioritätsfluss j, der mit der VOQ j (nicht einzeln dargestellt) assoziiert ist. Ebenso empfängt auch jede Eingangseinheit IU_i von einer Steuerung jeder Niederprioritäts-VOQ im Eingangsport i das Signal lp_cell_arrival (i,j) für jeden Niederprioritätsfluss j, der mit einer entsprechenden Niederprioritäts-VOQ j (nicht dargestellt) assoziiert ist. Zusätzlich hat jeder Eingangsport IU_i eine Anzahl von Bussen, die jeweils mit jedem Ausgangsport OU_j verbunden sind. Die soeben beschriebenen Busse beinhalten ein „Ready"-(Bereit)-Signal und eine Bedienungsnummer, die beide von einer Eingangseinheit IU_i zu einem Ausgangsport OU_j gesendet werden, und ein „Request"-(Anforderung)-Signal, das in der entgegengesetzten Richtung, vom Ausgangsport OU_j zum Eingangsport IU_i, gesendet wird.
Ferner hat auch, wie in den 5A und 5B illustriert, jede Eingangseinheit IU_i und jede Ausgangseinheit OU_j einen Phasenbus, der eine Phase anzeigt (in Form einer Zahl, z.B. im Bereich von 1-10, die monoton einmal pro Taktzyklus ansteigt, es sei denn, dass sie am Ende des Bereichs zurückspringt), in dem der Zuteiler 120 gerade arbeitet. Die Phase wird von jeder Eingangseinheit IU_i und jeder Ausgangseinheit OU_j zum Bewahren der Synchronisation miteinander verwendet. Zudem hat auch jede Eingangseinheit IU_i und jede Ausgangseinheit OU_j einen Mikroprozessorbus, der eine Schnittstelle zu einem externen Mikroprozessor 401 (4) für die Verwendung beim Initialisieren bereitstellt.
6A illustriert in einer i-ten Eingangseinheit IU_i einer bestimmten Ausgestaltung enthaltene Register. In der nachfolgenden Beschreibung werden diese Begriffe synonym benutzt:

erster Zähler Fluidzähler

zweiter Zähler Einzelzähler

Bandbreitenanforderung Gewichtung

benutzte Eingangsportbandbreite S_i ⁱⁿ

benutzte Ausgangsportbandbreite S_i ^out
Jede Eingangseinheit IU_i enthält N Hochprioritäts-Fluidzähler 608, N Hochprioritäts-Einzelzähler 609, N Niederprioritäts-Fluidzähler 610, N Niederprioritäts-Einzelzähler 611, N Hochprioritätsgewichtungen 607 und N Niederprioritätsgewichtungen 606 der von der i-ten Eingangseinheit ausgehenden Flüsse.
Jede Eingangseinheit IU_i enthält auch ein Register 601 zum Speichern der Bandbreite, die während der Zwischenzuteilungsperiode verwendet wird, ein Register 602 zum Anzeigen der der Eingangseinheit entnommenen Fluidmenge und ein Register 603 zum Anzeigen der Summe S_i ⁱⁿ von Gewichtungen der von der Eingangsheit ausgehenden aktiven Flüsse. Jede Eingangseinheit IU_i enthält auch Logik 605 (auch „Eingangseinheitslogik" genannt), die mit jedem der soeben beschriebenen Zähler (auch „Register" genannt) zum Lesen und/oder Beschreiben der Register in der oben beschriebenen Weise verbunden ist (z.B. mit Bezug auf die in 3B illustrierte Methode). Der Deutlichkeit halber sind die Verbindungen zwischen der Logik 605 und den Zählern in 6A nicht dargestellt.
Auf ähnliche Weise illustriert 6B eine Ausgangseinheit OU_j, die Register für Hochprioritätsgewichtungen 616 und Niederprioritätsgewichtungen 617 der für die j-te Ausgangseinheit bestimmten Flüsse enthält. 6B illustriert auch Register 611-613, um jeweils Bandbreite, die zur Ausgangseinheit ablaufende Fluidmenge und die Summe der Gewichtungen der für die Ausgangseinheit bestimmten aktiven Flüsse zu speichern.
Die Ausgangseinheitslogik 615 ist auch mit jedem der soeben beschriebenen Register verbunden, um die Register in der oben beschriebenen Weise zu lesen und/oder darauf zu schreiben (z.B. mit Bezug auf die in 3B illustrierte Methode). In den 6A und 6B sind interne Details der Eingangseinheitslogik und der Ausgangseinheitslogik jeweils nicht illustriert, weil eine solche Schaltungsanordnung je nach Ausgestaltung anders ist.
In einer speziellen Implementation beinhaltet eine Eingangseinheit IU_i eine Schaltung 700 (7A) zum Erzeugen des Ready-Signals (oben erörtert) und eine bediente Fluidmenge für einen Hoch- oder Niederprioritätsfluss (ebenfalls oben erörtert), die einer Ausgangseinheit OU_j zugeführt werden. Die bediente Fluidmenge σ_ij kann wie nachfolgend im Addendum A in der Beschreibung vor Gleichung (9) und wie mit Bezug auf Gleichung (15) beschrieben bestimmt werden. In dieser Implementation, wie in 7A illustriert, beinhaltet die Schaltung 700 einen Subtrahierer 701, der Eingangsleitungen hat, die mit den oben beschriebenen Registern 601 und 602 (auch a_j ⁱⁿ und s_i ⁱⁿ Register genannt) verbunden sind, und Ausgangsleitungen, die mit einem Logikblock 701 zum Prüfen auf Nicht-Null-Werte verbunden sind. Speziell prüft Block 701, ob der vom Subtrahierer 704 erzeugte Wert ungleich null ist, und steuert, wenn ja, ein Signal zum AND-Gate 703 aktiv an. Das AND-Gate 703 erhält sein anderes Eingangssignal von einem anderen Nicht-Null-Block 702, der wiederum mit einem Zähler 121AAL verbunden ist (auch Nieder prioritäts-Fluidzähler f_ij ^lp genannt).
Wie oben erwähnt, kann die Eingangseinheit IU_i unter bestimmten Umständen eine Fluidanforderung von der Ausgangseinheit OU_j empfangen, und der angeforderte Betrag ρ_ij wird in einem Register 708 (7A) zwischengespeichert, das auch in der Schaltung 700 enthalten ist. Die Zwischenspeicherung erfolgt als Reaktion darauf, dass ein Signal latch_request aktiv wird (das in den Phasen 4 und 8 wie in 12 illustriert aktiv wird, z.B. aufgrund eines in der Eingangseinheitslogik 605 enthaltenen Signalgenerators). Das zwischengespeicherte Signal wird als erstes Eingangssignal zu einem Block 707 gesendet, der den Mindestwert von drei Eingangssignalen findet. Block 707 empfangt ein zweites Eingangssignal (das die Menge an Niederprioritätsfluid f_ij ^lp in der Eingangseinheit anzeigt) vom Zähler 121AAL (auch Niederprioritäts-Fluidzähler genannt). Block 707 empfängt ein drittes Eingangssignal von einer Multiplizier/Dividier-Einheit 706.
In der Schaltung 700 empfängt die Multiplizier/Dividier-Einheit 706 drei Eingangssignale und erzeugt als Ausgang das Ergebnis der Multiplikation der beiden ersten Eingangssignale und der Division des Ergebnisses durch das dritte Eingangssignal, wenn das dritte Eingangssignal ungleich null ist. Wenn das dritte Eingangssignal null ist, dann sendet der Multiplizier/Dividier-Block 706 einen Nullwert zum Min-Block 707. In der Schaltung 700 empfangt der Multiplizier/Dividier-Block 706 als sein erstes Eingangssignal einen Wert, der vom Subtrahierer 704 erzeugt wurde, als sein zweites Eingangssignal eine Niederprioritätsfluid-Gewichtung w_ij ^lp in einem Register 606i und als sein drittes Eingangssignal eine Summe von Gewichtungen von aktiven Flüssen S_i ⁱⁿ. Block 707 sendet das kleinste seiner Eingangssignale zu einem Mux 710, der ein 2-zu-1-Multiplexer ist. Der Mux 710 empfangt als sein anderes Eingangssignal einen Wert von einem Min-Block 709, der zwei Eingangssignale empfangt, von jedem der beiden Register 121AAH und 607i (jeweils auch Hochprioritätsfluidzähler und Hochprioritätsgewichtung genannt). Der Mux 710 sendet ein Signal zum Serve-Bus gesteuert durch ein Signal serve_bus_select_hp, das bewirkt, dass der Serve-Bus im aktiven Zustand den Hochprioritätsbetrag und im inaktiven Zustand einen Niederprioritätsbetrag hat.
7B illustriert in einem Low-Level-Blockdiagramm die Logik 720 in einer Implementation der Eingangseinheitslogik 605 einer Eingangseinheit IU_i (6A) zum Aktualisieren eines zusätzlichen Zählers 602 (gemäß Gleichung (16) in Addendum A) zum Anzeigen des zugeführten Betrags s_i ⁱⁿ (d.h. die benutzte Bandbreite). Die Logik 720 beinhaltet einen Addierer 721, der als Eingang jeden der zugeführten Beträge von jeder der Ausgangseinheiten OU_1-OU_N empfängt und die Summe zu einem anderen Addierer 722 sendet, der als seinen anderen Eingang den bedienten Gesamtbetrag s_i ⁱⁿ empfängt, der im Register 602 enthalten ist. Ein Steuersignal update_served_in veranlasst das Register 602, den Ausgang vom Addierer 722 zwischenzuspeichern, um dadurch zu bewirken, dass das Register 602 den bedienten Gesamtbetrag s_i ⁱⁿ um die Summe der Beträge in den Serve-Bussen zu jeder Ausgangseinheit von der i-ten Eingangseinheit zu inkrementieren.
Die 7C und 7D illustrieren einen Schaltkomplex in der Eingangseinheitslogik 605 einer Eingangseinheit IU_i (6A), um jeweils den Hoch- und den Niederprioritäts-Fluidzähler 608i und 610i zu aktualisieren. Mit Bezug auf 7C, wenn das Signal hp_cell_arrival angelegt wird, dann wählt der Multiplexer 731 seinen Nicht-Null-Eingang, mit Auflösung R, und dieser R-Wert wird einem Subtrahierer 733 zugeführt. Der Subtrahierer 733 empfängt als seinen anderen Eingang einen Null-Wert, wenn das Signal decrement_hp_fluid inaktiv ist, und empfängt ansonsten als seinen anderen Eingang den bedienten Betrag (vom Serve-Bus von der i-ten Eingangseinheit zur j-ten Ausgangseinheit). Wenn also das Signal decrement_hp_fluid inaktiv ist, dann wird der Hochprioritäts-Fluidzähler 608i um R, die Auflösung, inkrementiert. Wenn das Steuersignal decrement_hp_fluid angelegt wird (z.B. durch einen Steuersignalgenerator des in 9B illustrierten Typs), dann wird der Fluidzähler 608ii um den in dem gezeigten Serve-Bus gezeigten Betrag dekrementiert. Man beachte, dass die obige Schaltung 730 dann wie erwartet funktioniert, wenn beide Signale anliegen. Aufbau und Betrieb des Schaltkomplexes 740 (7D) für Niederprioritätsfluid sind mit den oben für Hochprioritätsfluid erörterten identisch, nur dass die entsprechenden Mengen für niedrige Priorität verwendet werden.
7E illustriert in einem Low-Level-Blockdiagramm Logik in einer Ausführung der Eingangseinheit von 6A zum Berechnen der Summe der Gewichtungen der Niederprioritätsflüsse mit Nicht-Null-Anforderungen, die von der i-ten Eingangseinheit stammen. Speziell, ein Addierer 753 empfängt ein Signal von jedem der Multiplexer 751A-751N, wobei jeder Multiplexer 751k wiederum entweder den Null-Wert oder die Niederprioritätsgewichtung w_ik ^lp wählt, je nachdem, ob der angeforderte Betrag von der k-ten Ausgangseinheit größer als null ist oder nicht (was in einem Checker 752k markiert ist). Die vom Addierer 753 bereitgestellte Summe wird im Register 603 zwischengespeichert, wenn das Signal sum_lp_weights_in aktiv wird (z.B. in den Phasen 5 und 9).
8A illustriert in einem Low-Level-Blockdiagramm Logik in einer Ausführung der Ausgangseinheit von 6B zum Berechnen des Anforderungsbetrags zur i-ten Eingangseinheit. Speziell, der Schaltkomplex 800 beinhaltet eine Multiplizier/Dividier-Einheit 806, die drei Eingangssignale empfangt: ein erstes Signal vom Subtrahierer 804, ein zweites Signal vom Register 617k, das die Niederprioritätsgewichtung w_ik ^lp identifiziert, und einen dritten Eingang vom Register 613 (oben beschrieben), das den Gesamtbetrag von Fluid s_i ^out enthält, der während der aktuellen Periode zum i-ten Ausgangsport übertragen wird. Die Multiplizier/Dividier-Einheit 806 und der Subtrahierer 804 arbeiten auf eine Weise, die den oben beschriebenen entsprechenden Teilen in der Schaltung 700 ähnlich oder damit identisch sind, nämlich der Multiplizier/Dividier-Einheit 706 und dem Subtrahierer 704.
8B illustriert in einem Low-Level-Blockdiagramm die Logik 820 in einer Ausführung der Ausgangseinheit von 6B zum Berechnen des im Register 613 gehaltenen bedienten Fluidbetrags s_i ^out gemäß Gleichung (18) in Addendum A. Die Logik 820 ist im Hinblick auf Aufbau und Funktion der oben mit Bezug auf 7 beschriebenen Logik 720 ähnlich, ausgenommen, dass Ausgangsmengen anstatt Eingangsmengen verwendet werden.
8C illustriert in einem Low-Level-Blockdiagramm die Logik 850 in einer Ausführung der Ausgangseinheit von 6B zum Berechnen der Summe von Niederprioritätsgewichtungen von Flüssen mit anliegendem Ready-Signal. Die Logik 850 ist im Hinblick auf Aufbau und Funktion der oben mit Bezug auf 7E beschriebenen Logik 750 ähnlich, mit der Ausnahme, dass kein Checker 752k benötigt wird, weil das Ready-Signal ein Einzelbit-Signal ist, das den Betrieb des Mux 851k direkt steuert.
Es wird eine Reihe von Steuersignalen für die Verwendung mit Logik in den Ein- und Ausgangsports gemäß der in 9A illustrierten Timing-Tabelle erzeugt. 9B illustriert die Erzeugung dieser Signale auf der Basis einer Phasenzahl, indem einfach ein Decoder zum Erzeugen von zehn Signalen verwendet wird, die individuell in den jeweiligen zehn Subintervallen der aktuellen Periode aktiv sind. Wenn also die aktuelle Periode 10 Taktzyklen lang dauert, dann werden zehn Signale erzeugt (eines pro Taktzyklus), und jedes Signal ist in einem anderen Subintervall aktiv. Jedes Steuersignal, das in einem bestimmten Subintervall aktiv sein muss, wird von einem entsprechenden aktiven Signal aus den 10 aktiven Signalen abgeleitet.
Einige Ausgestaltungen des Zuteilers weisen Bandbreite für Niederprioritätsdatenverkehr wie folgt zu: (1) Inkrementieren der benutzten Eingangsportbandbreite (siehe 7B) und der benutzten Ausgangsportbandbreite (8B) um einen Wert auf der Basis von einem oder mehreren aus: (a) Eingangsportrestbandbreite, (b) angeforderter Betrag und (c) Gewichtung des Niederprioritätsflusses vom Eingangsport (gemäß Illustration durch einen „Min"-Block 707 in 7A), (2) Dekrementieren des ersten Zählers für den Niederprioritätsfluss um den soeben beschriebenen Inkrementwert (siehe 7D), und (3) Erzeugen eines bedienten Betrags, der den soeben beschriebenen Inkrementwert anzeigt (siehe 7A). Die Schritte (1) Inkrementieren der benutzten Eingangsportbandbreite, (2) Dekrementieren des zweiten Zählers und (3) Erzeugen des bedienten Betrags können ein oder mehrere Male wiederholt werden, um sicherzustellen, dass keine Bandbreite ungenutzt bleibt.
Für die Fachperson werden angesichts der Offenbarung zahlreiche Modifikationen und Adaptionen an den hierin beschriebenen Ausgestaltungen offensichtlich sein.
So überträgt beispielsweise in einer alternativen Ausgestaltung das Crossconnect anstatt Zellen fester Länge Pakete variabler Länge. In einer solchen alternativen Ausgestaltung wird der Fluss, anstatt an einem Eingangsport um einen festen Betrag bei Ankunft einer Zelle inkrementiert zu werden, um einen variablen Betrag inkrementiert, der proportional zur Länge des Pakets bei dessen Ankunft ist. Ferner kann in bestimmten Ausgestaltungen der Zuteiler, anstatt vom hierin beschriebenen Typ zu sein, der einen elektrischen Crossconnect-Switch steuert, einen optischen Switch steuern, und anstatt von Zeitfenstern wird jedem Eingangsport Bandbreite in Form von einer oder mehreren Wellenlängen für die Übertragung von Datenverkehr durch den optischen Switch zugeordnet. In einigen Ausgestaltungen wird zwar ein einzelner Prozessor in jedem simulierten Eingangsport und jedem simulierten Ausgangsport des Zuteilers benutzt, aber in anderen Ausgestaltungen können andere Prozessoren die einzelnen Schritte eines Verfahrens des hierin beschriebenen Typs ausführen, so dass diese Prozessoren eine solche Methode gemeinsam als eine Gruppe ausführen.
Ferner können einige Ausgestaltungen mehr als zwei Zähler in Verbindung mit jedem Fluss haben, die von einem Zuteiler geführt werden, und in diesem Fall werden wenigstens zwei Zähler in der hierin für den ersten Zähler und den zweiten Zähler beschriebenen Weise geführt. In einigen Ausgestaltungen hat der erste Zähler (auch „Fluidzähler" genannt) zwar eine größere Auflösung als der zweite Zähler (auch „Einzelzähler" genannt), aber in anderen Ausgestaltungen können beide Zähler dieselbe Auflösung haben und in diesem Fall werden die beiden Zähler unterschiedlich dekrementiert: der zweite Zähler wird um einen festen Betrag dekrementiert, der größer (z.B. eine oder zwei Größenordnungen größer als) der kleinste Betrag ist, um den der erste Zähler dekrementiert wird.
Ebenso können, obwohl im Zusammenhang eines Zuteilers beschrieben, eine oder mehrere Strukturen des Zuteilers und/oder ein oder mehrere Schritte der von dem Zuteiler ausgeführten Methode in anderen Geräten verwendet werden. So kann beispielsweise ein Scheduler, der den Fluss von Datenverkehr durch einen einzelnen Port eines Switch plant, die folgenden Schritte ausführen: (1) Inkrementieren eines Paares von Zählern für einen Fluss von Datenverkehr von einem für einen Ausgangsport bestimmten Eingangsport als Reaktion auf den Empfang von Verkehr am Eingangsport, (2) Dekrementieren eines ersten Zählers in dem Paar Zähler für jeden Fluss dekrementieren, wenn der erste Zähler ungleich null ist, (3) Wählen eines Siegereingangsports wenigstens auf der Basis von Werten von Zählern in dem Paar für wenigstens einen Fluss vom Eingangsport, und (4) Erzeugen eines Signals zum Übertragen einer Datenverkehrsmenge vom Siegereingangsport zum Ausgangsport.
Zahlreiche solcher Modifikationen und Adaptionen der hierin beschriebenen Ausgestaltungen werden durch die beiliegenden Ansprüche abgedeckt.
Addendum A, Addendum B und Addendum C sind integrale Bestandteile der vorliegenden ausführlichen Beschreibung und sind nachfolgend dargelegt. Addendum A illustriert verschiedene Grundsätze für die Verwendung beim Entwerfen eines Zuteilers des hierin beschriebenen Typs. Addendum B bietet eine architektonische Spezifikation für einen Zuteiler, der auf der Basis der Prinzipien in Addendum A entworfen wurde. Addendum C gibt Kontext für die Implementation eines Beispiels für einen Zuteiler des hierin beschriebenen Typs. Zusätzlich illustriert der beiliegende Software-Anhang Aufbau und Betrieb eines Zuteilers gemäß der Erfindung in Form einer Einzelevent-Simulation.
Addendum A
Nachfolgend wird die GPS-(Generalized Processor Sharing)-Fair-Arbitration beschrieben.
Die dem Fluss von Zellen vom i-ten Eingangsport zum j-ten Ausgangsport zugewiesene Bandbreite sei r_ij. Wenn die Portbandbreiten alle gleich L und alle Gewichtungen gleich sind, dann impliziert Fairness r_ij = L/N für alle i und j in {1, 2, ..., N}. Wir möchten die Definition von Fairness erweitern, wenn die Gewichtungen nicht alle gleich sind und wenn sich Portbandbreiten stark unterscheiden.
Eine natürliche Art, Fairness zu definieren, ist im Sinne von Fluidflüssen. Dies ist dem Ansatz des Definierens von (GPS) Fairness für (gewichtete) Service-Planungsansätze von ATM-Multiplexern ähnlich. r_i(t) sei die Bandbreite, die von dem Fluss vom i-ten Eingangsport zum Ausgangsport empfangen wird. w_i sei die Gewichtung, die dem i-ten Eingangsport zugewiesen wird. B(t) bedeutet den Satz von rückständigen Eingangsports zum Zeitpunkt t und L sei die Bandbreite der Ausgangslink. Es heißt, ein Planungsansatz sei dann GPS-fair, wenn der Satz r_i(t), 1 ≤ i ≤ N die einzige Lösung für das folgende Optimierungsproblem ist: Minimiere
vorbehaltlich der Bedingung Σ_i∊B(t)r_i(t) = L.
Die obige Definition von Fairness einer gewichteten Service-Planung kann auf die gewichtete Zuteilung erweitert werden. w_ij sei die Gewichtung des Flusses vom i-ten Eingangsport zum j-ten Ausgangsport. B(t) ⊆ {(i, j) : 1 ≤ i ≤ N,1 ≤ j ≤ N} sei die Teilmenge von rückständigen virtuellen Ausgangswarteschlangen (VOQs) zum Zeitpunkt t. L in / i (L out / i) sei die Bandbreite des i-ten Eingangs- (bzw. Ausgangs-) Ports. Es heißt, ein Zuteilungsansatz sei dann GPS-fair, wenn der Satz r_ij(t),1 ≤ i ≤ N,1 ≤ j ≤ N die einzige Lösung für das folgende Optimierungsproblem ist: Minimiere
vorbehaltlich der folgenden Bedingungen:
Es gibt einen einfachen Algorithmus zum Berechnen der Lösung für das Optimierungsproblem (2). Erhöhen der Bandbreite r_ij, die dem Fluss vom i-ten Eingangsport zum j-ten Ausgangsport zugeordnet ist, für alle i und j in {1, 2, ..., N} um w_ijΔ, wobei Δ ein kleiner Betrag ist, bis ein oder mehrere Flüsse aufgrund einer Portbandbreitenbeschränkung oder deshalb nicht weiter erhöht werden kann/können, weil r_ij die Quellrate des Flusses vom i-ten Eingangsport zum j-ten Ausgangsport erreicht hat. Ein solcher Fluss wird als gesättigter Fluss bezeichnet. Man erhöhe die ungesättigten Flüsse weiter, bis einer oder mehrere davon gesättigt wird/werden. Man wiederhole, bis alle Flüsse gesättigt sind. Der resultierende Satz von Raten r_ij ist die Lösung für das Optimierungsproblem (2).
Wenn wir zwei Prioritätsklassen haben, dann werden die Hochprioritätsraten direkt durch die Gewichtungen spezifiziert und die Niederprioritätsraten sind Lösungen für das Optimierungsproblem (2) mit L out / j und L in / j in Bedingungen (3) und (4), ersetzt durch die Restbandbreiten:
wobei R hpout / j (R hpin / i) die Gesamtbandbreite ist, die vom Hochprioritätsverkehr im j-ten Ausgangsport (bzw. i-ten Eingangsport) benutzt wird.
Der FFTA (Fluid Flow Tracking Arbiter = Fluidflussverfolgungszuteiler)) wird nachfolgend beschrieben:
Für jedes Ein-/Ausgangspaar (i, j) hat der FFTA zwei Zähler: den Einzelanforderungszähler d_ij und den Fluidanforderungszähler f_ij. Wenn eine Anforderung vom i-ten Eingangsport für den j-ten Ausgangsport empfangen wird, dann werden sowohl d_ij als auch f_ij um eine Zelle inkrementiert.
FFTA simuliert Fluidflüsse von den Eingangsports zu den Ausgangsports gemäß den Gewichtungen der Flüsse auf die oben beschriebene GPS-faire Weise. Für den i-ten Eingangsport gewährt der FFTA dem j-ten Ausgangsport, dessen Einzelanforderungsrückstand d_ij in Bezug auf den entsprechenden Fluidanforderungsrückstand f_ij am weitesten zurückliegt,. Und der gewählte d_ij wird um eine Zelle dekrementiert.
Die vom FFTA benutzten Variablen werden nachfolgend beschrieben:
Zum Unterstützen von zwei Service-Klassen, hohe Priorität und niedrige Priorität, brauchen wir vier Zähler für jedes Ein-/Ausgangspaar: d hp / ij, f hp / ij, d lp / ij und f lp / ij.
Die Einzelanforderungszähler nehmen nur ganzzahlige Werte an, während die Fluidanforderungszähler Bruchteile von Zellen repräsentieren müssen. Anstatt kostspieliger Gleitpunktarithmetik für Fluidanforderungszähler zu benutzen, können Ganzzahlenzähler benutzt werden, bei denen eine Einheit einen Bruchteil 1/R einer Zelle repräsentiert. Wir bezeichnen R als die Fluidauflösung. Wenn die Einzelanforderungszähler k Bits benötigen, dann brauchen die Fluidanforderungszähler k + ⌈log₂ R⌉ Bits. Ein geeigneter Wert für R ist 256, was bedeutet, dass die Fluidanforderungszähler 8 Bit mehr benötigen als die Einzelanforderungszähler.
Der Zuteiler gewährt jedes Zwischenzuteilungsintervall, das gleich dem Zwischenzellenintervall in der Switch-Fabric ist. Eine praktische Art und Weise des Vorgebens von Bandbreite eines Flusses oder eines Ports ist als Zellenbruchteil pro Zwischenzuteilungsintervall. Zum Beispiel, wenn der Zuteiler mit 2,5 Gbit/s Bandbreite arbeitet, dann beträgt das Zwischenzuteilungsintervall 169.600 Pikosekunden (ps). Ein Port mit 625 Mbit/sec Bandbreite hat 0,25 Zellen pro Zwischenzuteilungsintervall.
a in / i bedeute die Bandbreite des i-ten Eingangsports in der Zelle pro Zwischenzuteilungsintervall und a out / j bedeute die Bandbreite des j-ten Ausgangsports in der Zelle pro Zwischenzuteilungsintervall.
Jedes Ein-/Ausgangspaar hat auch zwei Gewichtungen, w hp / ij und w lp / ij, Die Hochprioritätsgewichtung w hp / ij gibt die Bandbreite des Flusses vom i-ten Eingangsport zum j-ten Ausgangsport vor. Es ist als Zellenbruchteil pro Zwischenzuteilungsintervall vorgegeben. Die Hochprioritätsklasse ist eine garantierte Bandbreiten-Serviceklasse und es gibt in dieser Klasse keine Überbuchung. Daher erfüllen die Hochprioritätsgewichtungen die folgenden Ungleichungen:
Der Niederprioritätsservice ist ein überbuchbarer Service, bei dem die w lp / ij Werte dimensionslose (nicht negative) Größen sind. Grob ausgedrückt, die von einem Niederprioritätsfluss vom i-ten Eingangsport zum j-ten Ausgangsport empfangene Bandbreite ist proportional zur Gewichtung w lp / ij, aber die genaue Menge an vom Fluss empfangener Bandbreite hängt von mehreren Faktoren wie z.B. der Gesamtmenge an Hochprioritätsdatenverkehr, den Portbandbreiten und dem Überbuchungsbetrag am j-ten Ausgangsport ab. Man beachte, dass VCs zugelassen sind, so dass es keine Überbuchung an den Eingangsports gibt.
Die anderen vom FFTA verwendeten Größen sind s in / i und s out / i. s in / i ist die Gesamtfluidmenge, die vom i-ten Eingangsport während des aktuellen Zwischenzuteilungsintervalls übertragen wird. Man beachte, dass s in / i die folgende Begrenzung erfüllt: 0 ≤ s in / i ≤ a in / i. Ebenso ist s out / j die Fluidmenge, die während des aktuellen Zwischenzuteilungsintervalls zum j-ten Ausgangsport übertragen wurde, und erfüllt die Begrenzung: 0 ≤ s out / i ≤ a out / i.

Die vom FFTA verwendeten Variablen sind in Tabelle 1 zusammengefasst. Tabelle 1: Die vom FFTA verwendeten Variablen

Name	Beschreibung
d hp / ij	Der Hochprioritäts-Einzelanforderungszähler
d lp / ij	Der Niederprioritäts-Einzelanforderungszähler
f hp / ij	Der Hochprioritäts-Fluidanforderungszähler
f lp / ij	Der Niederprioritäts-Fluidanforderungszähler
w hp / ij	Die Hochprioritätsgewichtung
w lp / ij	Die Niederprioritätsgewichtung
a in / i	Die Bandbreite des i-ten Eingangsports in Zelle pro Zwischenzuteilungsintervall
a out / i	Die Bandbreite des i-ten Ausgangsports in Zelle pro Zwischenzuteilungsintervall
s in / i	Die Fluidmenge (sowohl hp als auch lp), die vom i-ten Eingangsport während des aktuellen Zwischenzuteilungsintervalls übertragen wird
s out / i	Die Fluidmenge (sowohl hp als auch lp), die während des aktuellen Zwischenzuteilungsintervalls zum i-ten Ausgangsport übertragen wird

Der Aufbau des FFTA ist in 4 dargestellt, wo hp_request(i,j) die Hochprioritätsanforderung durch den i-ten Eingangsport für Zugang zum j-ten Ausgangsport bedeutet. Ebenso bedeutet lp_request(i,j) die Niederprioritätsanforderung durch den i-ten Eingang für den j-ten Ausgangsport. Der zum Verbinden der Zuteilereingangseinheiten mit den Ausgangseinheiten verwendete Bus besteht aus drei Subbussen. Das einzelne Bit-Ready-Signal zeigt an, dass die Eingangseinheit (Niederprioritäts-)Fluid für die Ausgangseinheit verfügbar hat. Der ⌈log₂ R⌉-Bitanforderungsbus zeigt die Menge an (Niederprioritäts-)Fluid an, die von der Ausgangseinheit zur Eingangseinheit angefordert wurde, und der ⌈log₂ R⌉-Bit-Serve-Bus zeigt die von der Eingangseinheit zur Ausgangseinheit gesendete Menge an (Niederprioritäts-)Fluid an.
Die i-te Eingangseinheit enthält d hp / ij, d lp / ij, f lp / ij, f lp / ij für 1 ≤ j ≤ N. Sie enthält auch s in / i und a in / i. Die j-te Ausgangseinheit enthält s out / j und a out / j. Die Gewichtungen w hp / ij und w lp / ij sind sowohl für die i-te Eingangseinheit als auch die j-te Ausgangseinheit zugängig.
Immer wenn das Hoch- (Nieder-) Prioritätsanforderungssignal zum i-ten Eingangsport für den j-ten Ausgangsport angelegt wird, werden sowohl d hp / ij als auch f hp / ij (bzw. d lp / ij und f lp / ij) um eine Zelle inkrementiert. Da eine Zelle gleich R Einheiten ist, wird der Fluidzähler um R Einheiten inkrementiert.
In jedem Zwischenzuteilungsintervall führt der FFTA zwei Tasks parallel aus.
Die erste Task überträgt Fluid von den Eingangsports zu den Ausgangsports, die zweite Task berechnet Gewährungen durch Beobachten der Differenzen zwischen dem Einzel- und dem Fluidanforderungszähler. Diese Tasks werden deshalb parallel ausgeführt, weil Gewährungen auf der Basis der Differenzen zwischen Fluid- und Einzelanforderungsrückständen im vorherigen Zwischenzuteilungsintervall berechnet werden können.
Der Transfer von Fluid wird nachfolgend beschrieben:
Tabelle 2 zeigt die an jedem Taktzyklus in einem Zwischenzuteilungsintervall zum Übertragen von Fluid von den Eingangsports zu den Ausgangsports ausgeführten Operationen. Das Hochprioritätsfluid kann in einem Taktzyklus übertragen werden, während der Transfer von Niederprioritätsfluid, der zum Füllen der Restbandbreite proportional zu den Niederprioritätsgewichtungen verwendet wird, Anforderungsbedienungs-Iterationen erfordert. Die Ausgangsportanforderung für Niederprioritätsfluid zu den Eingangsports und dem Eingangsport sendet Niederprioritätsfluid zu den anfordernden Ausgangsports. In Tabelle 2 sind zwei Niederprioritätsiterationen zu sehen. Die erste Iteration erfolgt von Taktzyklus 3 bis 6, die zweite Iteration erfolgt von Taktzyklus 7 bis 10. Die Details der individuellen Operationen werden nachfolgend angegeben.

Im ersten Taktzyklus setzt der i-te Eingangsport s in / ij auf 0 und der j-te Eingangsport setzt s in / ij auf 0. Tabelle 2: Transfer-Fluidprozeduroperationen in jedem Taktzyklus

Taktzyklus	Operation(en)
¹	Reset s in / i und s out / i auf 0 für 1 ≤ i ≤ N
2	Transfer von hp-Fluid
3	Berechnen der Summe von lp-Gewichtungen an Ausgängen
4	lp-Anforderungen durch Ausgänge
5	Berechnen der Summe von lp-Gewichtungen an Eingängen
6	lp-Service durch Eingänge
7	Berechnen der Summe von lp-Gewichtungen an Ausgängen
8	lp-Anforderungen durch Ausgänge
9	Berechnen der Summe von lp-Gewichtungen an Eingängen
10	lp-Service durch Eingänge

In der Folge bedeutet Variable ρ_ij die Menge an Fluid, die vom j-ten Ausgangsport zum i-ten Eingangsport über den Anforderungsbus angefordert wurde, und σ_ij bedeutet die Fluidmenge, die von der i-ten Eingangseinheit für die j-te Ausgangseinheit über den Serve-Bus übertragen wurde.
Im zweiten Taktzyklus setzt der i-te Eingangsport den mit der j-ten Ausgangseinheit verbundenen Serve-Bus auf σ_ij = min(w hp / ij, f hp / ij). Die folgenden Operationen werden ebenfalls im zweiten Taktzyklus durchgeführt: sini ← sini + σij (9) fhpij ← fhpij – σij (10) soutj ← soutj + σij (11)
Der i-te Eingangsport führt die ersten beiden Operationen, der j-te Ausgangsport die letzte Operation durch. Man beachte, dass im Wesentlichen die Menge an vom i-ten Eingangsport zum j-ten Ausgangsport übertragenem Hochprioritätsfluid gleich der Hochprioritätsgewichtung w hp / ij ist. Die min() Operation stellt sicher, dass die Menge an übertragenem Fluid die Fluidmenge im (i, j)-ten Hochprioritäts-Fluidanforderungszähler f hp / ij nicht übersteigt. Man beachte auch, dass am Ende dieses Zyklus s in / i ≤ a in / i und s out / j ≤ a out / j ist, weil die Ungleichungen (7) und (8) oben durch die Hochprioritätsgewichtungen erfüllt werden.
Im dritten Taktzyklus legt die i-te Eingangseinheit das Ready-Signal an die j-te Ausgangseinheit an, wenn (f lp / ij > 0) und (s in / i ≤ a in / i) ist. Mit anderen Worten, das Ready-Signal wird dann und nur dann angelegt, wenn die i-te Eingangseinheit Niederprioritätsfluid für die j-te Ausgangseinheit verfügbar hat und die Grenze für die Gesamtfluidmenge, die vom i-ten Eingangsport abgelassen werden kann, nicht erreicht ist. Die j-te Ausgangseinheit berechnet die Summe der Niederprioritätsgewichtungen s out / j über alle Eingangseinheiten, an denen das Ready-Signal anliegt:
Im vierten Taktzyklus setzt die j-te Ausgangseinheit den Anforderungsbus zur i-ten Eingangseinheit auf ρ_ij, wobei:
Im fünften Taktzyklus berechnet die i-te Eingangseinheit die Summe s in / i der Niederprioritätsgewichtung w lp / ij über alle j (Ausgänge) mit Nicht-Null-Anforderungen (ρ_ij > 0).
Im sechsten Taktzyklus berechnet die i-te Eingangseinheit die Menge an zuzuführendem Niederprioritätsfluid σ_ij zur j-ten Ausgangseinheit wie folgt und setzt den Wert in den Serve-Bus.
Die folgenden drei Operationen werden ebenfalls im sechsten Taktzyklus ausgeführt: sini ← sini + σij (16) flpij ← flpij – σij (17) soutj ← soutj + σij (18)
Auch hier werden die ersten beiden Operationen von der i-ten Eingangseinheit ausgeführt, die letzte Operation wird von der j-ten Ausgangseinheit ausgeführt. Man beachte die Differenz zwischen diesen Operationen und denen, die im zweiten Taktzyklus ausgeführt werden. Im zweiten Taktzyklus wurde f hp / ij dekrementiert, während im sechsten Taktzyklus f lp / ij dekrementiert wird.
Die Taktzyklen 3 bis 6 führen eine einzelne Iteration des Niederprioritätsfluid-Anforderungsbedienungszyklus aus. Diese Schritte werden in den Taktzyklen 7 bis 10 für die zweite Iteration wiederholt. Wenn im Zwischenzuteilungsintervall genügend Taktzyklen zur Verfügung stehen, dann kann auch eine dritte Iteration erfolgen. Die Zahl der Taktzyklen pro Zwischenzuteilungsintervall wird durch die Geschwindigkeit des Zuteilers gegenüber der Taktgeschwindigkeit bestimmt. Ein mit 2,5 Gbit/sec arbeitender Zuteiler, der mit 155,52 MHz getaktet wird, hat 24 Taktzyklen pro Zwischenzuteilungsintervall.
Zusammenfassend, der Hochprioritätsfluidtransfer wird vornehmlich durch die Hochprioritätsgewichtung bestimmt und das Niederprioritätsfluid wird mit einem Algorithmus ähnlich dem oben beschriebenen übertragen.
Die Berechnung von Gewährungen wird nachfolgend beschrieben:
Wie bereits erwähnt, wird die Task des Berechnens von Gewährungen parallel zu der oben beschriebenen Task des Übertragens von Fluid ausgeführt. Jede Eingangseinheit (siehe 4) berechnet die Gewährungen durch Ermitteln des Ausgangsports mit der größten Differenz zwischen den Einzel- und Fluidanforderungszählern. Man betrachte die i-te Eingangseinheit. Der j-te Ausgangsport gilt dann als siegesfähig, wenn entweder
Man beachte, dass ein Ausgangsport zu unterschiedlichen Zeiten für jeden Eingangsport wählbar gemacht wird. Eine solche gestaffelte Freigabe minimiert die Wahrscheinlichkeit von Grant-Bündeln für denselben Ausgangsport zu unterschiedlichen Eingangsports.
E_i sei der Satz von Ausgangsports, die für den i-ten Eingangsport zum gegenwärtigen Zeitpunkt wählbar sind. Der i-te Eingangsport ermittelt einen Ausgangsport j_w und eine Priorität ρ_w so, dass: dρwijw – fρwijw ≥ dhpij – fhpij und (21) dρwijw – fρwijw ≥ dlpij – flpij für alle j ∊ Ei (22)
Mit anderen Worten, der Siegerausgangsport und das Siegerprioritätspaar (j_w, ρ_w) maximieren die Differenz zwischen dem Einzel- und Fluidanforderungsrückstand unter allen wählbaren Ausgangsports des i-ten Eingangsports. Die i-te Eingangsporteinheit sendet eine Gewährung zum i-ten Eingangsport für den j_w Ausgangsport und die Priorität ρ_w. Man beachte, dass zum Reduzieren von Hardware die Ermittlung eines wählbaren Ausgangsports mit der maximalen Differenz über eine Reihe von Taktzyklen erfolgen kann.
Addendum B
Eine Ausgestaltung des Zuteilers (auch FFTA genannt) hat die folgenden Merkmale:

1. Bandbreitenregulierbarkeit: w hp / ij(w lp / ij) sei die Hochprioritäts-(Niederprioritäts-)Gewichtung für den Fluss vom i-ten Eingangsport zum j-ten Ausgangsport. Die vom Hochprioritätsfluss empfangene Bandbreite beträgt (w hp / ij/WEIGHT_RESOLUTION*OC48_RATE). Das heißt, jede Einheit der Hochprioritätsgewichtung repräsentiert eine absolute Bandbreite von (OC48_RATE/WEIGHT_ RESOLUTION). Eine WEIGHT_RESOLUTION von 256 bedeutet, dass die Gewichtungen 8-Bit-Größen sind. Andererseits ist die vom Niederprioritätsfluss empfangene Bandbreite
Die Summe im Nenner ist die Gesamtzahl der aktiven Eingangsports, die Niederprioritätsverkehr zum Ausgangsport speisen, und BW_AVAILABLE_FOR_LP ist die Ausgangslinkbandbreite minus der von den Hochprioritätsflüssen benutzten Bandbreite.
2. 100% Durchsatz: Simulationsstudien zeigen, dass der FFTA unter den meisten Bedingungen 100% Durchsatz liefert.
3. Erleichtert Multi-QoS-Support: Der FFTA basiert auf einem flexiblen Rahmen, der Multi-QoS-Support erleichtert.
4. Erleichtert Multicast- und Bridging-Support: Der flexible Rahmen des FFTA kann zum Unterstützen von Multicasting und Bridging verwendet werden, ohne dass dies auf Kosten des Durchsatzes ginge und ohne dass eine zusätzliche Switch-Beschleunigung oder zusätzliche Hardware im Zuteiler erforderlich wäre.

Der FFTA simuliert einen Fluidfluss von den Eingangsports zu den Ausgangsports auf eine solche Weise, dass die Fluidmenge, die von einem Eingangsport zum Ausgangsport fließt, die Bandbreitenanforderung erfüllt. Der FFTA plant Grants so, dass der Datenverkehrsfluss den simulierten Fluidfluss möglichst nahe verfolgt. Dies erfolgt durch Senden von Grants zum Ein-/Ausgangspaar, dessen Paketfluss in Bezug auf den entsprechenden Fluidfluss am meisten nacheilt.
Vom FFTA verwendete Variablen beinhalten eine Anzahl von Gewichtungen. w hp / ij(w lp / ij) sei die Hochprioritäts-(Niederprioritäts-)Gewichtung des Flusses vom i-ten Eingang zum j-ten Ausgangsport, R out / i(R in / i) sei die asynchrone Bandbreite des i-ten Ausgangs- (Eingangs-) Ports. Dann ist, wie bereits beschrieben, die vom Hochprioritätsfluss empfangene Bandbreite (w hp / ij/WEIGHT_RESOLUTION*OC48_RATE) und die vom Niederprioritätsfluss empfangene Bandbreite ist
Ein Paket-VOQ-Längenzähler wird vom FFTA wie folgt geführt. ρ hp / ij(ρ lp / ij) sei die Länge des j-ten Hoch-(Nieder-)Prioritäts-VOQ im i-ten Eingangsport. ρ hp / ij(ρ lp / ij) wird immer dann inkrementiert, wenn der VOQC des i-ten Eingangsports den Zuteiler über Zellenankünfte an seinem j-ten Hoch- (Nieder-) Prioritäts-VOQ informiert, und wird dekrementiert, wenn eine Gewährung zum i-ten Eingang für den j-ten Hoch-(Nieder-)Prioritäts-VOQ gesendet wird.
Ein Fluid-VOQ-Längenzähler wird vom FFTA wie folgt geführt. f hp / ij(f lp / ij) sei die Länge des j-ten Hoch-(Nieder-)Prioritäts-Fluid-VOQ im i-ten Eingangsport. f hp / ij(f lp / ij) wird immer dann inkrementiert, wenn der VOQC des i-ten Eingangsports den Zuteiler über Zellenankünfte an seinem j-ten Hoch-(Tief-)Prioritäts-VOQ informiert. Der Fluidzähler wird während des Schritts update_fluid_queue_length() des im nächsten Abschnitt beschriebenen FFTA-Algorithmus (um Zellenbruchteile) dekrementiert.
Der Bedienungsbetrag von Ein- und Ausgangsports wird vom FFTA wie folgt geführt. s in / i(s out / i) sei die Menge an Fluidzellen, die während des aktuellen Zuteilungszyklus von (zu) dem i-ten Eingangs- (Ausgangs-) Port übertragen werden. Diese Variablen werden zu Beginn jedes Zuteilungszyklus auf null zurückgesetzt und bei jeder Übertragung von Fluidzellen inkrementiert. a in / i(a out / i) sei die maximale Anzahl an Fluidzellen, die von (zu) dem i-ten Ein- (Ausgangs-) Port in jedem Zuteilungszyklus übertragen werden kann. Diese Variablen sind proportional zur Anzahl der dem Port zugeordneten asynchronen Kanäle, nämlich
(WEIGHT_RESOLUT:ON* number_of_async_channels_allocated_to_the_port/ MAX_NUMBER_OF_ASYNC_CHANNELS, wobei MAX_NUMBER_OF_ASYNC_CHANNELS 60 ist.
Eine Blockfluidlänge genannte Variable wird vom FFTA wie folgt geführt. Speziell, jeder Ausgangsport des Zuteilers hat eine Variable mit der Bezeichnung „Blockfluidlänge". Diese Variable wird immer dann inkrementiert, wenn eine äußere Zelle am Port ankommt. Multicast-Zellen passen zu Portzellen von überbrückten VCs, und Zellen, die ankommen, wenn der Ausgangsportpuffer seinen Schwellenwert überschritten hat, befinden sich vom Standpunkt des Zuteilers her gesehen außerhalb, weil diese Zellen nicht direkt vom Zuteiler gewährt werden. Für den Zuteiler erscheinen diese Zellen als „Hintergrundrauschen" und der Zuteiler wird damit fertig. Das heißt, wann immer es eine äußere Zelle gibt, hemmt der Zuteiler seine Grant-Geschwindigkeit von Niederprioritätsdatenverkehr wie nachfolgend beschrieben.
Eine Bedienungsmengenreduzierung wird vom FFTA wie folgt geführt. ρ out / i ist eine experimentelle Variable in Verbindung mit dem i-ten Ausgangsport. Dieser Wert wird auf (WEIGHT_RESOLUTION * Summe des Multicast- und passenden Portüberbrückten Flusses zum Port)/OC48_RATE eingestellt. Diese Menge wird von a out / i subtrahiert. Dieser Ansatz wird anstatt des oben beschriebenen Blockfluidansatzes angewendet. Der Nachteil dieses Ansatzes ist, dass Niederprioritätsdatenverkehr die dem Multicast- und überbrückten VC zugeordnete Bandbreite nicht benutzen kann, selbst wenn letzterer im Ruhezustand ist.
Die Datenstrukturen des Fluidflow-Verfolgungszuteilers bestehen aus Variablen in Verbindung mit den Eingangsports, den Ausgangsports und den Ein-/Ausgangsportpaaren. Im nachfolgend gezeigten Pseudocode sind die mit dem Eingangsport assoziierten Variablen als Mitglieder des Strukts ARB_INPUT_PORT dargestellt. Ebenso sind die, die mit dem Ausgangsport und dem Ein-/Ausgangsportpaar assoziiert sind, als Mitglieder des Strukts_ARB_OUTPUT_PORT bzw. des Strukts ARB_INOUT_PORT dargestellt. Zum Beispiel, jeder Eingangsport enthält eine boolesche Variable zum Anzeigen, ob der Eingangsport freigegeben oder gesperrt ist oder nicht, eine ganzzahlige Variable zum Anzeigen des Siegerausgangsports für den Eingangsport und Variablen zum Repräsentieren von s it / i und a in / i.
Zunächst werden die globalen Konstanten, die Anzahl der Ports und die Gewichtungsauflösung definiert, die 8 Bit beträgt.
const int NUM_PORTS = 24
const int WEIGHT_RESOLUTION = 256;
Die mit den Zuteilerausgangsports assoziierten Variablen sind als Mitglieder des Strukts ARB_OUTPUT_PORT dargestellt: Dies sind der Siegereingangsport, a out / i, s out / i, p out / i und die Blockfluidlänge.
Die mit dem Zuteilereingangsport assoziierten Variablen sind als Mitglieder des Strukts ARB_INPUT_PORT dargestellt: Dies sind die boolesche Variable zum Anzeigen, ob der Eingangsport freigegeben ist oder nicht. Der Eingangsport wird gesperrt, wenn die Zellenwarteschlange am Eingang des asynchronen Crosspoint-Switch ihren Schwellenwert übersteigt oder wenn die Grant-Warteschlange ihren Schwellenwert übersteigt. Der Siegerausgangsport a in / i und s in / i.
Die mit dem Zuteilerein-/-ausgangsportpaar assoziierten Variablen sind als Mitglieder des Strukts ARB_INOUT_PORT dargestellt: Dies sind w hp / ij, w lp / ij, die Zahl der durch den Ausgangsport zum Eingangsport angeforderten (Niederprioritäts-) Fluidzellen f hp / ij, p hp / ij, f lp / ij, und p lp / ij.
Die Datenstruktur des Zuteilers besteht aus einer eindimensionalen Reihe von ARB_INPUT_PORT und ARB_OUTPUT_PORT mit Länge NUM_PORTS. Sie enthält auch eine zweidimensionale Matrix NUM_PORTS x NUM_PORTS von ARB_INOUT_PORT.
Eine Schnittstelle zum Zuteiler besteht aus Mitgliedsfunktionen zum Festlegen von Gewichtungen für die Flüsse, Informieren des Zuteilers über Zellenankünfte zum VOQ, Freigeben/Sperren von Eingangsports, Freigeben/Sperren von Ausgangsports, Informieren des Zuteilers über die asynchrone Bandbreite jedes Ports und Funktionen zum Berechnen des Siegerausgangsports für jeden Eingangsport. Der Zuteiler besteht auch aus mehreren Private-Member-Funktionen, die nach den Public-Member-Funktionen benannt sind. Diese Funktionen werden später beschrieben, wenn die Public-Member-Funktionen beschrieben werden.
Das Festlegen der Gewichtung eines Flusses (auch "Ein-Ausgangsfluss" genannt) kann über eine Public-Member-Funktion set_weight() erfolgen, die einfach die geeignete Gewichtungsvariable des Zuteilers initialisiert.
Das Informieren des FFTA über Zellenankünfte am VOQ kann wie folgt erfolgen.
Es gibt zwei Zellenankunftstypen. Eine gewöhnliche Ankunft inkrementiert den Anforderungszähler des Ein-Ausgangspaares, während eine außergewöhnliche Ankunft, die den Zuteiler über eine externe Zellenankunft informiert (Zellenankunft am passenden Port eines überbrückten VC) verwendet wird, um die Blockfluidlänge des Ausgangsports zu inkrementieren.
Wenn eine Zelle an den Multicast-Flüssen ankommt, dann wird die folgende Funktion zum Einführen von Blockfluid in alle Ausgangsports der ankommenden Multicast-Zelle verwendet.
Mit der folgenden Member-Funktion wird der vorgegebene Eingangsport freigegeben oder gesperrt. Wenn ein Eingangsport gesperrt ist, dann erzeugt der Zuteiler keine Grants für den Eingangsport. Feedback vom Crosspoint-Switch:
Die folgende Member-Funktion dient zum Freigeben oder Sperren des vorgegebenen Ausgangsports. Das Sperren des Ausgangsports inkrementiert einfach die Blockfluidlänge des Ausgangsports, wodurch die Gewährung von Niederprioritätszellen behindert wird.
Informieren des Zuteilers über die Portgeschwindigkeit
Die folgende Member-Funktion dient zum Festlegen der Service-Grenze a in / i des Eingangsports. Wie bereits erwähnt, ist dies proportional zur Anzahl der dem Eingangsport zugeordneten asynchronen Kanäle.
Die folgende Member-Funktion dient zum Festlegen der Service-Grenze a out / i des Ausgangsports. Wie bereits erwähnt, ist dies proportional zur Anzahl der dem Ausgangsport zugeordneten asynchronen Kanäle.
Zurücksetzen des Zuteilers
Mit der folgenden Funktion wird der Zuteiler zurückgesetzt. Er initialisiert alle relevanten Variablen des Zuteilers.
Die folgende Funktion dient zum Berechnen der Grants. Der Anrufer sendet einen Zeiger zu einer Array von Ausgangsports und einen Zeiger zu einer Array von booleschen Werten. Die Funktion berechnet den Siegerausgangsport für jeden der Eingangsports und ob der Sieger hohe Priorität hat oder nicht. Diese Funktion wird in jedem INTER_ARBITERATION_INTERVAL (z.B. alle 12 Zyklen oder 10 Zyklen je nach Implementation) aufgerufen und das Ergebnis dient zum Senden von Grants zum VOQC. Die Funktion arbeitet wie folgt: Zunächst wird mit der Private-Member-Funktion update_fluid_q_lens() die geeignete Menge an Fluidzellen von den Eingangsports zu den Ausgangsports übertragen. Dann wird mit der Private-Member-Funktion find_output_port() der Siegerausgangsport für jeden Eingangsport ermittelt. Wenn es keine Siegerausgangsports für einen Eingangsport gibt, dann wird dies mit -1 angezeigt. Wenn es Siegerausgangsports für einen Eingangsport gibt, dann wird die Anzahl der Anforderungen um eins dekrementiert.
Der Zuteiler arbeitet wie folgt:
Die Private-Member-Funktion update_fluid_q_lens() wird nachfolgend dargestellt. Sie ruft eine Serie von weiteren Private-Funktionen ab. Zunächst wird die init_service() Funktion aufgerufen, um s in / i und s out / i auf 0 für alle Ein- und Ausgangsports zu initialisieren. Dann wird die Funktion transferhp_fluid() zum Übertragen von Hochprioritätsfluid von den Eingangsports zu den Ausgangsports aufgerufen. Die Funktion add_block_fluid() dient zum Füllen des restlichen a out / i mit Blockfluid. Schließlich werden die Funktionen make_lp_request() und serve_lp_request() mit einigen Iterationen aufgerufen, um eventuelle Restteile von a out / i mit Niederprioritätsfluid zu füllen.
Die Übertragung von Fluid von Eingangseinheiten zu den Ausgangseinheiten erfolgt folgendermaßen:
Die Funktion init_service() dient zum Initialisieren von s in / i und s out / i auf 0.
Übertragen von Hochprioritätsfluid
Die Funktion transfer_hp_fluid() überträgt einfach eine Menge Delta vom i-ten Eingangsport zum j-ten Ausgangsport und aktualisiert die Variablen s in / i, s out / i und f hp / ij. Delta ist einfach gleich w hp / ij. Da Delta jedoch f hp / ij nicht übersteigen kann, wird Delta (a out / i – p out / i – s out / i), (a in / i – s in / i) auf gleich das Minimum dieser vier Größen gesetzt.
Die Funktion add_block_fluid() überträgt Blockfluid zum verbleibenden a out / i. Das heißt, die Ausgangsservicegrenze wird zuerst mit dem Hochprioritätsfluid gefüllt, dann mit Blockfluid, und eventuell verbleibende Teile werden wie gezeigt mit Niederprioritätsfluid gefüllt. Wenn also eine ausreichende Menge Blockfluid im Ausgangsport vorhanden ist, dann gibt es keinen Platz für das Niederprioritätsfluid. Dies bedeutet, dass das Niederprioritätsfluid vom Eingangsport mit einer geringeren Geschwindigkeit abgegeben wird und daher ist die Rate geringer, mit der die Grants zum Niederprioritäts-VOQ ausgegeben werden. Wie bereits angedeutet, wird der Feedback-Mechanismus vom Ausgangsport des asynchronen Switch zum Inkrementieren des Blockfluids des Zuteilerausgangsports verwendet.
Wenn das Blockfluid in das Servicekontingent des Zuteilerausgangsports eingegangen ist, wird eventuell verbleibender Raum mit Niederprioritätsfluid gefüllt. Man betrachte den i-ten Ausgangsport. Sein verbleibender Raum (a out / i – p out / i – s out / i) wird unter den wählbaren Eingangsports proportional zu deren Niederprioritätsgewichtungen aufgeteilt. Ein Eingangsport ist dann wählbar, wenn er freigegeben ist, für den i-ten Ausgangsport bestimmte Fluidzellen hat und sein Servicekontingent noch nicht aufgebraucht ist: a in / i > s in / j. Die Außenschleife der Member-Funktion make_lp_request() iteriert durch jeden der Ausgangsports. Die erste innere Schleife der Funktion berechnet die Summe der Niederprioritätsgewichtungen über alle wählbaren Eingangsports: die Summe der Gewichtungen für die i-ten Ausgangsport ist
, wobei E_i der Satz an wählbaren Eingangsports für den i-ten Ausgangsport ist. Die zweite innere Schleife berechnet die Anzahl an Fluidzellen zum Anfordern jedes Eingangsports. Die Fluidmenge, die vom i-ten Ausgangsport zum j-ten Eingangsport angefordert wurde, r_ij, ist
Wenn jedoch der j-te Eingangsport gesperrt ist oder kein Niederprioritätsfluid hat oder wenn das Servicekontingent der Eingangsports aufgebraucht ist, dann ist der angeforderte Betrag 0.
Die Member-Funktion serve_lp_request() iteriert durch jeden der Zuteilereingangsports und berechnet die Menge an Fluid, die zu den anfordernden Ausgangsports gesendet werden soll. Wie bei der Funktion make_lp_request(), berechnet die erste innere Schleife die Summe der Niederprioritätsgewichtungen über alle Ausgangsports mit Nicht-Null-Anforderungen zu diesem Eingangsport. Die zweite innere [Schleife] berechnet die Menge an Niederprioritätsfluid, die zu den Ausgangsports zu senden ist. Die äußere Schleife in serve_lp_request() kann zum Füllen eventueller verbleibender Anforderungen wiederholt werden.
Die Funktion find_output_port() berechnet den Siegerausgangsport und die Priorität für jeden Eingangsport. Der Siegerausgangsport ist der Port mit der größten Differenz zwischen der Zellenwarteschlange und der Fluidwarteschlange. Die Variable max_diff verfolgt die maximale Differenz. Man beachte, dass ein Ausgangsport nur dann in Betracht gezogen wird, wenn die Differenz zwischen der Zellenwarteschlange und der Fluidwarteschlange größer ist als ein positiver Schwellenwert. Der Schwellenwert ist proportional zum Index des Eingangsports. Der Grund für diese gestaffelte Freigabe ist, Grant-Bündel für einen Eingangsport minimal zu halten.
Gleitpunktgrößen können im FFTA wie folgt vermieden werden. In dem oben beschriebenen Algorithmus werden idealerweise Gleitpunktvariablen für die Gewichtungen und Fluidzähler verwendet. Die resultierenden Hardware-Kosten können jedoch durch Verwenden von ganzzahligen Größen mit ausreichender Auflösung vermieden werden. Eine geeignete Auflösung ist 256 oder 8 Bits. Somit ist die kleinste zuweisungsfähige Hochprioritätsbandbreite 1/256 der OC48-Rate = 10 Mbit/sec.
Die Hardware-Struktur des FFTA ist in 4 dargestellt. Sie besteht aus einer kompletten Verbindung von 24 Eingangseinheiten mit 24 Ausgangseinheiten. Die Schnittstellen der Ein- und Ausgangseinheiten sind in 3 dargestellt. Die Niederprioritäts-Fluidtransferiterationen können wie folgt erfolgen: Die i-te Eingangseinheit legt das Ready-Signal an, wenn es freigegeben ist, wenn es für den Ausgangsport bestimmte Fluidzellen hat und wenn seine Service-Menge s in / i < a in / i beträgt. Die j-te Ausgangseinheit berechnet die Anforderungsmenge und fordert die Eingangseinheiten an, die bereit sind. Die Eingänge berechnen die zugeführte Menge und informieren die Ausgangseinheiten, die eine Nicht-Null-Anforderung gemacht haben. Wie zuvor erwähnt, übersteigt die zugeführte Menge die angeforderte Menge nicht und übersteigt auch die Menge des aktuellen Fluidrückstands nicht. Eine Eingangseinheit mit anliegendem Sperrsignal legt das Ready-Signal nicht an. Ebenso wird eine Ausgangseinheit mit anliegendem Sperrsignal keinen Service anfordern. Die Sperrsignale werden vom asynchronen Crosspoint-Switch auf eine Weise ähnlich dem aktuellen Zuteiler angelegt. Der Phaseneingang zu den Ein- und Ausgangseinheiten informiert, welche Phase des Algorithmus die aktuelle Phase ist.
Zum Berechnen der Anforderungsmenge in einem Taktzyklus braucht jede Ausgangseinheit 24 8-Bit-Vervielfacher und einen einzelnen Teiler. Ebenso braucht auch die Eingangseinheit 24 8-Bit-Vervielfacher und einen einzelnen Teiler. (Diese Vervielfacher können möglicherweise gemeinsam genutzt werden, da sie nicht gleichzeitig rechnen.)
Die Vervielfachereinheit berechnet die 8-Bit-Größe r (Anforderung) von den drei 8-Bit-Größen f (freier Betrag), w (Gewichtung) und s (Summe der Gewichtungen). Diese Größen erfüllen die folgenden Einschränkungen:

1. 0 ≤ w ≤ s
2. s > 0
3. 0 ≤ r ≤ 2⁸

Wenn die Eingänge eine oder mehrere der obigen Einschränkungen verletzen, können die Ausgänge auf „Egal"-Werte gesetzt werden. Diese Egal-Werte können zum Minimieren der Logik der Vervielfacher-/Dividiereinheit verwendet werden (mit einem Quine-McClusky-Algorithmus). Jede Ein- und Ausgangseinheit des Zuteilers braucht 24 solcher Vervielfacher-/Dividiereinheiten (keine gemeinsame Nutzung angenommen).
Zum Unterstützen von Bridging und Multicasting braucht jeder Eingangsport zusätzliche Logik zum Verfolgen der Ausgangsports, zu denen eine Kopie der Zellen gesendet wurde. Der Eingangsport muss die Routing-Map halten können und muss die Bits löschen, wenn Kopien des Kopfes der Leitungszelle zu ihren Ausgangsports gesendet werden. Wie zuvor, arbeitet der Round-Robin-Scheduler jedes Ausgangsports unabhängig. Wenn mehr als ein Ausgang einen Eingangsport wählt, dann wählt der Eingangsport eine Teilmenge der Ausgangsports, für die die HOL-(Head of the Line)-Zelle bestimmt ist, und sendet Kopien der HOL-Zelle gleichzeitig zur Teilmenge der Ausgangsports.
Addendum C
In einer speziellen Implementation hat ein Zuteiler des hierin beschriebenen Typs 24 Eingangseinheiten und 24 Ausgangseinheiten und verfolgt die Länge jedes der 24 × 24 = 576 VOQs mit 576 Zählern für jede Priorität. Da der Zuteiler zwei Prioritäten unterstützt (auch QoS-Klassen genannt), verwendet der Zuteiler 1152 Register zum Verfolgen der VOQ-Längen. Mit Hilfe der Gewichtungen bietet der Zuteiler lineare Bandbreitenregulierbarkeit. Für Hochprioritätsflüsse darf die von dem Fluss empfangene Bandbreite niemals kleiner sein als die vorgegebene Bandbreite. Die Hochprioritätsflüsse sind niemals überbucht. Für die Niederprioritätsflüsse ist die von einem Fluss empfangene Bandbreite proportional zur vorgegebenen Bandbreite (in Form von Gewichtungen). Wenigstens zwei Unicast-QoS-Klassen können in einer solchen Implementation unterstützt werden. Inklusive Multicast/Bridging werden die folgenden Klassen unterstützt: a) Multicast/Bridge mit garantierter Bandbreite und Verzögerung, b) garantierte Unicast-Bandbreite und Verzögerung und c) gewichtete Unicast-Best-Effort. Ferner wird wenigstens Zweiweg-Überbrückung (Multicast) von nicht unbedingt benachbarten Ports zur Erzielung von Redundanzunterstützung bereitgestellt. Speziell, Zweiweg-Überbrückung wird zum Unterstützen von UPSR (Unidirectional Path Switched Ring) benötigt. Der Zuteiler ist auf höhere Geschwindigkeiten skalierbar: eine Ausgestaltung hat Schaltkapazität von 50 Gbit/sec, eine andere von 200 Gbit/sec. Der Arbiter hat geringe Hardware-Komplexität und niedrige Leistungsanforderungen, weil er implementierbar ist in: a) 0,13 Mikron ASIC-Prozess oder kleiner, mit b) maximaler Kerntaktfrequenz <= 155 MHz, und c) Chipfläche < 14 mm².
Diese Implementation des Zuteilers wird mit einer passiven Backplane verwendet, über die die Leitungskarten (Ein- und Ausgangsports) und Switch-Fabric-Karten (Zuteiler und Crossconnect) montiert sind. Die Backplane enthält keine aktiven Komponenten, um die Wahrscheinlichkeit zu reduzieren, dass dies ein einzelner Fehlerpunkt sein kann. Die Leitungskarten enthalten die Ingress- und Egress-Netzwerkprozessoren, die Aufgaben wie Strategiefestlegung, VC-(Per-Virtual Connection)-Queuing, Per-VC-Kontenführung, Planung und Gestaltung ausführen. Im Falle von VOQ-(Virtual Output Queued)-Switches enthalten die Leitungskarten auch die Eingangspuffer, die virtuelle Ausgangswarteschlangen (VOQs) implementieren, und Steuerungen für die VOQs, die mit dem Zuteiler kommunizieren, um die Ankunft von Datenverkehr anzuzeigen und Grants für den Transfer des Datenverkehrs zu empfangen.
Speziell, der Zuteiler und der Crosspoint-Switch werden in die Switch-Fabric-Karte gesetzt. Die physische Trennung des Zuteilers und der VOQs hat wichtige Auswirkungen auf das Switch-Design. Die Kommunikation über die Backplane ist kostspielig, weil diese Signale durch Hochstromtransceiver angesteuert werden müssen, um Signalverschlechterungen zu reduzieren. Daher sind die Verbindungen zwischen den Leitungseinheiten und der Switch-Fabric nur ein paar serielle Verbindungen und es gibt etwas Verzögerung. Wenn die Zuteiler-Grants zum direkten Steuern des Crosspoint-Switch verwendet werden, dann kann die Verzögerung den Durchsatz des Switch reduzieren.
Eine Lösung dieses Problems besteht darin, ein Crossconnect des in 1A gezeigten Typs mit einem oder mehreren Round-Robin-Scheduler zu erweitern. Wie in 1A gezeigt, befinden sich kleine FIFOs an den Ein- und Ausgangsports des Crosspoint-Switch. In der erweiterten Version des Crossconnect beinhaltet der Satz von zwischen einer Eingangseinheit und einer Ausgangseinheit ausgetauschten Signalen die folgenden drei Signale. Ein Zelle-verfügbar-Signal von der Eingangseinheit informiert die Ausgangseinheit darüber, dass die HOL-Zelle in ihrem FIFO für die Ausgangseinheit bestimmt ist. Ein Auswahlsignal von der Ausgangseinheit informiert die Eingangseinheit, dass die Ausgangseinheit die Eingangseinheit gewählt hat. Ein Multi-Bit-Zellenbus im Crossconnect von der Eingangseinheit zur Ausgangseinheit überträgt die Zelle.
Jede Ausgangseinheit eines solchen erweiterten Crossconnect hat auch einen einfachen unabhängigen Scheduler, der die Eingangseinheiten, bei denen das Zelleverfügbar-Signal anliegt, auf Round-Robin-Weise bedient. Ein Zuteiler des oben beschriebenen Typs steuert ein solches erweitertes Crossconnect nicht direkt. Der Zuteiler empfangt einfach Anzeigen von Zellenankünften von VOQs in der Leitungseinheit und gibt Grants dazu aus. Daher wird der Zuteiler mit dem erweiterten Crossconnect „lose gekoppelt". Der Zuteiler empfangt nur Signale von dem erweiterten Crossconnect, die die Füllstände der FIFOs anzeigen. Wenn die FIFO-Stände einen eingestellten Schwellenwert übersteigen, dann verlangsamt der Zuteiler die Ausgabe von Grants zu den überfüllten Ports. Die lose Kopplung eines Zuteilers des hierin beschriebenen Typs mit einem Crossconnect, der mit Round-Robin-Schedulern erweitert ist, funktioniert in der Praxis sehr gut. Wie an anderer Stelle hierin erwähnt, kann anstatt eines Crossconnect ein beliebiger anderer Switch mit einem solchen Zuteiler verwendet werden, und ein solcher anderer Switch kann wie oben beschrieben erweitert werden.

Claims

Verfahren zum Übertragen von Datenverkehr durch einen Switch mit einer Mehrzahl von Eingangsports und einem Ausgangsport, wobei das Verfahren die folgenden Schritte beinhaltet: Inkrementieren (141) eines Paares (123) von Zählern für einen Datenverkehrsfluss (A) von einem Eingangsport (102I) zu einem Ausgangsport (103) als Reaktion auf den Empfang von Datenverkehr am Eingangsport (102I); Dekrementieren (142) eines ersten Zählers in dem Paar Zählern für jeden Fluss (A), wenn der erste Zähler ungleich null ist; Auswählen (143) eines Eingangsports (102) als Siegerport wenigstens teilweise auf der Basis von Werten von Zählern in dem Paar für wenigstens einen Fluss von dem Eingangsport (102); und Erzeugen eines Signals zum Übertragen einer Datenverkehrsmenge von dem Siegereingangsport zum Ausgangsport, dadurch gekennzeichnet, dass eine Differenz zwischen der Rate, mit der Datenverkehr tatsächlich übertragen wird, angezeigt durch den zweiten Zähler in dem Paar, und der Rate ermittelt wird, mit der Datenverkehr idealerweise übertragen werden sollte, angezeigt durch den genannten ersten Zähler in dem Paar, wobei die genannte Differenz zum Identifizieren eines Siegerflusses verwendet wird.
Verfahren nach Anspruch 1 zum Übertragen von Datenverkehr durch einen Switch mit einer Mehrzahl von Eingangsports und einer Mehrzahl von Ausgangsports, wobei das Verfahren ferner das Auswählen (143) eines der Flüsse am Eingangsport wenigstens teilweise auf der Basis von Werten von Zählern in dem Paar für jeden Fluss von dem Eingangsport zu einem der Ausgangsports beinhaltet.
Verfahren nach Anspruch 2, wobei das Dekrementieren (142) des ersten Zählers wenigstens teilweise auf einer vorbestimmten Bandbreitenanforderung, Gewichtung genannt, des Flusses basiert.
Verfahren nach Anspruch 2 oder 3, das ferner die folgenden Schritte beinhaltet: Dekrementieren des zweiten Zählers entsprechend dem Siegerausgangsport des Eingangsports; periodisches Wiederholen der genannten Aktion des Dekrementierens des ersten Zählers, es sei denn, dass der erste Zähler null ist; wenn ein vorbestimmtes Kriterium von Zählern in einem Paar für wenigstens einen Fluss vom Eingangsport während einer Periode erfüllt wird, Wiederholen der genannten Aktion des Auswählens, Wiederholen der genannten Aktion des Erzeugens, es sei denn, dass der zweite Zähler null ist, und Wiederholen der genannten Aktion des Dekrementierens des zweiten Zählers.
Verfahren nach Anspruch 4, wobei das vorbestimmte Kriterium für das Paar Zähler (123) beinhaltet, dass der erste Zähler gleich oder niedriger ist als der zweite Zähler.
Verfahren nach Anspruch 4, wobei das vorbestimmte Kriterium für das Paar Zähler (123) beinhaltet, dass der erste Zähler um einen Betrag geringer ist als der zweite Zähler, der auf einer Identität des Eingangsports (102) basiert.
Verfahren nach einem der vorherigen Ansprüche, wobei: der genannte Fluss (A) einer aus einer Mehrzahl von Flüssen zwischen dem genannten Eingangsport (102) und dem genannten Ausgangsport (103) ist; jeder Fluss (A) mit wenigstens zwei Zählern assoziiert ist; und die genannten Schritte des Inkrementierens (141), Dekrementierens (142) des ersten Zählers, Wählens und Erzeugens wenigstens einmal für jeden Fluss (A) ausgeführt werden.
Verfahren nach Anspruch 7, wobei: der genannte Ausgangsport (103) einer aus einer Mehrzahl von mit dem genannten Eingangsport (102) gekoppelten Ausgangsports ist; und der Siegerausgangsport des Eingangsports (102) nur dann gewählt wird, wenn eine Differenz zwischen Zählern für einen der Flüsse zum Siegerausgangsport das Maximum unter Differenzen zwischen Zählern für alle Flüsse aller Ausgangsports (103) ist.
Verfahren nach Anspruch 7, wobei: der genannte Ausgangsport (103) einer aus einer Mehrzahl von mit dem genannten Eingangsport gekoppelten Ausgangsports ist; und der Siegerausgangsport des Eingangsports (102) nur dann gewählt wird, wenn eine Differenz zwischen Zählern für einen der Flüsse (A) zum Siegerausgangsport das Maximum unter Differenzen zwischen Zählern für Flüsse aller Ausgangsports ist, die ein vorbestimmtes Kriterium erfüllen.
Verfahren nach Anspruch 7, wobei: die Mehrzahl von Flüssen wenigstens einen Hochprioritätsfluss und einen Niederprioritätsfluss umfasst; und das Verfahren ferner das Unterhalten eines Zählers beinhaltet, der eine „benutzte Eingangsportbandbreite" für den Eingangsport definiert, die die Gesamtdekremente in einer Periode in dem ersten Zähler jedes Flusses zwischen dem Eingangsport und allen Ausgangsports einschließlich dem genannten Ausgangsport anzeigt; und wobei das Verfahren ferner die Verwendung einer Differenz beinhaltet, die „eine Eingangsportrestbandbreite" zwischen der benutzten Eingangsportbandbreite und einer vorbestimmten Eingangsportbandbreite zum Übertragen von Datenverkehr in den Niederprioritätsflüssen von dem Eingangsport definiert.
Verfahren nach Anspruch 10, wobei die Mehrzahl von Flüssen nur aus dem Hochprioritätsfluss und dem Niederprioritätsfluss besteht und wobei das Verfahren ferner die folgenden Schritte beinhaltet: Erzeugen eines Signals, „Bereitschaftssignal" genannt, das die Bereitschaft zum Übertragen von Datenverkehr vom Eingangsport zum Ausgangsport anzeigt, wenn der erste Zähler des Niederprioritätsflusses ungleich null ist und wenn die Eingangsportrestbandbreite ungleich null ist.
Verfahren nach Anspruch 11, das ferner die folgenden Schritte beinhaltet: Unterhalten eines Zählers, der eine „benutzte Ausgangsportbandbreite" für jeden Ausgangsport definiert, die eine Summe von Dekrementen im ersten Zähler jedes Flusses zwischen dem genannten Ausgangsport und allen Eingangsports einschließlich dem genannten Eingangsport anzeigt; und Verwenden einer Differenz, die eine „Ausgangsportrestbandbreite" zwischen der benutzten Ausgangsportbandbreite und einer vorbestimmten Ausgangsportbandbreite zum Übertragen von Datenverkehr in den Niederprioritätsflüssen zum Ausgangsport definiert.
Verfahren nach Anspruch 12, das ferner das Anzeigen einer Menge beinhaltet, die die „angeforderte Menge" von Datenverkehr von einem Niederprioritätsfluss zum Ausgangsport von jedem Eingangsport definiert, wenigstens teilweise auf der Basis der Ausgangsportrestbandbreite.
Verfahren nach Anspruch 13, wobei die angeforderte Menge von einem Ausgangsport zum Eingangsport durch proportionales Zuordnen der Ausgangsportrestbandbreite unter den Niederprioritätsflüssen auf der Basis der Gewichtungen der Niederprioritätsflüsse erhalten wird.
Verfahren nach Anspruch 14, das ferner das Anzeigen einer Menge beinhaltet, die die „erledigte Menge" an Datenverkehr von einem Niederprioritätsfluss vom Eingangsport zum Ausgangsport wenigstens teilweise auf der Basis von (a) der Eingangsportrestbandbreite, (b) der angeforderten Menge und (c) der Gewichtung des Niederprioritätsflusses vom Eingangsport definiert.
Verfahren nach Anspruch 15, das ferner das Wiederholen der Aktionen von (a) dem Erzeugen des Bereitschaftssignals, (b) dem Anzeigen der angeforderten Menge und (c) dem Anzeigen der erledigten Menge beinhaltet.
Verfahren nach einem der vorherigen Ansprüche, wobei der erste Zähler eine höhere Auflösung hat als der zweite Zähler.
Vorrichtung, die Folgendes umfasst: einen Kommunikationsswitch, der einen Puffer zum Halten von Datenverkehr an einem Eingangsport umfasst, der für einen Ausgangsport bestimmt ist; und e in mit dem Kommunikationsswitch gekoppeltes rechnerlesbares Speichermedium, wobei das rechnerlesbare Speichermedium die Aufgabe hat, ein Computerprogramm zu speichern, das ein Paar Zähler für den Puffer aufweisen kann; und eine Zustandsmaschine mit der Aufgabe, automatisch das Paar Zähler (123IJ) als Reaktion auf den Empfang von Datenverkehr am Eingangsport (102) zu inkrementieren (141), mit der Aufgabe, einen ersten Zähler in dem Paar Zählern für jeden Fluss (A) zu dekrementieren, wenn der erste Zähler ungleich null ist, und die Aufgabe hat, einen Eingangsport (102) wenigstens teilweise auf der Basis von Werten von Zählern in dem Paar für wenigstens einen Fluss vom Eingangsport (102) auszuwählen, dadurch gekennzeichnet, dass die Zustandsmaschine die Aufgabe hat, eine Differenz zwischen der Rate, mit der Datenverkehr tatsächlich übertragen wird, angezeigt durch einen zweiten Zähler in dem Paar, und der Rate zu ermitteln, mit der der Datenverkehr idealerweise übertragen werden sollte, angezeigt durch den ersten Zähler in dem Paar, wobei die genannte Differenz einen Siegerfluss identifizert.
Vorrichtung nach Anspruch 18, wobei die Zustandsmaschine den ersten Zähler in dem genannten Paar wenigstens teilweise auf der Basis einer vorbestimmten Bandbreite zwischen dem Eingangsport (102) und dem Ausgangsport (103) dekrementiert (142).
Vorrichtung nach Anspruch 19, wobei das rechnerlesbare Speichermedium ferner Folgendes umfasst: einen dritten Zähler (121AA) von Gesamtdekrementen in dem genannten ersten Zähler jedes Flusses zwischen dem Eingangsport und allen Ausgangsports einschließlich dem genannten Ausgangsport; und einen vierten Zähler (122AA) für jeden Ausgangsport, der eine Summe von Dekrementen im ersten Zähler jedes Flusses (A) zwischen dem genannten Ausgangsport (103J) und allen Eingangsports (102IJ) einschließlich des genannten Eingangsports (102I) anzeigt.