Derzeit ist die Entwicklung von Technologien für paketbasier- te Netze ein zentrales Betätigungsfeld für Ingenieure aus den Gebieten der Netztechnik, der Vermittlungstechnik und der In- ternet-Technologien.

Dabei steht das Ziel im Vordergrund, möglichst ein paketori- entiertes Netz für beliebige Dienste verwenden zu können.

Traditionell werden über paketorientierte Netze zeitunkriti- sche Datenübertragungen vorgenommen, wie z. B. der Transfer von Dateien oder elektronischer Mail. Sprachübertragung mit Echtzeitanforderungen wird traditionell über Telefonnetze mit Hilfe von der Zeitmultiplextechnik abgewickelt. Man spricht in diesem Zusammenhang häufig auch von TDM (time division multiplexing) Netzen. Mit der Verlegung von Netzen mit hoher Bandbreite bzw. Übertragungskapazität ist neben der Daten- und Sprachübertragung auch die Realisierung von Bild- bezogenen Diensten in den Bereich des Machbaren gerückt.

Übertragung von Videoinformationen in Echtzeit, z. B. im Rah- men von Video-on-demand Diensten oder Videokonferenzen, wird eine wichtige Kategorie von Diensten zukünftiger Netze sein.

Die Entwicklung zielt dahin, möglichst alle Dienste, datenbe- zogene, sprachbezogene und auf Videoinformationen bezogene, über ein paketorientiertes Netz durchführen zu können. Für die verschiedenen Anforderung bei der Datenübertragung im Rahmen der verschiedenen Dienste definiert man üblicherweise Dienstklassen. Die Übertragung mit einer definierten Dienst- qualität (quality of service) vor allem bei Diensten mit Echtzeitanforderungen verlangt eine entsprechende Steuerung bzw. Kontrolle für die Paketübertragung über das Netz. Im

Englischen gibt es eine Reihe von Begriffen die sich auf die Kontrolle bzw. Steuerung des Verkehrs beziehen : traffic mana- gement, traffic conditioning, traffic shaping, traffic engi- neering, policing ect. Verschiedene Vorgehensweisen für eine Kontrolle bzw. Steuerung für den Verkehr eines paketorien- tierten Netzes sind in der einschlägigen Literatur beschrie- ben.

Bei ATM (asynchroneous transfer mode) Netzen wird für jede Datenübertragung auf der gesamten Übertragungsstrecke eine Reservierung vorgenommen. Durch die Reservierung wird das Verkehrsaufkommen beschränkt. Zur Überwachung findet ab- schnittsweise eine Überlastkontrolle statt. Eine eventuelle Verwerfung von Paketen wird nach Maßgabe des CLP-Bits (CLP : Cell loss priority) des Paketheaders vorgenommen.

Das Diff-Serv Konzept wird bei IP (internet protocol) Netzen angewendet und zielt auf eine bessere Dienstqualität für Dienste mit hohen Qualitätsanforderungen durch Einführung von Dienstklassen. Man spricht in diesem Zusammenhang auch häufig von einem CoS (class of service) Modell. Das Diff-Serv Kon- zept ist in den von der IETF veröffentlichten RFCs mit den Nummern 2474 und 2475 beschrieben. Im Rahmen des Diff-Serv Konzepts wird mit Hilfe eines DS (Differentiated Services) Feldes im IP Header der Datenpakete durch Setzen des DSCP (DS codepoint) Parameters eine Priorisierung des Paketverkehrs vorgenommen. Diese Priorisierung erfolgt mit Hilfe einer"per hop"Ressourcenallokation, d. h. die Pakete erfahren bei den Knoten je nach der im DS Feld durch den DSCP Parameter fest- gelegten Dienstklasse (class of service) eine unterschiedli- che Behandlung. Die Kontrolle bzw. Steuerung des Verkehrs wird also nach Maßgabe von den Dienstklassen vorgenommen. Das Diff-Serv Konzept führt zu einer privilegierten Behandlung von dem Verkehr priorisierter Dienstklassen, nicht jedoch zu einer zuverlässigen Kontrolle des Verkehrsvolumens.

Ein anderer Ansatz für im Hinblick auf eine quality of servi- ce Übertragung über IP Netze ist durch das RSVP (resource re- servation protocol) gegeben. Bei diesem Protokoll handelt es sich um ein Reservierungsprotokoll, mit dessen Hilfe eine Bandbreitenreservierung entlang eines Pfades vorgenommen wird. Über diesen Pfad kann dann eine quality of service (QoS) Übertragung stattfinden. Das RSVP Protokoll wird zusam- men mit dem MPLS (multi protocol label switching) Protokol eingesetzt, das virtuelle Pfade über IP Netze ermöglicht. Für eine Garantie der QoS Übertragung wird in der Regel entlang des Pfades das Verkehrsaufkommen kontrolliert und gegebenen- falls beschränkt. Durch die Einführung von Pfaden verliert man jedoch viel von der ursprünglichen Flexibilität von IP Netzen.

Zentral für Garantien von Übertragungsqualitätsparametern ist eine effiziente Kontrolle des Verkehrs. Bei einer Kontrolle des Verkehrsaufkommen im Rahmen von Datenübertragung über pa- ketorientierte Netze ist zudem auf eine hohe Flexibilität und geringe Komplexität bei der Datenübertragung zu achten, wie sie z. B. IP Netze in hohem Maße aufweisen. Diese Flexibilität bzw. geringe Komplexität geht bei der Verwendung des RSVP Protokolls mit einer Ende-zu-Ende Pfadreservierung jedoch zu einem großen Teil wieder verloren. Andere Verfahren wie Diff- Serv führen zu keinen garantierten Dienstklassen.

Die Erfindung hat zur Aufgabe, eine effiziente Verkehrskon- trolle für ein paketorientiertes Netz anzugeben, das die Nachteile herkömmlicher Verfahren vermeidet.

Die Aufgabe wird durch ein Verfahren zur Verkehrsbegrenzung in einem paketorientierten Netz nach Anspruch 1 gelöst.

Im Rahmen des erfindungsgemäßen Verfahren werden für eine Gruppe von über das Netz zu übertragenden Datenpaketen eines Flows zwei Zulässigkeitsprüfungen durchgeführt. Die erste Zu- lässigkeitsprüfung wird mit Hilfe eines Grenzwertes für den

über den Netzeingangsknoten des Flows geleiteten Verkehr und die zweite mit Hilfe eines Grenzwertes für den über den Netz- ausgangsknoten des Flow geleiteten Verkehr durchgeführt. Die Übertragung der Gruppe von Datenpaketen wird nicht zugelas- sen, wenn ein Zulassen der Übertragung zu einem einen der beiden Grenzwerte überschreitenden Verkehrsaufkommen führen würde.

Die beiden Zulässigkeitsprüfungen werden beispielsweise bei dem Netzeingangs-und Netzausgangsknoten des Flows durchge- führt. In diesem Fall wird beispielsweise das Ergebnis bezüg- lich des über den Netzausgangsknoten geleiteten Verkehrs dem Netzeingangsknoten übermittelt, um dort aufgrund der Ergeb- nisse beider Zulässigkeitsprüfungen die Übertragung der Grup- pe von Datenpaketen zu erlauben oder nicht zu erlauben.

Bei dem paketorientiertem Netz kann es sich auch um ein Teil- netz oder Subnetz handeln. In IP (Internet Protocol) Systemen gibt es z. B. Netzarchitekturen, bei denen das Gesamtnetz in "autonome Systeme"bzw."autonomous system"genannte Netze unterteilt ist. Das erfindungsgemäße Netz kann z. B. ein auto- nomes System oder der Teil des Gesamtnetzes im Zuständig- keitsbereich eines Dienstanbieters (z. B. ISP : internet servi- ce provider) sein. Im Falle eines Teilnetzes können über eine Verkehrskontrolle in den Teilnetzen und eine effiziente Kom- munikation zwischen den Teilnetzen Dienstparameter für eine Übertragung über das Gesamtnetz festgelegt werden.

Der Begriff"Flow"wird üblicherweise verwendet, um den Ver- kehr zwischen einer Quelle und einem Ziel zu bezeichnen. Hier bezieht sich Flow auf den Eingangsknoten und den Ausgangskno- ten des paketorientierten Netzes, d. h. alle Pakete eines Flows im Sinne unseres Sprachgebrauchs werden über den selben Eingangsknoten und denselben Ausgangsknoten übertragen. Die Gruppe von Paketen ist beispielsweise einer Verbindung (bei einer TCP/Ip Übertragung definiert durch IP Adresse und Port-

nummer von Ausgangs-und Zielprozess) und/oder einer Dienst- klasse zugeordnet.

Eingangsknoten des paketorientierten Netzes sind Knoten, über die Pakete in das Netz geleitet werden ; Ausgangsknoten sind Knoten des Netzes, über die Pakete das Netz verlassen. In der englischsprachigen Literatur spricht man häufig von ingress nodes und egress nodes. Beispielsweise kann ein Netz gegeben sein, das Randknoten und innere Knoten umfasst. Wenn z. B. über alle Randknoten des Netzes Pakete in das Netz gelangen oder das Netz verlassen können, wären in diesem Falle die Randknoten des Netzes sowohl Netzeingangsknoten sowie Netz- ausgangsknoten.

Ein erfindungsgemäßer Zulässigkeitstest kann durch eine Kon- trollinstanz in einem Knoten oder den Knoten vorgeschalteten Rechnern durchgeführt werden. Eine Kontrollinstanz kann dabei für mehrere Knoten Kontrollfunktionen übernehmen.

Durch die erfindungsgemäße Zulässigkeitsprüfung wird das Ver- kehrsaufkommen innerhalb des Netzes kontrolliert. Bei einer erfindungsgemäßen Behandlung für den gesamten Verkehr, der über das Netz geleitet wird, dass ein Gesamtverkehrsaufkommen erwächst, das zu einer Überlast im Netz und damit zu Verzöge- rungen und Paketverwerfungen führen würde. Bei bekannter Ver- kehrsverteilung im Netz können die Grenzen für die Zulässig- keitsprüfungen so gewählt werden, dass auf keiner Teilstrecke Überlastprobleme auftreten.

Die Beschränkung des Verkehrsaufkommen kann im Sinne einer Übertragung mit ausgehandelten Dienstqualitätsmerkmalen (SLA : service level agreements) vorgenommen werden, z. B. nach Maß- gabe der Priorisierung des Verkehrs.

Für eine Garantie für Dienste mit QoS Datenübertragung ist es wichtig, das gesamte Verkehrsaufkommen innerhalb des Netzes zu kontrollieren. Dieses Ziel kann erreicht werden, indem für

alle Netzeingangsknoten und Netzausgangsknoten Grenzwerte für den über die Knoten geleiteten Verkehr festgesetzt werden.

Die Grenzwerte für den über Eingangs-und Ausgangsknoten ge- leiteten Verkehr können mit Werten für das maximale Ver- kehrsaufkommen auf Teilstrecken (häufig auch Links genannt) in Zusammenhang gesetzt werden. Der maximale Wert für das Verkehrsaufkommen auf Teilstrecken wird sich dabei im Allge- meinen nicht nur nach der Bandbreite, sondern auch nach der verwendeten Netzwerktechnologie richteh. Z. B. wird in der Re- gel zu berücksichtigen sein, ob es sich um ein LAN (Local area Network), ein MAN (Metropolitan Area network), ein WAN (Wide Area network) bzw. ein Backbone-Netzwerk handelt. Ande- re Parameter als die Übertragungskapazität, wie z. B. Verzöge- rungen bei der Übertragung, müssen z. B. für Netze für Echt- zeitanwendungen mitberücksichtigt werden. Beispielsweise ist ein Auslastungsgrad nahe bei 100% für LAN mit CSMA/CD (Car- rier Sense Multiple Access (with) Collision Detection) mit Verzögerungen verbunden, die Echtzeit-Anwendungen in der Re- gel ausschließen. Aus den maximalen Werten für das maximale Verkehrsaufkommen auf Teilstrecken lassen sich dann die Grenzwerte für den über die Eingangs-und Ausgangsknoten ge- leiteten Verkehr festlegen.

Der Zusammenhang zwischen die Grenzwerte für den über die Eingangs-und Ausgangsknoten geleiteten Verkehr und dem Ver- kehrsaufkommen auf Teilstrecken des Netzes basiert in der be- vorzugten Ausgestaltung auf dem für Paare von Netzeingangs- knoten und Netzausgangsknoten anteilsmäßigen Verkehrsaufkom- men über die einzelnen Teilstrecken des Netzes. Die für die Paare von Netzeingangsknoten und Netzausgangsknoten anteils- mäßigen Verkehrsaufkommen über die einzelnen Teilstrecken des Netzes können anhand von Erfahrenswerten oder bekannten Ei- genschaften von Knoten und Links ermittelt werden. Möglich ist auch, das Netz auszumessen, um diese die anteilsmäßigen Verkehrsaufkommen über die einzelnen Teilstrecken in Abhän- gigkeit von Netzeingangsknoten und Netzausgangsknoten zu er-

halten. In der Verkehrstheorie spricht man in diesem Zusam- menhang von der Verkehrsmatrix.

Die Erfindung hat den Vorteil, dass Informationen für die Zu- gangskontrolle nur bei Eingangs-und Ausgangsknoten vorgehal- ten werden müssen. Diese Informationen umfassen für einen Eingangsknoten bzw. Ausgangsknoten z. B. die Grenzwerte und aktuellen Werte für den über den jeweiligen Knoten geleiteten Verkehr. Der Umfang der Informationen ist beschränkt. Die Ak- tualisierung der Information ist wenig aufwändig. Die inneren Knoten brauchen hinsichtlich der Zulässigkeitskontrolle keine Funktionen übernehmen. Das Verfahren ist somit erheblich auf- wandsärmer und hat einen niedrigeren Komplexitätsgrad als Verfahren, die für einzelne Teilstrecken Zulässigkeitskon- trollen vorsehen. Im Gegensatz zu herkömmlichen Verfahren wie ATM oder MPLS braucht innerhalb des Netzes kein Pfad reser- viert zu werden.

ES kann ein Zusammenhang zwischen den Verkehrsaufkommen zwi- schen Paaren von Netzeingangsknoten und Netzausgangsknoten und dem Verkehrsaufkommen auf Teilstrecken des Netzes herge- stellt werden. Mittels der Werte für ein maximales Ver- kehrsaufkommen auf den Teilstrecken des Netzes können Grenzen für das Verkehrsaufkommen zwischen den Paaren von Netzein- gangsknoten und Netzausgangsknoten sowie Grenzwerte für den über die Netzeingangsknoten geleiteten Verkehr und über die Netzausgangsknoten geleiteten Verkehr bestimmt werden.

Der Zusammenhang zwischen den Verkehrsaufkommen zwischen Paa- ren von Netzeingangsknoten und Netzausgangsknoten und dem Verkehrsaufkommen auf Teilstrecken des Netzes kann als Opti- mierungsproblem mit Randbedingungen bzw. Nebenbedingungen in Form von Ungleichungen hergestellt werden. Dabei fließt das anteilsmäßige Verkehrsaufkommen über die einzelnen Teilstre- cken des Netzes zur Formulierung des Zusammenhangs zwischen den Verkehrsaufkommen zwischen Paaren von Netzeingangsknoten

und Netzausgangsknoten und dem Verkehrsaufkommen auf Teil- strecken des Netzes ein.

Diese Formulierung erlaubt zusätzlich, weitere Kriterien in Form von Ungleichungen in die Bestimmung der Grenzen bzw.

Grenzwerte für die Zulässigkeitsprüfungen aufzunehmen. Es können z. B. bei der Bestimmung von Grenzen bzw. Grenzwerten für die Zulässigkeitsprüfungen Bedingungen in Form von Un- gleichungen aufgenommen werden, die ein geringes Verkehrsauf- kommen von hochpriorisierten Verkehr auf Teilstrecken mit größeren Verzögerungszeiten bedingen. Ein anderes Beispiel ist das eines Ausgangsknoten, über den Pakete zu mehreren Eingangsknoten von anderen Netzen übertragen werden können, d. h. der Ausgangsknoten hat Schnittstellen zu mehreren ande- ren Netzen. Wenn Eingangsknoten eines der nachfolgenden Netze ein geringeres Datenvolumen als der Ausgangsknoten bearbeiten kann, kann durch eine weitere Nebenbedingung in Form einer Ungleichung sicher gestellt werden, dass der über den Aus- gangsknoten zu dem Eingangsknoten geleitete Verkehr dessen Kapazität übersteigt.

In einer Variante des erfindungsgemäßen Verfahrens wird zu- sätzlich eine weitere Zulässigkeitsprüfung vorgesehen, wobei die Zulässigkeitsprüfung mit Hilfe eines Grenzwertes für das Verkehrsaufkommen zwischen dem Netzeingangsknoten und dem Netzausgangsknoten des Flows durchgeführt wird. Die Gruppe von Datenpaketen wird zugelassen, wenn alle drei Prüfungen positiv ausfallen. Zu diesem Zweck kommunizieren die Prü- fungsinstanzen miteinander, um mit Hilfe der Ergebnisse der einzelnen Zulässigkeitsprüfungen eine Entscheidung bezüglich der Übertragung der Gruppe von Datenpaketen herbeizuführen.

Entsprechend einer Weiterbindung der Erfindung werden bei Ausfall einer Teilstrecke die Grenzen bzw. Grenzwerte für die Zulässigkeitsprüfung bzw. die Zulässigkeitsprüfungen neu mit der Bedingung festgesetzt werden, dass über die ausgefallene Teilstrecke keine Pakete übertragen werden. Durch die erneute

Festsetzung der Grenzen wird erreicht, dass über andere Links der Verkehr geleitet wird, der sonst über den ausgefallenen Link übertragen worden wäre, ohne dass es zu einer Überlast durch den umgeleiteten Verkehr käme. Es kann so flexibel auf Ausfälle reagiert werden.

Ein vorsorglicher Schutz gegen Linkausfälle kann durch die Wahl der Grenzwerte bzw. Grenzen gewährleistet werden. Dabei werden für eine Mehrzahl von möglichen Störfällen jeweils Grenzen bzw. Grenzwerte bestimmt, bei denen das Verkehrsauf- kommen auch im Störfall in einem zulässiger Rahmen bleibt, d. h. Parameter wie Laufzeitverzögerung und Paketverlustrate in durch die Qualitätsanforderungen für die Datenübertragung definierten Bereichen bleiben. Die Grenzen bzw. Grenzwerte werden dann auf das Minimum der Werte für die untersuchten Störfälle gesetzt. D. h. jeder der Störfälle ist durch die Wahl der Grenzen bzw. Grenzwerte abgefangen. Die Mehrzahl der Störfälle kann z. B. alle Ausfälle von Links umfassen.

Die genannten Zulässigkeitsprüfungen lassen sich auch in Ab- hängigkeit der Dienstklasse durchführen. Es ist beispielswei- se denkbar, eine niedrig priorisierte Dienstklasse zu haben, bei der man Verzögerungen oder den Verwurf von Paketen in Kauf nimmt, wenn die Auslastung des Netzes hoch ist. Dagegen würden für hoch priorisierten Verkehr die Grenzen so gewählt werden, dass Garantien bezüglich Übertragungsqualitätsparame- ter übernommen werden können.

Die Erfindung wird im folgenden anhand einer Figur im Rahmen eines Ausführungsbeispiels näher erläutert.

Die Figur zeigt ein erfindungsgemäßes Netz. Randknoten sind durch gefüllte Kreise, innere Knoten durch nicht gefüllte Kreise gekennzeichnet. Links sind durch Verbindungen zwischen den Knoten dargestellt. Exemplarisch ist ein Eingangsknoten mit I, ein Ausgangsknoten mit E und ein Link mit L bezeich- net. Über den Link L wird ein Teil des Verkehrs zwischen den

Knoten I und E übertragen. Die Zulässigkeitsprüfungen bei dem Eingangsknoten I und bei dem Ausgangsknoten E stellen zusam- men mit den Zulässigkeitsprüfungen bei anderen Randknoten si- cher, dass keine Überlast bei dem Link L auftritt.

Im folgenden werden mathematische Zusammenhänge für das er- findungsgemäße Verfahren dargestellt. In der Praxis werden in der Regel Grenzen bzw. Grenzwerte in Abhängigkeit der maxima- len Linkkapazitäten festgesetzt. Ob der einfacheren mathema- tischen Darstellung wird im folgenden der umgekehrte Fall be- trachtet, d. h. in Abhängigkeit der Grenzen bzw. Grenzwerte die Dimensionierung der Links berechnet. Die Lösung des umge- kehrten Problems kann dann mit numerischen Methoden erfolgen.

Für die folgende detailliertere Darstellung werden folgende Größen eingeführt : c (L) : das Verkehrsaufkommen auf dem Netzabschnitt (Link) L aV (i, j, L) : das anteilsmäßige Verkehrsaufkommen über den Link L des gesamten Verkehrsaufkommens zwischen dem Eingangsknoten i und dem Ausgangsknoten j, Ingress (i) : Der Grenzwert für den Verkehr über den Netzein- gangsknoten i, Egress (j) : Der Grenzwert für den Verkehr über den Ausgangs- knoten j, 5 (i, j) : Das Verkehrsaufkommen zwischen dem Netzeingangsknoten i und dem Netzausgangsknoten j.

Es lassen sich nun folgende Ungleichungen formulieren : Für alle i gilt z b (i, j) < Ingress (i), Summe über alle j. (1) Für alle j gilt 2 b (i, j) < Egress (j), Summe über alle i. (2)

Für alle Links L gilt : c (L)- (i, j) aV (i, j, L), Summe über alle i und j. (3) Mit Hilfe des Simplex-Algorithmus können für vorgegebene Wer- te von Ingress (i) und Egress (j) die maximalen c (L) berechnet werden, die die Ungleichungen (2) bis (4) erfüllen. Anders herum kann für einen Satz Grenzen bzw. Grenzwerte Ingress (i), Egress (j) und BBB (i, j) überprüft werden, ob auf einem Link L eine unzulässig hohe Last auftreten kann. Eine der zu hohen Last entgegenwirkende Änderung der Grenzen bzw. Grenzwerte kann in diesem Fall vorgenommen werden.

Das erfinderische Verfahren lässt auf einfache Weise zu, durch Änderung der Grenzen bzw. Grenzwerte auf Störungen zu reagieren. So kann bei dem Ausfall eines Links L der Zusam- menhang diesen Link ausklammern (z. B. durch Nullsetzen aller aV (i, j, L) für diesen Link L). Durch die neue Formulierung des Zusammenhangs können abgeänderte Grenzen bzw. Grenzwerte er- mittelt werden, die als Zulässigkeitskriterien Überlast in- nerhalb des Netzes verhindern.

Für die Ausgestaltung mit einer zusätzlichen Zulässigkeits- prüfungen Zulässigkeitsprüfung mit Hilfe eines Grenzwertes für das Verkehrsaufkommen zwischen Netzeingangsknoten und Netzausgangsknoten des lässt sich folgender mathematischer Zusammenhang formulieren : Es gelten die obigen Definitionen. Zudem sei BBB (i, j) : die Grenze für das Verkehrsaufkommen zwischen dem Eingangsknoten i und dem Ausgangsknoten j, Für alle 2-Tupel (i, j) gilt 5 (i, j) < BBB (i, j). (4)

Es gilt wieder (3). Die Optimierung erfolgt unter den Bedin- gungen (1), (2) und (4). Neu im Vergleich zu der ersten For- mulierung des Problems sind die Bedingungen (4). Da bei der Formulierung des Problems mit den Bedingungen (4) mehr Bedin- gungen zu erfüllen sind, sind die maximalen Werte für c (L) kleiner oder gleich als bei der Lösung ohne die Bedingungen (4). Die zusätzlichen Bedingungen (4) schränken den Lösung- raum ein und führen bei gleichen Werten für die Ingress (i) und Egress (j) zu kleineren Werten c (L) hinsichtlich der Di- mensionierung der Links L. Bei der Umkehrung des Problems führen folglich bei gleichen vorgegebenen Werten für die ma- ximale Kapazität c (L) der Links L die Bedingungen (4) in der Regel zu größeren Werten für die Ingress (i) und Egress (j).

Man hat daher mehr Flexibilität bei der Festsetzung der Gren- zen, und damit bezüglich der optimalen Auslastung des Netzes.