DE69733258T2

DE69733258T2 - Verfahren und anlage zur messung der proportion eines einem bestimmten kriterium genügenden anteils eines atm-zellenflusses

Info

Publication number: DE69733258T2
Application number: DE69733258T
Authority: DE
Inventors: Marc Bavant
Original assignee: Thales SA
Current assignee: Remote Access Los Altos Calif Us LLC
Priority date: 1996-07-12
Filing date: 1997-07-11
Publication date: 2006-08-03
Anticipated expiration: 2017-07-12
Also published as: CA2260089A1; EP0910911B1; US6330228B1; WO1998002996A1; DE69733258D1; FR2751108B1; FR2751108A1; EP0910911A1

Description

Die vorliegende Erfindung betrifft ein Meßverfahren und eine Meßvorrichtung, die auf Netze für die paketweise Datenübertragung anwendbar sind, insbesondere auf die unter der angelsächsischen Abkürzung ATM (asynchronous transfer mode, asynchroner Übertragungsmodus) bekannten Netze.
Die in den ATM-Netzen transportierten Pakete werden Zellen genannt, und es kann von Interesse sein, an einem Punkt eines Zellenflusses zu wissen, welches zu jedem Zeitpunkt der Anteil von Zellen ist, die ein bestimmtes Kriterium erfüllen; zum Beispiel, welches der Anteil von Zellen ist, die einer gegebenen Verbindung, einem gegebenen Dienst usw. entsprechen.
Wenn man den Gesamtdurchfluß des Zellenflusses kennt, was zum Beispiel dann der Fall ist, wenn es sich um einen ATM-Zellenfluss handelt, der durch einen Kanal mit bekanntem Durchfluß geht, ermöglicht es eine Anteilsmessung, ein Maß des Durchflusses für diejenigen Zellen abzuleiten, die das betrachtete Kriterium erfüllen.
Ihrem Wesen nach muß eine solche Messung zu jedem Zeitpunkt ein Ergebnis liefern, aber sie muß Ereignisse berücksichtigen, die vor mehr oder weniger kurzer Zeit geschehen sind. Ein einfacher gleitender Mittelwert, wie er in der Patentanmeldung WO-A-94/11972 beschrieben wird, mag in zahlreichen Fällen genügen, aber die Umsetzung eines solchen Algorithmus beruht im Allgemeinen auf einer zirkulären Folge der letzten Werte, was Kapazitäten von Speicherung- und Zugriff verlangt, der auf den Speicher indiziert ist. Übrigens hängt die Reichweite dieses Mittelwertes, d.h. seine Speicherkapazitäten der Vergangenheit, direkt vom verfügbaren physischen Speicher ab.
Es ist das Ziel der Erfindung, die genannten Nachteile durch ein Verfahren und eine Vorrichtung zu beheben, die es erlauben, eine Anteilsmessung auszuführen, die minimale Hardwareressourcen verlangt.
Daher hat die Erfindung ein Verfahren zur Messung des Anteils der einem Kriterium entsprechenden ATM-Zellen an einem bestimmten Punkt eines Netzes zur zellenweisen Datenübertragung zum Gegenstand, das dadurch gekennzeichnet ist, daß es darin besteht, den durch den bestimmten Punkt passierenden Zellen, die das Kriterium erfüllen, einen ersten Zahlenwert zuzuordnen, und denjenigen Zellen, die das Kriterium nicht erfüllen, einen zweiten Wert zuzuordnen, und einen exponentiellen Mittelwert von der Folge von so jeder Zelle zugeordneten Werten u_n zu erzeugen.
Die Erfindung hat ebenfalls eine Vorrichtung zur Umsetzung des genannten Verfahrens zum Gegenstand.
Weitere Merkmale und Vorteile der Erfindung werden aus der folgenden Beschreibung hervorgehen, die angesichts der beigefügten Zeichnungen gegeben wird, in denen:
1 und 2 Vorrichtungen für die Umsetzung des erfindungsgemäßen Verfahrens darstellen.
3a bis 3c Beispiele für Ergebnisse darstellen, die durch Anwendung des erfindungsgemäßen Verfahrens erhalten wurden.
Bei der Umsetzung des erfindungsgemäßen Verfahrens wird das bekannte Verfahren der Berechnung des exponentiellen Mittelwertes eingesetzt, das nichts anderes darstellt als das Ergebnis einer linearen, zeitdiskreten Filterung erster Ordnung ist, die mit einer Folge von Eingangswerten u_n erzeugt wird. Die Folge x_n der entsprechenden Filterzustände wird durch die Gleichung xn+1 = a·xn + (1 – a)·un (1)definiert, wo a ein Parameter ist, der kleiner als eins ist, aber nahe an 1 ist, und die Reichweite des Filters definiert. Die Folge x_n stellt somit eine Art von augenblicklichem Mittelwert der Eingangswerte u_n über einen mehr oder weniger langen Zeitraum dar. Das erfindungsgemäße Verfahren besteht darin, u_n einen ersten Wert zuzuordnen, wenn eine zu einem Zeitpunkt n einen bestimmten Meßpunkt eines ATM-Netzes passierende Zelle, ein bestimmtes Kriterium erfüllt, und ihm einen zweiten Wert zu erteilen, wenn die betrachtete Zelle dieses Kriterium nicht erfüllt, sodann eine Filterung der Werte von u_n nach Gleichung (1) zu erzeugen, um zu jedem Zeitpunkt einen Mittelwert x_n zu erhalten, der den Anteil der Anzahl der Zellen darstellt, die das Kriterium erfüllen und die den Meßpunkt im Netz durchlaufen.
Beispielsweise liefert der Wert von x_n den gesuchten Anteil auf einer Skala von 0 bis 241, wenn der erste Wert von u_n auf 256 und der zweite Wert von u_n auf null festgelegt und als Wert von a ein beachtlicher Wert, wie 15/16, gewählt wird, um die Operationen der Multiplikation und Division auf binäre Verschiebungen zu beschränken.
Eine entsprechende Vorrichtung für die Umsetzung des erfindungsgemäßen Verfahrens ist in 1 dargestellt. Sie umfaßt eine Schaltung zur Erfassung 1 der dem betrachteten Kriterium entsprechenden Zellen, gekoppelt mit einer Schaltung 2 zur Berechnung des exponentiellen Mittelwertes, die innerhalb einer geschlossenen, gestrichelten Linie dargestellt ist. Die Schaltung zur Erfassung 1 liefert den dem betrachteten Kriterium entsprechenden Wert u_n an den Eingang der Schaltung zur Berechnung 2, der zum Beispiel aus einem vorbestimmten Feld der ATM-Zelle gelesen wird. Die Schaltung zur Berechnung 2 umfaßt einen Additionsoperator 3, der über einen ersten mit „+" bezeichneten Operandeneingang an einen ersten Ausgang der Schaltung zur Erfassung 1 angeschlossen ist. Sie umfaßt weiter einen ersten Verschiebungsoperator 4, der an den Ausgang des Additionsoperators 3 angeschlossen ist, um die Folge der Werte x_n zu liefern. Der Ausgang des ersten Verschiebungsoperators 4 ist über einen zweiten Verschiebungsoperator 5 und eine damit in Reihe geschaltete Ein-Bit-Verzögerungsschaltung 6 an einen zweiten mit „+" bezeichneten Operandeneingang des Additionsoperators 3 angeschlossen. Ein dritter, mit „–" bezeichneter Operandeneingang des Additionsoperators 3 ist an den Ausgang der Verzögerungsschaltung 6 angeschlossen. Um dem zitierten Beispiel zu folgen, wo a = 15/16 und u_n auf 256 oder null festgelegt ist, ist der erste Verschiebungsoperator 4 so eingestellt, daß er eine Verschiebung um vier Bits nach rechts erzeugt, der zweite Operator 5 ist so eingestellt, daß er eine Verschiebung um vier Bits nach links erzeugt.
Natürlich kann das gleiche Ergebnis mit Hilfe eines mikroprogrammierten Mikroprozessors erhalten werden. In diesem Falle wird Gleichung (1): xn+1 = ((xn ≪ 4) – xn + un) ≫ 4 (2)wo die „und"-Operatoren logische Verschiebungsoperatoren wie in der Sprache C sind.
Vergleichbare Ergebnisse können ebenfalls mit anderen so beachtlichen Werten von a wie (2^r – 2^s)/2^r erhalten werden. Dafür genügt es, die Vorrichtung wie in der in 2 dargestellten Weise abzuändern, wo die den Elementen der 1 homologen Elemente mit den gleichen Bezugszeichen dargestellt sind. In diesem Falle ist der erste Operator 4 so eingestellt, daß er eine Verschiebung um r Bits nach rechts erzeugt, während der zweite Operator 5 so eingestellt ist, daß er eine Verschiebung um r Bits nach links erzeugt. Die Vorrichtung unterscheidet sich von der Vorrichtung der 1 durch das Hinzukommen eines dritten Verschiebungsoperators 7, der zwischen die Verzögerungsvorrichtung 6 und den Additionsoperator 3 eingefügt werden muß, sowie eines vierten Verschiebungsoperators 8 zwischen dem Ausgang des Detektors 1 und dem ersten Operandeneingang des Additionsoperators 3, beide um eine Verschiebung um s Bits nach links zu erzeugen. Im Falle von a gleich (2^r – 2^s)/2^r und für u_n = 2^q oder 0, je nachdem, ob die betrachtete Zelle das fragliche Kriterium erfüllt oder nicht, liegt der durch die folgende Gleichung berechnete Anteil zwischen 0 und 2^q – 2^r–s + 1, d.h. xn+1 = (xn ≪ r – xn ≪ s + un ≪ s) ≫ r (3)
Beispiele für Ergebnisse, die durch die Realisierung des erfindungsgemäßen Verfahrens erhalten wurden, werden in 3a, 3b und 3c gezeigt.
Die in 3a dargestellte Kurve zeigt den gemessenen Anteil, wenn jede zweite Zelle das gegebene Kriterium erfüllt.
Die in 3b dargestellte Kurve zeigt den gemessenen Anteil, wenn jede Zelle das gegebene Kriterium mit einer Wahrscheinlichkeit von 60 % erfüllt. (Zufallssimulation durch eine gleichförmige Zufallsvariable.) Die in 3c dargestellte Kurve zeigt den gemessenen Anteil, wenn der Strom der das gegebene Kriterium erfüllenden Zellen an die in leichten Linien gezeichnete Sinuskurve angepaßt wird. (Wenn die Zelle zum Zeitpunkt n das Kriterium erfüllt, dann kommt die nächste, das Kriterium erfüllende Zelle zum Zeitpunkt p an, der ein ganzzahliger Teil von n + 1/r(n) ist.)

Claims

Verfahren zur Messung des an einem bestimmten Punkt eines Netzes zur zellenweisen Datenübertragung einem Kriterium entsprechenden Anteils von ATM-Zellen, dadurch gekennzeichnet, daß es darauf beruht, (1) den durch den bestimmten Punkt passierenden Zellen, die das Kriterium erfüllen, einen ersten Zahlenwert zuzuordnen, und den das Kriterium nicht erfüllenden Zellen einen zweiten Zahlenwert zuzuordnen, und (2) einen exponentiellen Mittelwert von der Folge von so jeder Zelle zugeordneten Werten u_n zu erzeugen.
Verfahren nach Anspruch 1, dadurch gekennzeichnet, daß der exponentielle Mittelwert (2) von der Folge von Werten u_n mit Hilfe eines digitalen Filters erster Ordnung erzeugt wird, das durch die folgende Gleichung definiert wird: xn+1 = axn + (1 – a)un wobei a ein Parameter kleiner als 1, aber nahe an 1 ist, und x_n die Folge der Zustände des Filters darstellt.
Verfahren nach Anspruch 2, dadurch gekennzeichnet, daß es darauf beruht, dem ersten Wert von u_n einen Wert 256 und dem zweiten Wert von u_n den Wert 0 zuzuordnen.
Verfahren nach den Ansprüchen 2 und 3, dadurch gekennzeichnet, daß es darauf beruht, dem Parameter "a" den Wert 15/16 zuzuordnen.
Verfahren nach Anspruch 2, dadurch gekennzeichnet, daß es darauf beruht, dem Parameter "a" einen durch die Beziehung (2^r – 2^s)/2^r definierten Wert und dem ersten Wert von u_n den Wert 2^q sowie dem zweiten Wert von u_n den Wert 0 zuzuordnen, wobei q, r und s positive ganze Zahlen sind.
Vorrichtung zur Messung des an einem bestimmten Punkt eines Netzes zur zellenweisen Datenübertragung einem Kriterium entsprechenden Anteils von ATM-Zellen, dadurch gekennzeichnet, daß sie eine Schaltung (1) zur Erfassung von Zellen umfaßt, die dieses Kriterium erfüllen oder nicht erfüllen, und die in Abhängigkeit von dieser Erfassung jeder Zelle einen Wert u_n zuordnet, wobei die Schaltung mit einer Schaltung zur Berechnung des exponentiellen Mittelwerts (2) von der Folge von Werten u_n gekoppelt ist, die aus einem digitalen Filter erster Ordnung besteht, das durch die Gleichung x_n+1 = ax_n+ (1 – a)u_n definiert ist, wobei a ein Parameter kleiner als 1, aber nahe an 1 ist, und x_n die Folge der Zustände des Filters darstellt.
Vorrichtung nach Anspruch 6, dadurch gekennzeichnet, daß die Schaltung zur Berechnung des exponentiellen Mittelwerts (2) umfaßt – einen Additionsoperator (3), der an einem ersten Operandeneingang die Folge von Werten u_n empfängt, – einen ersten Verschiebeoperator (4), der an den Ausgang des Additionsoperators (3) gekoppelt ist, um die Folge von Werten x_n zu liefern, – einen zweiten Verschiebeoperator (5), der in Reihe mit einer Ein-Bit-Verzögerungsschaltung (6) zwischen dem Ausgang des ersten Verschiebeoperators (4), der die Folge der Werte x_n liefert, und einem zweiten Eingang des Additionsoperators (3) gekoppelt ist, – einen dritten Verschiebeoperator (7), der zwischen dem Ausgang der Ein-Bit-Verzögerungsschaltung (6) und einem dritten Operandeneingang des Additionsoperators (3) gekoppelt ist, und einen vierten Verschiebeoperator (8), um die Folge von Werten u_n an den ersten Operandeneingang des Additionsoperators (3) anzulegen.
Vorrichtung nach Anspruch 7, dadurch gekennzeichnet, daß der erste Verschiebeoperator (4) eine Verschiebung um r Bits nach rechts, der zweite Verschiebeoperator (5) eine Verschiebung um r Bits nach links, der dritte Verschiebeoperator (7) und der vierte Verschiebeoperator (8) eine Verschiebung um s Bits nach links erzeugt.
Vorrichtung nach den Ansprüchen 7 und 8, dadurch gekennzeichnet, daß sie Verschiebeoperatoren umfaßt, die jeweils Verschiebelängen von r = 4 und s = 0 Bits aufweisen.