DE69429773T2

DE69429773T2 - Zellenvermittlung und verfahren zur weglenkung von zellen durch diese vermittlung

Info

Publication number: DE69429773T2
Application number: DE69429773T
Authority: DE
Inventors: Waldemar Sandquist
Original assignee: Telefonaktiebolaget LM Ericsson AB
Current assignee: Telefonaktiebolaget LM Ericsson AB
Priority date: 1993-06-23
Filing date: 1994-06-17
Publication date: 2002-08-14
Anticipated expiration: 2014-06-18
Also published as: BR9406843A; SE9302176L; NO955275D0; KR100237337B1; NO955275L; US5506841A; CN1073316C; EP0705511B1; AU7088794A; FI956242A0; SE515148C2; DE69429773D1; TW256980B; EP0705511A1; WO1995001031A1; FI956242A; KR960703299A; JPH08512179A; SE9302176D0; CN1126012A

Description

Technisches Gebiet der Erfindung

Die vorliegende Erfindung bezieht sich auf eine Zellenvermittlung, welche eine Vielzahl von Vermittlungsanschlüssen umfasst, wobei jeder mit einer Anzahl von Benutzerendgeräten verbunden ist, um Zellen der Benutzerendgeräte zu senden und zu empfangen, wobei die Zellen Nutzlast- und Adresseninformation enthalten, einen Vermittlungskern, welcher die Vermittlungsanschlüsse verbindet, um eine Kommunikation zwischen ihnen zu ermöglichen, ein Markierungsmittel in den Vermittlungsanschlüssen, um auf der Grundlage der Adresseninformation einer von einem Benutzerendgerät empfangenen Zelle eine Marke zu erzeugen, welche zu der Zelle gehört und Wegleitungs- bzw. Routing-Information enthält, die das Routing der Zelle durch den Vermittlungskern ermöglicht.
Die Erfindung bezieht sich ferner auf ein Verfahren für das Routing von Zellen durch eine Zellenvermittlung, welche eine Vielzahl von Vermittlungsanschlüssen umfasst, wobei jeder mit einer Anzahl von Benutzeranschlüssen verbunden ist, zum Senden und Empfangen von Zellen der Benutzerendgeräte, wobei die Zellennutzlast- und Adresseninformation enthalten, einen Vermittlungskern, der die Vermittlungsanschlüsse verbindet, um eine Kommunikation zwischen Ihnen zu gestatten.

Beschreibung des Standes der Technik

In einer Vermittlung der oben angegebenen Art können Zellenpuffer angeordnet sein, um ein Verlust von Zellen zu vermeiden, die gleichzeitig bei der Vermittlung ankommen und eine den Zellen gemeinsame Ressource passieren, zum Beispiel einen Ausgang. In bekannten Systemen müssen Zellenpuffer zur Lösung dieser Aufgabe im Vermittlungskern befindlich sein. Um eine hohe Effizienz zu erreichen, ist daher eine große Zahl von Zellenpuffern im Vermittlungskern erforderlich.
Indem Zellenpuffer nur in den Vermittlungsanschlüssen lokalisiert wären, könnte die Größte des Kerns und dadurch seine Kosten verringert werden. Dies wäre insofern vorteilhaft, dass geringe Kosten für den Vermittlungskern die Gesamtkosten für skalierbare Systeme verringern, welche mit nur einer geringen Zahl von Anschlüssen konfiguriert wurden. Die Vermittlungskosten wären somit modularer.
Ein Problem ist jedoch, wie ein Konflikt im Vermittlungskern vermieden werden kann, so dass die Notwendigkeit von Zellenpuffern im Kern beseitigt werden könnte.
US 4,817,084 offenbart eine Schiedsprozedur zur Vermeidung eines Konflikts in den Ausgangsanschlüssen einer Paketvermittlung der "Batcher-Bunyan"-Art. In einer ersten Phase wird für jedes Paket eine Anforderung bzw. Request geschickt, betreffend die Frage ob das Paket an seinen Zielanschluss in einer folgenden dritten Phase geschickt werden kann. Ein Schiedsverfahren wird durchgeführt, während welchem Pakete für das Senden ausgewählt werden, welche an verschiedene Zielanschlüsse adressiert sind. In einer zweiten Phase wird das Ergebnis des Schiedsverfahrens den Anschlüssen mitgeteilt, und in der dritten Phase werden Pakete, welche eine Sendeerlaubnis erhalten haben, geschickt, wohingegen andere Pakete in den Puffern zurückgehalten werden.
Die Zeitplanungsprozedur, auf welche sich die vorliegende Erfindung richtet unterscheidet sich wesentlich von dem oben beschriebenen Schiedsverfahren. Im vorliegenden Fall sollte eine ausdrückliche Sendezeit für jedes Paket zu ein und derselben Zeitplanungsgelegenheit bestimmt werden. Im Fall des Schiedsverfahrens nach US 4,817,084 werden Pakete ausgewählt, welche den Vermittlungskern ohne Konflikt passieren können. Nur für diese ausgewählten Pakete wird die Sendeerlaubnis gegeben, d. h. sie erhalten keine ausdrückliche Sendezeit. Die Pakete, welche in Zusammenhang mit einem Schiedsergebnis keine Sendeerlaubnis erhalten, nehmen an einem oder mehreren folgenden Schiedsverfahren teil, d. h. zu mehreren Schiedsgelegenheiten.
In EP 268,259 wird eine Vermittlung mit einem mehrstufigen Pakettransfer zwischen Vermittlungseingängen und Vermittlungsausgängen beschrieben. Eine Marke identifiziert das Paketziel für das Routing des Pakets an einen geeigneten Ausgang, während Übertragungskonflikte vermieden werden. Eine. Pufferung ist vorgesehen für Pakete, welche aufgrund von Konflikten nicht unmittelbar übertragen werden können, wobei eine Obergrenze eingestellt ist für den Verbleib des Pakets in dem Paketübertragungsnetz.
Die Pakete werden in mehreren Stufen behandelt, und die Marken werden zwischen den Stufen modifiziert, aber die Marken werden nicht im voraus für die Zeitplanung der Sendezeiten der Pakete aus den Eingangsanschlüssen geschickt.
In US 4,630,258 wird ein Paketübertragungsknoten mit einer Anzahl von Eingangs- und Ausgangsanschlüssen beschrieben. Eine einzelne Warteschlange ist mit jedem Eingangsanschluss verbunden, um Pakete zu speichern und an alle Ausgangsanschlüsse zu übertragen. Konflikte können auftreten zwischen Paketen, welche an unterschiedliche Anschlüsse gerichtet sind. Ein Mehranschlussspeicher ist zwischen den Eingangs- und Ausgangsanschlüssen angeschlossen. Eine Steuerlogik ist angeordnet, um unter anderem Pakete an Ausgangsanschlüsse zu übertragen, welche in entsprechenden Routing-Marken identifiziert werden, auf der Grundlage eines vorbestimmten Prioritätsschemas. Eine Pufferlogik führt ein Schiedsverfahren durch bezüglich von Marken, die bei den gleichen Eingangsanschlüssen ankommen und bezüglich des gleichen Ausgangsanschlusses konkurrieren. Ferner wird eine zufällige Wahl von Paketen durchgeführt, welche zum gleichen Ausgangsanschluss gerichtet sind, so dass das Paket nicht während einer unbestimmten Zeit warten muss.
In den Eingangsanschlüssen wird keine Markierung durchgeführt. Existierende Marken folgen den übertragenen Paketen, und werden somit nicht im voraus geschickt.
In US 4,621,359 wird ein Pakettransfer beschrieben, bei dem ein Pakettransferknoten Pakete verarbeitet, welche Routing- Marken enthalten, die Angaben über Ausgangsanschlussziele machen. Das Ziel ist die Bereitstellung eines Gleichgewichts der Zahl von Paketen, welche für jeden der Ausgangsanschlüsse adressiert sind. Neue Marken werden daher erzeugt, um die Ausgangsanschlusslast umzuverteilen. Die neuen Marken werden modifiziert, um ein vorbestimmtes Ausgangsprioritätsschema zu erhalten.
Es gibt kein Vorausschicken von Marken, um ein zeitlich gesteuertes Sendeschema für nachfolgende Pakete bereitzustellen.
In US 4,623,996 wird ein Pakettransferknoten beschrieben, welcher Pakete verarbeitet, die Routing-Marken enthalten, welche eine Angabe über Ausgangsanschlussziele machen. Eine Vielzahl von Wartschlangen-Vermittlungen sind einzeln zwischen einer Vielzahl von Eingangsanschlüssen und einer Vielzahl von Wartschlangen-Sätzen, welche eine Vielzahl von Warteschlangen enthalten, angeschlossen, welche Warteschlangen angelegte Pakete speichern und als Funktion des Ausgangsanschlussziels übertragen. Die Warteschlange jedes Warteschlangen-Satzes sind mit verschiedenen Ausgangs- Schiedsrichtern verbunden, welche das Routing an einen bestimmten Ausgangsanschluss steuern.
Es werden keine Marken im voraus geschickt, um ein zeitlich gesteuertes Sendeschema für folgende Pakete zu erhalten.

ZUSAMMENFASSUNG DER ERFINDUNG

Eine Aufgabe der Erfindung ist die Bereitstellung einer Vermittlung der eingangs genannten Art, welche die zuvor erwähnten Probleme von jener Art vermeidet, wie sie in einer in US 4,817,084 präsentierten Vermittlung auftreten. Dies impliziert unter anderem, dass in der erfindungsgemäßen Vermittlung eine explizite Sendezeit für jedes Paket zu ein und derselben Zeitplanungsgelegenheit bestimmt werden sollte.
Eine weitere Aufgabe ist das Konfliktproblem im Kern auf solche Weise zu lösen, dass die Notwendigkeit von Zellenpuffern intern beseitigt wird. Die erfindungsgemäße Vermittlung umfasst Mittel um Marken an den Vermittlungskern vor entsprechenden Zellen zu schicken. Ein Zeitplanungsmittel ist im Kern vorgesehen, um die im voraus geschickten Marken zu empfangen, und um auf der Grundlage der darin enthaltenen Routing-Information für die jeweiligen Zellen aus den Vermittlungsanschlüssen Zeitplanungsinformation zu schaffen bezüglich einer Sendezeit, zu welcher die Zelle zu den Zielvermittlungsanschlüssen geschickt werden kann, ohne dass ein Konflikt mit anderen Zellen auftritt, für welche eine Zeitplanung bereits stattgefunden hat. Ferner sind Mittel vorgesehen zum Senden der Zeitplanungsinformation an die Ursprungsvermittlungsanschlüsse der Zellen. Ein Verzögerungsmittel hält die Zellen in den Anschlüssen zurück, bis ihre jeweils geplante Sendezeit erscheint, und die Zellen werden dann zu ihren jeweils geplanten Sendezeiten in den Kern geschickt.
Bei dem erfindungsgemäßen Verfahren wird auf der Grundlage der Zielinformation von empfangenen Zellen eine jeweilige Marke für jede empfangene Zelle erzeugt, welche Routing- Information enthält, die ein Routing der Zelle durch den Kern zu einem gewünschten Zielanschluss gestattet. Die Marken werden vor entsprechenden Zellen an den Vermittlungskern geschickt. Beruhend auf der Routing-Information, die in den im voraus geschickten Zellen enthalten ist, wird Zeitplanungsinformation bezüglich der Sendezeiten der jeweiligen Zellen aus den Anschlüssen geschaffen, um eine Zeitplanung während dieser Sendezeiten der zu den Zielanschlüssen zu sendenden Zellen ohne das Auftreten eines Konflikts mit anderen Zellen durchzuführen. Die Zeitplanungsinformation wird an die Ursprungsvermittlungsanschlüsse der Zellen geschickt, welche in den Anschlüssen zurückgehalten werden, bis ihre jeweils geplanten Sendezeiten auftreten.
Erfindungsgemäß wird ein Konflikt somit vermieden, indem die Vermittlungsanschlüsse dem Kern im voraus Routing-Information bereitstellen. Dadurch kann eine geeignete Rückkopplung zu den Anschlüssen erhalten werden, so dass Zellen im voraus geschickt werden können, um ein gleichzeitiges Passieren von gemeinsamen Ressourcen zu vermeiden.
Die Zellen werden mittels von Marken durch den Kern gerichtet. Eine Marke ist eine Routing-Information, welche jeder Zelle vorangeht. Jede Marke enthält Routing- Information, welche nicht in Beziehung steht mit der unmittelbar ankommenden Zelle, sondern mit irgendeiner später folgenden Zelle, womit die Zellen in den Anschlüssen verzögert werden. Eine Verarbeitung der Routing-Information wird im Kern durchgeführt, wonach eine geeignete Zeitplanungsinformation zu den Anschlüssen zurückgekoppelt wird.
Die Zellen werden in angrenzenden Intervallen fester Länge übertragen, welche als Übertragungszyklen bezeichnet werden, und werden durch den Kern geschickt, während Marken verwendet werden, die interne Zellenziele enthalten. Die Zellenziele können auf eine für sich bekannte Weise als Bits in einer Bitabbildung bzw. Bitmapping vorgesehen sein, wodurch eine Zelle mehrere Ziele haben kann (Gruppenadressierung). Die Markierung wird in den Anschlüssen durchgeführt. Jeder Zelle geht eine Marke voraus. Die Marken werden während der Zellenübertragungszyklen aus den Anschlüssen zum Kern übertragen. In der umgekehrten Richtung, das heißt vom Kern zu den Anschlüssen, wird während der Übertragungszyklen anstelle der Marken Zeitplanungsinformation und ein Flag für eine gültige Zelle übertragen.
Die Phasenlage zwischen ankommenden und herausgehenden Übertragungszyklen ist etwas unterschiedlich, so dass eine Zelle in einem Übertragungszyklus von einem Anschluss zum Kern Zeit hat, durch den Kern zu laufen, und kann ohne zusätzliche Verzögerung in einem Übertragungszyklus vom Kern zum Anschluss liegen.
Zellen werden in den Anschlüssen eine bestimmte Mindestzahl von Übertragungszyklen verzögert nachdem entsprechende Marken zum Kern geschickt wurden, so dass Zeit reserviert ist für die Konfliktvermeidungsverarbeitung.
Ein Konflikt wird durch Verteilung der Zellen in der Zeit vermieden. Der Kern führt eine Zeitplanung für alle Zellen durch und informiert die Anschlüsse, so dass die Anschlüsse gezwungen sind die Zellen in bestimmten Übertragungszyklen zu übertragen. Zellen, welche um eine gemeinsame Ressource konkurrieren werden zu unterschiedlichen Übertragungszyklen übertragen. Eine Marke ohne Routing-Information zeigt dem Kern an, dass keine neue Zelle auf eine Zeitplanung wartet. Die erfindungsgemäße Lösung führt zu einem kleinen Kern, welcher innerhalb bestimmter Grenzen unabhängig von der Dimension des Systems sehr kosteneffizient verwendet werden kann. Ferner können von Anfang an kleine Systeme auf einfache Weise erweitert werden, ohne Verlust der ursprünglichen Investition.

KURZE BESCHREIBUNG DER ZEICHNUNGEN

Die Erfindung wird nun ausführlicher unter Bezugnahme auf die angehängten Zeichnungen beschrieben, in welchen
Fig. 1 die Topologie einer Beispiels-Zellenvermittlung veranschaulicht, in welcher die Erfindung verwendet wird,
Fig. 2 eine Marke mit einem Zellen-Routing-Bitmap zeigt,
Fig. 3 das Format der Zeitplanungsinformation zeigt,
Fig. 4 eine Zelle zeigt, die aus einer Kennung und einer Nutzlast besteht,
Fig. 5 die Phasenverschiebung zwischen den Übertragungszyklen für Anschluss-zu-Kern und Kern- zu-Anschluss zeigt, und das Verhältnis zwischen der Marke und der Zeitplanungsinformation, welche mit der Marke in Beziehung steht,
Fig. 6 die Orte einer Marke und ihrer entsprechenden Zelle zeigt, welche um zwei Übertragungszyklen verzögert ist,
Fig. 7 einen Block zeigt, der einen Teil eines Zeitplaners bildet, und die Steuerung der Zeitplanungssequenz und Zeitpriorität,
Fig. 8 eine Zustandsmaschine bzw. State-Machine zeigt, die einen Teil des Zeitplaners bildet und in einem Steuerblock enthalten ist,
Fig. 9 einen Block zeigt, der einen Teil des Zeitplaners bildet und Haltepulse für Speicher für Zeitplanungsdaten erzeugt,
Fig. 10 einen Speicher für ankommende Marken zeigt,
Fig. 11 eine Datenvermittlung zeigt, welche zwischen einer der Zeilen aus dem Speicher für ankommende Marken wählt und sie an den Ausgängen präsentiert,
Fig. 12 eine Schaltung zeigt, die an mehreren Stellen im Speicher für Zeitplanungsdaten enthalten ist,
Fig. 13 ein Beispiel des Speichers für geplante Daten zeigt,
Fig. 14 ein Beispiel eines Konfliktsteuerblocks zeigt,
Fig. 15 den Zeitplaner zeigt, der eine Anzahl der in den Fig. 7 bis 14 gezeigten Blöcke enthält,
Fig. 16 ein Verzögerungsmittel zeigt, welches die Zellen in den Anschlüssen zurückhält und sie in den geplanten Übertragungszyklen zum Kern schickt,
Fig. 17 einen Block zeigt, der in mehreren Instanzen in dem Verzögerungsmittel enthalten ist,
Fig. 18 eine Zustandsmaschine bzw. State-Machine zeigt, welche einen Teil eines Blocks gemäß Fig. 17 eines Verzögerungsmittels in dem entsprechenden Anschluss bildet,
Fig. 19 ein Szenario zeigt, während welchem Zellen über eine Vermittlung der vorgeschlagenen Art unter Verwendung der Erfindung verbunden werden.

AUSFÜHRLICHE BESCHREIBUNG BEVORZUGTER AUSFÜHRUNGEN

Fig. 1 zeigt schematisch eine Art von Zellenvermittlung, in welcher die Erfindung verwendet werden kann.
Die Vermittlung enthält eine Anzahl von Anschlüssen 2.n und einen Vermittlungskern 4 mit einer Zahl von Eingängen 6.n und Ausgängen 8.n. Der Einfachheit halber sind in Fig. 1 nur vier Anschlüsse 2.1-2.4 gezeigt, vier Eingänge 6.1-6.4 und vier Ausgänge 8.1-8.4. Die Anschlüsse 2.n bilden die äußere Schnittstelle der Vermittlung. Eine Vielzahl von Benutzerendgeräten kann mit jedem Anschluss verbunden sein.
Durch zwei entgegengesetzt gerichtete Übertragungskanäle 10.n bzw. 12.n ist jeder Anschluss 2.n mit einem entsprechenden Eingang 6.n bzw. Ausgang 8.n des Vermittlungskerns verbunden.
Als Beispiel kann die Vermittlung von jener Art sein, die Koordinaten vermittelt und nicht blockierend ist, d. h. sie soll in der Lage sein beliebige Kombinationen von Eingängen und Ausgängen gleichzeitig zu verbinden. Die Erfindung ist jedoch nicht auf irgendeine bestimmte innere Struktur der Vermittlung beschränkt.
Zellenpuffer sind erforderlich, um einen Verlust von Zellen aufgrund von Konflikten in den Ausgängen zu vermeiden, d. h. wenn mehrere für den gleichen Ausgangsanschluss bestimmte Zellen zeitlich überlappt zu der Vermittlung geschickt werden.
Nach einem wichtigen Merkmal der Erfindung befinden sich alle Zellenpuffer in den Anschlüssen. Da der Kern keine Zellenpuffer hat, müssen bestimmte Maßnahmen ergriffen werden, um einen Zellenkonflikt zu vermeiden. Dies wird auf eine unten ausführlicher beschriebene Art und Weise durchgeführt, indem die Ankunft der Zellen beim Kern zeitlich geplant wird, und sie so hereingelassen werden, dass ein Konflikt an den Ausgängen des Kerns vermieden wird.
Alle Anschlüsse arbeiten zellensynchron, und die Zellen werden in aneinandergrenzenden Intervallen fester Länge übertragen, welche als Übertragungszyklen bezeichnet werden. Während sie auf ihre jeweiligen Sendezeiten warten, werden die Zellen in Speicherelementen gespeichert. In dem als Beispiel gegebenen System wird angenommen, dass die Zellen eine Form von Adressinformation haben, welche gesammelt und übersetzt wird, indem in Tabellen geschaut wird, nach interner Routing-Information in der Form von Bitmaps, wobei die Positionen der Bits unterschiedliche Ausgänge darstellen. Diese Maps, welche aus der Übersetzungstabelle erhalten werden, werden als Marken bezeichnet, was eine gewähltes Konzept ist. In bekannten System werden die Marken zusammen mit ihren entsprechenden Zellen geschickt, wohingegen im System der vorliegenden Erfindung die Marken und die entsprechenden Zellen getrennt sind.
Fig. 2 zeigt schematisch eine Marke 14 mit einem Zellenziel- Bitmap, mit vier Feldern 14.1 14.4, von welchen in dem gegebenen Beispiel ganz einfach angenommen wird, dass sie jeweils einen der vier Spalten des Vermittlungskerns entsprechen. Jedes Feld kann ein Bit enthalten, welches zum Beispiel nur wenn es auf eins eingestellt ist angibt, dass die entsprechende Zelle die fragliche Spalte als Ziel hat.
Wie unten näher beschrieben wird, werden während jedes Übertragungszyklus aus jedem Anschluss 2.n eine Marke und eine Zelle geschickt, welche einander nicht entsprechen. Die Marke hat die Doppelfunktion der Bereitstellung von Routing- Information an den Vermittlungskern 4, und des Fragens nach einem Übertragungszyklus für die entsprechende Zelle. Der Kern 4 verarbeitet die Anfrage und weist einen Übertragungszyklus zu, der eine Zellenübertragungszeit für den Anschluss 2.n angibt. Der Anschluss wartet diesen Zeitpunkt ab und sendet die Zelle in dem zugewiesenen Übertragungszyklus. Während der Warteperiode können andere Anfragen und Zellen verarbeitet werden.
Wenn die Marken in einem Übertragungszyklus empfangen worden sind, wird der Prozess der Zeitplanung aller verlangten Zellen begonnen. Alle Marken und die entsprechende Zeitplanungsinformation wird gespeichert bis die Zellen geschickt worden sind. Die Zeitplanungsinformation (der zugewiesene Übertragungszyklus), welcher das Resultat des Zeitplanungsprozesse ist, wird während des unmittelbar folgenden Übertragungszyklus aus dem Kern 4 an den fraglichen Anschluss 2.n geschickt.
Fig. 3 zeigt schematisch das Format der Zeitplanungsinformation, welche allgemein mit 15 bezeichnet wird. Die Darstellung ist binär. Die drei letzten der vier gezeigten Felder entsprechen einem Bit b0, b1 bzw. b2, entsprechend dem ersten, zweiten bzw. dritten Bit eines Dreibit-Worts. Eine Null (alle Bits auf Null gesetzt) zeigt an, dass ein Zugriff auf dem Kern nach einer Verzögerung einer vorbestimmten Mindestzahl von Übertragungszyklen gestattet ist. Alle anderen Nummern geben weitere Wartezyklen an. 5 gibt zum Beispiel an, dass die Zelle weitere 5 Übertragungszyklen verzögert werden soll. Während dieser Zeit können Zellen, welche an andere Ausgänge gerichtet sind, übertragen werden. Das erste der vier gezeigten Felder umfasst ein Flag 16 für eine gültige Zelle. Das Flag ist aktiviert, wenn die aus dem Kern 4 an die Anschlüsse 2.n geschickte Zelle gültig ist und keine Leerzelle ist.
Fig. 4 zeigt eine Zelle 17, die aus einem Label bzw. einer Kennung 18 und einer Nutzlast 20 besteht. Die Kennung wird nur interpretiert und wird möglicherweise von einem früheren Protokoll in den Vermittlungsanschlüssen manipuliert. Auf der Grundlage der Kennung wird direkt kein internes Routing durchgeführt.
Fig. 5 zeigt die Phasenverschiebung dt zwischen den Übertragungszyklen für die Zelle 17 mit der Marke 14, welche nicht zu dieser Zelle gehört, in der Richtung vom Anschluss zum Kern bzw. für die gleiche Zelle 17 mit der Zeitplanungsinformation 15, welche der Marke entspricht, in Übereinstimmung mit Fig. 3, und einem Flag 16 für eine gültige Zelle in der Richtung vom Kern zum Anschluss.
Fig. 6 zeigt den Ort einer Marke 14 und ihrer entsprechenden Zelle 17, wenn die Zelle um zwei Übertragungszyklen verzögert ist. In der vorliegenden Erfindung ist dies eine bestimmte Mindestverzögerung.
Wenn die Zellen in Übereinstimmung mit der Zeitplanungsinformation 15 ankommen, werden die aufgewahrten Marken 14 und die Zeitplanungsinformation verwendet, um den Zusammenhang zwischen den Zellen und den Ausgangsanschlusszielen herzustellen.
Der Zeitplaner besteht strukturell aus einer Anzahl von Blöcken, welche in den Fig. 7-14 gezeigt sind, welche entsprechend Fig. 15 verbunden sind.
An seinen Eingängen, welche in Fig. 15 als 21 bezeichnet werden, empfängt der Zeitplaner die aus den Anschlüssen ankommenden Marken - eine aus jedem Anschluss. Diese Marken umfassen Routing-Information und Anfragen nach Übertragungszyklen.
Der Zeitplaner verarbeitet alle solche Anfragen aus den Anschlüssen, eine nach der anderen, während eines Übertragungszyklus. Während die Anfragen eine nach der anderen verarbeitet werden, wird es während eines Übertragungszyklus zunehmend weniger wahrscheinlich, dass herausgehende Übertragungszyklen gefunden werden könne, in welchen kein Konflikt auftreten kann. Aus diesem Grund wird die Reihenfolge der Verarbeitung von Anfragen bei jedem Übertragungszyklus geändert, um Gerechtigkeit zwischen den Anschlüssen zu schaffen.
Der Zeitplaner kümmert sich um alle Marken, welche in kommenden dritten bis sechsten Übertragungszyklen entsprechen. Alle Marken werden an Speicherpositionen gespeichert, die jeweiligen relativen Sendezeiten entsprechen. Während jeder Übertragungszyklus voranschreitet, werden alle Marken in Speicherorte verschoben, welche näherliegenden Planungszeiten entsprechen. Die aus dem Zeitplaner herausgeschobenen Marken werden in FIFOs verschoben, welche nicht abgebildet sind, die die Marken um zwei weitere Übertragungszyklen verzögern, welche die herausgehenden ersten und zweiten Übertragungszyklen umfassen. Während die Zeit vergeht, geben die Speicherorte somit immer den gegenwärtigen Zustand wieder, und somit wie sich die relativen Übertragungszeiten geändert haben.
Der Eingang für das "serielle Laden" des Speicherorts, der Marken enthält, welche dem entferntesten Übertragungszyklus gehören, wird mit "keine Zeitplanung durchgeführt" (Nullen) gespeist. Der Ausgang aus den FIFOs ist eine Abbildung bzw. Map über die Schnittpunkte, welche in jedem Übertragungszyklus aktiviert werden sollen.
Jede ankommende Marke wird im Hinblick auf Marken, für welche bereits eine Zeitplanung stattgefunden hat, bezüglich des Konfliktrisikos überprüft. Die gesamte Verarbeitung einer ankommenden Marke wird gleichzeitig durchgeführt. Vorausgesetzt, dass mindestens ein herausgehender Übertragungszyklus gefunden worden ist, in welchem kein Konflikt auftritt, wird die Marke an dem Speicherort gespeichert, der den frühesten solchen Übertragungszyklus darstellt.
Nach einer vollständigen Sequenz der Verarbeitung aller Marken eines ankommenden Übertragungszyklus, kann die Zeitplanung für einige oder alle diesen Marken entsprechenden Zellen durchgeführt worden sein. Ihre jeweiligen Übertragungszeiten wurden während, der Verarbeitung festgestellt, und werden einer Vorrichtung zugeführt, welche die Übertragung von Zeitplanungsinformation (die Zellenübertragungszeiten) an die Anschlüsse organisiert.
Ein Fehler bei der Zeitplanung einer Zelle kann zum Beispiel angezeigt werden durch Angabe einer relativen Übertragungszeit, welche größer ist als die verfügbare Zahl von Speicherorten, anstelle einer korrekten Übertragungszeit.
Eine Steuerschaltung, welche als Eingangsschaltung des Zeitplaners dient und allgemein als 22 bezeichnet wird, ist in Fig. 7 und 15 gezeigt. Die Steuerschaltung 22 enthält eine Zustandsmaschine 24, welche ausführlich in Fig. 8 gezeigt ist, zusammen mit der untergeordneten Zustandstabelle 26 und dem Zustandsschaubild 28.
Die Steuerschaltung 22 steuert die Zeitplanungssequenz und Zeitplanungs-Zeitpriorität auf eine unten ausführlicher beschriebene Weise.
Unter Bezugnahme auf die Zustandstabelle 26 hat die Zustandsmaschine 24 vier Ruhezustände S05, S15, S25 und S35, in welchen sie empfindlich ist gegenüber einem an einem Eingang START ankommenden Startsignal. Das Startsignal kommt einmal für jeden Übertragungszyklus an, wenn ankommende Marken verfügbar sind. Die Zustandsmaschine 24 führt dann Zähloperationen (Modulo-4) durch, wonach ein Zustand auftritt, indem ein Ausgang SH (für Shift bzw. Verschiebung) aktiv ist. Danach erscheint der nächste Ruhezustand. Während der Zählzustände ist ein Ausgang SC (für Schedule bzw. Zeitplanung) aktiv. Jede der vier Zählsequenzen hat unterschiedliche Startwerte, wie aus der Zustandstabelle hervorgeht.
Ein D-Flipflop 30 empfängt das für die Zustandsmaschine 24 bestimmte Startsignal und synchronisiert es mit einem Zeitgebersignal K, bevor es dem Eingang START der Zustandsmaschine 24 eingegeben wird. Das Zeitgebersignal wird auch einem Invertierer 32 eingegeben, welcher ein gegenphasiges Zeitsignal für den Zeitsignaleingang CLK der Zustandsmaschine. Das Zeitgebersignal wird auch einem Eingang eines UND-Gatters 34 zugeführt, dessen anderer Eingang angeschlossen ist, um das Startsignal zu empfangen, so dass das Gatter 34 an seinem Ausgang 35 ein synchronisiertes Haltesignal für ankommende Marken bereitstellt.
Das Signal SH wird von einem Invertierer 36 (Einbit-Decoder) decodiert. Das decodierte Signal besteht aus dem Signal SH und der Ausgabe aus dem Invertierer 36. Ein Decoder 38, der mit der Zustandsmaschine 24 auf die gezeigte Weise verbunden ist, aktiviert einen seiner Ausgänge Y0-Y3, wenn das Aktivierungssignal an seinem Eingang EN bzw. Freigabe erscheint, welche somit während einer Zählsequenz durchgeführt wird.
Ein Prioritätscodierer 40 codiert das Eingangssignal höchsten Rangs, welches an einem seiner Eingänge P0-P3 aktiviert ist. Ein Ausgangssignal an seinem Ausgang EN bzw. Freigabe ist auf Null gestellt, wenn keiner der Eingänge aktiviert ist. Ein Decoder 42, der mit dem Codierer 40 auf die abgebildete Weise verbunden ist, ist mit dem Decoder 38 identisch. Der Prioritätscodierer 40 und der Decodierer 42 bilden zusammen einen Block, der nur einen der Ausgänge Y0-Y3 aktiviert, der dem aktivierten Eingang höchsten Rangs entspricht.
Die Funktion der in Fig. 7 gezeigten Steuerschaltung geht aus der folgenden Beschreibung des Zeitplaners und seiner Funktion in Zusammenhang mit den Fig. 9-15 hervor.
Die beim Zeitplaner an einem Eingang 21 ankommenden Marken werden in einem Speicher 44 gemäß Fig. 10 gespeichert. Jede Zeile in diesem Speicher stellt eine Marke für einen bestimmten Anschluss 2.n dar, und jede Spalte stellt eine Adresse zu einem der Ausgangsanschlüsse 8.n dar. Die Marken werden in einer Zeile des Speichers in D-Flipflops 45 gespeichert, und werden durch das Haltesignal gehalten bzw. verriegelt, welches entsprechend der obigen Beschreibung an dem Ausgang 35 des UND-Gatters 34 im Steuerblock 22 erscheint. Die Ausgänge des Speichers 44 sind mit Eingängen einer Datenvermittlung verbunden, welche unten unter Bezugnahme auf Fig. 11 beschrieben wird.
Die Ausgangssignale der Decoder 38, 42 werden Zeilenleiteinrichtungen 46 bzw. Spaltenleiteinrichtung 48 eines in Fig. 9 gezeigten Adressierungsblocks 50 zugeführt, der Haltepulse für einen Speicher für Zeitplanungsdaten schafft, welcher unten unter Bezugnahme auf die Fig. 12, 13 näher beschrieben wird. Die entsprechenden Eingänge von UND- Gattern 52 sind mit dem Zeilen- und Spaltenleiteinrichtungen 38 bzw. 42 verbunden, und daher aktiviert eine Kombination von Signalen - ein aktiviertes Signal für jeden Decoder 38 bzw. 42 - den Ausgang eines dieser UND-Gatter. Der Block 50 enthält auch ODER-Gatter 54, in welchen ein Eingang mit dem Ausgang des entsprechenden UND-Gatters 52 verbunden ist, und der andere Eingang mit dem Ausgang SH (Shift) des Steuerblocks 22 verbunden ist.
Die Ausgänge der ODER-Gatter 54 sind alle aktiviert wenn SH des Steuerblocks 22 aktiviert ist. Immer wenn das SH-Signal oder das Decodersignal in ein UND-Gatter 52 aktiviert ist, wird der Ausgang des ODER-Gatters 54, das mit diesem bestimmten UND-Gatter verbunden ist, somit aktiviert sein. Die Ausgänge der ODER-Gatter 54 sind mit einem Eingang eines jeweiligen UND-Gatters 56 verbunden. Der andere Eingang jedes UND-Gatters 56 ist für den Empfang des Taktgebersignals K angeschlossen, und sein Ausgang bildet einen der Ausgänge 58 des Adressierungsblocks 50, und daher sind Signale, welche an letzterem erscheinen, mit dem Zeitgeber synchronisiert.
Der Adressierungsblock 50 taktet entweder einen Speicherort eines Markenspeichers 60, welcher unten näher beschrieben wird, für Anfragen, für welche die Zeitplanung stattgefunden hat (Fig. 13), der einen bestimmten Eingangsanschluss und einen herausgehenden Übertragungszyklus darstellt, oder alle Speicherorte.
Eine Datenvermittlung 22, welche in Fig. 11 gezeigt ist, hat wie oben erwähnt Eingänge 64, die mit den Ausgängen des Speichers 44 verbunden sind, und Steuereingänge 66, 68, 70, 72, welche mit dem Ausgang des Decoders 38 verbunden sind. Die Datenvermittlung 62 gibt eine der Marken aus dem Speicher 44 auf einem seiner Ausgänge 73 aus, wenn der untergeordnete Steuereingang 66-72 aktiviert ist.
Fig. 12 zeigt einen Block 74 mit einem Flipflop 75 und einer Eingangsvermittlung, die aus UND-Gattern 76, 77 und einem ODER-Gatter 78 besteht. Die Steuereingänge 80 und 82 sind mit einem Eingang eines jeweiligen Gatters 76, 77 verbunden. Wenn einer der Steuereingänge 80, 82 aktiviert ist und der Flipflop 75 getaktet wird, werden die Daten auf dem Dateneingang, der dem aktivielten Steuereingang entspricht, gehalten, und auf dem Ausgang 84 des Flipflop 75 bereitgestellt.
Eine Gruppe von Blöcken 74 der in Fig. 12 gezeigten Art ist im Speicher 60, der in Fig. 13 gezeigt ist, enthalten, für Anfragen, für welche eine Zeitplanung durchgeführt wurde. Jede Zeile der Gruppe kann eine Marke empfangen.
Fig. 14 zeigt ein Beispiel des Konfliktsteuerblocks. Der Konfliktsteuerblock prüft eine Marke nach der anderen aus dem Speicher von ankommenden Marken, gegenüber einer entsprechenden Instanz des Speichers für Marken, für welche eine Zeitplanung stattgefunden hat.
Die Ausgänge aus der in Fig. 11 gezeigten Datenvermittlung 62 sind mit Eingängen 85 jeder der vier Konfliktprüfungsblocks 86 verbunden, gemäß Fig. 14. Die Bits einer isolierten Marke werden einem Eingang von NUND-Gattern 88, 90, 92, 94 in jedem Konfliktprüfungsblock zugeführt. Jeder Konfliktprüfungsblock 86 ist auch mit einem entsprechenden Speicher der vier Markenspeicher 60 für Anfragen, für welche eine Zeitplanung stattgefunden hat, gemäß Fig. 13 verbunden. Die Ausgänge 96 für alle Zeilen und Spalten der Speicher 60 sind zeilenweise mit NODER-Gattern 98, 100, 102, 104 verbunden, und spaltenweise mit ODER-Gattern 106, 108, 110, 112. Die NODER- Gatter 98-104 stellen ihre Ausgänge auf Null, wenn ein beliebiges Bit in ihren jeweiligen Zeilen auf eins eingestellt ist. Auf eine der Zeilen wird von UND-Gattern 114, 116, 118, 120 und einem ODER-Gatter 122 verwiesen, dessen Ausgang mit einem von fünf Eingängen eines UND-Gatters 124 verbunden ist. Die Ausgänge aus den ODER-Gattern 106-112 sind auf eins eingestellt, wenn ein beliebiges Bit an ihren jeweiligen Spalten auf eins eingestellt ist. Der entsprechende andere Eingang der NUND-Gatter 88-94 ist mit dem Ausgang eines jeweiligen ODER-Gatters 16, 108, 110 und 112 verbunden. Die NUND-Gatter 88-94 stellen daher ihre Ausgänge auf Null, wenn ihre jeweils am Eingang 85 empfangenen Markenbits und ein beliebiges Bit der Bits in einer aus dem entsprechenden ODER-Gatter 106-112 empfangenen Spalte auf eins eingestellt ist. Die Ausgänge der NUND-Gatter 88-94 bilden einen weiteren Eingang des UND-Gatters 124. Der Ausgang des UND-Gatters 124 ist daher auf eins eingestellt, wenn es keine auf eines eingestellten Bits in der Zeile gibt, auf welche verwiesen wird, und keine auf eins eingestellten Markenbits am Eingang 85 auf den gleichen Spalten vorkommen, wie auf eins eingestellte Bits in den Markenspeichern. Eine ankommende Marke kann dann möglicherweise in dem Speicher 60 für Anfragen, für welche eine Zeitplanung stattgefunden hat, platziert werden, was aus dem folgenden hervorgeht.
Die Ausgänge von allen UND-Gattern 124 sind mit dem Prioritätscodierer 40 des Steuerblocks 22 verbunden, und daher werden jene der Eingänge P0-P3 des Prioritätscodierers auf eins gesetzt, welche Übertragungszyklen entsprechen, in welchen Zellen erfolgreich eingeplant werden können. Der Prioritätscodierer 40 codiert den Eingang höchsten Rangs in ein Binärwort (2 Bit) und ein EN bzw. Freigabesignal. Der Ausgang des Prioritätscodierers 40 bildet den frühesten ausgehenden Übertragungszyklus (wenn es einen gibt), der keinen Zellenkonflikt für die Zelle verursacht, für welche die Planung stattfindet. Alle Ausgänge des Prioritätscodierers 40 sind mit den Eingängen des Codierers 42 und nicht abgebildeten Flipflops verbunden, und einer Vorrichtung, welche dafür sorgt, dass Zeitplanungsinformation an die Anschlüsse geschickt wird. Die Ausgänge des Codierers 42 sind mit Spaltenwahleingängen des Adressierungsblocks 50 verbunden, ein Ausgang für jede Spalte. Die Spalten des Adressierungsblocks stellen somit ausgehende Übertragungszyklen dar.
Die ankommende Marke einer Zeile, welche verarbeitet wird, wird den Eingängen aller Markenspeicher 60 für Anfragen, für welche eine Zeitplanung stattgefunden hat, zugeführt, aber aus dem Adressierungsblock 50 wird ein Haltepuls nur an den Speicherort in den Markenspeicher geschickt, der einen Anschluss darstellt, aus welchem die verarbeitete Anfrage ankommt, und einen ausgehenden Übertragungszyklus in welchem kein Konflikt auftreten wird, wodurch die Marke nur in diesen Speicherort getaktet wird.
Beim Auftreten von Zuständen, in welchen SH bzw. Shift aktiviert ist, wird der den Invertierer 36 enthaltende Decoder den im Block in Fig. 12 enthaltenden Eingangswähler dazu bringen, den anderen Dateneingang zu wählen. Diese Eingänge und Ausgänge 84 sind so verbunden, dass eine Datenverschiebung durchgeführt wird, wenn die Flipflops getaktet werden.
In jedem der Anschlüsse 2.n gibt es ein Verzögerungsmittel der in Fig. 16 gezeigten Art. Während auf Zeitplanungsinformation aus dem Zeitplaner gewartet wird, wird eine von außerhalb des Systems ankommende Zelle in einem Zellenpuffer, der nicht abgebildet ist, im Anschluss zwischengespeichert. Die Zelle wird auf dem Eingang "CELL IN" in allen Blöcken 130 bereitgestellt, die im Verzögerungsmittel enthalten sind, für eine weitere Verzögerung der Zellen, wird aber nur in D-Flipflops 152 in Block 130 gespeichert, deren Eingang "STORE" auf eins eingestellt ist. Auf der Grundlage der Zeitplanungsinformation, welche aus dem Kern ankommt und für die Eingänge "SCHEDULING INFO" bereitgestellt wird, wird die Zelle auf dem Ausgang "CELL OUT" zu dem Zeitpunkt bereitgestellt, zu dem die Zelle zum Anschluss geschickt werden soll, wie unten näher beschrieben wird.
Ein Block der oben erwähnten Art ist in Fig. 17 ausführlicher gezeigt, wobei eine darin enthaltene Zustandsmaschine 132 in Fig. 18 zusammen mit einem entsprechenden Zustandsschaubild 133, einer Tabelle 134 mit Zustandsänderungsbedingungen und einer Zustandstabelle 135 gezeigt ist.
Jeder der Blöcke 130 hat einen Ausgang "FREE", welcher, wenn er auf eins eingestellt ist, anzeigt, dass ein entsprechender Puffer eine neue Zelle speichern kann. Diese Ausgänge aus den Blöcken 130 werden den Eingängen P0, P1 bzw. P2 eines Prioritätscodierers 136 zugeführt. Der Prioritätscodierer 136 hat einen Ausgang EN (für Enable bzw. Freigabe), der mit einem Eingang eines UND-Gatters 138 verbunden ist, welches auf die in Fig. 16 gezeigte Weise durch einen weiteren Eingang angeschlossen ist, um ein Flag "VALID SOURCE CELL FLAG" zu empfangen. Wenn es auf eins gesetzt ist, zeigt dieses Flag an, dass eine von außerhalb des Systems ankommende Zelle keine leere Zelle ist. Der Ausgang des UND- Gatters 138 ist mit einem Eingang EN (für Freigabe) eines Decoders 140 verbunden. Wenn die zwei Eingänge des UND- Gatters auf eins eingestellt sind, was auftritt, wenn das Flag "VALID SOURCE CELL FLAG" und mindestens einer der Eingänge P0, P1 oder P2 auf eins gesetzt sind, ist der Ausgang am UND-Gatter 138 auf eins eingestellt. Dadurch sind auch einige der Ausgänge Y0, Y1 oder Y2 aus dem Decoder 140 auf eins eingestellt, entsprechend dem Eingang höchster Ordnung, welcher durch die Eingänge P0, P1 und P2 des Prioritätscodierers 136 aktiviert ist. Dies führt dazu, dass ein Zellenpuffer 141 des einen Blocks der Blöcke 130, dessen Eingang "STORE" auf eins eingestellt ist, mit der Zelle geladen wird, und die hierdurch in dem gleichen Block empfangenen Zeitplanungsinformation geführt hat, wird am Ausgang "CELL OUT" des Zellenpuffers im Übertragungszyklus präsentiert, in dem die Zelle zum Anschluss geschickt werden soll. Über ODER-Gatter 142 wird die Zelle am Ausgang 144 des Verzögerungsmittels bereitgestellt, da nur ein Puffer auf einmal auf eins eingestellte Ausgänge haben kann.
Die in jedem der Blöcke 130 enthaltenen Mittel zur Bereitstellung einer Zelle aus einem Zellenpuffer 141 im richtigen Übertragungszyklus enthalten die Zustandsmaschine 132, welche ein Sperrsignal am Ausgang "LATCH" bereitstellt, zählt die Zahl der Übertragungszyklen herab, welche durch die Zeitplanungsinformation angegeben ist, welche auf den Eingängen "SCHEDULING INFO" empfangen wird, und stellt ein Auslesesignal am Ausgang "DISPATCH" bereit, wenn die Herabzählung durchgeführt worden ist.
Das Zustandsschaubild 133 in Fig. 18 zeigt die Zustände und die Zustandsübergänge, welche auftreten, wenn die Zustandsmaschine die Zeit herabzählt. Der Zustand S00 ist ein Ruhezustand, in welchem sich die Zustandsmaschine befindet, wenn die Zelle weggeschickt wurde und keine neue Zelle im Zellenpuffer gespeichert werden soll. Der Zustand S10 betrifft das Auslesen der Zelle im unmittelbar folgenden Übertragungszyklus, wohingegen 520, S30 und S40 das Auslesen nach dem Herabzählen betreffen.
Die Tabelle 134 mit den Zustandsänderungsbedingungen zeigt den Rest der Zustandsübergänge. In den Ruhezustand S00 gelangt die Zustandsmaschine aus S00 (dem gleichen Zustand), S10, S20, S30 oder S40. In S10, S21, S32 und S43 gelangt die Zustandsmaschine entweder aus dem Ruhezustand oder aus dem Zustand S10 (dem gleichen Zustand), S20, S30 oder S40. In S10 gelangt die Zustandsmaschine wenn die Zelle in dem unmittelbar folgenden Übertragungszyklus geschickt werden soll, wohingegen die Maschine in S21, S32 und S43 gelangt, wenn die Zelle für weitere Übertragungszyklen verzögert werden soll.
In der Zustandstabelle 135 ist der Status der Ausgänge in unterschiedlichen Zuständen gezeigt. "FREE" ist nur in Zustand S00 auf eins gesetzt. "LATCH" ist in den Zuständen S10, S21, S32 und S43 auf eins gestellt. "DISPATCH" ist in den Zuständen S10, S0, S30 und S40 auf eins eingestellt.
Um ein gegenphasiges Zeitsignal für die Zustandsmaschine 132 zu erhalten, wird das Zeitgebersignal an "CLOCK" über einen Invertierer 146 geschickt.
Ein UND-Gatter 148 und ein D-Flipflop 150 sind mit dem Ausgang "LATCH" bzw. "DISPATCH" der Zustandsmaschine 132 verbunden. Das Zeitgebersignal ist auch mit dem anderen Eingang des UND-Gatters 148 und dem Zeitsignaleingang des D- Flipflop 150 verbunden, wodurch die Signale "LATCH" und "DISPATCH" mit dem Zeitsignal erfolgt. Der Ausgang aus dem UND-Gatter 148 ist mit Zeitgebereingängen D-Flipflops 152.1- 152.n verbunden, welche zusammen den Zellenpuffer 141 bilden, dessen Dateneingang D mit dem Eingang "CELL IN" des Blocks 130 verbunden ist.
Der Ausgang aus dem D-Flipflop 150 ist mit einem Eingang von UND-Gattern 154.1-154.n verbunden, in welchen ein zweiter Eingang mit einem jeweiligen Ausgang des D-Flipflop 152.1- 152.n verbunden ist. Der Ausgang der UND-Gatter 154 ist mit dem Ausgang "CELL OUT" des Blocks 130 verbunden. Somit wird die Taktung des Zellenpuffers 192 über das UND-Gatter 148 durch das Signal "LATCH" gesteuert, und die Bereitstellung der Zelle am Ausgang "CELL OUT" des Blocks 130 über den D- Flipflop 150 durch das Signal "DISPATCH".
Die Zeitgeberpulse kommen synchron und in Phase mit ausgehenden Übertragungszyklen an. In dem gleichen Übertragungszyklus, während die Zeitplanungsinformation für eine Zelle ankommt, muss sie und "STORE" zu dem Zeitpunkt, zu dem die Zustandsmaschine getaktet wird, stabil sein.
In Fig. 19 ist ein beispielhaftes Kopplungsszenario gezeigt, um ein mögliches Verhalten des Systems zu demonstrieren. Fünf vollständige aufeinanderfolgende Übertragungszyklen von Anschluss zu Kern und Kern zu Anschluss sind in der Figur gezeigt und unten beschrieben.
Zur Bezeichnung von Marken-, Zellen und Zeitplanungsinformation in Fig. 19, werden die gleichen Konzepte und Bezugszeichen verwendet, wie in der Beschreibung unter Bezugnahme auf die Fig. 2 bis 6. Unterschiedliche Sätze von verbundenen Marken-, Zellen- und Zeitgebungsinformation werden einerseits durch die Hinzufügung eines unterschiedlichen kleinen Buchstabens unterschieden, obwohl gemeinsam für die Marken-, Zelle- und Zeitplanungsinformation, nach dem entsprechenden Bezugszeichen, und andererseits durch unterschiedliche Linienmarkierungen in der Figur.
Jede Marke wird angegeben durch eine Sequenz von vier gleich großen rechteckigen Feldern, entsprechend der Felder 14.1- 14.4. in Fig. 2, und darin eine Bitangabe. Das gleiche gilt für die Zeitplanungsinformation mit Feldern entsprechend der Felder 16, b2, b1, b0 in Fig. 3. Jede Zelle ist wie in Fig. 5 angegeben, mit einem liegenden und schräggeschnittenen Rechteck.
Die Zeilen A1 und A2 bezeichnen einen Übertragungszyklus für Anschluss zu Kern bzw. Kern zu Anschluss, in Beziehung mit einem ersten Anschluss, welcher als Entsprechung zum Anschluss 2.1 in Fig. 1 angesehen werden kann. Das gleiche gilt für die Zeilen B1 und B2, C1 und C2, D1 und D2 bezüglich der Anschlüsse 2.2, 2.3 bzw. 2.4.
Während des ersten Übertragungszyklus wird wie aus Linie A1 hervorgeht, eine Marke 14a dem Kern aus dem Anschluss 1 zugeführt. Mit der Marke 14a wird auch eine Zelle 17 geliefert, welche wie bereits beschrieben wurde, nicht zur Marke 14a gehört. Die Marke 14a zeigt eine Anfrage an, eine Zelle zum Anschluss 3 zu schicken, indem das dritte Bit (14.3) auf eins eingestellt ist, was durch die Liniemarkierung des fraglichen Feldes angegeben wird. Da keine anderen Anfragen für das Schicken von Zellen zum Anschluss 3 erscheinen, wird eine Zeitplanung für die Zelle 17a, welche zur Marke 14a gehört, vorgenommen, mit einer vorbestimmten Mindestverzögerung, wie es auf Linie A2 erscheint, durch die Zeitplanungsinformation 15a aus dem Kern an den Anschluss 1 in dem Übertragungszyklus 2 (alle Bits b2, b1 und b0 sind auf Null eingestellt). Die Mindestverzögerung, welche in dem Beispielssystem bestimmt ist, beträgt zwei Übertragungszyklen. Der Anschluss 1 empfängt Zeitplanungsinformation 15a und schickt dementsprechend die Zelle 17a an den Kern in Übertragungszyklus 3, wie in Linie A1 gezeigt. Der Kern zeigt im Übertragungszyklus 3, Line C2, in Richtung vom Kern zum Anschluss 3 an, dass die Zelle 17a gültig ist, wie aus dem Flag 16a hervorgeht. Im gleichen Übertragungszyklus schickt der Kern die Zelle 17a an den Anschluss 3 mit einem minimalen dt von weiterer Verzögerung und praktisch keiner Pufferung.
Drei Marken 14b, 14c und 14d in den Linien B1, C1 und C3 mit konfliktbeladenen Zellenzielen zum Anschluss 1, wie aus dem jeweiligen ersten Feld (14.1 in Fig. 2) hervorgeht, werden während des Übertragungszyklus 1 an den Kern übertragen. Die Marke 14c des Anschlusses 3 zeigt an, dass die zugehörige Zelle mehrere Ziele hat, d. h. neben Anschluss 1 auch Anschluss 4 (Felder 14.1 und 14.4 in Fig. 2).
Der Konfliktverarbeitungsalgorithmus, der sich im Kern befindet, hat den Zellen aus den Anschlüssen 2, 3 und 4 unterschiedliche Sendezeiten zugewiesen, entsprechend der Marken 14b, 14c und 14d, mit einem gemeinsamen Ziel zum Anschluss 1. Abhängig von dem Zustand der Zustandsmaschine 24 in dem Beispiel, wird die Marke 14b aus dem Anschluss 3 im Kern erst verarbeitet, siehe die Zeitplanungsinformation 15c in Linie C2, und dadurch die früheste Sendezeit erhalten, und danach folgend die Anschlüsse 4 und 2. Die Zelle 17c aus dem Anschluss 3 wird somit im Übertragungszyklus 3 an den Anschluss 1 und 4 geschickt, siehe Linie C1 für die Richtung des Kerns, und die Linien A2 und D2 für die Richtung zu den jeweiligen Anschlüssen. Die Zelle 17d, zusammen mit einer ihr nicht gehörenden Marke, wird vom Anschluss 4 zum Kern geschickt, siehe Linie D1 und von dort zum Anschluss 1 im Übertragungszyklus 4, siehe Linie A2. Die Zelle 14b wird zusammen einer ihr nicht gehörenden Marke vom Anschluss 2 zum Kern geschickt, siehe Linie B1 und von dort zum Anschluss 1 im Übertragungszyklus 5.
Während die Zelle 17d des Anschlusses 4, für welche die Zeitplanung stattgefunden hat, die den Anschluss 1 als Ziel hat, darauf wartet weitergeschickt zu werden, wird eine Zeitplanung vorgenommen für eine neue Zelle 17e aus dem Anschluss 4 mit dem Zielanschluss 3. Der Übertragungszyklus 5 wird der Zelle 17e zugewiesen, siehe Linie D1 und C2, da eine vorher geplante Zelle aus dem Anschluss 4 im Übertragungszyklus 4 weitergeschickt wird. Während die Zelle 17b in Anschluss 2, mit dem Zielanschluss 1 darauf wartet weitergeschickt zu werden, wird eine Zeitplanung und Weiterleitung einer weiteren Zelle 17f aus dem Anschluss 2 zum Anschluss 3 durchgeführt, siehe Linie B1 und C2.

Claims

1. Zellenvermittlung, umfassend

eine Vielzahl von Vermittlungsanschlüssen (2.n), wobei jeder mit einer Anzahl von Benutzerendgeräten verbunden ist, um Zellen der Benutzerendgeräte zu senden und zu empfangen, wobei die Zellen Nutzlast- und Adresseninformation enthalten,

einen Vermittlungskern (4), welcher die Vermittlungsanschlüsse verbindet, um eine Kommunikation zwischen ihnen zu ermöglichen,

ein Markierungsmittel in den Vermittlungsanschlüssen, um auf der Grundlage der Adresseninformation einer von einem Benutzerendgerät empfangenen Zelle (17) eine Marke (14) zu erzeugen, welche zu der Zelle gehört und Routing-Information enthält, die das Routing der Zelle durch den Vermittlungskern ermöglicht,

gekennzeichnet durch

ein Mittel (22) um Marken an den Vermittlungskern (4) vor entsprechenden Zellen zu schicken, eine Marke für jede Zelle,

ein Zeitplanungsmittel (21, 22, 44, 45, 62, 60, 86 - Fig. 15) in dem Vermittlungskern, um die im voraus geschickten Marken zu empfangen und um auf der Grundlage der darin enthaltenen Routing-Information für die jeweiligen Zellen aus den Vermittlungsanschlüssen (2.n) Zeitplanungsinformation (15) zu schaffen bezüglich einer Sendezeit, zu welcher die Zelle zu den

Zielvermittlungsanschlüssen geschickt werden kann, ohne dass ein Konflikt mit anderen Zellen auftritt, und

zum Senden der Zeitplanungsinformation an die Ursprungs- Vermittlungsanschlüsse der Zellen,

ein Verzögerungsmittel zum Zurückhalten der Zellen in den Vermittlungsanschlüssen, bis ihre jeweilige geplante Sendezeit auftritt, und zum Senden der Zellen in den Vermittlungskern zu den jeweils geplanten Sendezeiten.

2. Vermittlung nach Anspruch 1, dadurch gekennzeichnet, dass das Mittel (22) zum Senden von Marken an den Vermittlungskern angeordnet ist, eine Marke während eines anderen Übertragungszyklus zu übertragen, als jener der entsprechenden Zelle aus dem entsprechenden Anschluss (2.n) an den Kern (4).

3. Vermittlung nach Anspruch 2, dadurch gekennzeichnet, dass zwischen dem Übertragungszyklus für die Übertragung einer Marke und dem Übertragungszyklus für die Übertragung einer entsprechenden Zelle eine Zeitverzögerung von mindestens einer Anzahl von Übertragungszyklen besteht, welche erforderlich ist, um die Verarbeitung zur Vermeidung von Konflikten zu ermöglichen.

4. Vermittlung nach Anspruch 2 oder 3, dadurch gekennzeichnet, dass das Mittel (22) zum Senden von Marken an den Vermittlungskern während jedes Übertragungszyklus angeordnet ist die Übertragung einer Marke einer Zelle, für welche noch keine Zeitplanung stattgefunden hat, zusammen mit einer Zelle, für welche eine Zeitplanung stattgefunden hat, in Richtung vom Anschluss (2.n) zum Kern (4) zu erlauben.

5. Vermittlung nach einem der Ansprüche 1 bis 4, dadurch gekennzeichnet, dass das Zeitplanungsmittel (21, 22, 44, 50, 60, 62, 86 - Fig. 15) angeordnet ist, ein Senden einer Zelle zusammen mit der Zeitplanungsinformation einer späteren Zelle und einem Flag für eine gültige Zelle vom Kern (4) zum Anschluss (2.n) zu erlauben.

6. Vermittlung nach einem der Ansprüche 1 bis 5, dadurch gekennzeichnet, dass eine ungültige Marke (14), welche keine Routing-Information hat, dem Kern anzeigt, dass es keine neue Zelle gibt, welche auf eine Zeitplanung wartet.

7. Vermittlung nach einem der Ansprüche 1 bis 6, dadurch gekennzeichnet, dass die Marken (14), welche aus den Anschlüssen gesendet wurden und Routing-Information enthalten, jeweils eine implizite Anforderung für die Zuweisung eines Übertragungszyklus enthalten.

8. Vermittlung nach Anspruch 7, dadurch gekennzeichnet, dass das Zeitplanungsmittel (21, 22, 44, 50, 60, 62, 86 - Fig. 15) angeordnet ist alle solchen Anforderungen eine nach der anderen während eines Übertragungszyklus zu verarbeiten, wobei die Verarbeitungsreihenfolge für jeden Übertragungszyklus geändert wird, um Fairness zwischen den Anschlüssen zu erreichen.

9. Vermittlung nach Anspruch 7 oder 8, dadurch gekennzeichnet, dass das Zeitplanungsmittel (21, 22, 44, 50, 60, 62, 86 - Fig. 15) ein Mittel (60, Fig. 13) hat, um alle Marken zu speichern, welche zu Zellen gehören, für welche eine Zeitplanung stattgefunden hat.

10. Vermittlung nach einem der Ansprüche 7 bis 9, dadurch gekennzeichnet, dass das Zeitplanungsmittel (21, 22, 44, 50, 60, 62, 86 - Fig. 15) Speicherorte (44 - Fig. 10) hat, um alle Marken an Speicherorten zu speichern, welche implizit die relativen Sendezeiten für ihre entsprechenden Zellen angeben, und zum Verschieben aller Marken für jeden neuen Übertragungszyklus in neue Speicherorte, welche nähere Sendezeiten darstellen, so dass die Marken somit immer an Speicherorten gespeichert sind, welche die relativen Sendezeiten wiedergeben.

11. Vermittlung nach einem der Ansprüche 7 bis 10, gekennzeichnet durch ein Mittel (86 - Fig. 14) zur Prüfung jeder Marke, die beim Kern ankommt, parallel gegenüber früheren Zellen, für welche eine Zeitplanung stattgefunden hat, bezüglich des Konfliktrisikos.

12. Vermittlung nach einem der Ansprüche 7 bis 11, dadurch gekennzeichnet, dass das Zeitplanungsmittel (21, 22, 44, 50, 60, 62, 86 - Fig. 15) angeordnet ist, die erfolglose Zeitplanung einer Zelle anzuzeigen, indem eine relative Sendezeit für die Zelle genannt wird, welche größer ist, als die verfügbare Zahl von Speicherorten.

13. Verfahren für das Routing von Zellen durch eine Zellenvermittlung, welche umfasst:

eine Vielzahl von Vermittlungsanschlüssen (2.n), wobei jeder mit einer Anzahl von Benutzeranschlüssen verbunden ist, zum Senden und Empfangen von Zellen der Benutzerendgeräte, wobei die Zellen Nutzlast- und Adresseninformation enthalten,

einen Vermittlungskern (4), der die Vermittlungsanschlüsse verbindet, um eine Kommunikation zwischen ihnen zu gestatten,

umfassend die Schritte:

beruhend auf der Adressinformation der empfangenen Zellen, Erzeugen einer jeweiligen Marke (14) für jede empfangene Zelle (17), welche Routing-Information enthält, die ein Routing der Zelle durch den Vermittlungskern (4) zu einem gewünschten Zielanschluss gestattet,

und gekennzeichnet durch:

Senden der Marken an den Vermittlungskern (4) vor entsprechenden Zellen,

beruhend auf der Routing-Information, die in den im voraus gesendeten Marken enthalten ist, Schaffen von Zeitplanungsinformation (15) bezüglich der Sendezeiten der jeweiligen Zellen aus den Anschlüssen, um eine Zeitplanung für diese Sendezeiten der zu sendenden Zellen zu den Zielanschlüssen ohne das Auftreten eines Konflikts mit anderen Zellen durchzuführen,

Senden der Zeitplanungsinformation (15) an die Ursprungs-Vermittlungsanschlüsse (2.n) der Zellen,

Zurückhalten der Zellen in den Vermittlungsanschlüssen (2.n) bis ihre jeweils geplanten Sendezeiten auftreten, und

Senden der Zellen in den Vermittlungskern (4) zu ihren jeweiligen geplanten Sendezeiten.

14. Verfahren nach Anspruch 13, umfassend den Schritt der Übertragung einer Marke (14) und der entsprechenden Zelle (17) während unterschiedlicher Übertragungszyklen aus dem entsprechenden Anschluss (2.n) an den Kern (4)

15. Verfahren nach Anspruch 14, umfassend den Schritt, dass zwischen dem Übertragungszyklus für die Übertragung einer Marke und dem Übertragungszyklus für die Übertragung einer entsprechenden Zelle, eine Zeitverzögerung von mindestens einer Anzahl von Übertragungszyklen vorgesehen ist, welche erforderlich ist, um die Verarbeitung zur Vermeidung eines Konflikts zu ermöglichen.

16. Verfahren nach Anspruch 14 oder 15, umfassend den Schritt, dass während jedes Übertragungszyklus eine Zelle (17) für welche eine Zeitplanung stattgefunden hat, zusammen mit einer Marke (14) einer Zelle, für welche noch keine Zeitplanung stattgefunden hat, in Richtung von dem Anschluss (2.n) zum Kern (4) übertragen wird.

17. Verfahren nach einem der Ansprüche 13 bis 16, umfassend den Schritt, dass eine Zelle (17) zusammen mit der Zeitplanungsinformation einer späteren Zelle und einem Flag (16) für eine gültige Zelle aus dem Kern (4) an den Anschluss (2.n) gesendet wird.

18. Verfahren nach einem der Ansprüche 13 bis 17, umfassend den Schritt, dass dem Kern (4) mittels einer ungültigen Marke (14) angezeigt wird, dass keine neue Zelle (17) auf eine Zeitplanung wartet.

19. Verfahren nach einem der Ansprüche 13 bis 18, umfassend den Schritt, dass jede der Marken (14), welche von den Anschlüssen gesendet und Routing-Information enthält, mit einer impliziten Anforderung nach Zuweisung eines Übertragungszyklus ausgestattet wird.

20. Verfahren nach Anspruch 19, umfassend den Schritt, dass alle Anforderungen eine nach der anderen während eines Übertragungszyklus verarbeitet werden, und die Reihenfolge solcher Verarbeitung für jeden Übertragungszyklus geändert wird, um Fairness zwischen den Anschlüssen (2.n) zu erreichen.

21. Verfahren nach Anspruch 19 oder 20, umfassend den Schritt, dass alle Marken (14), welche zu Zellen (17) gehören, für welche eine Zeitplanung stattgefunden hat, gespeichert werden.

22. Verfahren nach Anspruch 21, umfassend den Schritt, dass alle Marken gespeichert werden, so dass die Speicherorte (44) implizit die relativen Sendezeiten für ihre entsprechenden Zellen (17) angeben, und Verschieben aller Marken (14) für jeden neuen Übertragungszyklus in neue Speicherorte, welche nähere Sendezeiten darstellen, so dass die Marken somit immer an Speicherorten gespeichert sind, welche die relativen Sendezeiten wiedergeben.

23. Verfahren nach einem de Ansprüche 13 bis 22, umfassend den Schritt, dass jede Marke, welche beim Kern ankommt, parallel gegenüber Marken von früheren Zellen, für welche eine Zeitplanung stattgefunden hat, bezüglich des Konfliktrisikos geprüft wird.

24. Verfahren nach einem der Ansprüche 13 bis 23, umfassend den Schritt, dass die erfolglose Zeitplanung einer Zelle angezeigt wird durch Angabe einer relativen Sendezeit für die Zelle, welche größer ist, als die verfügbare Zahl von Speicherorten.