Adaptive polling rate algorithm for SNMP-based network monitoring

[0002] This invention relates generally to the field of network management and in particular to a method for efficient polling of network hosts and resources and a network manager for implementing the same.

[0003] Referring to FIG. 1, identifying the various hosts and resources 13, 15 and 17-19, connected and available to a network 18 is a vital part of proper network management. Typically one host on the network is assigned the task of network manager (“NM”) 10, running appropriate software, while the remaining hosts and resources are identified as agents. The manager 10 will periodically request information from the agents using one of a variety of protocols, e.g. Simple Network Manager Protocol (“SNMP”) at the application layer, or Packet Internet Groper (“PING”) at the IP layer, and expect a response from each agent using the same protocol. This process is referred to as “polling.”

[0004] Efficient polling is becoming increasingly important with new bandwidth-intensive applications such as conferencing and web-push applications. Proper monitoring of the network can help deploy such applications. The collected traffic pattern of the network can be used to set and administer policies on application use, to configure intranet switches and routers, and to detect errant behavior. The challenge in polling is to be able to poll with high throughput, yet avoid intruding on the performance of user applications in the network.

[0005] Presently, the de facto network management software is marketed by Hewlett Packard under the trade name OpenView (“OV”) and described more fully in R. Sturm, “Q&A”, OpenView Advisor, pp. 11-13, 1(2) (March 1995), hereby incorporated by reference as if fully set forth herein. In operation, OV can transmit a maximum of N outstanding polls, where N is typically 3. For example, NM 10 may send a first poll to node 17. NM 10 will then wait a time-out period T₁, for a response. If no response is received, a second poll is sent to node 17 and NM 10 will wait a time-out period 2×T₁, for a response. This is repeated two more times with corresponding time-out periods of 4×T₁and 8×T₁, respectively. NM 10 resends the poll these four times with continuously increasing time-out periods in order to rule out that the lack of a response is due to network traffic. If after four attempts no response to the polls is received, NM 10 concludes that node 17 is unavailable to the network.

[0006] It has been reported that the foregoing method of polling network resources is inefficient and leads to network “freeze up” as for example when a succession of nodes are unresponsive. See, A. B. Bondi, “A Nonblocking Mechanism for Regulating the transmission of Network Management Polls” IM '97, pp. 565-80 (May 1997), hereby incorporated by reference as if fully set forth herein. One proposed solution to ameliorate the deficiencies of the OV method is described in Bondi, supra. As described more fully therein, a minimum time threshold τ is set under which no two polls can be transmitted, while the maximum number of polls parameter N of OV is eliminated. As a result, freeze up is avoided by removing the constraint of N and network traffic is managed with constraint τ. However, even this proposal suffers from its inability to provide feedback relating to network congestion. The ability of a poller to quickly adapt to congestion is becoming increasingly important. Newer applications require continual monitoring, for example, at a rate of 5% of network capacity. Such monitoring can cause a network that is already congested with user traffic to collapse.

[0007] Accordingly, the present invention provides an adaptive rate of polling which is sensitive to network congestion. In accordance with the invention the network resources are polled with a minimum rate of transmission to avoid “freeze up,” while also providing feedback as to network congestion. 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 based on earlier poll responses and changes in node status such as recently activated or deactivated nodes.

[0008] FIG. 1 is prior art diagram of a network of hosts and routers monitored by a network manager through polling.

[0009] FIG. 2 is a time line describing the polling rate adaptation of the present invention.

[0010] In accordance with the present invention a network manager begins an initial polling round at a rate R₀and a corresponding maximum number of hosts to be polled in a polling round, N_max. These initial parameters are typically based on engineering criteria. Thus for the initial round j=1, R_jis set equal to R₀and N_jis set equal to N_max. Using SNMP, the network manager sends a poll to each of N_jactive nodes, where polls to consecutive nodes are spaced by a time equal to 1/R_j, and as in OV, waits for an acknowledgment from each polled node for a period of time T¹. In one advantageous embodiment of the present invention T¹is set equal to 10 seconds. If an acknowledgment is not received within time T¹, another poll is sent and the NM waits for an acknowledgment for a period of time 2×T¹. This continues two more times for corresponding waiting periods of 4×T¹and 8×T¹, respectively. If after four polls a node does not respond it is taken off the list of active nodes that are used in the next immediate round j+1. A node is returned to the active list through well-known mechanisms like traps, as described more fully in J. Case, et al., “A Simple Network Management Protocol (SNMP)” RFC 1157, Network Working Group, IETF (1990), hereby incorporated by reference as if fully set forth herein.

[0011] Referring to FIG. 2, after the last node in round j is polled, round j+1 begins. Prior to polling further network resources, the network manager notes the number of active nodes after round j, as N_j+1, the polling rate of the prior round, R_j, and the congestion feedback which is derived from the received acknowledgments during round j. These parameters are then used to compute the polling rate R_j+1for round j+1, which entails estimating the network congestion from polls issued in round j.

[0012] In particular, a congestion metric {overscore (D_j)} is computed as the average delay over the resolved and outstanding polls. Polls are resolved when the node acknowledges the poll. They are outstanding when they have not been acknowledged but the NM has not concluded that the polled node is inactive. Thus the sum of the delays of acknowledged polls is added to the sum of the current timeout values of all outstanding delays and the result is divided by the number of outstanding and resolved polls. This metric represents the acknowledgment delay of the active polls.

[0013] With {overscore (D_j)}, congestion can be estimated by comparison with the levels of timeout described above. Thus for example, if {overscore (D_j)} is less than or equal to T¹, e.g. 10 seconds, the network is normally loaded and not experiencing congestion. For D{overscore (j_j)} greater than T¹but less than or equal to T², e.g. 20 seconds, the network is experiencing a first level of congestion. Similarly for the third and fourth levels of timeout, the network would be experiencing second and third levels of congestion, respectively. Each range of consecutive time-out values from a lower bound to a next upper bound, represents a level of congestion. Thus for four time-out values, there exists congestion levels 1 through 3, represented by the variable k.

[0014] This congestion feedback {overscore (D_j)} is used to adapt the polling rate at round j+1. In the presence of any level of congestion 1 through 3, i.e. T^k<{overscore (D_j)}≦T^k+1, the equation $R_{j+1}=\min \left(\frac{N_{j+1}}{N_{\max }}\times R_0,\frac{R_j}{2^k}\right)$

[0015] is used. The multiplicative factor of 2^−kcorresponds to the exponential growth of delay in the presence of congestion with a slight increase in throughput. Thus the polling rate must be reduced exponentially fast. As congestion increases the minimum of the above two terms is biased toward the right term which causes the polling rate to decrease. Furthermore, as nodes become inactive the desired period for polling a particular node can be maintained even at a slower polling rate since there are fewer nodes to poll within the same period of time. In this case the left term is biased as the new polling rate.

[0016] Under a normal load, however, where {overscore (D_j)} is less than or equal to T¹, the delay will grow approximately linearly with increased load. Thus to assure that the network will not become congested, the right most term of the right side of the equation is modified by setting k=0 and adding a ΔR which is typically a small fraction of R₀, for example R₀/10. Thus R_j+ΔR₀. In this way, the method of rate adaptive polling in accordance with the present invention maximizes the benefits of polling by maintaining a desired polling rate whenever possible and minimizes the undesirable effects of bandwidth congestion.

[0017] The foregoing merely illustrates the principles of the present invention. Those skilled in the art will be able to devise various modifications, which although not explicitly described or shown herein, embody the principles of the invention and are thus within its spirit.