Adaptive polling rate algorithm for SNMP-based network monitoring

• US 6,173,323 B1
• Filed: 12/24/1997
• Issued: 01/09/2001
• Est. Priority Date: 12/24/1997
• Status: Expired due to Term

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Moghe, Pratyush
• Primary Examiner(s): Rinehart, Mark H.
• Assistant Examiner(s): Prieto, Beatriz
• Application Number:
  US08/998,213
• Time in Patent Office: 1,112 Days
• Field of Search: 709/224, 709/226, 709/235, 709/227, 340/825.07, 340/825.08, 340/825.55, 372/220, 710/220, 379/92.01
• US Class Current: 709/224
• CPC Class Codes: H04L 43/0817 by checking functioning
• CPC Class Codes: H04L 43/0852 Delays
• CPC Class Codes: H04L 43/10 Active monitoring, e.g. heartbeat, ping or trace-route
• CPC Class Codes: H04L 43/103 with adaptive polling, i.e. dynamically adapting the polling rate

Abstract

A rate adaptive polling method sensitive to network congestion is used to monitor network resources. Initially, a baseline rate constraint is set based on desirable engineering factors. Unacknowledged polls are retransmitted with timeouts, successively increasing by a factor of 2. During each polling round, the rate is adapted in accordance with congestion feedback and changes in node status such as recently activated or deactivated nodes. Congestion feedback is estimated from a congestion metric computed as the average delay of all active nodes. Depending on the value of the congestion metric corresponding to polling round R_j, the minimum rate of polling for round R_j+1 is adapted accordingly.

Claims

1. A method for monitoring network nodes with a minimum polling rate per round j, R_j, said method comprising the steps of:

polling said nodes during each round at said rate R_j where R_j equals R₀ for said initial round;

estimating congestion in said network experienced during said round j;

adapting the polling rate for round j+1 based on said estimated congestion during round j, said adapted polling rate for round j+1 represented as R_j+1; and

setting j=(j+1) and repeating said polling, estimating and adapting steps.

2. A method according to claim 1 wherein R_j is set initially to R₀, and said estimating step further comprising the step of computing a congestion metric {overscore (D_j)} as the average delay over all resolved and outstanding polls.

3. A method according to claim 2 wherein said network comprises an initial maximum number of nodes to be polled in a round, N_max, said method further comprising a list of active nodes, said polling steps further comprising the steps of:

transmitting up to four successive polls to each node where said node fails to acknowledge a prior poll within a predetermined period of time T¹ and wherein T¹ increases by a factor of 2 for each successive poll;

determining the number of active nodes N_j+1 remaining at the conclusion of each round j; and

removing each node that has failed to acknowledge a poll after said four successive polls, from said list of active polls.

4. A method according to claim 3 wherein said adapting step assigns a value to R_j+1 equal to the lesser of $\frac{N_{j+1}}{N_{\max }}\times$

R0, 

and $\frac{R_j}{2^k}$

where T^k<

{overscore (D_j)}≦

T^k+1, wherein k is an integer and has a value at least equal to 1, and assigns a value to R_j+1 equal to the lesser of $\frac{N_{j+1}}{N_{\max }}\times <br><br>R_0$

and R_j+Δ

R₀ where {overscore (D_j)}≦

T¹.

5. A computer implemented network manager for monitoring network nodes with a minimum polling rate per round j, R_j, comprising:

means for polling said nodes during each round at said rate R_j where R_j equals R₀ for initial round;

means for estimating congestion in said network experienced during said round j;

means for adapting the polling rate for round j+1 based on said estimated congestion during round j, said adapted polling rate represented as R_j+1; and

means for polling said nodes during round j+1 at said adapted polling rate R_j+1.

6. The computer implemented network manager of claim 5 wherein R_j is set initially to R₀, and wherein said means for estimating further comprising means for computing a congestion metric {overscore (D_j)} as the average delay over all resolved and outstanding polls.

7. The computer implemented network manager of claim 6 wherein said network comprises an initial maximum number of nodes to be polled in a round, N_max, said network manager further comprising a list of active nodes, said first recited and second recited means for polling further comprising:

transmitting up to four successive polls to each node where said node fails to acknowledge a prior poll within a predetermined period of time T¹ and wherein T¹ increases by a factor of 2 for each successive poll;

determining the number of active nodes N_j+1 remaining at the conclusion of each round; and

removing each node that has failed to acknowledge a poll after said four successive polls, from said list of active polls.

8. The computer implemented network manager of claim 7 wherein said means for adapting includes means for assigning a value to R_j+1 equal to the lesser of $\frac{N_{j+1}}{N_{\max }}\times$

R0 

and $\frac{R_j}{2^k}$

where T^k<

{overscore (D_j)}≦

T^k+1, wherein k is an integer and has a value at least equal to 1, and means for assigning a value to R_j+1 equal to the lesser of $\frac{N_{j+1}}{N_{\max }}\times <br><br>R_0$

and R_j+Δ

R₀ where {overscore (D_j)}≦

T¹.