DE69800157T2

DE69800157T2 - Vorrichtung und Verfahren zur schablonenbasierten Planung in Kommunikationsnetzen unter Verwendung von niedrigen Begrenzungswerten von Gleichmässigkeitmessungen

Info

Publication number: DE69800157T2
Application number: DE69800157T
Authority: DE
Inventors: Simon C. Borst; Kajamalai Gopalaswamy Ramakrishnan
Original assignee: Lucent Technologies Inc
Current assignee: Nokia of America Corp
Priority date: 1997-03-27
Filing date: 1998-03-17
Publication date: 2001-01-25
Anticipated expiration: 2018-03-18
Also published as: DE69800157D1; JPH10303935A; US6016305A; CA2228236A1; JP3178711B2; EP0868058B1; CA2228236C; EP0868058A1

Description

Die vorliegende Erfindung betrifft Verfahren zur Identifizierung einer Ablaufsteuerungsschablone für ein Netz und Knoten zur Verwendung in einem Kommunikationsnetz.
Netze sind ein Hauptmittel für den Austausch oder die Übertragung von Informationen wie zum Beispiel Informationssignalen, die Sprache, Audio, Daten oder Video darstellen, zwischen Kommunikationsgeräten. Solche Kommunikationsgeräte enthalten häufig Geräte zum Senden und/oder Empfangen von Informationen, wie zum Beispiel Computerterminals, Multimedia-Workstations, Faxmaschinen, Drucker, Server und Fernsprecher. Auf dem letz übertragene Informationen können in vielen verschiedenen Formen vorliegen, werden aber häufig zu Datenpaketen oder -zellen fester Länge formatiert. Netze wie zum Beispiel Breitband-ISDN (BISDN), die eine Paketvermittlung im asynchronen Übertragungsmodus (ATM) einsetzen, werden zunehmend für die zuverlässige, schnelle Übertragung von Informationen verwendet. Diese gesteigerte Verwendung hat zu wesentlichen Veränderungen beim Entwurf der Netzarchitektur und -infrastruktur sowie bei Netzoperationen geführt, um die Kommunikationskapazität und -qualität zu vergrößern.
Ein typisches Netz enthält Vermittlungsknoten mit Ports, die durch Strecken an Ports anderer Knoten und an die Kommunikationsgeräte angekoppelt sind. Jede Strecke ist einseitig oder zweiseitig gerichtet und durch eine Bandbreite oder Streckenkapazität in den Richtungen der Informationsübermittlung gekennzeichnet. Auszutauschende Informationen werden häufig über einen Weg geführt, der eine Menge von Knoten und zwei Geräte verbindende Strecken enthält. Ein solcher Weg kann als eine "virtuelle Leitung" (VC - virtual circuit) betrachtet werden, wodurch ein Kommunikationsgerät das beabsichtigte Zielgerät für die Informationen angibt und das Netz die Informationen so liefert, als ob die beiden Kommunikationsgeräte eine fest zugeordnete Leitung verbinden würde. Häufig werden mehrere VCs gleichzeitig über einen einzigen Vermittlungsknoten gehalten. Ähnlich werden verschiedene VCs häufig gleichzeitig über eine gemeinsame Strecke zwischen Vermittlungsknoten gehalten.
Pufferspeicher werden in der Regel in den Vermittlungsknoten verwendet, um die Anzahl von VCs zu vergrößern, die gleichzeitig durch den Knoten geführt werden kann, indem die Übertragung von Datenpaketen eines Typs, der relativ verzögerungsunempfindlich ist, gepuffert wird, während die Übertragung der Pakete eines Typs, der relativ verzögerungsempfindlich ist, in geringerem Ausmaß gepuffert wird. Solche Pufferspeicher wirken effektiv als jeweilige Warteschlangen für die Pakete, die durch die jeweiligen Ports zu einer gemeinsamen Strecke oder mehreren Strecken geführt werden sollen. Durch Auswahl einer vorteilhaften Reihenfolge, in der Pakete aus diesen Warteschlangen durch einen gemeinsamen Vermittlungsknoten gelenkt oder über eine gemeinsame Strecke multiplexiert werden, ist es möglich, die Anzahl von VCs zu vergrößern, die der Vermittlungsknoten gleichzeitig aufrechterhalten kann, sowie die Kommunikationsqualität zu vergrößern.
Bei bestimmten Netzen wird zur Bereitstellung der Übertragungs-Ablaufsteuerungsreihenfolge für Datenpakete der jeweiligen VCs eine Schablone verwendet. Eine herkömmliche Schablone enthält eine feste Anzahl von Schlitzen, wobei jede Schlitzposition eine Ablaufsteuerungsposition entsprechender Pakete für eine bestimmte VC darstellt. Die Reihenfolge solcher Schlitze in der Schablone bestimmt die Reihenfolge oder Abfolge, in der der Vermittlungsknoten wiederholt Pakete für die entsprechenden VCs sendet. Wünschenswerte Ablaufsteuerungsreihenfolgen, die eine vergrößerte VC-Kapazität und eine verbesserte Qualität des Dienstes erleichtern, senden Pakete für VCs mit relativ verzögerungsempfindlichen Informationen auf eine Weise, die im wesentlichen regulär ist, wie zum Beispiel zumindest ungefähr periodisch und nicht stoßartig.
Zu bekannten Verfahren zur Bestimmung von Ablaufsteuerungsreihenfolgen oder Schablonen-Schlitzpositionen gehören Reigen- und Golden-Ratio-Verfahren, die in Y. Arian und Y. Levy, "Algorithms for Generalized Round Robin Routing", Operations Research Letters, Band 12, Nr. 5, S. 313-319 (Nov. 1992) und A. Itai und Z. Rosberg, "A Golden Ratio Control Policy for a Multiple-Access Channel", IEEE Trans. on Automatic Control, Band AC-29, Nr. 8, S. 712-718 (Aug. 1984) beschrieben werden.
Durch solche Ablaufsteuerungsverfahren wird jedoch nur eine geringfügig verbesserte Anordnung der Schablonenschlitze bereitgestellt, und diese Verfahren übersehen gelegentlich vorteilhaftere Schlitzanordnungen.
Dementsprechend wird ein Verfahren zur Bestimmung verbesserter Anordnungen von Ablaufsteuerungsschablonen benötigt.
EP-A-0702473 richtet sich an Verfahren und Vorrichtungen zum Formen des Ausgangsverkehrs in einem Vermittlungsnetzknoten mit Zellen fester Länge. Es werden Zellen-Warteschlangen von bestehendem Verkehr geführt. Wenn neuer Verkehr hergestellt wird, wird eine Zeitmultiplexierungstabelle auf der Grundlage einer relativ rechenintensiven Vorberechnung der besten Plazierung der Einträge für den neuen Verkehr aktualisiert. Die Berechnung soll die Zellenverzögerungsvariation (CDV), die durch einen GCRA-Überwacher berechnet wird, minimieren. Die CDV ist definiert als die Abweichung der Plazierung der Zellen in der Ausgabe, die aus ihrer Idealposition gezeigt ist, d. h. wenn die Einträge mit einem Intervall beabstandet sind, das der Verkehrsperiode entspricht, die zum Zeitpunkt der Verkehrsherstellung ausgehandelt wird. Das Verfahren versucht die Schlitzbearbeitung von neuem Verkehr zu optimieren, indem ausgewertet wird, welche Schlitze zu einem bestimmten Zeitpunkt verfügbar sind.
Gemäß einem Aspekt der vorliegenden Erfindung wird ein Verfahren nach Anspruch 1 bereitgestellt. Gemäß einem weiteren Aspekt der vorliegenden Erfindung wird ein Knoten nach Anspruch 25 bereitgestellt.
Die Erfindung basiert auf einem vorteilhaften Meßverfahren zur Auswertung der Gesamt-Ablaufsteuerungsregularität, die durch eine Ablaufsteuerungsschablone mit bestimmten Schlitzzuweisungen zu jeweiligen Klassen von Kommunikationssignalen wie zum Beispiel jeweiligen virtuellen Leitungen erzeugbar ist.
Eine vorteilhafte Schablonen-Schlitzanordnung wird bestimmt, indem mindestens zwei anfängliche Schlitzpositionen einer bestimmten Klasse zugewiesen werden, um eine Zwischenschablone zu bilden, und dann ein Regularitätsmaß auf der Grundlage einer unteren Grenze für das Regularitätsmaß solcher Zuweisungen und der übrigen, nicht zugewiesenen Schlitzpositionen der Zwischenschablone bestimmt wird. Diese untere Grenze für das Regularitätsmaß der nicht zugewiesenen Schlitze basiert vorteilhafterweise auf einer hypothetischen Zuweisung von Teilen der jeweiligen Schlitzpositionen zu verschiedenen Klassen, anstatt die Zuweisung eines Schlitzes auf eine einzige Klasse zu begrenzen. Diese Teil-Schlitzzuweisung erzeugt ein Regularitätsmaß, das in der Regel vorteilhafter als oder gleich einem entsprechenden Regularitätsmaß ist, das darauf basiert, einen ganzen Schlitz einer bestimmten Klasse zuzuweisen, und liefert deshalb eine untere Grenze.
Die untere Grenze des Regularitätsmaßes wird dann mit einem Bezugsregularitätsmaß verglichen, das zum Beispiel aus einer bekannten Anwärter- Ablaufsteuerungsschablone stammt. Wenn das Bezugs- Regularitätsmaß niedriger als die bestimmte untere Grenze ist, dann ist bekannt, daß die Bezugsschablone eine wünschenswertere Ablaufsteuerungsregularität als alle Schablonen liefern würde, bei denen die zugewiesenen Schlitze der Zwischenschablone von den Zuweisungen der nicht zugewiesenen Schlitze der Zwischenschablone unabhängig sind. Als Folge können andere Schlitzzuweisungen mit der Bezugs-Ablaufsteuerungsschablone verglichen werden, um schnell Ablaufsteuerungsschablonen mit verbesserten Regularitätskenngrößen zu identifizieren.
Solche Verfahren zur Bestimmung der Ablaufsteuerungs-Schablonenschlitzanordnung sind vorteilhafterweise in vielfältigen Kommunikationsnetzen, darunter verdrahtete Netze wie zum Beispiel BISDN-Netze, sowie in drahtlosen Netzen wie zum Beispiel Netze, die auf Zeitmultiplex mit Mehrfachzugriff basieren, verwendbar.
Zusätzliche Merkmale und Vorteile der vorliegenden Erfindung werden leichter aus der folgenden ausführlichen Beschreibung in Verbindung mit den beigefügten Zeichnungen deutlich.

Kurze Beschreibung der Zeichnungen

Fig. 1 zeigt ein Blockschaltbild eines beispielhaften Netzes, in dem Knoten verwendet werden;
Fig. 2 zeigt ein Blockschaltbild eines beispielhaften Knotens, der in dem Netz von Fig. 1 verwendet wird;
Fig. 3 zeigt ein Blockschaltbild einer alternativen Ausführungsform des Knotens von Fig. 2;
Fig. 4A, 4B und 4C zeigen beispielhafte Ablaufsteuerungsschablonen, die in dem Netz von Fig. 1 und den Knoten von Fig. 2 und 3 verwendbar sind;
Fig. 5 zeigt ein Flußdiagramm eines Verfahrens zur Bestimmung von Ablaufsteuerungsschablonen;
Fig. 6 zeigt ein Flußdiagramm eines beispielhaften Verfahrens zur Bestimmung eines Regularitätsmaßes zur Verwendung bei dem Verfahren von Fig. 5; und
Fig. 7 zeigt ein Flußdiagramm eines beispielhaften Verfahrens zur Bestimmung einer vorteilhaften Ablaufsteuerungsschablone.

Ausführliche Beschreibung

Die Erfindung betrifft Techniken zur Bestimmung einer Ablaufsteuerungsschablone zur Verwendung bei der Bereitstellung einer vorteilhaften Ablaufsteuerung einer Reihenfolge von Ereignissen wie zum Beispiel das Übertragen von Kommunikationssignalen von verschiedenen Signalklassen in einem Kommunikationsnetz. Eine solche vorteilhafte Ablaufsteuerung erleichtert eine verbesserte Kommunikationskapazität auf dem Netz und eine verbesserte Kommunikationsqualität. In einer Ablaufsteuerungsschablone ist eine Vielzahl von Schlitzen entsprechenden Signalklassen zugewiesen, wie zum Beispiel für die Datenpaket-Ablaufsteuerung für eine Vielzahl virtueller Leitungen, die durch einen Netzknoten gelassen werden. Eine Anordnung der Schlitze zeigt eine Ablaufsteuerungsreihenfolge zur Übertragung der Kommunikationssignale der jeweiligen Klassen an. Zur Erleichterung der verbesserten Kommunikationskapazität und/oder Kommunikationsqualität bestimmt die Erfindung eine Schablone, die eine Übertragungsreihenfolge oder Signalfolge für die Klassen bereitstellt, die im wesentlichen regulär ist oder zumindest ungefähr periodisch und nicht stoßartig ist.
Obwohl die Signalklassen der bereits beschriebenen Schablonen Kommunikationssignale jeweiliger virtueller Leitungen darstellen, kann eine Signalklasse auch mehr als eine virtuelle Leitung zur Übertragung von Informationen derselben oder einer ähnlichen Art darstellen, sowie es nachfolgend ausführlicher in bezug auf Fig. 5 beschrieben wird.
Die Erfindung ist verwendbar in Kommunikationsnetzen, die aus einer verbesserten Übertragungsablaufsteuerung für Kommunikationssignale profitieren könnten, darunter verdrahtete Netze, wie zum Beispiel Breitband-ISDN-Netze (BISDN-Netze) und drahtlose Netze wie zum Beispiel Netze, die auf Zeitmultiplex mit Vielfachzugriff (TDMA) basieren. Beispielhafte Ausführungsformen der Erfindung werden nachfolgend jedoch lediglich als Beispiel in bezug auf ein BISDN-Netz beschrieben und sollen keine Einschränkung der Erfindung bedeuten. In bezug auf ein auf TDMA basierendes drahtloses Netz ist die Erfindung verwendbar zur Bestimmung der Ablaufsteuerungsreihenfolge der jeweiligen Kommunikationssignalübermittlung zwischen einer Basisstation und zugeordneten drahtlosen Endgeräten.
Außerdem sind Ablaufsteuerungsschablonen verwendbar zur Bereitstellung der Reihenfolge des Zuweisens von Verbindungen, die zwischen zwei Gebieten gelenkt werden, über eine jeweilige Vielzahl von Netzrouten zwischen solchen Punkten. Wenn zum Beispiel zwanzig verschiedene Telekommunikationsrouten zum Lenken von Verbindungen zwischen Chicago und New York verwendbar sind, dann kann die Reihenfolge, in der Verbindungen über die jeweiligen Routen durch einen Telekommunikationsanbieter geleitet werden, auf solchen Ablaufsteuerungsschablonen basieren. Darüber hinaus ist eine Ablaufsteuerungsschablone verwendbar zur Anzeige der Reihenfolge von Ereignissen, in der einzelne Datenprozessoren, wie zum Beispiel Mikroprozessoren oder Computer, einer Vielzahl von Prozessoren jeweilige Operationen, wie zum Beispiel Transaktionen durchführen. Auf diese Weise können relativ große Zahlen von Operationen oder Transaktionen durch eine jeweilige Anzahl von Prozessoren durchgeführt werden. Ablaufsteuerungsschablonen für die Transaktionsverarbeitung sind vorteilhafterweise von Finanzinstitutionen verwendbar. Auf ähnliche Weise sind Ablaufsteuerungsschablonen verwendbar in Computern mit einer Vielzahl von Prozessoren zur Ablaufsteuerung von Operationen, die durch jeweilige Prozessoren zur parallelen Verarbeitung mit verbesserter Verarbeitungskapazität durchgeführt werden sollen.
Ein beispielhaftes Kommunikationsnetz 100 enthält Kommunikationsstrecken 120, die an Kommunikationsvermittlungsknoten 110 angekoppelt sind (siehe Fig. 1). Bei einem typischen BISDN-Netz ist es möglich, daß die Anzahl von mit einem Knoten 110 verbundenen Strecken in der Größenordnung von 512 oder mehr liegt. Jede Strecke 120 besitzt eine jeweilige Kapazität von Datenpaketen, die pro Zeiteinheit über die Strecke geführt werden können, was in der Regel als die Bandbreite der Strecke bezeichnet wird. Beispielhafte Strecken mit Bandbreiten von ungefähr 622 MB/s wurden in herkömmlichen BISDN-Netzen eingesetzt. Jeder Mehrfachportknoten 110 enthält in der Regel einen zur Pufferspeicherung von Signalen, die zu jeweiligen Strecken 120 gelenkt werden, verwendbaren Pufferspeicher.
Zu beispielhaften Paketen gehören ATM-Zellen mit einer festen Länge von 53 Byte. Solche Datenpakete können verschiedene Arten von Informationen darstellen, darunter zum Beispiel Sprache, Video, Audio oder Daten wie zum Beispiel Text. Außerdem können Pakete in einer höheren Protokollschicht länger sein und werden in der Regel als Nachrichten bezeichnet, die unterteilt werden können, um eine Vielzahl von Zellen zur ATM-Vermittlung zu erzeugen.
Es ist möglich, daß sich einer oder mehrere der Knoten 110 in einer bestimmten Netzvermittlung befinden, wie zum Beispiel in ATM-Datenvermittlungen, die von der Firma Lucent Technologies Inc. in Murray Hill, N. J., hergestellt werden, darunter die Vermittlungen GlobeView 2000® von Lucent. Bestimmte Knoten 110 sind außerdem an Zugriffsregulatoren 107 angekoppelt, die an Kommunikationsgeräte 105 angekoppelt sind. Die Kommunikationsgeräte 105 werden in der Regel von Dienstanbietern und Benutzern betrieben. Die Zugriffsregulatoren 107 regulieren den Fluß bzw. die Rate von Datenpaketen aus den Kommunikationsgeräten 105 in das Netz 100 auf der Grundlage einer Menge von Zugriffsregulatorparametern. Es ist möglich, daß die Zugriffsregulatoren 107 Löchriger-Eimer-Regulatoren, gepufferte Löchriger- Eimer-Regulatoren oder kaskadierte Löchriger-Eimer- Regulatoren sind. Zugriffsregulatoren werden in der Regel in herkömmlichen BISDN-Netzen verwendet, dies ist für die Ausübung der vorliegenden Erfindung jedoch unwesentlich. Es ist möglich, daß die Kommunikationsgeräte 105 direkt an die Knoten 110 in Fig. 1 angekoppelt sind.
Die Kommunikationsgeräte 105 kommunizieren mit jeweiligen anderen Kommunikationsgeräten 105 durch eine VC, die über bestimmte Knoten 110 hergestellt wird, und über Strecken 120 in dem Netz 100. Genauer gesagt ist es möglich, daß Informationen zwischen einleitenden und Ziel-Kommunikationsgeräten 105 übermittelt werden, indem das einleitende Gerät 105 anfordert, daß ein VC-Weg zum Führen der Verbindung zwischen den bestimmten Geräten 105 hergestellt wird. Zum Beispiel enthält ein möglicher Weg zum Führen oder Lenken einer Verbindung aus einem Kommunikationsgerät 105A zu einem Ziel-Kommunikationsgerät 105B die Knoten 111, 112, 113 und 114 und die Strecken 121, 122 und 123.
Der bestimmte gewählte Weg zum Lenken einer VC durch das Netz 100 erfordert, daß die enthaltenen Knoten 110 und Strecken 120 über ausreichend verfügbaren Pufferspeicher und ausreichend verfügbare Streckenbandbreite verfügen, um eine solche VC zu lenken. Bevor die angeforderte VC gelenkt werden kann, müssen der Knoten-Pufferspeicherplatz und die Streckenbandbreite bestimmt werden, um einen Weg mit ausreichenden Betriebsmitteln zur Erfüllung dieser Anforderungen zu wählen. Wie bei herkömmlichen Knoten ist es möglich, daß mehr als eine VC durch einen einzigen Ausgangsport des Knotens 110 hergestellt wird. Die konkrete Technik zur Herstellung einer VC ist für die Ausübung der Erfindung nicht wesentlich, und es ist möglich, eine beliebige von vielfältigen Techniken zu verwenden, darunter zum Beispiel aus den eigenen US- Patenten Nr. 5,519,836 und 5,502,816 bekannte Techniken.
Ein mit der Erfindung verwendbarer beispielhafter Mehrfachportknoten 110 ist in Fig. 2 gezeigt. Beispielhafte Bauelemente für die abgebildeten Knotenbauelemente in Fig. 2 können die in den zuvor aufgeführten handelsüblichen ATM-Datenvermittlungen verwendeten sein. Der Knoten 110 von Fig. 2 enthält eine Vielzahl von Eingangsports 210 und Ausgangsports 220, die mit jeweiligen Netzstrecken 120 in Fig. 1 verbunden sind. Es ist möglich, daß die Anzahl von Ports 210 und 220 in der Größenordnung von mehreren Hundert liegt. Die Ports 210 und 220 sind außerdem an eine Eingangs/Ausgangs-Satzbaugruppe (E/A-Satzbaugruppe) 200 angekoppelt, die durch eine Steuerung 230 gesteuert wird.
Die Steuerung 230 liefert eine Verbindungsannahme-Steuerung (CAC), die auf Anforderungen zur Herstellung von Wegen aus konkreten Eingangsports 210 zu konkreten Ausgangsports 220 zur Bereitstellung eines konkreten Segments einer VC zum Führen von Paketen über das Netz 100 reagiert. Jeder Port 210 und 220 in dem Mehrfachportknoten 100 kann in der Regel Verbindungen mindestens eines spezifischen Prioritätswerts lenken. Die Steuerung 230 und die E/A-Baugruppe 200 sind außerdem an einen Pufferspeicher 240 angekoppelt, durch den der Knoten 110 vorübergehend empfangene Daten für bestimmte durch einen Ausgangsport 220 gelenkte Verbindungen speichern kann. Für den Pufferspeicher 240 kann Direktzugriffsspeicher (RAM) verwendet werden.
Durch die Knotenanordnung in Fig. 2 können verschiedene, an einem oder mehreren Eingangsports 210 empfangene Pakete durch Ausgangsports 220 hindurch auf eine einzelne Netzstrecke 120 gelenkt und multiplexiert werden. Auf ähnliche Weise können durch diese Anordnung verschiedene Pakete, die an einem einzelnen Eingangsport 210 empfangen werden, durch zwei oder mehr Ausgangsports 220 hindurch auf jeweilige Netzstrecken 120 gelenkt und demultiplexiert werden. Das Multiplexieren und Demultiplexieren der Pakete, die über die Strecken 120 gesendet und/oder empfangen werden, kann zum Beispiel durch die Baugruppe 200 durch die Steuerung 230 gesteuert durchgeführt werden.
Obwohl die Kommunikationsstrecken 120 direkt entweder an Eingangs- oder Ausgangsports angekoppelt sind, können die Strecken 120 als Alternative ein solches Ankoppeln bereitstellen, indem sie Vermittlungsnetze zwischen den Strecken 120 und den Ports 210 und 220 verwenden. Die konkrete verwendete Anordnung zum Ankoppeln der Ports 210 und 220 und der Netzstrecken 120 ist für die Ausübung der Erfindung jedoch nicht wesentlich. Zum Beispiel können bei der Erfindung als Alternative Knoten mit Ports, die Informationen senden und empfangen können, verwendet werden. Außerdem können anstelle der Baugruppe 200 zur Durchführung der gewünschten Multiplexierung und Demultiplexierung (siehe Fig. 3) auch Demultiplexer 250 und/oder Multiplexer 260 verwendet werden, die zwischen die jeweiligen Eingangs- und Ausgangsports 210 und 220 und die Strecken 120 geschaltet und durch die Steuerung 230 gesteuert werden. Der Klarheit halber sind ähnliche Bauelemente in Fig. 2 und 3 gleich beziffert, wie zum Beispiel die Steuerung 230 und die Ports 210 und 220.
In typischen ATM-Paketvermittlungsnetzen wie zum Beispiel BISDN-Netzen ist es möglich, VCs zum Senden von Datenpaketen mehrerer verschiedener Informationstypen herzustellen. Solche Informationstypen weisen häufig verschiedene jeweilige Empfindlichkeiten gegenüber Verzögerung oder Regelmäßigkeit des Empfangs entsprechender Datenpakete durch ein Zielgerät auf. Eine Informationsempfindlichkeit gegenüber Regularität des Empfangs betrifft das ungefähre Ausmaß, zu dem der Empfang entsprechender Datenpakete von Periodizität abweicht. Zum Beispiel ist es bei herkömmlichen ATM-Systemen möglich, VCs zum Senden von Datenpaketen herzustellen, die jeweilige Informationstypen von Datenpaketen mit konstanter Bitrate (CBR), wie zum Beispiel für Sprach- oder Audiodaten, Pakete mit echtzeitvariabler Bitrate (RT-VBR) für Videodaten, wie zum Beispiel Videokonferenzen, Pakete mit nicht-echtzeitvariabler Bitrate (NRT-VBR), wie zum Beispiel für Standbilddaten, Pakete mit verfügbarer Bitrate (ABR), wie zum Beispiel für relativ verzögerungsunempfindlichen Text, und Pakete mit unspezifizierter Bitrate (UBR) darstellen.
In Fig. 2 und 3 kann der Pufferspeicher 240 den Knoten 110 aktivieren, um jeweilige zulässige Verzögerungen und Regularität verschiedener Informationstypen beim Führen von Datenpaketen zu ihren Bestimmungsorten ausnutzen, indem er vorübergehend Pakete in einem warteschlangenartigen Verfahren speichert, die aus einem Eingangsport 210 empfangen werden, und schließlich durch einen Ausgangsport 220 hindurch lenkt, während andere Pakete geführt werden. Eine solche selektive Pufferspeicherung ermöglicht eine relativ hohe Paket-Führungskapazität für den Knoten 110. Die Steuerung 230 liefert außerdem ein Pufferspeichermanagement für den Pufferspeicher 240. Die Steuerung 230 verwendet eine Ablaufsteuerungsschablone zur Bestimmung der Reihenfolge, in der Datenpakete aus den Warteschlangen über eine oder mehrere der mehreren Strecken 120 gemäß jeweiliger hergestellter VCs gesendet werden sollen.
Darstellungen dreier verschiedener beispielhafter Ablaufsteuerungsschablonen 300, 310 und 320, die der Knoten 110 von Fig. 2 und 3 verwenden kann, sind in Fig. 4A, 4B und 4C gezeigt. Die Schablonen 300, 310 und 320 benennen die Ablaufsteuerungsreihenfolge zum Senden von Datenpaketen für vier verschiedene Signalklassen, die vier verschiedene hergestellte VCs durch den Knoten 110 darstellen, die durch die Darstellungen A, B, C und D angezeigt werden. Jede Ablaufsteuerung 300, 310 und 320 besitzt lediglich als Beispiel sechzehn Schlitze 330, und es sind Ablaufsteuerungsschablonen mit einer größeren oder kleineren Anzahl von Schlitzen ebenfalls verwendbar.
Schlitzpositionen in jeder Schablone 300, 310 und 320 werden durch die Bezugszahlen 335 bezeichnet.
Bei dem abgebildeten Beispiel beträgt das Verhältnis von Paketen, die über eine Zeiteinheit gesendet werden sollen, zum Senden von sechzehn Paketen für die vier verschiedenen Klassen A, B, C und D jeweils 6 : 3 : 5 : 2. Solche Verhältnisse können zum Beispiel gemäß den Verzögerungs- oder Jitter- Empfindlichkeiten der jeweiligen Klassen und Bandbreitenanforderungen der jeweiligen virtuellen Leitungen bestimmt werden. Die Reihenfolge, in der die Klassendarstellungen in den Schlitzen 330 der jeweiligen Schablonen 300, 310 und 320 erscheinen, ist die Reihenfolge, in der die Pakete durch den entsprechenden Knoten 110 von Fig. 2 oder 3 gesendet werden. Somit ist die Reihenfolge, in der Pakete gemäß der Ablaufsteuerungsschablone 300 gesendet werden, sechs, die Klasse A darstellende Pakete in den Schlitzen 1 bis 6, dann drei, die Klasse B darstellende Pakete in den Schlitzen 7 bis 9, dann fünf, die Klasse C darstellende Pakete in den Schlitzen 10 bis 14 und dann zwei, die Klasse D darstellende Pakete in den Schlitzen 15 und 16. Die Folge der Schablone 300 wird dann nochmal für die nächsten sechzehn und nachfolgende Pakete wiederholt.
Eine solche Schablonenanordnung ist jedoch nicht sehr vorteilhaft, wenn etwaige der Klassen relativ empfindlich gegenüber Verzögerungen oder Verzögerungsschwankungen durch das Empfangsgerät sind. Die Übertragung von sechs Paketen für die Klasse A und dann eine Pause von einem Intervall, das der Übertragung von zehn Paketen entspricht, für andere VCs oder Signalklassen vor der Übertragung weiterer sechs Pakete der Klasse A liefert relativ lange Verzögerungen von zehn Paketübertragungen vor Stoß von sechs Paketübertragungen der Klasse A. Solche Verzögerungen zwischen Stößen von Paketen sind für relativ verzögerungsempfindliche oder regularitätsempfindliche Informationen, wie zum Beispiel CBR in herkömmlichen ATM-Netzen, im allgemeinen unerwünscht. Somit ist es wünschenswert, eine Ablaufsteuerungsschablonenschlitzanordnung zu identifizieren, die in bezug auf die Verzögerungsschwankungs- und Regularitätsempfindlichkeit der zu sendenden Klassen vorteilhaft ist.
Wenn zum Beispiel die Klassen A, B, C und D der Übertragung von ATM-Informationen wie zum Beispiel den Informationstypen CBR, RT-VBR, NRT-VBR bzw. UBR entsprächen, dann wäre die Reihenfolge der Priorität im Hinblick auf Verzögerungs- oder Regularitätsempfindlichkeit Klassen A, B, C und D. Die Klassen A, B, C und D stellen lediglich als Beispiel vier verschiedene Informationstypen dar und sollen keine Einschränkung der Erfindung bedeuten. Es ist möglich, vorteilhafte Ablaufsteuerungsschablonenanordnungen gemäß der Erfindung zu bestimmen, wenn eine oder mehrere der Klassen Kommunikationssignale oder Datenpakete für mehr als eine virtuelle Leitung desselben oder ähnlichen Informationstyps darstellt. Zu beispielhaften ähnlichen Informationstypen würden UBR und ABR gehören, die durch dieselbe Klasse in einer Schablone darstellbar sind.
Die Ablaufsteuerungsschablone 310 von Fig. 4B stellt eine verbesserte Ablaufsteuerungsreihenfolge für solche Klassen in bezug auf die Schablone 300 von Fig. 4A dar. Die Anordnung in Schlitzpositionen 1 bis 8 ist A, B, C, D, A, B, C und D. Obwohl Datenpakete für jede Informationsklasse vorteilhafterweise in den ersten acht Schlitzen 335 gleich beabstandet sind, ist dies für die letzteren acht Schlitze 335 nicht der Fall. Die Ablaufsteuerungsschablone 320 von Fig. 4C besitzt eine weitere verbesserte Anordnung in bezug auf die Schablone 310 von Fig. 4B, wobei die Klasse A mit der höchsten Empfindlichkeit gegenüber Verzögerung im wesentlichen in den sechzehn Schlitzen gleich beabstandet ist. Schlitzpositionen für die Klasse B werden zum höchstmöglichen Grad in den Schlitzen 335, die nicht der Klasse A zugewiesen sind, weiter getrennt. Die Klassen C und D, die NRT-VBR und UBR/ABR darstellen, besitzen die niedrigste Priorität in bezug auf Verzögerungsempfindlichkeit und werden in einer beliebigen Reihenfolge den übrigen Schlitzen zugewiesen. Die Verfahren ermöglichen eine Bestimmung vorteilhafter Schablonenablaufsteuerungsanordnungen wie zum Beispiel die der Schablone 320 von Fig. 4C auf relativ schnelle Weise.
Fig. 5 zeigt eine Technik 400 zur Bestimmung einer vorteilhaften Schablone aus einer Vielzahl von Anwärterschablonen. In Fig. 5 wird eine Vielzahl möglicher Anwärterschablonen im Schritt 410 identifiziert. Es ist möglich, diese Vielzahl von Anwärterschablonen auf der Grundlage eines Auswahlkriteriums zu identifizieren oder auszuwählen, wie zum Beispiel das Auswählen von Anwärterschablonen mit im wesentlichen zufälliger Anordnung oder bestimmter Anordnung auf der Grundlage von Signalklassenpriorität. Das konkrete zur Bestimmung der Vielzahl von Anwärterschablonen verwendete Kriterium ist für die Ausübung des Verfahrens 400 jedoch nicht wesentlich, und es können auch andere Routinen zur Bereitstellung der Vielzahl von Anwärterschablonen verwendet werden.
Danach wird gemäß Schritt 420 für jede der identifizierten Vielzahl von Anwärterschablonen ein Regularitätsmaß bestimmt. Das Regularitätsmaß ist ein Maß der Übertragungsregularität oder des Ausmaßes der periodischen Übertragungen von Datenpaketen für jeweilige Signalklassen, das durch die jeweilige Anwärterschablone erzeugbar ist. Ein beispielhaftes Verfahren 500 zur Bestimmung eines solchen Regularitätsmaßes ist in der nachfolgend beschriebenen Fig. 6 gezeigt. Nach der Bestimmung der Regularitätsmaße für die Vielzahl von Schablonenanwärtern im Schritt 420 von Fig. 5 wird im Schritt 430 die Anwärterschablone mit dem niedrigsten Regularitätsmaß bestimmt und zur Übertragung von Datenpaketen verwendet.
Obwohl das Verfahren 400 die Anwärterschablone mit dem niedrigsten Regularitätsmaß zur Verwendung bei der Bestimmung der Reihenfolge bei der Übertragung von Datenpaketen auswählt, kann man als Alternative die Anwärterschablone verwenden, die ein im wesentlichen wünschenswertes Regularitätsmaß aufweist, wie zum Beispiel ein Maß, das relativ nahe bei dem niedrigsten Maß liegt. Darüber hinaus ist es möglich, das Regularitätsmaß für weniger als die Gesamtheit der Vielzahl von Anwärterschablonen zu bestimmen. Zum Beispiel ist es möglich, das Regularitätsmaß einer ausreichenden Anzahl von Anwärterschablonen zu bestimmen, um die erste mit einem Regularitätsmaß zu identifizieren, das einen wünschenswerten Schwellenwert erfüllt.
Fig. 6 zeigt ein beispielhaftes Verfahren 500 zur Bestimmung eines Regularitätsmaßes einer Anwärter- Ablaufsteuerungsschablone zur Verwendung im Schritt 420 von Fig. 5. Das Verfahren 500 bestimmt das Regularitätsmaß einer Anwärter-Ablaufsteuerungsschablone auf der Grundlage eines Gesamtwerts von Summierungen von Funktionen von Positionsabständen zwischen den Schlitzpositionen, die jeweiligen Signalklassen zugewiesen sind. Zum Beispiel ist in der Anwärter-Ablaufsteuerungsschablone 320 von Fig. 4C die Positionsabstände zwischen den Schlitzen, die der Klasse A zugewiesen sind, 2, 3, 3, 2, 3 und 3 der Reihe nach von links nach rechts. In dieser Summierung ist eine "Umkehrungs"-Positionsdistanz zwischen dem letzten. Auftreten eines der Klasse A, Schlitzposition 14, zugewiesenen Schlitzes und dem ersten Auftreten eines der Klasse A, Schlitzposition 1, zugewiesenen Schlitzes enthalten, bei der es sich um die Positionsdistanz von 3 handelt. Es ist vorteilhaft, diese "Umkehrungs"- Positionsdistanz in das Regularitätsmaß aufzunehmen, weil Schablonen zum Senden von Datenpaketen auf eine zyklische Weise verwendet werden, so daß nach dem Senden der ersten 16 Datenpakete gemäß der Schablone 320 die Übertragung des siebzehnten Datenpakets die Übertragung einer Signalklasse wäre, die der Ablaufsteuerungsschlitzposition 1 entspricht.
Außerdem kann dieser Gesamtwert von Summierungen des Regularitätsmaßes weiterhin die Positionsdistanzen zwischen den n-ten Vorkommnisse von Schlitzpositionen in der Folge von Schlitzpositionen, die den jeweiligen Klassen zugewiesen sind, für mindestens ein n größer oder gleich 2 enthalten. Solche Summen des n-ten Auftretens werden nachfolgend als Alternative als Summierungen höherer Ordnung bezeichnet. Zum Beispiel ist eine Distanz zweiter Ordnung für die Signalklasse A in Fig. 4C jeweils 5, 6, 5, 5, 6, 5. Die letzte Distanz in diesen Distanzen zweiter Ordnung enthält vorteilhafterweise eine "Umkehrungs"-Positionsdistanz von 5. Für die jeweiligen Summierungen der bestimmten Signalklassen sind Gewichtungskoeffizienten verwendbar, um die Signifikanz bzw. das Gewicht, die bzw. das Schlitzpositionen jeweiliger Signalklassen gegeben wird, und/oder die Signifikanz der Summierungen höherer Ordnung zu vergrößern oder zu verkleinern. Der resultierende Gesamtwert von Summierungen zeigt das Ausmaß der Übertragungsregularität an, die mit der Anwärter- Ablaufsteuerungsschablone erzielbar ist. Relativ niedrige Regularitätsmaßwerte zeigen relativ hohe Werte der erzielbaren Regularität an.
Genauer gesagt werden gemäß dem Verfahren 500 von Fig. 6 zunächst im Schritt 505 mehrere Werte initialisiert. Insbesondere wird die Gesamtzahl von Signalklassen, die in der Anwärter-Ablaufsteuerungsschablone, die bewertet werden soll, dargestellt werden, einem Wert K zugewiesen; das Array Lk(k = 1 bis K) ist die Anzahl von Schlitzzuweisungen in der Schablone für die jeweiligen Klassen K; und das zweidimensionale Array Ck,l (k = 1 bis K), (l = 1 bis Lk-1) stellt Gewichtungskoeffizienten für die Signalklasse k und die Ordnung l dar. Außerdem wird im Schritt 505 der Summierungswert SUM und der Klassenwert k auf 0 bzw. 1 initialisiert.
In den Schritten 510 und 515 werden dann der Vorkommniswert l, der Ordnungswert n und die Vorkommnis- und Positionswerte X und Y folgendermaßen initialisiert: l = 1, n = 1, X = l + n und Y = 0. Im Schritt 520 schreitet das Verfahren dann, wenn der Offsetwert X kleiner oder gleich dem Gesamtwert der Schlitzzuweisungen Lk für die Signalklasse k ist, zum Schritt 530 fort, andernfalls wird der Schritt 525 durchgeführt, bevor das Verfahren 500 zum Schritt 530 fortfährt. Schritt 520 erkennt, wenn eine "Umkehrungs"- Positionsdistanz berechnet werden soll, und der Schritt 525 stellt den Vorkommnis-Offsetwert X und den Schlitzpositions-Offsetwert Y entsprechend ein. Im Schritt 530 wird die Positionsdistanz P zwischen dem 1-ten und 1-ten Auftreten von Schlitzzuweisungen zu der Signalklasse k bestimmt.
Wenn die Werte l und n beide eins sind und der Wert Lk zwei oder größer ist, wird somit die Positionsdistanz P auf die Distanz zwischen dem ersten und zweiten Auftreten der Signalklasse k gesetzt. Dementsprechend ist die Positionsdistanz P zwischen dem ersten und zweiten Auftreten der Signalklasse A der Schablone 320 in Fig. 4C 2 (3-1). Im Schritt 530 von Fig. 6 bleibt der Positionsdistanz-Offsetwert Y bei der Bestimmung der Positionsdistanz P null, außer wenn eine "Umkehrungs"-Bestimmung erfolgt. In diesem Fall wird der Offset Y auf einen Wert gesetzt, der die Gesamtzahl von Schlitzpositionen darstellt. Nachdem im Schritt 530 ein Positionsdistanzwert P bestimmt wurde, wird eine streng konvexe Funktion dieses Distanzwerts berechnet. Eine Funktion F(x) ist streng konvex, wenn F (αx&sub1; + (1-α)x&sub2;) < αF(x&sub1;) + (1-α)F(x&sub2;), wobei 0 < α < 1 ist. Eine graphische Darstellung einer solchen Funktion hat eine konvexe Form. Die konkrete verwendete konvexe Funktion ist für die Ausübung der Erfindung nicht wesentlich. Konvexe Funktionen sind zum Beispiel PZ, wobei Z > 1; ZP, wobei Z > 1; und 1 / L - p, wobei L die Anzahl von Schablonen-Schlitzpositionen ist.
Der erzeugte Wert PZ wird dann durch den entsprechenden Gewichtungsfaktor skaliert und im Schritt 535 zu dem Summierungswert SUM addiert. Der Vorkommniswert l wird dann im Schritt 540 erhöht. Danach kehrt das Verfahren 500 im Schritt 545, wenn der erhöhte Vorkommniswert l kleiner oder gleich der Gesamtzahl von Vorkommnisse Lk in der Schablone für die Klasse k ist, zum Schritt 515 zurück, um die nächste Bestimmung der Positionsdistanz für die bestimmte Ordnung n und Signalklasse k durchzuführen, andernfalls fährt das Verfahren 500 zum Schritt 550 fort. Genauer gesagt fährt das Verfahren 500 zum Schritt 550 fort, wenn die Gesamtzahl von Positionsdistanzen der Ordnung n für die Signalklasse k summiert wurde und in die Summierung SUM einschließlich der entsprechenden "Umkehrungs"-Bestimmungen einbezogen wurde. Im Schritt 550 wird der Ordnungswert n erhöht.
Danach kehrt das Verfahren 500 im Schritt 555, wenn der erhöhte Ordnungswert n kleiner oder gleich der Gesamtzahl von Vorkommnisse Lk weniger eins in der Schablone für die Klasse k ist, d. h. der höchsten Reihenfolge für die bestimmte Klasse k, zum Schritt 515 zurück, um die nächste Bestimmung der Positionsdistanz für die erhöhte Ordnung n für die Signalklasse k durchzuführen, andernfalls fährt das Verfahren 500 zum Schritt 560 fort. Im Schritt 560 wird der Signalklassenwert k erhöht, und im Schritt 565 fährt das Verfahren 500, wenn der erhöhte Wert k größer als die Gesamtzahl von Signalklassen K ist, die in der Anwärterschablone dargestellt sind, zum Schritt 570 fort, andernfalls kehrt es zum Schritt 510 zurück, um Positionsdistanzen für Schlitzzuweisungen der nächsten Signalklasse in die Summierung SUM einzubeziehen. Im Schritt 570 enthält die resultierende Summierung SUM die gewichteten Summierungen der geordneten Positionsdistanzen zwischen Schlitzzuweisungen der jeweiligen Signalklassen und wird als das Regularitätsmaß bereitgestellt.
Somit bestimmt das Verfahren 500 zunächst die Positionsdistanzen einer bestimmten Ordnung n für eine Signalklasse k und führt dann die nächsten und nachfolgenden Ordnungsbestimmungen durch und führt dann diese Bestimmungen für die nächste Signalklasse durch. Die konkrete Folge von Schritten des Verfahrens 500 wurde nur als Beispiel gezeigt und soll keine Einschränkung der Erfindung darstellen. Es ist möglich, diese Schritte in einer anderen Reihenfolge oder auf parallele Weise durchzuführen. Außerdem sind zur Erzielung der gewünschten gewichteten Summierungen verschiedene Schritte verwendbar.
Das Verfahren 500 bestimmt das Regularitätsmaß auf der Grundlage gewichteter Summierungen aller Signalklassen, die in der Anwärter-Ablaufsteuerungsschablone dargestellt sind, und aller möglichen Ordnungen von Positionsdistanzen lediglich als Beispiel. Es ist jedoch möglich, ein Regularitätsmaß auf der Grundlage mindestens einer in der Ablaufsteuerungsschablone dargestellten Signalklasse zu bestimmen. Außerdem ist es möglich, eine Regularitätsmaßsummierung unter Verwendung der Summierung einer ersten Ordnung oder der Distanzen zwischen den Vorkommnisse von Schlitzpositionen, die der Signalklasse zugewiesen sind, sowie der Positionsdistanzsummierung mindestens einer höheren Ordnung zu bestimmen, wobei Distanzen zwischen n-ten Vorkommnisse von dieser Signalklasse zugewiesenen Schlitzpositionen gemessen werden. Ein solches Maß ist immer noch eine ausreichend gute Anzeige der Regularität einer Anwärterschablone zur Verwendung bei der Identifizierung von Schablonen für einen Knoten in einem Kommunikationsnetz.
Das Verfahren 400 von Fig. 5 bestimmt Ablaufsteuerungsschablonen, indem es vorteilhafterweise aus einer Vielzahl von Anwärterschablonen eine Schablone mit einem wünschenswerten Regularitätsmaß auswählt. Fig. 7 zeigt ein Verfahren 600 zur Bestimmung vorteilhafter Schlitzzuweisungen bei der Erzeugung einer wünschenswerten Ablaufsteuerungsschablone.
Bei der Durchführung des Verfahrens 600 sind die Anzahl von Schlitzen, die in der Schablone erforderlich sind, sowie die Anzahl benötigter jeweiliger Signalklassenpositionen, die zugewiesen werden sollen, bekannt.
Gemäß der vorliegenden Ausführungsform der Erfindung wird zur Herstellung eines Schwellen- Regularitätsmaßes eine Bezugs-Ablaufsteuerungsschablone verwendet. Untere Grenzen für Regularitätsmaße von Zwischenschablonen mit einer Anzahl von zugewiesenen und nicht zugewiesenen Schlitzen zu Signalklassen werden dann bestimmt. Wenn die Zwischenschablonen mit Teilzahlen zugewiesener Schlitze eine untere Grenze aufweisen, die größer als das Schwellenmaß der Bezugsschablone ist, dann würde keine Schlitzanordnung für die nicht zugewiesenen Schlitze der Zwischenschablone eine Ablaufsteuerungsschablone mit einem niedrigeren Regularitätsmaß als die Bezugsschablone ergeben. Als Folge können Schablonen mit den Zuweisungen einer solchen Zwischenschablone aus der weiteren Bewertung beseitigt werden.
Wenn eine Zwischenschablone identifiziert wird, die eine untere Grenze des Regularitätsmaßes aufweist, die niedriger als das Schwellen-Regularitätsmaß ist, dann wird als Alternative mindestens eine der nicht zugewiesenen Schlitzpositionen in solchen Zwischenschablonen einer jeweiligen Signalklasse zugewiesen, und es wird erneut eine Bestimmung und Bewertung einer unteren Grenze durchgeführt. Solch eine Routine wird systematisch wiederholt, bis alle Schlitze in der Zwischenschablone zugewiesen sind oder keine Schablone als eine untere Grenze aufweisend identifiziert wird, die niedriger als das Schwellen- Regularitätsmaß ist. Auf diese Weise bestimmt das Verfahren Ablaufsteuerungsschablonen mit vorteilhaften Regularitätsmaßen.
Dieses Verfahren basiert auf einer neuartigen und nicht offensichtlichen Bestimmung einer unteren Grenze eines Regularitätsmaßes der Zwischenschablonen, bei denen Teilzahlen von Schlitzpositionen festliegen oder jeweiligen Signalklassen zugeordnet sind. Die untere Grenze einer Zwischenschablone wird auf der Grundlage einer hypothetischen Zuweisung jeweiliger Teile der nicht zugewiesenen Schlitze zu verschiedenen Signalklassen bestimmt. Eine solche Teil-Schlitzzuweisung stellt vorteilhafterweise ein niedrigstes Regularitätsmaß oder eine untere Grenze dar, die überhaupt mit einer Schablone erzielt werden kann, die mindestens die Schlitzzuweisungen der Zwischenschablone aufweist. Obwohl Teil-Schlitzzuweisungen ein solches Maß mit unterer Grenze erzielen, können Zuweisungen ganzer Schlitze zu Signalklassen möglicherweise kein solches Maß erzielen. Nur in in der Regel seltenen Fällen würden ganze Schlitzzuweisungen die untere Grenze erzielen.
Es ist möglich, die Bestimmung der unteren Grenze durch Lösung eines quadratischen Programmierungsproblems durchzuführen, das die Zwischenschablone darstellt. Wie nachfolgend in bezug auf Fig. 7 beschrieben wird, ist es möglich, ein entsprechendes lineares Programm aus dem quadratischen Programmierungsproblem zu erzeugen, das leichter gelöst werden kann. Es können jedoch auch andere geeignete Verfahren zur Lösung des quadratischen Programmierungsproblems oder zur Darstellung der Zwischenschablone mit den hypothetischen Teil-Schlitzzuweisungen verwendet werden.
Zur Bestimmung einer Ablaufsteuerungsschablone mit einem wünschenswerten Regularitätsmaß auf der Grundlage der Bestimmungen der vorteilhaften unteren Grenzen von Zwischenschablonen können zahlreiche Verfahren verwendet werden. Das beispielhafte Verfahren 600 von Fig. 7 ist ein rechnerisch effizientes Verfahren zur Bestimmung einer Ablaufsteuerungsschablone mit einem im wesentlichen optimalen Regularitätsmaß für jeweilige Signalklassen und wird hier lediglich als Beispiel gezeigt. Andere Techniken, die Bestimmungen der unteren Grenze verwenden, sind zur Bestimmung von Ablaufsteuerungsschablonen mit vorteilhaften Regularitätsmaßen sowie von Schablonen mit im wesentlichen optimalen Regularitätsmaßen verwendbar.
In dem Verfahren 600 wird zunächst im Schritt 605 ein Schwellen-Regularitätsmaß bestimmt. Es ist möglich, das Schwellen-Maß als ein bestimmtes Regularitätsmaß einer Bezugsschablone mit vorteilhaften Schlitzzuweisungen zugrunde zu legen. Die Art und Weise der Auswahl der Bezugsschablone ist für die Ausübung der Erfindung nicht wesentlich und kann zum Beispiel eine zufällige Auswahl sein oder auf einem Kriterium wie zum Beispiel den zuvor in bezug auf das Verfahren 400 von Fig. 5 beschriebenen basieren. Die Auswahl einer Bezugsschablone mit einem relativ niedrigen Schwellen-Regularitätsmaß ermöglicht die Bestimmung einer Ablaufsteuerungsschablone durch das Verfahren 600 mit im Vergleich zu Bezugsschablonen mit höheren Regularitätsmaßen Verbesserter rechnerischer und Verarbeitungseffizienz. Dementsprechend ist es als Alternative möglich, daß das Schwellenmaß auf einen bekannten wünschenswerten Wert gesetzt wird, ohne aus einer Bezugsschablone bestimmt zu werden.
Nachdem im Schritt 605 das Schwellenmaß bestimmt wurde, werden die Listenkennung 1 und der Festschlitzpositionszähler k auf 1 bzw. 2 gesetzt (Schritt 610). Als nächstes wird im Schritt 615 eine durch den Bezug 1 bezeichnete erste Liste erzeugt, die Anzeiger für alle möglichen Zwischenschablonen mit verschiedenen anfänglichen Schlitzpositionszuweisungen von k Schlitzen zu denselben jeweiligen Signalklassen enthält. Eine Zwischenschablone ist insofern keine vollständige Schablone, als sie zwar die gewünschte Anzahl von Schlitzpositionen besitzt, aber nur eine begrenzte Anzahl von Schlitzen einer Klasse zugewiesen wird, was übrige Schlitze unzugewiesen läßt.
Der Wert k muß größer oder gleich 2 sein, und mindestens zwei der Schlitzzuweisungen müssen derselben Signalklasse zugewiesen sein. In diesem Beispiel wird der Wert k auf 2 initialisiert. Somit erfolgen die anfänglichen Schlitzzuweisungen im Schritt 615 zu derselben Klasse. Mit k = 2 anfänglichen zugewiesenen Schlitzen beträgt die Anzahl von in der Liste 1 dargestellten Zwischenschablonen ferner
wobei der Wert P die Gesamtzahl von Schlitzen ist, die in der resultierenden Schablone enthalten sind. Die Verwendung von k = 2 anfänglichen Schlitzzuweisungen für die Zwischenschablonen dient lediglich als Beispiel, und es kann als Alternative eine große Anzahl anfänglicher Schlitzzuweisungen verwendet werden. Die Verwendung einer größeren Anzahl von anfänglichen Schlitzzuweisungen vergrößert jedoch die Anzahl der auf der Liste 1 dargestellten Zwischenschablonen, die ausgewertet werden müssen.
Nachdem im Schritt 615 die Liste 1 erzeugt wurde, fährt das Verfahren zum Schritt 620 fort. Im Schritt 620 fährt das Verfahren 600, wenn alle Zwischenschablonen in der Liste l ausgewertet wurden, z um Schritt 625 fort. Im Schritt 625 werden die Listenkennung l und der Festschlitzpositionszähler k beide erhöht, und im Schritt 630 kehrt das Verfahren 600, wenn der Festschlitzpositionszähler k kleiner oder gleich der Gesamtzahl von Schlitzen minus eins (P-1) ist, zum Schritt 620 zurück, andernfalls endet das Verfahren 600. Die Schritte 625 und 630 werden nachfolgend ausführlicher beschrieben. Wenn noch nicht alle Zwischenschablonen in der Liste l ausgewertet wurden, fährt das Verfahren 600 als Alternative im Schritt 620 zum Schritt 635 fort. Man beachte, daß in einer ersten Iteration des Verfahrens 600 keine der Zwischenschablonen auf der Liste 1 ausgewertet wurden, so daß das Verfahren vom Schritt 620 zum Schritt 635 fortfahren würde.
Im Schritt 635 wird eine Zwischenschablone Tk aus der Liste l, die noch nicht durch das Verfahren 600 ausgewertet wurde, ausgewählt, und im Schritt 640 wird die untere Grenze eines Regularitätsmaßes für diese Zwischenschablone Tk bestimmt. Die untere Grenze stellt ein niedrigstes Regularitätsmaß dar, das überhaupt mit einer Schablone mit mindestens den Schlitzzuweisungen der Zwischenschablone Tk erzielt werden könnte. Die untere Grenze für das Regularitätsmaß der Zwischenschablone Tk basiert vorteilhafterweise auf den zugewiesenen Schlitzen und einer hypothetischen Zuweisung von Teilen der jeweiligen nicht zugewiesenen Schlitzpositionen zu verschiedenen Signalklassen, anstelle der Begrenzung der Zuweisung eines Schlitzes zu einer einzigen Klasse. Diese Teil-Schlitzzuweisung erzeugt ein Regularitätsmaß, das besser oder gleich einem entsprechenden Regularitätsmaß auf der Grundlage der Zuweisung eines ganzen Schlitzes zu einer bestimmten Signalklasse ist, und wird deshalb als eine untere Grenze betrachtet.
Ein beispielhaftes Verfahren zur Bestimmung der unteren Grenze ist wie folgt. Ablaufsteuerungsschablonen können zum Beispiel aus einer Darstellung eines quadratischen ganzzahligen Zuweisungsproblems auf der Grundlage des Regularitätsmaßes bestimmt werden. Zum Beispiel erzeugt ein im wesentlichen minimales H(x) in dem folgenden quadratischen Zuweisungsausdruck für ein Regularitätsmaß ein im wesentlichen optimales Regularitätsmaß:
wobei xi1j1 und xi2j2 die jeweiligen Zuweisungen der bestimmten Signalklassen darstellen und einen ganzzahligen Wert von 0 oder 1 aufweisen, dij die gewünschte konvexe Funktion der Positionsdistanz zwischen i und j darstellt, die für das Regularitätsmaß wie zuvor in bezug auf Fig. 5 beschrieben verwendet wird, und fij die konkreten gewichteten Werte der konkreten verwendeten Positionsdistanzreihenfolgen darstellt.
Ein solches quadratisches ganzzahliges Zuweisungsproblem ist rechnerisch schwierig zu lösen, kann aber in einen linearen, ganzzahligen Programmierungsausdruck transformiert werden. Die Ganzzahl-Anforderungen von xi1j1 und xi2j2 werden dann gelockert, um Teil-Schlitzzuweisungen zu ermöglichen, so daß
j = 1, ..., P und 0 ≤ xij ≤ 1 ist, um das lineare ganzzahlige Programm in ein stetiges lineares Programm umzusetzen, das ohne weiteres lösbar ist, um die untere Grenze des Regularitätsmaßes bereitzustellen. Das Lösen quadratischer Zuweisungsprobleme unter Verwendung linearer Programmierungsprobleme wird ausführlicher bei zum Beispiel M. G. C. Resende, K. G. Ramaskrishnan und Z. Drezner, "Computing Lower Bounds for Quadratic Assignment Problem with an Interior Point Algorithm for Linear Programming", Operations Research, Band 43, Nr. 5, S. 781-791 (Sept.-Okt. 1995) beschrieben.
Nachdem im Schritt 640 die untere Grenze für die Zwischenschablone Tk bestimmt wurde, schreitet das Verfahren 600 zum Schritt 645 fort. Wenn die bestimmte untere Grenze größer oder gleich dem Schwellen- Regularitätsmaß ist, dann ist im Schritt 645 bekannt, daß eine Ablaufsteuerungsschablone mit den Schlitzzuweisungen der Zwischenschablone Tk kein niedrigeres Regularitätsmaß als das der Bezugsschablone erzielen konnte, unabhängig von den Zuweisungen der nicht zugewiesenen Schlitze der Zwischenschablone. Bei einer solchen Bestimmung kehrt das Verfahren 600 zum Schritt 620 zurück, um eine weitere Zwischenschablone 2%, aus der Liste 1 auszuwählen und auszuwerten.
Wenn im Schritt 645 die untere Grenze einer Zwischenschablone 2%, größer als das Schwellen- Regularitätsmaß ist, konnten somit die Schlitzzuweisungen der Zwischenschablone Tk keine Ablaufsteuerungsschablone mit einer besseren Übertragungsregularität als die Bezugsschablone erzeugen. Demzufolge ist keine weitere Auswertung von Schablonen mit den Schlitzzuweisungen dieser Zwischenschablone Tk erforderlich, und das Verfahren 600 kehrt zum Schritt 620 zurück, um eine neue Zwischenschablone auszuwerten. Wenn die bestimmte untere Grenze im Schritt 645 kleiner als das Schwellen- Regularitätsmaß ist, dann könnte als Alternative eine Schablone mit den Schlitzzuweisungen der Zwischenschablone Tk existieren, die ein niedrigeres Regularitätsmaß als das Schwellenmaß besitzt, und das Verfahren 600 führt die Schritte 650 bis 670 durch, um diese Bestimmung durchzuführen.
Im Schritt 650 werden dann Darstellungen aller möglichen verschiedenen Zwischenschablonen mit Schlitzzuweisungen, die der Zwischenschablone Tk entsprechen, und mit einer zusätzlichen Schlitzzuweisung dann an eine Liste 1+1 angehängt. Da von der Anzahl von Zwischenschablonen, die in der Liste 1 dargestellt sind, im Schritt 645 bestimmt wird, daß sie eine untere Grenze von weniger als dem Schwellenmaß aufweisen, würde jedoch die Anzahl nachfolgender Zwischenschablonen, die im Schritt 650 an die Liste 1+1 angehängt werden, entsprechend zunehmen.
Nachdem im Schritt 650 Darstellungen an die Liste 1+1 angehängt wurden, werden die nicht zugewiesenen Schlitze in der Zwischenschablone Tk im Schritt 655 gemäß einem Kriterium jeweiligen Signalklassen zugewiesen, um eine Anwärterschablone Tk* zu erzeugen. Das verwendete Kriterium zur Herstellung solcher Schlitzzuweisungen ist für die Ausübung der Erfindung nicht wesentlich, und kann zum Beispiel ein im wesentlichen zufälliges oder auf der Priorität der Regularität der Signalklassen oder anderen Hybrid- Ansätzen basierendes Zuweisen umfassen.
Im Schritt 660 wird dann für die Prüfschablone Tk* ein Regularitätsmaß R bestimmt. Wenn das bestimmte Maß R im Schritt 665 größer oder gleich dem Schwellen- Regularitätsmaß ist, kehrt das Verfahren 600 zum Schritt 620 zurück, um die Auswertung einer nächsten, in der Liste 1 dargestellten Zwischenschablone zu beginnen. Wenn das bestimmte Maß R im Schritt 665 jedoch kleiner als das Schwellenmaß ist, dann wird die Bezugsschablone und das entsprechende Schwellen- Regularitätsmaß im Schritt 670 durch die Prüfschablone Tk* und das Regularitätsmaß R ersetzt, bevor das Verfahren 600 zum Schritt 620 zurückkehrt, um die nächste Zwischenschablone auszuwerten.
Auf diese Weise wertet das Verfahren 600 alle Zwischenschablonen aus, die in der Liste l = 1 dargestellt sind, indem es die Schritte 620 bis 670 durchführt. Wenn das verwendete Schwellen-Regularitätsmaß der Bezugsschablone ein relativ niedriger Wert ist, dann würde in der Regel eine große Anzahl der Auswertungen der Zwischenschablonen, die in der Liste l dargestellt sind, nur die Berechnung ihrer unteren Grenze und die Bestimmung, daß diese untere Grenze größer als das Schwellenmaß ist (Schritte 640 und 645) umfassen, bevor zum Schritt 620 zurückgekehrt wird, um eine nächste Zwischenschablone in der Liste l = 1 zu verarbeiten. Für diejenigen, in der Liste l = 1 dargestellten Zwischenschablonen, die einen unteren Grenzwert von weniger als dem Schwellenmaß aufweisen, werden jedoch Darstellungen der entsprechenden anderen Zwischenschablonen mit einer zusätzlichen zugewiesenen Schlitzposition im Schritt 650 an eine Liste l+1 = 2 angehängt, bevor das Verfahren 600 zum Schritt 620 zurückkehrt, um eine nächste Zwischenschablone in der Liste l = 1 zu verarbeiten.
Außerdem wird in den Schritten 655 und 660 für diejenigen Zwischenschablonen, die als eine untere Grenze von weniger als das Schwellenmaß aufweisend identifiziert wurden, ein erster Versuch zur Erreichung einer entsprechenden Ablaufsteuerungsschablone Tk* mit einem niedrigeren Regularitätsmaß R als das Schwellenmaß durchgeführt. Wenn die erreichte Ablaufsteuerungsschablone Tk* ein niedrigeres Regularitätsmaß R aufweist, dann wird sie in den Schritten 665 und 670 für nachfolgende Iterationen des Verfahrens 600 beginnend mit dem Schritt 620 in die Bezugsschablone verwandelt, und ihr Regularitätsmaß R in das Schwellenmaß verwandelt. Ein solches Verfahren bewirkt, daß die Bezugsschablone in der Regel iterativ mit zunehmend niedrigeren Schwellen-Regularitätsmaßen geändert wird, wodurch größere Zahlen von Zwischenschablonen nur durch die Schritte 620 bis 645 ausgewertet werden, um eine wünschenswerte Verarbeitungseffizienz bei der Bestimmung einer im wesentlichen optimalen Ablaufsteuerungsschablonen- Schlitzanordnung zu erzielen.
Ferner schreitet das Verfahren 600 im Schritt 620 bei der Erkennung, daß alle möglichen Zwischenschablonen in der l = 1 ausgewertet wurden zum Schritt 625 fort, in dem der Listenzeiger l = 1 und der zugewiesene Schlitzzähler k = 2 auf 2 bzw. 3 erhöht werden. Wenn im Schritt 630 der zugewiesene Schlitzzähler k kleiner oder gleich der Anzahl von gesamten Schlitzpositionen weniger 1 (P-1) ist, dann schreitet das Verfahren 600 zum Schritt 620 fort, um dann alle Anwärterschablonen in der gebildeten Liste l = 2 zu verarbeiten, die Zwischenschablonen mit k = 3 zugewiesenen Schlitzpositionen enthält. Diese Verarbeitung wird fortgesetzt, bis alle Schlitzpositionen bestimmt sind. Man beachte, daß das Verfahren 600 im Schritt 630 endet, wenn alle bis auf einen der Schlitze zugewiesen sind, weil an diesem Punkt ein nicht zugewiesener Schlitz und eine nicht zugewiesene Signalklasse übrigbleiben.
Auf diese Weise bestimmt das Verfahren 600 eine Ablaufsteuerungsschablone mit einem im wesentlichen optimalen Regularitätsmaß durch effektive Auswertung aller möglichen Anwärterschablonen auf eine im wesentlichen rechnerisch effiziente Weise. Die rechnerische Effizienz kann weiter verbessert werden, indem entlang des Weges vom Schritt 630 zum Schritt 620 ein Schritt eingefügt wird, der etwaige verdoppelte Zwischenschabloneneinträge entfernt, die in einer jeweiligen Liste 1 auftreten könnten. Außerdem sind die Schritte 650 bis 670 wahlweise und können weggelassen werden, wenn nach dem Schritt 630 zusätzliche Schritte eingefügt werden, die die bestimmte der möglichen einen oder mehreren bestimmten Anwärterschablonen identifizieren, die ein niedrigstes Regularitätsmaß zur Verwendung bei der Übertragung von Kommunikationssignalen in dem Netz aufweist. Als Alternative könnte bei Identifizierung eine Anwärterschablone mit einem vorteilhaft niedrigen Regularitätsmaß, das zwar nicht das im wesentlichen optimale Regularitätsmaß ist, diese Schablone in dem Kommunikationsnetz verwendet werden, wenn sie einen gewünschten Grad der Regularität liefert.
Zu zusätzlichen Techniken zur Verbesserung der rechnerischen Effizienz gehört das Sortieren der in einer Liste 1 dargestellten Zwischenschablonen auf der Grundlage von Werten ihrer entsprechenden unteren Grenzen des Regularitätsmaßes. Eine solche resultierende Reihenfolge der sortierten Liste kann als die Reihenfolge des Auswertens solcher Zwischenschablonen verwendet werden. Es wurde festgestellt, daß die Auswertung dieser Zwischenschablonen mit höheren unteren Grenzen, die immer noch unter dem Schwellenmaß liegen, schnell Anwärterschablonen mit relativ niedrigen Regularitätsmaßen ergeben.
Außerdem kann das Verfahren 600 als eine Breitenauswertung angesehen werden, da alle möglichen Zwischenschablonen mit k zugewiesenen Schlitzen ausgewertet werden, bevor entsprechende Zwischenschablonen mit k+1 zugewiesenen Schlitzen ausgewertet werden. Es ist aber auch möglich, eine Tiefenauswertung durchzuführen, bei der Schablonen mit einer bestimmten gemeinsamen Zuweisung von k Schlitzen zu einer bestimmten Signalklasse mit verschiedenen anderen Schlitzpositionen vor der Auswertung von Schablonen mit einer verschiedenen gemeinsamen Zuweisung von k Schlitzen ausgewertet werden. Außerdem kann man auch einen hybriden Breite/Tiefe-Auswertungsansatz verwenden.
Es ist möglich, je nach Bedarf unmittelbar vorteilhafte Ablaufsteuerungsschablonen zu bestimmen oder als Alternative off-line eine Vielzahl von Schablonen für andere Verhältnisse erforderlicher Schlitze für Signalklassen zu erzeugen, die dann in einer Tabelle gespeichert werden. Wenn eine Schablone für ein bestimmtes Verhältnis erforderlicher Schlitze für Signalklassen erforderlich ist, kann dementsprechend schnell eine entsprechende Schablone aus einer solchen Tabelle identifiziert werden.
Obwohl mehrere Ausführungsformen der Erfindung oben ausführlich beschrieben wurden, können viele, im Schutzumfang der folgenden Ansprüche liegende Modifikationen vorgenommen werden.
Zum Beispiel ist es möglich, die Technik zur Identifizierung von Ablaufsteuerungsschablonen zur Ablaufsteuerung anderer Ereignisse, wie zum Beispiel der Übertragungsreihenfolge jeweiliger Kommunikationssignale in einem drahtlosen TDMA-Kommunikationsnetz oder die Verarbeitungsreihenfolge von Operationen/- Transaktionen in einem Mehrprozessorsystem zu verwenden.

Claims

1. Verfahren zur Identifizierung einer Ablaufsteuerungsschablone (400) für ein Netz (100), wobei in der Schablone eine Vielzahl von Schlitzen entsprechenden Signalklassen zugewiesen ist, wobei eine Anordnung der Schlitze eine sich wiederholende Ablaufsteuerungsreihenfolge für Ereignisse auf dem Netz anzeigt, bei dem:

a) mindestens zwei Schlitzpositionen einer bestimmten Signalklasse zugewiesen werden, um eine Zwischenschablone zu bilden (615);

b) eine untere Grenze eines Regularitätsmaßes für die Zwischenschablone bestimmt wird (640);

c) mindestens ein zusätzlicher Schlitz der Zwischenschablone einer Signalklasse der übrigen jeweils zuzuweisenden Signalklassen zugewiesen wird, wenn die bestimmte untere Grenze des Regularitätsmaßes vorteilhafter als der aktuelle Wert eines Schwellen- Regularitätsmaßes ist (650);

d) die Schritte b) und c) wiederholt werden, bis alle Schlitze in der Zwischenschablone zugewiesen sind, um eine Anwärter-Ablaufsteuerungsschablone bereitzustellen; und

e) ein Regularitätsmaß der Anwärterschablone bestimmt wird, und wenn es vorteilhafter als der aktuelle Wert des Schwellen-Regularitätsmaßes ist, die Anwärterschablone für das Netz verwendet wird (660).

2. Verfahren nach Anspruch 1, wobei der Schritt des Bestimmens der unteren Grenze des Regularitätsmaßes auf den Schlitzpositionszuweisungen in der Zwischenschablone und einer hypothetischen Teil-Schlitzzuweisung für übrige, nicht zugewiesene Schlitze an die jeweiligen zuzuweisenden Signalklassen basiert.

3. Verfahren nach Anspruch 2, wobei der Schritt des Bestimmens der unteren Grenze des Regularitätsmaßes auf einer Bestimmung durch lineares Programmieren basiert, die aus einem quadratischen, ganzzahligen Zuweisungsproblem abgeleitet wird.

4. Verfahren nach Anspruch 1, wobei das Regularitätsmaß der Anwärterschablone im Schritt e) für mindestens eine der Signalklassen das Bestimmen des Regularitätsmaßes auf der Grundlage einer Summierung von Werten umfaßt, die konvexe Funktionen von Positionsdistanzen zwischen Schlitzen darstellen, die derselben Signalklasse zugewiesen sind.

5. Verfahren nach Anspruch 4, wobei die Summierung eine erste Summierung, die auf Positionsdistanzen zwischen jedem Schlitz, der einer Signalklasse zugewiesen wurde, und einem entsprechenden nächsten Auftreten einer Schlitzzuweisung in der Folge von Schablonenschlitzen für diese Signalklasse basiert, und eine zweite Summierung, die auf Positionsdistanzen zwischen jedem Schlitz, der dieser Signalklasse zugewiesen wurde, und einem entsprechenden N-ten Auftreten einer Schlitzzuweisung in der Folge von Schablonenschlitzen für diese Signalklasse basiert, umfaßt, wobei N zwischen 2 und M-1 liegt und M ein Wert ist, der angibt, wie oft Schlitze dieser Signalklasse zugewiesen wurden.

6. Verfahren nach Anspruch 5, wobei die zweite Summierung auf der Grundlage jedes Werts von N zwischen 2 und M-1 durchgeführt wird.

7. Verfahren nach Anspruch 5, wobei die erste und die zweite Summierung für eine Vielzahl der Signalklassen durchgeführt werden und die jeweiligen erzeugten Summierungen auf der Grundlage der relativen Priorität gewünschter Regularität der entsprechenden Signalklasse skaliert werden.

8. Verfahren nach Anspruch 1, bei dem, wenn die bestimmte untere Grenze des Regularitätsmaßes im Schritt c) nicht vorteilhafter als das Schwellen- Regularitätsmaß ist, weiterhin

neue Schlitzpositionen Signalklassen zugewiesen werden, wobei mindestens zwei dieser Schlitzpositionen derselben Klasse zugewiesen werden; und

die Schritte b) und c) wiederholt werden.

9. Verfahren nach Anspruch 1, wobei das Schwellen- Regularitätsmaß ein Regularitätsmaß einer Bezugs- Ablaufsteuerungsschablone ist.

10. Verfahren nach Anspruch 9, wobei die Auswahl der Bezugs-Ablaufsteuerungsschablone auf einem Kriterium basiert.

11. Verfahren nach Anspruch 10, wobei die Bezugs- Ablaufsteuerungsschablone auf der Grundlage des Regularitätsmaßes aus einer Vielzahl von Schablonen ausgewählt wird.

12. Verfahren nach Anspruch 9, bei dem:

mögliche Anwärterschablonen auf der Grundlage von Zwischenschablonen bestimmt werden, die auf der Grundlage der unteren Grenzen ihres entsprechenden Regularitätsmaßes in einer sortierten Reihenfolge dargestellt werden;

Regularitätsmaße für die Anwärterschablone bestimmt werden; und

die Bezugs-Ablaufsteuerungsschablone durch die gebildete Anwärterschablone und das Schwellen-Maß durch das bestimmte Regularitätsmaß ersetzt werden.

13. Verfahren nach Anspruch 9, bei dem für eine Zwischenschablone mit einer unteren Grenze, die vorteilhafter als das Schwellen-Maß ist,

die übrigen, nicht zugewiesenen Schlitze in der Zwischenschablone gemäß einem Kriterium zugewiesen werden, um mindestens eine Anwärterschablone zu bilden; und

Regularitätsmaße für die Anwärterschablone bestimmt werden; und

die Bezugsschablone durch die gebildete Anwärterschablone und das Schwellen-Maß durch das bestimmte Regularitätsmaß ersetzt werden.

14. Verfahren nach Anspruch 1, bei dem mögliche Zwischenschablonen mit k Schlitzzuweisungen mit entsprechenden Regularitätsmaßen mit unterer Grenze bestimmt werden, die vorteilhafter als das Schwellen-Maß sind, bevor diese Bestimmung für Zwischenschablonen mit k+1 Schlitzzuweisungen vorgenommen wird, wobei k ≥ 2 ist.

15. Verfahren nach Anspruch 14, bei dem die möglichen Zwischenschablonen mit k Schlitzzuweisungen gemäß der unteren Grenze ihres Regularitätsmaßes sortiert werden.

16. Verfahren nach Anspruch 1, bei dem mögliche Anwärterschablonen auf der Grundlage einer bestimmten Zwischenschablone mit k anfänglichen Schlitzzuweisungen bestimmt werden, bevor mögliche Anwärterschablonen auf der Grundlage einer anderen Zwischenschablonen mit k Schlitzzuweisungen bestimmt werden, wobei k ≥ 2 ist.

17. Verfahren nach Anspruch 1, wobei das Verfahren durchgeführt wird, um eine jeweilige Vielzahl von Ablaufsteuerungsschablonen für verschiedene Signalklassenablaufsteuerungsanforderungen zu bestimmen, und eine der Vielzahl bestimmter Ablaufsteuerungsschablonen verwendet wird, wenn eine Kommunikationssignalübertragungsanforderung einer der entsprechenden Ablaufsteuerungsanforderungen entspricht.

18. Verfahren nach Anspruch 1, wobei eine Ablaufsteuerungsschablone in Abständen während des Betriebs des Netzes bestimmt wird.

19. Verfahren nach Anspruch 1, wobei das Netz ein Zeitmultiplexnetz mit Vielfachzugriff ist und für die Kommunikation zwischen einer Basisstation und drahtlosen Endgeräten eine Ablaufsteuerungsschablone verwendet wird.

20. Verfahren nach Anspruch 1, wobei die Ereignisse der Übertragung von Datenpaketen und die Signalklassen mindestens einer virtuellen Leitung in dem Netz entsprechen.

21. Verfahren nach Anspruch 20, wobei eine Ablaufsteuerungsschablone zur Verwendung in dem Netz identifiziert wird, wenn eine virtuelle Leitung hergestellt oder abgeschlossen wird.

22. Verfahren nach Anspruch 20, bei dem:

eine Vielzahl bestimmter Ablaufsteuerungsschablonen in einer Tabelle gespeichert wird; und

nach Bedarf zur Übertragung der Datenpakete der virtuellen Leitungen eine bestimmte Schablone identifiziert wird.

23. Verfahren nach Anspruch 1, wobei es sich bei den Ereignissen um die Verarbeitung von Operationen der durch die Signalklassen dargestellten Typen handelt.

24. Verfahren nach Anspruch 23, wobei die Verarbeitung von Operationen die Verarbeitung jeweiliger Transaktionen ist.

25. Knoten (110) zur Verwendung in einem Kommunikationsnetz (100) zum Übermitteln von Kommunikationssignalen über hergestellte virtuelle Leitungen durch den Knoten mit:

einer Eingangs/Ausgangs-Satzbaugruppe (200), die zur Verarbeitung von Kommunikationssignalen als ankommende und abgehende Signale an eine Vielzahl von Ports (210) angekoppelt ist, wobei die Satzbaugruppe zum Empfangen von ankommenden Kommunikationssignalen aus mindestens einem Eingangsport (210) und zum Senden von abgehenden Kommunikationssignalen durch mindestens einen Ausgangsport (220) dient;

einem Pufferspeicher (240) zum vorübergehenden Speichern von Kommunikationssignalen, die durch den Ausgangsport (220) geführt werden sollen; und

einer Steuerung (230), die zum Steuern der Satzbaugruppe zum Senden der Kommunikationssignale für jeweilige virtuelle Leitungen auf der Grundlage einer Ablaufsteuerungsschablone konfiguriert ist, wobei in der Schablone eine Vielzahl von Schlitzen entsprechenden virtuellen Leitungen zugewiesen ist, wobei eine Anordnung der Schlitze eine sich wiederholende Ablaufsteuerungsreihenfolge zur Übertragung von Kommunikationssignalen anzeigt, die den jeweiligen virtuellen Leitungen zugeordnet sind, wobei die Steuerung so ausgelegt ist, daß sie eine wünschenswerte Ablaufsteuerungs-Schlitzreihenfolge identifiziert, indem:

a) mindestens zwei Schlitzpositionen einer bestimmten Signalklasse zugewiesen werden, um eine Zwischenschablone zu bilden;

b) eine untere Grenze eines Regularitätsmaßes für die Zwischenschablone bestimmt wird;

c) mindestens ein zusätzlicher Schlitz der Zwischenschablone einer Signalklasse der übrigen jeweiligen zuzuweisenden Signalklassen zugewiesen wird, wenn die bestimmte untere Grenze des Regularitätsmaßes vorteilhafter als der aktuelle Wert eines Schwellen- Regularitätsmaßes ist;

e) ein Regularitätsmaß der Anwärterschablone bestimmt wird, und wenn es vorteilhafter als der aktuelle Wert des Schwellen-Regularitätsmaßes ist, die Anwärterschablone für das Netz verwendet wird.

26. Knoten nach Anspruch 25, wobei die Kommunikationssignale Datenpakete des asynchronen Transfermodus sind.

27. Knoten nach Anspruch 25, wobei die Bestimmung der unteren Grenze des Regularitätsmaßes auf den Schlitzpositionszuweisungen in der Zwischenschablone und einer hypothetischen Teil-Schlitzzuweisung für übrige, nicht zugewiesene Schlitze an die jeweiligen zuzuweisenden Signalklassen basiert.

28. Knoten nach Anspruch 25, wobei die Bestimmung des Regularitätsmaßes der Anwärterschablone im Schritt

e) für mindestens eine der Signalklassen auf einer Summierung von Werten basiert, die konvexe Funktionen von Positionsdistanzen zwischen Schlitzen darstellen, die derselben Signalklasse zugewiesen sind.