||||||||||||l|||||||||||||||||||||||||||||
`
`
`
`USUl16173323Bl
`
`(12) United States Patent
`US 6,173,323 B1
`(45) Date of Patent:
`Jan. 9, 2001
`Moghe
`
`(10) Patent 1%.:
`
`(54) ADAPTIVE POLLING RATE ALGORITHM
`FOR SNMP-BASEI) NETWORK
`MONITORING
`
`(75)
`
`Inventor:
`
`I’I‘atyltsh Moghe, Aberdeen, NJ (US)
`
`(73) Assignee: Lucent Technologies lite, Murray Hill,
`NJ (US)
`
`( * ) Notice:
`
`Under 35 U.S.C. 154th], the term of this
`patent shall be extended [or 0 days.
`
`(21) Appl. No.: 081998313
`
`(22
`
`Filed:
`
`Dec. 24, 1997
`
`(51)
`Int. CL? ......................... .. G061" [51116; 0061' 15r'173
`
`(52) U.S. Cl. .. __
`__
`7091224; T092315; 7095225;
`34082507; 349382555; 379-9101
`(58) Field of Search ................................... .. 709,924. 226.
`709.3235, 227; 34082507, 825.08, 825.55;
`372220; 710K220; 37992.01.
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`4.598.363 "
`#689,619 *
`4.905.233 *
`5,084,825 *
`5.l93,l5l
`*
`5.2?e.e?7 *
`5.633,.‘59 *
`5.659528? *
`5,896,56l
`*
`5,922,05I
`*
`
`791086 Clark ct at.
`........................ .. 304.3200
`.. 34th‘825tl8
`8,-‘1987 O‘Brien
`
`2.!1990 Cain et al.
`..... .. 370323?
`
`lx'19‘32 Weinbergeret at.
`it‘ll-1r)
`3f1993 Jain ctal.
`TTNIZ37
`
`11’1994 Rantamurthy et al.
`320.3232
`
`5,!199?
`Iain elal.
`3203234
`811997 Schiellz
`TiFMZZé
`
`41’1999 Scltrader et a.
`.. 455.3611
`23‘1999 Sidey ................................. .. “19.3223
`OTHER PUBLICATIONS
`
`A multiple access scheme I‘or Wireless access to a broadband
`ATM LAN polling and sectored antennas, Mahmoud, A.S.;
`Mahmoud. 8A.; Falconer. DD. Dept. of Syst. & Compl.
`
`Eng. Carleton Univ., Ottawa, Ont. Canada. pp. 596—608.
`May, 1996.*
`Adaptive polling schemes [or an ATM bus, Karlsson, .I.M.;
`Perros. II.G.; Viniolis, I., Center for Common.
`81. Signal
`Process. North Carolina State Univ., Raleigh, NC, USA. pp.
`403-417. ISBN: 0—7803-0006—8, May 1996.*
`.1. Case et al., "A Simple Network Management Protocol
`(SNMP)", RFC [157, Network Working Group, IETF, 1990.
`R. Sturm, “0&A". Open View Adviser, pp. 11—13, 1(2),
`Mar. 1995.
`
`AB. Bondi. "A nonhlocking mechanism for regulating the
`transmission of network management polls”.
`lit/[’92. pp.
`565—580, May 1997.
`Analysis of symmetric nortexhaustive polling with multiple
`server, Marsanrn, de Moraes. Donatelli, Neri. INITOCOM
`")0 May 6,199tt.*
`
`* cited by examiner
`
`Primary Examiner—Mark I-I. Rineharl
`Assistant Exmniner—Beatriz Prieto
`
`(57)
`
`ABSTRACT
`
`A rate adaptive polling method sensitive to network eon-
`gestion is used to monitor network resources. Initially, a
`baseline rate constraint is set based on desirable engineering
`factors. Unacknowledgcd polls are retransmitted with
`timeouts. successively increasing by a [actor 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 fee-(Iv
`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 RI, the
`minimum rate of polling for round RI.” is adapted accord-
`ingly.
`
`3 Claims, 1 Drawing Sheet
`
`POLLING ROUND j+1 HITH Nj.” POLLS
`POLLING ROUND j HITH N j POLLS
`
`Ir—PDLLS FROM
`5
`NHS
`1
`
`taI
`
`\
`
`r
`
`I1t'
`
`HATE ESTIMATION
`FOO ROUND 3
`
`HATE ESTIMATION
`FOR HOUNO j+1
`
`RATE ESTIMATION
`FOR ROUND j+2
`
`001
`
`US. Patent No. 8,724,622
`
`Apple Inc.
`APLl 1 19
`
`001
`
`Apple Inc.
`APL1119
`U.S. Patent No. 8,724,622
`
`

`

`US. Patent
`
`Jan. 9, 2001
`
`US 6,173,323 B1
`
`1
`FIG.
`[PRIOR ART]
`
`,5
`OTHER
`
`
`
`
`10
`
`POLLING
`MESSAGES
`
`
` SUBNET 19
`
`FIG. 2
`
`
`
`POLLING ROUND j HITH Ni POLLS POLLING ROUND j+1 HITH Nj+1 POLLS
`
`‘.
`
`POLLS FHBH--\
`HMS
`
`x
`
`E
`:
`
`
`
`HATE ESTIMATION
`FOR ROUND j
`
`HATE ESTIMATION
`FOR ROUND j+1
`
`HATE ESTIMATION
`FOR ROUND j+2
`
`002
`
`002
`
`

`

`US 6,173,323 B1
`
`1
`ADAPTIVE POLLING RATE ALGORITHM
`FOR SNMP-IMSED NETWORK
`MONITORING
`
`TECHNI CAI . FIEI .D
`
`This invention relates generally to the field of network
`management and in particular to a method for eflicicnt
`polling of network hosts and resources and a network
`manager for implementing the same.
`BACKGROUND 0]: TIIE INVENTION
`
`It]
`
`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 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 -
`layer, and expect a response from each agent using the same
`protocol. This process is referred to as "polling."
`Eflicient 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 traflic
`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.
`
`_
`
`so
`
`Presently, the de t‘acto network management software is
`marketed by Hewlett Packard under the trade name Open-
`View (“0V”) and described more fully in R. Sturm, "0&A”,
`OpenView Advisor, pp. 11—13, 1(2) (March 1995), hereby
`incorporated by reference as if fully set forth herein. In
`operation, 0V can transmit a maximum of N outstanding
`polls. where N is typically 3. For example, NM ll] may send
`a lirst 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
`timeout period 2xT1, for a response. This is repeated two
`more times with corresponding time-out periods of 4><T1 and
`8x’l'1, respectively. NM 10 resends the poll these four times
`with continuously increasing timeout 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 It] 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-
`sponsive. See,A. B. Bondi, "ANonblocking 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 0V method is described
`in Bondi, supra. As described more fully therein, a minimum
`time threshold 1'.
`is set under which no two polls can be
`transmitted, while the maximum number of polls parameter
`N of 0V is eliminated. As a result, freeze up is avoided by
`removing the constraint of N and network traffic is managed
`with constraint ‘5. 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 01.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 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 TIIE
`INVENTION
`
`In accordance with the present invention a network man-
`ager begins an initial polling round at a rate 11,, and a
`corresponding maximum number of hosts to be polled in a
`polling round, NW”. These initial parameters are typically
`based on engineering criteria. Thus for the initial round j=1,
`R- is set equal
`to litD and N,- is set equal to NM“. Using
`SNMP. the network manager sends a poll to each ofNJ. active
`nodes, where polls to consecutive nodes are spaced by a time
`equal to 1ij, and as in CV, waits for an acknowledgment
`from each polled node for a period of time T]. In one
`advantageous embodiment of the present invention T-1 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 2x1". This continues
`two more times for corresponding waiting periods of 41le
`and BX'I'I, respectively. If after four polls a node does not
`respond it is taken oh" the list of active nodes that are used
`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 ll57, 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 round j is polled,
`round j+l begins. Prior to polling further network resources,
`the network manager notes the number of active nodes after
`round j, as N,,,, the polling rate of the prior round, R,, and
`the congestion feedback which is derived from the received
`acknowledgments during roundj. These parameters are then
`used to compute the polling rate RAM for round j+t, which
`entails estimating the network congestion from polls issued
`in round j.
`is computed as the
`In particular, a congestion metric
`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.
`
`congestion can be estimated by comparison with
`With
`the levels of timeout described above. Thus for example, if
`E is less than or equal to T1, eg. 10 seconds, the network
`is normally loaded and not experiencing congestion. For D
`
`003
`
`

`

`US 6,173,323 B1
`
`3
`j_-greater than T1 but less than or equal to T2, e.g. 205econds.
`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
`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.
`
`is used to adapt the polling
`This congestion feedback
`rate at round j+1. [n th_e presence of any level of congestion
`1 through 3, Le. T‘”<Dj‘=‘T‘”1, the equation
`
`.i'-I
`. N
`“N “mini... “a
`
`
`
`3'J'
`
`4
`
`determining the number of active nodes NIH 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,-M equal to the lesser of
`
`Niel
`NM“
`
`X fin.
`
`and
`
`5
`
`It)
`
`15
`
`is used. The multiplicative factor ol~ 24' 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
`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 caso the left term is biased *
`as the new polling rate.
`is less than or
`Under a normal load, however, where
`equal to '1”, 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=U and adding a AR
`which is typically a small fraction of R”, for example RUIIO.
`Thus RJ-+ARU.
`[n 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 elTecLs 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:
`l. A method for monitoring network nodes with a mini-
`mum polling rate per roundj. RI, said method comprising the
`steps of:
`polling sajd nodes during each round at said rate R;— where
`R, equals R0 for said initial round;
`estimating congestion in said network experienced during
`said round j;
`adapting the polling rate [or round j+1 based on said
`estimated congestion during round j, said adapted poll-
`ing rate for round j+l represented as R)“; and
`setting j=fi+1) and repeating said polling, estimating and
`adapting steps.
`2. Amethod according to claim I wherein R}. is set initially
`to RD, and said estimating step further comprising the step of
`computing a congestion metric
`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, NM”, said method further comprising a list of
`active nodes, said polling steps further comprising the steps
`of:
`
`3f]
`
`35
`
`40
`
`45
`
`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 TJ and wherein
`TI increases by a factor of 2 for each successive poll;
`
`65
`
`004
`
`where TWEETI‘”. wherein k is an integer and has a value
`at least equal to l, and assigns a value to R;—H equal to the
`lesser of
`
`
`ngi I
`NM“
`
`x Ru
`
`and Rfl-éRD where fiéTl.
`5. A computer implemented network manager for moni-
`toring network nodes with a minimum polling rate per round
`j, R), comprising:
`means for polling said nodes during each round at said
`rate R;— where R}. equals R0 [or initial round;
`means for estimating congestion in said network experi-
`enced 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 RI“; and
`means for polling said nodes during round j+l at said
`adapted polling rate RI“.
`6. The computer implemented network manager of claim
`5 wherein R,- is set initially to R0, and wherein said means
`for estimating further comprising means for computing a
`congestion metric E as the average delay over all resolved
`and outstanding po s.
`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, Nmm, 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 [our successive polls to each node
`where said node fails to acknowledge a prior poll
`within a predetermined period of time T1 and wherein
`'1“ increases by a [actor of 2 [or each successive pol];
`determining the number of active nodes NI,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 R1“ equal to the lesser oil
`thI—><ti.I
`NM “
`
`and
`
`004
`
`

`

`US 6,173,323 B]
`
`where 'I“<fij§'l“”l, wherein R is an integer and has a value 5
`al lcasl equal to 1, and means for assigning a value [0 RH1
`equal [0 [he lesser of
`
`and Rfifikn where [7521“.
`
`a:
`
`no:
`
`005
`
`005
`
`