Detecting network instability

• US 6,918,067 B2
• Filed: 04/30/2002
• Issued: 07/12/2005
• Est. Priority Date: 04/30/2002
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Bartucca, Francis Michael, Jeffries, Clark Debs, Strole, Norman Clark, Slager, Rosemary Venema
• Primary Examiner(s): Baderman, Scott
• Assistant Examiner(s): PUENTE, EMERSON C
• Application Number:
  US10/135,296
• Publication Number:
  US 20030204787A1
• Time in Patent Office: 1,169 Days
• Field of Search: 714/4, 714/5, 714/6, 714/43, 714/47, 714/53, 714/763, 711/3, 370/229, 370/232, 709223-225
• US Class Current: 714/47.2
• CPC Class Codes: H04L 41/0681 Configuration of triggering conditions
• CPC Class Codes: H04L 43/0829 Packet loss
• CPC Class Codes: H04L 43/0894 Packet rate
• CPC Class Codes: H04L 43/16 Threshold monitoring

Abstract

A method, system and computer program product for detecting conditions of network instability. An attribute indicative of network instability, e.g., processor and/or co-processor utilization, packet arrival rates, packet peak rates, packet size distribution, packet clustering tendencies, buffer usage patterns, occurrence of peak utilization, out-of-buffer conditions, packet discard rates, may be monitored for a network device, e.g., router. The monitored attribute may be associated with a plurality of labels (variables) where a portion of those labels may be stored in a cache. A hit ratio for the cache storing labels associated with the monitored attribute may be tracked within a period of time based on the number of requested items, i.e., labels, that are currently stored in the cache. A condition of network instability may then be detected based on the hit ratio by determining if the absolute value of the acceleration of the hit ratio exceeds a threshold.

Claims

1. A method for detecting conditions of network instability comprising the steps of:

monitoring an attribute of a network device in relation to a receipt of a plurality of packets of data, wherein a plurality of labels are associated with said attribute, wherein a portion of said plurality of labels are stored in a cache;

tracking a hit ratio of said cache within a particular period of time based on a number of requested labels that are stored in said cache; and

detecting a condition of said network instability based on said hit ratio.

2. The method as recited in claim 1, wherein said condition of said network instability is detected based on an acceleration of said hit ratio.

3. The method as recited in claim 2, wherein if an absolute value of said acceleration of said hit ratio is greater than or equal to a threshold value then said condition of said network instability is detected.

4. The method as recited in claim 3, wherein said absolute value of said acceleration of said hit ratio is determined by an absolute value of a second derivative of said hit ratio.

5. The method as recited in claim 3, wherein said absolute value of said acceleration of said hit ratio is determined by an absolute value of:

(h(t−

2*dt)−

2*h(t−

dt)+h(t))/2,

wherein t is an index of time;

wherein dt is a time interval; and

wherein h(t) is said hit ratio at time t.

6. The method as recited in claim 3, wherein if said detection of said condition of said network instability is not a valid detection then said threshold value is increased to:

T(new)=(1−

K)*T(old)+K*MAX,

wherein K is a constant;

wherein T(old) is a threshold value prior to being increased;

wherein T(new) is a threshold value after being increased; and

wherein MAX is a maximum value.

7. The method as recited in claim 3, wherein if said detection of said condition of said network instability is a valid detection than said threshold value is unchanged.

8. The method as recited in claim 2, wherein if an absolute value of said acceleration of said hit ratio is less than a threshold value then said condition of said network instability is not detected.

9. The method as recited in claim 1, wherein said attribute monitored is at least one of the following:

processor utilization, packet arrival rates, packet peak rates, packet size distribution, packet clustering tendencies, buffer usage patterns, occurrence of peak utilization, out-of-buffer conditions and packet discard rates.

10. The method as recited in claim 1 further comprising the step of:

transmitting an alert indicating said detection of said condition of said network instability.

11. A computer program product embodied in a machine readable medium for detecting conditions of network instability comprising the programming steps of:

monitoring an attribute of a network device in relation to a receipt of a plurality of packets of data, wherein a plurality of labels are associated with said attribute, wherein a portion of said plurality of labels are stored in a cache;

tracking a hit ratio of said cache within a particular period of time based on a number of requested labels that are stored in said cache; and

detecting a condition of said network instability based on said hit ratio.

12. The computer program product as recited in claim 11, wherein said condition of said network instability is detected based on an acceleration of said hit ratio.

13. The computer program product as recited in claim 12, wherein if an absolute value of said acceleration of said hit ratio is greater than or equal to a threshold value then said condition of said network instability is detected.

14. The computer program product as recited in claim 13, wherein said absolute value of said acceleration of said hit ratio is determined by an absolute value of a second derivative of said hit ratio.

15. The computer program product as recited in claim 13, wherein said absolute value of said acceleration of said hit ratio is determined by an absolute value of:

(h(t−

2*dt)−

2*h(t−

dt)+h(t))/2,

wherein t is an index of time;

wherein dt is a time interval; and

wherein h(t) is said hit ratio at time t.

16. The computer program product as recited in claim 13, wherein if said detection of said condition of said network instability is not a valid detection then said threshold value is increased to:

T(new)=(1−

K)*T(old)+K*MAX,

wherein K is a constant;

wherein T(old) is a threshold value prior to being increased;

wherein T(new) is a threshold value after being increased; and

wherein MAX is a maximum value.

17. The computer program product as recited in claim 13, wherein if said detection of said condition of said network instability is a valid detection than said threshold value is unchanged.

18. The computer program product as recited in claim 12, wherein if an absolute value of said acceleration of said hit ratio is less than a threshold value then said condition of said network instability is not detected.

19. The computer program product as recited in claim 11, wherein said attribute monitored is at least one of the following:

processor utilization, packet arrival rates, packet peak rates, packet size distribution, packet clustering tendencies, buffer usage patterns, occurrence of peak utilization, out-of-buffer conditions and packet discard rates.

20. The computer program product as recited in claim 11 further comprising the programming step of:

transmitting an alert indicating said detection of said condition of said network instability.

21. A system, comprising:

a memory unit operable for storing a computer program operable for detecting conditions of network instability; and

a processor coupled to said memory unit, wherein said processor, responsive to said computer program, comprises;

circuitry operable for monitoring an attribute of a network device in relation to a receipt of a plurality of packets of data, wherein a plurality of labels are associated with said attribute, wherein a portion of said plurality of labels are stored in a cache;

circuitry operable for tracking a hit ratio of said cache within a particular period of time based on a number of requested labels that are stored in said cache; and

circuitry operable for detecting a condition of said network instability based on said hit ratio.

22. The system as recited in claim 21, wherein said condition of said network instability is detected based on an acceleration of said hit ratio.

23. The system as recited in claim 22, wherein if an absolute value of said acceleration of said hit ratio is greater than or equal to a threshold value then said condition of said network instability is detected.

24. The system as recited in claim 23, wherein said absolute value of said acceleration of said hit ratio is determined by an absolute value of a second derivative of said hit ratio.

25. The system as recited in claim 23, wherein said absolute value of said acceleration of said hit ratio is determined by an absolute value of:

(h(t−

2*dt)−

2*h(t−

dt)+h(t))/2,

wherein t is an index of time;

wherein dt is a time interval; and

wherein h(t) is said hit ratio at time t.

26. The system as recited in claim 23, wherein if said detection of said condition of said network instability is not a valid detection then said threshold value is increased to:

T(new)=(1−

K)*T(old)+K*MAX,

wherein K is a constant;

wherein T(old) is a threshold value prior to being increased;

wherein T(new) is a threshold value after being increased; and

wherein MAX is a maximum value.

27. The system as recited in claim 23, wherein if an absolute value of said acceleration of said hit ratio is less than a threshold value then said condition of said network instability is not detected.

28. The system as recited in claim 22, wherein if an absolute value of said acceleration of said hit ratio is less than a threshold value then said condition of said network instability is not detected.

29. The system as recited in claim 21, wherein said attribute monitored is at least one of the following:

processor utilization, packet arrival rates, packet peak rates, packet size distribution, packet clustering tendencies, buffer usage patterns, occurrence of peak utilization, out-of-buffer conditions and packet discard rates.

30. The system as recited in claim 21, wherein said processor further comprises:

circuitry operable for transmitting an alert indicating said detection of said condition of said network instability.