PatentDe  


Dokumentenidentifikation DE602004004831T2 08.11.2007
EP-Veröffentlichungsnummer 0001478140
Titel Verfahren und Vorrichtung zur Ablauffolgeplanung von Paketen auf einer Netzwerkverbindung mit einer auf der Eingangsrate basierenden Priorität
Anmelder France Telecom, Paris, FR
Erfinder Oueslati, Sara, 92130 Issy-les-Moulineaux, FR;
Roberts, James, 78960 Voisins-le-Bretonneux, FR
Vertreter derzeit kein Vertreter bestellt
DE-Aktenzeichen 602004004831
Vertragsstaaten AT, BE, BG, CH, CY, CZ, DE, DK, EE, ES, FI, FR, GB, GR, HU, IE, IT, LI, LU, MC, NL, PL, PT, RO, SE, SI, SK, TR
Sprache des Dokument FR
EP-Anmeldetag 05.04.2004
EP-Aktenzeichen 042908921
EP-Offenlegungsdatum 17.11.2004
EP date of grant 21.02.2007
Veröffentlichungstag im Patentblatt 08.11.2007
IPC-Hauptklasse H04L 12/56(2006.01)A, F, I, 20051017, B, H, EP

Beschreibung[de]
Technisches Gebiet und Stand der Technik

Die Erfindung betrifft des Gebiet der Architektur von Paketnetzen und die Verwaltung der Dienstqualität dieser Netze.

Das Internet ist für Mehrfachdienste bestimmt und soll eine große Palette von Diensten und Anwendungen unterstützen. Man unterscheidet zwei große Verkehrsklassen in diesem Netz, den Echtzeitverkehr (oder "streaming"-Verkehr), der im Allgemeinen von den Audio- oder Video-Anwendungen erzeugt wird, und den Datenverkehr (oder elastischen Verkehr), der der Übertragung von digitalen Dokumenten entspricht. Der Echtzeitverkehr hat Dienstqualitätsanforderungen, die der Notwendigkeit der Signalerhaltung entsprechen – die Durchsatzveränderungen, die das von der Quelle erzeugte Signal kennzeichnen, müssen erhalten bleiben, wenn das Signal das Netz durchquert. Die Dienstqualität des Datenverkehrs misst sich durch die Übertragungszeit der Dokumente. Diese Zeit, oder auf äquivalenter Weise der bei der Übertragung realisierte mittlere Durchsatz, hängt von der ganzen Kommunikationskette von der Quelle bis zum Empfänger ab. Ein Dienstqualitätsziel für ein Internet könnte sein, für den Datenverkehr transparent zu wirken, indem keine zusätzliche Durchsatzreduzierung bezüglich der anderweitig eingeführten Begrenzungen (Server, Zugriffsnetze, Einrichtung des Benutzers) eingeführt wird; in diesem Sinne gewährleistet das Netz die Erhaltung des Durchsatzes der Datenflüsse.

Das öffentliche Internet bietet Benutzerkunden einen Transportdienst in einem kommerziellen Kontext an. Die Frage der Preisfestsetzung ist also wichtig. Die Netzarchitektur muss eine Kapitalrendite für den Betreiber erlauben, mit konkurrenzfähigen Preisen für die von den Benutzern geforderten Qualitätsdienste.

Verschiedene Vorschläge einer Netzarchitektur entsprechen diesen Qualitäts- und Rentabilitätsanforderungen unterschiedlich. Manche, wie Intserv, Diffserv oder MPLS-TE, sind genormt, während andere proprietär bleiben.

Die existierende IP-Netzwerk-Architektur, "Best-Effort-Architektur" (oder Architektur der "größten Mühe") genannt, bietet keinerlei Garantie für die Dienstqualität. Die Leistung wird zufriedenstellend durch die Überdimensionierung. Die Leistung hängt ebenfalls von der Kooperation der Benutzer ab, die im Prinzip den Durchsatz ihrer Anwendungen in Abhängigkeit vom Stauzustand des Netzes regeln müssen (insbesondere dank der Protokolle TCP und "TCP-friendly"). Die Pakete des Echtzeitverkehrs und des Datenverkehrs werden unterschiedslos verarbeitet.

Die IP-Router verwenden üblicherweise das Prinzip eines Lastverbunds, wenn zwei oder mehrere Pfade für die Weiterleitung eines Pakets verfügbar sind. Die Wahl für ein gegebenes Paket wird typischerweise durch die Anwendung einer "Hash"-Funktion an der Ursprungs-IP-Adresse des Pakets bestimmt: Diese Funktion führt als Ergebnis zu einer ganzen Zahl, die die fragliche Schnittstelle bezeichnet. So wird die Last auf die verschiedenen Pfade verteilt, während alle Pakete des gleichen Flusses dem gleichen Pfad folgen und somit in der richtigen Reihenfolge ankommen.

Die Preisfestsetzung ist im Allgemeinen für die Kleinnutzer pauschal. Die Großnutzer können dagegen den Betreiber in Abhängigkeit vom gesendeten (oder empfangenen) Verkehrsvolumen bezahlen. In diesem Fall gibt es im Allgemeinen einen Vertrag, der die angebotenen Dienstqualitätsmerkmale spezifiziert: Paket-Verlustrate, Durchgangszeit, Sicherheitselemente.

Unter den verschiedenen entwickelten Architekturvorschlägen, die es ermöglichen, die obige Architektur zu verbessern, verwenden die meisten ein Prinzip der Reservierung von Ressourcen. Das Netz und der Benutzer erstellen einen "Verkehrsvertrag" für eine vorgesehene Kommunikation:

  • – der Benutzer meldet die vorgesehene Kommunikation an, indem er die Beschaffenheit des Verkehrs beschreibt,
  • – das Netz teilt, wenn möglich, die notwendigen Ressourcen zu (Zugangskontrolle),
  • – der gesendete Verkehr wird beim Zugriff kontrolliert, um zu überprüfen, ob er die vorhergehende Beschreibung beachtet (oder die zugeteilten Ressourcen werden von einer Zeitablaufsteuerung vom Typ WFQ kontrolliert).

Gemäß der vorgeschlagenen Architektur betrifft dieser Vertrag unterschiedlich einen Mikrofluss oder ein Aggregat von Flüssen, eine Punkt-zu-Punkt-Kommunikation oder eine Mehrfachpunkt-Kommunikation.

Die Preisfestsetzung ist Teil des Vertrags. Sie hängt im Allgemeinen von der vom Benutzer gelieferten Verkehrsbeschreibung ab, die die Zuweisung von Ressourcen bedingt.

Bei der Differenzierung in Dienstklassen verarbeitet das Netz spezifisch alle Pakete, die zur gleichen Klasse gehören. Man unterscheidet die Differenzierung zwischen den zwei Qualitätstypen, die für den Echtzeitverkehr bzw. den Datenverkehr notwendig sind, und die Differenzierung zwischen unterschiedlichen Qualitätsniveaus des gleichen Typs. Es ist im Allgemeinen notwendig, die Zuteilung der Pakete zu den verschiedenen Dienstklassen sorgfältig zu kontrollieren, unter Beachtung des Wortlauts des Vertrags zwischen dem Benutzer und dem Betreiber bezüglich von Verkehrsaggregaten.

Die Preisfestsetzung ist Teil des Vertrags. Sie hängt im Allgemeinen vom in jeder Klasse gesendeten Verkehrsvolumen ab. Es gibt nicht unbedingt eine Tarifdifferenzierung je Qualitätsniveau, da sonst jeder Benutzer seinen ganzen Verkehr in der höchsten Qualitätsklasse platzieren würde.

Das selbstverwaltete Internet, das von F.P. Kelly in "Models for a self-managed Internet", Philosophical Transactions of the Royal Society, Vol. A358, Seiten 2335–2348, 2000, beschrieben wird, vermeidet den Rückgriff auf die Zuteilung und auf die Verwendung von Dienstklassen. In dieser Architektur sendet das Netz im Fall eines Staus ECN-Marken ("Explicit Congestion Notification"), die mit einem Einheits-"Preis" versehen sind. Die Benutzer können ihre "Rechnung" in Abhängigkeit von ihrer Reaktion auf die empfangenen Marken modulieren. Sie können so den Stau ignorieren, indem sie nicht auf die empfangenen Marken reagieren, wenn sie akzeptieren, mehr für ihre Kommunikation zu zahlen.

Die Notwendigkeit, Echtzeitverkehr und Datenverkehr zu unterscheiden, wird im Prinzip vermieden. Man beabsichtigt, die Laufzeit der Pakete vernachlässigbar zu machen (gering genug für Echtzeitflüsse), indem man die Besetzung einer virtuellen Wartenschlange nutzt, um die ECN-Markierung zu bestimmen.

Das selbstverwaltete Netz erfordert keine Anordnung eines spezifischen Signalisationsprotokolls und ermöglicht eine ebenso einfache Ressourcenverwaltung wie diejenige eines "Best Effort"-Netzes.

In der Architektur vom Typ "flow-aware networking" (Netz mit Kenntnis der Flüsse), die zu Beispiel von J. Roberts et al. in "Quality of service by flow-aware networking", Philosophical Transactions of the Royal Society, Vol. A358, Seiten 2197–2207, 2000, beschrieben ist, wird jeder Benutzerfluss "im Flug" identifiziert, und es wird eine Verkehrskontrolle auf der Basis dieser Flüsse durchgeführt. Ein Fluss ist eine Einheit von Paketen mit den gleichen Werten in bestimmten unveränderlichen Feldern des Vorspanns. Diese Felder sind typischerweise die Ursprungs- und Ziel-IP-Adressen, die Port-Nummern des Transportprotokolls IPv4 oder die Felder "Flow Label" in der Version IPv6. Ein Fluss kann durch diese Werte in Zuordnung zu einer Inaktivitätsdauer (Verzögerung) spezifiziert werden. Ein Fluss endet, wenn während dieses Inaktivitätsintervalls kein Paket beobachtet wird. Das Prinzip und die Elemente dieser Architektur sind in 1 dargestellt. Mittel 4 gewährleisten eine Überwachung des Spitzendurchsatzes der Echtzeitflüsse. Die Pakete werden anschließend an ein Modul 6 der Weiterleitungsentscheidung übertragen, das eine Liste 10 von geschützten Flüssen konsultiert. Es überträgt die zugelassenen Pakete zu einem Modul 8, das sie gemäß einer prioritären Schlange ordnet. Diese verleiht den Paketen der Flüsse vom Typ "Echtzeit" die Priorität. Daten 16 von Zulässigkeitsbedingungen werden vom Modul 8 zum Modul 6 gesendet. Es handelt sich hauptsächlich um eine Schätzung des aktuellen kumulierten Durchsatzes der Echtzeitflüsse und eine Messung der für einen Datenfluss verfügbaren Bandbreite.

Eine implizite Zugangskontrolle wird angewendet, um den Start neuer Flüsse zu verhindern, wenn ein Link oder ein Pfad momentan im Zustand der Überlastung ist. Diese Kontrolle hat den Schutz der Dienstqualität der bereits begonnenen Flüsse zum Gegenstand. Es gibt mehrere Vorschläge für die Durchführung einer impliziten Zugangskontrolle in der Literatur, zum Beispiel in dem Artikel von A. Kumar et al. "Non-intrusive TCP connection admission control for bandwidth management of an Internet access Link", IEEE Comm. Mag. Vol 38, Nr. 5, Seiten 160–167, 2000.

In der Architektur der 1 wird eine Differenzierung pro Dienstklasse angewendet, um Echtzeitverkehr und Datenverkehr zu unterscheiden. Die Zugriffsbedingungen hängen aber weder vom Typ noch von den besonderen Verkehrsmerkmalen der Flüsse ab. So vermeidet man die Notwendigkeit, die Verkehrsmerkmale der Flüsse anzuzeigen. Es bleibt notwendig, beim Zugriff zu gewährleisten, dass der Spitzendurchsatz der Echtzeitflüsse einen im Voraus festgelegten Grenzwert nicht überschreitet. Die Kenntnis dieses Grenzwerts ist obligatorisch, um die Zugangsbedingungen zu bestimmen (siehe den Artikel von T. Bonald et al. "IP traffic and QoS control towards a flow-aware architecture", Proc. of World Telecom. Conf., Paris 2002).

Die Preisfestsetzung in dieser Architektur könnte nur von dem von einem Kunden gesendeten (oder empfangenen) Verkehrsvolumen abhängen. Jeder begonnene Fluss ist wirksam (da geschützt) und somit kostenpflichtig. Die Unterscheidung Echtzeit/Daten erfordert keine Tarifdifferenzierung, da es keine Anregung für eine Substituierung gibt: Die Echtzeitflüsse erfahren vernachlässigbare Verluste und Verzögerungen, während die Datenflüsse durchsatzmäßig nicht begrenzt sind.

Ein anderer Typ von Architektur der Art "flow-aware" wird von der amerikanischen Firma Caspian Networks vorgeschlagen (siehe zum Beispiel die Veröffentlichungen von Patentanmeldungen US-2002/57699, US-2002/57651 und US-2002/80786). Die Flüsse werden wie oben "im Flug" identifiziert. Jedem zugelassenen Fluss werden Dienstqualitätsparameter und eine Route zugeordnet. Die Dienstqualitätsparameter werden von verschiedenen Informationsquellen abgeleitet, darunter der Vorspann der Pakete und eine Tabelle von Spezifikationen, die vom SLA des Benutzers abgeleitet werden. Die Route wird in Abhängigkeit von den Dienstqualitätsparametern und der aktuellen Benutzung der Ressourcen des Netzes berechnet, um die Leistungsanforderungen des Flusses zu beachten. Die Dienstqualitätsparameter präzisieren unter anderen einen garantierten Durchsatz (GR, für "guaranteed rate"). Ein verfügbarer Durchsatz (AR, für "available rate") wird dem Fluss für ein bestimmtes Zeitintervall in Abhängigkeit vom Stauzustand seiner Route zugeteilt. Diese Architektur verwendet eine Zeitablaufsteuerung am Eingang, um zu gewährleisten, dass der Durchsatz des Flusses den zugeteilten Durchsatz (GR + AR) beachtet. Eine Zeitablaufsteuerung am Ausgang gewährleistet die Beachtung der Leistungsanforderungen (insbesondere Laufzeit pro Paket). Die Zeitablaufsteuerung am Eingang erfolgt durch Abstand mit Zurückweisung der überflüssigen Pakete, und die Zeitablaufsteuerung am Ausgang verwendet einen Algorithmus vom Typ WFQ pro Fluss. Die Zugangskontrolle der Flüsse muss verwendet werden, wenn es unmöglich ist, eine geeignete Route für einen neuen eingehenden Fluss zu finden.

Die soeben beschriebenen Architekturen haben alle Nachteile, die auf verschiedene Weise mit der Beschaffenheit der Qualitätsgarantien, der Komplexität der Anwendung oder der Rentabilität des Netzes zusammenhängen.

Die Nachteile einer Architektur vom Typ "best effort" sind allgemein bekannt:

  • – Verschlechterung der Leistung aller Kommunikationen im Fall eines Staus,
  • – unkontrollierte Laufzeiten und Verluste von Paketen für die Echtzeitkommunikationen in Konkurrenz mit dem Datenverkehr,
  • – keine faire Aufteilung der Bandbreite, insbesondere, wenn bestimmte Benutzer böswillig sind,
  • ggf. hohe Kosten, um die Dienstqualität durch Überdimensionierung zu gewährleisten,
  • – die pauschale Preisfestsetzung erschwert die Definition eines gerechten Preises, der die Kapitalrendite gewährleistet, wenn der Verkehr der Benutzer sehr variabel ist,
  • – die Preisfestsetzung in Abhängigkeit vom Verkehrsvolumen ist anfechtbar aufgrund der Empfindlichkeit dieses letzteren für die Überlastung (Erneuerung von verlorenen Paketen) und der möglichen Nichtbeachtung eines Mindest-Qualitätsniveaus, die den Abbruch von laufenden Kommunikationen verursacht.

Bezüglich des Reservierungsprinzips treten die folgenden Nachteile auf:

  • – es stellt sich in der Praxis als unmöglich heraus, den Verkehr einer Kommunikation (mit typischerweise sehr variablem Durchsatz) mit kontrollierbaren Parametern beim Zugriff knapp zu beschreiben,
  • – die Anwendung der Reservierung ist komplex und erfordert ein Signalisationsprotokoll, die Aufrechterhaltung von Datenbanken mit den Parametern jeder Kommunikation (im Englischen "state" genannt) und die Anwendung von Zeitablaufsteuerungsmechanismen,
  • – der Begriff der Reservierung wird ungenau, wenn der von einer Kommunikation eingeschlagene Pfad nicht spezifiziert werden kann ("Reservierung" für eine Einheit von Verkehrsflüssen mit unterschiedlichen Zielen, insbesondere im Fall einer Architektur Diffserv, Instabilität des IP-Routing, ...),
  • – eine strikte Dienstqualitätsgarantie – im "garantierten Dienst" von Intserv, zum Beispiel – ist eine teure Lösung bezüglich der Ressourcen,
  • – die Über-Reservierung, die allgemein angewendet wird, um die Tatsache zu kompensieren, dass die Benutzer ihren Verkehr überschätzen, führt zur einer fehlenden realen Garantie,
  • – die Preisfestsetzung ist problematisch im Fall einer Über-Reservierung, die Preisfestsetzung auf der Basis der Verkehrsparameter (des Verkehrsvertrags) steht nicht in direkter Verbindung mit den Kosten der Kommunikation (die vom tatsächlich gesendeten Verkehrsvolumen abhängt); im Fall einer strikten Garantie kann eine Preisfestsetzung in Verbindung mit der Menge der reservierten Ressourcen (Bandbreite, Speicher) unerschwinglich sein.

Die Differenzierung in Dienstklassen führt zu weiteren Nachteilen:

  • – ein Fehlen von quantifizierbaren und überprüfbaren Dienstqualitätsgarantien für den Datenverkehr,
  • – Unmöglichkeit, die Dienstqualität des Echtzeitverkehrs zu garantieren, wenn der Pfad der Kommunikationen nicht festgelegt ist,
  • – die Verwaltung der Verkehrsgrenzwerten pro Klasse und pro Benutzer bleibt komplex (Verwaltung von SLA, "Policy"-Server, Signalisation der Verkehrsparameter, ...),
  • – der Verkehr innerhalb einer Klasse geringer Priorität erfährt die gleichen Nachteile wie der Verkehr in einer Architektur vom Typ "best effort" (Zusammenbruch der Leistung im Fall der Überlastung, kein Schutz vor böswilligen Benutzern),
  • – die Preisfestsetzung der verschiedenen Dienstklassen ist problematisch, ein Preisunterschied ist notwendig, kann aber von den Benutzern schlecht festgestellt werden, wenn kein Qualitätsunterschied ersichtlich ist,
  • – das Fehlen einer direkten Verbindung zwischen Tarif und Kosten erschwert die Definition einer Preisfestsetzung, die die notwendige Kapitalrendite ermöglicht.

Das selbstverwaltete Internet vermeidet eine große Anzahl der oben erwähnten Nachteilen, stützt sich aber auf ein Preisfestsetzungssystem, das selbst problematisch ist:

  • – die Anwendung einer auf den ECN-Marken basierenden Preisfestsetzung ist komplex und kann angefochten werden,
  • – wie können einem Benutzer, der beim Netz des Betreibers A abonniert ist, die Staumarken berechnet werden, die vom dahinter liegenden Netz kommen, das einem anderen Betreiber B gehört?
  • – die Einnahmen der ECN-Preisfestsetzung gewährleisten nicht die Kapitalrendite eines gut dimensionierten Netzes; da ein anderes Preisfestsetzungsprinzip diese Rendite gewährleisten muss, könnte die ECN-Preisfestsetzung den Benutzern als ein unberechtigter Aufpreis erscheinen.

Die Architektur vom Typ "flow-aware", die in den oben erwähnten Veröffentlichungen erläutert wird, hat noch die folgenden Nachteile:

  • – die explizite Differenzierung zwischen Echtzeitverkehr und Datenverkehr erfordert die Kontrolle des Spitzendurchsatzes der Echtzeitflüsse,
  • – es ist notwendig, einen maximalen Spitzendurchsatz für die Echtzeitflüsse festzulegen und ihn rigoros zu kontrollieren, während es ohne Stau möglich wäre, Flüsse mit größerem Durchsatz zuzulassen, ohne der Leistung zu schaden,
  • – die Leistung bleibt gegenüber der möglichen Böswilligkeit von Seiten der Benutzer verletzlich,
  • – die vorgeschlagenen Verfahren, um den Stauzustand zu messen (Schätzung der verfügbaren Bandbreite mit einer TCP-Phantom-Verbindung oder ausgehend von der Beobachtung des Verlustgrads) können schwierig anzuwenden sein.

Bezüglich der Architektur vom Typ "flow-aware" von Caspian seien die folgenden Nachteile erwähnt:

  • – die Berücksichtigung von Dienstqualitäts- und Verkehrsparametern pro Fluss erfordert eine komplexe Anwendung, die zu Problemen der Erweiterbarkeit führen könnte,
  • – die über diese Architektur verfügbare Literatur präzisiert nicht die Verfahren, die angewendet werden, um die Beachtung der Dienstqualität der Flüsse durchzusetzen; diese Verfahren, und insbesondere die Definition der Prinzipien der Zugangskontrolle, sind aber bestimmend für die Wirksamkeit der vorgeschlagenen Architektur,
  • – die erwähnten Zeitablaufsteuerungen (Abstand am Eingang, WFQ pro Fluss am Ausgang) erfordern die Kenntnis der spezifischen Parameter pro Fluss (insbesondere, wenn sie vom Echtzeittyp – GR, MR – oder vom Typ Daten sind – AR), um ihre Dienstqualitätsanforderungen zu beachten.
  • – die Frage der Preisfestsetzung wird nicht angesprochen.

Die Druckschrift WO 02062013 beschreibt einen Algorithmus und eine Vorrichtung, die eine Zeitablaufsteuerung vom Typ "faires Einreihen" mit einer prioritären Verarbeitung bestimmter Pakete in Abhängigkeit von den Informationen, die sie enthalten, einbeziehen. Das Dokument Wang et al., "A priority based WFQ schedules for real time networks" XP 010365375, beschreibt ein Zeitablaufsteuerungssystem basierend auf den Sitzungen zugeordneten Attributen.

Darlegung der Erfindung:

Die Erfindung hat eine Vorrichtung sowie ein Verfahren zur Verarbeitung von Flusspaketen auf einem Netz-Link zum Gegenstand, wie es in den unabhängigen Ansprüchen 1 und 19 beschrieben ist.

Eine Zeitablaufsteuerung vom Typ "faires Einreihen mit Priorität" ermöglicht es, den Paketen der Flüsse Priorität zu verleihen, deren Durchsatz unter einem dynamischen Schwellwert liegt. Dieser Schwellwert entspricht zum Beispiel dem Durchsatz, der aktuell von den Flüssen realisiert wird, die mehrere Pakete im Wartezustand haben, da diese letzteren gemäß einem Algorithmus vom Typ "faires Einreihen" bedient werden.

Eine solche Vorrichtung oder Verfahren kann ohne Zugangskontrollmittel funktionieren, insbesondere im Rahmen eines Zugriffsnetzes, in dem die Gefahr eines Staus besser beherrschbar ist als im Kern des Netzes.

Erfindungsgemäß kann man auch eine Zugangskontrolle pro Fluss mit einer Zeitablaufsteuerung vom Typ "faires Einreihen" ("fair queuing" im Englischen) zuordnen.

Die Erfindung hat also ebenfalls eine Vorrichtung und ein Verfahren zur Verarbeitung von Paketen der Flüsse auf einem Netz-Link zum Gegenstand, die aufweisen:

  • – Mittel, bzw. einen Schritt, der Zugangskontrolle, um den Zugang der Flüsse in die Vorrichtung gemäß so genannten Zugangskriterien zu kontrollieren,
  • – Mittel, bzw. einen Schritt, der Zeitablaufsteuerung, um die Pakete in einer Warteschlange gemäß einem Algorithmus zum fairen Einreihen mit Priorität einzuordnen.

Die Zeitablaufsteuerungsmittel können an die Zugangskontrollmittel Daten von Zulässigkeitsbedingungen senden.

Diese Vorrichtung und dieses Verfahren ermöglichen die Gewährleistung einer Dienstqualität, ohne explizit zwischen Echtzeitflüssen und Datenflüssen zu unterscheiden.

So minimiert man die Laufzeit der Pakete der Echtzeitflüsse, deren Durchsatz unter einem durch die Zugangsbedingungen bestimmten Schwellwert bleibt. Wenn die Zugangskontrolle nicht aktiviert ist, wird dieser Schwellwert eher durch die Verkehrsbedingungen bestimmt.

Die Zulässigkeitsbedingungen werden direkt von Zeitablaufsteuerungsmitteln bestimmt, die den fairen Durchsatz, der von den Datenflüssen realisiert wird, sowie die von den prioritären Paketen repräsentierte Last messen.

Die Vereinigung der Zugangskontrolle und der Zeitablaufsteuerung vom Typ faires Einreihen ermöglicht es, einen gewissen "gekreuzten Schutz" herzustellen:

  • – man schützt den Durchsatz der Datenflüsse, indem ein faires Einreihen gewährleistet wird,
  • – man schützt die Paket-Laufzeit der Echtzeitflüsse, indem ihre Priorität gewährleistet wird,
  • – man vermeidet die Komplexität der Zeitablaufsteuerung zum fairen Einreihen, indem die Anzahl von zu berücksichtigenden Flüssen durch Zugangskontrolle begrenzt wird,
  • – die Zugangskontrolle wird durch die Messungen erleichtert, die in die Zeitablaufsteuerungsmittel integriert sind.

Durch Vereinigung der Techniken der Zugangskontrolle (implizit) und der Zeitablaufsteuerung zum fairen Einreihen ermöglicht die Erfindung die Gewährleistung einer "adäquaten" Qualität ohne Angabe von Verkehrseigenschaften, ohne Definition von Dienstklassen und ohne explizite Reservierung von Ressourcen.

Wenn die Zugangskontrolle nicht aktiviert ist, verliert man gewisse Vorteile des gekreuzten Schutzes, aber man behält die implizite Differenzierung der Dienstqualität bei, vorausgesetzt, dass das Link nicht überlastet ist. Die Pakete der Echtzeitflüsse mit geringem Durchsatz erfahren nur eine geringe Wartezeit, während die Datenflüsse den vom fairen Einreihen gewährleisteten Durchsatz erreichen können. Diese Konfiguration kann insbesondere im Fall eines Links des Zugriffsnetzes genügen, in dem die Staugefahr aufgrund der relativ geringen Anzahl von bedienten Benutzern gering ist.

Die gewählte Zeitablaufsteuerung macht die Architektur unverletzlich gegenüber der möglichen Nicht-Kooperation von Seiten der Benutzer. Die Architektur ermöglicht eine einfache Preisfestsetzung auf der Basis des gesendeten oder empfangenen Verkehrsvolumens. Man behält die Einfachheit der Beziehungen Benutzer-Betreiber des selbstverwalteten Netzes bei, ohne die mit der Preisfestsetzung in Abhängigkeit von den ECN-Marken verbundenen Nachteile. Diese Einfachheit wird von der Robustheit und der Wirksamkeit der Architektur "flow-aware" begleitet.

Die Flüsse, deren Durchsatz bei der Ankunft derart ist, dass sie mindestens ein Paket in der Warteschlange behalten, stellen am Ausgang in etwa den gleichen Durchsatz, "fairer Durchsatz" genannt, her. Wenn die Pakete eines Echtzeitflusses in einem Burst mit einem Durchsatz ankommen, der momentan höher ist als der faire Durchsatz (aufgrund von Wartezeiten in den stromaufwärts liegenden Schlangen, zum Beispiel) lässt die Zeitablaufsteuerungsvorrichtung erfindungsgemäß das erste Paket prioritär durch, verzögert aber die folgenden, indem sie einen mit dem fairen Durchsatz kompatiblen Abstand auferlegt. Wenn der Ursprungsdurchsatz des Flusses geringer ist als dieser faire Durchsatz, "glättet" der Abstand den Fluss, indem keine zusätzliche Laufzeit im Vergleich mit der vom Empfangsspeicher am Zielort auferlegten Laufzeit eingeführt wird (der an den Endbenutzer die Pakete mit ihrer Ursprungsgeschwindigkeit senden muss). In diesem Sinne bleibt die Laufzeit vernachlässigbar. Ein Echtzeitfluss, dessen Durchsatz höher ist als der faire Durchsatz, würde dagegen verändert, und die Quelle würde typischerweise zu einer Durchsatzverringerung gezwungen, um den Verlust von Paketen zu vermeiden.

Die eingesetzten Mechanismen garantieren also eine Laufzeit und einen Verlust von Paketen, die vernachlässigbar sind für die Flüsse, deren Spitzendurchsatz, der von Elementen außerhalb des fraglichen Netzes bestimmt wird, unter einem gewissen Schwellwert liegt. Dieser Schwellwert ist dynamisch und entspricht dem fairen Durchsatz (im Sinne max-min), der von der gewählten Zeitablaufsteuerung realisiert wird. Die Zugangskontrolle realisiert dann das doppelte Ziel der Beibehaltung des Durchsatzes der Datenflüsse und der Beibehaltung des Signals der Echtzeitflüsse.

Die Zugangskontrolle macht die Zeitablaufsteuerung mit fairem Einreihen erweiterbar, indem sie die Anzahl von zu berücksichtigenden Flüssen begrenzt. Das faire Einreihen erleichtert die Messung des Stauzustands des bedienten Links, Messung, die es ermöglicht, die Zugangsbedingungen zu bestimmen.

Die Erfindung ermöglicht es, eine Vorrichtung und ein Verfahren der Zeitablaufsteuerung vom Typ faires Einreihen mit Priorität zu verwenden, um implizit die Echtzeitflüsse und die Datenflüsse zu unterscheiden, indem den ersten eine geringe Laufzeit pro Paket gewährleistet wird.

Die Vereinigung der impliziten Zugangskontrolle pro Fluss mit der Zeitablaufsteuerung des fairen Einreihens mit Priorität ermöglicht es, die Dienstqualität zu gewährleisten, ohne explizit die Echtzeitflüsse und Daten zu unterscheiden.

Man kann einen Lastteilungsmechanismus verwenden, um eine adaptive Weiterleitung ausgehend von der Kennung der Flüsse durchzuführen. Die Zugangskontrolle weist nämlich die Flüsse zurück, die ankommen, wenn das Link überlastet ist, indem sie das erste empfangene Paket zurückweist. Der entsprechende Verkehr ist dadurch nicht verloren, wenn der Benutzer seinen Versuch wiederholt, indem er das gleiche Paket bis zum Erfolg immer wieder sendet. Die Erfolgswahrscheinlichkeit ist größer, wenn das Paket bei jedem Versuch einem anderen Link präsentiert wird, das in der Lage ist, es zu seinem Zielort weiterzuleiten.

Zu diesem Zweck kann der vom Router verwendete Lastverbundmechanismus auf den Flussidentifikator einwirken, wobei dieser ein frei vom Benutzer gefülltes Feld aufweist (zum Beispiel eine Port-Nummer in IPv4, das "flow label" in IPv6). Die den Lastverbund herstellende "Hash"-Funktion enthält als Argument dieses freie Feld, so dass der Benutzer eine Art adaptives Routen durchführt, indem er den Wert des fraglichen Felds bei jeder Erneuerung verändert.

Die Erfindung ermöglicht es, die Robustheit des Netzes mit Kenntnis der Flüsse mit der Einfachheit des selbstverwalteten Internets zu verbinden. Man nimmt vom ersten die implizite Zugangskontrolle unter Vermeidung der Notwendigkeit für den Benutzer, den Echtzeitverkehr vom Datenverkehr zu unterscheiden. Diese Unterscheidung wird automatisch vom Netz gemacht, indem es ihre verschiedenen Verkehrsmerkmale auswertet.

Kurze Beschreibung der Figuren:

1 zeigt schematisch Elemente der Architektur "flow-aware networking",

2 zeigt Elemente einer Architektur gemäß der Erfindung,

3 ist ein Diagramm eines Zulässigkeitsbereichs,

4 stellt das Prinzip einer PIFO-Warteschlange dar,

die 5 und 6 stellen einen Algorithmus dar, der entweder bei Ankunft eines Pakets oder am Ende des Sendens eines Pakets ausgeführt wird,

die 7 und 8 stellen die Operationen dar, die die Messung der Stauanzeiger, prioritäre Last und fairer Durchsatz, gewährleisten.

Ausführliche Beschreibung der Ausführungsformen der Erfindung:

Eine erste Ausführungsform ist in 2 dargestellt.

In dieser Figur bezeichnet das Bezugszeichen 24 ein Modul oder Weiterleitungsmittel, die die Zugangskontrolle der Pakete 20 der eingehenden Flüsse ausführen.

Die Definition eines Flusses ist zum Beispiel diejenige der flow-aware-Architektur, die im Artikel von Bonald et al. "IP traffic and QoS control: the need for a flow-aware architecture", World Telecom Conference, Paris, 2002, dargelegt wird.

Die diesem Modul präsentierten Pakete 20 werden zum Beispiel durch klassische Weiterleitungsfunktionen bestimmt, die einen Lastverbund enthalten können, der durch Anwendung einer "Hash"-Funktion an eine Untereinheit der Felder des Fluss-Identifikators erhalten wird. Eine Form des adaptiven Routings wird durchgeführt, indem in dieser Untereinheit ein Feld des Vorspanns eingefügt wird, das frei vom Benutzer ausgefüllt wird (Port-Nummer des Transportprotokolls, "flow label" von IPv6).

Das Modul 24 konsultiert und aktualisiert eine Liste 30 von so genannten "geschützten" Flüssen: Es handelt sich tatsächlich um die (durch die Mittel 24) zugelassenen und aktiven Flüsse (d.h., dass ein neues Paket des Flusses innerhalb eines gewissen Zeitintervalls identifiziert wurde).

Das Bezugszeichen 28 bezeichnet ein Modul oder Zeitablaufsteuerungsmittel, die es erlauben, die Warteschlange der Pakete gemäß einem Algorithmus oder einem Verfahren des fairen Einreihens mit Priorität zu verwalten.

Gemäß diesem Algorithmus oder diesem Verfahren sind die Pakete der Flüsse prioritär, deren Durchsatz den dem aktuellen fairen Durchsatz entsprechenden Schwellwert nicht überschreitet. Diese Bedingung äußert sich durch die Werte bestimmter Parameter des verwendeten Algorithmus zum fairen Einreihen, wie weiter unten im Rahmen einer besonderen Ausführung erläutert wird. Dagegen werden die Pakete der Flüsse, deren Ankunftsdurchsatz den fairen Durchsatz überschreitet, als "nicht-prioritär" eingestuft.

Dies ermöglicht es außerdem, den Spitzendurchsatz der Echtzeitflüsse zu regeln. Die eingehenden Flüsse 20, deren Durchsatz zu hoch ist, werden nämlich vom Zeitablaufsteuerungsmodul 28 identifiziert und als "nicht-prioritär" zurückgestuft oder eingeordnet.

Dieser Mechanismus ersetzt also das Modul 4 der Überwachung des Spitzendurchsatzes der Echtzeitflüsse der 1 und erlaubt, es wegzulassen.

Außerdem liefern das Modul oder die Mittel 28 Daten oder Parameter 36 von Zulässigkeitsbedingungen an das Weiterleitungsmodul 24.

Schließlich bezeichnet das Bezugszeichen 32 den Abgang der Pakete, während die Bezugszeichen 34 und 38 die Zurückweisung der Pakete durch das Zeitablaufsteuerungsmodul bzw. durch das Zugangskontrollmodul bezeichnen.

Es sei daran erinnert, das in einem Benutzungsmodus der Erfindung das Zugangskontrollmodul fehlen kann, so dass die Flüsse 20 sich direkt dem Modul 28 präsentieren.

Dieser Mechanismus muss nicht a priori die Pakete oder die Flüsse als vom Echtzeittyp oder vom elastischen Typ identifizieren.

Typischerweise wird die Architektur der 2 in einem Router oder in einem Prozessor oder einem Mikroprozessor für einen Router installiert, der programmiert ist, um die gewünschten Funktionen auszuführen.

Ein Ausführungsbeispiel des Moduls 24 der Weiterleitungsentscheidung wird nun etwas ausführlicher erläutert.

In einem klassischen IP-Netz werden die Flüsse auf einem einzigen Pfad weitergeleitet, der durch die IP-Zieladresse unabhängig von ihrem Stauzustand bestimmt wird. In der vorliegenden Architektur entscheidet ein Weiterleitungsentscheidungsmodul 24 auf der Basis von Informationen, die in einer oder mehreren Listen 30 von geschützten Flüsse (LFP) enthalten sind, ob die Pakete eines gegebenen Flusses weitergeleitet werden sollen oder nicht.

Eine Liste von geschützten Flüssen 30 ist eine Liste von Identifikatoren von Flüssen, die für jeden die Ankunftszeit des letzten Pakets angeben. Jede Liste ist einer Aufteilung des Raums der Identifikatoren zugeteilt. Diese Aufteilung ermöglicht es, die Kapazität jeder Liste zu begrenzen und somit die Erweiterbarkeit zu garantieren.

Ein Fluss wird von der Liste 30 gestrichen, wenn die seit dem letzten für den Fluss empfangenen Paket vergangene Zeit einen Schwellwert oder ein Verzögerungsintervall überschreitet. Die Länge dieses Intervalls ist ein Parameter des Systems, zum Beispiel in der Größenordnung von einigen Sekunden. Vorzugsweise wird die Tabelle dimensioniert, um die Sättigungswahrscheinlichkeit zu begrenzen, d.h. ein Zustand, in dem ein Fluss in die Liste zugelassen werden müsste, während diese aber voll ist. Die Konsequenz einer solchen Sättigung wäre nur, dass ein Fluss verzögert den Status eines geschützten Fluss erlangen würde. Seine Pakete würden trotzdem korrekt weitergeleitet, wenn der Stauzustand es erlaubt. Die Sättigungswahrscheinlichkeit kann durch eine geeignete Dimensionierung ausreichend gering gemacht werden.

Die Weiterleitungsentscheidungen werden bei Ankunft jedes Pakets getroffen. Das Modul 24 bestimmt zusammen ausgehend von den Informationen des Vorspanns des Pakets die Ausgangsschnittstelle und die geeignete Liste. Wenn das Paket zu einem geschützten Fluss gehört, wird es sofort weitergeleitet. Die Ankunftszeit des letzten Pakets wird in der Liste aktualisiert. Wenn der Fluss nicht bereits geschützt ist, muss eine Weiterleitungsentscheidung getroffen werden.

Das Paket wird zurückgewiesen, wenn Zugangsbedingungen nicht erfüllt sind. Die Beschaffenheit dieser Bedingungen wird weiter unten erläutert. Die angewendeten Bedingungen können von besonderen Attributen des Pakets abhängen, darunter der Wert des Felds "Verkehrsklasse" in IPv6, oder das Feld ToS in IPv4 oder IP-Adressen Quelle und Ziel.

Die Zugangskontrolle ermöglicht es, die Transparenz der zugelassenen Flüsse zu gewährleisten: Beibehaltung des Signals für die Echtzeitflüsse, Beibehaltung des Durchsatzes für die Datenflüsse. Tatsächlich wird diese Transparenz nur den Flüssen angeboten, deren Spitzendurchsatz (bestimmt durch die externen Begrenzungen) unter einem bestimmten Schwellwert bleibt. Der zulässige Durchsatzschwellwert ist geringer für die Echtzeitflüsse als für die Datenflüsse, da die jeweiligen Transparenzgarantien (d.h. Durchsatzbeibehaltung und Signalbeibehaltung) in den beiden Fällen unterschiedliche Zeitskalen erfordern. Für einen Echtzeitfluss sucht man sich zu vergewissern, dass der verfügbare Durchsatz größer ist als sein Spitzendurchsatz in einer kleinen Zeitskala, die mit einer "vernachlässigbaren" Laufzeit der Pakete (einige Millisekunden) kompatibel ist. Für die Datenflüsse versucht man, in etwa einen gewissen mittleren Durchsatz über eine relativ große Zeitdauer (von einigen Sekunden) zu realisieren.

Die beiden fraglichen Spitzendurchsätze resultieren aus der Wahl der Zugangskriterien. Anders gesagt, um die Transparenz der Flüsse eines gewissen Durchsatzes zu gewährleisten, definiert man eine geeignete Zugangsbedingung, die auf den Staumessungen "fairer Durchsatz" und "prioritäre Last" basiert. Für den Fall, in dem die Flüsse alle elastisch sind, wird die Wahl eines geeigneten Schwellwerts für den fairen Durchsatz zum Beispiel von Ben Fredj et al. (Measurement based admission Control for Elastic Traffic, Teletraffic Engineering in the Internet Era, ITC 17, Elsevier, 2001) beschrieben. Es sei threshold_1 (T1) der fragliche Schwellwert. Wenn alle Flüsse vom Echtzeittyp mit begrenztem Spitzendurchsatz sind, kann ein Zugangsschwellwert auf die prioritäre Last von der Vorgehensweise von Gibbens et al "A decision theoretic approach to Call Admission in ATM Networks", IEEE J. on Selected Areas in Communications, Vol. 13, Nr. 6, S. 1101–1114, 1995, abgeleitet werden. Es sei threshold 2 (T2) dieser zweite Schwellwert.

3 zeigt als Beispiel einen Zulässigkeitsbereich, der von diesen zwei Schwellwerten definiert wird. Man weist einen neuen Fluss zurück, wenn der faire Durchsatz unter T1 liegt (Zone I in der Grafik) oder wenn die prioritäre Last größer ist als T2 und wenn der faire Durchsatz unter T2 liegt (Zone II). Wenn nämlich die prioritäre Last den Schwellwert T2 überschreitet, wenn aber der faire Durchsatz größer ist als sie, ist das eine Anzeige dafür, dass die als prioritär angesehenen Pakete nicht ausschließlich von Echtzeitflüssen mit begrenztem Spitzendurchsatz kommen. Durch Erprobung kann man die Definition dieses Zulässigkeitsbereichs verfeinern.

Man definiert eine logische Funktion Admit (fairer Durchsatz, prioritäre Last) derart, dass es, wenn Admit den Wert 1 hat, möglich ist, einen neuen Fluss zu akzeptieren, und wenn Admit den Wert 0 hat, die neuen Flüsse zurückgewiesen werden müssen. Gemäß einem einfachen Beispiel der Zugangspolitik werden alle Flüsse unter den gleichen Bedingungen angenommen oder zurückgewiesen. Man kann nämlich die Beschaffenheit eines Flusses nicht a priori erraten. Also wird eine Hypothese "schlimmster Fall" erstellt, und man nimmt an, dass der neuen Fluss so anspruchsvoll und so störend wie möglich sein könnte. Diese Politik gewährleistet, dass alle Flüsse auf faire Weise gegenüber der Blockierung behandelt werden.

Wenn gemäß den Zugangsbedingungen das Paket nicht zurückgewiesen werden soll, wird es über das entsprechende Link weitergeleitet. Die Identität des Flusses ist dann Kandidat für die Einfügung in die Liste 30. Mehrere zusätzliche Kriterien könnten definiert werden, um diese Einfügung schließlich zu erlauben. Insbesondere könnte die Entscheidung probabilistisch sein, mit der Wahrscheinlichkeit p wird der Fluss hinzugefügt, mit der Wahrscheinlichkeit 1-p wird das Paket weitergeleitet, aber der Fluss bleibt ungeschützt. Diese Wahrscheinlichkeit p kann von den Attributen des Pakets abhängen, darunter der wert des Felds "Verkehrsklasse", des Felds ToS oder der IP-Adressen.

Wenn p gering ist (zum Beispiel 0.1), werden die meisten kleinen Flüsse nicht berücksichtigt, während die großen Flüsse ab dem Senden der ersten Zehnern von Paketen geschützt werden. Ein Nachteil der Wahl p < 1 ist die mögliche Zurückweisung eines laufenden Flusses, die Anfangspakete werden übertragen, aber eine Zugangskontrollentscheidung sperrt den Fluss, ehe er in den Zustand eines geschützten Flusses übergeht.

Bezüglich der oben erwähnten Zugangsbedingungen, so hängen sie von Staumessungen, die innerhalb der Vorrichtung durchgeführt werden, oder von den Zeitablaufsteuerungsmitteln 28 ab. Man kann zum Beispiel zwei Indikatoren messen, den fairen Durchsatz und die prioritäre Last:

  • – der faire Durchsatz ist eine Messung des Durchsatzes, den ein Datenfluss reaisieren würde, der immer Pakete zu senden hätte,
  • – die prioritäre Last ist die Summe der Länge der prioritären Pakete, übertragen innerhalb eines bestimmten Intervalls, dividiert durch die Dauer dieses Intervalls.

Um den fairen Durchsatz zu schätzen, kann man in den Algorithmus der Zeitablaufsteuerung einen Fluss von fiktiven Paketen einführen, und man misst den Durchsatz, den dieser Fluss empfangen hätte, unter der Annahme, dass er immer Pakete zu senden hat. Natürlich werden die fiktiven Pakete nicht wirklich gesendet. Man unterscheidet zwei Fälle:

  • – in Gegenwart von Flüssen mit mehreren wartenden Paketen fügt der fiktive Fluss seine Pakete zyklisch zwischen ihre Sendungen ein, indem er die prioritären Pakete vorlässt,
  • – wenn die Warteschlange leer ist (kein wartendes reales Paket), wird der fiktive Fluss theoretisch auf den Durchsatz des Links geregelt. Die Berechnung des fairen Durchsatzes am Ende der Messperiode berücksichtigt diese Perioden der Inaktivität.

Mittels Durchführung periodischer Messungen erhält man ein durchgehendes Zählen des Zustands der Last des kontrollierten Links. Die Periode der Messungen wäre typischerweise unterschiedlich für die zwei Werte des fairen Durchsatzes (zum Beispiel in der Größenordnung von etwa hundert Millisekunden) und der prioritären Last (zum Beispiel in der Größenordnung von etwa zehn Millisekunden).

Die von der Zugangskontrolle verwendeten Schätzungen können zum Beispiel exponential geglättete Durchschnittswerte der Messungen pro Zyklus sein (d.h. Schätzfunktion ← &agr; × Schätzfunktion + (1 – &agr;) × neue Messung, für 0 < &agr; < 1).

Ein Ausführungsbeispiel des Zeitablaufsteuerungsmoduls 28 wird nun genauer beschrieben.

Vorzugsweise wird eine Zeitablaufsteuerung vom Typ faires Einreihen ("fair queuing" in der englischen Terminologie) angewendet.

Eine solche Zeitablaufsteuerung, SFQ genannt, ist zum Beispiel in dem Artikel von P. Gayal et al. "Start-time Fair Queuing: A scheduling algorithm for integrated services packet switching network", IEEE/ACM Trans. Networking, Vol 5, Nr. 5, S. 690–704, 1997 beschrieben.

Dieser Typ von Zeitablaufsteuerung ermöglicht es, auf faire Weise die Bandbreite eines Links zwischen den laufenden Flüsse zu teilen, indem man sich vom kooperativen Verhalten der Benutzer befreit. In Zuordnung zur Zugangskontrolle ermöglicht er außerdem, den zugelassenen Flüssen eine Durchsatzgarantie anzubieten.

Die Probleme der Erweiterbarkeit, die zum "fair queuing" pro Fluss gehören, werden in der vorliegenden Architektur vermieden, indem der Zustand eines Flusses nur während der Zeit aufrecht erhalten wird, in der er aktiv ist, und indem beobachtet wird, dass die Anzahl solcher Flüsse notwendigerweise von der Zugangskontrolle begrenzt wird.

Die Priorität wird den Paketen verliehen, die ankommen, wenn der Fluss nicht "aktiv" ist in dem Sinn, dass er nicht in einer Liste von Flüssen inventarisiert ist. Das bedeutet, dass er noch keine Pakete in der Warteschlange hat und seit einem gewissen Zeitintervall (das durch die laufenden Parameter des Algorithmus zum fairen Einreihen SFQ bestimmt wird) keine gehabt hat. Im Prinzip ist ein Fluss, dessen Spitzendurchsatz den fairen Durchsatz nicht überschreitet, bei der Ankunft der Pakete von diesem Fluss nicht aktiv.

Diese Anpassung, gekoppelt mit der Zugangskontrolle, ermöglicht es also, eine vernachlässigbare Veränderung der Echtzeitflüsse zu gewährleisten, deren Durchsatz einen bestimmten Schwellwert nicht überschreitet.

Da man in dieser Architektur die Echtzeitflüsse und die Datenflüsse nicht unterscheidet, gibt die Zeitablaufsteuerungsvorrichtung die Priorität ebenfalls bestimmten Paketen der Datenflüsse (alle Pakete eines Flusses, deren Durchsatz unter dem fairen Durchsatz bleibt, zum Beispiel).

Diese Mehrdeutigkeit ist problemlos, so lange die Zugangskontrolle eine vernachlässigbare Laufzeit für die prioritären Pakete gewährleistet.

Um den Betrieb der Zeitablaufsteuerungsvorrichtung darzustellen, wird das Beispiel eines Routers angegeben, bei dem die Warteschlange nur am Ausgang gebildet wird (englisch: Router mit "output queuing").

Es wird ein Warteschlangensystem vom Typ "PIFO" (Abkürzung des englischen Ausdrucks "push in, first out") verwendet, das ein Paket in einer beliebigen Stellung zulässt, die durch den Wert eines Zeitstempels bestimmt wird. Die Schlange leert sich immer über ihren Kopf, das am Kopf der Schlange befindliche Paket wird gesendet.

Gemäß diesem Beispiel verwendet die Vorrichtung die folgenden Daten oder die folgenden Elemente:

  • – eine Schlange "push in, first out" (PIFO), in der die Pakete in zunehmender Ordnung eines Zeitstempels gespeichert sind; die Elemente des PIFO sind Einheiten {packet, time_stamp}, wobei packet die Informationen bezüglich des Pakets bezeichnet (Flussidentifikator, Größe, Speicheradresse) und time_stamp der Zeitstempel ist (bestimmt gemäß dem Algorithmus SFQ, der weiter unten beschrieben wird),
  • – einen Zeiger P, der das letzte der prioritären Pakete am Kopf der PIFO identifiziert; wenn die Schlange kein prioritäres Paket enthält, P = Null,
  • – eine Liste von Flüssen flow_list, die den Identifikator der aktiven Flüsse sowie einen Fluss-Zeitstempel flow_time_stamp enthält, der dem Wert von time-stamp des letzten Pakets, erhöht um seine Länge, entspricht (es handelt sich um das "finish tag" des Pakets in SFQ),
  • - ein virtueller Zeitzähler virtual_time, der die Berechnung der Zeitstempel erlaubt.

Im Beispiel des bereits oben erwähnten Algorithmus SFQ ist die virtuelle Zeit gleich dem Zeitstempel ("start tag") des letzten Pakets, das sein Senden begonnen hat.

Die Stau-Schätzfunktionen verwenden die folgenden Daten:

  • – die aktuelle Zeit (local_time) gemäß dem lokalen Taktgeber,
  • – die Anzahl von Bytes prioritärer Pakete, die während des laufenden Messintervalls übertragen werden, priority_bytes,
  • – eine logische Variable, die anzeigt, ob die Warteschlange leer ist, silence_flag,
  • – die kumulierte Dauer der Pausenintervalle, silence_time,
  • – die Startzeit des laufenden Pausenintervalls, silence_start.

4 zeigt schematisch eine Warteschlange 50 vom Typ PIFO. Ein Paket 52 wird in Abhängigkeit von seinem Zeitstempel in sie eingefügt. Ein prioritäres Paket 56 soll in die Kopf-Pakete eingefügt werden, während das Paket 54 das nächste zu sendende Paket ist. Das Paket 56 wird als letztes der prioritären Pakete eingefügt:

Es ist dieses Paket, auf das der Zeiger P nach seiner Einfügung in die Schlange zeigen wird. Es ist anzumerken, dass alle prioritären Pakete den gleichen Zeitstempel gleich dem laufenden Wert der virtual_time erben werden.

Um die prioritäre Last zu schätzen, empfiehlt es sich, bei jeder Einfügung eines prioritären Pakets in die PIFO-Schlange einen Byte-Zähler priority_bytes zu aktualisieren. Dieser Zähler wird dann um den Wert L inkrementiert, der die Byte-Größe des Pakets darstellt. Durch Abtasten dieses Zählers in regelmäßigen Intervallen leitet man eine Schätzung der prioritären Last als die Differenz im Wert priority_bytes zu Beginn und am Ende des Messintervalls dividiert durch seine Dauer ab. Es sei PB(T) der Wert von priority_bytes im Zeitpunkt T, (T1, T2) ein Messintervall (in Sekunden), C der Durchsatz des Links (in Bits/Sekunde). Dann ist eine Schätzfunktion der prioritären Last für das Intervall: Prioritäre Last = (PB(T2) – PB(T1))·8/(T2 – T1)/C.

Um den fairen Durchsatz zu schätzen, sind mehrere Vorgehensweisen möglich, da nach Ben Fredj et al. im bereits erwähnten Artikel diese Messung nicht mit einer sehr großen Präzision ausgewertet werden muss. Ein mögliches Verfahren wäre es, die Anzahl von aktiven Flüssen zu zählen (die Anzahl von Flüssen in der Liste flow_list) und als Messwert des fairen Durchsatzes den Durchsatz des Links dividiert durch diese Anzahl zu nehmen. In den weiter unten beschriebenen Algorithmen verwendet man eine andere Vorgehensweise, die auf dem oben erwähnten Begriff eines fiktiven Flusses basiert.

Es wird angenommen, dass der fiktive Fluss Pakete der Länge 1 Byte sendet, die sich zwischen die realen Pakete in einer vom Algorithmus SFQ diktierten Reihenfolge einfügen. In einer Periode, in der die Schlange immer besetzt ist, leitet sich die Anzahl von Bytes, die der fiktive Fluss hätte senden können, von der Entwicklung des virtuellen Zeitzählers virtual_time ab. Wenn die Schlange leer ist, hätte der fiktive Fluss mit dem Durchsatz des Links senden können. Indem man die Folge von Besetzungs- und von Pausenperioden vereinigt, leitet man die folgende Schätzfunktion ab. Es sei VT(T) der Wert der virtual_time im Zeitpunkt T, (T1, 12) ein Messintervall und S die Gesamtpausendauer während dieses Intervalls. Dann ist die gewählte Schätzfunktion: fairer Durchsatz = max(S·C/(T2 – T1), (VT(T2) – VT(T1))·8/(T2 – T1)).

Der erste Term ist typischerweise maßgeblich, wenn die Last des Links gering ist, da der fiktive Fluss die ganze Kapazität des Links genutzt hätte, die verfügbar bleibt. Der zweite Term ist in der Besetzungsperiode maßgeblich und misst in etwa den Durchsatz, der von einem realen Fluss realisiert wird, der immer mindestens ein Paket in der Schlange hat.

Die Operationen des Algorithmus werden entweder bei Ankunft eines Pakets oder am Ende einer Paketaussendung ausgeführt, wie in den 5 und 6 dargestellt. In diesen Figuren beziehen sich die gestrichelt umrahmten Operationen auf die Staumessungen und werden weiter unten kommentiert.

In 5 entspricht der Anfang des Algorithmus dem Schritt der Ankunft eines Pakets (Schritt 100).

Es wird zunächst festgestellt (Schritt 102), ob die PIFO-Schlange überlastet ist oder nicht.

Wenn sie es ist, wird die Wahl des ggf. zurückzuweisenden Pakets durchgeführt (Schritt 104).

Das Paket kann zurückgewiesen werden (Schritte 106 und 108) oder nicht, in welchem Fall (ein Paket eines anderen Flusses wird dann zurückgewiesen) zum Test des Schritts 110 übergangen wird, ebenso wie wenn die Antwort auf den Schritt 102 negativ ist.

Schritt 110 ist ein Test der Zugehörigkeit des Identifikators des Paket zur Liste der Flüsse.

Wenn der Fluss-Identifikator des Pakets nicht zur Liste der Flüsse gehört, heißt dies, dass der Fluss, zu dem dieses Paket gehört, nicht aktiv ist. Dieser Typ von Paket erhält eine Priorität in dem Fall, in dem die Liste der Flüsse (flow_list) nicht gesättigt ist. wenn letztere es ist (Schritt 120), wird die Zurückweisung des Pakets durchgeführt (Schritt 108). Ansonsten wird die Liste (flow_list) aktualisiert, indem der Identifikator des neuen Flusses hinzugefügt wird, mit einem Fluss-Zeitstempel flow_time_stamp gleich virtual_time erhöht um die Länge des Pakets L (Schritt 124). Das Paket wird in die PIFO-Schlange an der durch den Zeiger P angezeigten Stelle eingefügt, und der Wert dieses letzteren wird aktualisiert (Schritt 124).

Wenn der Fluss bereits zur Liste der aktiven Flüsse gehört (positive Antwort im Schritt 110), wird das Paket in die PIFO-Schlange mit einem Zeitstempel gleich dem laufenden Wert von flow_time_stamp eingefügt (Schritt 122). Dieser Wert in flow_list wird dann durch die Länge L des Pakets inkrementiert.

Der Algorithmus ist dann beendet (Schritt 134). Die Ankunft eines neuen Pakets löst wieder den gleichen Algorithmus aus. Das Zugangsende eines Pakets löst den folgenden Algorithmus aus (6).

Die gestrichelt umrahmten Operationen ermöglichen die durchgehende Messung der Stauparameter fairer Durchsatz und prioritäre Last. Wenn die PIFO-Schlange leer ist (Schritt 210), beobachtet man das Ende einer Pausenperiode. Der Pausendauerzähler silence_time wird aktualisiert, und der logische Anzeiger silence_flag wird auf den Wert FALSCH gesetzt (Schritt 212). Wenn ein neuer Fluss zur Liste flow_list hinzugefügt wird, wird außerdem der Wert von priority_bytes durch die Länge des fraglichen Pakets inkrementiert (Schritt 204).

Der Algorithmus der 6 wird durch ein anderes Ereignis ausgelöst, nämlich das Ende der Sendung eines Pakets (Schritt 150).

In einem ersten Schritt (Schritt 154) wird festgestellt, ob die PIFO-Schlange leer ist oder nicht.

Wenn ja, werden alle noch aktiven Flüsse aus der Liste flow_list gestrichen (Schritt 156). Der Zeiger P wird zurückgesetzt.

Ansonsten wird das Senden des nächsten Pakets ausgeführt, indem der Wert seines Zeitstempels next_time_stamp notiert wird (Schritt 160). Wenn next_time_stamp nicht höher ist als virtual_time (diese Variablen haben also gleiche Werte), ist der Algorithmus beendet. Im gegenteiligen Fall müssen virtual_time geändert und aus flow_list die inaktiv gewordenen Flüsse gestrichen werden, da ihr flow_time_stamp unter virtual_time liegt (Schritt 164). Der Algorithmus ist dann beendet.

Die mit den Staumessungen verbundenen Operationen sind gestrichelt umrahmt. Wenn die Schlange sich leert, wird der Indikator silence_flag auf den Wert RICHTIG gesetzt, die Epoche des Beginns der Pausenperiode wird gespeichert (Schritt 220).

Die Ankunft eines neuen Pakets löst den vorhergehenden Algorithmus aus (5), das Ende des Sendens eines Pakets löst erneut den Algorithmus der 6 aus.

Die 7 und 8 zeigen die Operationen, die beim Abtasten der Stauzähler durchgeführt werden.

Die Operationen der 7 werden alle time_interval_CP Sekunden (gemäß dem lokalen Taktgeber) ausgeführt. Man berechnet die prioritäre Last (Schritt 232) und speichert den laufenden Wert des Zählers priority_bytes für die nächste Ausführung als die variable priority_bytes_old.

Die Operationen der 8 werden alle time_interval_DE Sekunden (gemäß dem lokalen Taktgeber) ausgeführt. Die Berechnungen unterscheiden sich, je nachdem, ob das Link eine Pause hat (Warteschlange leer) oder nicht. Wenn ja, wird die Pause für die Bedürfnisse der Berechnungen unterbrochen (Schritt 248). In allen Fällen erhält man eine Schätzung rate_1 des fairen Durchsatzes entsprechend dem verfügbaren Durchsatz während des Messintervalls (Schritt 246 oder 248). Man berechnet dann die zweite Durchsatz-Schätzfunktion rate_2 gemäß der Formel des Schritts 250. Der faire Durchsatz ist die größere der zwei Schätzfunktionen rate_1 und rate_2 (Schritte 254, 256 und 258). Schließlich werden die aktuellen Werte von silence_time und virtual_time für das nächste Intervall gespeichert (Schritt 252).

Eine andere Anwendung berechnet gleitende Mittelwerte ausgehend von den Werten, die am Ende jeder Messperiode exportiert werden. Die Wahl der Glättungsgewichte und der Länge der Messintervalle muss abhängig von den Parametern des Systems und des Verkehrs optimiert werden. Diese Anwendung liefert die Schätzfunktionen fairer Durchsatz und prioritäre Last und leitet den Wert der Funktion Admit ab, die bereits weiter oben erwähnt wurde.

Die Wahl des zurückzuweisenden Pakets im Schritt 104 der 5 erfolgt durch Gewährleistung der Fairness der Durchsatzteilung zwischen den aktiven Flüssen. Diese wird gewährleistet, indem für die Zurückweisung ein Paket des Flusses gewählt wird, dessen Gesamtanzahl an wartenden Bytes die größte ist. Zurückweisungsbedingungen sowie ein Mechanismus der Auswahl des zurückzuweisenden Pakets werden zum Beispiel in dem Artikel von B. Suter et al. "Buffer Management schemes for supporting TCP in Gigabit Routers with Per-Flow Queuing", IEEE J. in Selected Areas in Communications, August 1999, offenbart. Es sei schließlich angemerkt, dass die Paketzurückweisung in manchen Fällen durch eine einfache Markierung mit der Verwendung des ECN-Bits ("explicit congestion notification") des IP-Vorspanns ersetzt werden kann.

Das erfindungsgemäße Verfahren ist erweiterbar: Es funktioniert unabhängig von den Lastbedingungen, zum Beispiel auf einem Link mit 1Mbit/s oder mit 10Mbit/s oder mit 1Gbit/s oder mehr.

Die Komplexität des Zeitablaufsteuerungsmechanismus, und insbesondere des SFQ, ist linear in der Anzahl von aktiven Flüssen. Die Erweiterbarkeit wird durch die Tatsache gewährleistet, dass diese Anzahl durch die Zugangskontrolle begrenzt wird und relativ gering bleibt, unabhängig vom Durchsatz des Links C.

Um diese Anzahl zu schätzen, wird zunächst angenommen, dass die Zugangskontrolle perfekt funktioniert und gewährleistet, dass der faire Durchsatz nie unter einen Zielwert &THgr; sinkt. Die Anzahl von Flüssen, deren Durchsatz &THgr; überschreiten könnte (da nicht begrenzt durch andere Elemente auf ihrem Pfad) ist gezwungenermaßen niedriger als oder gleich C/&THgr;: Man wählt &THgr; so, dass die Wahrscheinlichkeit, mehr als C/&THgr; aktive Flüsse zu haben, sehr gering ist, so lange die Last einen bestimmten Grenzwert nicht überschreitet. Für einen Last-Grenzwert von 90%, nach der Analyse von Ben Fredj et al. ("Statistical Bandwidth Sharing: a study of congestion at flow levels" Proc. of ACM SIGCOMM 2001), ist die Wahrscheinlichkeit, dass die Anzahl von Flüssen 100 überschreitet, geringer als 1/10000. Man kann also &THgr; = C/100 festlegen, so dass die Anzahl von aktiven Flüssen immer niedriger ist als 100, und die Wahrscheinlichkeit der Blockierung ist niedriger als 10–4, wenn die Last 90% nicht überschreitet.

Eine große Anzahl anderer Flüsse mit einem Durchsatz von weniger als &THgr; können im Gang sein. Jedoch hat zu jedem Zeitpunkt nur eine kleine Anzahl dieser Flüsse ein Paket in der Warteschlange. Es sei zur Vereinfachung angenommen, dass die Pakete aller Flüsse die gleiche Länge haben. Diese Flüsse haben immer nur ein einziges Paket in der Warteschlange (da ihr Durchsatz unter dem fairen Durchsatz liegt). Wenn die Flüsse unabhängig sind, verhält die Anzahl von Paketen in der prioritären Schlange sich dann wie eine Warteschlange M/D/1. In gleicher Weise ist die Anzahl von aktiven Flüssen (die in der Liste der Flüsse des Algorithmus zum fairen Einreihen inventarisiert sind) gleich der Anzahl von Kunden, die an einer Besetzungsperiode der gleichen Warteschlange teilnehmen. Letztere ist mit großer Wahrscheinlichkeit geringer als 100, so lange die Last 90% nicht überschreitet.

Die Wirkung der variablen Größe der Pakete und des im Netz stromaufwärts erworbenen Jitters ändern nicht die Tatsache, dass die Anzahl von zu berücksichtigenden Flüssen unter normalen Lastbedingungen geringer als einige hundert bleibt (200, wenn man die obigen Grenzwerte summiert). Bei einer Überlast hat die Zugangskontrolle genau die Aufgabe, die Anzahl von laufenden Flüssen zu begrenzen. Die Kontrolle des fairen Durchsatzes begrenzt natürlich die Anzahl von aktiven Flüssen. Die Kontrolle der prioritären Last gewährleistet, dass die lokale Last aufgrund der Flüsse mit geringerem Durchsatz als der faire Durchsatz mit großer Wahrscheinlichkeit unter dem festgelegten Grenzwert bleibt (zum Beispiel 90%).

Der optimale Wert der maximalen Anzahl von Flüssen unter Berücksichtigung der Ungenauigkeit der Algorithmen der Zugangskontrolle kann bestimmt werden durch Ausprobieren der nachfolgend beschriebenen Algorithmen.

Wenn die Vorrichtung ohne Zugangskontrolle verwendet wird, ist die Anzahl von zu berücksichtigenden Flüssen nicht begrenzt. Diese Tatsache könnte im Rahmen eines Zugriffsnetzes nicht störend sein, in dem die Anzahl von bedienten Benutzern selbst begrenzt ist.

Eine Unterscheidung könnte wünschenswert sein, um Dienstklassen auf der Ebene der Zugangskontrolle zu unterscheiden. Es ist nämlich möglich, bestimmte Klassen von Flüsse auf einer bestimmten Stauebene zurückzuweisen, um Kapazität für andere Flüsse einer prioritäreren Dienstklasse aufrechtzuerhalten. Die Priorität könnte zum Beispiel vom Wert verschiedener Felder des Vorspanns des Pakets abhängen, darunter die Verkehrsklasse von IPv6 oder die Felder ToS von IPv4 oder die IP-Adressen.

Man nimmt also an, dass es eine Einheit von logischen Funktionen Admit-i (fairer Durchsatz, prioritäre Last), i = 1, ..., m für m Dienstklassen gibt. Die Klasse i ist prioritär bezüglich der Klasse j, wenn gilt i < j. Die Funktionen sind derart, dass für die gleichen Argumente gilt Admit_1 ≥ Admit_2 ≥ ... ≥ Admit_m. Die Zugangspolitik ist dann, die Flüsse der Klasse mit dem Index i zurückzuweisen, wenn gilt Admit_i gleich 0, und sie zuzulassen, wenn gilt Admit_i gleich 1.

Admit_1 wird wie die Funktion Admit in der einfachen Politik ohne Klassen gewählt, um die Transparenz der Flüsse mit einem Spitzendurchsatz geringer als die jeweiligen Ziel-Durchsätze aufrechtzuerhalten. Die anderen Funktionen Admit_1 für i = 2, ..., m ermöglichen es, die Zugänglichkeit der prioritären Klassen zu privilegieren.

Die Begrenzungen des Spitzendurchsatzes sind nicht "hart" insofern als die Benutzer sie problemlos überschreiten können, wenn die Verkehrsbedingungen es erlauben. Es handelt sich um eine Hypothese, die die Dimensionierung und die Erstellung von präzisen Zugangsbedingungen erlaubt. Die vom Betreiber angezeigten Garantien ermöglichen es den Benutzern, eine nicht-adaptive Codierung für die Echtzeitdienste zu verwenden, so lange ihr Spitzendurchsatz unter dem festgelegen Grenzwert liegt. Der Durchsatz der Datentransfers wird nur durch das Netz begrenzt, wenn die äußeren Grenzen (Zugriffsnetz, Kapazität des Servers, ...) über dem Ziel-Spitzendurchsatz liegen.

Die erfindungsgemäße Architektur ist nicht empfindlicher für irrationale oder böswillige Verhaltensweisen von Seiten der Benutzer als die bekannten Architekturen des Stands der Technik. Für eine optimale Leistung ist aber eine geeignete Interpretation der aus dem Paketverlust bestehenden impliziten Signale durch die Anwendungen vorteilhaft.

Der Verlust der ersten Pakete eines neuen Flusses sollte als die Zurückweisung dieses letzteren interpretiert werden. Die darunter liegende Anwendung könnte weiter Pakete senden, bis eines von ihnen akzeptiert und der Fluss in die Liste der geschützten Flüsse eingetragen wird. Diese erneuten Sendungen sind nicht schädlicher als die Erneuerung von verlorenen Paketen durch TCP. Die oben erwähnte Möglichkeit des adaptiven Routens ermöglicht eine intelligentere Reaktion. Wenn die ersten Pakete verloren gehen, ermöglicht die Änderung des Identifikators des Flusses in den folgenden Paketen, einen anderen Pfad zu testen.

Die Echtzeitanwendungen können Testpakete senden, um die Verfügbarkeit eines Pfads abzuschätzen. Die Quittierung eines Testpakets ist eine gute Anzeige dafür, dass der Fluss akzeptiert und in die Liste der geschützten Flüsse eingetragen wird. Es werden keine anderen spezifischen Mechanismen der Verarbeitung der Testpakete benötigt.

Bei den meisten Kommunikationen werden zwei Flüsse aufgebaut, einer in jeder Richtung. Es könnte vorteilhaft sein, wenn die Benutzer die Regelung annehmen, gemäß der der freie Bereich des Identifikators (der flow Label in IPv6 oder die Port-Nummern in IPv4) in beiden Richtungen der gleiche ist. Dies würde es den Benutzern ermöglichen, die Quittierungen eines bestimmten Flusses zu erkennen, insbesondere im Fall eines Routing durch Überflutung:

Der Benutzer sendet mehrere Pakete mit unterschiedlichen Identifikatoren, wodurch mehrere Pfade getestet werden können; die Kommunikation wird in dem Fluss fortgesetzt, der zuerst quittiert wird.

Die Architektur führt keine neuen Gelegenheiten für einen Angriff vom Typ "DoS" ("denial of service") ein. Es können zwei Verhaltensweisen in Betracht gezogen werden:

  • – Ein Benutzer wechselt mit jedem Paket den Fluss-Identifikator: Dies könnte eine Liste von geschützten Flüssen schnell sättigen; die Konsequenz wäre der fehlende Schutz bestimmter Flüsse, aber diese würden nur im Fall einer gleichzeitigen Überlastung des angegriffenen Links darunter leiden; das Einschreiben eines Flusses in die Liste 30 mit nur einer geringen Wahrscheinlichkeit p reduziert die Wirkung eines solchen Angriffs.
  • – Ein Benutzer behält den gleichen Identifikator für mehrere Flüsse bei: Die aufeinander folgenden Flüsse unterliegen so lange nicht der Zugangskontrolle, wie das Intervall zwischen zwei Paketen unter der Verzögerung bleibt, die parallel gesendeten Flüsse können keinen stärkeren globalen Durchsatz realisieren als der laufende Wert des fairen Durchsatzes; in beiden Fällen ist die für die anderen Benutzer erzeugte Behinderung minimal.

Schließlich ist es für einen Benutzer selbstverständlich möglich, mehrere Flüsse für die Beförderung der gleichen Anwendung aufzubauen. Er könnte dann einen stärkeren Durchsatz erhalten, unter der Bedingung, dass sein Spitzendurchsatz es erlaubt.

Um den Lastausgleich auf Pfaden bei gleichen Kosten zu realisieren, wenden die meisten aktuellen Router eine Hash-Funktion an den IP-Adressen der Quelle und/oder des Ziels an, um die Ausgangsschnittstelle für ein gegebenes Paket zu wählen. Alle Pakete des gleichen Flusses folgen so dem gleichen Pfad. Man kann das Argument der Hash-Funktion ausweiten, um ebenfalls den freien Bereich des Fluss-Identifikators zu umfassen (d.h. der flow label in IPv6 oder die Port-Nummern in IPv4). So hängt die Routenwahl von einem vom Benutzer festgelegten Wert ab. Bei einem Scheitern auf einer Route ist der Benutzer frei, den Identifikator zu ändern und erneut zu versuchen. Nach einem oder mehreren Versuchen könnte er eine Route mit ausreichender Kapazität finden. Er könnte sogar mehrere Flüsse gleichzeitig initiieren und die Kommunikation nur auf einem von ihnen fortsetzen – demjenigen, für den man zuerst eine Quittierung bekommt, zum Beispiel.

Die Netzelemente, die die erfindungsgemäße Architektur anwenden, können die Flüsse zum Beispiel durch eine Funktion (vom Typ "Hash") der Adressenattribute identifizieren. Vorzugsweise ermöglicht die Wahl dieser Funktion einen Kompromiss zwischen der Komplexität der Anwendung und der Verwechslungswahrscheinlichkeit zwischen zwei Flüssen, für die die Funktion den gleichen Wert zurücksendet. Die Wirkungen einer solchen Verwechslung sind begrenzt: Mögliches vermeiden einer Blockierung durch die Zugangskontrolle, Reduktion des Durchsatzes, der den Flüssen durch das fair queuing zugeteilt wird.

Erfindungsgemäß wird ein Lastverbundmechanismus verwendet, um eine adaptive Weiterleitung ausgehend von der Kennung der Flüsse durchzuführen. Die Zugangskontrolle weist nämlich die Flüsse zurück, die ankommen, wenn das Link überlastet ist, indem sie das erste empfangene Paket zurückweist. Der entsprechende Verkehr ist deswegen aber nicht verloren, wenn der Benutzer seinen Versuch wiederholt, indem er das gleiche Paket bis zum Erfolg wieder sendet. Die Erfolgswahrscheinlichkeit ist größer, wenn bei jedem Versuch das Paket einem anderen Link präsentiert wird, das in der Lage ist, es zu seinem Ziel weiterzuleiten. Dies ist durchführbar, wenn der vom Router verwendete Lastverbundmechanismus auf den Flussidentifikator einwirkt, und wenn dieser ein Feld aufweist, das frei vom Benutzer ausgefüllt wird (zum Beispiel eine Port-Nummer in IPv4, das "flow label" in IPv6). Die "Hash"-Funktion, die den Lastverbund herstellt, enthält als Argument dieses freie Feld, so dass der Benutzer eine Art von adaptivem Routen ausführt, indem er den Wert des fraglichen Felds bei jeder Wiederholung ändert.


Anspruch[de]
Vorrichtung zur Verarbeitung von Paketen (20) von Flüssen auf einem Netz-Link, die es ermöglicht, eine Dienstqualität zu gewährleisten, ohne explizit zwischen Echtzeitflüssen und Datenflüssen zu unterscheiden, und die Zeitablaufssteuerungsmittel (28) aufweist, um die Pakete in einer Warteschlange (50) gemäß einem Algorithmus zum fairen Einreihen mit Priorität anzuordnen, wobei die Vorrichtung dadurch gekennzeichnet ist, dass den Paketen derjenigen Flüsse eine Priorität zugeteilt wird, deren Durchsatz unter einem dynamischen Schwellwert liegt, wobei der Schwellwert von Verkehrsbedingungen bestimmt wird. Vorrichtung nach Anspruch 1, die weiter Zugangskontrollmittel (24) aufweist, um den Zugang der Pakete in die Vorrichtung gemäß so genannten Zugangskriterien zu kontrollieren. Vorrichtung nach Anspruch 2, wobei die Zeitablaufssteuerungsmittel (28) an die Zugangskontrollmittel (24) Daten (36) von Zulässigkeitsbedingungen senden. Vorrichtung nach einem der Ansprüche 2 oder 3, wobei die Zugangskontrollmittel Mittel aufweisen, um für jedes eingehende Paket (20) eine Liste (30) von so genannten geschützten Flüssen abzufragen. Vorrichtung nach Anspruch 4, die ebenfalls Mittel aufweist, um Flüsse aus der Liste (30) der geschützten Flüsse zu entfernen, bei denen die seit dem letzten empfangenen Paket vergangene Zeit einen Schwellwert übersteigt. Vorrichtung nach Anspruch 4 oder 5, wobei die Zugangskontrollmittel (24) Mittel aufweisen, um, wenn ein Paket zu einem Fluss gehört, der sich nicht in der Liste der geschützten Flüsse befindet, zu bestimmen, ob die Zugangskriterien erfüllt sind. Vorrichtung nach einem der Ansprüche 4 bis 6, die Mittel aufweist, um einen neuen Fluss in die Liste (30) einzuschreiben, wenn die Zugangskriterien erfüllt sind. Vorrichtung nach einem der Ansprüche 3 bis 7, wobei die Daten (36) von Zulässigkeitsbedingungen aufweisen:

– einen Durchsatzwert, fairer Wert genannt, der ein Maß des Durchsatzes ist, den ein Datenfluss herstellen würde, der immer zu sendende Pakete hätte,

– einen prioritären Lastwert, der die Summe der Länge der in einem bestimmten Zeitintervall übertragenen prioritären Pakete dividiert durch die Dauer dieses Zeitintervalls ist.
Vorrichtung nach einem der Ansprüche 1 bis 8, wobei die Zeitablaufssteuerungsmittel die Pakete der Flüsse als prioritär in der Warteschlange (50) einordnen, die nicht in eine Liste der aktiven Flüsse eingetragen sind, und als nicht-prioritär die Pakete der Flüsse, die bereits in diese Liste eingetragen sind. Vorrichtung nach einem der Ansprüche 1 bis 9, wobei die Zeitablaufssteuerungsmittel (28) die Pakete in einer Warteschlange (50) vom Typ PIFO einordnen. Vorrichtung nach Anspruch 10, wobei ein Zeiger P das letzte der prioritären Pakete am Kopf der Schlange (50) identifiziert. Vorrichtung nach Anspruch 11, die weiter eine Liste von aktiven Flüssen anwendet, die die Kennung von so genannten aktiven Flüssen enthält, wobei ein Zeitstempel die Zeitablaufssteuerung der Pakete ermöglicht. Vorrichtung nach Anspruch 11, die weiter Mittel aufweist, um die Flüsse in die Liste der aktiven Flüsse einzutragen und aus ihr zu löschen in Abhängigkeit von der Ankunft und dem Abgang der Pakete der verschiedenen Flüsse. Vorrichtung nach Anspruch 12 oder 13, die weiter Staumessmittel aufweist. Vorrichtung nach Anspruch 14, wobei die Staumessungen in Abhängigkeit von einem aktuellen Zeitdatenwert, einer Anzahl von Bytes von prioritären Paketen, die während eines laufenden Messintervalls übertragen werden, und einer Anzahl von Bytes durchgeführt werden, die ein fiktiver Fluss in dem laufenden Messintervall hätten senden können. Vorrichtung nach einem der Ansprüche 10 bis 15, die Mittel aufweist, um zu bestimmen, ob die PIFO-Schlange (50) leer ist oder nicht. Vorrichtung nach einem der vorhergehenden Ansprüche, die außerdem Unterscheidungsmittel aufweist, um in Höhe der Zugangskontrolle Dienstklassen zu unterscheiden. Vorrichtung nach einem der vorhergehenden Ansprüche, bei der die Flüsse durch eine Funktion vom Typ "Hash" von Adressenattributen identifiziert werden. Verfahren zur Verarbeitung von Paketen (20) von Flüssen auf einem Netz-Link, das es ermöglicht, eine Dienstqualität zu gewährleisten, ohne explizit zwischen Echtzeitflüssen und Datenflüssen zu unterscheiden, das einen Schritt der Zeitablaufssteuerung aufweist, um die zugelassenen Pakete in eine Warteschlange (50) gemäß einem Algorithmus zum fairen Einreihen mit Priorität einzuordnen, wobei das Verfahren dadurch gekennzeichnet ist, dass den Paketen derjenigen Flüsse eine Priorität zugeteilt wird, deren Durchsatz unter einem dynamischen Schwellwert liegt, wobei der Schwellwert durch Verkehrsbedingungen bestimmt wird. Verfahren nach Anspruch 19, das weiter einen Zugangskontrollschritt aufweist, um den Zugang der Pakete in eine Verarbeitungsvorrichtung der Pakete (20) gemäß so genannten Zugangskriterien zu kontrollieren. Verfahren nach Anspruch 20, das außerdem das Senden von Daten (36) von Zulässigkeitsbedingungen an die Zugangskontrollmittel (24) aufweist. Verfahren nach Anspruch 21, wobei der Zugangskontrollschritt für jedes eingehende Paket (20) eine Abfrage einer Liste (30) von so genannten geschützten Flüssen aufweist. Verfahren nach Anspruch 22, wobei die Flüsse, bei denen die seit dem letzten empfangenen Paket vergangene Zeit einen Schwellwert überschreitet, von der Liste (30) der geschützten Flüsse gelöscht werden. Verfahren nach Anspruch 22 oder 23, das, wenn ein Paket zu einem Fluss gehört, der nicht in der Liste der geschützten Flüsse enthalten ist, einen Schritt aufweist, um zu bestimmen, ob die Zugangskriterien erfüllt sind. Verfahren nach einem der Ansprüche 22 bis 24, das einen Schritt des Eintragens eines neuen Flusses in die Liste (30) aufweist, wenn die Zugangskriterien erfüllt sind. Verfahren nach einem der Ansprüche 21 bis 25, wobei die Zulässigkeitsbedingungsdaten aufweisen:

– einen Durchsatzwert, fairer Wert genannt, der ein Maß des Durchsatzes ist, den ein Datenfluss ausführen würde, der immer zu sendende Pakete hätte,

– einen prioritären Lastwert, der die Summe der Länge der in einem bestimmten Zeitintervall übertragenen prioritären Pakete dividiert durch die Dauer dieses Zeitintervalls ist.
Verfahren nach einem der Ansprüche 20 bis 26, wobei der Zeitablaufssteuerungsschritt die Pakete der Flüsse als prioritär in der Warteschlange (50) einordnet, die nicht in eine Liste der aktiven Flüsse eingetragen sind, und als nicht-prioritär die Pakete der Flüsse, die bereits in diese Liste eingetragen sind. Verfahren nach einem der Ansprüche 20 bis 26, wobei die Zeitablaufssteuerungsmittel die Pakete in einer Warteschlange (50) vom Typ PIFO einordnen. Verfahren nach Anspruch 28, wobei ein Zeiger P das letzte der prioritären Pakete am Kopf der Schlange identifiziert. Verfahren nach Anspruch 29, das außerdem eine Liste von aktiven Flüssen anwendet, die die Kennung der Flüsse enthält, wobei ein Zeitstempel die Zeitablaufssteuerung der Pakete ermöglicht. Verfahren nach Anspruch 30, das weiter Schritte des Eintragens der Flüsse in und des Löschens der Flüsse aus der Liste der aktiven Flüsse in Abhängigkeit von der Ankunft und dem Abgang der verschiedenen Flüsse aufweist. Verfahren nach Anspruch 30 oder 31, das außerdem eine Staumessung aufweist. Verfahren nach Anspruch 32, wobei die Staumessungen in Abhängigkeit von einem aktuellen Zeitdatenwert, einer Anzahl von Bytes von prioritären Paketen, die während eines laufenden Messintervalls übertragen werden, und einer Anzahl von Bytes durchgeführt werden, die ein fiktiver Fluss in dem laufenden Messintervall hätte senden können. Verfahren nach einem der Ansprüche 28 bis 33, das einen Schritt aufweist, um zu bestimmen, ob die PIFO-Schlange (50) leer ist oder nicht. Verfahren nach einem der Ansprüche 19 bis 34, wobei ein Signal bezüglich des Verlusts von Paketen an einen Benutzer gesendet wird. Verfahren nach einem der Ansprüche 19 bis 34, das weiter eine Unterscheidung zwischen Dienstklassen in Höhe der Zugangskontrolle aufweist. Verfahren nach einem der Ansprüche 19 bis 36, bei dem die Teilung der Flüsse auf mehrere Links mit Hilfe einer Funktion der Adressenattribute erfolgt, die den freien Bereich der Flusskennung einschließt.






IPC
A Täglicher Lebensbedarf
B Arbeitsverfahren; Transportieren
C Chemie; Hüttenwesen
D Textilien; Papier
E Bauwesen; Erdbohren; Bergbau
F Maschinenbau; Beleuchtung; Heizung; Waffen; Sprengen
G Physik
H Elektrotechnik

Anmelder
Datum

Patentrecherche

Patent Zeichnungen (PDF)

Copyright © 2008 Patent-De Alle Rechte vorbehalten. eMail: info@patent-de.com