DE60117957T2

DE60117957T2 - Verfahren, System und Rechnerprogrammprodukt zur Bandbreitenzuteilung in einem System mit Mehrfachzugriff

Info

Publication number: DE60117957T2
Application number: DE60117957T
Authority: DE
Inventors: James T. Goode St. John
Original assignee: Telefonaktiebolaget LM Ericsson AB
Current assignee: Telefonaktiebolaget LM Ericsson AB
Priority date: 2001-01-12
Filing date: 2001-12-27
Publication date: 2006-08-31
Anticipated expiration: 2021-12-28
Also published as: DE60117957D1; ATE320686T1; EP1225734A2; EP1225734A3; US6917591B2; EP1225734B1; US20020136200A1

Description

ALLGEMEINER STAND DER TECHNIK
Die vorliegende Erfindung bezieht sich allgemein auf das Gebiet der Kommunikationen und insbesondere auf die Bandbreitenzuordnung für einen Vorwärtskanal.
Mit zunehmender Beliebtheit des Internets und anderer bidirektionaler Kommunikationsdienste sieht sich die vorhandene Kommunikationsinfrastruktur vor neue Aufgaben gestellt, um die Bereitstellung solcher Dienste unterstützen zu können. Angesichts der typischen Bandbreitenbegrenzungen des öffentlichen Fernsprechnetzes (PSTN), das allgemein für Kommunikationen wie Internet-Datenkommunikationen benutzt wird, gibt es Ansätze dafür, diese Dienste über das CATV-System (Kabelfernsehsystem) bereitzustellen. CATV stellt typisch eine koaxiale verdrahtete Verbindung von einer Kabelsystem-Serviceprovidereinrichtung zu Endbenutzern zur Verfügung. Während das CATV-System in erster Linie dazu benutzt wird, stromabwärtige Kommunikationen von der Kabelsystem-Serviceprovidereinrichtung zu Endbenutzern (wie Kabelfernsehsignale) bereitzustellen, kann es auch stromaufwärtige Kommunikationen von Endbenutzern zum CATV-Systemprovider unterstützen. Die stromabwärtige Seite des Kanals ist typisch ein Netzwerk mit One-to-Many-Distribution (Einer-zu-vielen-Verteilung), während der stromaufwärtige Kanal typisch ein Netzwerk mit Many-to One-Distribution (Vielen-zu-Einem) ist. Da die Bereitstellung dieser Dienste über das Breitband-Kabelnetzwerk immer beliebter wird, können die Bandbreiten-Begrenzungen selbst im stromabwärtigen Breitbandkanal des CATV-Systems Probleme mit sich bringen.
Des Weiteren, da das Internet für verschiedene Medientypen, wie Streaming Audio und Streaming Video, benutzt wird, hat man verschiedene Serviceebenen benutzt. Allgemein gesagt, können diese verschiedenen Servicetypen nach Servicequalitätskriterien, wie garantierter Bandbreite, Paketverlust oder dergleichen, eingestuft werden. Bei gemeinsamer Benutzung eines stromabwärtigen Kanals kann jedoch Servicequalität (QoS) in einem CATV-System schwierig sein, besonders dann, wenn das System überbenutzt ist.
Wie oben erwähnt, kann das Breitband-Kabelnetzwerk viele Serviceklassen, unterschiedliche Verkehrscharakteristiken und Servicequalität-Anforderungen unterstützen. Servicequalität wird typisch durch Paketeinstufung, Stromzugriff, Bandbreitenzuordnung und Puffermanagement unterstützt. Bei Stromzugriff muss Benutzern, die Dienste auf einer bestimmten Servicequalitätsebene anfordern, typisch Zugriff zum System gewährt oder verweigert werden, abhängig davon, ob die Servicequalitätsebene unterstützt werden kann. Dies führt allgemein dazu, dass entweder die Anzahl der Teilnehmer am System auf die maximale Anzahl von Teilnehmern, die unterstützt werden können, begrenzt wird, oder dass ihnen während der Höchstbelastungszeiten Dienste verweigert werden. Bei vorhandenen Systemen werden typisch Pakete mit niedriger Priorität entfernt, wenn das System überbenutzt ist, was zur Folge hat, dass typisch die Servicequalität des Systems geopfert wird. Demgemäß müssen verbesserte Verfahren zur Zuordnung von Bandbreite geschaffen werden, um die Servicequalität des Systems zu wahren.
Die internationale Patentanmeldung WO 99/11003 offenbart einen Mechanismus zur Bereitstellung einer strategiebasierten Servicequalität, wobei mehrere Warteschlangen geführt werden. Ein Paketweiterleitungsgerät empfängt ein eingehendes Paket und identifiziert eine für das Paket zu verwendende Verkehrsgruppe. Dann wird das Übertragen des Pakets aufgrund der Servicequalität-Strategie für die identifizierte Verkehrsgruppe geplant, anstatt sich auf ein Ende-zu-Ende-Signalprotokoll zu verlassen.
Die europäische Patentanmeldung EP 0901301 offenbart einen Scheduler mit dynamischer Geschwindigkeitssteuerung innerhalb eines ATM-Schalters (asynchroner Übertragungsmodus). Um sicherzustellen, dass jedem ATM-Verkehrsstrom ein genügender Anteil an Schalter-Bandbreite zugewiesen wird, bestimmt der ATM-Schalter eine entsprechende Stromgeschwindigkeit, die zwei Komponenten – eine garantierte Mindestgeschwindigkeit und einen Antel an der überschüssigen Bandbreite – enthält. Dadurch kann der ATM-Schalter einen Service gemäß den verschiedenen Servicequalitätsanforderungen bereitstellen und Geschwindigkeiten einrichten, die stromabwärtige Engpässe berücksichtigen.
Shreedbar und Varghese offenbaren eine annähernd gerechte Warteschlangentechnik, genannt "Deficit Round-Robin" in ihrem Artikel "Efficient Fair Queuing Using Deficit Round-Robin" in IEEE/ACM Transactions on Networking, Band 4, Nr. 3, Seite 375–385, Juni 1996. Sie benutzen eine gerechte Zufallswarteschlangentechnik zur Zuordnung eines Stroms zu Warteschlangen. Diese Warteschlangen sind somit Dienste, die "Round-Robin" verwenden, wobei jeder Warteschlange ein Service-Quantum zugeordnet wird. Wenn eine Warteschlange nicht fähig ist, ein Paket in der letzten Runde zu senden, weil das Paket zu groß war, wird der Rest des vorherigen Quantums zum Quantum für die nächste Runde hinzugefügt.
ZUSAMMENFASSUNG DER ERFINDUNG
Ausführungsformen der vorliegenden Erfindung stellen Verfahren, Systeme und Computerprogrammprodukte zur Zuordnung von übermäßiger und mangelnder Bandbreite (Bandbreitenüberschuss und Bandbreitendefizit) zu einer Mehrzahl von Warteschlangen in einem Mehrfachzugriffssystem bereit. Jede der mehreren Warteschlangen ist mit einer Servicequalität verbunden und weist einen entsprechenden Quantenwert auf. Ein verfügbarer Quantenwert basiert auf einer Gesamtsumme fester Bandbreite an einem Vorwärtskanal und einer Gesamtsumme der Bandbreite am Vorwärtskanal. Die Quantenwerte jeder der mehreren Warteschlangen werden mit einem Aktualisierungsquantenwert aktualisiert, der den entsprechenden Quantenwerten der mehreren Warteschlangen entspricht. Die Aktualisierungsquantenwerte basieren auf dem verfügbaren Quantenwert, einem reservierten Gesamtquantenwert entsprechend den Paketen, die für eine Aktualisierungsperiode in die mehreren Warteschlangen eingereiht wurden, und auf der Servicequalität der betreffenden Warteschlange.
In bestimmten Ausführungsformen der vorliegenden Erfindung entsprechen die Quantenwerte der mit der betreffenden Warteschlange verbundenen Servicequalität. Ferner kann die Aktualisierungsperiode konstant oder variabel sein und kann durch Bestimmen des Unterschieds zwischen der aktuellen Zeit und der Zeit der letzten Aktualisierungsperiode bestimmt werden.
In bestimmten Ausführungsformen der vorliegenden Erfindung kann die Mehrzahl der Warteschlangen eine Mehrzahl von Paketen enthalten, die unter Einsatz eines modifizierten "Deficit Round Robin" Algorithmus (Unterringalgorithmus) verarbeitet werden.
Des Weiteren kann der verfügbare Quantenwert durch Berechnen der Gesamtsumme der festen Bandbreite am Vorwärtskanal und durch Berechnen der Gesamtsumme der Bandbreite am Vorwärtskanal bestimmt werden. In bestimmten Ausführungsformen wird der Unterschied zwischen der Gesamtsumme der festen Bandbreite am Vorwärtskanal und der Gesamtsumme der Bandbreite am Vorwärtskanal durch Bestimmen des verfügbaren Quantenwerts bestimmt.
Die Gesamtsumme der festen Bandbreite am Vorwärtskanal kann auch auf einer Bandbreitengesamtsumme basieren, die für den Sprachverkehr, den Datenverkehr und den Signalverkehr festgelegt wurde.
In weiteren Ausführungsformen der vorliegenden Erfindung werden die Quantenwerte durch Berechnen des reservierten Gesamtquantenwerts für die Aktualisierungsperiode aktualisiert, basierend auf einem reservierten Mindestquantenwert für jede der Mehrzahl von Warteschlangen und Aktualisierung der Quantenwerte jeder der mehreren Warteschlangen mit einem Aktualisierungsquantenwert. Der Aktualisierungsquantenwert für jede der mehreren Warteschlangen kann Null sein, wenn der verfügbare Quantenwert kleiner als oder gleich Null ist. Der Aktualisierungsquantenwert kann auch aus dem reservierten Mindestquantenwert für die Aktualisierungsperiode bestehen, erhöht um einen Überquantenwert für die Aktualisierungsperiode, wenn der verfügbare Quantenwert größer als der reservierte Gesamtquantenwert ist. Der Aktualisierungsquantenwert kann ferner der reservierte Mindestquantenwert für die Aktualisierungsperiode, reduziert um einen Unterquantenwert für die Aktualisierungsperiode, sein, wenn der reservierte Gesamtquantenwert größer als der verfügbare Quantenwert ist.
Der Überquantenwert und der Unterquantenwert können der mit der betreffenden Warteschlange verbundenen Servicequalität entsprechen. Zum Beispiel können der Überquantenwert und der Unterquantenwert proportional zur Servicequalität der jeweiligen Warteschlange sein.
Ausführungsformen der vorliegenden Erfindung können in einem Breitband-Mehrfachzugriffssystem bereitgestellt werden.
KURZBESCHREIBUNG DER ZEICHNUNGEN
1 zeigt ein schematisches Blockdiagramm eines Kabelsystems mit einem Bandbreiten-Zuordner gemäß erfindungsgemäßen Ausführungsformen.
2 zeigt ein Blockdiagramm eines Kabelmodem-Terminalservers (CMTS) einschließlich eines Bandbreiten-Zuordners gemäß erfindungsgemäßen Ausführungsformen.
3 zeigt ein Ablaufdiagramm, das einen Vorgang zur Bandbreitenzuordnung gemäß erfindungsgemäßen Ausführungsformen veranschaulicht.
4 zeigt ein Ablaufdiagramm, das einen Vorgang zur Verarbeitung von Paketen veranschaulicht, wobei ein DRR-Ansatz (Deficit Round Robin) gemäß erfindungsgemäßen Ausführungsformen zum Einsatz kommt.
5 zeigt ein Ablaufdiagramm, das einen Vorgang zur Bandbreitenzuordnung gemäß erfindungsgemäßen Ausführungsformen veranschaulicht.
6 zeigt ein Ablaufdiagramm, das einen Vorgang zur Zuordnung von Bandbreitenüberschuss gemäß erfindungsgemäßen Ausführungsformen veranschaulicht.
7 zeigt ein Ablaufdiagramm, das einen Vorgang zur Zuordnung von Bandbreitendefizit gemäß erfindungsgemäßen Ausführungsformen veranschaulicht.
AUSFÜHRLICHE BESCHREIBUNG
Im Folgenden wird die vorliegende Erfindung ausführlich mit Bezug auf die beiliegenden Zeichnungen beschrieben, in denen illustrative Ausführungsformen der Erfindung dargestellt sind. Die Erfindung kann jedoch auf viele verschiedene Weise verkörpert werden und sollte nicht als durch die hier erklärten Ausführungsformen begrenzt verstanden werden; vielmehr wurden diese Ausführungsformen zum Zwecke einer gründlichen und vollständigen Offenbarung bereitgestellt, um dem Fachmann den Geltungsbereich der Erfindung ausführlich zu erklären.
Wie der Fachmann ohne Weiteres erkennen wird, kann die vorliegende Erfindung als Verfahren, Datenverarbeitungssystem oder Computerprogrammprodukt verkörpert werden. Demgemäß kann die vorliegende Erfindung als reine Hardware-Ausführungsform, reine Software-Ausführungsform oder als Ausführungsform implementiert werden, die Software- und Hardware-Aspekte kombiniert, die in dieser Schrift allgemein als "Kreis" bezeichnet werden. Ferner kann die vorliegende Erfindung als Computerprogrammprodukt auf einem computerbenutzbaren Speichermedium realisiert werden, das computerbenutzbare Programmcodemittel aufweist. Jedes geeignete computerlesbare Medium kann verwendet werden, einschließlich Festplatten, CD-ROMs, optischen Speichergeräten, Übertragungsmedien wie solchen, die das Internet oder ein Intranet unterstützen, oder magnetischen Speichergeräten.
Computerprogrammcode zur Ausführung der erfindungsgemäßen Vorgänge kann in einer objektorientierten Programmiersprache wie Java^®, Smalltalk oder C++ geschrieben werden. Der Comuterprogrammcode zur Ausführung der Vorgänge kann jedoch auch in konventionellen verfahrenstechnischen Programmiersprachen, wie zum Beispiel der "C" Programmiersprache, geschrieben werden. Der Programmiercode kann ganz auf dem Computer des Benutzers, teilweise auf dem Computer des Benutzers, als unabhängiges Softwarepaket, teilweise auf dem Computer des Benutzers und teilweise auf einem entfernten Computer oder ganz auf einem entfernten Computer ausgeführt werden. Im letzteren Szenario kann der entfernte Computer über ein Lokalbereichsnetz (LAN) oder ein Weitbereichsnetz (WAN) an den Computer des Benutzers angeschlossen werden, oder der Anschluss kann durch einen externen Computer vorgenommen werden (zum Beispiel über das Internet mit einem Internet-Serviceprovider).
Im Folgenden wird die vorliegende Erfindung mit Bezug auf Ablaufdiagramm-Darstellungen und/oder Blockdiagramme von Verfahren, Vorrichtungen (Systemen) und Computerprogrammprodukten gemäß erfindungsgemäßen Ausführungsformen beschrieben. Es versteht sich, dass jeder Block der Ablaufdiagramm-Darstellungen und/oder Blockdiagramme und Kombinationen der Blöcke in den Ablaufdiagramm-Darstellungen und/oder Blockdiagrammen von Computerprogrammanweisungen implementiert werden können. Diese Computerprogrammanweisungen können an einem Prozessor eines Allzweckcomputers, eines Spezialzweckcomputers oder anderer programmierbarer Datenverarbeitungsvorrichtungen bereitgestellt werden, um eine Maschine zu erstellen, mit der die Anweisungen, die über den Prozessor des Computers oder eine andere programmierbare Datenverarbeitungsvorrichtung ausgeführt werden, Mittel zur Implementierung der Funktionen erstellen, die im Ablaufdiagramm und/oder in dem oder den Blockdiagrammblöcken angegeben sind.
Diese Computerprogrammanweisungen können auch in einem computerlesbaren Speicher gespeichert werden, der einen Computer oder eine andere programmierbare Datenverarbeitungsvorrichtung anweisen kann, auf eine bestimmte Weise zu funktionieren, so dass die im computerlesbaren Speicher gespeicherten Anweisungen einen Herstellungsgegenstand einschließlich Anweisungsmitteln erzeugen, die die in dem Ablaufdiagramm und/oder Blockdiagrammblock oder -blöcken angegebenen Funktionen implementieren.
Die Computerprogrammanweisungen können auch in einen Computer oder eine andere programmierbare Datenverarbeitungsvorrichtung geladen werden, um eine Reihe von Arbeitsschritten auf dem Computer oder einer anderen programmierbaren Datenverarbeitungsvorrichtung durchzuführen, mit denen ein computer-implementierter Prozess erzeugt wird, so dass die Anweisungen, die auf dem Computer oder einer anderen programmierbaren Datenverarbeitungsvorrichtung ausgeführt werden, Schritte zum Implementieren der in dem Ablaufdiagramm und/oder Blockdiagrammblock oder -blöcken angegebenen Funktionen bereitstellen.
Ausführungsformen der vorliegenden Erfindung sollen nun mit Bezug auf 1 beschrieben werden, welche ein Blockdiagramm eines beispielhaften Kabelsystems einschließlich eines Bandbreiten-Zuordners 120 gemäß erfindungsgemäßen Ausführungsformen darstellt. Das in 1 darstellte beispielhafte Kabelnetzwerk 130 umfasst eine Verkabelungsinfrastruktur, wie koaxiales Kabel oder Faseroptikkabel, das die entfernten Teilnehmerorte mit einem Kabelmodem-Terminierungssystem oder einem Kabelmodem-Terminalserver (CMTS) 110 verbindet. Der CMTS 110 kann Dienste, wie einen Fernsehservice, Fernsprechservice, Internet-Service und andere Benutzerdienste für Teilnehmer des Kabelsystems über ein Kabelmodem 140 durch Übertragung von Daten über das Kabelnetzwerk 130 bereitstellen. Zum Beispiel hätte ein Endbenutzer vom Benutzergerät 150 aus Zugang zum IP-Netzwerk 100 (Internet) über das Kabelmodem 140. Wie ein Fachmann erkennen wird, kann das Benutzergerät 150 eins von vielen Geräten sein einschließlich eines Telefons, eines Fernsehers oder eines Personalcomputers. Es versteht sich ferner, dass trotz der Tatsache, dass 1 nur ein Kabelmodem 140 darstellt, ein tatsächliches Kabelnetzwerk typisch viele Kabelmodems enthalten würde.
Der CMTS 110 managt die Dienste, die den jeweiligen Teilnehmern im Kabelsystem bereitgestellt werden. Zum Beispiel könnte ein erster Teilnehmer Fernseh-, Fernsprech- und Internetdienste empfangen, während ein zweiter Teilnehmer nur Internetdienste empfangen könnte. Darüber hinaus könnten verschiedene Teilnehmer eine andere Servicequalität empfangen. Zum Beispiel könnte ein erster Teilnehmer Internetdienste mit relativ kleiner Bandbreite empfangen, während ein zweiter Teilnehmer Internetdienste mit relativ großer Bandbreite empfangen könnte. Demgemäß sendet und empfängt der CMTS 110 Daten zu und von den Kabelmodems 140 mit Geschwindigkeiten entsprechend den jeweiligen Teilnehmern. Die Kabelmodems 140 unterstützen auch Fernseh- und Fernsprechdienste, gegebenenfalls gleichzeitig mit Datenkommunikationen, wie solchen, die zum Internet gehen.
Ein Fachmann wird erkennen, dass die Datenübertragungen zwischen dem CMTS 110 und den Kabelmodems 140 gemäß den in der Technik bekannten Standards durchgeführt werden. Zum Beispiel können Datenübertragungen zwischen dem CMTS 110 und den Kabelmodems 140 mit Hilfe einer zeitaufteilenden Mehrfachzugriffstechnik (TDMA) durchgeführt werden, wobei die Daten über ein Kabelnetzwerk 130 unter Einsatz von Kanälen gesendet und empfangen werden, die als ein oder mehrere vordefinierte Zeitfenster mit einer Frequenz identifiziert wurden. Der Aufwärtskanal kann eine Mehrzahl solcher Unterkanäle umfassen. Standards für die Übertragung von Daten in Kabelsystemen werden in der DOCSIS-Spezifikation (Date Over Cable System Interface) besprochen, die von Cable Television Laboratories Incorporated veröffentlicht wurde.
Wie in 1 dargestellt, umfasst der CMTS 110 in der dargestellten Ausführungsform einen Bandbreiten-Zuordner 120 gemäß erfindungsgemäßen Ausführungsformen. Der erfindungsgemäße Bandbreiten-Zuordner kann die übermäßige und mangelnde Bandbreite (Bandbreitenüberschuss und Bandbreitendefizit) am Vorwärtskanal auf die Warteschlangen verteilen, und zwar auf Basis der Servicequalität-Garantien für die betreffenden Warteschlangen. Demgemäß kann der erfindungsgemäße Bandbreiten-Zuordner 120 trotz Maximierung des Einsatzes verfügbarer Ressourcen die Servicequalität des Systems wahren.
Mit Bezug auf 2 soll nun ein Blockdiagramm des CMTS 110 einschließlich des Bandbreiten-Zuordners gemäß Ausführungsformen der vorliegenden Erfindung beschrieben werden. Am CTMS 110 ankommende Pakete können entsprechend ihrer einzelnen Servicequalitätsanforderungen eingestuft werden. Die Pakete können dann einer Warteschlange (210, 215, 220) zugeführt werden, die fähig ist, die angeforderte Servicequalitätsebene bereitzustellen. Obwohl die vorliegende Erfindung mit Bezug auf das in 2 dargestellte Drei-Wartenschlangen-System beschrieben wurde, ist dieses System lediglich ein Beispiel, und es können sehr viel mehr Warteschlangen vorgesehen werden. Nach Einreihen der Pakete in die Warteschlangen werden diese gemäß des hier beschriebenen Vorgangs für Bandbreiten-Zuordnung verarbeitet, wobei Pakete von den Warteschlangen 210, 215 und 220 zu der Ausgabewarteschlange 225 geschickt werden. Erfindungsgemäße Ausführungsformen stellen einen modifizierten DRR-Ansatz (Deficit Round Robin) bereit, mit dem Pakete von den Warteschlangen 210, 215 und 220 zu der Ausgabewarteschlange 225 geschickt werden.
Die vorliegende Erfindung wurde hier mit Bezug auf das Kabelsystem von 1 und dem CMTS 110 von 2 beschrieben. Ein Fachmann wird jedoch ohne Weiteres erkennen können, dass die vorliegende Erfindung auf jede beliebige Netzwerkkonfiguration angewendet werden kann. Ferner können die Funktionen der vorliegenden Erfindung mit einem Datenverarbeitungssystem implementiert werden, das unter Softwaresteuerung, als dedizierte Hardware oder als Kombination derselben läuft. Somit können die Warteschlangen als Partitionen im Verarbeitungssystemspeicher, als FIFO-Puffer-integrierte Kreise, als Orte auf einem Speichergerät wie einer Festplatte oder anderen Speichermedien oder auf anderen derartigen dem Fachmann bekannten Geräten implementiert werden.
Der Bandbreiten-Zuordner 120 in 1 und 2 kann Bandbreite auf die einzelnen Warteschlangen 210, 215 und 220 verteilen. Jeder Warteschlange wird typisch ein Quantenwert zugeordnet, der den Durchsatz dieser Warteschlange definiert. In anderen Worten, der Quantenwert jeder Warteschlange definiert typisch die Servicequalität, die die jeweilige Warteschlange garantieren kann. Der Quantenwert stellt typisch die Bandbreitenquantität dar, die einer Warteschlange zugeordnet wird und im Sinne eines Bitwerts definiert werden kann, zum Beispiel können die Quantenwerte für Warteschlangen 210, 215 und 220 auf 500, 750 bzw. 1000 Bits eingestellt werden. Für ein voll belastetes System ist die Summe der Quantenwerte (Bits) aller mit der Servicerate multiplizierten Warteschlangen typisch gleich der verfügbaren Bandbreite auf dem Vorwärtskanal 240. Wenn das System unterbelastet ist, kann der Bandbreiten-Zuordner den stromabwärtigen Bandbreitenüberschuss auf die Warteschlangen verteilen. Wenn das System überbelastet ist (zu viele Teilnehmer), kann der Bandbreiten-Zuordner das stromabwärtige Bandbreitendefizit auf die Warteschlangen verteilen. Es ist möglich, dass nicht jeder Warteschlange die gleiche Bandbreitenmenge zugeordnet wird, denn die Verteilung der Bandbreite wird typisch in einer Weise durchgeführt, die die relativen Servicequalitätsebenen für jede der Warteschlangen bewahrt.
Ausführungsformen der vorliegenden Erfindungen sollen nun mit Bezug auf 3 beschrieben werden, die ein Ablaufdiagramm der Arbeiten des Bandbreiten-Zuordners 120 gemäß erfindungsgemäßen Ausführungsformen veranschaulicht. Der verfügbare Quantenwert (verfügbare Bandbreite) des Vorwärtskanals wird bestimmt (Block 300). Das verfügbare Quantum kann mit Bezug auf die stromabwärtige Gesamtbandbreite und die feste Gesamtbandbreite berechnet werden. Feste Bandbreite ist diejenige Bandbreite, die bereit festgelegt wurde, zum Beispiel für den Sprachverkehr, den Datenverkehr und/oder den Signalverkehr. Zum Beispiel können die obigen Variablen wie folgt berechnet werden: Verfügbares Gesamtquantum = (1.0 – Overhead) × (Stromabwärtige Bandbreite) – (Feste Bandbreite),wobei

Feste Bandbreite: = Feste Sprachbandbreite + Feste Datenbandbreite + Feste Signalbandbreite
Feste Sprachbandbreite: = (für N aktive Serviceströme) = Stromabwärtige maximale Dauerrate (Sprachservicestrom 1) + Stromabwärtige maximale Dauerrate (Sprachservicestrom 2).. + Stromabwärtige maximale Dauerrate (Sprachservicestrom N)
Feste Datenbandbreite: = DC.0 + DC.1 + DC.2
Feste Signalbandbreite: = 1 × Feste Sprachbandbreite

Overhead ist typisch der Prozentsatz der stromabwärtigen Bandbreite, die dem Overhead Messaging zugeordnet wird. Die stromabwärtige maximale Dauerrate für Verkehr kann sich nach der Servicequalität der Warteschlange richten und bezieht sich auf die maximale stromabwärtige Bandbreite pro Servicestrom. Ein Servicestrom ist typisch der Pfad eines Pakets vom CMTS 110 im Vorwärtskanal zum Benutzergerät 150. Diese Serviceströme können nach Servicequalität eingestuft werden. Nach Berechnung des verfügbaren Quantenwerts kann der Quantenwert jeder Warteschlange mit einem Aktualisierungsquantenwert (Block 310) aktualisiert werden.
Nach Aktualisierung des Quantenwerts einer Warteschlange mit dem Aktualisierungsquantenwert können die Pakete in dieser Warteschlange verarbeitet werden, indem sie zuerst in die Ausgabewarteschlange gesetzt und dann auf dem Vorwärtskanal zu ihrem Zielort gesendet werden. Es können viele Ansätze zur Verarbeitung dieser Pakete verwendet werden.
Ausführungsformen der vorliegenden Erfindung können einen DRR-Ansatz zur Verarbeitung der Pakete in den Warteschlangen verwenden.
DRR (Deficit Round Robin) verarbeitet die Warteschlangen, die ein Round-Robin-Verarbeitungssystem verwenden. Da Round-Robin-Verarbeitung dem Fachmann gut bekannt ist. DRR (Deficit Round Robin) unterscheidet sich von traditionellem Round-Robin dadurch, dass eine in Verarbeitung befindliche Warteschlange eventuell nicht fähig ist, ein Paket zu verarbeiten, weil ihre Paketgröße größer als der Quantenwert für die Warteschlange ist. Ferner ist es vielleicht einer anderen Warteschlange möglich, mehrere Pakete zu senden, deren kumulative Bitzählung unter dem Quantenwert der Warteschlange liegt.
Ausführungsformen der vorliegenden Erfindung können eine modifizierte Version des bestehenden DRR-Ansatzes implementieren. Traditionelles DRR benutzt einen statischen Quantenwert für jede Priorität (Servicequalität). Folglich, wenn die Menge und Größe der in das System eingehenden Pakete entweder größer oder kleiner ist als von einem statischen Quantenwert bewältigt werden kann, wird entweder Bandbreite verschwendet, oder Bandbreite, die nicht auf dem Vorwärtskanal verfügbar ist, kann auf die Warteschlangen verteilt werden, und Servicequalität geht typisch verloren. Um diese Probleme mit dem bestehenden Verfahren der Paketverarbeitung zu bewältigen, können Ausführungsformen der vorliegenden Erfindung den Bandbreitenüberschuss oder das Bandbreitendefizit auf die Warteschlangen auf Basis ihrer jeweiligen Servicequalität verteilen und folglich variable Quantenwerte für die Warteschlangen im System bereitstellen.
Bezugnehmend auf 4 soll nun ein Ablaufdiagramm beschrieben werden, das einen Vorgang zur Verarbeitung von Paketen veranschaulicht, die einen modifizierten DRR-Ansatz gemäß erfindungsgemäßer Ausführungsformen verwenden. Jede Warteschlange hat typisch einen Defizitzähler (DC.0, DC.1, DC.2), der den Quantenwert der Warteschlange identifiziert. Jeder Warteschlange kann ein anderer Quantenwert entsprechend einer anderen Servicequalität zugeordnet werden. In anderen Worten – je größer allgemein der einer Warteschlange zugeordnete Quantenwert ist, umso größer ist die Servicequalitätgarantie für die jeweilige Warteschlange.
Der Defizitzähler jeder der Warteschlangen 210, 215 und 220 wird anfänglich auf Null gesetzt (Block 410). Dann wird die Servicequalität (QoS) auf Null gesetzt (Block 420). Servicequalität kann mit Priorität gleichgesetzt werden, wenn die Priorität einer Warteschlange durch die Servicequalität der Warteschlange definiert wird. Je größer die Servicequalitätsgarantie, umso höher die Priorität. Es wird bestimmt, ob Warteschlange 210 mit QoS = 0 Pakete zum Senden hat (Block 430). Wenn Warteschlange 210 keine Pakete zum Senden hat, wird QoS auf QoS + 1 (Block 475) gesetzt. Es wird bestimmt, ob QoS kleiner als 3 ist (Block 485). Der Grund hierfür besteht darin, zu bestimmen, ob alle Warteschlangen in dieser Service-Runde verarbeitet wurden. Wenn QoS kleiner als 3 ist, geht der Prozess zurück zu Block 430 und wiederholt sich für QoS = QoS + 1, weil die Service-Runde nicht abgeschlossen ist. Wenn QoS größer als oder gleich 3 ist, geht der Prozess zurück zu Block 420, wo QoS wieder auf Null gesetzt wird und eine neue Service-Runde beginnt.
Wenn bestimmt wird, dass Warteschlange 210 mit QoS = 0 Pakete zum Senden aufweist, wird der Quantenwert des Defizitzählers für diese Warteschlange (DC.0) um den Wert erhöht, um den der Quantenwert in dieser Aktualisierungsrunde (Aktualisierungsquantenwert) zu aktualisieren ist. Der Aktualisierungsquantenwert basiert typisch auf dem verfügbaren Quantenwert, dem reservierten Gesamtquantenwert für eine Aktualisierungsrunde und der Servicequalität für jede der Warteschlangen. Der reservierte Gesamtquantenwert kann mit Bezug auf den reservierten Mindestquantenwert jeder der Warteschlangen auf jeder QoS-Ebene bestimmt werden. Der reservierte Mindestquantenwert ist typisch der Quantenwert, der zur Erreichung der reservierten Mindestverkehrsrate pro QoS (0, 1, 2) Datenverkehr benötigt wird. Zum Beispiel:

Reservierter Mindestquantenwert 0: = Benötigter Quantenwert zur Erreichung des reservierten Mindestverkehrs für Qos 0 Datenverkehr.
Reservierter Mindestquantenwert 1: = Benötigter Quantenwert zur Erreichung des reservierten Mindestverkehrs für Qos 1 Datenverkehr.
Reservierter Mindestquantenwert 2: = Benötigter Quantenwert zur Erreichung des reservierten Mindestverkehrs für Qos 2 Datenverkehr.

Folglich ist der reservierte Gesamtquantenwert typisch gleich der Summe aller reservierten Mindestquantenwerte.
Die Summe des Defizitzählers und der Aktualisierungsquantenwert werden nun mit dem höchstmöglichen Wert des Defizitzählers für diese Warteschlange (DC.Max.QoS) (Block 440) verglichen. Wenn diese Summe kleiner als DC.Max.QoS ist, wird der Defizitzähler für diese Warteschlange auf einen mit DC.QoS gleichwertigen Wert, erhöht um den Aktualisierungsquantenwert.QoS (Block 460), eingestellt. Wenn diese Summe größer als DC.Max.QoS ist, wird der Defizitzähler für diese Warteschlange auf einen mit DC.Max.QoS gleichwertigen Wert eingestellt (Block 450).
Der höchstmögliche Wert des Defizitzählers für jede Warteschlange (DC.Max.QoS) wird typisch mit Bezug auf die Anzahl der aktiven Serviceströme mit der jeweiligen QoS der Warteschlange und die maximale Verkehrsdauerrate des stromabwärtigen Verkehrs für die jeweilige QoS der Warteschlange bestimmt. Wie oben angegeben, ist ein Servicestrom typisch der Pfad eines Pakets vom CMTS 110 im Vorwärtskanal zum Benutzergerät 150. Serviceströme werden typisch nach QoS eingeteilt. Die Anzahl der aktiven Serviceströme kann mit Bezug auf die Anzahl der Serviceströme bestimmt werden, die gegenwärtig mindestens ein Paket haben, das für den Strom eingestuft wurde.
Nach Einstellen des Quantenwerts des Defizitzählers für die Warteschlange für die gegenwärtige Service-Runde wird bestimmt, ob die Größe des ersten Pakets in der Warteschlange kleiner als oder gleich dem Quantenwert des Defizitzählers für diese Warteschlange (Block 470) ist. Wenn das erste Paket kleiner als oder gleich dem Quantenwert des Defizitzählers ist, wird das erste Paket in der Warteschlange verarbeitet (480). Nachdem das erste Paket verarbeitet wurde, zeigt der Defizitzähler einen um die Größe des übertragenen Pakets reduzierten Wert an (Block 490). Der Vorgang kehrt zu Block 490 zurück und der Prozess wiederholt sich, bis die Größe des zu sendenden Pakets den Wert des Defizitzählers überschreitet.
Wenn der Wert des Defizitzählers um die Größe des ersten Pakets in der Warteschlange überschritten wird, geht der Vorgang zu Block 475 weiter, wo QoS auf QoS + 1 eingestellt wird. Es wird bestimmt, ob QoS kleiner als 3 ist (Block 485). Wenn QoS kleiner als 3 ist, geht der Vorgang zu Block 430 zurück, und der Prozess wiederholt sich für QoS = QoS + 1, weil die Service-Runde nicht abgeschlossen ist. Wenn QoS größer als oder gleich 3 ist, kehrt der Vorgang zu Block 420 zurück, der die QoS auf Null zurücksetzt und eine neue Service-Runde startet.
Die Berechnung des Aktualisierungsquantenwerts, der oben mit Bezug auf 4 beschrieben wurde, kann auch anders implementiert werden, je nachdem, ob das System unter- oder überbelastet ist. Wenn das System unterbelastet ist, kann der Aktualisierungsquantenwert für jede Warteschlange höher als der reservierte Mindestquantenwert für jede Warteschlange sein. Wenn andererseits das System überbelastet ist, kann der Aktualisierungsquantenwert für jede Warteschlange kleiner als der reservierte Mindestquantenwert für jede Warteschlange sein.
Im Folgenden werden Ausführungsformen der vorliegenden Erfindung mit Bezug auf 5 beschrieben, welche ein Ablaufdiagramm eines Vorgangs zur Bandbreitenzuordnung darstellt. Im Netzwerk ankommende Pakete fordern eine QoS an (Block 500). Danach werden die Pakete entsprechend ihrer QoS-Anforderung eingestuft und einer Warteschlange zugeführt, die fähig ist, die QoS-Anforderung zu erfüllen (Block 510). Der verfügbare Quantenwert (verfügbare Bandbreite) auf dem Vorwärtskanal wird wie oben mit Bezug auf 4 besprochen, berechnet (Block 520). Es wird bestimmt, ob der verfügbare Quantenwert gleich oder größer als Null ist (Block 530). In anderen Worten, es wird bestimmt, ob der Vorwärtskanal irgendeine verfügbare Bandbreite enthält. Wenn keine verfügbare Bandbreite vorhanden ist (der verfügbare Quantenwert kleiner als Null ist), wird der Quantenaktualisierungswert auf Null gesetzt (Block 535), weil keine verfügbare Bandbreite zur Verteilung auf die Warteschlangen vorhanden ist.
Wenn bestimmt wird, dass der verfügbare Quantenwert größer als oder gleich Null ist, wird der reservierte Gesamtquantenwert, wie oben besprochen (Block 540) berechnet und mit dem verfügbaren Quantenwert (Block 550) verglichen. Wenn bestimmt wird, dass der verfügbare Quantenwert den reservierten Gesamtquantenwert überschreitet, werden die Quantenwerte der Warteschlangen aktualisiert, wobei ein Vorgang zur Zuordnung von Bandbreitenüberschuss gemäß erfindungsgemäßen Ausführungsformen zum Einsatz kommt (Block 560). In anderen Worten, nachdem die Mindestanforderungen des Systems erfüllt wurde, ist extra Bandbreite auf dem Vorwärtskanal vorhanden, die auf die Warteschlangen verteilt werden kann. Der Überschuss-Algorithmus wird unten mit Bezug auf 6 besprochen. Wenn bestimmt wird, dass der reservierte Gesamtquantenwert den verfügbaren Quantenwert überschreitet, werden die Quantenwerte der Warteschlangen aktualisiert, wobei ein Vorgang zur Zuordnung von Bandbreitendefizit gemäß erfindungsgemäßen Ausführungsformen zum Einsatz kommen (Block 555). In anderen Worten, es steht nicht genügend Bandbreite auf dem Vorwärtskanal zur Verfügung, um die Mindestanforderungen des Systems zu erfüllen. Der Defizit-Algorithmus wird unten mit Bezug auf 7 besprochen.
Die Über- und Unterquantenwerte können je nach der Servicequalität, die für einen bestimmten Servicestrom bereitzustellen ist, unterschiedlich sein. Der Quantenwert basiert auf der Anzahl von Paketen in der Warteschlange und dem garantierten Durchsatz der Warteschlange (QoS der Warteschlange). Ausführungsformen der vorliegenden Erfindung befassen sich mit der Situation, wenn der garantierte Durchsatz entweder höher oder niedriger als der Systemdurchsatz ist. Wenn ein Bandbreitenüberschuss vorhanden ist, ist der garantierte Durchsatz niedriger als der Systemdurchsatz. Wenn nicht genügend Bandbreite vorhanden ist, also ein Defizit vorliegt, ist der garantierte Durchsatz höher als der Systemdurchsatz.
Im Folgenden wird nun mit Bezug auf 6 ein Ablaufdiagramm beschrieben, welches einen Vorgang zur Zuordnung von Bandbreitenüberschuss gemäß erfindungsgemäßen Ausführungsformen veranschaulicht. QoS wird mit 0 gleichgesetzt (Block 600). Der reservierte Mindestquantenwert für die Warteschlangen mit QoS = 0 wird wie oben besprochen berechnet (Block 610). Der reservierte Mindestquantenwert 0 ist der Quantenwert, der zur Erfüllung des reservierten Mindestverkehrs für QoS 0 Datenverkehr benötigt wird.
Der Überquantenwert für die Warteschlangen mit QoS = 0 wird berechnet (Block 620). Der Quantenwert wird typisch berechnet, um zwischen verschiedenen Serviceebenen – einer Mindestserviceebene, einer gerechten Verteilung von Ressourcen in einem überbenutzten System und/oder einer optimalen Verteilung in einem unterbenutzten System – unterscheiden zu können.
Bei Quantenberechnungen muss eventuell der CMTS 110 die Anzahl der aktiven Serviceströme und die QoS-Parameter aller stromabwärtigen Serviceströme verfolgen oder auf sie zugreifen können. Ein aktiver stromabwärtiger Servicestrom, wie oben definiert, ist typisch die Anzahl der Serviceströme, die gegenwärtig mindestens ein für diesen Strom eingestuftes Paket aufweisen. Die aktiven Serviceströme können ebenfalls nach QoS eingeteilt sein. Die Anzahl der aktiven Serviceströme kann in einer Tabelle verfolgt werden. Eine solche Tabelle verfolgt zum Beispiel typisch Warteschlangenbezogene Information, wie die aktuelle Priorität dieser Warteschlange, die aktuelle Prioritätsebene für die Warteschlangenverarbeitung, die Anzahl der Jobs (Anforderungen) in jeder Warteschlange, und die Warteschlange, aus der Anforderungen aktuell verarbeitet werden. Diese Tabelle kann als Warteschlangenprioritäts- und Servicetabelle (QPS) bezeichnet werden. Der QPS oder Standardwert wird während der Einstufung zugeordnet.
Jeder stromabwärtige Servicestrom ist typisch mit dem QoS-Parameter verknüpft. Der QoS-Parameter kann auf der Verkehrspriorität, der stromabwärtigen maximalen Verkehrsdauerrate und/oder der reservierten Mindestverkehrsrate basieren. Für den Sprachverkehr ist der Servicestrom typisch mit Gewährungsgröße (grant size), Gewährungsintervall und/oder Gewährungen pro Intervall verknüpft.
Wiederum mit Bezug auf 6 wird der Aktualisierungsquantenwert mit der Summe aus Überquantenwert und reserviertem Mindestquantenwert gleichgesetzt (Block 630). Dieser Aktualisierungsquantenwert kann als der Aktualisierungsquantenwert benutzt werden, der oben mit Bezug auf 4 besprochen wurde (Block 440 und 460). Der Quantenwert der Warteschlange mit QoS = 0 wird mit dem Aktualisierungsquantenwert gleichgesetzt (Block 640). QoS wird mit QoS + 1 gleichgesetzt (Block 650). Es wird bestimmt, ob QoS kleiner als 3 ist (Block 660). Wenn QoS kleiner als 3 ist, kehrt der Vorgang zu 600 zurück und der Prozess wiederholt sich für QoS = QoS + 1, weil die Aktualisierungsrunde nicht abgeschlossen ist. Wenn QoS nicht kleiner als 3 ist, kehrt der Vorgang zu Block 600 zurück, der die QoS auf Null zurücksetzt und eine neue Aktualisierungsrunde startet, wenn das Aktualisierungsintervall abgeschlossen ist.
Die Quantenwerte werden in Zeitintervallen, die gleich dem Update_interval sind, aktualisiert. Wenn dieses Intervall nicht konstant gehalten kann, kann das Update_interval auf die aktuelle Zeit, reduziert um das letzte Aktualisierungsintervall, eingestellt werden. Hier kann das letzte Aktualisierungsintervall mit der aktuellen Zeit zu der Zeit gleichgesetzt werden, zu der die Quantenwerte aktualisiert werden.
Im Folgenden wird mit Bezug auf 7 ein Ablaufdiagramm beschrieben, welches einen Vorgang zur Zuordnung von Bandbreite gemäß erfindungsgemäßen Ausführungsformen veranschaulicht. QoS wird mit 0 gleichgesetzt (Block 700). Der reservierte Mindestquantenwert für die Warteschlangen mit QoS = 0 wird berechnet (Block 710). Wie oben angegeben, wird der reservierte Mindestquantenwert benötigt, um den reservierten Mindestverkehr für QoS 0 Datenverkehr zu erfüllen.
Der Unterquantenwert für die Warteschlangen mit QoS = 0 wird berechnet (Block 720). Der Quantenwert wird typisch berechnet, um zwischen verschiedenen Serviceebenen – einer Mindestserviceebene, einer gerechten Verteilung von Ressourcen in einem überbenutzten System und/oder einer optimalen Verteilung in einem unterbenutzten System – unterscheiden zu können.
Der Aktualisierungsquantenwert wird mit dem reservierten Mindestquantenwert, reduziert um den Unterquantenwert, gleichgesetzt (Block 730). Dieser Aktualisierungsquantenwert kann als der Aktualisierungsquantenwert benutzt werden, der oben mit Bezug auf 4 besprochen wurde (Block 440 und 460). Der Quantenwert für die Warteschlange mit QoS = 0 wird mit dem Aktualisierungsquantenwert gleichgesetzt (Block 740). Dann wird die QoS mit QoS + 1 gleichgesetzt (Block 750). Es wird bestimmt, ob QoS kleiner als 3 ist (Block 760). Wenn QoS kleiner als 3 ist, kehrt der Vorgang zu Block 700 zurück und der Prozess wiederholt sich für QoS = QoS + 1, weil die Aktualisierungsrunde nicht abgeschlossen ist. Wenn QoS nicht kleiner 3 ist, geht der Vorgang zu Block 700 zurück, der die QoS auf Null zurücksetzt und eine neue Aktualisierungsrunde startet, wenn das Update_interval abgeschlossen ist.
Insbesondere können Variablen der oben besprochenen erfindungsgemäßen Ausführungsformen durch die folgenden Gleichungen beschrieben werden. Die in die Gleichungen aufgenommenen Variablen können, wie in Tabelle 1 unten dargestellt, definiert werden.
FALL: Available-Bandwidth >= 0.0:
FALL: Verfügbare Mindestquantenaktualisierung >= 0.0 Aktualisierungsquantenwert.0 = update_interval × (min_Quant_update_0 + UU_weight_0 × DC.0/Committed_Data BW × Available_Bandwidth) Aktualisierungsquantenwert.1 = update_interval × (min_Quant_update_1 + UU_weight_1 × DC.1/Committed_Data_BW × Available_Bandwidth) Aktualisierungsquantenwert.2 = update_interval × (min_Quant_update_2 + UU_weight_2 × DC.2/Committed_Data_BW × Available_Bandwidth)
WOBEI

update_interval

= (Current-time + Previous_service_time + min_update_interval

FÜR DIESE ANWENDUNG

UU_weight_0 + UU_weight_1 + UU_weight_2 = 1.0

Min_Quant_Update_0

= Anzahl der aktiven Serviceströme mit Priorität 0 × minimum-reserved_traffic_rate

Min_Quant_Update_1

= Anzahl der aktiven Serviceströme mit Priorität 1 × minimum-reserved_traffic_rate

Min_Quant_Update_2

= Anzahl der aktiven Serviceströme mit Priorität 2 × minimum-reserved_traffic_rate

DC.Max.0 = (Anzahl der aktiven Serviceströme mit Priorität 0) × (Stromabwärtige maximale Verkehrsdauerrate 0) DC.Max.1 = (Anzahl der aktiven Serviceströme mit Priorität 1) × (Stromabwärtige maximale Verkehrsdauerrate 1) DC.Max.2 = (Anzahl der aktiven Serviceströme mit Priorität 2) × (Stromabwärtige maximale Verkehrsdauerrate 2)FALL: Available_Bandwidth < 0.0

WENN

Stromabwärtige maximale Verkehrsdauerrate (Sprachservicestrom 1) + Stromabwärtige maximale Verkehrsdauerrate (Sprachservicestrom 2) + .. Stromabwärtige maximale Verkehrsdauerrate Sprachservicestrom N) + (OU_weight_0 × Anzahl der aktiven Serviceströme mit Priorität 0 × minimum_reserved_traffic_rate_0) + (OU_weight_1 × Anzahl der aktiven Serviceströme mit Priorität 1 × minimum_reserved_traffic_rate_1) + (OU_weight_1 × Anzahl der aktiven Serviceströme mit Priorität 2 × minimum_reserved_traffic_rate_2) <= Verfügbare Bandbreite

DANN

Aktualisierungsquantenwert.0 = update_interval × (OU_weight_0 × Anzahl der aktiven Serviceströme mit Priorität 0 × minimum_reserved_traffic_rate_0) Aktualisierungsquantenwert.1 = update_interval × (OU_weight_1 × Anzahl der aktiven Serviceströme mit Priorität 1 × minimum_reserved_traffic_rate_1) Aktualisierungsquantenwert.2 = update_interval × (OU_weight_2 × Anzahl der aktiven Serviceströme mit Priorität 2 × minimum_reserved_traffic_rate_2)

WOBEI

update_interval

= (Current_time – Previous_service_time + min_update_interval)

Für diese Implementierung:

OU_weight_0

= OU_weight_1 = OU_weight_2

OU_weight_0

= (Downstream_Bandwidth – Committed_Voice_BW – Committed_Signaling_BW) + (Committed_Data_Bandwidth)

Tabelle 1
Die Ablaufdiagramme und Blockdiagramme in 1 bis 7 veranschaulichen die Architektur, Funktionalität und Betriebsweise möglicher Implementierungen für Systeme, Verfahren und Computerprogrammprodukte zur Zuordnung von Bandbreite gemäß verschiedener Ausführungsformen der vorliegenden Erfindung. In dieser Hinsicht kann jeder. Block in den Ablaufdiagrammen oder Blockdiagrammen ein Modul, ein Segment oder einen Codeabschnitt darstellen, der eine oder mehrere ausführbare Anweisungen zur Implementierung der angegebenen logischen Funktion(en) enthält. Es wird darauf hingewiesen, dass bei einigen Implementierungsalternativen die in den Blöcken angegebenen Funktionen in einer anderen als der in den Figuren angegebenen Reihenfolge vorkommen können. Zum Beispiel können zwei als aufeinanderfolgend dargestellte Blöcke in Wirklichkeit im Wesentlichen gleichzeitig ausgeführt werden, oder zuweilen, je nach betreffender Funktionalität, in umgekehrter Reihenfolge ausgeführt werden.
In den Zeichnungen und der Spezifikation wurden typische illustrative Ausführungsformen der Erfindung offenbart, aber obwohl spezifische Ausdrücke verwendet wurden, sind diese nur in einem allgemeinen und beschreibenden Sinn zu verstehen und dienen nicht zum Zwecke der Begrenzung; der Geltungsbereich der Erfindung ist den beiliegenden Ansprüchen zu entnehmen.

Claims

Verfahren zum Zuordnen von Bandbreite zwischen mehreren Warteschlangen (210, 215, 220), wobei jede der mehreren Warteschlangen (210, 215, 220) mit einer Servicequalität verbunden ist und einen entsprechenden Quantenwert aufweist, wobei das Verfahren folgende Schritte umfasst: Berechnen eines reservierten Gesamtquantenwerts, der Paketen entspricht, die in den mehreren Warteschlangen (210, 215, 220) eingereiht sind, für eine Aktualisierungsperiode anhand eines reservierten Mindestquantenwerts von jeder der mehreren Warteschlangen (210, 215, 220); Bestimmen eines verfügbaren Quantenwerts anhand einer Gesamtsumme der festen Bandbreite an einem Vorwärtskanal (240) und einer Gesamtsumme der Bandbreite am Vorwärtskanal (240); Bestimmen, für jede der mehreren Warteschlangen (210, 215, 220), eines jeweiligen Aktualisierungsquantenwertes anhand des verfügbaren Quantenwertes, des reservierten Gesamtquantenwertes und der Servicequalität in Verbindung mit der jeweiligen Warteschlange (210, 215, 220); und durch Folgendes gekennzeichnet: Aktualisieren der Quantenwerte von jeder der mehreren Warteschlangen (210, 215, 220) durch den jeweiligen Aktualisierungsquantenwert, der übermäßige Bandbreite zwischen den mehreren Warteschlangen (210, 215, 220) zuordnet, wenn der verfügbare Quantenwert größer als der reservierte Gesamtquantenwert ist, und der mangelnde Bandbreite zwischen den mehreren Warteschlangen (210, 215, 220) zuordnet, wenn der verfügbare Quantenwert kleiner als der reservierte Gesamtquantenwert ist.
Verfahren nach Anspruch 1, dadurch gekennzeichnet, dass die Quantenwerte der Servicequalität in Verbindung mit der jeweiligen Warteschlange (210, 215, 220) entsprechen.
Verfahren nach Anspruch 1, dadurch gekennzeichnet, dass der Schritt des Bestimmens des verfügbaren Quantenwerts folgende Schritte umfasst: Berechnen der Gesamtsumme der festen Bandbreite am Vorwärtskanal (240); Berechnen der Gesamtsumme der Bandbreite am Vorwärtskanal (240); und Bestimmen des Unterschieds zwischen der Gesamtsumme der festen Bandbreite am Vorwärtskanal (240) und der Gesamtsumme der Bandbreite am Vorwärtskanal (240).
Verfahren nach Anspruch 3, dadurch gekennzeichnet, dass der Schritt des Berechnens der Gesamtsumme der festen Bandbreite am Vorwärtskanal (240) auf einer Gesamtsumme der festen Bandbreite für Sprachverkehr, Datenverkehr und Signalverkehr beruht.
Verfahren nach Anspruch 1, dadurch gekennzeichnet, dass der jeweilige Aktualisierungsquantenwert Folgendes umfasst: einen Wert von Null, wenn der verfügbare Quantenwert kleiner als Null ist; den reservierten Mindestquantenwert für die Aktualisierungsperiode plus einen Überquantenwert für die Aktualisierungsperiode, wenn der verfügbare Quantenwert größer als der reservierte Gesamtquantenwert ist; und den reservierten Mindestquantenwert für die Aktualisierungsperiode minus einen Unterquantenwert für die Aktualisierungsperiode, wenn der reservierte Gesamtquantenwert größer als der verfügbare Quantenwert ist.
Verfahren nach Anspruch 5, dadurch gekennzeichnet, dass der Überquantenwert und der Unterquantenwert der Servicequalität in Verbindung mit der jeweiligen Warteschlange (210, 215, 220) entsprechen.
Verfahren nach Anspruch 5, dadurch gekennzeichnet, dass der Überquantenwert und der Unterquantenwert proportional zur Servicequalität in Verbindung mit der jeweiligen Warteschlange (210, 215, 220) sind.
Verfahren nach Anspruch 1, dadurch gekennzeichnet, dass das Verfahren in einem Breitband-Mehrfachzugriffssystem realisiert (110) ist.
Verfahren nach Anspruch 1, dadurch gekennzeichnet, dass die Aktualisierungsperiode ein konstantes Aktualisierungsintervall ist.
Verfahren nach Anspruch 1, dadurch gekennzeichnet, dass die Aktualisierungsperiode kein konstantes Aktualisierungsintervall ist.
Verfahren nach Anspruch 10, dadurch gekennzeichnet, dass die Aktualisierungsperiode eine aktuelle Zeit minus eine Zeit der letzten Aktualisierungsperiode ist.
Verfahren nach Anspruch 1, dadurch gekennzeichnet, dass die mehreren Warteschlangen (210, 215, 220) mehrere Pakete umfassen, die durch den Einsatz eines Deficit-Round-Robin-Algorithmus ausgeführt werden.
System (110) zum Zuordnen von Bandbreite, das Folgendes umfasst: mehrere Warteschlangen (210, 215, 220), wobei jede der mehreren Warteschlangen (210, 215, 220) mit einer Servicequalität verbunden ist und einen entsprechenden Quantenwert aufweist, der konfiguriert ist, um Pakete zu speichern, die vom Netz eingehen; eine Ausgabewarteschlange (225), die konfiguriert ist, um Pakete von den mehreren Warteschlangen (210, 215, 220) zu empfangen und sie zu einem Kanal (240) zu schicken; einen Bandbreitenzuordnungskreis (120), der konfiguriert ist, um empfangene Pakete anhand von Anforderungen an eine Servicequalität zu klassifizieren und um die Pakete zu einer der mehreren Warteschlangen (210, 215, 220) zu leiten, und der einen Quantenberechnungskreis umfasst, der konfiguriert ist, um einen reservierten Gesamtquantenwert zu berechnen, der Paketen entspricht, die in den mehreren Warteschlangen (210, 215, 220) eingereiht sind für eine Aktualisierungsperiode anhand eines reservierten Mindestquantenwertes von jeder der mehreren Warteschlangen (210, 215, 220), wobei der Bandbreitenzuordnungskreis (120) ferner Folgendes umfasst: einen Bandbreitendifferenzialkreis, der konfiguriert ist, um einen verfügbaren Quantenwert zu bestimmen anhand einer Gesamtsumme der festen Bandbreite an einem Vorwärtskanal (240) und einer Gesamtsumme der Bandbreite am Vorwärtskanal (240); und dadurch gekennzeichnet, dass der Bandbreitenzuordnungskreis (120) ferner Folgendes umfasst: einen Quantenaktualisierungskreis, der konfiguriert ist, um die Quantenwerte von jeder der mehreren Warteschlangen (210, 215, 220) zu aktualisieren durch einen jeweiligen Aktualisierungsquantenwert, der den jeweiligen der mehreren Warteschlangen (210, 215, 220) entspricht, wobei die jeweiligen Aktualisierungsquantenwerte auf dem verfügbaren Quantenwert, dem reservierten Gesamtquantenwert und der Servicequalität in Verbindung mit der jeweiligen Warteschlange (210, 215, 220) beruhen, und die jeweiligen Aktualisierungsquantenwerte übermäßige Bandbreite zwischen den mehreren Warteschlangen (210, 215, 220) zuordnen, wenn der verfügbare Quantenwert größer als der reservierte Quantenwert ist und mangelnde Bandbreite zwischen den mehreren Warteschlangen (210, 215, 220) zuordnen, wenn der verfügbare Quantenwert kleiner als der gesamte reservierte Quantenwert ist.
System nach Anspruch 13, dadurch gekennzeichnet, dass die Quantenwerte der Servicequalität in Verbindung mit der jeweiligen Warteschlange (210, 215, 220) entsprechen.
System nach Anspruch 13, dadurch gekennzeichnet, dass der Bandbreitendifferentialkreis Folgendes umfasst: einen Bandbreitenberechnungskreis, der konfiguriert ist, um die Gesamtsumme der festen Bandbreite am Vorwärtskanal (240) und die Gesamtsumme der Bandbreite am Vorwärtskanal (240) und den Unterschied zwischen der Gesamtsumme der festen Bandbreite am Vorwärtskanal (240) und der Gesamtsumme der Bandbreite am Vorwärtskanal (240) zu berechnen.
System nach Anspruch 15, dadurch gekennzeichnet, dass der Bandbreitenberechnungskreis (120) ferner konfiguriert ist, um die Gesamtsumme der festen Bandbreite am Vorwärtskanal (240) anhand einer Gesamtsumme der festen Bandbreite für Sprachverkehr, Datenverkehr und Signalverkehr zu berechnen.
System nach Anspruch 13, dadurch gekennzeichnet, dass der jeweilige Aktualisierungsquantenwert für jede der mehreren Warteschlangen (210, 215, 220) Folgendes umfasst: einen Wert von Null, wenn der verfügbare Quantenwert kleiner als Null ist; den reservierten Mindestquantenwert für die Aktualisierungsperiode plus einen Überquantenwert für die Aktualisierungsperiode, wenn der verfügbare Quantenwert größer als der reservierte Gesamtquantenwert ist; und den reservierten Mindestquantenwert für die Aktualisierungsperiode minus einen Unterquantenwert für die Aktualisierungsperiode, wenn der reservierte Gesamtquantenwert größer als der verfügbare Quantenwert ist.
System nach Anspruch 17, dadurch gekennzeichnet, dass der Überquantenwert und der Unterquantenwert der Servicequalität in Verbindung mit der jeweiligen Warteschlange (210, 215, 220) entsprechen.
System nach Anspruch 17, dadurch gekennzeichnet, dass der Überquantenwert und der Unterquantenwert proportional zur Servicequalität in Verbindung mit der jeweiligen Warteschlange (210, 215, 220) sind.
System nach Anspruch 13, dadurch gekennzeichnet, dass das System (110) ein Breitband-Mehrfachzugriffssystem ist.
System nach Anspruch 13, dadurch gekennzeichnet, dass die Aktualisierungsperiode ein konstantes Aktualisierungsintervall ist.
System nach Anspruch 13, dadurch gekennzeichnet, dass die Aktualisierungsperiode kein konstantes Aktualisierungsintervall ist.
System nach Anspruch 22, dadurch gekennzeichnet, dass die Aktualisierungsperiode eine aktuelle Zeit minus eine Zeit der letzten Aktualisierungsperiode ist.
System nach Anspruch 13, dadurch gekennzeichnet, dass die mehreren Warteschlangen (210, 215, 220) mehrere Pakete umfassen, die durch den Einsatz eines Unter-Ringalgorithmus ausgeführt werden.
Computerprogrammprodukt zum Zuordnen von Bandbreite zwischen mehreren Warteschlangen (210, 215, 220), wobei jede der mehreren Warteschlangen (210, 215, 220) mit einer Servicequalität verbunden ist und einen entsprechenden Quantenwert aufweist, wobei es Folgendes umfasst: ein computerlesbares Programmmittel, in dem ein computerlesbarer Programmcode ausgeführt ist, wobei der computerlesbare Programmcode einen reservierten Gesamtquantenwert berechnet, der Paketen entspricht, die in den mehreren Warteschlangen (210, 215, 220) eingereiht sind, für eine Aktualisierungsperiode anhand eines reservierten Mindestquantenwerts von jeder der mehreren Warteschlangen (210, 215, 220); einen computerlesbaren Programmcode, der einen verfügbaren Quantenwert anhand einer Gesamtsumme der festen Bandbreite an einem Vorwärtskanal (240) und einer Gesamtsumme der Bandbreite am Vorwärtskanal (240) bestimmt; einen computerlesbaren Programmcode, der für jede der mehreren Warteschlangen (210, 215, 220) einen jeweiligen Aktualisierungsquantenwert anhand des verfügbaren Quantenwertes, des reservierten Gesamtquantenwertes und der Servicequalität in Verbindung mit der jeweiligen Warteschlange (210, 215, 220) bestimmt; und gekennzeichnet durch einen computerlesbaren Programmcode, der Quantenwerte von jeder der mehreren Warteschlangen (210, 215, 220) durch den jeweiligen Aktualisierungsquantenwert aktualisiert, der übermäßige Bandbreite zwischen den mehreren Warteschlangen (210, 215, 220) zuordnet, wenn der verfügbare Quantenwert größer als der reservierte Gesamtquantenwert ist, und der mangelnde Bandbreite zwischen den mehreren Warteschlangen zuordnet, wenn der verfügbare Quantenwert kleiner als der reservierte Gesamtquantenwert ist.