`
`1111111111111101111110101111111141!!°11111!11111111111111111111110111111
`
`(19) United States
`(12) Patent Application Publication (10) Pub. No.: US 2004/0090923 Al
`May 13, 2004
`Kan et al.
`(43) Pub. Date:
`
`(54) NETWORK MONITORING SYSTEM
`RESPONSIVE TO CHANGES IN PACKET
`ARRIVAL VARIANCE AND MEAN
`
`(76)
`
`Inventors: Chao Kan, Frisco, TX (US); Aziz
`Mohammed, Plano, TX (US); Wei
`Hao, Richardson, TX (US); Jimin Shi,
`Plano, TX (US)
`
`Correspondence Address:
`ALCATEL USA
`INTELLECTUAL PROPERTY DEPARTMENT
`3400 W. PLANO PARKWAY, MS LEGL2
`PLANO, TX 75075 (US)
`
`(21) Appl. No.:
`
`10/412,127
`
`(22) Filed:
`
`Apr. 11, 2003
`
`Related U.S. Application Data
`
`(60) Provisional application No. 60/424,495, filed on Nov.
`7, 2002.
`
`Publication Classification
`
`(51) Int. C1.7
`(52) U.S. Cl.
`
`H04J 1/16
`370/252; 370/329
`
`(57)
`
`ABSTRACT
`
`A network monitoring system (10) for monitoring a network
`along which network traffic flows in a form of packets. The
`system comprises circuitry (36, 42) for receiving a packet
`communicated along the network and for determining
`whether the received packet satisfies a set of conditions. The
`system further comprises circuitry (36/30, 46), responsive to
`a determination that the received packet satisfies the set, for
`determining a measure, wherein the measure is determined
`over a defined time interval and comprises a ratio of packet
`arrival variance and a mean of packets arriving during the
`time interval and for comparing the measure to a threshold.
`Lastly, the system comprises circuitry (36, 52), responsive to
`the measure exceeding the threshold, for adjusting network
`resources.
`
`40
`
`42
`
`CAPTURE PACKET;
`PACKET SATISFY RULE
`IN RULE SET(S)
`
`NO
`
`44
`
`YES
`STORE PACKET INFORMATION,
`INCLUDING TIME OF ARRIVAL,
`IN FLOW CORRESPONDING
`TO SATISFIED RULE(S)
`
`46
`
`FOR DEFINED INTERVAL, t,
`DETERMINE IDC FOR EACH FLOW
`
`IDC > THRESHOLD?
`
`NO
`
`48
`
`YES
`
`OoS MET FOR
`THRESHOLD-EXCEEDING
`PACKET(S)?
`
`YES
`
`50
`
`NO
`
`52
`
`RE-ADJUST TRAFFIC
`PARAMETERS
`
`Cloudflare - Exhibit 1009, page 1
`
`Cloudflare - Exhibit 1009, page 1
`
`

`

`Patent Application Publication May 13, 2004 Sheet 1 of 2
`
`US 2004/0090923 Al
`
`FIG. 1
`
`ER3
`
`ER 4
`
`ST3
`
`ER1
`
`ER2
`
`CR2
`
`N
`
`NM
`
`ER-11
`
`CR1
`
`NM
`
`CR 3
`
`ER 6
`
`ST2
`
`ER 9
`
`ERi 0
`
`NM 7
`
`NM 4
`
`CR4
`
`NM 5
`
`ER 8
`
`ER 7
`
`NM 6
`
`ST3
`
`ST4
`
`20
`
`30
`
`00
`
`MEI
`
`FIG. 2
`
`r
`
`32
`
`34
`
`36
`
`L
`
`RECORDER LAYER
`
`RTFM METER
`
`J
`
`CORE NETWORK/ROUTER
`
`Cloudflare - Exhibit 1009, page 2
`
`Cloudflare - Exhibit 1009, page 2
`
`

`

`Patent Application Publication May 13, 2004 Sheet 2 of 2
`
`US 2004/0090923 Al
`
`40
`
`42
`
`CAPTURE PACKET;
`PACKET SATISFY RULE
`IN RULE SET(S)
`
`NO
`
`44
`
`YES
`STORE PACKET INFORMATION,
`INCLUDING TIME OF ARRIVAL,
`IN FLOW CORRESPONDING
`TO SATISFIED RULE(S)
`
`46
`
`FOR DEFINED INTERVAL, t,
`DETERMINE IDC FOR EACH FLOW
`
`IDC > THRESHOLD?
`
`NO
`
`48
`
`YES
`
`00S MET FOR
`THRESHOLD-EXCEEDING
`PACKET(S)?
`
`YES
`
`50
`
`NO
`
`52
`
`RE-ADJUST TRAFFIC
`PARAMETERS
`
`FIG. 3
`
`Cloudflare - Exhibit 1009, page 3
`
`Cloudflare - Exhibit 1009, page 3
`
`

`

`US 2004/0090923 Al
`
`May 13, 2004
`
`1
`
`NETWORK MONITORING SYSTEM RESPONSIVE
`TO CHANGES IN PACKET ARRIVAL VARIANCE
`AND MEAN
`
`CROSS-REFERENCES TO RELATED
`APPLICATIONS
`
`[0001] This application claims the benefit, under 35
`U.S.C. §119(e)(1), of U.S. Provisional Application No.
`60/424,495, filed Nov. 7, 2002, and incorporated herein by
`this reference.
`
`STATEMENT REGARDING FEDERALLY
`SPONSORED RESEARCH OR DEVELOPMENT
`
`[0002] Not Applicable.
`
`BACKGROUND OF THE INVENTION
`
`[0003] The present embodiments relate to computer net-
`works and are more particularly directed to a system for
`monitoring network performance and correcting network
`congestion by evaluating changes in packet arrival variance
`relative to mean packet arrival.
`
`[0004] As the number of users and traffic volume continue
`to grow on the global Internet and other networks, an
`essential need has arisen to have a set of mechanisms to
`monitor network performance and to take corrective mea-
`sures in response to falling performance. Such performance
`may be evaluated in various forms, including but not limited
`to detecting and troubleshooting network congestion. Net-
`work congestion results from mismatches between network
`capacity and network demand. The mismatch may be a
`long-term one, or at instantaneous time scales. Further,
`network capacity may appear to be ample when using tools
`that look at long-term traffic averages; however these
`approaches are not always suitable because a more subtle
`problem may arise with short bursts of packets, or peak
`demand. With congestion analyses mechanisms, the reliabil-
`ity and availability of the network nodes (e.g., IP routers)
`and the given internet paths can be evaluated. This is
`especially true for Internet Service Providers ("ISPs") seek-
`ing to comply with the Service Level Agreements ("SLAs")
`that they are now providing to customers. Additionally, such
`a need is prevalent for the underlying internet protocol
`("IP") networks in the Internet.
`
`[0005] The Internet is also evolving towards an advanced
`architecture that seeks to guarantee the quality of service
`("QoS") for real-time applications. QoS permits the control-
`ling of what happens to packets when there is congestion in
`a network, or more precisely when there is insufficient
`network capacity to deliver all of the offered load without
`any noticeable queuing delays. One type of QoS framework
`seeks to provide hard specific network performance guar-
`antees to applications such as band-width/delay reservations
`for an imminent or future data flow. Such QoS is usually
`characterized in terms of ability to guarantee to an applica-
`tion-specified peak and average band-width, delay, jitter and
`packet loss. Another type is to use Class-of-Service ("CoS")
`such as Differentiated Services ("Diff-Serv") to represent the
`less ambitious approach of giving preferential treatment to
`certain kinds of packets, but without making any perfor-
`mance guarantees.
`
`[0006] During the QoS process to provide services better
`than the traditional best effort, network congestion detection
`
`often becomes the starting point for the network perfor-
`mance analysis. In the past, a number of congestion detec-
`tion and control schemes have been investigated in data
`networks. One congestion detection scheme uses the trans-
`port-layer protocols to infer congestion from the estimated
`bottleneck service time or from changes in throughput or
`end-to-end delay, as well as from packet drops. Specifically,
`the Internet has traditionally relied on mechanisms in the
`Transport Control Protocol ("TCP"), such as sliding window
`control and retransmission timer deficiencies to avoid con-
`gestion. TCP operates to seek excess bandwidth by increas-
`ing transmission rates until the network becomes congested
`and then reducing transmission rate once congestion occurs.
`A few limitations arise from this approach. First, TCP
`congestion detection at a first node requires an acknowl-
`edgement from a second node, that is, the increased trans-
`mission is continued until no acknowledgement is received
`from the second node; thus, a feedback communication is
`required from another node and that feedback also utilizes
`bandwidth on the network. Second, in its effort to identify
`bandwidth, TCP necessarily causes the very congestion
`which it then seeks to minimize, where the congestion is
`caused as the TCP increases the bandwidth to a point that
`exceeds the network capacity. Another type of congestion
`detection scheme is to involve network components such as
`routers in the entire process. As most network congestion
`occurs in routers, they may be considered an ideal position
`to monitor network load and congestion and respond thereto
`in a control scheme. Such network-based congestion control
`uses explicit signaling between routers to provide feedback
`congestion information to a transmitting router, where the
`transmitting router may then alter its behavior in response to
`the feedback, or an overall scheme can change the packet
`processing within one or more routers so as to reduce
`congestion. In any event, this latter scheme also requires a
`form of feedback from a recipient router, thereby increasing
`traffic on the network to accommodate the feedback and also
`requiring the reliance of the transmitting router on the
`integrity of a different router.
`
`In view of the above, there arises a need to address
`[0007]
`the drawbacks of the prior art, as is accomplished by the
`preferred embodiments described below.
`
`BRIEF SUMMARY OF THE INVENTION
`
`In the preferred embodiment, there is a network
`[0008]
`monitoring system along which network traffic flows in a
`form of packets. The system comprises circuitry for receiv-
`ing a packet communicated along the network and for
`determining whether the received packet satisfies a set of
`conditions. The system further comprises circuitry, respon-
`sive to a determination that the received packet satisfies the
`set, for determining a measure and circuitry for comparing
`the measure to a threshold, wherein the measure is deter-
`mined over a defined time interval and comprises a ratio of
`packet arrival variance and a mean of packets arriving
`during the time interval. Lastly, the system comprises cir-
`cuitry, responsive to the measure exceeding the threshold,
`for adjusting network resources.
`
`[0009] Other aspects are also described and claimed.
`
`Cloudflare - Exhibit 1009, page 4
`
`Cloudflare - Exhibit 1009, page 4
`
`

`

`US 2004/0090923 Al
`
`May 13, 2004
`
`2
`
`BRIEF DESCRIPTION OF THE SEVERAL
`VIEWS OF THE DRAWING
`
`[0010] FIG. 1 illustrates a block diagram of a network
`system 10 into which the preferred embodiments may be
`implemented.
`
`[0011] FIG. 2 illustrates a block diagram of each network
`monitor NM, through NM, of FIG. 1.
`
`[0012] FIG. 3 illustrates a flow chart of the operation of
`each network monitor NM, through NM, of FIG. 2.
`
`DETAILED DESCRIPTION OF THE
`INVENTION
`
`[0013] FIG. 1 illustrates a block diagram of a system 10
`into which the preferred embodiments may be implemented.
`System 10 generally includes a number of stations ST,
`through ST4, each coupled to a network 20 via a router, and
`each operable to send packets as a source or receive packets
`as a destination. By way of example, network 20 is an
`internet protocol ("IP") network such as the global Internet
`or other IP-using network, where each station and IP net-
`works in general are well known in the art. One skilled in the
`art should appreciate that the use of the IP protocol is by way
`of illustration, and many of the various inventive teachings
`herein may apply to numerous other protocols, including by
`way of examples asynchronous transfer mode ("ATM"),
`token ring, Novell, Apple Talk, and still others. In any event,
`returning to network 20 as an IP network, and also by way
`of an example, each station STx may be constructed and
`function as one of various different types of computing
`devices, all capable of communicating according to the IP
`protocol. Lastly and also by way of example, only four
`stations STx are shown so as to simplify the illustration and
`example, where in reality each such station may be proxi-
`mate other stations (not shown) and at a geography located
`at a considerable distance from the other illustrated stations.
`
`[0014] Continuing with FIG. 1, along the outer periphery
`of network 20 are shown a number of edge routers ER,
`through ER„, while within network 20 are shown a number
`of core routers CR, through CR4. The terms edge router and
`core router are known in the art and generally relate to the
`function and relative network location of a router. Typically,
`edge routers connect to remotely located networks and
`handle considerably less traffic than core routers. In addition
`and due in part to the relative amount of traffic handled by
`core routers, they tend to perform less complex operations
`on data and instead serve primarily a switching function; in
`other words, because of the tremendous amount of through-
`put expected of the core routers, they are typically hardware
`bound as switching machines and not given the capability to
`provide operations based on the specific data passing
`through the router. Indeed, core routers typically do not
`include much in the way of control mechanisms as there
`could be 10,000 or more connections in a single trunk.
`Further, typically core routers do not involve their opera-
`tions with TCP related items and instead deal at the IP level
`and below. In contrast, edge routers are able to monitor
`various parameters within data packets encountered by the
`respective router. In any event, the various routers in FIG.
`1 are shown merely by way of example, where one skilled
`in the art will recognize that a typical network may include
`quite a different number of both types of routers. Finally,
`note that each core router CRx and each edge router ERx may
`
`be constructed and function according to the art, with the
`exception that preferably selected ones of those routers may
`include additional functionality for purposes of traffic con-
`gestion detection and response based on packet arrival
`variance and mean as described later. In addition, selected
`routers may be further constructed to respond to the traffic
`congestion detection that the router determines as well as in
`response to the traffic congestion detection of another router
`in network 20. Moreover, in one approach, core routers may
`be configured to respond differently than edge routers in the
`case of detecting traffic congestion.
`
`[0015] Completing the discussion of FIG. 1, note that the
`various stations, edge routers, and core routers therein are
`shown connected to one another in various fashions and also
`by way of example. Such connections are intended to
`illustrate an example for later discussion of the preferred
`operation and also to reflect a general depiction of how
`networks are generally established. Thus, each station STx is
`shown connected to a single edge router ERx, where that
`edge router ERx is connected to one or more core routers
`CRx. The core routers CRx, also by way of example, are
`shown connected to multiple ones of the other core routers
`CRx. By way of reference, the following Table 1 identifies
`each station and router shown in FIG. 1 as well as the other
`device(s) to which each is connected.
`
`TABLE 1
`
`station or router
`
`connected nodes
`
`ST1
`ST2
`ST3
`ST4
`ER1
`ER2
`ER3
`ER4
`ER5
`ER6
`ER7
`ER8
`ER9
`ER10
`ER11
`CR1
`
`CR2
`
`CR3
`CR4
`
`ER1
`ER10
`ER5
`ER7
`ST1; CR1
`CR1; CR2
`CR2
`CR7
`ST3; CR2; CR3
`CR3; CR4
`ST4; CR4
`CR4
`CR4
`ST2; CR1
`CR1
`ER1; ER11; ER10; ER7; CR3;
`CR3; CR4
`ER2; ER3; ER4; CR1; CR3;
`CR4; ER5
`ER5; ER6; CR2; CR1; CR4
`ER7; ER8; ER9; CR1; CR2;
`CR3; ER6
`
`[0016] Given the various illustrated connections as also set
`forth in Table 1, in general IP packets flow along the various
`illustrated paths of network 20, and in groups or in their
`entirety such packets are often referred to as network traffic.
`In this regard and as developed below, the preferred embodi-
`ments operate to identify and respond to congestion in such
`network traffic. Finally, note that FIG. 1 may represent a
`simplified version of a network or the Internet in that only
`a few stations and routers are shown, while one skilled in the
`art will readily appreciate that the inventive concepts in this
`document may be applied to a larger number of stations,
`routers, and the network interconnectivity between those
`devices.
`[0017] FIG. 1 also illustrates a number of network moni-
`tors NM, through NM, according to the preferred embodi-
`
`Cloudflare - Exhibit 1009, page 5
`
`Cloudflare - Exhibit 1009, page 5
`
`

`

`US 2004/0090923 Al
`
`May 13, 2004
`
`3
`
`ments, where the choice of eight such network monitors is
`only by way of example given the amount of other hardware
`that is shown for network 20. As detailed below, each
`network monitor NM„ is operable to sample each packet that
`is received along the conductor(s) to which the network
`monitor is connected, and if corrective action is deemed as
`useful then a routing table associated with a router that is
`also associated with the network monitor NM„ may be
`modified to improve network performance. The components
`of each network monitor NM„ are described below, but at
`this point the connections of each such monitor are noted in
`the following Table 2:
`
`TABLE 2
`
`network monitor
`
`connected nodes
`
`NM,
`NM2
`NM3
`NM4
`NM5
`
`NM6
`NM4
`NM8
`
`CR4; CR2
`CR2; CR3
`CR4; CR3
`CR3; CR4
`CR4; CR2; CR3; ER4; ER8;
`ER9
`CR4; ST4
`ST2; CR4
`ER5; ST3
`
`[0018] FIG. 1 and Table 2 demonstrate that each of
`network monitors NM, through NM4 and NM8 is connected
`to sample packets passing along the conductor(s) between a
`pair of nodes, such as between routers or between a router
`and a station. However, network monitors NM5, NM6, and
`NM7 are each by way of alternative examples incorporated
`into respective routers CR4, ER7, and ER10. As a result, each
`of network monitors NM5, NM6, and NM7 is able to sample
`packets communicated with any of the nodes to which its
`respective router is connected; for example with respect to
`network monitor NM5, it may sample packets communi-
`cated with respect to any node to which core router CR4 is
`connected, namely, core routers CR4, CR2, CR3, and edge
`routers ER7, ER8, and ER9. Thus, the contrast of network
`monitors NM5, NM6, and NM7 to the other illustrated
`network monitors NM4 through NM4 is shown to demon-
`strate that in the preferred embodiment each network moni-
`tor NM„ may sample packets as a stand alone entity or may
`be combined with the hardware and software of an existing
`router; indeed, in the preferred embodiments a network
`monitor NM„ also may be combined with network or ele-
`ment management systems. In any event and by way of
`introduction to details provided later, in the preferred
`embodiments the sampling functionality of each network
`monitor NM„ permits real-time monitoring, over a defined
`period of time, of a ratio of the packet arrival variance and
`mean for selected packets, and in response determinations
`may be made, and actions may be taken, based on thresholds
`exceeded by the ratio, thereby presenting an indication of
`likely network traffic congestion.
`[0019] FIG. 2 illustrates a block diagram of each network
`monitor NM4 through NM4 and NM8 of FIG. 1, with the
`further understanding
`that functionally
`the following
`description also may be applied to any of network monitors
`NM5, NM6, and NM7, with the addition that certain func-
`tionality may be provided by the hardware and software
`already available from each respective router CR4, ER7, and
`ER10. Turning then to FIG. 2, a console 30 is associated
`with network monitor NM„, where in the preferred embodi-
`
`ment a single such console 30 communicates with multiple
`network monitors NM,c. For example, returning briefly to
`FIG. 1, preferably each of network monitors NM4 through
`NM8 communicates with a single console 30, where such
`communications also may be by way of packets between
`console 30 and the network monitors NM,c. Console 30 may
`be constructed by one skilled in the art using various forms
`of hardware and software, where the selection is a matter of
`implementation choice in order to achieve the functionality
`described in this document. Turning to that functionality,
`console 30 preferably provides an administration (configu-
`ration) function and a reporting function. To permit a user to
`perform these functions, various interfaces may be used such
`as a graphical Web-based configuration tool or a command
`line tool, where one preferable approach implements con-
`sole 30, by way of example, using the Apache Web server
`with the PHP server-side scripting language to provide a
`dynamic interface to a flow store 32. In any event, the user
`interface preferably provides different screens for each of
`the administration and reporting functions. The actual inter-
`face and screens, however, may be implemented in various
`forms, where it is desirable for any form that an operator
`may properly control console 30 to perform its administra-
`tion and reporting functions with respect to its flow store 32.
`Preferably, a network administrator or the like uses the
`administration functionality of console 30 to create a set of
`rules and to provide those rules, along with a methodology
`for determining an index dispersion for counts ("IDC") and
`responding thereto, to an RTFM meter 36 described later. By
`way of introduction, the set of rules causes meter 36 to store
`packet arrival time for each packet that satisfies one (or
`more) of the provided rules, that is, those packets are
`selected from among all packets that pass through the meter
`with the arrival time of such selected packets being
`recorded; thereafter, meter 36 determines the IDC for the
`selected packets over a specified time interval t. Also, once
`the system is configured and left to collect packet arrival
`about the monitored packets, the network administrator can
`use the reporting screen to query the information so as to
`generate network status reports based on the collected
`information and to thereby analyze network congestion.
`
`[0020] As introduced above, console 30 is connected to a
`flow store 32, which preferably represents a storage medium
`that stores a flow database relating to monitored packets. In
`the preferred embodiment, each network monitor NM„
`includes its own flow database, although alternative embodi-
`ments may be created where more than one network monitor
`NM„ shares a common flow database. In the preferred
`embodiment the flow database in flow store 32 is an SQL-
`compatible database using the PostgreSQL relational data-
`base management system, although in alternative embodi-
`ments various other types of databases may be used in flow
`store 32. Using the preferred embodiment as an example,
`console 30 communicates with this database through the
`Web server's PHP link to the SQL database. Thus, any
`administration and configuration changes made via console
`30 are passed directly to flow store 32. Given the preceding,
`one skilled in the art should appreciate that access to flow
`store 32 can be achieved by SQL queries, enabling network
`administrators to automate the configuration process or
`integrate report generation. As introduced above, in the
`preferred embodiment, flow store 32 also stores what is
`referred to in this document as a "rule set" (or "rule sets"
`when plural), which is initially provided to the flow store 32
`
`Cloudflare - Exhibit 1009, page 6
`
`Cloudflare - Exhibit 1009, page 6
`
`

`

`US 2004/0090923 Al
`
`May 13, 2004
`
`4
`
`from console 30 as part of the administration function and
`which is also thereby conveyed to meter 36. As shown by
`example below, each rule set specifies one or more criteria
`against which meter 36 evaluates each incoming packet to
`determine if the criteria are satisfied. Additionally, in one
`embodiment, flow store 32 may store the packet arrival
`information for those criteria-satisfying packets in a moni-
`tored flow so that such information may be evaluated,
`including the determination of IDC information and possible
`responses thereto, by console 30. Moreover and as also
`discussed below, flow store 32 may store numerous different
`sets of packet arrival information, each corresponding to a
`different set of flow criteria, that is, corresponding to one of
`the different specified rule sets. The stored information is
`therefore accessible by console 30 and permits other analy-
`ses of the flow information so as to provide information and
`reports that are useful for network engineering and manage-
`ment purposes.
`[0021] Continuing with FIG. 2, recorder layer 34 provides
`an interface between flow store 32 and a meter 36 (or
`meters) in use and coupled to the network. Generally, the
`applications of recorder layer 34 can be separated into two
`categories: manager applications and meter reading appli-
`cations. Manager applications configure meter 36, based on
`information, including rules in one or more rule sets, in flow
`store 32. Meter reading applications permit the data col-
`lected and/or determined by meter 36 to be provided in a
`data format usable by flow store 32 and, indeed, recorder
`layer 34 facilitates the passage of that data into the flow
`database of flow store 32. Recorder layer 34 applications
`may pass information between flow store 32 and the network
`probes of meter 36 either synchronously or asynchronously.
`This gives network administrators the flexibility of either
`using real-time network flow meters (i.e. NeTraMet) or
`importing data from other network analysis tools that are not
`able to provide real-time data (e.g. Cisco NetFlow data).
`[0022]
`In the preferred embodiment, meter 36 is a Real-
`Time Traffic Flow Measurement ("RTFM") meter which is
`a concept from the Internet Engineering Task Force
`("IETF"). As known in the RTFM art, RTFM meters are
`previously known to be used in systems for determining the
`service requested by IP packets that are passing through a
`network for purposes of collecting revenue, where such a
`service is identifiable by the transport port number specified
`in each IP packet. For example, RTFM meters are currently
`being considered for use in systems whereby an Internet user
`is charged based on the service he or she is using on the
`Internet; for example, a different fee may be charged to the
`user for each different Internet service, including mail,
`video, phone calls, and web browsing. However, as detailed
`in this document, the preferred embodiment implements the
`RTFM meter instead to analyze each packet and to deter-
`mine if the packet satisfies a rule in the rule set and, if so,
`to store sufficient packet arrival time corresponding to the
`defined interval t so that packet IDC may be determined and
`used as a basis to indicate, and respond to, network con-
`gestion. Thus, in real time, meter 36 physically probes the
`underlying network traffic and each time meter 36 detects an
`IP packet on the network, it determines whether the packet
`satisfies a rule in the rule set(s). Also, during the real-time
`passage of numerous IP packets by the evaluating meter 36,
`meter 36 does not always copy a fixed portion of each such
`packet into a database such as the entire packet or the entire
`packet header; instead, each meter 36 evaluates the appro-
`
`priate field(s) in the packet and, if a rule in the rule set(s) is
`satisfied, then meter 36 stores sufficient packet arrival time
`so that the IDC corresponding to that packet may be deter-
`mined. In addition, meter 36 may store additional informa-
`tion about each rule set-satisfying packet, as further explored
`later. Returning to the aspect of meter 36 storing information
`to determine the packet IDC, the present inventive scope
`contemplates two alternatives of the actual IDC determina-
`tion, namely, either meter 36 may itself determine the IDC,
`or meter 36 may store sufficient information and console 30
`may determine the IDC from the stored information, where
`in either case the IDC is determined as detailed later. Further,
`the trade-off between these two alternative embodiment
`approaches is that the meter-side implementation introduces
`the overhead on network processors but with less messaging
`bandwidth overhead to meter readers. The read-side solu-
`tion, on the other hand, actually functions as an application
`analysis component in the RTFM architecture. The overhead
`to the router processor is minimal but the messaging band-
`width overhead for passing raw data to the IDC monitor for
`computation may be unendurable.
`[0023] The Index of Dispersion for Counts ("IDC") has
`heretofore been proposed to be used to characterize packet
`burstiness in an effort to model Internet traffic, whereas in
`contrast, in the present inventive scope IDC is instead
`combined with the other attributes described herein to detect
`and respond, in a real-time manner, to packet congestion. By
`way of background, in the prior art, in a document entitled
`"Characterizing The Variability of Arrival Processes with
`Index Of Dispersion," (IEEE, Vol. 9, No. 2, February 1991)
`by Riccardo Gusella and hereby incorporated herein by
`reference, there is discussion of using the IDC, which
`provides a measure of burstiness, so that a model may be
`described for Internet traffic. Currently in the art, there is
`much debate about identifying the type of model, whether
`existing or newly-developed, which will adequately describe
`Internet traffic. In the referenced document, IDC, as a
`measure of burstiness, is suggested for use in creating such
`a model. IDC is defined as the variance of the number of
`packet arrivals in an interval of length t divided by the mean
`number of packet arrivals in t. For example, assume that a
`given network node has an anticipation (i.e., a baseline) of
`receiving 20 packets per second ("pps"), and assume further
`that in five consecutive seconds this node receives 30
`packets in second 1, 10 packets in second 2, 30 packets in
`second 3, 15 packets in second 4, and 15 packets in second
`5. Thus, over the five seconds, the node receives 100
`packets; on average, therefore, the node receives 20 packets
`per second, that is, the average receipt per second equals the
`anticipated baseline of 20 pps. However, for each individual
`second, there is a non-zero variance in the amount of packets
`received from the anticipated value of 20 pps. For example,
`in second 1, the variance is +10, in second 2 the variance is
`—10, and so forth. As such, the IDC provides a measure that
`reflects this variance, in the form of a ratio compared to its
`mean, and due to the considerable fluctuation of the receiv-
`ing rate per second over the five second interval, there is
`perceived to be considerable burstiness in the received
`packets, where the prior art describes an attempt to compile
`a model of this burstiness so as to model Internet traffic.
`[0024] Looking now to the preferred embodiment, it uses
`IDC not solely as a predicate for Internet traffic modeling,
`but instead to provide an ongoing determination of whether
`selected packet traffic is causing congestion, where such
`
`Cloudflare - Exhibit 1009, page 7
`
`Cloudflare - Exhibit 1009, page 7
`
`

`

`US 2004/0090923 Al
`
`May 13, 2004
`
`5
`
`congestion is detected in part in response to a threshold-
`exceeding IDC, and preferably further in view of additional
`considerations, such as in relation to quality of service
`("QoS"). Having thus introduced IDC in its past application
`as well as in the present inventive scope, its actual deter-
`mination is now explored in greater detail. Recalling that the
`
`weakly stationary, that is, that their first and second moments
`are time invariant, and that the auto-covariance series
`depends only on the distance k, the lag, between samples:
`cov(c,, ci„)=cov
`for all i, j, and k.
`
`[0027] Further in view of Equations 1 and 2, consider the
`following Equation 3:
`
`n-1
`
`n-j
`
`j=1
`
`k=1
`
`cov(ci, cJ+k) = sum of
`
`1=1,
`
`j = 2,
`
`cov(1)+ cov(2)+ • • + cov(rt - 2) + cov(rt- 1)
`cov(1)+ cov(2)+ • • • + cov(rt- 2)
`
`Equation 3
`
`j=n - 2,
`
`j=n-1,
`
`cov(1) + cov(2)
`cov(1)
`
`(n - j)cov(j)
`
`j=1
`
`IDC is defined as the variance of the number of packet
`arrivals in an interval of length t divided by the mean
`number of packet arrivals in t, it may be written as shown in
`the following Equation 1:
`
`[0028] Further, for the auto-correlation coefficient
`may be stated as in the following Equation 4:
`
`it
`
`IDC, -
`
`var(Aft )
`
`
`E(N,)
`
`Equation 1
`
`= fic
`
`cov(ci, ci+k)
`
`var(ci) -N/var(ci,)
`
`cov(k)
`
`COV(Cr)
`
`Equation 4
`
`In Equation 1, N, indicates the number of arrivals
`[0025]
`in an interval of length t. In the preferred embodiment and
`for estimating the IDC of measured arrival processes, only
`considered are the time at discrete, equally spaced instants
`
`[0029] Then from Equation 4, the following Equation 5
`may be written:
`
`n • var(cr) +2
`
`cov(cj, cj+k)
`
`=
`
`j=1 k=1
`
`n • E(c)
`
`var(Cr )
`
`E(c)
`
`1+2
`
`1 n- j
`
`var(Cr )
`
` 1
`E(Cr)
`
`2
`
`1=
`
`TX
`
`by using cov(k) = ek • val(ci)
`
`Equation 5
`
`Ti (1[ 0). Further, letting c„ indicate the number of arrivals in
`the time interval
`the following Equation 2 may
`_1 ,then
`be stated:
`
`[0030] Finally, therefore, the unbiased estimate of E(c.,),
`var(c,),and
`are as shown in the following respective
`Equations 6 through 8:
`
`var
`
`ci
`
`IDC„ =
`
`i
`
`E
`
`i=1
`
`
`
`)
`ci
`
`var(c1 + c2 +
` + (.2
`E(c1
`
`• • • + c n )
`cn)
`
`Equation 2
`
`n • var(Cr ) + 2
`
`CO*
`
`e