-
HINTERGRUND DER ERFINDUNG
-
(1) Gebiet der Erfindung:
-
Die
vorliegende Erfindung bezieht sich auf eine Paketweiterleitungsvorrichtung,
die mit einem Paketweiterleitungsnetz verbunden ist, und insbesondere
auf eine Verkehrsformungseinheit, die in der Paketweiterleitungsvorrichtung
vorgesehen ist.
-
(2) Beschreibung des Standes der Technik:
-
In
der Paketweiterleitung, die in einem Netz wie etwa im Internet oder
dergleichen genutzt wird, unterteilt ein Nutzer Informationen in
Datenblöcke (Nutzinformationsdaten)
mit einer Länge
von etwa mehreren zehn Bytes bis etwa zehntausend Bytes. Diese Datenblöcke werden
als Pakete weitergeleitet, zu denen in Übereinstimmung mit den für jedes
Kommunikationsprotokoll bestimmten Formaten Köpfe hinzugefügt werden,
die jeweils Zielinformationen und Steuerinformationen enthalten.
-
Die
Pakete haben für
alle Protokolle eine andere Länge.
Es sind solche bekannt, bei denen alle Pakete wie im Fall eines
IP (Internetprotokolls) eine variable Länge haben, und jene, die jeweils
wie etwa im ATM (Asynchronen Übertragungsmodus)
eine feste Länge
haben. In letzter Zeit werden auf ein öffentliches Paketnetz preiswerte
Dienste angewendet. Die Aufmerksamkeit konzentriert sich auf ein
Virtuelles Privates Netz (VPN), in dem mehrere private Netze über ein öffentliches
Paketnetz miteinander verbunden sind.
-
In 2 ist
ein Diagramm der Verbindungen zwischen Unternehmensnetzen über ein öffentliches Netz
gezeigt.
-
In 2 sind
ein privates Netz A41 und ein privates Netz B42 über ein öffentliches Netz 40 miteinander
verbunden. Wenn über
ein öffentliches
Netz Übermittlungen
ausgeführt
werden, geht jeder Anwender normalerweise vor der Paketweiterleitung
mit einem Manager für
das öffentliche
Netz einen Vertrag für
eine Sendebandbreite und für
Paketweiterleitungsprioritäten
ein.
-
Wenn
der Vertrag zwischen jedem der Anwender und dem Manager des öffentlichen
Netzes abgeschlossen worden ist und ein Endgerät Pakete an das öffentliche
Netz zu übertragen
oder weiterzuleiten beginnt, überwacht
eine Paketweiterleitungsvorrichtung 402, die sich am Eintritt
des öffentlichen Netzes
befindet, für
jedes Endgerät
eine Sendebandbreite, um die Priorität von Paketen von einem Endgerät, das den
Inhalt des Vertrags verletzt, zu verringern oder um Verletzungspakete
zu verwerfen. Diese Überwachungsfunktion
auf Seiten des öffentlichen Netzes
wird als UPC (Nutzungsparametersteuerung) bezeichnet. Selbst wenn
ein Paket während
der Übermittlungen
verworfen wird, ist ein empfangendes Endgerät normalerweise mit einer Funktion
zum Erkennen des Auftretens eines verworfenen Pakets und zum Anfordern
einer erneuten Sendung des Pakets zu einem sendenden Endgerät versehen,
während
das sendende Endgerät
mit der Funktion zum erneuten Senden des Pakets versehen ist. Somit
gibt es schließlich
keine Weglassung von Informationen. Allerdings ist es erwünscht, das
Auftreten des Paketverwerfens zu vermeiden, da dies zu einer starken Zunahme
der Übertragungsverzögerung und
zu einer Stauung von Netzen wegen erneut gesendeter Pakete führen könnte.
-
Somit
muss eine Paketweiterleitungsvorrichtung 401, die Pakete
an das öffentliche
Netz sendet, die Pakete gemäß der Steuerung
einer Sendebandbreite in der Weise senden, dass die Pakete nicht durch
die UPC des öffentlichen
Netzes verworfen werden. Die Funktion zum Steuern dieser Paketsendebandbreite
wird als Verkehrsformungsfunktion bezeichnet oder einfach Formungsfunktion
genannt. Es kann Fälle
geben, in denen für
das sendende Endgerät
eines Anwenders oder für
einen Austrittsabschnitt eines öffentlichen
Netzes zum Senden von Paketen an ein privates Netz sowie für die oben
beschriebene direkt mit dem öffentlichen
Netz verbundene Paketweiterleitungsvorrichtung eine Formungseinheit
erforderlich ist, um die Formungsfunktion zu realisieren.
-
Der
für jeden
Anwender durch das öffentliche Netz
bereitgestellte Dienst, d. h. der zwischen dem Anwender und dem
Manager des öffentlichen
Netzes abgeschlossene Vertrag, ist grob in einen Vertrag, gemäß dem Pakete
gesendet werden, nachdem eine vorgegebene Bandbreite in dem öffentlichen
Netz immer sichergestellt ist, und in einen Vertrag vom Typ des
besten Bemühens,
gemäß dem Pakete
weitergeleitet werden, ohne eine Bandbreite in einem öffentlichen
ATM-Netz sicherzustellen, klassifiziert. Das Erstere ist geeignet
für die Übertragung
von Sprache oder dergleichen, da das Paket immer mit einer vorgegebenen
Bandbreite übertagen
werden kann, ohne durch die Verkehrsmenge für andere Anwender in dem öffentlichen
Netz beeinflusst zu werden. Das Letztere ist normalerweise preiswerter
als ein Vertrag mit fester Bandbreite, obgleich eine Übertragungsverzögerung je
nach der Verkehrsmenge für
andere Anwender zunehmen könnte
oder Pakete in dem Netz verworfen werden könnten. Dies wird für die Übertragung
von Bündeldaten-
oder Ausbruch datenverkehr wie etwa FTP (Dateiübertragungsprotokoll), E-Mail
usw. verwendet.
-
In
letzter Zeit ist eine Klasse vorgeschlagen worden, die eine vorgegebene
Bandbreite selbst dann garantiert, wenn ein öffentliches Netz belegt ist, während sie
der Vertrag vom Typ des besten Bemühens ist. Im ATM wird dies "GFR (Garantierte
Rahmenrate)" genannt.
In dieser Klasse werden die minimale garantierte Bandbreite und
die maximale Sendebandbreite vor der Übertragung von Paketen vertraglich
vereinbart. Wenn das öffentliche
Netz nicht belegt ist, werden die Pakete mit der maximalen Sendebandbreite
weitergeleitet, während
Pakete, die der minimalen garantierten Bandbreite entsprechen, selbst
dann sicher übertragen
werden, wenn das Netz belegt wird.
-
RFC
2475 beschreibt eine Paketweiterleitungsvorrichtung gemäß dem Oberbegriff
von Anspruch 1.
-
Ein
Verfahren zur Realisierung der Formungseinheit ist z. B. in "Traffic Shaping Device" beschrieben worden,
die in der japanischen veröffentlichten
ungeprüften
Patentanmeldung Nr. Hei 9-307566 (Stand der Technik 1) offenbart
worden ist. Der Stand der Technik 1 hat einen ATM beschrieben. Insbesondere
wird ein in dem ATM genutztes Paket fester Länge allgemein als "Zelle" bezeichnet. Im Stand
der Technik 1 sind für
alle Vertragseinheiten (z. B. VC: Virtuelle Verbindungen), bei denen
es erwünscht
ist, die Formung auszuführen,
Warteschlangen vorgesehen. Bei der Sendung der Zellen wird eine
Zeit berechnet, zu der bei einer VC mit gesendeten Zellen die nächste Zelle
gesendet werden kann, (im Folgenden "geplante Sendezeit" genannt) und unter Verwendung einer
binären
Baumstruktur gespeichert.
-
In
diesem Fall werden die geplanten Sendezeiten bei der jeweiligen
VC unten in einem binären Baum
gespeichert. Weiter gehen VC mit früher geplanten Sendezeiten,
die jenen entsprechen, die auf einer Zeitbasis in der Vergangenheit
liegen, nach oben, während
sie über
andere hinausgehen und schließlich
die VC mit der frühesten
geplanten Sendezeit ausgewählt
wird. Somit wird eine geplante Sendezeit, die einem der Werte unten
in dem binären Baum
entspricht, für
die mit der höchsten
Priorität
zu sendende VC oben in dem binären
Baum gespeichert.
-
Die
Berechnung und die Sortierung jeder geplanten Sendezeit werden selbst
dann, wenn eine Zelle in einem von auf das Senden wartenden Zellen freien
Zustand empfangen wird, sowie bei einer Zellensendung ausgeführt. Da
die Sortierung unter Verwendung eines Sortierergebnisses ausgeführt werden
kann, das durch die binäre
Baumstruktur bei der vorhergehenden Zellensendung angegeben wird, kann
somit die VC, die mit einer höchsten
Priorität
zu senden ist, in einer Verarbeitungszeit in der Größenordnung
von log{VC-Nummer} ausgewählt
werden.
-
In
den Paketen, die an einen Kommunikationsweg oder -kanal gesendet
werden, sind wichtige Pakete und Pakete, die nicht besonders wichtig
sind, in gemischter Form vorhanden. Die wichtigen Pakete sind hier
Pakete für
Verkehre, die für
die Übertragung mit
niedriger Verzögerung
wie etwa "telnet" usw. benötigt werden,
während
die Pakete, die soweit nicht wichtig sind, Pakete für Verkehre
sind, die wie im Fall der E-Mail selbst dann, wenn die Verzögerung zunimmt,
unter weniger Einfluss versetzt werden.
-
Es
ist wichtig, eine solche Prioritätssteuerung
auszuführen,
dass dann, wenn auf diese Weise die wichtigen Pakete und die soweit
nicht wichtigen Pakete in gemischter Form vorhanden sind, die wichtigen
Pakete selbst dann, wenn das Netz überfüllt ist, vorzugsweise vor den
anderen gesendet werden. Somit enthält ein Kopf des normalen Pakets
ein Feld zur Angabe der Priorität
des Pakets. Zum Beispiel wird für
ein IP-Paket ein TOS-Feld (Diensttypfeld) vorbereitet, während für eine ATM-Zelle
ein CLP-Bit (Zellenverlustprioritätsbit) vorbereitet wird. Im
Interesse der Einfachheit wird die Priorität im Folgenden übrigens
als zwei Stufen, hohe Priorität
und niedrige Priorität,
erläutert.
Allerdings kann jedem IP-Paket außerdem eine weiter detaillierte
Priorität
zugeteilt werden. Ferner wird ein Paket, dem eine hohe Priorität zugewiesen
worden ist, als ein Paket hoher Priorität beschrieben und ein Paket,
dem eine niedrige Priorität
zugewiesen worden ist, als ein Paket niedriger Priorität beschrieben.
-
Wenn
die herkömmliche
Formungseinheit auf den Dienst vom Typ des besten Bemühens angewendet
wird, der eine Bandbreitengarantie ausführt, werden alle Pakete mit
hoher Priorität
gesendet. Die Priorität
jedes Pakets hoher Priorität,
das die Garantiebandbreite überschritten
hat, wird durch die UPC-Funktion verringert. Da zu dieser Zeit das
Paket hoher Priorität
und das Paket niedriger Priorität
bestimmt werden, ohne die oben beschriebenen wichtigen Pakete oder
unwichtigen Pakete zu berücksichtigen,
könnte
ein wichtiges "telnet"-Paket dem Paket niedriger
Priorität
zugewiesen werden oder könnte ein
Web-Paket, das nicht besonders wichtig ist, dem Paket hoher Priorität zugewiesen
werden. Dies ist keine für
Anwender erwünschte
Prioritätszuweisung.
-
Es
ist leicht, in der Formungseinheit die wichtigen Pakete den Paketen
hoher Priorität
zuzuweisen und die unwichtigen Pakete den Paketen niedriger Priorität zuzuweisen.
Falls die Formung jedoch nicht in der Weise ausgeführt wird,
dass die Sendebandbreite für
Pakete hoher Priorität
unter die garantierte Bandbreite fällt, wird die Priorität durch
die UPC zufällig
verringert. Somit ist dies für
die Anwender ebenfalls keine wünschenswerte
Prioritätszuweisung.
Ferner kann die garantierte Bandbreite nicht effektiv genutzt werden,
wenn die Verkehrsmenge für
wichtige Pakete klein ist. Da ein Hauptziel zum Ausführen der Abrechnung
die garantierte Bandbreite ist, ist es wichtig, dass die garantierte
Bandbreite vollständig effektiv
genutzt wird.
-
ZUSAMMENFASSUNG DER ERFINDUNG
-
Eine
erste Aufgabe der vorliegenden Erfindung ist die Schaffung einer
Formungseinheit, in der unter Paketen, die an dasselbe Ziel gesendet
werden, Pakete, die vorzugsweise zu senden sind, mit einer garantierten
Bandbreite gesendet werden, die vor der Paketübertragung vertraglich vereinbart
wird, wobei dann, wenn es eine Zuteilung für eine Kanalbandbreite gibt,
Nichtprioritätspakete
in der Weise gesendet werden, dass eine Bandbreite, die der Summe
einer Sendebandbreite für
die Prioritätspakete
und einer Sendebandbreite für
die Nichtprioritätspakete
entspricht, unter die vor der Paketübertragung vertraglich vereinbarte
maximale Übertragungsbreite
fällt.
-
Eine
zweite Aufgabe der vorliegenden Erfindung ist die Schaffung einer
Formungseinheit, in der eine Prioritätszuweisung ausgeführt wird,
die für
die oben erwähnten
Anwender erwünscht
ist, wobei einige Pakete, die nicht besonders wichtig sind, als
Pakete hoher Priorität
gesendet werden, um dadurch die garantierte Bandbreite effektiv
zu verwenden.
-
Eine
dritte Aufgabe der vorliegenden Erfindung ist die Schaffung einer
Formungseinheit, die einen GFR-Dienst bewältigen kann, der eine Bandbreitengarantie
in Einheiten von Paketen der oberen Schicht in einem ATM-Netz ausführt.
-
Zur
Lösung
der oben erwähnten
Aufgaben schafft die vorliegende Erfindung eine Paketweiterleitungsvorrichtung
und ein Verfahren zum Setzen der Priorität von Paketen gemäß den unabhängigen Ansprüchen. Die
abhängigen
Ansprüche
beziehen sich auf bevorzugte Ausführungsformen.
-
Es
wird eine Formungseinheit, die sich in der Leitungsschnittstelle
einer Paketweiterleitungsvorrichtung befindet, mit einer Warteschlange
zum Speichern von Paketen hoher Priorität (im Folgenden eine "Prioritätswarteschlange" genannt) und mit
einer Warteschlange zum Speichern von Paketen niedriger Priorität (im Folgenden
eine "Nichtprioritätswarteschlange" genannt) für jeden
Anwender geschaffen. Die Prioritätswarteschlange
und die Nichtprioritätswarteschlange
können
für jeden
Anwender eine nach der anderen vorbereitet werden. Alternativ können für jede Prioritätsklasse
mehrere Warteschlangen vorhanden sein.
-
Außerdem ist
die Formungseinheit gemäß der vorliegenden
Erfindung mit einem Rechner für geplante
Sendezeiten zum Berechnen einer geplanten Sendezeit eines Kopfs
oder eines vordersten Pakets in auf das Senden wartenden Paketen,
die in jeder Prioritätswarteschlange
gespeichert sind, um eine garantierte Bandbreite aufrechtzuerhalten, zum Berechnen
einer geplanten Sendezeit eines vordersten Pakets in auf das Senden
wartenden Paketen, die in jeder Nichtprioritätswarteschlange gespeichert sind,
als eine sofortige gesendete Zeit, und zum Berechnen einer geplanten
Sendezeit, die einer Sendebandbreite (maximalen vertraglich vereinbarten Bandbreite)
entspricht, die die beiden Bandbreiten der Prioritätswarteschlange
und der Nichtprioritätswarteschlange
integriert, versehen. Ferner enthält die Formungseinheit eine
Prioritätsinformations-Ergänzungsschaltung
zum Zuteilen einer hohen Priorität
zu einem Paket, das aus der Prioritätswarteschlange ausgelesen
wird, und zum Zuteilen einer niedrigen Priorität zu einem Paket, das aus der
Nichtprioritätswarteschlange
ausgelesen wird. Wegen des Rechners für geplante Sendezeiten und
der Prioritätsinformations-Ergänzungsschaltung
können
wichtige Pakete als Pakete hoher Priorität mit einer garantierten Bandbreite
gesendet werden und können
Nichtprioritätspakete
als Pakete niedriger Priorität
mit einer verbleibenden Bandbreite, die die Differenz der maximalen
vertraglich vereinbarten Bandbreite und der garantierten Bandbreite
ist, gesendet werden.
-
Der
Rechner für
geplante Sendezeiten kann bei Berechnung einer geplanten Sendezeit
für die Prioritätswarteschlange
auf eine Warteschlangenlänge
(die Anzahl gespeicherter Pakete) jeder Prioritätswarteschlange Bezug nehmen
und eine sofortige Sendezeit als die geplante Sendezeit berechnen, ohne
eine garantierte Bandbreite aufrechtzuerhalten, wenn eine vorgegebene
Menge oder mehr Mengen von Paketen gespeichert sind. Somit ist es
möglich, eine
solche Erscheinung zu vermeiden, dass die Anzahl der in der Prioritätswarteschlange
gespeicherten Pakete zunimmt, da die Formung ausgeführt wird, wodurch
die Pakete von der Warteschlange überlaufen.
-
Zur
Lösung
der obigen zweiten Aufgabe ist die Prioritätsinformations-Ergänzungsschaltung
in der vorliegenden Erfindung mit der Funktion versehen, einem auf
das Senden wartenden Paket, das aus der Nichtprioritätswarteschlange
ausgelesen wird, eine hohe Priorität zuzuteilen, wenn kein auf das
Senden wartendes Paket in der Prioritätswarteschlange vorhanden ist,
selbst wenn die Zeit zum Senden eines Pakets von der Prioritätswarteschlange
erreicht ist. Somit wird selbst dann, wenn die Verkehrsmenge für das wichtige
Paket klein ist, die gesamte garantierte Bandbreite auf die Sendung
von Prioritätspaketen
angewendet, wodurch die garantierten Bandbreiten effektiv verwendet
werden können.
-
Zur
Lösung
der obigen dritten Aufgabe enthält
die Formungseinheit gemäß der vorliegenden Erfindung
die Funktion, eine letzte Zelle eines Pakets der oberen Schicht
(im Folgenden EOP-Zelle (Paketende-Zelle) genannt) erst dann zu erfassen
und die oben beschriebene Verarbeitung bei der Sendung oder beim
Empfang des IP-Pakets auszuführen, wenn
die EOP-Zelle gesendet oder empfangen wird. Somit ist es möglich, Zellen
in Einheiten eines zu der oberen Schicht gehörenden Pakets zu senden und zu
empfangen und eine an den GFR-Dienst
angepasste Formung auszuführen.
-
KURZBESCHREIBUNG DER ZEICHNUNG
-
1 ist
ein Blockschaltplan, der eine Konfiguration einer Ausführungsform
einer Verkehrsformungseinheit zeigt, auf die die vorliegende Erfindung angewendet
wird.
-
2 ist
ein Diagramm, das Verbindungen zwischen Unternehmensnetzen über ein öffentliches Netz
veranschaulicht.
-
3 ist
ein Blockschaltplan, der eine Konfiguration einer Ausführungsform
einer Paketweiterleitungsvorrichtung zeigt.
-
4 ist
ein Diagramm, das ein Format eines IP-Pakets zeigt.
-
5 ist
eine Tabelle, die Auswahlregeln für eine in einem Rechner 13 für geplante
Sendezeiten vorgesehene Wähleinrichtung 132 zeigt.
-
6 ist
ein Diagramm, das ein Speicherformat eines Arbeitsspeichers 122 zeigt,
der in einem Speicher 12 für geplante Sendezeiten vorgesehen ist.
-
7 ist
ein ausführlicher
Blockschaltplan der Schaltung 12 des Speichers für geplante
Sendezeiten.
-
8 ist
ein konzeptionelles Diagramm eines Formungszeitgebers, der unter
Verwendung eines Zählers
mit einer endlichen Anzahl von Bits konfiguriert ist.
-
9 ist
ein Ablaufplan zur Bestimmung einer geplanten Sendezeit beim Paketempfang.
-
10 ist
ein Ablaufplan zur Bestimmung einer geplanten Sendezeit bei der
Paketsendung.
-
11 ist
ein Ablaufplan für
die Aktualisierung eines Zeitgültigkeitsmerkers.
-
12 ist
ein konzeptionelles Diagramm, das Beispiele einer Sendebandbreite
für die
Formungseinheit 1 und zu sendende Pakete zeigt.
-
13 ist
ein Blockschaltplan, der eine Konfiguration einer Ausführungsform
einer GFR-Verkehrsformungseinheit veranschaulicht, auf die die vorliegende
Erfindung angewendet wird.
-
14 ist
eine Tabelle, die Auswahlregeln für eine in einem Rechner 73 für geplante
Sendezeiten vorgesehene Wähleinrichtung 732 zeigt.
-
BESCHREIBUNG DER BEVORZUGTEN
AUSFÜHRUNGSFORMEN
-
3 zeigt
eine Konfiguration einer Paketweiterleitungsvorrichtung, auf die
die vorliegende Erfindung angewendet wird.
-
Im
Folgenden wird ein Paket als ein IP-Paket beschrieben. Ein Format
des IP-Pakets ist in 4 gezeigt.
-
Anhand
von 3 ist eine Paketweiterleitungsvorrichtung 98 mit öffentlichen
Netzen 99-1 bis 99-3 verbunden. Die Paketweiterleitungsvorrichtung 98 umfasst
Leitungsschnittstellen 2-1 bis 2-3, die dem Typ
der damit verbundenen Leitung (Ethernet, ATM, Frame Relay usw.)
entsprechen, Paketverarbeitungseinheiten 3-1 bis 3-2,
um jeweils die nächsten Übertragungsziele
zu bestimmen, und einen Kreuzschienenschalter 8 zum Weiterschalten
der mehreren Paketverarbeitungseinheiten.
-
Während die
mehreren Leitungsschnittstellen 2-1 und 2-2 in 3 durch
einen Bus 9 mit einer Paketverarbeitungseinheit 3-1 verbunden
sind, kann eine Leitungsschnittstelle so konfiguriert sein, dass sie
mit einer Paketverarbeitungseinheit verbunden ist. Während die
mehreren Paketverarbeitungseinheiten 3-1 bis 3-2 in 3 ebenfalls
durch den Kreuzschienenschalter 8 miteinander verbunden sind,
kann die Anzahl der Paketverarbeitungseinheiten als eine konstruiert
sein. In diesem Fall wird der Kreuzschienenschalter 8 unnötig.
-
Nachfolgend
wird der Betrieb der Paketweiterleitungsvorrichtung 98 beschrieben,
die darin ein Paket empfängt,
ein Sendeziel wiedergewinnt und ein Paket zu einer dem Ergebnis
der Wiedergewinnung entsprechenden Leitung sendet oder weiterleitet.
-
Ein
von dem öffentlichen
Netz 99-2 empfangenes Paket wird über die Leitungsschnittstelle 2-2 und über den
Bus 9 an eine Paketsendeeinheit 4 in der Paketverarbeitungseinheit 3-1 gesendet.
Die Paketsendeeinheit 4 speichert das empfangene Paket vorübergehend
in einem Paketpuffer 5 und meldet einen Kopf, in den für die Leitweglenkung
notwendige Informationen wie etwa eine Übertragungsziel-IP-Adresse des IP-Pakets
wie in 4 gezeigt usw. geschrieben worden sind, an eine
Leitwegwiedergewinnungseinheit 6.
-
Die
Leitwegwiedergewinnungseinheit 6 liest anhand der Übertragungszieladresse
in dem Kopf ein in einem Leitweglenkungsinformations-Speicher 7 gespeichertes
Leitweglenkungsziel aus. Die Leitwegwiedergewinnungseinheit 6 meldet
die aus dem Ergebnis des Auslesens erhaltenen Informationen über das
Leitweglenkungsziel an die Paketsendeeinheit 4. Die Paketsendeeinheit 4 liest
das entsprechende Paket aus dem Paketpuffer 5 aus und leitet das
ausgelesene Paket an das von der Leitwegwiedergewinnungseinheit 6 gemeldete
Leitweglenkungsziel weiter.
-
Je
nach dem Ergebnis der Leitweglenkungsziel-Wiedergewinnung wird ein
Paket über
den Kreuzschienenschalter 8, über eine weitere Paketverarbeitungseinheit
und über
den Bus an seine entsprechende Leitungsschnittstelle übertragen.
Andernfalls wird das Paket über
den Bus 9 direkt an seine entsprechende Leitungsschnittstelle übertragen. Wenn
das Paket z. B. an das öffentliche
Netz 99-1 weitergeleitet wird, wird das Paket über den
Bus 9 an die Leitungsschnittstelle 2-1 übertragen
und durch eine Formungseinheit 1 geformt, um eine mit dem öffentlichen
Netz 99-1 vertraglich vereinbarte Bandbreite aufrechtzuerhalten
oder einzuhalten, worauf die Sendung über eine Bitübertragungsschicht-Verarbeitungseinheit 111 an
das öffentliche
Netz 99-1 folgt. Wenn das Paket an ein privates Netz gesendet wird,
ist die Notwendigkeit für
die Formung allgemein gering.
-
1 zeigt
einen Blockschaltplan der in der Leitungsschnittstelle 2-1 vorgesehenen
Formungseinheit 1.
-
Anhand
von 1 umfasst die Formungseinheit 1 einen
Paketpuffer 10 für
die vorübergehende
Warteschlangeneinreihung jedes Pakets, eine Warteschlangenentscheidungsschaltung 11 zum Entscheiden
der Priorität
jedes der empfangenen Pakete und zum Bestimmen einer Warteschlange
für die
Warteschlangeneinreihung des empfangenen Pakets, einen Speicher 12 für geplante
Sendezeiten zum Speichern geplanter Sendezeiten von einer geplanten
Sendezeit, die unter Verwendung einer binären Baustruktur für jede Warteschlange
auf eine geplante Sendezeit für
eine Warteschlange gesetzt wird, damit sie für jeden Anwender mit der höchsten Priorität gesendet wird,
und geplanter Sendezeiten von einer geplanten Sendezeit, die unter
Verwendung einer binären
Baustruktur für
jeden Anwender auf eine geplante Sendezeit für einen Anwender gesetzt wird,
damit sie mit der höchsten
Priorität
gesendet wird, eine Sortierschaltung 17 zum Wählen der
zu sendenden Warteschlange mit der höchsten Priorität unter
Verwendung der in dem Speicher 12 für geplante Sendezeiten gespeicherten
geplanten Sendezeiten in der binären
Baumstruktur und um das Ergebnis davon wieder in den Speicher 12 für geplante
Sendezeiten zurückzuschreiben,
einen Rechner 13 für
geplante Sendezeiten zum Berechnen einer geplanten Sendezeit für das entsprechende
Ausgangsziel bei der Paketsendung und beim Paketempfang und zum Zuteilen
des Speichers 12 für
geplante Sendezeiten zum Halten oder Speichern der geplanten Sendezeit, die
durch das Ergebnis der obigen Berechnung erhalten wurde, eine Paketausleseschaltung 14 zum
Auslesen von Paketen von dem Paketpuffer 10, um sie in Übereinstimmung
mit der geplanten Sendezeit für jede
in dem Speicher 12 für
geplante Sendezeiten gespeicherte Warteschlange zu senden, eine
Prioritätsinformations-Ergänzungsschaltung 15,
um jedem zu sendenden Paket Prioritätsinformationen (hohe Priorität oder niedrige
Priorität)
zuzuteilen, und einen Zeigeber 16 zum Angeben der gegenwärtigen Zeit.
-
Der
Paketpuffer 10 umfasst Prioritätswarteschlangen 100,
die für
jeden Anwender vorhanden sind, z. B. eine Prioritätswarteschlange 100-1 für einen
Anwender 1 und eine Prioritätswarteschlange 100-2 für einen
Anwender 2, wie sie in 1 gezeigt sind,
um Prioritätspakete,
die in einer garantierten Bandbreite zu senden sind, in eine Warteschlange einzureihen,
und Nichtprioritätswarteschlangen 101, um
Nichtprioritätspakete,
die zu senden sind, wenn ein Netz nicht belegt ist oder eine Bandbreite
außerhalb
der garantierten Band breite verfügbar
ist, in eine Warteschlange einzureihen. Diese Warteschlangen sind
gemäß ähnlichen
Regeln wie für
die Prioritätswarteschlangen
in 1 mit den Bezugszeichen 101-1 und 101-2 bezeichnet.
-
Der
Rechner 13 für
geplante Sendezeiten umfasst einen Rechner 130 für Sofort-Auslesezeiten zum
Berechnen einer geplanten Sendezeit 1300, die dazu verwendet
wird, das entsprechende Paket vom Zeitpunkt des Paketempfangs oder
der Paketsendung sofort zu senden, einen Rechner 131 für Auslesezeiten
garantierter Bandbreite zum Berechnen einer geplanten Sendezeit 1310,
die dazu verwendet wird, ein solches Sendeintervall aufrechtzuerhalten, dass
die garantierte Bandbreite nicht überschritten wird, eine Wähleinrichtung 132 zum
Auswählen
des Schreibens einer der zwei geplanten Sendezeiten 1300 und 1310 in
den Speicher 12 für
geplante Sendezeiten oder zum Nichtschreiben beider in den Speicher 12 für geplante
Sendezeit, und einen Rechner 133 für Auslesezeiten maximaler Bandbreite
zum Berechnen einer geplanten Sendezeit, die dazu verwendet wird,
ein solches Sendeintervall aufrechtzuerhalten, dass die maximale
vertraglich vereinbarte Bandbreite nicht überschritten wird.
-
Genauer
beschrieben berechnet der Rechner 130 für Sofort-Auslesezeiten die
geplante Sendezeit 1300 unter Verwendung der von dem Zeitgeber 16 gemeldeten
gegenwärtigen
Zeit 1600 wie folgt:
geplante Sendezeit 1300 =
gegenwärtige
Zeit + 1
-
Das
heißt,
wenn keine Pakete von anderen Warteschlangen zu senden sind, wird
das entsprechende Paket sofort gesendet. Ferner berechnen der Rechner 131 für Auslesezeiten
garantierter Bandbreite und der Rechner 133 für Auslesezeiten
maximaler Bandbreite die ge plante Sendezeit 1310 gemäß einem
solchen Algorithmus, dass Pakete selbst dann im Durchschnitt mit
einer vertraglich vereinbarten Bandbreite gesendet werden können, wenn
geplante Sendezeiten für
mehrere VC miteinander konkurrieren, was Schwankungen verursacht.
Falls z. B. der in "The
ATM Forum TM4.0" beschriebene
Leaky-Bucket-Algorithmus
oder dergleichen verwendet wird, werden die oben erwähnten Schwankungen
absorbiert und können
Pakete im Durchschnitt mit der vertraglich vereinbarten Bandbreite
gesendet werden.
-
In 6 bzw. 7 sind
ein Speicherformat des Speichers 12 für geplante Sendezeiten und
ein ausführlicher
Blockschaltplan davon gezeigt.
-
Wie
in 6 gezeigt ist, sind in dem Speicher 12 für geplante
Sendezeiten für
jede Warteschlange eine geplante Sendezeit 30, ein Zeitgültigkeitsmerker 31,
der angibt, dass die geplante Sendezeit 30 gültig ist,
und ein Paketgültigkeitsmerker 32, der
angibt, dass in der Warteschlange ein auf das Senden wartendes Paket
gespeichert ist, gespeichert.
-
Wie
in 7 gezeigt ist, umfasst der Speicher 12 für geplante
Sendezeiten ferner einen Arbeitsspeicher 122 zum Speichern
von Informationen über
die geplante Sendezeit, eine Arbeitspeichersteuereinheit (einen
Speicher für
geplante Sendezeiten) 120 zum Erzeugen eines Steuersignals
für den Arbeitspeicher 122 und
zum Senden der aus dem Arbeitspeicher 122 ausgelesenen
Daten an jeden Schaltungsblock und eine Zeitgültigkeitsmerker-Erneuerungsschaltung 121 zum
Bestimmen, ob die in dem Arbeitspeicher 122 gespeicherte
geplante Sendezeit 30 ein effektiver Wert ist oder nicht
und zum Aktualisieren des Zeitgültigkeitsmerkers 31.
-
Es
wird nun die Bedeutung des Zeitgültigkeitsmerkers
beschrieben. Der Zeitgeber 16 zum Bestimmen einer Formungszeit
ist normalerweise als ein Zähler
mit einer endlichen Anzahl von Bits konstruiert. In diesem Fall
gibt er aber für
jede Konstante oder für
jeden festen Zyklus, der gemäß der Anzahl der
Bits des Zählers
bestimmt wird, dieselbe Zeit an. Das heißt, selbst wenn in dem Arbeitsspeicher 122 eine
gegebene geplante Sendezeit gespeichert ist, kann nicht bestimmt
werden, ob die gegebene Zeit die richtige geplante Sendezeit oder
eine falsche Zeit (lange in der Vergangenheit) angibt, bei der der
Zähler über einen
Zyklus oder über
eine Periode heraufgezählt
worden ist. Der Zeitgültigkeitsmerker 31 wird dazu
verwendet, zwischen den zwei zu unterscheiden. Der Zeitgültigkeitsmerker 31 ist
ein Merker, der auf '1' gesetzt wird, wenn
die geplante Sendezeit 30 die richtige Zeit angibt, und
der auf '0' gesetzt wird, wenn
die geplante Sendezeit 30 die falsche Zeit angibt, zu der
der Zähler über einen
Zyklus heraufgezählt
worden ist.
-
Es
werden die Operationen der Formungseinheit 1 erläutert, die
ausgeführt
werden, wenn über den
Bus 9 ein Paket von der Paketsendeeinheit 4 empfangen
wird, um das Paket an die entsprechende Ausgangsleitung zu senden.
Die Sortierschaltung 17 führt die Sortierung übrigens ähnlich dem
im Stand der Technik 1 gezeigten Sortierverfahren aus.
-
(1) Paketempfangsoperation:
-
Die
Paketempfangsoperation gibt jetzt die Operation zu der Zeit an,
zu der die Formungseinheit 1 über den Bus 9 ein
Paket von der Paketsendeeinheit 4 empfängt.
-
Wenn
die Formungseinheit 1 ein Paket darin empfängt, bestimmt
die Warteschlangenentscheidungsschaltung 11 zunächst, ob
das empfangene Paket in seine entsprechende Prioritätswarteschlange 100 oder
Nichtprioritätswarteschlange 101 eingereiht
werden soll. Im Fall eines IP-Pakets wird die Bestimmung der Warteschlange
z. B. unter Verwendung von Informationen, die den Informationen
in den in 4 schraffiert gezeigten Feldern
entsprechen, wie etwa dem Diensttyp, der Paketlänge, dem Protokolltyp, der
SIP (Quell-IP-Adresse) der DIP (Ziel-IP-Adresse) usw. ausgeführt, die
in einem Kopf jedes empfangenen Pakets liegen.
-
Wenn
die Warteschlange für
die Warteschlangeneinreihung des empfangenen Pakets bestimmt worden
ist, wird das empfangene Paket in die Warteschlange in dem Paketpuffer 10 eingereiht. Gleichzeitig
mit der Warteschlangeneinreihung des empfangenen Pakets wird an
den Rechner 13 für
geplante Sendezeiten ein Signal 1100 gesendet, das die
Warteschlange angibt, in die das empfangene Paket eingereiht worden
ist. Der Rechner 13 für
geplante Sendezeiten liest aus dem Speicher 12 für geplante
Sendezeiten die geplante Sendezeit 30, den Zeitgültigkeitsmerker 31 und
den Paketgültigkeitsmerker 32 in
Bezug auf die Warteschlange aus, in die das empfangene Paket eingereiht
worden ist.
-
In 5 sind
Betriebsregeln für
die in dem Rechner 13 für
geplante Sendezeiten vorgesehene Wähleinrichtung 132 gezeigt
und in 9 ist ein Ablaufplan beim Empfang gezeigt.
-
Wenn
der Paketgültigkeitsmerker
= 1 ist (siehe Schritt 50 in 9), heißt das,
dass wenigstens ein Paket bereits in die Warteschlange eingereiht worden
ist und eine geplante Sendezeit für das erste auf das Senden
wartende Paket davon berechnet worden ist. Somit wird die geplante
Sendezeit nicht aktualisiert. Wenn der Paketgültigkeitsmerker = 0 ist und
wenn der Zeitgültigkeitsmerker
= 0 ist (siehe Schritt 51 in 9), soll
das empfangene Paket in eine unbesetzte Warteschlange eingereiht
werden und soll die geplante Sendezeit aktualisiert werden, da die
gespeicherte geplante Sendezeit ungültig wird, da bereits eine
ausreichende Zeit verstrichen ist. Wenn der Paketgültigkeitsmerker
= 0 ist und der Zeitgültigkeitsmerker
= 1 ist, gibt die gespeicherte geplante Sendezeit eine gültige Zeit
an.
-
Wenn
die gespeicherte geplante Sendezeit im Vergleich zu der gegenwärtigen Zeit
in der Zukunft liegt (siehe Schritt 52 in 9),
wird die geplante Sendezeit nie aktualisiert, um zu verhindern,
dass ein Formungsintervall verschmälert wird. Wenn die gespeicherte
geplante Sendezeit dieselbe Zeit wie die gegenwärtige Zeit ist oder im Vergleich
zu der gegenwärtigen
Zeit in der Vergangenheit liegt, ist bereits ein Intervall, das
das Formungsintervall übersteigt,
gebildet worden. In diesem Fall kann die geplante Sendezeit aktualisiert
werden, da das Formungsintervall selbst dann aufrechterhalten werden
kann, wenn ein Paket bereits ausgelesen worden ist.
-
Alle
Erneuerungen der geplanten Sendezeiten beim Paketempfang sind für die Ausführung des sofortigen
Paketauslesens bestimmt.
-
Somit
wird die durch den Rechner 130 für Sofort-Auslesezeiten berechnete
geplante Sendezeit 1300, wenn die geplante Sendezeit aktualisiert
wird, in einem Gebiet oder Bereich 30 für geplante Sendezeiten in dem
Speicher 12 für
geplante Sendezeiten überschrieben
(siehe Schritt 53 in 9). Da die
entsprechende Warteschlange das Paket darin empfangen hat, wird
der Paketgültigkeitsmerker 32 immer auf
1 gesetzt. Die für
jeden Anwender gesetzte geplante Sendezeit wird gemäß ähnlichen
Regeln wie oben ebenfalls geändert.
-
Obgleich
die geplante Sendezeit für
diejenige Warteschlange, von der ein Paket mit der höchsten Priorität gesendet
werden soll, wie oben beschrieben ebenfalls in dem Speicher 12 für geplante Sendezeiten
gespeichert ist, besteht eine Möglichkeit,
dass die Warteschlange mit der höchsten
Priorität
geändert
worden ist, da die geplante Sendezeit 30 und der Paketgültigkeitsmerker 32 gemäß dem Paketempfang
aktualisiert worden sind. Somit führt die Sortierschaltung 17 auf
der Grundlage der aktualisierten Informationen eine Sortierung aus,
um eine Warteschlange mit der höchsten
Priorität
auszuwählen.
-
(2) Paketsendeoperation:
-
Die
Paketsendeoperation gibt nun die Operation des Sendens eines Pakets
von der Formungseinheit 1 an ihre entsprechende Ausgangsleitung
an. Die Paketsendung wird asynchron zu dem Paketempfang ausgeführt.
-
Die
Paketausleseschaltung 14 in 1 liest für jeden
Anwender, für
den die Paketsendung mit der höchsten
Priorität
ausgeführt
werden soll, die geplante Sendezeit 30, den Zeitgültigkeitsmerker 31 und
den Paketgültigkeitsmerker 32 aus,
die alle in dem Speicher 12 für geplante Sendezeiten gespeichert
worden sind. Es wird beurteilt, dass ein Anwender nur dann Pakete
senden kann, wenn der Paketgültigkeitsmerker
(32) = 1 ist, wenn der Zeitgültigkeitsmerker (31)
= 1 ist und wenn die geplante Sendezeit (30) ≤ gegenwärtige Zeit
ist, d. h., wenn die geplante Sendezeit in der Vergangenheit oder
in der Gegenwart liegt. Da selbst das Paket für die mit der höchsten Priorität zu sendende
Warteschlange in einem nicht sendefähigen Zustand ist, ist es anderenfalls
nicht möglich,
Pakete von allen Warteschlangen zu senden.
-
Bei
der Sendung eines mit der höchsten
Priorität
zu sendenden Anwenderpakets liest die Paketausleseschaltung 14 nachfolgend
eine geplante Sendezeit 30, einen Zeitgültigkeitsmerker 31 und
einen Paketgültigkeitsmerker 32 für ein mit
der höchsten Priorität für den entsprechenden
Anwender zu sendendes Anwenderpaket aus. Das Paket wird nur dann
ausgelesen, wenn der Paketgültigkeitsmerker 32 =
1 ist, wenn der Zeitgültigkeitsmerker 31 =
1 ist und wenn die geplante Sendezeit 30 ≤ gegenwärtige Zeit
ist. Anderenfalls wird kein Paket von irgendeiner Warteschlange
gesendet. Wenn eine Prioritätswarteschlange
und eine Nichtprioritätswarteschlange
für denselben
Anwender beide in einem lesbaren Zustand sind, wird durch die ideale
Prioritätssteuerung zwangsläufig ein
Paket für
die Prioritätswarteschlange
gesendet.
-
Ein
durch die Paketausleseschaltung 14 aus dem Paketpuffer 10 gelesenes
Paket wird an die Prioritätsinformations-Ergänzungsschaltung 15 übertragen,
wo die Prioritätsinformationen
zu dem Paket ergänzt
werden. Die Prioritätsinformationen
repräsentieren
im Fall eines IP-Pakets ein Diensttypfeld (den Diensttyp in 4)
und im Fall einer ATM-Zelle ein CLP-Bit. Die Prioritätsinformations-Ergänzungsschaltung 15 teilt
einem von der Prioritätswarteschlange 100 ausgelesenen
Paket eine hohe Priorität
zu und teilt einem von der Nichtprioritätswarteschlange 101 ausgelesenen
Paket eine niedrige Priorität
zu und sendet das Paket an seine entsprechende Ausgangsleitung.
-
Wenn
das Paket gesendet wird, wird die geplante Sendezeit 30 für das nächste in
dieselbe Warteschlange eingereihte Paket aktualisiert. Bei der Paketsendung
wird an den Rechner 13 für geplante Sendezeiten ein
Signal 1400 gesendet, das den Typ der Warteschlange der
gesendeten Zelle angibt.
-
5 zeigt
die Betriebsregeln für
die in dem Rechner 13 für
geplante Sendezeiten vorgesehene Wähleinrichtung 132 und 10 zeigt
einen Ablaufplan beim Senden.
-
Wenn
das gesendete Paket einem aus einer Prioritätswarteschlange ausgelesenen
Paket entspricht, wählt
die Wähleinrichtung 132 das
Ergebnis der Berechnung 1310 durch den Rechner 131 für Auslesezeiten
garantierter Bandbreite aus, um eine garantierte Bandbreite aufrechtzuerhalten
(siehe Schritt 54-1 in 10). Da
ein sofortiges Auslesen ausgeführt
werden kann, wenn ein von einer Nichtprioritätswarteschlange ausgelesenes
Paket gesendet wird, wählt
die Wähleinrichtung 132 das
Ergebnis der Berechnung 1300 durch den Rechner 130 für Sofort-Auslesezeiten
aus (siehe Schritt 54-2 in 10). Die
gewählte
geplante Sendezeit wird in ihrem entsprechenden geplanten Bereich 30 für geplante
Sendezeiten des Speichers 12 für geplante Sendezeiten überschrieben.
Gleichzeitig wird in ihrem entsprechenden Bereich für geplante
Sendezeiten ebenfalls eine von An wender zu Anwender geplante Sendezeit aktualisiert
und überschrieben.
-
Wenn
eine Warteschlange wegen der Sendung des Pakets leer wird (Warteschlangenlänge = 0),
wird in dem Speicher 12 für geplante Sendezeiten der
Paketgültigkeitsmerker
= 0 gespeichert. Wenn die Warteschlange nicht geleert wird (die
Warteschlangenlänge > 0 ist), selbst wenn
das Paket gesendet wird, wird der Paketgültigkeitsmerker 32 (=
1) in dem Speicher 12 für
geplante Sendezeiten nicht aktualisiert und wird der Zeitgültigkeitsmerker
in einem Zustand "1" aufrechterhalten.
-
(3) Zeitgültigkeitsmerker-Aktualisierungsoperation:
-
In
der vorliegenden Erfindung wird ein Zeitgeber verwendet, der eine
wie in 8 gezeigte Struktur besitzt.
-
Ein
gegebener Zeitwert in einem Zeitgeber 89 mit einer endlichen
Anzahl von Bits gibt die gegenwärtige
Zeit 80 an. Dieser Wert wird mit einer vorgegebenen Geschwindigkeit
heraufgezählt
und nimmt in Uhrzeigerrichtung zu. Die Heraufzählgeschwindigkeit hängt von
einer Bandbreite einer Sendezielleitung ab. Ein Bereich, in dem
die gegenwärtige
Zeit 80 bereits verstrichen ist, entspricht einem Vergangenheitsbereich 81 und
ein Bereich, den die gegenwärtige
Zeit 80 noch nicht ereicht hat, entspricht einem Zukunftsbereich 82.
An einem Berührungsbereich des
Vergangenheitsbereichs 81 und des Zukunftsbereichs 82 ist
ein unsicherer Bereich 83 vorgesehen, der nicht der gegenwärtigen Zeit 80 entspricht.
Der unsichere Bereich 83 ist ein Bereich, der weder der Vergangenheits-
noch der Zukunftsbereich ist und wird von der gegenwärtigen Zeit
aus gezählt
immer in einem vorgegebenen Abstand (Zeitabstand) gehalten.
-
Falls
der unsichere Bereich 83 nicht vorgesehen ist, entsteht
eine Unzweckmäßigkeit
der Art, dass eine geplante Sendezeit, die zu einer bestimmten Zeit
in der Vergangenheit gehalten wird, allein durch einen Zeitzuwachs
zu einer zukünftigen
Zeit führen
würde,
sodass keine richtige Formung ausgeführt werden kann. Die in dem
Arbeitsspeicher 122 gespeicherte geplante Sendezeit 30 führt zu einer Zeit
in dem Vergangenheitsbereich 81, ohne aktualisiert zu werden.
In der vorliegenden Erfindung wird der Zeitgültigkeitsmerker auf '0' gebracht, wenn die Zeit weiter zunimmt
und die geplante Sendezeit 30 dadurch eine Zeit in dem
unsicheren Bereich 83 erreicht.
-
Anhand
eines in 11 gezeigten Ablaufplans wird
der Betrieb der in dem Speicher 12 für geplante Sendezeiten vorgesehenen
Zeitgültigkeitsmerker-Erneuerungsschaltung 121 erläutert.
-
Die
Zeitgültigkeitsmerker-Erneuerungsschaltung 121 liest
zunächst
eine geplante Sendezeit 30, einen Zeitgültigkeitsmerker 31 und
einen Paketgültigkeitsmerker 32 aus,
die für
jede Warteschlange von dem Arbeitsspeicher 122 gesetzt
worden sind (siehe Schritt 55 in 11).
-
Wenn
der ausgelesene Zeitgültigkeitsmerker (31)
= 0 ist, werden alle Informationen nicht aktualisiert, da bereits
beurteilt worden ist, dass die geplante Sendezeit 30 ungültig ist
(siehe Schritt 56 in 11). Wenn
der Zeitgültigkeitsmerker
(31) = 1 ist und die geplante Sendezeit 30 in
dem unsicheren Bereich 93 nicht vorhanden ist, werden alle
Informationen nicht aktualisiert, da die geplante Sendezeit 30 noch
gültig
ist (siehe Schritt 57 in 11).
-
Wenn
der Zeitgültigkeitsmerker
(31) = 1 ist, die geplante Sendezeit 30 in dem
unsicheren Bereich 93 liegt und der Paketgültigkeitsmerker
(32) = 1 ist, gibt es immer noch ein auf das Senden wartendes Paket,
sodass der Zeitgültigkeitsmerker
nie auf 0 gebracht wird. In diesem Fall wird die geplante Sendezeit
auf eine von der gegenwärtigen
Zeit in dem Vergangenheitsbereich am weitesten entfernte Zeit erhöht (siehe 94 in 9)
und in den Arbeitsspeicher 122 zurückgeschrieben. Der Zeitgültigkeitsmerker und
der Paketgültigkeitsmerker
bleiben beide auf 1 gehalten und werden ohne ihre Erneuerung in
den Arbeitsspeicher 122 zurückgeschrieben (siehe Schritte 58-1 und 59 in 11).
Wenn der Zeitgültigkeitsmerker
(31) = 1 ist, die geplante Sendezeit 30 in dem
unsicheren Bereich 93 liegt und der Paketgültigkeitsmerker
(32) = 0 ist, ist kein auf die Sendung wartendes Paket
vorhanden. Somit werden die geplante Sendezeit und der Paketgültigkeitsmerker
ohne ihre Aktualisierung in den Arbeitsspeicher 122 zurückgeschrieben
und wird der Zeitgültigkeitsmerker
auf 0 erhöht
und in den Arbeitsspeicher 122 zurückgeschrieben (siehe Schritte 58-2 und 59 in 11).
-
Nachfolgend
wird eine Beschreibung hinsichtlich der Zeitgebung der Zeitaktualisierung
gegeben.
-
Falls
eine bestimmte Warteschlange in dem unsicheren Bereich 93 ohne
Aktualisierung gelassen wird, tritt die geplante Sendezeit in den
Zukunftsbereich mit dem Zeitgültigkeitsmerker
= 1 ein. In diesem Fall kann auf ähnliche Weise wie bei der Nichtbereitstellung
des unsicheren Bereichs 83 keine richtige Formung ausgeführt werden.
Somit ist es notwendig, an allen Warteschlangen in dem unsicheren
Bereich die oben beschriebene Zeitgültigkeitsmerker-Aktualisierungs operation
einmal oder mehrmals auszuführen.
Dies kann leicht dadurch realisiert werden, dass die geplante Sendezeit
in einem Zyklus aktualisiert wird, der kleiner oder gleich einer
Zeitbreite des unsicheren Bereichs ist.
-
Obgleich 1 das
Beispiel gezeigt hat, in dem sowohl die Prioritätswarteschlange 100 als
auch die Nichtprioritätswarteschlange 101 für jeden
Anwender eine nach der anderen vorhanden ist, können für jeden Anwender mehrere Prioritätswarteschlangen
und mehrere Nichtprioritätswarteschlangen
vorgesehen sein. Falls die Anzahl der Warteschlangen zunimmt, kann
eine feinere Prioritätssteuerung
der Art ausgeführt
werden, dass selbst im Fall des gleichen E-Mail-Verkehrs z. B. eine
E-Mail für
einen Anwender A gegenüber
einer E-Mail für
einen Anwender B bevorzugt übertragen
wird.
-
Wenn
für jeden
Anwender mehrere Prioritätswarteschlangen
vorbereitet werden, müssen
die Parameter für
einen Leaky-Bucket-Algorithmus in der Weise gesetzt werden, dass
eine garantierte Bandbreite zur Summe der Sendebandbreiten der mehreren
Prioritätswarteschlangen
führt.
Ferner können dann,
wenn mehrere Nichtprioritätswarteschlangen vorbereitet
werden, als Steuerverfahren zum Steuern der Priorität zwischen
den Nichtprioritätswarteschlangen
z. B. eine ideale Prioritätssteuerung,
in der alle Pakete in einer Warteschlange hoher Ebene gegenüber den
anderen immer bevorzugt sind, oder eine gewichtete Round-Robin-Steuerung,
in der die Pakete für
eine Warteschlange hoher Ebene und für eine Warteschlange niedriger
Ebene in einem vorgegebenen Verhältnis
(z. B. 2:1) gesendet werden, angewendet werden.
-
Gemäß der oben
beschriebenen Ausführungsform
der Formungseinheit wird die Formung an den Prioritätspaketen
in der minimalen garantierten Bandbreite ausgeführt. Somit besteht dann, wenn
die Eingangsbandbreite größer als
die minimale garantierte Bandbreite ist, eine Möglichkeit, dass einige der Warteschlangen
einen Überlaufstatus
erhalten und übergelaufene
Pakete verworfen werden könnten. Um
diesen Status zu verhindern, kann die Funktion hinzugefügt werden,
Pakete maximal zu senden, ohne die minimale garantierte Bandbreite
aufrechtzuerhalten, wenn die Warteschlange wahrscheinlich überläuft.
-
Das
Ergebnis der Berechnung durch den Rechner 131 für Auslesezeiten
garantierter Bandbreite wird in der in 1 gezeigten
Formungseinheit als eine geplante Sendezeit für das nächste Paket angewendet, wenn
das Prioritätspaket
gesendet wird. In diesem Fall kann die obige Funktion leicht durch
Bezugnahme auf eine Warteschlangenlänge einer Prioritätswarteschlange
und Ändern
einer Auswahlbedingung gemäß der Warteschlangenlänge realisiert
werden. Das heißt,
die Bedingung der Wähleinrichtung 132 kann
einfach in der Weise geändert werden,
dass dann, wenn die Warteschlangenlänge der Prioritätswarteschlange
größer als
eine voreingestellte Schwelle ist, das Ergebnis der Berechnung durch
den Rechner 131 für
Auslesezeiten garantierter Bandbreite als eine geplante Sendezeit
für das nächste Paket
angewendet wird, und dann, wenn die Warteschlangenlänge der
Prioritätswarteschlange größer als
die Schwelle ist, das Ergebnis der Berechnung durch den Rechner 130 für Sofort-Auslesezeiten als
eine geplante Sendezeit für
das nächste
Paket angewendet wird. Prioritätspakete,
die einer Bandbreite entsprechen, die die garantierte Bandbreite übersteigt,
werden durch die UPC auf der Netzseite nicht verworfen, falls sie
mit niedriger Priorität
gesendet werden.
-
Falls
die Eingangsbandbreite für
die Prioritätspakete
klein ist, fällt
eine Sendebandbreite für
mit hoher Priorität
zu sendende Pakete unter die garantierte Bandbreite. In diesem Fall
kann die hauptsächlich
für die
Abrechnung bestimmte garantierte Bandbreite nicht effektiv genutzt
werden. Um die garantierte Bandbreite effektiv zu nutzen, kann die
Paketausleseschaltung 14 Pakete aus einer Nichtprioritätswarteschlange
auslesen, wobei die Prioritätsinformations-Ergänzungsschaltung 15 diesen
Nichtprioritätspaketen
selbst dann hohe Priorität
zuteilt, wenn in einer Prioritätswarteschlange
kein auf das Senden wartendes Paket vorhanden ist, wenn die geplante Sendezeit
für die
Prioritätswarteschlange
erreicht ist.
-
12 zeigt
die Art, in der Pakete von der mit der oben beschriebenen Formungseinheit 1 versehenen
Paketweiterleitungsvorrichtung 98 an das öffentliche
Netz 99-1 gesendet werden.
-
Eine
obere Hälfte
von 12 gibt Zeitintervalle gesendeter Pakete an, wobei
die horizontale Achse als eine Zeitachse gesetzt ist. Eine untere Hälfte von 12 gibt Änderungen
der Sendebandbreite bei allen einzelnen Zeiten an.
-
Ein
Anwender sendet Pakete mit einer Bandbreite zwischen der minimalen
garantierten Bandbreite und der maximalen vertraglich vereinbarten Bandbreite
(Bereich 1). Wenn die Anzahl der Anwender, die Pakete gleichzeitig
senden, zunimmt, wird die Sendebandbreite für jeden Anwender verringert, fällt aber
nicht unter die minimal garantierte Bandbreite (Bereich 2). Ferner
nimmt die Sendebandbreite für jeden
Anwender bis zu der maximalen vertraglich vereinbarten Bandbreite
zu (Bereich 3), wenn die Anzahl der Anwender abnimmt. In jedem Fall
werden Pakete hoher Priorität
gesendet, was eine konstante oder feste Bandbreite sicherstellt,
ohne von der Anzahl der Anwender abzuhängen. Pakete niedriger Priorität werden
bei unbesetzter oder verfügbarer Bandbreite
nur dann gesendet, wenn es eine Zuteilung für eine Bandbreite eines Kommunikationswegs oder
-kanals gibt.
-
Als
eine zweite Ausführungsform
wird eine Formungseinheit für
GFR beschrieben, die eine ATM-Zelle nutzt. 13 zeigt
einen Blockschaltplan der Formungseinheit für GFR.
-
Die
ATM-Zelle ist ein Paket mit einer festen Länge von 53 Bytes. Ein Paket
für eine
obere Schicht umfasst eine Gruppe von einer oder von mehreren Zellen.
Wenn verschiedene Pakete in derselben VC miteinander gemischt werden,
ist es für
die Seite des empfangenden Endgeräts nicht möglich, die Begrenzung zwischen
den Paketen zu identifizieren. Somit ist eine Zellenausleseschaltung 74 mit
der Funktion zum ununterbrochenen Auslesen von Zellen, die zu demselben
Paket der oberen Schicht gehören,
und zum Senden desselben vorgesehen. Ferner bestimmt eine Warteschlangenentscheidungsschaltung 71 durch
Bezugnahme auf VPI, VCI und CLP in einem Kopf jeder empfangenen
ATM-Zelle eine Warteschlange für
die Warteschlangeneinreihung jeder empfangenen ATM-Zelle.
-
Die
letzte Zelle des Pakets der oberen Schicht kann durch einen Nutzinformationstyp
(3 Bits) in einem Zellenkopf identifiziert werden. Wenn der Typ
der Nutzinformationen als "000" oder "010" gegeben ist, gibt
er die vorderste oder erste Zelle oder eine Zwischenzelle an. Wenn
der Nutzinformationstyp als "001" oder "011" gegeben ist, gibt er
die letzte Zelle an. Die anderen Werte geben an, dass die Zelle
eine Managementzelle wie etwa eine OAM-Zelle oder eine RM-Zelle
ist.
-
Der
Betrieb für
das Empfangen der ATM Zelle unterscheidet sich in den folgenden
Punkten von dem für
das Empfangen eines IP-Pakets.
-
Wenn
ein Paket für
eine obere ATM-Schicht empfangen wird, teilt eine SAR (Segmentierung
und Wiederzusammensetzen) 78 zunächst das Paket in Datenblöcke, die
jeweils 48 Bytes aufweisen, zu denen 5-Byte-ATM-Köpfe hinzugefügt werden,
um ATM-Zellen zu bilden. Diese ATM-Zellen werden an die Warteschlangenentscheidungsschaltung 71 übertragen.
Wenn die vorderste Zelle oder die Zwischenzelle des Pakets der oberen
Schicht empfangen wird, aktualisiert die Warteschlangenentscheidungsschaltung 71 eine
geplante Sendezeit, einen Zeitgültigkeitsmerker
und einen Paketgültigkeitsmerker
nicht. Die Warteschlangenentscheidungsschaltung 71 führt nur
dann eine Aktualisierung der geplanten Sendezeit, des Zeitgültigkeitsmerkers
und des Paketgültigkeitsmerkers
aus, wenn die letzte Zelle des Pakets der oberen Schicht empfangen
wird. Die Verarbeitung beim Empfang der letzten Zelle ist gleich
den Regeln für
das IP-Paket (siehe 14).
-
Nachfolgend
wird ein unterschiedlicher Punkt zwischen der Sendung bei der Zelle
und der Sendung beim IP-Paket erläutert.
-
Da
eine Bandbreitengarantie an einem Paket der oberen Schicht ausgeführt werden
muss, ist es notwendig, ununterbrochen Zellen auszulesen, wenn wie
oben beschrieben die vorderste Zelle oder eine Zwischenzelle des
Pakets der obersten Schicht gesendet wird. Dementsprechend liefert
die Zellenausleseschaltung 74 in diesem Fall un abhängig davon, ob
die Warteschlange, die eine Zelle gesendet hat, zu einer Prioritätswarteschlange
oder zu einer Nichtprioritätswarteschlange
gehört,
in der Weise Anweisungen 7400, dass eine Wähleinrichtung 732 in
einem Rechner 73 für
geplante Sendezeiten das Ergebnis der Berechnung 7300 durch
einen Rechner 730 für Sofortauslesezeiten
als eine geplante Sendezeit auswählt.
Wenn andererseits die letzte Zelle des Pakets der oberen Schicht
gesendet wird, wird eine geplante Sendezeit gemäß den gleichen Regeln wie bei
der IP-Paketsendung (siehe 14) ausgewählt.
-
Gemäß der IP-Paketformungseinheit 1 der vorliegenden
Erfindung kann eine Formungseinheit für GFR wie oben beschrieben
leicht dadurch konstruiert werden, dass zu der Bedingung für die Wähleinrichtung
in dem Rechner für
geplante Sendezeiten einfach die Bedingung, die auf der letzten
Zelle und auf der ersten Zelle oder auf der Zwischenzelle beruht,
hinzugefügt
wird.
-
Wie
oben beschrieben wurde, wird gemäß der vorliegenden
Erfindung eine Formungseinheit geschaffen, in der wichtige Pakete
als Pakete hoher Priorität
mit einer garantierten Bandbreite gesendet werden können, und
in der dann, wenn zwischen den wichtigen Paketen eine unbesetzte
oder verfügbare Zeit
vorhanden ist, unwichtige Pakete dicht als Pakete niedriger Priorität gesendet
werden können.
Somit können
gemäß der vorliegenden
Erfindung Pakete mit der maximalen Bandbreite übertragen werden, wenn ein
Netz nicht belegt ist. Selbst dann, wenn das Netz belegt ist, können die
wichtigen Pakete mit der garantierten Bandbreite übertragen
werden, um dadurch die Bandbreite für einen Kommunikationsweg oder
-kanal effektiv zu verwenden. Ferner können unwichtige Pakete als
Pakete hoher Priorität
gesendet werden, wenn die Verkehrsmenge für die wichtigen Pakete klein
ist, sodass die garantierte Bandbreite maximal genutzt werden kann.
-
Gemäß der vorliegenden
Erfindung wird außerdem
eine Formungseinheit für
den GFR-Dienst geschaffen, die die UPC in Einheiten eines Pakets der
oberen Schicht in einem ATM-Netz ausführt, wodurch Pakete der oberen
Schicht mit der maximalen Bandbreite gesendet werden können, wenn
ein Netz nicht belegt ist, und Prioritätspakete der oberen Schicht
selbst dann mit einer garantierten Bandbreite gesendet werden können, wenn
das Netz belegt ist.