WO2003065644A2

WO2003065644A2 - Verfahren zur bestimmung der last in einem kommunikationsnetz mittels datenpaket-markierungen

Info

Publication number: WO2003065644A2
Application number: PCT/DE2003/000189
Authority: WO
Inventors: Martin Karsten; Jens Schmitt
Original assignee: TU Darmstadt
Current assignee: TU Darmstadt
Priority date: 2002-02-01
Filing date: 2003-01-24
Publication date: 2003-08-07
Anticipated expiration: 2004-08-01
Also published as: WO2003065644A3; EP1470676B1; DE50301802D1; US20050083951A1; US7426183B2; EP1470676A2; ES2253664T3; ATE311709T1

Abstract

Bei einem Verfahren zur Bestimmung der Last in einem Kommunikationsnetz (1) mit Netzelementen, wie internen Knoten (5, 6, …, 9) und Leitungen (10, 11, 12), und mit Zugangsknoten (2, 3, 4), die aus jeweils einem Eingangsknoten (21, 31, 41) und einem Ausgangsknoten (22, 32, 42) bestehen und von angeschlossenen Endgeräten und/oder anderen Netzen Datenpakete zu- und ableiten, wobei die internen Knoten und Leitungen nach Routing-Algorithmen Pfade bilden und wobei die internen Knoten Datenpakete mit einer lastabhängigen Markierung (M) versehen, ist vorgesehen, dass die Ausgangsknoten die aus dem Kommunikationsnetz eintreffenden Datenpakete und die darin enthaltenen Markierungen nach Pfaden getrennt zählen und daraus jeweils einen Wert für die relative Last entlang des jeweiligen Pfades ableiten und dass die von allen Ausgangsknoten abgeleiteten Werte als Parameter in ein Gleichungssystem eingebracht werden, welches das Kommunikationsnetz mit den internen Knoten und Zugangsknoten beschreibt und dessen Lösung die ermittelte relative Last der Netzelemente ergibt. Aus ferner ermittelten eingehenden Datenraten und Gesamtdatenraten der Netzelemente kann die jeweils ermittelte relative Last korrigiert werden. Es können von den internen Knoten auch unterschiedliche Markierungsalgorithmen in Abhängigkeit von Informationen im Header der Datenpakete angewandt werden.

Description

Beschreibung

Verfahren zur Bestimmung der Last in einem Kommunikationsnetz

Technisches Gebiet

Die Erfindung betrifft ein Verfahren zur Bestimmung der Last in einem Kommunikationsnetz mit Netzelementen, wie internen Knoten und Links, und mit Zugangsknoten, wobei die Zugangsknoten aus jeweils einem Eingangsknoten und einem Ausgangsknoten bestehen und von angeschlossenen Endgeräten und/oder anderen Netzen Datenpakete zu- und ableiten, wobei die internen Knoten und Links nach Routing-Algorithmen Pfade bilden, über welche die Datenpakete von einem Eingangsknoten zu einem Ausgangsknoten geleitet werden, und wobei die internen Knoten Datenpakete mit einer lastabhängigen Markierung versehen.

Stand der Technik

Zur Erfassung von Überlastungen bzw. Blockierungen im Internet ist es durch Kadangode K. Ramakrishnan, Sally Floyd and David Black, IETF RFC 3168: The Addition of Explicit Congestion Notification (ECN) to IP, September 2001 bekanntgeworden, denjenigen Datenpakete, welche mindestens einen internen Knoten durchlaufen haben, bei dem eine Überlastung festgestellt wurde, eine Markierung, bestehend aus einem entsprechend gesetzten Bit, hinzuzufügen. Beim Empfang des Datenpaketes im Ausgangsknoten kann somit festgestellt werden, ob mindestens einer der zur Übertragung dieses Datenpaketes benutzten Knoten und Links hoch belastet oder überlastet is . Das obengenannte Dokument ist ebenso wie die weiter unten genannten Dokumente der IETF (Internet Engineering Task Force) unter der Adresse http ://www. ietf .org/rfc .html verfügbar.

Bei den bekannten Verfahren zur lastabhangigen Markierung wird unter Last nicht die Rechenlast am Vermittlungsknoten verstanden, sondern die Übertragungslast am ausgehenden Link. Dies beinhaltet die implizite Annahme, dass die Vermittlungskapazität des Vermittlungsknotens immer ausreichend ist und hohe Last oder Überlast nur entsteht, wenn die Summe des Verkehrs für einen bestimmten Ausgangslink dessen Kapazität überschreitet.

Die bekannten Verfahren zur lastabhängigen Markierung können unterschieden werden in

- Warteschlangen-orientiert (hier wird markiert, wenn die Warteschlange bestimmte Füllhöhen überschreitet) ,

- Raten-orientiert (hier wird in Abhängigkeit von der Verkehrsrate markiert) ,

- virtuelle Warteschlangen (hier wird ein virtuelles System mitgeführt, bei dem die Übertragungskapazität kleiner ist als beim realen System; wenn die Warteschlange im virtuellen System bestimmte Füllhöhen überschreitet, wird im realen System markiert) .

Mit diesen bekannten Verfahren ist eine näherungsweise Bestimmung der Last jeweils eines Pfades möglich, eine Bestimmung der Last innerhalb des Kommunikationsnetzes, insbesondere in den einzelnen Netzelementen, kann damit jedoch nicht erfolgen. Aufgabe der vorliegenden Erfindung ist es daher, ein Verfahren zur Bestimmung der Last in einem

Kommunikationsnetz anzugeben, bei dem die Last der einzelnen Netzelemente ermittelt wird.

Darstellung der Erfindung

Diese Aufgabe wird bei einer ersten Ausführungsform der Erfindung dadurch gelöst, dass die Ausgangsknoten die aus dem Kommunikationsnetz eintreffenden Datenpakete und die darin enthaltenen Markierungen nach Pfaden getrennt zählen und daraus jeweils einen Wert für die relative Last entlang des jeweiligen Pfades ableiten und dass die von allen Ausgangsknoten abgeleiteten Werte als Parameter in ein Gleichungssystem eingebracht werden, welches das Kommunikationsnetz mit den internen Knoten und Zugangsknoten beschreibt und dessen Lösung die ermittelte relative Last der Netzelemente ergibt.

Dieses Verfahren hat den Vorteil, dass für Netzelemente, die bei dem Setzen der Markierungen berücksichtigt werden, die Last bestimmt werden kann. Solche Netzelemente sind in erster Linie Knoten und Links, wobei das Verfahren nicht auf diese Netzelemente beschränkt ist, sondern andere Netzelemente, wie beispielsweise Speicher, in das Verfahren einbezogen werden können. Dazu sind keine zusätzlichen Maßnahmen in den Knoten erforderlich, um Lastmeldungen an eine oder mehrere zentrale oder dezentrale Stellen zu senden. Die internen Knoten können also die beispielsweise im Internet vorhandene Struktur im wesentlichen behalten.

Eine Weiterbildung des erfindungsgemäßen Verfahrens besteht darin, dass das Gleichungssystem linear ist. Diese Weiterbildung kann in vorteilhafter Weise derart ausgestaltet sein, dass das Gleichungssystem wie folgt lautet :

Σ In (l-m(L )) = ln(l-M(p. .)) für alle i und j, wobei Ln die relevante Last eines Netzelementes, m(L) eine

Funktion zur Berechnung einer Markierungswahrscheinlichkeit zwischen 0 und 1 für eine relative Last L und M(p. .) die abgeleitete relative Last eines Pfades p zwischen einem Eingangsknoten i und einem Ausgangsknoten j ist und wobei die Summe über alle Netzelemente des jeweiligen Pfades p. . gebildet wird.

Diese Weiterbildung ermöglicht die Lösung der Gleichungen mit einem möglichst geringen Rechenaufwand, so dass die Bestimmung der Last in weitgehend kurzzeitigen Intervallen ohne übermäßigen Rechneraufwand erfolgen kann. Diese Berechnungen können in einer zentralen Stelle erfolgen. Die Durchführung des erfindungsgemäßen Verfahrens ist jedoch auch an entsprechend vielen dezentralen Stellen, beispielsweise in den Zugangsknoten, möglich.

Eine Voraussetzung für eine zuverlässige Bestimmung der Last ist gemäß einer Ausgestaltung dadurch gegeben, dass die Knoten die Häufigkeit der Markierungen nach einer stetig und strengen monoton steigenden Funktion der Last ausführen.

Zur Bestimmung der Last in den jeweiligen Netzelementen, nämlich internen Knoten und Links, kann bei dem erfindungsgemäßen Verfahren vorgesehen sein, dass bei der Ausführung der Markierungen in den Knoten die Last im Knoten zugrundegelegt wird und/oder dass bei der Ausführung der Markierungen die Lasten in den vom Knoten ausgehenden Links berücksichtigt werden.

Eine andere Ausgestaltung des erfindungsgemäßen Verfahrens besteht darin, dass die ermittelte relative Last zur Steuerung von Routing-Algorithmen verwendet wird und dass die ermittelten relativen Lasten in Pfadvorgaben für die von den Eingangsknoten zu sendenden Datenpakete berücksichtigt werden.

Es kann jedoch auch vorgesehen sein, dass die ermittelten relativen Lasten für spätere Auswertungen gespeichert werden.

Üblicherweise übersteigt die Zahl der Pfade die Zahl der Links bzw. Knoten. Da die einzelnen Parameter der Berechnung außerdem mit einem gewissen Fehler behaftet sind (durch die Verzögerung bei der Informationsgewinnung) , kann es vorkommen, dass das Gleichungssystem überspezifiziert und nicht direkt lösbar ist. Dieses wird mit einer anderen Ausgestaltung dadurch verhindert, dass die Berechnungen zur Lösung des Gleichungssystems erfolgen, wenn die Zahl der Werte für die relative Last, die von den Ausgangsknoten gemeldet werden, zur eindeutigen Lösung des Gleichungssystems ausreicht.

Damit wird bewirkt, dass jeweils nur die neuesten für die Anzahl der Netzelemente erhaltenen Pfad-Last-Werte zur Berechnung verwendet werden, die linear unabhängig sind und somit alle Netzelemente abdecken.

Außer der Bestimmung der relativen Last im

Kommunikationsnetz, insbesondere der relativen Last aller

Netzelemente, kann das erfindungsgemäße Verfahren auch zur

Bestimmung der Kapazitäten aller Netzelemente angewendet werden. Dazu ist gemäß einer weiteren Ausgestaltung der

Erfindung vorgesehen, dass in den Ausgangsknoten ferner die eingehende Datenrate nach Pfaden getrennt ermittelt wird und dass zur Bestimmung der Kapazität der Netzelemente folgende

Gleichung angewendet wird,

e Kapazität des Netzelementes,' Ln die ermittelte

relative Last, t. . die übertragene Datenrate entlang eines

^■*^• ' J Pfades p. . ist und die Summe über alle Pfade p. . gebildet wird.

Bei dem erfindungsgemäßen Verfahren kann zwar die relative Last der einzelnen Netzelemente ermittelt - besser gesagt geschätzt - werden, es ergeben sich jedoch durch unumgehbare Messgenauigkeiten und Übertragungsverzögerungen Fehler. Bei der oben genannten Weiterbildung des erfindungsgemäßen Verfahrens besteht das Gleichungssystem aus einer multiplikativen Verknüpfung von Koeffizienten. Diese Verknüpfung wird durch eine Transformation mit der Logarithmusfunktion in eine additive Verknüpfung umgewandelt, so dass sich zwar ein lineares Gleichungssystem ergibt. Durch die ursprünglich multiplikative Verknüpfung der Koeffizienten können jedoch die genannten Fehler recht groß werden.

Dies wird bei einer anderen Weiterbildung dadurch verhindert,

- dass in den Ausgangsknoten ferner die eingehende Datenrate nach Pfaden getrennt ermittelt wird,

- dass für die einzelnen Netzelemente die ermittelten Datenraten, die für diejenigen Pfade ermittelt wurden, auf denen das jeweilige Netzelement liegt, zu einer Gesamtdatenrate des Netzelements aufaddiert werden,

- dass die Gesamtdatenrate und die relative Last wiederholt ermittelt werden und

- dass die jeweils ermittelte relative Last unter Berücksichtigung der zuvor ermittelten relativen Last und einer Änderung der Gesamtdatenrate korrigiert wird.

Bei der Berechnung der Gesamtdatenrate je Knoten bzw. Link werden die Datenraten aller den Knoten bzw. Link durchlaufenden Pfade addiert. Diese Addition hat den Vorteil, dass sich Fehler nicht fortpflanzen und vergrößern wie im obengenannten Gleichungssystem.

Eine vorteilhafte Ausgestaltung dieser Weiterbildung besteht darin, dass die korrigierte relative Last aus Mittelung der jeweils ermittelten relativen Last und der zuvor ermittelten relativen Last, die mit der Änderung der Gesamtdatenrate bewertet wird, berechnet wird.

Diese Ausgestaltung kann insbesondere derart ausgeführt sein, dass die Berechnung der korrigierten relativen Last mit der Gleichung Lk = (cü-La-Un/Ua + Ln)/(α+l) erfolgt, wobei Lk die korrigierte relative Last, c ein Gewichtsfaktor, der bestimmt, wie stark die Änderung der Gesamtdatenrate berücksichtigt wird, La der zuvor ermittelte Wert für die relative Datenrate, Un die jeweils ermittelte Gesamtdatenrate, Ua die zuvor ermittelte Gesamtdatenrate und Ln die jeweils aktuell ermittelte relative Last ist.

Der Gewichtungsfaktor CÜ ist je nach Voraussetzungen im Einzelnen vom Fachmann festzulegen.

Die bekannten Verfahren gehen davon aus, dass nicht verschiedene dieser Markierungsalgorithmen in einem Kommunikationsnetz angewendet werden.

Für verschiedene Zwecke kann es jedoch sinnvoll sein, verschiedene Markierungsalgorithmen quasi gleichzeitig anzuwenden und bei der Auswertung getrennt zu berücksichtigen. Bei den bekannten Verfahren kann jedoch aus dem einmal markierten Datenpaket kein Rückschluss auf den jeweils angewandten Markierungsalgorithmus vorgenommen werden.

Dies wird bei einer zweiten Ausführungsform der Erfindung dadurch ermöglicht, dass die internen Knoten mindestens zwei unterschiedliche Markierungsalgorithmen anwenden in Abhängigkeit davon, welcher Typ im Header des jeweils weiterzuleitenden Datenpakets angegeben ist, dass die Eingangsknoten entsprechend der Zahl der unterschiedlichen Markierungsalgorithmen jeweils pro Pfad einen vorgegebenen Anteil der Typen angeben und dass zur Bestimmung der Markierungsraten der verwendeten Markierungsalgorithmen die Ausgangsknoten die Zahl der markierten Datenpakete entsprechend dem Verhältnis der Zahlen der einzelnen Typen der nicht markierten Datenpakete auf die einzelnen Typen aufteilen.

Bei den derzeit im Internet gebräuchlichen Standards sind zwei Bit innerhalb eines Headers vorgesehen, die bei markierten Datenpaketen einen vorgegebenen Zustand (11) einnehmen (CE-Markierung) . Bei nicht markierten Datenpaketen sind zwei Codepoints möglich, nämlich ECT01 und ECT10. Datenpakete, die mit dem Code 00 versehen sind, werden nicht markiert, aber mit einer höheren Wahrscheinlichkeit verworfen.

Für die Anwendung im Rahmen dieses Standards ist bei einer Weiterbildung der Erfindung vorgesehen, dass zwei unterschiedliche Markierungsalgorithmen in Abhängigkeit von zwei im Header angegebenen möglichen Typen angewendet werden und vorzugsweise dass die Eingangsknoten über jeweils einen Pfad gesendete Datenpakete gleich häufig mit dem einen oder anderen Typ kennzeichnen.

Eine einfache Bestimmung der auf die jeweiligen Markierungsalgorithmen bezogenen Markierungsrate ist gemäß einer vorteilhaften Ausgestaltung der Erfindung dadurch möglich, dass in den Ausgangsknoten die relative Markierungsrate für den ersten Typ zu Ml=l- (2a/N) und für den zweiten Typ zu M2=l- (2b/N) berechnet wird, wobei N die Summe aller empfangenen markierten oder mit einem der Typen bezeichneten Datenpakete, a die Anzahl der nicht markierten empfangenen Datenpakete des ersten Typs und b die Anzahl der empfangenen nicht markierten Datenpakete des zweiten Typs ist .

Kurze Beschreibung der Zeichnungen

Die Erfindung läßt zahlreiche Ausführungsformen zu. Einige davon sind schematisch in der Zeichnung anhand mehrerer Figuren dargestellt und nachfolgend beschrieben. Es zeigt:

Fig. 1 schematisch ein Kommunikationsnetz und

Fig. 2 ein Beispiel für Markierungen von Datenpaketen bei der Durchführung der zweiten Ausführungsform des erfindungsgemäßen Verfahrens.

Beschreibung der Ausführungsbeispiele

Fig. 1 stellt schematisch das Kommunikationsnetz 1 mit Zugangsknoten 2, 3, 4 (Gateways) und internen Knoten 5, 6, 7, 8, 9 dar. Die Zugangsknoten 2, 3, 4 verbinden das Kommunikationsnetz 1 mit anderen Netzen und Endgeräten und bestehen jeweils aus einem Eingangsknoten 21, 31, 41 (ingress node) und einen Ausgangsknoten 22, 32, 42 (egress node) . Die internen Knoten 5 bis 9 dienen zum Weiterleiten der jeweiligen Datenpakete von einem Eingangsknoten 21, 31, 41 zu einem Ausgangsknoten 22, 32, 42. Welchen Weg dabei jeweils ein Datenpaket nimmt, wird von Routing-Algorithmen bestimmt, die je nach Belastung der einzelnen Knoten veränderbar sind. Die Routing-Algorithmen im einzelnen sind an sich bekannt, und brauchen im Zusammenhang mit der vorliegenden Erfindung nicht näher erläutert zu werden. Ergibt sich beispielsweise für die internen Knoten 5, 6 ein erhöhtes Verkehrsaufkommen, so werden die von ihnen weitergeleiteten Datenpakete mit einer Markierung M versehen. Solche Markierungen enthalten beispielsweise die Datenpakete, die vom Eingangsknoten 21 über die internen Knoten 5, 6 zum Ausgangsknoten 32 geleitet werden. Sind die internen Knoten 5, 6 sowie deren Verbindungen untereinander und zu den Knoten 21 und 32 überlastet, werden von den vom Eingangsknoten 21 zum Ausgangsknoten 32 zu sendenden Datenpaketen mehr über die internen Knoten 8, 9 geleitet.

Im Ausgangsknoten 32 werden in einem vorgegebenen Zeitabschnitt die in den vom Eingangsknoten 21 erhaltenen Datenpaketen enthaltenen Markierungen M gezählt. Zusätzlich werden die Bytes und die Datenpakete gezählt, die in der vorgegebenen Zeit vom Eingangsknoten 21 zum Ausgangsknoten 32 übertragen werden. Die Anzahl der Markierungen geteilt durch die Anzahl der Datenpakete ergibt ein gutes Maß für die Belastung des Kommunikationsnetzes hinsichtlich der Übertragung zwischen dem Eingangsknoten 21 und dem Ausgangsknoten 32.

In den einzelnen internen Knoten erfolgt die Markierung mit einer Wahrscheinlichkeit m(L) , wobei L eine relative Last ist. Für jedes durch einen Pfad verbundene Paar

Zugangsknoten (i,j) ist p. . der verbindende Pfad. Dann

¹ ' 3 berechnet sich die gemessene Last M(p. .) entlang des Pfades ⁱ / J p , . zu

M(p. ■) = 1- (l-m(L )) • (l-m(L ))•... • (l-m(L ) ) , wobei n die

Anzahl der Knoten jeweils eines Pfades ist und für jeden

Pfad p. . eine Gleichung aufgestellt wird. Dieses

Gleichungssystem kann wie folgt umgeformt werden:

1 - M(p_i .) = (l-m(L₁)) Al-m(L₂)) •... Al-m(L_n)) .

Durch Logarithmierung erhält man das lineare

Gleichungssystem

Σ In (l-m(L )) = ln(l-M(p. .)) für alle i und j, bei dem die Funktion ln(l-m(L.)) durch y. substituiert werden kann. Falls m(L.) im Wertebereich zwischen 0 und 1 eine Umkehrfunktion besitzt, kann ln(l-m(L.)) = y. für alle Knoten gelöst werden. Dann kann mit der Lösung des linearen Gleichungssystems die Lösung des Ausgangsgleichungssystems bestimmt werden.

Falls die Berechnung von m(L) auf Link-Last basiert, so sind die Pfade als gerichtet zu betrachten, das heißt beide Richtungen eines Pfades werden separat berücksichtigt. Entsprechend werden beide Richtungen eines Links durch separate Lastzustände L abgebildet.

Aus den ermittelten Werten für die relative Last Ln der internen Knoten bzw. Links und der von den Ausgangsknoten ermittelten über die einzelnen Datenpfade p. . übertragenen

^-' 3 Datenraten kann die Kapazität c der Knoten bzw. Links wie folgt berechnet werden: c = (∑t. . )/L , n I, j n' wobei c die Kapazität des Netzelementes, L die ermittelte relative Last, t. . die übertragene Datenrate entlang eines

-¹- 3 Pfades p . . ist und die Summe über alle Pfade p . . gebildet wird.

Bei einem anderen Ausführungsbeispiel wird durch Lösung des Gleichungssystems ∑ In (l-m(L )) = ln(l-M(p. .)) die relative Last L für die einzelnen Netzelemente (interne Knoten und Links) ermittelt.

Ferner werden aus den an den Ausgangsknoten 22, 32, 42 nach den einzelnen Pfaden getrennt ermittelten Datenraten die Gesamtdatenraten für die einzelnen Netzelemente berechnet. Dies erfolgt durch eine Addition der Datenraten derjenigen Pfade, an denen das jeweilige Netzelement beteiligt ist. Dabei werden jeweils alle Pfade berücksichtigt, die aufgrund der Netzstruktur und der Routing-Algorithmen möglich sind. Als Beispiel ist im folgenden für den internen Knoten 8 folgende Gleichung zu nennen:

U(8) = U(21,8,7,6,32) + U (21, 8 , 7 , 9 , 32 )

+ U(31,6,7,8,22) + U (31, 9 , 7 , 8 , 22 )

+ 11(21,8,42) + U(21,8,7, 9,42)

+ U(41,8,22) + U(41, 9,7,8,22) ...

Dabei bedeutet beispielsweise U(21, 8 , 7, 6, 32) die Datenrate des Pfades zwischen dem Eingangsknoten 21 über die internen Knoten 8, 7, und 6 zum Ausgangsknoten 32.

Sowohl die relative Last L als auch die Gesamtdatenrate werden regelmäßig gemessen - beispielsweise in Zeitabständen von wenigen Sekunden. Bei dem bevorzugten Ausführungsbeispiel werden je Netzelement die jeweils neu ermittelten Werte Ln und Un sowie die vorangegangenen Werte La und Ua zur Bildung der korrigierten Last Lk nach folgender Gleichung verwendet :

Lk = (α-La-Un/Ua + Ln)/(α+l). Der Gewichtsfaktor kann vom Fachmann nach folgenden Gesichtspunkten ermittelt werden:

Ist ot klein gegenüber 1, ist die Wirkung der erfindungsgemäßen Korrektur sehr gering. Allerdings erfolgt auch eine schnelle Anpassung an Änderungen der verfügbaren Kapazität, bei denen sich auch die relative Last schnell ändert, nicht jedoch die Gesamtdatenrate. Je größer a ist, desto stärker wirkt die Fortschreibung der früher ermittelten relativen Last anhand der Änderung der Gesamtdatenrate. Eine Anpassung an Kapazitätsänderungen erfolgt dann langsamer. Im Extremfall, in dem a viel größer als 1 ist, erfolgt praktisch nur eine Fortschreibung auf der Basis von Änderungen der Gesamtdatenrate. Zur Erläuterung der zweiten Ausführungsform werden im folgenden ECT-Markierungen von Datenpaketen auf den Links 10, 11 und 12 betrachtet. Der Eingangsknoten 21 sendet abwechselnd ECT-Typen 10 und 01, was in der oberen Zeile in Fig. 2 dargestellt ist. Es ist nicht erforderlich, dass der Wechsel nach jedem Datenpaket, das über den Link 10 zum internen Knoten 5 gesendet wird, erfolgt. Entscheidend ist, dass über einen jeweils zu betrachtenden Zeitraum die ECT-Typen 10 und 01 gleich häufig gesendet werden.

Im Knoten 5 werden je nach vorliegender Last einige der Datenpakete mit CE-Markierungen versehen, das heißt, beide Bits werden auf 1 gesetzt. Dies ist in der mittleren Zeile der Fig. 2 erkennbar, welche die Datenpakete auf dem Link 11 darstellt. Einige noch nicht markierte Datenpakete werden dann im internen Knoten 6 bei entsprechender Last mit einer CE-Markierung versehen, so dass sich auf dem Link 12 die in der unteren Zeile der Fig. 2 dargestellten Datenpakete ergeben. Die Gesamtzahl N ist gleich 16. Von den Datenpaketen des Typs 10 sind drei nicht markiert worden, weshalb a gleich 3 ist. Von den Datenpaketen des Typs 01 sind fünf nicht markiert worden. Deshalb ist b gleich 5. Die Markierungsraten errechnen sich dann, wie in Fig. 2 ferner angegeben, zu Ml = 5/8 und M2 = 3/8.

Die Gleichungen zur Berechnung der Markierungsraten lassen sich wie folgt ableiten, wobei P eine Anzahl von Datenpaketen ist, für welche die relative Anzahl von markierten Datenpaketen - also die Markierungsrate - berechnet werden soll. Ferner ist N die Anzahl der ECT01-, ECT10- und CE-Datenpakete. Die anderen Datenpakete (P-N) sind irrelevant.

Ferner sind a die Anzahl der ECTOl-Datenpakete, b die Anzahl der ECT10-Datenpakete und c die Anzahl der CE-Datenpakete .

Es gilt also N = a+b+c.

Wegen der abwechselnden Kennzeichnung als ECTOl und ECT10 am

Eingangsknoten gilt a≤N/2 und b≤N/2.

Dann ergeben sich die Markierungsraten zu:

Ml = l-(a/(N/2)) = l-(2a/N) und

M2 = l-(b/(N/2)) = l-(2b/N).

Claims

Technische Universität DarmstadtAnsprüche

1. Verfahren zur Bestimmung der Last in einem Kommunikationsnetz mit Netzelementen, wie internen Knoten und Links, und mit Zugangsknoten, wobei die Zugangsknoten aus jeweils einem Eingangsknoten und einem Ausgangsknoten bestehen und von angeschlossenen Endgeräten und/oder anderen Netzen Datenpakete zu- und ableiten, wobei die internen Knoten und Links nach Routing-Algorithmen Pfade bilden, über welche die Datenpakete von einem Eingangsknoten zu einem Ausgangsknoten geleitet werden, und wobei die internen Knoten Datenpakete mit einer lastabhängigen Markierung versehen, dadurch gekennzeichnet, dass die Ausgangsknoten die aus dem Kommunikationsnetz eintreffenden Datenpakete und die darin enthaltenen Markierungen nach Pfaden getrennt zählen und daraus jeweils einen Wert für die relative Last entlang des jeweiligen Pfades ableiten und dass die von allen Ausgangsknoten abgeleiteten Werte als Parameter in ein Gleichungssystem eingebracht werden, welches das Kommunikationsnetz mit den internen Knoten und Zugangsknoten beschreibt und dessen Lösung die ermittelte relative Last der Netzelemente ergibt .

2. Verfahren nach Anspruch 1, dadurch gekennzeichnet, dass das Gleichungssystem linear ist.

3. Verfahren nach Anspruch 2, dadurch gekennzeichnet, dass das Gleichungssystem wie folgt lautet:

∑ ln (l-m(L )) = ln(l-M(p. .)) für alle i und j, wobei Ln die relevante Last eines Netzelementes, m(L) eine

Funktion zur Berechnung einer Markierungswahrscheinlichkeit zwischen 0 und 1 für eine relative Last L und M(p. . ) die abgeleitete relative Last eines Pfades p zwischen einem

Eingangsknoten i und einem Ausgangsknoten j ist und wobei die Summe über alle Netzelemente des jeweiligen Pfades p. .

¹ 3 gebildet wird.

4. Verfahren nach einem der vorhergehenden Ansprüche, dadurch gekennzeichnet, dass die Knoten die Häufigkeit der Markierungen nach einer stetig und strengen monoton steigenden Funktion der Last ausführen.

5. Verfahren nach Anspruch 4, dadurch gekennzeichnet, dass bei der Ausführung der Markierungen in den Knoten die Last im Knoten zugrundegelegt wird.

6. Verfahren nach Anspruch 4, dadurch gekennzeichnet, dass bei der Ausführung der Markierungen die Lasten in den vom Knoten ausgehenden Links berücksichtigt werden.

7. Verfahren nach einem der vorhergehenden Ansprüche, dadurch gekennzeichnet, dass die ermittelte relative Last zur Steuerung von Routing-Algorithmen verwendet wird.

8. Verfahren nach einem der vorhergehenden Ansprüche, dadurch gekennzeichnet, dass die ermittelten relativen Lasten in Pfadvorgaben für die von den Eingangsknoten zu sendenden Datenpakete berücksichtigt werden.

9. Verfahren nach einem der vorhergehenden Ansprüche, dadurch gekennzeichnet, dass die ermittelten relativen Lasten für spätere Auswertungen gespeichert werden.

10. Verfahren nach einem der vorhergehenden Ansprüche, dadurch gekennzeichnet, dass die Berechnungen zur Lösung des Gleichungssystems erfolgen, wenn die Zahl der Werte für die relative Last, die von den Ausgangsknoten gemeldet werden, zur eindeutigen Lösung des Gleichungssystems ausreicht.

11. Verfahren nach einem der vorhergehenden Ansprüche, dadurch gekennzeichnet, dass in den Ausgangsknoten ferner die eingehende Datenrate nach Pfaden getrennt ermittelt wird und dass zur Bestimmung der Kapazität der Netzelemente folgende Gleichung angewendet wird,

12. Verfahren nach einem der vorhergehenden Ansprüche, dadurch gekennzeichnet,

13. Verfahren nach Anspruch 12, dadurch gekennzeichnet, dass die korrigierte relative Last aus Mittelung der jeweils ermittelten relativen Last und der zuvor ermittelten relativen Last, die mit der Änderung der Gesamtdatenrate bewertet wird, berechnet wird.

14. Verfahren nach Anspruch 13, dadurch gekennzeichnet, dass die Berechnung der korrigierten relativen Last mit der Gleichung Lk = (α?-La-Un/Ua + Ln)/(α+l) erfolgt, wobei Lk die korrigierte relative Last, α ein Gewichtsfaktor, der bestimmt, wie stark die Änderung der Gesamtdatenrate berücksichtigt wird, La der zuvor ermittelte Wert für die relative Datenrate, Un die jeweils ermittelte Gesamtdatenrate, Ua die zuvor ermittelte Gesamtdatenrate und Ln die jeweils aktuell ermittelte relative Last ist.

15. Verfahren zur Bestimmung der Last in einem Kommunikationsnetz mit Netzelementen, wie internen Knoten und Links, und mit Zugangsknoten, wobei die Zugangsknoten aus jeweils einem Eingangsknoten und einem Ausgangsknoten bestehen und von angeschlossenen Endgeräten und/oder anderen Netzen Datenpakete zu- und ableiten, wobei die internen Knoten und Links nach Routing-Algorithmen Pfade bilden, über welche die Datenpakete von einem Eingangsknoten zu einem Ausgangsknoten geleitet werden, und wobei die internen Knoten Datenpakete mit einer lastabhängigen Markierung versehen, dadurch gekennzeichnet, dass die internen Knoten mindestens zwei unterschiedliche Markierungsalgorithmen anwenden in Abhängigkeit davon, welcher Typ im Header des jeweils weiterzuleitenden Datenpakets angegeben ist, dass die Eingangsknoten entsprechend der Zahl der unterschiedlichen Markierungsalgorithmen jeweils pro Pfad einen vorgegebenen Anteil der Typen angeben und dass zur Bestimmung der Markierungsraten der verwendeten Markierungsalgorithmen die Ausgangsknoten die Zahl der markierten Datenpakete entsprechend dem Verhältnis der Zahlen der einzelnen Typen der nicht markierten Datenpakete auf die einzelnen Typen aufteilen.

16. Verfahren nach Anspruch 15, dadurch gekennzeichnet, dass zwei unterschiedliche Markierungsalgorithmen in Abhängigkeit von zwei im Header angegebenen möglichen Typen angewendet werden.

17. Verfahren nach Anspruch 16, dadurch gekennzeichnet, dass die Eingangsknoten über jeweils einen Pfad gesendete Datenpakete gleich häufig mit dem einen oder anderen Typ kennzeichnen.

18. Verfahren nach Anspruch 17, dadurch gekennzeichnet, dass in den Ausgangsknoten die relative Markierungsrate für den ersten Typ zu Ml=l- (2a/N) und für den zweiten Typ zu M2=l- (2b/N) berechnet wird, wobei N die Summe aller empfangenen markierten oder mit einem der Typen bezeichneten Datenpakete, a die Anzahl der nicht markierten empfangenen Datenpakete des ersten Typs und b die Anzahl der empfangenen nicht markierten Datenpakete des zweiten Typs ist .