Rate monitoring of connections in a communications network using history buffer

• US 6,519,264 B1
• Filed: 04/26/1999
• Issued: 02/11/2003
• Est. Priority Date: 05/28/1998
• Status: Expired due to Term

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Alcatel Canada Inc. (Nokia Corporation)
• Inventors: Lee, Denny L. S., Sterne, Jason T., Carr, David W.
• Primary Examiner(s): Kizou, Hassan
• Assistant Examiner(s): ODLAND, DAVID E
• Application Number:
  US09/298,788
• Time in Patent Office: 1,387 Days
• Field of Search: 370/229, 370/230, 370/231, 370/232, 370/233, 370/235, 370/236, 370/253, 370/433, 370/310.1, 370/346, 370/449, 370/384, 370/395.1, 370/395--39, 370/422, 370/429, 370/450, 375/224, 375/225, 375/242, 375/371, 709/224, 709/227
• US Class Current: 370/449
• CPC Class Codes: H04L 12/5601 Transfer mode dependent, e.g. ATM
• CPC Class Codes: H04L 41/5003 Managing SLA; Interaction between SLA and QoS
• CPC Class Codes: H04L 43/024 by adaptive sampling
• CPC Class Codes: H04L 43/0882 Utilisation of link capacity
• CPC Class Codes: H04L 43/0894 Packet rate

Abstract

There is provided a method and device for measuring a rate of message element traffic over a message path in a communications network. The path includes at least one connection and is associated with a maximum rate of transmission. The path is periodically polled for transmission of a message element, the polling being performed at a polling rate associated with polling intervals which are at least as frequent as the maximum rate of transmission. If transmission of a message element is detected during a polling interval, a running count of such detection is incremented, the running count of detection being associated with the connection over which the message element was detected. If transmission of a message element is not detected, a running count of such non-detection is incremented, the running count of non-detection being associated with inactivity of the message path. During each polling interval, an oldest stored value is retrieved from a memory which includes a preselected number of stored values that correspond to an equal number of most recent sequential events of detection and non-detection. Each stored value which represents an event of detection corresponds to an identifier denoting the connection over which the message element was detected. Each stored value which represents an event of non-detection corresponds to an identifier denoting inactivity of the message path. Following retrieval during each polling interval, the running count of detection associated with the connection corresponding to the identifier of the retrieved value is decremented if the retrieved value represents an event of detection. The running count of non-detection is decremented if the retrieved value represents inactivity. The retrieved value is thereafter replaced with a value corresponding to an identifier which denotes the connection over which the message element was detected if transmission was detected. Otherwise the retrieved value is replaced in the memory with a value corresponding to an identifier which denotes inactivity if transmission was not detected. The foregoing steps are repeated for so long as the measurement is undertaken. The rate of message element traffic over a connection of the message path is proportional to the running count of detection associated with the connection.

Claims

1. A method of measuring a rate of message element traffic over a message path in a communications network, the message path including at least one connection and being associated with a maximum rate of transmission of message elements thereover, the method comprising the steps of:

(a) periodically polling the message path for transmission of a message element, the periodic polling being performed at a polling rate associated with polling intervals which are at least as frequent as the maximum rate of transmission;

(b) if transmission of a message element is detected during a said polling interval, incrementing a running count of such detection, the running count of detection being associated with the connection over which the message element was detected;

(c) if transmission of a message element is not detected during a said polling interval, incrementing a running count of such non-detection, the running count of non-detection being associated with inactivity of the message path;

(d) during each said polling interval, retrieving an oldest stored value from a memory comprising a preselected number of stored values each corresponding respectively to an equal number of most recent sequential events of detection and non-detection resulting from said periodic polling, wherein each stored value which represents an event of detection corresponds to an identifier denoting the connection over which the message element was detected and wherein each stored value which represents an event of non-detection corresponds to an identifier denoting inactivity of the message path;

(e) following step (d) and during each said polling interval, decrementing the running count of detection associated with the connection corresponding to the identifier of the retrieved value if the retrieved value represents an event of detection and decrementing the running count of non-detection if the retrieved value represents inactivity of the message path;

(f) following step (e) and during each said polling interval, replacing in the memory the retrieved value with a value corresponding to an identifier which denotes the connection over which the message element was detected if transmission of a message element was detected in step (b) and otherwise replacing in the memory the retrieved value with a value corresponding to an identifier which denotes inactivity of the message path if transmission of a message element was not detected in step (c);

(g) repeating each of steps (a) through (f) for so long as said measurement is undertaken; and

wherein the rate of message element traffic over a connection of the message path is proportional to the running count of detection associated with the connection.

2. The method of measuring a rate of message element traffic according to claim 1, wherein the memory is a buffer in which each of the stored values is ordered chronologically from the oldest stored value to a most recently stored value, the memory having a pointer which denotes the oldest stored value during each polling interval, the pointer denoting a next oldest sequential stored value in the buffer once the oldest stored value has been retrieved therefrom according to step (d) and has been replaced according to step (e).

3. The method of measuring a rate of message element traffic according to claim 2, wherein the pointer is associated with an index which is incremented to denote the next oldest sequential stored value pursuant to a modulo L counter, where L corresponds to the preselected number of stored values in the buffer.

4. The method of measuring a rate of message element traffic according to claim 2, wherein the buffer is a ring buffer.

5. The method of measuring a rate of message element traffic according to claim 2, wherein the message path comprises a plurality of connections and wherein a like plurality of running counts of detection are provided therefor, each of the connections corresponding respectively to a separate running count of detection.

6. The method of measuring a rate of message element traffic according to claim 5, wherein the communications network is an Asynchronous Transfer Mode (ATM) network and the message elements are ATM cells.

7. The method of measuring a rate of message element traffic according to claim 6, wherein the message path is a virtual path and the connections are virtual connections.

8. The method of measuring a rate of message element traffic according to claim 6, comprising the further step of declaring a connection as being inactive when the running count of detection for the connection transitions from a value of 1 to a value of 0 and of declaring a connection as being active when the running count of detection for the connection transitions from a value of 0 to a value of 1.

9. The method of measuring a rate of message element traffic according to claim 6, wherein the identifier denoting inactivity of the message path is a value of 0.

10. The method of measuring a rate of message element traffic according to claim 9, wherein the value corresponding to the identifier denoting the connection over which the message element was detected is an ATM cell connection identifier and wherein the method further includes the step of reading the ATM cell connection identifier upon such detection of transmission.

21. The method of measuring a rate of message element traffic according to claim 1, wherein the rate of message element traffic over a connection of the message path is computed as the product of the running count of detection associated with the connection and the quotient represented by the polling rate divided by the preselected number of stored values.

11. An apparatus for measuring a rate of message element traffic over a message path in a communications network, the message path including at least one connection and being associated with a maximum rate of transmission of message elements thereover, the apparatus comprising:

(a) an input port for receiving message elements which are transmitted over the message path;

(b) a timer producing a clock rate which is at least as frequent as the maximum rate of transmission;

(c) a processor for periodically polling the input port for transmission of a message element, the periodic polling being performed at polling intervals which are synchronized to the clock rate of the timer and;

(c.1) if transmission of a message element is detected during a polling interval, wherein the processor increments a running count of such detection, the running count of detection being associated with the connection over which the message element was detected; and

(c.2) if transmission of a message element is not detected during a polling interval, wherein the processor increments a running count of such non-detection, the running count of non-detection being associated with inactivity of the message path;

(d) a memory accessible by said processor and comprising a preselected number of stored values each corresponding respectively to an equal number of most recent sequential events of detection and non-detection resulting from said periodic polling, each stored value which represents an event of detection corresponding to an identifier denoting the connection over which the message element was detected and each stored value which represents an event of non-detection corresponding to an identifier denoting inactivity of the message path, and wherein;

(d.1) during each polling interval the processor retrieves an oldest stored value from the memory and decrements the running count of detection associated with the connection corresponding to the identifier of the retrieved value if the retrieved value represents an event of detection and decrements the running count of non-detection if the retrieved value represents inactivity of the message path;

(d.2) after decrementing such running count and during the same polling interval, the processor replaces the retrieved value in the memory with a value corresponding to an identifier which denotes the connection over which the message element was detected if transmission of a message element was detected over the input port during the same polling interval and otherwise the processor replaces in the memory the retrieved value with a value corresponding to an identifier which denotes inactivity of the message path if transmission of a message element was not detected over the input port during the same polling interval; and

wherein the rate of message element traffic over a connection of the message path is proportional to the running count of detection associated with the connection.

12. The apparatus for measuring a rate of message element traffic according to claim 11, wherein the memory is a buffer in which each of the stored values is ordered chronologically from the oldest stored value to a most recently stored value, the memory having a pointer which denotes the oldest stored value during each polling interval, the pointer denoting a next oldest sequential stored value in the buffer once the oldest stored value has been retrieved therefrom and has been replaced as aforesaid.

13. The apparatus for measuring a rate of message element traffic according to claim 12, wherein the pointer is associated with an index which is incremented to denote the next oldest sequential stored value pursuant to a modulo L counter, where L corresponds to the preselected number of stored values in the buffer.

14. The apparatus for measuring a rate of message element traffic according to claim 12, wherein the buffer is a ring buffer.

15. The apparatus for measuring a rate of message element traffic according to claim 12, wherein the message path comprises a plurality of connections and wherein a like plurality of running counts of detection are provided therefor, each of the connections corresponding respectively to a separate running count of detection.

16. The apparatus for measuring a rate of message element traffic according to claim 15, wherein the communications network is an Asynchronous Transfer Mode (ATM) network and the message elements are ATM cells.

17. The apparatus for measuring a rate of message element traffic according to claim 16, wherein the message path is a virtual path and the connections are virtual connections.

18. The apparatus for measuring a rate of message element traffic according to claim 16, wherein a connection is declared inactive when the running count of detection for the connection transitions from a value of 1 to a value of 0 and wherein the connection is declared active when the running count of detection for the connection transitions from a value of 0 to a value of 1.

19. The apparatus for measuring a rate of message element traffic according to claim 16, wherein the identifier denoting inactivity of the message path is a value of 0.

20. The apparatus for measuring a rate of message element traffic according to claim 19, wherein the value corresponding to the identifier denoting the connection over which the message element was detected is an ATM cell connection identifier and wherein the processor reads the ATM cell connection identifier upon such detection of transmission.

22. The apparatus for measuring a rate of message element traffic according to claim 11, wherein the rate of message element traffic over a connection of the message path is computed as the product of the running count of detection associated with the connection and the quotient represented by the polling rate divided by the preselected number of stored values.

23. A method of measuring a rate of message element traffic over a message path in a communications network,, said message path including at least one flow of message element traffic and being associated with a maximum rate of transmission of message elements thereover, said message path being polled periodically for transmission of a message element, said polling being performed at a polling rate associated with polling intervals which are at least as frequent as said maximum rate of transmission, said method comprising the steps of:

(a) establishing a running count of non-detection of a message element transmitted over said message path, said running count of non-detection representing events of inactivity of said message path for a predetermined number of sequential polling intervals; and

(b) for each flow of message element traffic of said message path, establishing a respective running count of detection of a message element being transmitted therein each said running count of detection representing a number of events of detection of a message element transmitted in a corresponding flow of message element traffic for said predetermined number of sequential polling intervals; and

wherein said predetermined number of sequential polling intervals reflects, for every polling interval, most recent said events of detection and of inactivity of said message path, and wherein said rate of message element traffic in said corresponding flow of message element traffic of said message path for said predetermined number of sequential polling intervals is proportional to said running count of detection for said corresponding flow of message element traffic.

24. A method of measuring a rate of message element traffic over a message path in a communications network according to claim 23, wherein each said flow of message element traffic is a connection.

25. A method of measuring a rate of message element traffic over a message path in a communications network according to claim 24, wherein said most recent said events of detection and of inactivity of said message path are recorded in a memory respectively as (i) a value indicating non-detection of a message element for a corresponding polling interval of said predetermined number of polling intervals and (ii) a value indicating detection of a message element in a corresponding polling interval of said predetermined number of polling intervals.

26. A method of measuring a rate of message element traffic over a message path in a communications network according to claim 25, wherein said value indicating non-detection of a message element corresponds to an identifier denoting inactivity of said message path and said value indicating detection of a message element corresponds to an identifier denoting the connection over which the message element was detected.

27. A method of measuring a rate of message element traffic over a message path in a communications network according to claim 26, wherein said stop (a) establishes said running count of non-detection based on a number of said identifiers in said memory denoting inactivity of said message path and wherein said step (b), for each said connection, establishes said ring count of detection for said corresponding connection based on a number of said identifiers in said memory denoting said corresponding connection.

28. A method of measuring a rate of message element traffic over a message path in a communications network according to claim 27, said method further comprising the step of:

(c) during a current polling interval, retrieving an oldest stored identifier from said memory;

wherein said running count of non-detection is established during each said polling interval by;

(a1) decrementing said running count of non-detection following said step (c) if said identifier retrieved during said current polling interval represents inactivity of said message path; and

(a2) incrementing said running count of non-detection if transmission of a message element is not detected during said current polling interval;

and wherein said running counts of detection are established during each said polling interval by;

(b1) decrementing said running count of detection corresponding to said connection denoted by said retrieved identifier following said step (c) if said identifier retrieved during said current polling interval represents an event of detection; and

(b2) incrementing said running count of detection corresponding to said connection in which said message element is transmitted if transmission of a message element is detected during said cue polling interval.

29. A method of measuring a rate of message element traffic over a message path in a communications network according to claim 28, wherein recording said most recent said events of detection and of inactivity of said message path in said memory replace said retrieved identifier in said memory with one of said identifiers (i) and (ii) as aforesaid.