a2) United States Patent
`US 6,173,323 Bl
`(10) Patent No.:
`Jan. 9, 2001
`(45) Date of Patent:
`Moghe
`
`US006173323B1
`
`(54) ADAPTIVE POLLING RATE ALGORITHM
`FOR SNMP-BASED NETWORK
`MONITORING
`
`(75)
`
`Inventor: Pratyush Moghe, Aberdeen, NJ (US)
`
`(73) Assignee: Lucent Technologies Inc., Murray Hill,
`NJ (US)
`
`(*) Notice:
`
`Under 35 U.S.C. 154(b), the term of this
`patent shall be extended for O days.
`
`(21) Appl. No.: 08/998,213
`
`(22)
`
`Filed:
`
`Dec. 24, 1997
`
`(92) Mel? ssccscanseen GO06F 15/16; GO6F 15/173
`
`(52) US. CI. ceceeccscssessssseee 709/224; 709/235; 709/225;
`340/825.07; 340/825.55; 379/92.01
`(53) Pield of Seareht siccccccasncain 709/224, 226,
`709/235, 227; 340/825.07, 825.08, 825.55;
`372/220; 710/220; 379/92.01
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`4,598,363 *
`4,689,619 *
`4,905,233 *
`5,084,875 *
`5,193,151 *
`5,276,677 *
`5,633,859 *
`5,659,787 *
`5,896,561 *
`5,922,051 *
`
`7/1986 Clark et al. ccccescceeceeeneee 364/200
`
`8/1987 O'Brien ....
`. 340/825.08
`2/1990 Cain et al.
`s.ccccccssseseseeseens 370/237
`
`1/1992 Weinberger et al... 714/46
`3/1993 Jain et al. veces
`ve 709/237
`
`
`a. 370/232
`1/1994 Ramamurthy et al.
`............
`ww. 370/234
`5/1997 Jain et al.
`
`w+ 709/226
`8/1997 Schieltz .....
`4/1999 Schrader et al.
`» 455/67,1
`F/1999 Sidey w..cccecccsesscseeseeseresenes 709/223
`OTHER PUBLICATIONS
`
`A multiple access scheme for Wireless access to a broadband
`ATM LANpolling and sectored antennas, Mahmoud, A.S.;
`Mahmoud, $.A.; Falconer, D.D. Dept. of Syst. & Compt.
`
`Eng. Carleton Univ., Ottawa, Ont. Canada, pp. 596-608,
`May, 1996.*
`Adaptive polling schemes for an ATM bus, Karlsson, J.M.;
`Perros, H.G.; Viniotis, I., Center for Commun. & Signal
`Process, North Carolina State Univ., Raleigh, NC, USA,pp.
`403-407, ISBN: 0-7803-0006-8, May 1996.*
`J. Case et al., “A Simple Network Management Protocol
`(SNMP)”, RFC 1157, Network Working Group, IETF, 1990.
`R. Sturm, “Q&A”, Open View Advisor, pp. 11-13, 1(2),
`Mar. 1995,
`
`A.B. Bondi, “A nonblocking mechanism for regulating the
`transmission of network management polls”, IM’97, pp.
`565-580, May 1997.
`Analysis of symmetric nonexhaustive polling with multiple
`server, Marsanm, de Moraes, Donatelli, Neri, INFOCOM
`‘00 May 6,1990.*
`
`* cited by examiner
`
`Primary Examiner—Mark H. Rinehart
`Assistant Examiner—Beatriz Prieto
`
`(57)
`
`ABSTRACT
`
`A rate adaptive polling method sensitive to network con-
`gestion is used to monitor network resources. Initially, a
`baseline rate constraint is set based on desirable engineering
`factors. Unacknowledged polls are retransmitted with
`limeouts, 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 feed-
`back is estimated from a congestion metric computed as the
`average delay of all active nodes. Depending on the value of
`the congestion metric correspondingto polling round R,, the
`minimum rate ofpolling for round R,,, is adapted accord-
`ingly.
`
`8 Claims, 1 Drawing Sheet
`
`POLLING ROUND j+4 WITH Nj 44 POLLS
`POLLING ROUND j WITH N; POLLS
`
`7-~POLLS FROH--s
`NMS
`.
`
`/
`
`|
`
`RATE ESTIMATION
`FOR ROUND j
`
`RATE ESTIMATION
`FOR ROUND j+4
`
`RATE ESTIMATION
`FOR ROUND j+#2
`
`001
`
`Apple Inc.
`APL1119
`U.S. Patent No. 8,724,622
`
`001
`
`Apple Inc.
`APL1119
`U.S. Patent No. 8,724,622
`
`

`

`U.S. Patent
`
`Jan. 9, 2001
`
`US 6,173,323 BI
`
`4
`FIG.
`(PRIOR ART)
`
`10
`
`
`
`
`
`
`POLLING
`
`FIG. 2
`
`POLLING ROUND j+4 WITH Ni44 POLLS
`POLLING ROUND } WITH Nj POLLS
`
`
`777 POLLS FROM--»,
`NMS
`
`é
`
`\
`
`‘ !
`
`t
`RATE ESTIMATION
`FOR ROUND j+2
`
`RATE ESTIMATION
`FOR ROUND j
`
`RATE ESTIMATION
`FOR ROUND j+4
`
`002
`
`002
`
`

`

`US 6,173,323 B1
`
`1
`ADAPTIVE POLLING RATE ALGORITHM
`FOR SNMP-BASED NETWORK
`MONITORING
`
`TECHNICAL FIELD
`
`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.
`BACKGROUNDOF THE INVENTION
`
`15
`
`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 LO will periodically request informa-
`tion from the agents using one of a variety of protocols,e.g.
`Simple Network Manager Protocol (“SNMP”) at the appli-
`cation layer, or Packet Internet Groper (“PING”) at the IP 2
`layer, and expect a response from each agent using the same
`protocol. This process is referred to as “polling.”
`Efficient polling is becoming increasingly important with
`new bandwidth-intensive applications such as conferencing
`and web-push applications. Proper monitoring of the net-
`work 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.
`
`30
`
`Presently, the de facto network management software is
`marketed by Hewlett Packard under the trade name Open-
`View (“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 2xT,, for a response. This is repeated two
`more times with corresponding time-out periods of 4xT, and
`&xT,, 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 networktraffic.
`If after four attempts no response to the polls is received,
`NM 10 concludes that node 17 is unavailable to the network.
`It has been reportedthat the foregoing method of polling
`network resourcesis inefficient and leads to network “freeze
`up” as for example when a succession of nodes are unre-
`sponsive. 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 methodis described
`in Bondi, supra. As described more fully therein, a minimum
`time threshold t is set under which no two polls can be
`transmitted, while the maximum numberofpolls parameter
`N of OV ts eliminated. As a result, freeze up is avoided by
`removing the constraint of N and network traffic is managed
`with constraint t. However, even this proposal suffers from
`its inability to provide feedback relating to network conges-
`tion. 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.
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`003
`
`2
`SUMMARY OF THE INVENTION
`
`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 conges-
`tion. 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 onearlier poll
`responses and changes in node status such as recently
`activated or deactivated nodes.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 is prior art diagram of a network of hosts and
`routers monitored by a network manager through polling.
`FIG. 2 is a time line describing the polling rate adaptation
`of the present invention.
`DETAILED DESCRIPTION OF THE
`INVENTION
`
`In accordance with the present invention a network man-
`ager begins an initial polling round at a rate R, and a
`corresponding maximum numberof hosts to be polled in a
`polling round, N,,,,,. These initial parameters are typically
`based on engineering criteria. Thus for the initial round j=1,
`R, is set equal
`to Ry and N, is set equal to N,,,,.... Using
`SNMP,the network manager sendsa poll to each of N, active
`nodes, where polls to consecutive nodes are spaced by a time
`equal to 1/R,, and as in OV, waits for an acknowledgment
`from each polled node for a period of time T'. In one
`advantageous embodimentofthe present invention T"is set
`equal to 10 seconds. If an acknowledgmentis not received
`within time T’, anotherpoll is sent and the NM waits for an
`acknowledgmentfor a period of time 2xT". This continues
`two more times for corresponding waiting periods of 4xT"
`and 8xT", respectively. If after four polls a node does not
`respondit 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 Work-
`ing Group, IETF (1990), hereby incorporated by reference
`as if fully set forth herein.
`Referring to FIG, 2, after the last node in roundj is polled,
`round j+1 begins. Prior to polling further network resources,
`the network managernotes the number of active nodesafter
`roundj, as N,,,, the polling rate of the prior round, R,, and
`the congestion feedback whichis derived from the received
`acknowledgments during round j. These parameters are then
`used to computethe polling rate R,,, for round j+1, which
`entails estimating the network congestion from polls issued
`in round j.
`In particular, a congestion metric D; is computed as the
`average delay over the resolved and outstanding polls. Polls
`are resolved when the node acknowledgesthe 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 ofthe delays of acknowledged polls is added to the
`sum of the current timeout valuesofall 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.
`With D,, congestion can be estimated by comparison with
`the levels of timeout described above. Thus for example,if
`D, is less than or equal to T’, e.g. 10 seconds, the network
`is normally loaded and not experiencing congestion. For D
`
`003
`
`

`

`US 6,173,323 B1
`
`3
`j; greater than T’ butless 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 |
`through 3, represented by the
`variable k.
`This congestion feedback D; is used to adapt the polling
`rate at round j+1. In the presence of any level of congestion
`1 through 3, ic. T*<D;ST**",the equation
`
`fel
`si = mi5max,
`ie
`
`x Ro.
`
`Ry
`Tm
`
`R
`
`remaining at
`
`4
`determining the numberofactive nodes N;.,,
`the conclusion of each round j; and
`removing each node that hasfailed to acknowledge a poll
`after said four successive polls, from saidlist of active
`polls.
`4. A method according to claim 3 wherein said adapting
`step assigns a value to R;,, equal to the lesser of
`
`
`x Ro,
`
`and
`
`R;
`
`5
`
`15
`
`
`Nia
`Niax
`
`x Ro
`
`is used. The multiplicative factor of 2~* correspondsto the
`exponential growth of delay in the presence of congestion
`where T*<D;=1T*", whereinkis an integer and hasa value
`with a slight increase in throughput. Thus the polling rate
`must be reduced exponentially fast. As congestion increases
`teo
`at least equal to 1, and assigns a value to R,,, equal to the
`the minimum of the above two terms is biased toward the
`lesser of
`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
`slowerpolling rate since there are fewer nodesto poll within
`the same period oftime. In this case theleft term is biased
`and Rj+AR, where D;ST".
`as the new polling rate.
`5. A computer implemented network manager for moni-
`Under a normal load, however, where D; is less than or
`toring network nodes with a minimum polling rate per round
`equal to T', the delay will grow approximately linearly with
`J, R,, comprising:
`increased load. Thus to assure that
`the network will not
`means for polling said nodes during each round at said
`become congested, the right most term of the night side of
`rate R; where R; equals R, for initial round;
`the equation is modified by setting k=0 and adding a AR
`means for estimating congestion in said network experi-
`which is typically a small fraction of R,, for example R,/10.
`enced during said round j;
`Thus R,+ARo.
`In this way,
`the method of rate adaptive
`polling in accordance with the present invention maximizes
`meansfor adapting the polling rate for round j+1 based on
`the benefits of polling by maintaining a desired polling rate 3
`said estimated congestion during roundj, said adapted
`whenever possible and minimizes the undesirable effects of
`polling rate represented as R,,,; and
`bandwidth congestion.
`means for polling said nodes during round j+1 at said
`The foregoing merely illustrates the principles of the
`adapted polling rate R;,..
`present invention. Those skilled in the art will be able to
`6. The computer implemented network manager of claim
`devise various modifications, which although not explicitly
`5 wherein R; is set initially to Ro, and wherein said means
`described or shown herein, embody the principles of the
`for estimating further comprising means for computing a
`invention and are thus within its spirit.
`congestion metric D; as the average delay overall resolved
`Whatis claimedis:
`and outstanding polls.
`1. A method for monitoring network nodes with a mini-
`7. The computer implemented network manager of claim
`mum polling rate per round j, R,, said method comprising the
`6 wherein said network comprises an initial maximum
`steps of:
`number of nodes to be polled in a round, N,,,,. said network
`polling said nodes during each round at said rate R, where
`manager further comprising a list of active nodes, said first
`R; equals Ro for said initial round;
`recited and second recited means for polling further com-
`estimating congestion in said network experienced during
`prising:
`said roundj;
`lransmitting up to four successive polls to each node
`adapting the polling rate for round j+1 based on said
`where said node fails to acknowledge a prior poll
`estimated congestion during round j, said adapted poll-
`within a predetermined period oftime T’ and wherein
`ing rate for round j+1 represented as R,,,; and
`T’ increases by a factor of 2 for each successive poll;
`setting j=(j+1) and repeating said polling, estimating and
`determining the numberofactive nodes N;,;
`remaining at
`adapting steps.
`the conclusion of each round; and
`2. Amethod according to claim 1 wherein R, is set initially
`removing each node that has failed to acknowledgeapoll
`to R,, and said estimating step further comprising the step of
`after said four successive polls, from saidlist of active
`compuling a congestion metric Dj as the average delay over
`polls.
`all resolved and outstanding polls.
`8. The computer implemented network manager of claim
`3. A method according to claim 2 wherein said network
`7 wherein said means for adapting includes means for
`comprises an initial maximum numberof nodes to be polled
`assigning a value to R;,, equal to the lesser of
`in a round, N,,,,.. said method further comprising a list of
`active nodes,said polling steps further comprising the steps
`1Y fel—— xR
`of:
`Nex
`
`40
`
`50
`
`55
`
`60
`
`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 cach successivepoll;
`
`65
`
`and
`
`004
`
`004
`
`

`

`US 6,173,323 B1
`
`Nia
`
`where T*<DjsT™, whereinkis an integer and has a value “and Rj+AR, where D,ST".
`at least equal to 1, and meansfor assigning a value to R,,,
`x
` #
`*
`#
`equal to the lesser of
`
`005
`
`005
`
`