(12) United States Patent
`Moghe
`
`I IIIII IIIIIIII Ill lllll lllll lllll lllll lllll lllll lllll lllll 111111111111111111
`US006173323Bl
`US 6,173,323 Bl
`Jan.9,2001
`
`(10) Patent No.:
`(45) Date of Patent:
`
`(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
`
`Int. Cl.7 ........................... G06F 15/16; G06F 15/173
`(51)
`(52) U.S. Cl. .......................... 709/224; 709/235; 709/225;
`340/825.07; 340/825.55; 379/92.01
`(58) Field of Search ..................................... 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 * 7/1986 Clark et al. .......................... 364/200
`4,689,619 * 8/1987 O'Brien .......................... 340/825.08
`4,905,233 * 2/1990 Cain et al. ........................... 370/237
`5,084,875 * 1/1992 Weinberger et al.
`.................. 714/46
`5,193,151 * 3/1993 Jain et al.
`............................ 709/237
`5,276,677 * 1/1994 Ramamurthy et al. .............. 370/232
`5,633,859 * 5/1997 Jain et al.
`............................ 370/234
`5,659,787 * 8/1997 Schieltz ................................ 709/226
`5,896,561 * 4/1999 Schrader et al. .................... 455/67.1
`5,922,051 * 7/1999 Sidey ................................... 709/223
`
`OTHER PUBLICATIONS
`
`A multiple access scheme for Wireless access to a broadband
`ATM LAN polling and sectored antennas, Mahmoud, AS.;
`Mahmoud, S.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.;
`Perras, 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.
`AB. 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
`'90 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(cid:173)
`gestion 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 feed(cid:173)
`back 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 Rj, the
`minimum rate of polling for round Rj+l is adapted accord(cid:173)
`ingly.
`
`8 Claims, 1 Drawing Sheet
`
`POLLING ROUND j WITH Nj POLLS
`
`POLLING ROUND j+1 WITH Nj+1 POLLS
`
`r - - POLLS FROM --,
`NMS
`\
`/
`R-1
`j
`
`\
`
`\
`
`NODE 1
`
`-1
`Rj+i
`NODE 2
`
`TIME
`
`I
`
`I
`NODE 1
`
`'
`
`NODE 2
`
`I
`
`I '
`
`RATE ESTIMATION
`FOR ROUND
`j
`
`I
`
`I '
`
`RATE ESTIMATION
`FOR ROUND j+1
`
`I
`
`I '
`
`RATE ESTIMATION
`FOR ROUND j+2
`
`Facebook's Exhibit No. 1019/1119
`Page 1
`
`

`

`U.S. Patent
`
`Jan.9,2001
`
`US 6,173,323 Bl
`
`FIG. 1
`(PRIOR ART)
`
`10
`
`NM
`
`15
`
`OTHER
`
`POLLS •
`
`: ROUTER 2
`
`I
`
`POLLING
`MESSAGES
`1---------..a I
`I 1----------J
`I
`I
`
`I
`
`I I
`
`I
`
`I
`
`I
`I
`I
`I
`.. ______ J
`
`I
`
`I
`
`I L------------~
`----------,
`1.I !.------
`
`18
`
`SUBNET
`
`19
`
`17
`
`18
`
`ROUTER 1
`
`' OTHER
`
`POLLS
`
`13
`
`FIG. 2
`
`POLLING ROUND j WITH Nj POLLS
`
`POLLING ROUND j+i WITH Nj+i POLLS
`
`r - - POLLS FROM --,
`NMS
`\
`I
`I
`1 \
`I
`-
`\ I
`j
`R
`
`/
`
`1
`1
`
`I
`:
`I
`I
`I
`If
`NODE 1
`
`NODE 2
`
`I
`
`I '
`
`RATE ESTIMATION
`FOR ROUND j
`
`I
`
`:
`
`\
`
`NODE 1
`
`-1
`Rj+1
`NODE 2
`
`TIME
`
`I
`
`I '
`
`RATE ESTIMATION
`FOR ROUND j+1
`
`I
`
`I '
`
`RATE ESTIMATION
`FOR ROUND j+2
`
`Facebook's Exhibit No. 1019/1119
`Page 2
`
`

`

`US 6,173,323 Bl
`
`2
`SUMMARY OF THE INVENTION
`
`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.
`
`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
`5 polled with a minimum rate of transmission to avoid "freeze
`up," while also providing feedback as to network conges(cid:173)
`tion. Initially, a baseline rate constraint is set based on
`desirable engineering factors. Unacknowledged polls are
`retransmitted with timeouts, successively increasing by a
`10 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.
`
`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
`
`45
`
`In accordance with the present invention a network man(cid:173)
`ager begins an initial polling round at a rate R0 and a
`corresponding maximum number of hosts to be polled in a
`polling round, Nmax· These initial parameters are typically
`based on engineering criteria. Thus for the initial round j=l,
`Rj is set equal to R0 and Nj is set equal to Nmax· Using
`SNMP, the network manager sends a poll to each of Nj active
`nodes, where polls to consecutive nodes are spaced by a time
`equal to 1/Rp and as in OV, waits for an acknowledgment
`from each polled node for a period of time T1
`. In one
`advantageous embodiment of the present invention T1 is set
`equal to 10 seconds. If an acknowledgment is not received
`35 within time T1
`, another poll is sent and the NM waits for an
`acknowledgment for a period of time 2xT1
`. This continues
`two more times for corresponding waiting periods of 4xT1
`and 8xT1
`, respectively. If after four polls a node does not
`respond it is taken off the list of active nodes that are used
`40 in the next immediate round j+l. 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(cid:173)
`ing Group, IETF (1990), hereby incorporated by reference
`as if fully set forth herein.
`Referring to FIG. 2, after the last node in round j is polled,
`roundj+l begins. Prior to polling further network resources,
`the network manager notes the number of active nodes after
`round j, as Nj+l' the polling rate of the prior round, Rj, and
`the congestion feedback which is derived from the received
`50 acknowledgments during roundj. These parameters are then
`used to compute the polling rate Rj+l for round j+l, which
`entails estimating the network congestion from polls issued
`in round j.
`In particular, a congestion metric Di 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
`60 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.
`With Dj, congestion can be estimated by comparison with
`the levels of timeout described above. Thus for example, if
`Di is less than or equal to T1
`, e.g. 10 seconds, the network
`is normally loaded and not experiencing congestion. For D
`
`BACKGROUND OF THE INVENTION
`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, 15
`while the remaining hosts and resources are identified as
`agents. The manager 10 will periodically request informa(cid:173)
`tion from the agents using one of a variety of protocols, e.g.
`Simple Network Manager Protocol ("SNMP") at the appli(cid:173)
`cation layer, or Packet Internet Groper ("PING") at the IP 20
`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- 25
`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 30
`intruding on the performance of user applications in the
`network.
`Presently, the de facto network management software is
`marketed by Hewlett Packard under the trade name Open(cid:173)
`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 T1 , 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 2xT1 , for a response. This is repeated two
`more times with corresponding time-out periods of 4xT 1 and
`8xT1 , 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.
`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 unre(cid:173)
`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 55
`to ameliorate the deficiencies of the OV method is described
`in Bondi, supra. As described more fully therein, a minimum
`time threshold -i: 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 -i:. However, even this proposal suffers from
`its inability to provide feedback relating to network conges(cid:173)
`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 65
`network capacity. Such monitoring can cause a network that
`is already congested with user traffic to collapse.
`
`Facebook's Exhibit No. 1019/1119
`Page 3
`
`

`

`US 6,173,323 Bl
`
`3
`fh· greater than T1 but less than or equal to T2
`, e.g. 20 seconds,
`t e 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 5
`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.
`This congestion feedback Di is used to adapt the polling
`rate at round j + 1. In the presence of any level of congestion 10
`1 through 3, i.e. Tk<Dj~Tk+ 1
`, the equation
`
`4
`determining the number of active nodes Nj+l 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 Rj+l equal to the lesser of
`
`NJ+l
`--XRo,
`Nm~
`
`·{NJ+!
`
`R1)
`
`R1+1=nn --XRo,k
`Nmax
`2
`
`and
`
`15
`
`is used. The multiplicative factor of 2-k corresponds 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 20
`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 25
`as the new polling rate.
`Under a normal load, however, where Di is less than or
`equal to T1
`, 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 30
`the equation is modified by setting k=O and adding a llR
`which is typically a small fraction of R0 , for example R0/10.
`Thus Rj+llR0 . 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 35
`whenever possible and minimizes the undesirable effects of
`bandwidth congestion.
`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.
`What is claimed is:
`1. A method for monitoring network nodes with a mini(cid:173)
`mum polling rate per round j, Rj, said method comprising the
`steps of:
`polling said nodes during each round at said rate Rj where
`Rj equals R0 for said initial round;
`estimating congestion in said network experienced during
`said round j;
`adapting the polling rate for round j+l based on said
`estimated congestion during round j, said adapted poll(cid:173)
`ing rate for round j+l represented as Rj+l; and
`setting j=Q+l) and repeating said polling, estimating and
`adapting steps.
`2. A method according to claim 1 wherein Rj is set initially
`to R0 , and said estimating step further comprising the step of
`computing a congestion metric Di 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, Nmax' 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 65
`within a predetermined period of time T1 and wherein
`T1 increases by a factor of 2 for each successive poll;
`
`50
`
`where Tk <Di~ Tk+ 1
`, wherein k is an integer and has a value
`at least equal to 1, and assigns a value to Rj+l equal to the
`lesser of
`
`NJ+l
`--XRo
`Nm~
`
`NJ+l
`--XRo
`Nm~
`
`and
`
`and Rj+i'lR0 where Di~T1
`.
`5. A computer implemented network manager for moni(cid:173)
`toring network nodes with a minimum polling rate per round
`j, RP comprising:
`means for polling said nodes during each round at said
`rate Rj where Rj equals R0 for initial round;
`means for estimating congestion in said network experi(cid:173)
`enced during said round j;
`means for adapting the polling rate for roundj+l based on
`said estimated congestion during round j, said adapted
`polling rate represented as Rj+l; and
`means for polling said nodes during round j+l at said
`adapted polling rate Rj+l ·
`6. The computer implemented network manager of claim
`40 5 wherein Rj is set initially to R0 , and wherein said means
`for estimating further comprising means for computing a
`congestion metric Dj as the average delay over all resolved
`and outstanding polls.
`7. The computer implemented network manager of claim
`45 6 wherein said network comprises an initial maximum
`number of nodes to be polled in a round, Nmax' said network
`manager further comprising a list of active nodes, said first
`recited and second recited means for polling further com-
`prising:
`transmitting up to four successive polls to each node
`where said node fails to acknowledge a prior poll
`within a predetermined period of time T1 and wherein
`T1 increases by a factor of 2 for each successive poll;
`determining the number of active nodes Nj+l 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
`60 7 wherein said means for adapting includes means for
`assigning a value to Rj+l equal to the lesser of
`
`55
`
`Facebook's Exhibit No. 1019/1119
`Page 4
`
`

`

`US 6,173,323 Bl
`
`5
`
`6
`
`where Tk<Di~Tk+i, wherein k is an integer and has a value
`at least equal to 1, and means for assigning a value to Rj+l
`equal to the lesser of
`
`* *
`
`* * *
`
`Facebook's Exhibit No. 1019/1119
`Page 5
`
`