DE68922905T2 - System und Verfahren zur Zugangsratensteuerung von Stationen in einem Paketvermittlungsnetzwerk. - Google Patents

Description

• Die Erfindung betrifft ein Verfahren zum Steuern der Zugangsraten von Stationen in einem Paketvermittlungsnetzwerk, mit einer Anzahl von Sende-Empfangsstationen, die durch Funkverbindungskanälen miteinander verbunden sind, über die Datenpakete von einer Station nach einer anderen entsprechend einem Leitwegplan übertragen werden können, wobei jede Station eine Anzahl von Sende-Empfangsstationen enthalten, die über Funkverbindungskanälen miteinander verbunden sind, über die von einer Station nach einer anderen entsprechend einem Leitwegplan Datenpakete übertragen werden könne, wobei im Betrieb des Netzwerks jede Station einen ersten Parameter berechnet, der für ihren Ausgangsfluß in Form der Anzahl erfolgreich übertragener Pakete je Zeiteinheit bezeichnend ist.
• Ein derartiges Verfahren ist in IBM Technical Disclosure Bulletin, Vol. 24, Nr. 4, September 1981, S. 2044-45, beschrieben. In diesem Artikel ist ein Durchflußregelverfahren in Paketvermittlungscomputernetzwerken unter Verwendung eines u.a. auf dem an jedem Knotenpunkt gemessenen Eingangsdurchfluß basierenden besonderen Durchflußregelalgorithmus beschrieben.
• Kanalzugriffsregelprotokolle zielen eine Einstellung auf Maximum der Durchflußleitung des Funkkanals durch optimales Abstimmen einiger Regelveränderlichen. In reinen und geschlitzten ALOHA-Netzwerken bestimmen die Laufvariablen die Rate, mit der jede Station überträgt, während in CSMA-Netzwerken sie die Rate bestimmen, mit der jede Station den Kanal abtastet. Im restlichen Teil dieser Anmeldung bezieht sich die Zugriffsrate einer Stationsschwelle auf unklare Weise auf die Rate, mit der eine Station überträgt (in einem ALOHA-Netzwerk) oder dem Kanal abtastet (in einem CSMA-Netzwerk). In einer einfachen Hopping-Topologie gibt es begriffsbestimmt einen einzigen Kanal und es bestehen relativ gut verstandene Zusammenhänge zwischen der Durchflußleistung des Kanals und den Laufvariablen. Diese Zusammenhänge bieten klare Objektive zum Abstimmen der Laufvariablen. In Mehrhopping-Topologien kann es begriffsbestimmt soviel unabhängige Kanäle geben wie es Stationen gibt, und es besteht kein genauer Zusammenhang für die allgemeine Durchflußleistung.
• Der Erfindung liegt die Aufgabe zugrunde, ein Verfahren zum Steuern der Zugangsrate der Stationen in einem Paketvermittlungsnetzwerk derart anzugeben, daß das Ausgangsverhältnis der Station mit mimimalem Ausgangsverhältnis durch optimales Abstimmen der Belastung der Stationen, die sich in direkter Reichweite der Station mit minimalem Ausgangsverhältnis befinden, und durch optimale gemeinsame Benutzung der Belastung der Station unter den zu dieser Belastung beitragenden Stationen erhöht wird.
• Zur Lösung dieser Aufgabe gibt die Erfindung ein Verfahren eingangs erwähnter Art an, daß dadurch gekennzeichnet ist, daß jede Station den ersten Parameter bei vorgegebenen Zeitintervallen an alle in Reichweite der Station befindlichen benachbarten Stationen überträgt, daß danach jede Station einen zweiten Parameter berechnet, der für ihre Eingangsflußerhöhungstendenz bezeichnend ist, die ein Maß auf der Basis der Ausgangsflüsse der benachbarten Stationen ist, auf dem die Station sich verlassen kann, der höher wird, wenn diese Ausgangsflüsse nachlassen, und einen dritten Parameter, der für ihre Belastung bezeichnend ist, wonach jede Station die zweiten und dritten Parameter auf ihre benachbarten Stationen überträgt, die nach dem Empfang des zweiten und des dritten Parameters bestimmen, welche Station in ihrer Nähe die größte Eingangsflußerhöhungstendenz aufweist und auf der Basis des dritten Parameters ihre Zugangsrate verbessern, um die Belastung der Station des dritten Parameters auf ihre Zugangsrate zu bringen, um die Belastung der Station mit der größten Eingangsflußerhöhungstendenz näher bei der Nennkanalbelastung zu bringen.
• In einem erfindungsgemäßen bevorzugten Verfahren ist der erste Parameter das Ausgangsverhältnis, das zwischen dem richtig übersandten und bestätigten Paketendurchsatz und dem zu übersendenden Durchsatz auftritt. Das Ausgangsverhältnis wird vorzugsweise durch ein erstes Berechnungsmittel als das Verhältnis zwischen der erfolgreich übersandten und in einer vorgegebenen Zeit bestätigten Paketendurchsatz und der Summe der Anzahl und der Anzahl von Paketen berechnet wird, die am Ende dieser Zeit noch Schlange stehen.
• Vorzugsweise ist der zweite Parameter die Eingangsflußerhöhungstendenz, und die Begriffsbestimmung dieser Tendenz wird nachstehend in der Figurbeschreibung erläutert.
• Die Erfindung bezieht sich ebenfalls auf ein System zum Durchführen des erfindungsgemäßen Verfahrens nach Anspruch 6.
• Die Erfindung wird nachstehend anhand der Zeichnung näher erläutert. Es zeigen
• Fig. 1 ein ziemlich einfaches mehrfaches Hopping-Paketnetzwerk,
• Fig. 2 sehr schematisch ein Mehrhopping-Funknetz,
• Fig. 3A eine Übersicht über die allgemeinen Aktualisierungsregeln der Zugangsrate bei Verwendung in dem erfindungsgemäßen Verfahren,
• Fig. 3B eine mögliche Wertgrupe für die Protokollparameter,
• Fig. 4 ein Blockschaltbild einer Hardware-Implementierung einer der Netzwerkstationen.
• Vor der Beschreibung der Kanalzugangsregelprotokolle für Mehrhopping- Netzwerke wird zunächst die Aufgabe derartiger Protokolle in einfachen Hopping- Netzwerken erläutert.
• In einfachen Hopping-Netzwerken wird die Kanalbelastung G durch die Summe der Zugangsraten g(K) der verschiedenen Stationen bestimmt. G muß gesteuert werden, um die Durchflußleistung des Kanals auf Maximum einzustellen. Eine zu große Kanalbelastung führt zu zuvielen Zusammenstößen, während eine zu kleine Kanalbelastung zu langen Betriebspausen führen. Also besteht eine optimale Kanalbelastung Gnom. Diese optimale Kanalbelastung muß beim Abstimmen der Zugangsraten g(K) der Stationen oder durch Abstimmen einiger Variablen aufrechterhalten werden, die diese Zugangsraten g(K) direkt steuern. Dies stellt die Aufgabe des Zugangssteuerprotokolls dar.
• Eine erste Kategorie eines derartigen Protokolls kann wie folgt funktionieren. Jede Station K sammelt Information über den Zustand des Kanals durch Abhören ein, und stimmt ihre eigene Zugangsrate g(K) dementsprechend ab. Beispielsweise entspricht der optimalen Kanalbelastung ein optimaler Prozentsatz zusammengeprallter Pakete. Durch die Messung des laufenden Prozentsatzes zusammengeprallter Pakete und durch den Vergleich dieses Prozentsatzes mit dem optimalen Prozentsatz kann jede Station ihre eigene Zugangsrate ändern, um sie auf den optimalen Wert einzustellen. In CSMA-Netzwerken kann dieselbe Strategie auf der Basis einer optimalen mittleren Länge für die Betriebspausen arbeiten. Diese Strategieart gibt lediglich an, daß jede Station den Kanal abhört.
• Eine andere Protokollkategorie basiert auf den Austausch von Informationen zwischen Stationen (also müssen derartige Protokolle über Kanalkapazität für diese Austauschvorgänge verfügen. Beispielsweise kann jede Station ihren Zustand (außerbetrieblich oder betriebsbereit) übertragen, so daß die Anzahl m der Stationen mit zu übertragenden Paketen dabei bekannt ist. In diesem Fall kann jede Station ihre eigene Zugangsrate auf Gnom/m abstimmen. Die Stationen können auch mitteilen, wieviel sie zum Übertragen benötigen (durch ein Angebot); die Gesamtkanalkapazität kann dabei entsprechend dieser Anforderungen gemeinsam benutzt werden. Im Vergleich zur ersten Kategorie verbessern derartige Informationsaustauschvorgänge nicht nur die Abstimmung der Kanalbelastung, sondern auch ermöglichen sie die auf Anfrage gemeinsam zu benutzende Kanalkapazität. Dieser Vorteil kann jedoch ziemlich mager sein und die für ihre Implementierung benutzte Kanalkapazität nicht berechtigen. Nichtsdestoweniger gibt es Situationen (Mehrhopping-Topologien), bei denen derartige Informationsaustauschvorgänge äußerst nützlich sein können.
• In Mehrhopping-Topologien sind nicht alle Stationen in Empfangsreichweite voneinander, der Zustand dabei ist, als gäbe es mehrere verschiedene Kanäle. In Anbetracht des Zustands nach Fig. 1 zur Veranschaulichung einer Anzahl von Stationen I, J, K und L gibt es zwei Stationen, die in graphischer Verbindung in Empfangsreichweite voneinander stehen. In diesem Zustand übertragen die Stationen I und L gleichzeitig ein Paket. Diese beiden Pakete werden von den Stationen J bzw. K richtig empfangen, vorausgesetzt diese Stationen schwiegen bei der Übertragung. Dies beleuchtet das Vorhandensein mehrerer Kanäle. Die Zielsetzung der Kanalzugangssteuerung in einer einfachen Hopping-Topologie war es, die Durchflußleistung auf Maximum einzustellen. In einer Mehrfachhopping-Topologie ist die Zielsetzung viel weniger klar. Beispielsweise wenn die Station J ein Paket überträgt, kann es in der Station I richtig empfangen werden und einen Zusammenprall in der Station K erzeugen (mit einem von der Station L übertragenen Paket). "Ist diese Übertragung als schädlich zu betrachten oder nicht?" ist die Art der zu beantwortenden Fragen. Nachstehend werden verschiedene gestellte Aufgaben erläutert, die Kriterien zur Steuerung der Zugangsraten liefern.
• Wenn davon ausgegangen wird, daß eine Quelle-Bestimmungsverkehrsmatrix M vorhanden ist, kann man versuchen, die einzelnen Zugangsraten zuzuordnen, um die erforderliche Zeit zum Durchschleusen dieser ganzen Verkehrsmatrix oder gleichermaßen zum Einstellen des Prozentsatzes auf Maximum, d.h. a%, der Verkehrsmatrix zu minimisieren, das je Zeiteinheit durchschleusbar ist. Die Zielsetzung kann also sein, das Einstellen des Verkehrsaufkommens a x M auf Maximum, das je Zeiteinheit richtig übertragbar ist. Diese Maximalisierung erfordert eine allgemeine Optimierung aller Zugangsraten. Nach der Beschreibung in "A distributed Controller for a Non-Persistent CSMA Channel", von P.J. Courtois, G. Scheys und P. Semal, Philips Research Laboratory, Brussel, Report R514, 1987, ist diese Optimierung berechnungsmäßig sehr schwierig und in der Praxis meist ungeeignet. Außerdem sind in Verteilersystemen nur örtliche Optimierungen der Zugangsraten zulässig. Es sind daher unteroptimale Zielsetzungen zu definieren.
• Es sei bemerkt, daß zwei Arten von Durchlaßleistung sich unterscheiden: Die Anzahl der Pakete, die eine Station K richtig je Zeiteinheit F(TK) empfangt, im weiteren mit Eingangsdurchfluß der Station K bezeichnet, und die Anzahl der Pakete, die eine Station je Zeiteinheit F(KT) erfolgreich überträgt, im weiteren mit dem Ausgangsdurchfluß der Station K bezeichnet. Es sei angenommen, daß die Station K früher oder später eine Bestätigung für diesen Durchfluß empfängt.
• Eine erste Zielsetzungsaufgabe kann die Maximalisierung des kleinsten Eingangsdurchflusses sein:
• Zielsetzung 1.: { min F(TK) } auf Maximum einstellen (1)
• K
• Um diese Zielsetzung zu erfüllen, muß jede Station bestimmen, welche Station (unter ihren Nachbarn und sich selbst) den kleinsten Eingangsdurchfluß darstellt, und muß ihre eigene Zugangsrate aktualisieren, um den Eingangsdurchfluß dieser Station zu erhöhen. Zum Implementieren dieser Zielsetzung muß jede Station ihren laufenden Eingangsdurchsatz F(TK) mitteilen, um das zu berechnende Minimum in (1) zuzulassen. Sobald das Minimum geortet ist, z.B. in der Station I, ändern die Nachbarn von I ihre Zugangsrate zum Erhöhen des Eingangsdurchsatzes der Station I. Eine Station muß daher immer die Möglichkeit haben, ihre Nachbarn darüber zu unterrichten, auf welche Weise ihr Eingangsdurchfluß erhöht werden kann. Typisch muß jede Station K die Möglichkeit haben, eine von ihr selbst gesehene laufende Kanalbelastung Gcur(K) zu messen und die Kanalbelastung Gnom(K) zu bestimmen, die ihren maximalen Eingangsdurchfluß F(TK) erreicht. Wenn diese beiden Werte ausgesandt werden, können die Nachbarn der Station I ihre Zugangsrate zum Erhöhen von F(TI) zu aktualisieren. Die von jeder Station auszusendende Information besteht also aus drei
• [F(TK), (Gnom(K), Gcur(K)] (2)
• oder in gedrängterer Form in
• [F(TK), Gr(K) = Gcur(K)/Gnom(K)] (3)
• Es sei bemerkt, daß dieser Vorgang sich nur auf das Erhöhen der Anzahl in der Station K richtig empfangener Pakete richtet. Nichts gewährleistet, daß diese Pakete für die Station K bestimmt sind oder von der Station K weitergeleitet werden müssen.
• Die Hauptkritik bezüglich der Zielsetzung 1 ist faktisch, daß die Station mit dem kleinsten Eingangsdurchfluß nicht notwendigerweise eine Erhöhung ihrer Eingangsdurchfluß benötigt; der Eingangsdurchfluß dieser Station, obgleich klein, kann ausreichen. Umgekehrt kann die Station mit der größten Eingangsdurchfluß immer noch etwas Eingangsdurchflußerhöhung erfordern. Um diese Kritik zu beantworten, muß jeweils der einzelne Bedarf berücksichtigt werden. Wenn T(TK) die Anzahl der Pakete (je Zeiteinheit) bezeichnet, die in der Station K empfangen werden muß, läßt sich folgende Zielsetzungsaufgabe wie folgt definieren:
• Zielsetzung 2.: {min F(TK)/T(TK)} auf Maximumtellen (4)
• Mit einer derartigen Zielsetzung wird eine Station ihre eigene Zugangsrate g(K) aktualisieren, um den Eingangsdurchsatz der benachbarten Station zu erhöhen, die das kleinste Verhältnis zwischen dem, was sie empfängt, und dem, was sie empfangen soll, darstellt. Unglücklicherweise wird der zu empfangende Durchfluß T(TK) auf die Nachbarn der Station K verteilt und steht also nicht für eine davon zur Verfügung. Außerdem definiert in den meisten Fällen der Leitweg nicht eindeutig, welche Station ein Paket weiterleiten muß. Die folgende Zielsetzungsaufgabe versucht dieses Problem zu beseitigen.
• Zielsetzung 3.: {min F(KT)/T(KT)} auf Maximum einstellen (5)
• K
• Statt der Berücksichtigung des Verhältnisses zwischen dem richtig empfangenen Durchfluß und dem zu empfangenden Durchfluß wird das Verhältnis zwischen dem richtig übersandten und bestätigten Durchfluß, dem Ausgangsdurchfluß F(KT), und dem auszusendenden Durchfluß T(KT) berücksichtigt. Dieses Verhältnis kann durch Messung der Ausgangsschlangenlänge der Station K bestimmt werden. Wenn in einer Zeit die Station K erfolgreich n(K) Pakete übersandt hat (sie wurden bestätigt), und wenn q(K) Pakete noch am Ende dieser Zeit Schlange stehen, hat man folgende Gleichheit für diese Zeit
• Die Menge 0(K) mit der Bezeichnung Ausgangsverhältnis kann von jeder Station bestimmt werden und nach ihren Nachbarn gesant, so daß ein Ortliches Minimum, mit der Reichweite beispielsweise von Station I, auf einfache Weise von jeder Station getrennt berechenbar ist. Die Zielsetzung richtet sich nunmehr auf die Erhöhung des minimalen Ausgangsverhältnisses. Die Formel (5) zeigt, daß der einzige Weg zum Erhöhen eines Ausgangsverhältnisses 0(I) in der Erhöhung des Ausgangsdurchsatzes F(IT) besteht, da der Leitweg nicht als eine Optimierungsvariable betrachtet wird. Jedoch ist eine Erhöhung des Ausgangsdurchsatzes F(IT) einer Station schwer zu erhalten, da die Station(en), die in I Schlange stehenden Pakete von vornherein nicht bekannt ist (sind). Eine ungefähre Annäherung besteht in der Reduktion der Zugangsrate der Nachbarn von I, um der Station I eine erhöhte Zugangsrate g(I) zu ermöglichen. Diese einfache Annäherung wird sich nur in sehr genaen Zellen wirksam erweisen und äußerst schadhaft, wenn sie uneingeschränkt angewandt wird.
• Hierdurch wird klar den doppelten Charakter der Probleme betont, die eine Zugangssteuerung in Mehrfachhopping-Topologien beweltigen muß. Einerseits kann eine Station, z.B. K, ihre Nachbarn darüber informieren, wie ihren Eingangsdurchsatz F(TK) erhöht werden kann, aber K kann nicht darüber urteilen, ob diese Erhöhung erforderlich ist (T(TK) ist unbekannt). Andererseits kann eine Station I versuchen, ihre Nachbarn mitzuteilen, daß sie genug übertragen können (ihr Ausgangsverhältnis ist zu gering), aber beim Erfolg wissen ihre Nachbarn nicht, wie auf die Erhöhung der Erfolge zu reagieren, und wissen ihre Nachbarn nicht, wie auf die Erhöhung des Ausgangsdurchsatzes der Station I reagiert werden muß.
• Das Beispiel nach Fig. 2 veranschaulicht diesen Zustand. Es zeigt ebenfalls, daß die allgemeine Annäherung, die in der Erhöhung der Zugangsrate der Station I besteht, die einen örtlich minimalen Ausgangsanteil 0(I) darstellt, die Leistungen in anderen Teilen des Netzes nachteilig beeinflussen können.
• Angenommen sei, daß die Station T durch Verkehr hauptsächlich aus der Gruppe M überlastet wird. Hierdurch hat I ein kleines Ausgangsverhältnis, viel kleiner als das ihrer einzigen Nachbarn A und insbesondere E und F, die über die Gruppe L leicht übertragen. Ein Versuch zum Erhöhen des Ausgangsdurchsatzes von I durch Erhöhung ihrer Zugangsrate g(I) würde nur den Zustand für die Gruppe M verschlimmbessern, die die Station (S) mit minimalem Ausgangsverhältnis enthalten könnte. Hierdurch zeigt es sich, daß Zugangsraten nur mit äußerster Sorgfältigkeit erhöht werden können. Dieses Beispiel betont klar die doppelte Art der Probleme, die die Zugangssteuerung beweltigen muß. Einerseits wissen die Station I und möglicherweise einige Stationen in M, daß ihre Ausgangsdurchgänge zu klein sind, aber sie wissen nicht, auf welche Weise sie verbessert werden können, und andererseits weiß diese Station T, daß ihr Eingangsdurchsatz größer sein könnte, aber sie weiß nicht, wann eine Erhöhung erforderlich ist. Dieser Zustand kann nur durch Ermöglichung von Informationsaustausch gelöst werden. Nachstehend wird ein verteiltes Protokoll nach der Erfindung beschrieben, das darauf gerichtet ist, das kleinste Ausgangsverhältnis auf Mamimal einzustellen, und daß zwei aufeinanderfolgende Informationsaustauschvorgänge erfordert.
• Zurück zum Beispiel nach der Veranschaulichunt in Fig. 2 kann dieses erfindungsgemäße Protokoll folgende Schritte enthalten:
• 1. Die Station I sendet ihr Ausgangsverhältnis aus;
• 2. (a) Die Station T verwirklicht durch Vergleich, daß das Ausgangsverhältnis der Station I das kleinste ist, und daß sie ein potentieller Empfänger der Pakete der Station I ist (d.h. durch eine Prüfung in ihrer Leitwegtabelle);
• (b) Die Station T leitet ihren Nachbarn weiter, daß ihre Eingangsdurch- Sätze erhöht werden müssen, und erzählt sie, auf welche Weise das erfolgen kann (d.h. durch Aussendung von Gcur(T) und Gnom(T);
• 3. Die Nachbarn von T ändern dabei ihre Zugangsrate, um Gcur(T) näher bei Gnom(T) zu bringen.
• Das Protokoll erfordert zwei aufeinanderfolgende Informationsaustauschvorgänge. Zunächst werden die Ausgangsverhältnisse ausgetauscht. Dies ermöglicht es jeder Station K, ihre Eingangsdurchgangserhöhungstendenz zu berechnen (IFIT):
• IFIT(K) = [ min 0(L)]&supmin;&sup4;, (7)
• L KεR(L)
• worin R(L) die Gruppe von Stationen bezeichnet, die die von der Station L emittierten Pakete weiterleiten kann. Das Minimum wird also über die Stationen L genommen, die Nachbarn (in Hörabstand) von K sind und von K weitergeleitet werden können. Diese Variable IFIT(K) mißt, auf welche Weise vieles des Eingangsdurchsatzes F(TK) der Station K verbessert werden kann (weitere Maßnahmen des Eingangsdurchflußerhöhungstendenz wird nachstehend näher erläutert). Im Netzwerk als ganzem erreicht IFIT(K) ein Maximalwert für die Station(en) K, die Weiterleitungen der Station mit dem allgemeinen minimalen Ausgangsverhältnis sind. Die Bestimmung der IFIT entspricht dem Schritt (2a) im obigen Protokoll.
• Der zweite Informationsaustausch bezieht sich auf die IFIT. Dieser Austausch ermöglich jeder Station K die Bestimmung der Station in ihrer Umgebung N(K), die die maximale IFIT darstellt:
• und läßt TK diese Station bezeichnen. In N(K) ist TK die Station, deren Eingangsdurchfluß erhöht werden muß. Die Station K muß dabei ihre Zugangsrate dementsprechend ändern. Also zielt dieses Protokoll auf die Erhöhung eines kleinsten Ausgangsverhältnis 0(I) durch Erhöhung des Eingangsdurchflusses einer Station TK, die I weiterleiten kann. Die Zugangsrate g(K) wird auf diese Weise entsprechend den folgenden Regeln aktualisiert, die in Fig. 3A angegeben sind.
• In dieser Figur 3A bezeichnen gmin bzw. gmax die minimalen und maximalen Zugangsraten, die zulässig sind, und ε, δ1, δ2, δ3 und δ4 sind Protokollparameter. Akzeptable Zahlen für diese Protokollparameter sind in Fig. 3B angegeben. Wenn die Belastung der Station TK zu hoch ist, reduzieren alle ihren Nachbarn ihre Zugangsrate. Wenn die Belastung von TK zu gering ist, kann die Station K ihre Zugangsrate nur erhöhen, wenn sie das minimale Ausgangsverhältnis hat, und wenn die Station TK K weiterleiten kann. Wenn die Verkehrsbelastung von TK bereits optimal abgestimmt ist, besteht die einzige nützliche Aktualisierung in eine geringe Erhöhung der Zugangsrate zur Station mit dem kleinsten Ausgangsverhältnis und in der geringen Reduktion der Zugangsraten der anderen Stationen.
• Die Aktualisierung der Zugangsraten wird komplizierter, wenn die Station TK nicht eindeutig ist. In diesem Fall müssen die Zugangsraten aktualisiert werden, um allgemein den Eingangsdurchsatz der Stationen TK zu erhöhen. Einiger Vorzug kann den Stationen TK erteilt werden, die nächst zur Bestimmung sich befinden, um eine höhere Priorität dem Verkehr zu erteilen, die das Netzwerk verlassen muß.
• Folgende allgemeinere Definition des Ausgangsverhältsnisses berücksichtigt begrenzende Bedingungen:
• Das Ausgangsverhältnis einer Station, die nichts zu übertragen hat oder hatte ist also (n(K) = 0 = q(K) ein Maximum.
• Außerdem ist die Eingangsdurchflußerhöhungstendenz IFIT oben als der invertierte Wert eines kleinsten Ausgangsverhältnisses definiert. Im praktischen Sinne gewährleistet dies, daß jede Station, die übertragen muß, einen minimalen Ausgangsdurchfluß ?. Es kann als eine Berechtigungseigenschaft des Protokolls betrachtigt werden. Andere Maßnahmen des IFIT kann der umgekehrte Wert des mittleren Ausgangsverhältnisses sein
• oder der umgekehrte Wert eines verallgemeinerten Ausgangsverhältnisses
• Mit diesen Maßnahmen werden die Leistungen jeder Station mit denen ihrer Nachbarn gemischt. Das Ergebnis kann ein Berechtigungsverlust eines Zustandes sein, in dem eine station nur wenige Pakete übertragen muß, aber einen nullwertigen Ausgangsdurchfluß hat.
• Die Zugangsrate g(K) muß auf spezifische Weise aktualisiert werden, wenn die Station mit maximalem IFIT die Station K selbst ist. Diese Aktualisierung muß dabei die Art und Weise berücksichtigen, wie die eigene Zugangsrate g(K) der Station K der Anzahl von der Station K richtig empfangener Pakete stört. Beispielsweise wenn die Station zum Empfangen unfähig ist, wenn sie im Übertragen begriffen ist, muß die Zugangsrate g(K) reduziert werden, um den Eingangsdurchsatz von K zu erhöhen.
• Alle hier beschriebenen Protokolle erfordern Informationsaustauschvorgänge. Daher müssen minimale Ausgangs- und Eingangsdurchgänge in jeder Station gewährleistet werden, um den Betrieb des Protokolls zu ermöglichen. Eine Folge dieser Anforderung ist, daß die Berechtigungseigenschaft des Protokolls vital erscheint.
• Eine Hardware-Konfiguration der verschiedenen Schaltungen in einer Station, die zum Arbeiten in einem Netzwerk entwickelt sind, in dem das oben beschriebene Verfahren implementiert wird, ist schematisch in Fig. 4 dargestellt.
• In Fig. 4 ist in Form eines Blockschaltbildes eine Station 10 mit einem Empfängerabschnitt 11, einem Senderabschnitt 12, einer Verkehrssteuerstufe 13 und einer zusätzlichen Steuerstufe 14 dargestellt. Im Betrieb arbeitet der Empfängerabschnitt 11 zum Empfangen von Datenpaketen aus verschiedenen Kanälen, und diese Datenpakete werden auf die Verkehrssteuerstufe 13 übertragen. Die Verkehrssteuerstufe 13 überwacht die Bestimmung jedes empfangenen Datenpakets und überträgt außerdem ein empfangenes Datenpaket auf den Senderabschnitt, wenn die Station 10 das empfangene Datenpaket weiterleiten muß, oder überträgt das empfangene Datenpaket auf den Ausgang 15, wenn die Station 10 die Bestimmung des empfangenen Datenpakets war, oder löscht sonst das empfangene Datenpaket. Die Arbeit des empfängenen Abschnitts 11, des Senderabschnitts 12 und der Verkehrssteuerstufe 13 wird als dem Fachmann in diesem Bereich bekannt angenommen und daher wird eine detaillierte Beschreibung der Arbeit dieser Schaltungen als überflüssig betrachtet.
• Nach obiger Angabe wird die Station 10 mit einer zusätzlichen Steuerstufe 14 ausgerüstet, die eine Anzahl von Unterschaltungen enthält, wie z.B. eine erste Berechenstufe 16, eine zweite Berechenstufe 17, eine dritte Berechenstufe 18, einen Vergleichsabschnitt 19 und ein Zugangsratenwechselmittel 20.
• Im Betrieb empfängt die erste Berechenstufe 16 Information aus der Verkehrssteuerstufe 13 beim jeweiligen erfolgreichen Übertragen eines Datenpakets vom Senderabschnitt 12. Die Berechenstufe 16 berechnet auf der Basis der Information aus der Verkehrssteuerstufe 13 den oben genannten ersten Parameter, der für die Anzahl der je Zeiteinheit von dem Senderabschnitt 12 erfolgreich übertragenen Pakete bezeichnend ist, oder mit anderen Worten der erste Parameter, der für den Ausgangsdurchfluß der Station 10 bezeichnend ist. Der berechnete erste Parameter wird von der Berechenstufe 16 dem Senderabschnitt 12 zugeleitet und auf die benachbarten Stationen übertragen.
• In der Station 10 empfängt der Empfängerabschnitt 11 ebenfalls erste Parameter aus benachbarten Stationen, und diese Parameter werden aus dem Empfängerabschnitt 11 auf eine zweite Berechenstufe 17 übertragen, in der sie zum Berechnen des oben genannten zweiten Parameters verwendet werden, der für die Eingangsdurchflußerhöhungstendenz der Station 10 bezeichnend ist.
• Das dritte Berechnungsmittel 18 empfängt Information aus der Verkehrssteuerstufe 13 und berechnet auf dieser Basis einen dritten Parameter, der für die Belastung der Station 10 bezeichnend ist.
• Sowohl der von der zweiten Berechenstufe 17 berechnete zweite Parameter als auch die von der dritten Berechenstufe 18 berechnete dritte Parameter werden auf den Senderabschnitt 12 übertragen und gelangen an alle benachbarten Stationen in der Reichweite der Station 10.
• Zweite und dritte Parameter aus benachbarten Stationen, die im Empfängerabschnitt 11 empfangen wurden, werden auf einen Vergleichsabschnitt 19 übertragen, in dem die empfangenen Parameter aus allen benachbarten Stationen miteinander verglichen werden, und in dem entschieden wird, welche Station in der direkten Umgebung der Station 10 die größte Eingangsdurchflußerhöhungstendenz aufweist. Ein diese Entscheidung reflektierendes Signal wird vom Vergleichsabschnitt 19 auf das Zugangsratenwechselmittel 20 übertragen, das auf den Empfang eines derartigen Signals durch die Lieferung geeigneter Steuersignale an die Verkehrssteuerstufe 13 antwortet, um die Zugangsrate der Station 10 auf die oben beschriebene Weise zu aktualisieren.
• Obgleich in Fig. 4 die zusätzliche Steuerstufe 14 eine Anzahl getrennter Unterschaltungen 16, 17, 18, 19 und 20 enthält, wird es klar sein, daß in einem moderneren Ausführungsbeispiel die zusätzliche Steuerstufe 14 einen geeignet programmierten Prozessor oder Computer enthalten kann, in dem die verschiedenen Berechnungen und Vergleichsoperationen ausgeführt werden, und der einerseits geeignete Signale an den Senderabschnitt 12 und andererseits Steuersignale an die Verkehrssteuerstufe 13 liefert.

Claims (11)

1. Verfahren zur Zugangsratensteuerung von Stationen in einem Paketvermittlungsnetzwerk, mit einer Anzahl von Sende-Empfangsstationen (10), die über Funkverbindungskanälen miteinander verbunden sind, über die Datenpakete von der einen Station nach der anderen entsprechend einem Leitwegplan übertragbar sind, wobei im Betrieb des Netzwerks jede Station (10) einen ersten Parameter berechnet, der für ihren Ausgangsdurchfluß bezeichnend ist, der die Anzahl der je Zeiteinheit erfolgreich übertragenen Pakete darstellt, dadurch gekennzeichnet, daß jede Station den ersten Parameter in vrogegebenen Zeitintervallen nach allen benachbarten Stationen in der Reichweite der Station überträgt, hiernach jedes Station einen zweiten Parameter berechnet, der für ihre Eingangsdurchflußerhöhungstendenz bezeichnend ist, die ein Maß auf der Basis der Ausgangsdurchflüsse der benachbarten Stationen ist, aus dem sich die Station verlassen kann und größer wird, wenn diese Ausgangsdurchflüsse abfallen, und einen dritten Parameter berechnet, der für ihre Belastung bezeichnend ist, wonach jede Station den zweiten und den dritten Parameter auf ihre benachbarten Stationen überträgt, die nach dem Empfang des zweiten und des dritten Parameters bestimmen, welche Station in ihrer Umgebung die größte Eingangsdurchflußerhöhungstendenz besitzt, und auf der Basis des dritten Parameters ihre Zugangsrate aktualisieren, um die Belastung der Station des dritten Parameters auf ihre Zugangsrate zu bringen, und die Belastung der Station mit der größten Eingangsdurchflußerhöhungstendenz näher bei der Nennkanalbelastung zu bringen.

2. Verfahren nach Anspruch 1, dadurch gekennzeichnet, daß der erste Parameter das Ausgangsverhältnis ist, das zwischen dem Durchfluß richtig ausgesandter und bestätigter Pakete und dem auszusendenden Durchfluß herrscht.

3. Verfahren nach Anspruch 2, dadurch gekennzeichnet, daß das Ausgangsverhältnis als das Verhältnis zwischen der Anzahl erfolgreich ausgesandter und bestätigter Pakete in einer vorgegebenen Zeit und der Summe der Anzahl und der Anzahl von Paketen herrscht, die noch am Ende der Zeit Schlange stehen.

4. Verfahren nach einem der Ansprüche 1 bis 3, dadurch gekennzeichnet, daß die Eingangsdurchflußerhöhungstendenz wie folgt definiert wird:

IFIT(K) = [ min 0(L)]&supmin;&sup4;,

L KεR(L)

worin IFIT(K) = die Eingangsdurchflußerhöhungstendenz der Station K, R(L) = die Gruppe von Stationen sind, die die von der Station L emittierten Pakete weiterleiten kann, und 0(L) = das Ausgangsverhältnis der Station L ist.

5. Verfahren nach einem der Ansprüche 1 bis 5, dadurch gekennzeichnet, daß die Zugangsrate g(K) jeder Station in Übereinstimmung mit folgenden Regeln aktualisiert wird: wenn so ist

worin Gmin bzw. Gmax die Mindest- und Höchstzugangsraten bezeichnen, die zulässig sind, und worin ε, δ1, δ2, δ3 und δ4 Protokollparameter sind.

6. System zum Steuern der Zugangsrate der Station (5) in einem Datenpaketvermittlungsnetzwerk, mit einer Anzahl von Sende-Empfangsstationen (10), die über Funkverbindungskanälen miteinander verbunden sind, über die Datenpakete von der einen Station nach der anderen entsprechend einem Leitwegplan übertragen werden können, wobei jede Station folgende Elemente enthält:

- Mittel (11) zum Empfangen und Mittel (12) zum Aussenden von Datenpaketen,

- erste Berechnungsmittel (16) zum Berechnen eines ersten Parameters, der für ihren Ausgangsdurchfluß bezeichnend ist, der die Anzahl der je Zeiteinheit erfolgreich übertragenen Pakete darstellt,

dadurch gekennzeichnet, daß jede Station außerdem folgende Elemente enthält:

- zweite Berechnungsmittel zum Berechnen eines zweiten Parameters, der für ihre Eingangsdurchflußerhöhungstendenz bezeichnend ist, die ein Maß auf der Basis der Ausgangsdurchflüsse der benachbarten Stationen ist, die die Station weiterleiten kann, wobei der zweite Parameter größer wird, wenn diese Ausgangsdurchflüsse abfallen,

- dritte Berechnungsmittel (18) zum Berechnen eines dritten Parameters, der für ihre Belastung bezeichnend ist,

- Sendemittel (12) zum Übersenden der ersten, zweiten und dritten Parameter nach allen benachbarten Stationen in der Reichweite der Station,

- Zugangsratenänderungsmittel (20) zum Ändern ihrer Zugangsrate,

- Vergleichsmittel (19),

wobei das System im Betrieb des Netzwerks auf derartige Weise arbeitet, daß in jeder Station der erste Parameter im ersten Berechnungsmittel (16) berechnet und vom Sendemittel in regelmäßigen Zeitintervallen nach allen benachbarten Stationen in der Reichweite der betreffenden Station übertragen wird, in jeder Station hiernach der zweite und der dritte Parameter in dem zweiten (17) und in dem dritten (18) Berechnungsmittel berechnet werden, wonach das Sendemittel (12) in jeder Station den zweiten und den dritten Parameter auf ihre benachbarten Stationen überträgt, in denen das Vergleichmittel (19) nach dem Empfang des zweiten und des dritten Parameters bestimmen, welche Station in ihren Umgebungen die größte Eingangsdurchflußerhöhungstendenz aufweist und dem Änderungsmittel (20) ermöglicht, auf der Basis des dritten Parameters ihre Zugangsrate zu aktualisieren, um die Belastung der Station mit der größten Eingangsdurchflußerhöhungstendenz näher bei der Nennkanalbelastung zu bringen.

7. System nach Anspruch 6, dadurch gekennzeichnet, daß daß der erste Parameter das Ausgangsverhältnis ist, das zwischen dem Durchfluß der richtig ausgesandten und bestätigten Pakete und dem Durchfluß der zu übersendenden Pakete herrscht.

8. System nach Anspruch 7, dadurch gekennzeichnet, daß im Betrieb das erste Berechnungsmittel (16) das Ausgangsverhältnis als das Verhältnis zwischen der Anzahl von Datenpaketsendemittel (20) erfolgreich übersandten und in einer vorgegebenen Zeit bestätigten Pakete und der Summe zwischen der Anzahl und der Anzahl der Pakete, die in dem Datenpaketsendemittel am Ende der Zeit immer noch Schlange stehen berechnet.

9. System nach einem der Ansprüche 6 bis 8, dadurch gekennzeichnet, daß im Betrieb das zweite Berechnungsmittel die Eingangsdurchflußerhöhungstendenz anhand des nachstehenden Algorithmus berechnet:

IFIT(K) = [ min 0(L)]&supmin;¹,

L KεR(L)

worin IFIT(K) = die Eingangsdurchflußerhöhungstendenz der Station K ist, R(L) = die Gruppe von Stationen ist, die die von der Station L ausgesandten Pakete weiterleiten kann, und 0(L) = das Ausgangsverhältnis der Station L ist.

10. System nach einem der Ansprüche 6 bis 9, dadurch gekennzeichnet, daß die Zugangsrate g(K) jeder Station von dem Änderungsmittel (20) in Übereinstimmung mit nachstehenden Regeln aktualisiert wird: wenn so ist

worin Gmin bzw. Gmax die Mindest- und Höchstzugangsraten bezeichnen, die zulässig sind, und worin ε, δ1, δ2, δ3 und δ4 Protokollparameter sind.

11. System nach einem der Ansprüche 6 bis 10, dadurch gekennzeichnet, daß das erste (16), das zweite (17) und das dritte (18) Berechnungsmittel in einem geeignet programmierten Computer kombiniert werden.