DE10148893A1 - Verteilte Übermittlung von Verkehrsströmen in Kommunikationsnetzen - Google Patents

Abstract

In einem Netzknoten ist pro aktuellem Verzweigungsmuster zumindest je eine Warteschlange vorgesehen. Dabei kann eine Warteschlange durchaus für mehrere Verteilungsfächer, die sich in diesem Knoten auf dasselbe Verzweigungsmuster abbilden, gemeinsam benutzt werden. Ankommende Pakete werden nach ihrer Zugehörigkeit zu einem bestimmten Verteilungsfächer (d. h. nicht nach der Zugehörigkeit zu einem bestimmten Flow innerhalb des Verteilungsfächers) unterschieden. Entsprechend werden sie in eine zugehörige Warteschlange eingetragen. Die Warteschlangen werden von den zum jeweiligen Verzweigungsmuster gehörenden Ports bedient. Sobald ein Port frei wird, wählt er die als nächstes von ihm zu bedienende Warteschlange aus. Die Auswahl beginnt so rechtzeitig, dass auf der abgehenden Leitung keine Lücke entsteht. Bedient ein Port mehrere (in diesem Falle sich ganz oder teilweise überlappende) Verzweigungsmuster, so wird bei dieser Auswahl zunächst über alle diese Verzweigungsmuster nach nicht leeren Warteschlangen gesucht. Werden dabei mehrere nicht leere Wartschlangen aus verschiedenen Verzweigungsmustern gefunden, so wird nach einem vorgegebenen Kriterium entschieden, welche Wartschlange als nächste bedient wird. Das aus dieser Warteschlange auszugebende Paket wird dann nach einem weiteren Kriterium bestimmt.

Description

• In einem Kommunikationsnetzen soll der Verkehr nach bestimmten Regeln möglichst gleichmäßig auf alle Knoten und Verbindungsleitungen im Kommunikationsnetz - auch "Netz" genannt - verteilt werden. Das Netz kann von der in der nicht vorveröffentlichten deutschen Patentanmeldung DE 101 49 349.9 offenbarten Art sein, deren Offenbarung durch Bezugnahme zum Inhalt der vorliegenden Beschreibung gemacht wird.
• Es ergibt sich bei dieser Art der Verteilung für jede Kommunikationsbeziehung von einem bestimmten Eingang A zu einem bestimmten Ausgang B ein sog. "Verteilungsfächer", der alle für diese Kommunikationsbeziehung sinnvoll nutzbaren Knoten und Verbindungswege umfasst (siehe Fig. 1). In einem entsprechend vermaschten Netz überlappen sich dabei zwangsläufig die Verteilungsfächer verschiedener Kommunikationsbeziehungen derart, dass an den einzelnen Knoten entweder identische oder sich teilweise überlappende oder aber auch völlig disjunkte "Verzweigungsmuster" entstehen (siehe Fig. 2). Die Überlappung hängt dabei von den in den Netzknoten zum Einsatz kommenden Verteilungsmechanismen ab.
• Bisher sind folgende Mechanismen zur individuellen Verteilung von Datenpaketen auf abgehende Bündel bekannt:
  
• 1. Einfache Verteilung des ankommenden Verkehrs auf ein abgehendes Bündel ohne Prioritäten:
  • a) Vorabverteilung des Verkehrs in individuelle Warteschlangen pro Port:
    Ein zentraler Verkehrsverteiler verteilt den ankommenden Verkehr auf einzelne Warteschlangen, von denen jeweils eine genau einem abgehenden Port des Bündels zugeordnet ist. Die Verteilung kann zyklisch oder (z. B. bei unterschiedlichen Port- Bandbreiten) gewichtet nach verschiedenen Kriterien erfolgen. Dabei kann z. B. auch der aktuelle Füllstand der einzelnen Warteschlangen (nach der Zahl der Pakete oder bei variablen Paketlängen nach der echten Datenmenge in Bytes) oder die individuelle Länge des aktuell zuzuteilenden Datenpaketes berücksichtigt werden. Die Ports bedienen die Warteschlangen in der Regel nach dem FIFO-Prinzip. Was einmal in einer Queue steht, muss dann auch vom zugeordneten Port abgearbeitet werden.
  • b) Verwendung einer einzigen Warteschlange mit einem Multi Server Prinzip:
    Eine günstige Verteilung des Verkehrs mit gleichzeitig optimaler Ausnutzung der verfügbaren Portkapazitäten kann mit dem Multi-Server-Prinzip erreicht werden. Dabei werden alle ankommenden Datenpakete in eine einzige Warteschlange eingereiht, aus der sich die Ports, wann immer sie frei sind bzw. frei werden, meist nach einem FIFO (First In First Out) Prinzip das nächste zu bedienende Paket abholen.
• 2. Verteilung des ankommenden Verkehrs auf ein abgehendes Bündel mit Prioritäten
  • a) Vorabverteilung des Verkehrs in individuelle Prioritäts-Warteschlangen pro Port:
    Ein zentraler Verkehrsverteiler verteilt den ankommenden Verkehr auf einzelne Warteschlangen, wobei für jeden abgehenden Port pro Prioritätsklasse jeweils eine individuelle Warteschlange bereitgestellt wird. Die Varianten gemäß 1 (a) sind analog anwendbar. Bei der Bedienung der Warteschlangen berücksichtigen die Ports die Prioritäten nach entsprechenden Regeln ("strikt", "gewichtet" usw.)
  • b) Multi Server Prinzip mit je einer Warteschlange pro Prioritätsklasse:
    Wie 1 (b), wobei die höherprioren Warteschlangen entsprechend der Prioritätsregeln bevorzugt bedient werden.
• 3. Verteilung des ankommenden Verkehrs auf ein abgehendes Bündel mit prioritätsgesteuertem Per Flow Queueing:
  Eine Verfeinerung der oben beschriebenen elementaren Mechanismen besteht darin, zur granulareren Unterscheidung und Priorisierung zwischen verschiedenen individuellen Kommunikationsbeziehungen (Flows) auch individuelle und separate Queues per Flow einzurichten. Damit wird jedoch der Aufwand für Queueing (wg. Zahl der Warteschlangen) und Scheduling (wg. Auswahl des nächsten auszugebenden Paketes aus der Vielzahl der Warteschlangen) um ein Vielfaches erhöht und sehr viel mehr von den Verkehrsmustern (d. h. Zahl der gleichzeitig aktiven Flows) abhängig. Zusätzlich muss dabei auch auf eine faire Verteilung der Ressourcen zwischen gleich priorisierten Flows geachtet werden, wofür spezielle Mechanismen wie z. B. "Weighted Fair Queueing" (WFQ) oder ähnliches eingesetzt werden, deren Komplexität (vor allem bei einer sehr großen Zahl von Queues) die eines einfachen Priority-Queueings um ein Vielfaches übersteigen kann. Selbstverständlich lässt sich Per Flow Queueing sowohl portindividuell [obiges Muster (a)] als auch in Verbindung mit dem Multi-Server-Prinzip [obiges Muster (b)] einsetzen.
• Bei allen genannten Verfahren wird bei der Implementierung in den Warteschlangen in der Regel lediglich ein Zeiger (Adresse) zur Identifizierung des jeweiligen Datenpakets in einem üblicherweise gemeinsamen Datenspeicher abgelegt. Die Reihenfolge der Bedienung ergibt sich implizit aus der Reihenfolge der Einträge in der Warteschlange (z. B. nach dem FIFO Prinzip) bzw. aus dem vorgelagerten Verfahren zur Auswahl der als nächstes zu bedienenden Warteschlange (z. B. nach Priorität und bei gleicher Priorität z. B. zyklisch, longest queue first, shortest queue first, nach Gewichtung wie bei WFQ).
• Um zusätzliche spezielle Effekte zu erzielen, können weitere Informationen in diese Scheduling-Entscheidung mit einbezogen werden. Vor allem in der ATM Technik wird sehr häufig (aber vereinzelt auch im IP Umfeld) von der Notwendigkeit eines Traffic Shaping gesprochen. Mit diesem Verfahren sollen in der Regel bestimmte Bandbreiten, meist realisiert durch entsprechende Abstandskriterien zwischen den Zellen (Paketen) einer Verbindung (d. h. Kommunikationsbeziehung), eingehalten werden. Dazu werden zusätzliche Zeitinformationen gespeichert, die einen frühesten, spätesten und/oder optimalen Bedienungszeitpunkt für eine Warteschlange oder eine bestimmte Zelle (Paket) angeben (sog. "Kalender").
• Die Mechanismen lassen sich mit gleicher Wirksamkeit auch für die Anwendung auf mehrere Bündel erweitern, sofern diese Bündel sich entweder gar nicht überlappen (disjunkt sind) oder sich vollständig überlappen (identisch sind). Ein Lösungsansatz für eine faire und effiziente paketweise Verkehrsverteilung auf sich teilweise überlappende Bündel mit Berücksichtigung von Prioritäten ist jedoch nicht bekannt.
• Eine Aufgabe der Erfindung liegt nun darin aufzuzeigen, wie in den Netzknoten unter Berücksichtigung einer evt. vorgesehenen Priorisierung einzelner Verkehrsströme oder individueller Datenpakete der Verkehr gemäß von vorgegebenen Verzweigungsmustern möglichst optimal auf die abgehenden Verbindungsleitungen verteilt werden kann, wobei jeder Netzknoten autonom und individuell pro Datenpaket entscheiden soll.
• Diese Aufgabe wird, durch die Erfindung gelöst. Die Erfindung sieht vor, dass meinem erfindungsgemäßen Netzknoten pro aktuellem Verzweigungsmuster zumindest je eine Warteschlange vorgesehen ist. Dabei kann eine Warteschlange durchaus für mehrere Verteilungsfächer, die sich in diesem Knoten auf dasselbe Verzweigungsmuster abbilden, gemeinsam benutzt werden. Ankommende Pakete werden nach ihrer Zugehörigkeit zu einem bestimmten Verteilungsfächer (d. h. nicht nach der Zugehörigkeit zu einem bestimmten Flow innerhalb des Verteilungsfächers) unterschieden. Entsprechend werden sie in eine zugehörige Warteschlange eingetragen.
• Die Warteschlangen werden von den zum jeweiligen Verzweigungsmuster gehörenden Ports bedient. Sobald ein Port frei wird, wählt er die als nächstes von ihm zu bedienende Warteschlange aus. Die Auswahl beginnt so rechtzeitig, dass auf der abgehenden Leitung keine Lücke entsteht. Bedient ein Port mehrere (in diesem Falle sich ganz oder teilweise überlappende) Verzweigungsmuster, so wird bei dieser Auswahl zunächst über alle diese Verzweigungsmuster nach nicht leeren Warteschlangen gesucht. Werden dabei mehrere nicht leere Warteschlangen aus verschiedenen Verzweigungsmustern gefunden, so wird nach einem vorgegebenen Kriterium entschieden, welche Warteschlange als nächste bedient wird. Das aus dieser Warteschlange auszugebende Paket wird dann nach einem weiteren Kriterium bestimmt.
• Vorteilhaft ist hierbei die Anzahl der benötigten Queues begrenzt und lediglich von der Topologie des Netzes, d. h. der Anzahl der Nachbarknoten unter Berücksichtigung einer Bündelung von Ports, aber nicht vom Verkehr abhängig.
• Es gibt es keinerlei Probleme bei einem Einsatz gemischten Netzen, da die Erfindung nur lokal in einem gegebenen Netzknoten zum Einsatz kommt.
• Weitergehende Ausgestaltungen der Erfindung sind wie folgt:
  
• - Zur Delay Optimierung werden mehrere, mit unterschiedlicher Priorität gekennzeichnete Warteschlangen innerhalb eines Verzweigungsmusters vorgesehen. Die Warteschlangen innerhalb eines Verzweigungsmusters werden strikt nach deren Priorität abgearbeitet. Bedient ein Port mehrere (in diesem Falle sich ganz oder teilweise überlappende) Verzweigungsmuster, so wird zunächst über alle diese Verzweigungsmuster nach der höchstprioren, nicht leeren Warteschlange gesucht und diese wird bedient. Werden dabei mehrere nicht leere Warteschlangen derselben Priorität aus verschiedenen Verzweigungsmustern gefunden, so erfolgt die Arbitrierung zwischen diesen Warteschlangen nach einem frei wählbaren Kriterien, z. B. dem Zufallsprinzip, einer zyklischen Reihenfolge, der Größe der Bündel, der Warteschlangenlänge (longest/shortest first), der vergangenen Zeit seit der letzten Bedienung dieser Warteschlange, der Anzahl der Ports, die für ihre Bedienung zuständig sind. Durch den Einsatz priorisierter Warteschlangen wird mit vergleichsweise geringem Aufwand eine ausreichend gute Delay- und Verteilungsqualität bewirkt.
• - Zur Optimierung auf den minimal möglichen Delay für jedes Paket werden ebenfalls mehrere, mit unterschiedlicher Priorität gekennzeichnete Warteschlangen innerhalb eines Verzweigungsmusters vorgesehen, die innerhalb eines Verzweigungsmusters nach strikter Priorität abgearbeitet. Bedient ein Port mehrere (in diesem Falle sich ganz oder teilweise überlappende) Verzweigungsmuster, so wird zunächst über alle diese Verzweigungsmuster nach der höchstprioren nicht leeren Warteschlange gesucht und diese wird bedient. Werden dabei mehrere nicht leere Warteschlangen derselben Priorität aus verschiedenen Verzweigungsmustern gefunden, so wird zwischen diesen nach einem Zeitkriterium entschieden. Dazu wird in den Warteschlangen neben einem Speicherzeiger (Adresse, s. o.) eine zusätzliche, vorzugsweise relative, Zeitinformation ("TimeStamp") mit abgelegt, aus der abgelesen werden kann, wann das Paket in die Warteschlange eingetragen wurde bzw. wie lange es sich schon darin befindet (Bild 4). Ausgewählt wird dann die Warteschlange, an deren Spitze sich das schon am längsten wartende Paket befindet, wodurch als Kriterium ein FIFO Prinzip realisiert wird.
  Mit dieser Ausgestaltung wird vorteilhaft sichergestellt, dass mit jedem frei werdenden Port, auch bei sich nur teilweise überlappenden Bündeln, über alle von diesem Port bediente Verzweigungsmuster hinweg immer die momentan gerade dringendste Anforderung mit der minimal möglichen Verzögerung bedient wird. Dies ist besonders dann sehr vorteilhaft, wenn als hochpriore Verkehrströme Daten interaktiver Echtzeitdienste, z. B. Telephon- oder Videokonferenzdienste, übermittelt werden.
• - Das paketindividuelle Zeitkriterium wird bei allen Warteschlangen verwendet, sondern nur bei hochprioren Verkehr (bspw. zeitkritischen Echtzeitanwendungen), um diesen mit dem kleinstmöglichen Delay und der entsprechend fairen Verteilung abzufertigen. Warteschlangen, die Verkehr ohne spezielle Delayanforderungen oder einfach nur Best Effort- Verkehr bedienen, können niedriger priorisiert und ohne Berücksichtigung dieser Zeitinformation behandelt werden. Prinzipiell reicht es aus, die Zeitinformation nur für die entsprechend hochprioren Warteschlangen zu speichern und auszuwerten.
• Die Granularität von Zeitinformation sollte die minimale Übertragungszeit eines Pakets, d. h. des kürzest möglichen Pakets auf der schnellsten Leitung des Bündels, berücksichtigen. Der mögliche Wertebereich sollte so gewählt werden, dass ein Überlauf innerhalb der erwarteten maximalen Verzögerungszeit eines entsprechend hochprioren Paketes nicht auftritt (Berücksichtigung der maximalen Längen der zugehörigen Queues, Portbandbreiten etc.) und jederzeit eine sichere Entscheidung möglich ist. Dabei kann auch eine evt. eingestellte Limitierung des hochprioren Verkehrs im Netz mit berücksichtigt werden mit dem Vorteil kürzerer Warteschlangen.
• Die Implementierung kann über einen einfachen, regelmäßig getakteten Rundzähler (Neustart bei Überlauf) erfolgen. Der Zähler ist nur lokal relevant, eine Synchronisation zwischen den Knoten ist nicht erforderlich, die Taktgenauigkeit unterliegt keinen spezifischen Anforderungen, eine Mischung von Knoten mit und ohne diesen Mechanismus im selben Netz ist jederzeit möglich. (Der Mechanismus betrifft nur die individuelle, lokale Arbeitsweise innerhalb eines Knotens.)
• 1. Das Zeitkriterium wird auch dazu verwendet, um Pakete, die aus irgendwelchen Gründen zu lange gewartet haben und deren weitere Übertragung (im Rahmen der zugehörigen Echtzeitanwendung) nicht mehr sinnvoll erscheint, auszusortieren und zu verwerfen. Dies kann entweder beim Schedulen oder durch einen separaten, parallel laufenden Prozess erfolgen. Ein solcher Prozess könnte z. B. die Zeitinformation beim Eintragen des Paketes in die Warteschlange auf einen definierten Anfangswert zu setzen, sie regelmäßig getaktet auf oder abwärts zu zählen und beim Erreichen eines bestimmten Grenz- oder Schwellenwertes entsprechende Aktionen, z. B. Entfernen des Paketes aus der Warteschlange, zu triggern. Alternativ könnte auch die Differenz zwischen dem Eintragszeitpunkt (als unveränderlicher Wert) und der aktuellen Zeit (die mitgezählt wird) in einem sich regelmäßig wiederholenden Vergleich als Entscheidungskriterium herangezogen werden.
  • - Die Warteschlangen werden von den Ports nach dem Multi Server Prinzip bedient. Das Multi-Server-Prinzip garantiert eine faire Zuteilung und die optimale Nutzung der verfügbaren Ressourcen auch und gerade bei variablen Paketlängen. Der Scheduling Prozess wird vom ausgehenden Port genau dann angestoßen, wenn dieser frei wird. Dies geschieht aber (unter Kenntnis der (Rest-)Länge des momentan bedienten Pakets) so rechtzeitig, dass die Entscheidung und das nächste auszugebende Paket rechtzeitig mit dem Ende des vorhergehenden zur Ausgabe bereitsteht. Ein weiterer großer Vorteil des Multi-Server-Prinzips besteht auch darin, dass bei Ports unterschiedlicher Bandbreite diese Unterschiede dadurch, dass frei werdende Ports sich quasi selbst neue Daten aus der (den) Queue(s) holen, automatisch bei der Verteilung berücksichtigt werden.
  • - Die Auswahl der als nächstes von einem Port zu bedienenden Warteschlange erfolgt mit Hilfe einer Scheduling-Funktion.
  • - Es werden weitere getrennte Warteschlangen eingesetzt, um zusätzliche, ggf. pro Verteilungsfächer unterschiedliche Kriterien zu berücksichtigen.
  • - Das weitere Kriterium ist ein FIFO (First In First Out).
  • - Die Warteschlangen werden nur bei Bedarf angelegt. Längere Zeit nicht verwendete Queues werden wieder freigegeben (time-out). Hierdurch wird die Zahl der tatsächlich benötigten Warteschlangen reduziert, weil die Zahl der aktuellen Verzweigungsmuster meiste kleiner sein dürfte als die Zahl der aktuellen Kommunikationsbeziehungen.
  • - Die Verkehrsströme werden gezielt ungleichmäßig nach entsprechenden Vorgaben verteilt. Hierzu werden weitere Kriterien in die Verteilungsentscheidung mit einbezogen werden.
  • - Es wird eine adaptive Annäherung an einen erwünschten Zielwert der Verteilung vorgesehen. Bei sich teilweise überlappenden Bündeln ist es möglich, dass die angestrebten gleichmäßigen bzw. vorgegebenen Verteilung nicht optimal bewirkt wird, weil sich Interferenzen zwischen den Bündeln störend auswirken.
    Eine einfache Alternative sieht vor, diese vorausberechnen und bei der Vorgabe der Scheduling-Regeln zu berücksichtigen.
    In komplexen Fällen (z. B. unter sich immer wieder ändernden realen Netzbedingungen), in denen das Netzverhalten und mithin das Verhalten der Komponenten der Erfindung nicht zuverlässig vorausberechnet werden kann, ist es von Vorteil, die Scheduling-Parameter im Betrieb adaptiv anpassen zu können.
    Dies kann entweder im Knoten autonom oder durch einen Anstoß von außen (Vorgabe neuer Regeln) erfolgen.
    Als regulierendes Kriterium kann dazu der Vergleich (resp. die Abweichung) der tatsächlich erzielten Verteilung mit (von) der gewünschten Verteilung dienen. Vorzugsweise sollte dazu im Knoten z. B. die Häufigkeit der Bedienung der verschiedenen Warteschlangen durch die verschiedenen Ports (oder die resultierende Last der Ports pro Verkehrsklasse) gemessen und für die korrigierende Einheit verfügbar gemacht werden.
    Für netzweite Korrekturen können auch Angaben über die mittlere und die maximal aufgetretenen Länge der verschiedenen Warteschlangen von Bedeutung sein.
    Vorzugsweise werden diese Messungen und Verfahren auf Basis der Anzahl der Pakete vorgenommen. Hierbei wird davon auszugehen, dass sich die Auswirkungen von variabel langen Pakete über relativ kurze Zeiträume ausmitteln. Alternativ können diese Betrachtungen und Messungen auch unter Berücksichtigung der individuellen Längen aller einzelnen Pakete angestellt werden.
  • - Zur Realisierung einer bestimmten Lastverteilung innerhalb eines Bündels wird pro Queue für jeden Port eine Zeitinformation gehalten und beim Scheduling mitberücksichtigt. Die Zeitinformation enthält z. B. die letzten Bedienungszeitpunkte der Queue durch die verschiedenen Ports.
    Vorteilhaft kann hiermit z. B. portindividuell ein bestimmter Mindest- und/oder Maximalabstand zwischen zwei Bedienungen eingestellt werden oder die Zeiten könnten relativ zueinander bewertet werden ("Port x kommt erst wieder dran, wenn er doppelt so lange nicht dran war wie Port y"). Solche Zeitinformationen könnten auch zur Bestimmung eines nächsten Ziel-Bedienungszeitpunktes (frühestens, spätestens, optimal) verwendet werden oder gleich als solche abgespeichert werden (Kalender).
    Eine alternative und vergleichsweise einfachere Lösung besteht darin, für jede Queue lediglich mitzuzählen, wie oft sie von welchem Port bedient wurde, und daraus die Entscheidung abzuleiten, ob sie aktuell mit berücksichtigt werden darf. Die Zähler könnten intervallweise oder auch gleitend (Leaky Bucket) zurückgesetzt bzw. dekrementiert werden.
    Auch bei diesen Varianten könnten die Vorgaben und Regeln wie oben beschrieben mit Hilfe von Messergebnissen adaptiv angepasst werden.
• Die Erfindung wird anhand von in den Figuren dargestellten Ausführungsbeispielen näher erläutert. Es zeigt hierbei:
• Fig. 1 einen Verteilungsfächer, der alle für eine Kommunikationsbeziehung in einem Netz sinnvoll nutzbaren Knoten und Verbindungswege umfasst;
• Fig. 2 überlappende Verteilungsfächer mehrerer Kommunikationsbeziehungen in dem Netz nach Fig. 1,
• Fig. 3 die Grundform einer erfindungsgemäßen Lösung (noch ohne "Timestamp") mit n = 1 für die elementarste Ausgestaltung der Erfindung, wobei durch die Pfeilrichtung andeutet wird, dass der Port sich das nächste auszugebende Paket abholt, und wobei die gestrichelten Dreiecke für die dabei (vom Port aus) aktivierte Scheduling Funktion stehen,
• Fig. 4 eine erfindungsgemäße Lösung mit Timestamp Information für die Pakete der höchstprioren Queue (das Timestamp Prinzip kann selbstverständlich auch für niederpriore Queues bis hin zum Best Effort eingesetzt werden), die vom Scheduler mit ausgewertet wird, wobei durch die Pfeilrichtung andeutet wird, dass der Port sich das nächste auszugebende Paket abholt, und wobei die gestrichelten Dreiecke für die dabei (vom Port aus) aktivierte Scheduling Funktion stehen,
• Fig. 5 eine erfindungsgemäße Lösung mit weiteren Hilfsregistern pro Queue (mit Hilfsinformationen zum Ansteuern einer vorgegebenen Verkehrsverteilung für die jeweilige Verzweigungsgruppe in dem sie bedienenden Bündel), wobei durch die Pfeilrichtung andeutet wird, dass der Port sich das nächste auszugebende Paket abholt, und wobei die gestrichelten Dreiecke für die dabei (vom Port aus) aktivierte Scheduling Funktion stehen,
• Es ist hierbei zu beachten, dass die Verzweigungsmuster in den Fig. 1 und 2 lediglich die Struktur der Vermaschung zwischen den Knoten zeigen. Dies schließt nicht aus, dass an einer Kante der Graphen (d. h. zwischen zwei benachbarten Knoten) mehrere parallele physikalische Leitungen (und sogar auch mit unterschiedlichen Bandbreiten) liegen können, die bei der Verteilung als separate Ports wie in den Fig. 3 bis 5 betrachtet werden (können).
• Ein besonders schöner Vorteil der Erfindung liegt darin, dass bei Einsatz sich überlappender Verzweigungsmuster durch, beliebige Kombination der Mechanismen a) Zeitkriterium pro Paket zur Delayoptimierung beim Arbitrieren, b) Einstellung einer vorgegebenen, bei Bedarf auch "schiefen" Verkehrsverteilung, c) adaptive Nachregelung auf das angestrebte Verteilungsmuster, eine sehr flexible und für nahezu jede Netzanwendung optimierbare Adaptionen der Netzknoten und mithin des Netzes als Ganzem ermöglicht wird.
• Ein Beispiel für eine gezielt ungleichmäßig Verteilung der Verkehrsströme nach entsprechenden Vorgaben mittels Einbeziehung weitere Kriterien in die Verteilungsentscheidung liegt darin, beim Scheduling für bestimmte Ports nach entsprechenden Regeln sporadisch eine bestimmte Warteschlange nicht zu berücksichtigen. Soll beispielsweise bei einer Verteilung auf 4 Ports der hoch- bzw. höchstpriore Verkehr einer Verzweigungsgruppe im Verhältnis 4 : 4 : 3 : 1 auf 4 Ports verteilt werden, so wird vom Scheduler für den 3. Port die höchstpriore Warteschlange dieser Verzweigungsgruppe bei jedem 4. Scheduling-Vorgang nicht berücksichtigt und für den 4. Port wird er nur bei jedem 4. Scheduling-Vorgang mit einbezogen. Dabei sollte das Gesamtvolumen des höchstprioren Verkehrs in jedem Fall (deutlich) unter der dafür bereitgestellten Gesamtkapazität (Port 1 + Port 2 + x Port 3 + R Port 4) des Bündels bleiben.
• Selbstverständlich können dabei auch Unsymmetrien der Portbandbreiten kompensiert werden. Hat z. B. der 4. Port gegenüber den übrigen 3 Ports nur die halbe Bandbreite, soll aber dennoch ein Zwölftel des Gesamtverkehrs zugeteilt bekommen, so wird für ihn die entsprechende Warteschlange jedes 2. mal mit berücksichtigt.
• Es sei betont, dass die Beschreibung der für die Erfindung relevanten Komponenten des Kommunikationsnetzes grundsätzlich nicht einschränkend zu verstehen ist. Für einen einschlägigen Fachmann ist insbesondere offensichtlich, dass die verwendeten Begriffe funktional und nicht physikalisch zu verstehen sind. Somit können die Komponenten auch teilweise oder vollständig in Software und/oder über mehrere physikalische Einrichtungen verteilt realisiert werden.

Claims (29)

1. Netzknoten eines paketorientierten Kommunikationsnetzes,
dessen Knoten gemäß der Topologie des Netzes so untereinander verbunden sind, dass eine Mehrzahl von Wegen zwischen den Netzknoten existiert,
wobei der Netzknoten in zumindest einem Verteilungsfächer enthalten ist, der für eine konkrete Kommunikationsbeziehung zwischen einem als Sendeknoten ausgebildeten Netzknoten und einem als Empfangsknoten ausgebildeten Netzknoten aus der Netztopologie abgeleitet ist und alle Netzknoten und Wege umfasst, die für eine verteilte Übermittlung von der Kommunikationsbeziehung zugeordneten Verkehrsströmen in dem Kommunikationsnetz sinnvoll genutzt werden können,
woraus zumindest für den Netzknoten ein Verzweigungsmuster, auf das der Verteilungsfächer abgebildet ist, bestimmt ist, durch das ein Bündel von abgehenden Ports des Netzknotens festgelegt ist, auf die die dem Verteilungsfächer zugeordneten Verkehrsströme verteilt werden sollen, wobei die den Ports zugeordneten Wege zu zumindest zwei unterschiedlichen, benachbarten Netzknoten führen,
wobei der Netzknoten zumindest ein, zumindest eine Warteschlage umfassendes Warteschlangensystem für das Verzweigungsmuster umfasst, die zumindest dann vorgesehen ist, wenn durch den Netzknoten zumindest ein Verkehrsstrom entsprechend dem Verzweigungsmuster aktuell verteilt übermittelt wird.

2. Netzknoten nach Anspruch 1, mit einem separaten Warteschlangensystem für jedes Verzweigungsmuster, dessen Bündel sich von den Bündeln der übrigen Verzweigungsmustern in mindestens einem Port unterscheidet.

3. Netzknoten nach einem der vorstehenden Ansprüche, mit einem separaten Warteschlangensystemen für zumindest einem Teil der Verteilungsfächer, sofern sie unterschiedlich sind (t, d).

4. Netzknoten nach einem der vorstehenden Ansprüche, mit je einem gemeinsamen Warteschlangensystem für zumindest einem Teil derjenigen unterschiedlichen Verteilungsfächer, die auf identische Verzweigungsmuster (i) abgebildet sind.

5. Netzknoten nach einem der vorstehenden Ansprüche, bei dem zumindest ein Warteschlangensystem zumindest zwei Warteschlangen umfasst, wobei zumindest eine der beiden Warteschlagen mit einer Priorität gekennzeichnet ist.

6. Netzknoten nach einem der vorstehenden Ansprüche, mit einer Zeitinformation zumindest für die in einer prioren, insbesondere hochprioren Warteschlange wartenden Pakete, aus der abgelesen werden kann, wann die Pakete in die Warteschlange eingetragen wurden bzw. wie lange sie sich schon darin befinden.

7. Netzknoten nach Anspruch 6, mit einem Wertebereich für die Zeitinformation, der unter Berücksichtigung der Übermittlungszeit des kürzest möglichen Pakets auf dem schnellsten Port so gewählt ist, dass ein Überlauf innerhalb einer gegebenen, maximalen Verzögerungszeit eines prioren Paketes nicht auftritt.

8. Netzknoten nach einem der Ansprüche 6 oder 7, umfassend einen separaten, parallel laufenden Prozess zum Aussortieren und/oder Verwerfen von Paketen, deren weitere Übermittlung unter Berücksichtigung der Zeitinformation nicht mehr sinnvoll erscheint.

9. Netzknoten nach einem der vorstehenden Ansprüche, umfassend zweite Zeitinformation für zumindest eine der Warteschlangen, durch die für jeden Port des der Warteschlange zugeordneten Bündels dessen jeweils letzter Bedienzeitpunkt der Warteschlange angezeigt wird.

10. Anordnung, insbesondere Kommunikationsnetz, umfassend zumindest einen Netzknoten nach einem der vorstehenden Vorrichtungsansprüche.

11. Verwendung eines Verfahrens mit nachfolgenden Schritten in einem Netzknoten nach einem der vorstehenden Vorrichtungsansprüche:
ein ankommendes Paket wird in eine der Warteschlangen eingetragen, und
ein Scheduling-Prozess zur Entscheidung über die Ausgabe eines nächsten Pakets aus einer der Warteschlangen wird zumindest von einem der abgehenden Ports des Netzknotens angestoßen.

12. Verwendung nach Anspruch 11, bei der der Scheduling-Prozess von dem Port so rechtzeitig vor seinem Freiwerden angestoßen wird, dass die Entscheidung über das nächste auszugebende Paket und das nächste Paket selbst so rechtzeitig bereitsteht, dass das nächste Paket von dem Port im unmittelbaren Anschluss an das vorhergehende Paket übermittelt werden kann.

13. Verwendung nach einem der vorstehenden Verwendungsansprüche, bei der im Falle von mehreren gefüllten Warteschlangen, die dem Port zugeordnet sind, nach einem ersten vorgegebenen Kriterium entschieden wird, welche Warteschlange als nächste bedient wird.

14. Verwendung nach dem vorstehenden Anspruch, bei dem im Falle einer zumindest teilweisen Kennzeichnung der Warteschlangen mit Prioritäten bei der Entscheidung die gefüllten Warteschlangen mit einer niedrigen Priorität solange unberücksichtigt bleiben, wir noch zumindest eine gefüllte Warteschlange mit einer im Vergleich zu diesen Warteschlangen höheren Priorität zu berücksichtigen ist.

15. Verwendung nach einem der beiden vorstehenden Ansprüche, bei dem das erste Kriterium als eines der nachfolgenden Kriterien ausgebildet ist:
Zufallsprinzip,
zyklischen Reihenfolge,
Größe der Bündel,
kürzeste Warteschlange zuerst,
längste Warteschlange zuerst,
nach Gewichtung der Warteschlangen,
vergangenen Zeit seit der letzten Bedienung dieser Warteschlange, insbesondere ausgebildet als FIFO Prinzip, bei dem die am längsten unbediente Warteschlange als nächste bedient wird, oder
Anzahl der Ports, die für ihre Bedienung zuständig sind.

16. Verwendung nach einem der vorstehenden Verwendungsansprüche, bei der das nächste Paket im Falle einer mit mehr als einem Paket gefüllten Warteschlange nach einem zweiten Kriterium bestimmt wird.

17. Verwendung nach dem vorstehenden Anspruch, bei der das zweite Kriterium als FIFO ausgebildet ist.

18. Verwendung nach einem der vorstehenden Verwendungsansprüche, bei der die Warteschlangen nur bei Bedarf angelegt und längere Zeit nicht genutzte Warteschlangen wieder freigegeben werden.

19. Verfahren zur Übermittlung von Verkehrsströmen in einem paketorientierten Kommunikationsnetz, angewendet in einem Netzknoten nach einem der vorstehenden Vorrichtungsansprüche, mit folgenden Schritten:

- ankommende Pakete werden nach ihrer Zugehörigkeit zu einem der Verteilungsfächer in eine entsprechende Warteschlange eingetragen, und

- über einen der Ports desjenigen Bündels übermittelt, das dem Verteilungsfächer zugeordnet ist und dessen Ports durch das Verzweigungsmuster festgelegt sind, auf das der Verteilungsfächer abgebildet ist.

20. Verfahren nach einem der vorstehenden Verfahrensansprüche, bei dem die Verkehrsströme einer Verzweigungsgruppe gezielt ungleichmäßig über die Ports des zugeordneten Bündels übermittelt werden.

21. Verfahren nach einem der vorstehenden Verfahrensansprüche, bei dem insbesondere bei teilweise überlappenden Bündeln eine Annäherung an einen erwünschten Verteilungszielwert durch adaptive Anpassung von Scheduling-Regeln bewirkt wird.

22. Verfahren nach dem vorstehenden Anspruch, bei dem die erforderliche Anpassung voraus berechnet und bei der Vergabe der Scheduling-Regeln berücksichtigt wird.

23. Verfahren nach einem der Ansprüche 19 bis 21, bei dem die Scheduling-Regeln im laufenden Betrieb des Kommunikationsnetzes adaptiv angepasst werden.

24. Verfahren nach dem vorstehenden Anspruch, bei dem die Anpassung der Scheduling-Regeln im Netzknoten autonom und/oder durch einen Anstoß von außen erfolgt.

25. Verfahren nach einem der Ansprüche 23 oder 24, bei dem die Anpassung unter Berücksichtigung eines regulierenden Kriteriums, insbesondere einem Vergleich zwischen der tatsächlich erzielten Verteilung mit dem erwünschten Verteilungszielwert bewirkt wird.

26. Verfahren nach dem vorstehenden Anspruch, bei dem zur Bewertung des Kriteriums die Häufigkeit der Bedienung der verschiedenen Warteschlangen und/oder die resultierende Last der Ports pro Verkehrsklasse gemessen wird.

27. Verfahren nach einem der Ansprüche 23 bis 26, bei dem für netzweite Korrekturen die mittlere und/oder die maximal aufgetretene Länge der verschiedenen Warteschlangen gemessen wird.

28. Verfahren nach einem der Ansprüche 26 oder 27, bei dem auf Basis der Anzahl der Pakete gemessen wird.

29. Verfahren nach einem der Ansprüche 26 oder 27, bei dem unter Berücksichtigung der individuellen Länge der einzelnen Pakete gemessen wird.