60010-0020 New Nonprovisional Application Under 37 CFR§1.53(b
`IAA
`122204
`nNseEeet
`
`UTILITY PATENT APPLICATION TRANSMITTAL
`
`Attorney Docket No.
`
`*
`
`TO THE COMMISSIONERFOR PATENTS:
`
`) application identifier or (X) first named inventor, Vishnu Natchu,entitled
`Transmitted herewith is the patent application of (
`
`MECHANISM FOR IDENTIFYING AND PENALIZING MISBEHAVING FLOWSIN_A NETWORK. , for a(n):
`
`113014U.S.PT11/022599°
`
`vOzeclMN
`
`e (X) Original Patent Application.
`(
`) Continuing Application (prior application not abandoned):
`(
`) Continuation
`(
`) Divisional
`(
`) Continuation-in-part (CIP)
`of prior application No:
`Filed on:
`:
`() AsStatement claiming priority under 35 USC § 120 has been addedto the specification.
`
`0 a
`
`(
`
`Enclosed are:
`Specification 30 Total Pages; (X) Drawing(s)_5 Total Sheets; (X) Cover Sheet 1 Page
`(X)
`(X) Oath or Declaration: _2_ Pages
`(X) A Newly Executed Combined Declaration and Power of Attorney:
`(X) Signed.
`(
`) Unsigned.
`(
`) Partially Signed.
`) A Copy from a Prior Application for Continuation/Divisional (37 CFR § 1.63(d)).
`(
`)
`Incorporation by Reference. The entire disclosure of the prior application, from which a copy ofthe
`oath or declaration is supplied, is considered as being part of the disclosure of the accompanying
`application and is hereby incorporated herein by referencein its entirety for all purposes.
`) Signed Statement Deleting Inventor(s) Named in the Prior Application. (37 CFR § 163(d)(2)).
`(
`Powerof Attorney.
`(X) Return Receipt Postcard.
`
`Associate Power of Attorney.
`(<) A Check in the amount of $_ 2,240.00. for the Filing Fee.
`Preliminary Amendment.
`(
`)
`Information Disclosure Statement and Form PTO-1449.
`Requestand Certification Under 35 U.S.C. 122(b)(2)(B)(i)
`A Duplicate Copy of this Form for Processing Fee Against Deposit Account.
`A Certified Copy of Priority Documents (if foreign priority is claimed).
`Applicant(s) is entitled to small entity status. See 37 CFR 1.27.
`Statement(s) of Status as a Smal! Entity Filed in Prior Application, Status Still Proper and Desired.
`Recordation of Assignment Cover Sheet and executed Assignment(2 pgs).
`Other:
`
`ON
`*%Neeeeeeeeeeeee
`Filing $0.00
`
`4
`
`CLAIMSAS FILED
`
`Total Claims
`Independent Claims
`Poa8200.008200.00
`Multiple Dependent Claims (if applicable
`Assignment Recording Fee
`ic
`
`$40.00
`$300.00
`$500.00
`$200.00
`
`Size Fee (for each additional 50 sheets that exceeds 100 sheets
`
`Total Filing Fee
`to Deposit Account
`Charge $
`pursuant to 37 CFR § 1.25.
`(X) Throughoutthe pendencyof this application, please charge any additional fees, including any required extension oftime
`fees, and credit all overpayments to deposit account 50-1302. A duplicate of this sheet is enclosed.
`
`$2,240.00
`
`Respectfully submitted,
`
`By:
`
`Bobby K. Truong, Reg. No. 37, 499
`
`
`
`
`
`Date: December 22, 2004
`
`Correspondence Address:
`
`29989
`
`
`
`
`I hereby certify that this is being deposited with the U.S. Postal
`Service “Express Mail Post Office to Addressee” service under
`to:
`37 CFR § 1.10 on the date indicated below andis addressed
`
` Commissionerfor Patents
`P.O. Box 1450
`
`Alexandria, VA 22313-1450
`
`Typed Name: Carmen Frias
`
`
`
`
`Express Mail Label No.: EV564758070US
`
`Date of Deposit: December 22, 2004
`
`By:
`
`Splunk Inc.
`
`Exhibit 1002
`
`Page 1
`
`Splunk Inc. Exhibit 1002 Page 1
`
`

`

`s
`
`PTO/SB/17 (12/04)
`Approved for use through 09/30/2005, OMB 0651-0032
`Patent and Trademark Office: U.S. DEPARTMENT OF COMMERCE
`are required to respond to a collection of information unless it displays
`a valid OMB control nurnber.
`
`FEE TRANSMITTAL
`
`
`for FY 2005
`December22, 2004
`Filing Date
`
`Patent fees are subject to annualrevision,
`
`
`
`Smail Entity payments must be supported by a small entity statement,
`First Named Inventor|Vishnu Natchu
`
`
`otherwise large entity fees must be paid. See Forms PTO/SB/09-12.
`
`Examiner Name
`NYA
`See 37 C.F.R. §§ 1.27 AND 1.28
`
`
`
`
`Application Number
`
`Complete ifKnown
`
`
`
`
`
`
`FEE CALCULATION (continued
`METHOD OF PAYMENT(check one)
`
`1 Throughout the pendency of this application, please charge§3. ADDITIONAL FEES
`
`
`
`
`.
`anyadditional fees, including any required extension oftime
`[Large Entity
`Small Entity
`Fee Paid
`Fee Description
`
`fees, and credit all overpayments to deposit aocount 50-
`Fee
`Fee
`Fea
`Fee
`
`
`
`
` 1302. A duplicate ofthis sheet is enclosed. Code {8} Code}
`
`
`
`
`Recount|50-1302
`
` 1051
`
` 130-2051 85 Surcharge — latefiling fee or oath
`Number
`
`1052
`50
`2052
`25 Surcharge — late provisionalfiling fee or
`
`cover sheet.
`Name
`Hickman Palermo Truong & Becker, LLP
` Revount
`
`120
`2251
`60 Extension for reply within first month
` 1251
`
`12652
`450
`2252
`225
`Extensionfor reply within second month
`
`
`1253
`1,020
`2253
`510 Extension for reply within third month
`
`Payment Enclosed:
`2.
`[XJ]
`
`
`1254
`1,590
`2254
`795 Extension for reply within fourth month
`Money
`
`
`
`Order | Other
`ix]
`Check
`
`‘
`ri
`:
`1255
`2,160
`2255
`1,080 Extension for reply within fifth month
`‘i
`
`
`
`om
`3. O Applicant(s) is entitled to small entity status.
`
`
`See 37 CFR 1.27.
`
`
`
`1401
`500
`2401
`250 Notice of Appeal
`FEE CALCULATION
`
` 1402 500 2402 250
`1. BASIC FILING FEE
`
`
`
`Filing a brief in support of an appeal
`1452
`500
`2452
`250 Petition to revive ~ unavoidable
`
`
`Large Entity Small Entity
`
`
`Fee
`Fee Description
`Fee
`Fee
`Fee
`1453
`1,500
`2453
`750 Petition to revive — unintentional
`
`
`
`
`
`
`Code=(8) Code (8)
`
`
`
`1501
`1,400
`2501
`700 Utility issue fee (or reissue)
`1011. 150—Utility filing fee300). 2011
`
`
`
`
`1111,
`500
`2111
`250
`Utility Search fee
`1502
`800
`2502
`400 Designissue fee
`
`
`
`200.00
`1504
`300
`2504
`300 Publication Fee
`1311, «2311+=100~——Utility Examination fee200
`
`
`
`
`
`1462
`1462
`
`
`1081
`250
`2081
`125
`Utility Application Size
`
` Petitions Director not specifically
`
`Fee
`provided for Group|
`
`
`
`
`
`1005
`200
`2005
`100
`Provisional Application
`200 Petitions Director not specifically
`
`
`
`
`Fee
`provided for GroupII
`
`
`
`1085
`250
`20835
`125
`Provisional
`
`130 Petitions Director not specifically
`
`Application Size Fee
`provided for GroupIll
`
`
`
`SUBTOTAL(1)
`1806
`180
`1806
`180 Submission of information Disclosure Stmt
`
`
`
`
`2. EXTRA CLAIM FEES
`
`
`
`8021
`40
`8021
`40 Recording each patent assignment per
`
`property (times numberof properties)
`
`
`
`2808
`790
`1809
`PaoChins ‘Chins hee Fee Paid
`395 reerTeo rejection
`
`
`
`
`
`
`
`Total Claims -20°*s ||x|$0.00|=| 1,000.00|1810 2810©395._“~For each additionalinvention to be©7909
`
`
`
`examined (37 CFR § 1.129(b))
`
`
`
`
`Otherfee (specify)
`aims
`Multipte Dependent|| *L____Jotner fee (speci)
`
`**or numberpreviously paid, if greater; For Reissues, see below
`
`Large Entity Small Entity
`Fee Description
`Fee
`Fee
`Fee
`Fee
`Code
`(8)
`Code
`(3)
`Claims in excess of 20
`1202.
`50
`2202
`25
`
`
`4201
`200
`2201
`100
`seependent claims in excess of
`
`1203
`360
`2203
`180 Multiple dependentclaim,if not paid
`
`4204
`200
`2204
`100
`**Reissue independent claims
`
`over original patent
`“Reissue claims in excess of 20
`
`and overorigina! patent
`1205
`50
`2205-25
`
`
`
`
`
`
`SUBTOTAL(2)
`()1,200.00
`
`
`“Reduced by Basic Filing Fee Paid
`SUBTOTAL(3)
`SUBMITTED BY
`
`
`
`37,499 Taephore|(408) 414-1080
`
`[SomeOONNO [ae|December 22, 2004
`
`
`WARNING:
`Information on this form may become pubfic. Credit card information should not be
`Included on this fomm. Provide credit cap information and authorization on PTO-2038.
`Burden Hour Statement: This form is estimated to take 0.2 hours to complete. Time will vary depending upon the needs of the individual case. Any comments on the
`amount of time you are required to complete this form should be sentto the Chief Information Officer, Patent and Trademark Office, Washington, DC 20231,
`DO NOT SEND FEES OR COMPLETED FORMS TO THIS ADDRESS. SEND TO: Commissionerfor Patents, P.O. Box 1450, Alexandria, VA 22313-1450.
`
`Group/Art Unit
`
`TOTAL AMOUNT OF PAYMENT
`
`($) 2,240.00
`
`Attomey Docket No.
`
`60010-0020
`
`1463
`
`1464
`
`200
`
`130
`
`«1463
`
`1464
`
`
`
`
`
`Splunk Inc.
`
`Exhibit1002
`
`Page 2
`
`Splunk Inc. Exhibit 1002 Page 2
`
`

`

`60010-0020
`
`Patent
`
`UNITED STATES PATENT APPLICATION
`
`FOR
`
`MECHANISM ForIDENTIFYING AND PENALIZING
`MISBEHAVING FLOWS IN A NETWORK
`
`INVENTOR(S):
`
`VISHNU NATCHU
`~
`
`PREPAREDBY:
`HICKMAN PALERMO TRUONG & BECKER, LLP
`1600 WILLOW STREET
`SAN JOSE, CALIFORNIA 95125-5106
`(408) 414-1080
`
`EXPRESS MAIL CERTIFICATE OF MAILING
`
`“Express Mail" mailing label number _EV564758070US
`
`Date of Deposit_December 22, 2004
`I herebycertify that this paperor fee is being deposited with the United States Postal Service "Express Mail Post Office
`to Addressee" service under 37 CFR 1.10 on the date indicated aboveandis addressed to Commissionerfor Patents,
`P.O. Box 1450, Alexandria, VA 22313-1450.
`
`CarmenFrias
`(Typed or printed name ofperson mailing paperorfee)
`*
`
`(Signature of person mailing paper or fee)
`
`Splunk Inc.
`
`Exhibit1002
`
`Page 3
`
`Splunk Inc. Exhibit 1002 Page 3
`
`

`

`60010-0020
`
`Background
`
`MECHANISM FOR IDENTIFYING AND PENALIZING
`
`MISBEHAVING FLOWS IN A NETWORK
`
`Inventor(s): Vishnu Natchu
`
`{0001}
`
`With the advent offile sharing applications such as KaZaA, Gnutella,
`
`BearShare, and Winny, the amountof peer-to-peer (P2P) traffic on the Internet has grown
`
`immensely in recent years. In fact, it has been estimated that P2P traffic now represents
`
`about 50-70 percentofthe totaltraffic on the Internet. This is so despite the fact that the
`
`number of P2P users is quite small compared to the number of non P2P users. Thus,it
`
`appearsthat mostof the bandwidth onthe Internet is being consumed by just a minority
`
`of the users. For this and other reasons, P2P traffic is viewed by ISP's (Internetservice
`
`providers) and others as being abusive/misbehavingtraffic that should be controlled and
`
`penalized.
`
`[0002]
`
`In order to control P2P traffic, however, it first needs to be identified. Earlier
`
`generations of P2P protocols used fixed TCP port numbersfor their transmissions. For
`
`example, FastTrack used TCP port 1214. This made P2Ptraffic easy to identify. Current
`
`P2P protocols, however, no longer haveto use fixed port numbers. Rather, they can be
`
`configured to use random dynamicport numbersso that P2Ptraffic can now be
`
`masqueradedas other typesoftraffic, such as HTTP web browsing and unspecified TCP
`
`traffic. As a result, the current P2P protocols have rendered the port-based identification
`
`techniquesineffective.
`
`Splunk Inc.
`
`Exhibit1002
`
`Page 4
`
`Splunk Inc. Exhibit 1002 Page 4
`
`

`

`60010-0020
`
`[0003]
`
`Another technique that has been used to identify P2P traffic involves the use
`
`of signatures. Specifically, it was observed that some P2P protocols inserted distinct
`
`information into their data packets. Usingthis distinct information as a signature, it was
`
`possible to identify packets that were assembled using those P2P protocols. This
`
`technique has several problems. First, it usually is effective for only a relatively short
`
`period of time. As the P2P protocols evolve and mutate (which they do onafairly
`
`constantbasis), their signatures change. Once that happens,the previous signatures are
`
`no longer valid, and the technique will have to be changed to recognize the new
`
`signatures. Another and moreserious problem is that the P2P protocols are now evolving
`
`to the pointthat they either leave no signature or they obfuscate their signatures (e.g. by
`
`encryption). This makesit extremely difficult if not impossible to identify P2P traffic
`
`using signatures.
`
`[0004]
`
`Overall, P2P protocols have gotten quite sophisticated, and the more
`
`sophisticated they become, the more difficult it is to identify P2P traffic. Unless P2P
`
`traffic can be identified, it cannot be effectively controlled.
`
`Summary
`
`[0005]
`
`In accordance with one embodimentofthe present invention, there is provided
`
`a mechanism for effectively identifying and penalizing misbehaving information packet
`
`flows in a network. This mechanism maybeapplied to any type of networktraffic
`
`including, but certainly not limited to, P2Ptraffic. In one embodiment, misbehaving
`
`flowsare identified based upontheir observed behavior. Unlike the prior approaches,
`
`they are notidentified based uponancillary factors, such as port numbers andsignatures.
`
`Splunk Inc.
`
`Exhibit1002
`
`Page 5
`
`Splunk Inc. Exhibit 1002 Page 5
`
`

`

`60010-0020
`
`Because misbehaving flowsare identified based upon their observed behavior, and
`
`because their behavior cannot be hidden, misbehaving flows cannot avoid detection.
`
`Thus, regardless of which protocols they use, or how those protocolstry to hide/obfuscate
`
`their nature, misbehaving flows can be identified. Once identified/detected, they can be
`
`controlled and/or penalized.
`
`[0006]
`
`In one embodiment, a flow is processed as follows. One or more information
`
`packets belongingto the flow are received and processed. As the information packets are
`
`processed, a set of behavioral statistics are maintained for the flow. These behavioral
`
`statistics reflect the empirical behavior of the flow. In one embodiment, the behavioral
`
`statistics includeatotal byte count(sum ofall of the bytesin all of the packets of the
`
`flow that have been processed up to the currenttime), a life duration (how long the flow
`
`has beenin existence since inception), a flow rate (derived by dividing the total byte
`
`countby the life duration ofthe flow), and an average packetsize (derived by dividing
`
`the total byte count bythe total numberofpackets in the flow that have beenprocessed).
`
`These behavioralstatistics are updated as information packets belonging to the flow are
`
`processed;thus, they provide an upto date reflection of the flow's behavior.
`
`[0007]
`
`Basedat least partially upon the behavioralstatistics, a determination is made
`
`as to whether the flow is exhibiting undesirable behavior. In one embodiment,this
`
`determination may be made by computing a badness factorfor the flow. This badness
`
`factor is computedbased,at least partially, upon the behavioralstatistics, and this
`
`badnessfactor provides an indication as to whether the flow is exhibiting undesirable
`
`behavior. In one embodiment, the badness factor also provides an indication ofthe
`
`degree to which the flow is misbehaving.
`
`Splunk Inc.
`
`Exhibit1002
`
`Page6é
`
`Splunk Inc. Exhibit 1002 Page 6
`
`

`

`60010-0020
`
`(0008)
`
`If the flow is exhibiting undesirable behavior, then a penalty may be enforced
`
`on the flow.
`
`In one embodiment, the penalty to be enforced is determined based,at least
`
`partially, upon the badness factor. This penalty may be an increased drop rate. When
`
`enforced on the flow,this increased drop rate causes the information packets belonging to
`
`the flow to have a higher probability of being dropped than information packets
`
`belonging to other flowsthat do not exhibit undesirable behavior. Thus, more packets
`
`may be dropped from the flow than from other non-misbehaving flows. In one
`
`embodiment, this penalty is enforced on the flow only if a congestion conditionis
`
`encountered. Thus,if there is no congestion, the flow (evenifit is exhibiting undesirable
`
`behavior) is not penalized.
`
`[0009)
`
`In one embodiment, enforcing the penalty on the flow hastheeffect of
`
`correcting the flow's behavior. That is, enforcing the penalty causes the badnessfactor of
`
`the flow to improve(e.g. decrease). As a result, by application of the penalty, a currently
`
`misbehaving flow can be turned into a non-misbehaving flow in the future. Once the
`
`flow is no longer misbehaving,it is no longer subject to penalty. In this manner, a
`
`misbehavingflow can be identified, penalized, and even rehabilitated in accordance with
`
`one embodimentof the present invention.
`
`BnefDescription of the Drawings
`
`[0010]
`
`Fig. 1 shows an overview of a network in which one embodimentofthe
`
`present invention may be implemented.
`
`[0011]
`
`Fig. 2 is a block diagram ofa router in which one embodimentofthe present
`
`invention may be implemented.
`
`Splunk Inc.
`
`Exhibit1002
`
`Page 7
`
`Splunk Inc. Exhibit 1002 Page 7
`
`

`

`60010-0020
`
`[0012]
`
`Fig. 3 is an operational flow diagram showingthe operation of a misbehaving
`
`flow manager (MFM)in accordance with one embodimentofthe present invention.
`
`[0013]
`
`Fig. 4 is a diagram of a sample flow block in accordance with one
`
`embodimentofthe present invention.
`
`[0014]
`
`Fig. 5 showsonepossible function for computing a badnessfactor for a flow
`
`in accordance with one embodimentofthe present invention.
`
`Detailed Description of Embodiment(s)
`
`Network Overview
`
`[0015]
`
`With reference to Fig. 1, there is shown an overview of a network 100 in
`
`which one embodimentofthe present invention may be implemented. As shown,the
`
`network 100 comprises a plurality of routers 102 interconnected to each other by trunks
`
`or links in such a way that each router 102 has multiple possible paths to every other
`
`router 102. For example, information from router 102a mayreach router 102d bygoing
`
`through routers 102b and 102c, or routers 102e and 102f, and information from router
`
`102c mayreach router 102a by going through router 102borrouter 102e.
`
`Interconnecting the routers 102 in this way provides flexibility in determining how
`
`information from one router 102 is delivered to another, and makesit possible to route
`
`around anyfailures that might arise. For the sake of simplicity, only a few routers 102
`
`are shown in Fig. 1; however, it should be noted that network 100 may be much more
`
`complex if so desired, comprising more routers 102, more connections between the
`
`routers 102, and other components.
`
`Splunk Inc.
`
`Exhibit1002
`
`Page 8
`
`Splunk Inc. Exhibit 1002 Page 8
`
`

`

`60010-0020
`
`[0016]
`
`In addition to being coupled to each other, each router 102 may further be
`
`coupled to various machines (not shown), suchasclients and servers, from which
`
`informationoriginates and to which informationis destined. By going through the
`
`routers 102, each of these machines may send information to any of the other machinesin
`
`the network 100.
`
`[0017]
`
`Information is conveyed from onerouter 102 to ee via a physicallink or
`
`trunk. Depending onthe type of network,this link or trunk may be an optical medium
`
`(e.g. an optical fiber), a coaxial cable, or some other type of medium. For purposes ofthe
`
`present invention, network 100 mayuse any type of transport medium.
`
`Router Overview
`
`[0018]
`
`Fig. 2 showsa block diagram of a sample router 102 that may be used to
`
`implementone or more ofthe routers 102 in network 100. As shown in Fig.2, the router
`
`102 comprisesa plurality of line cards 202 for coupling the router 102 to one or more of
`
`the other routers 102 in the network 100. For example, assuming that the router 102 in
`
`Fig. 2 is router 102b in network 100, line card 202d maycouple router 102bto router
`
`102f, line card 202c may couplerouter 102b to router 102c,line card 202b may couple
`
`router 102bto router 102e, and line card 202a may couple router 102b to router 102a.
`
`Overall, the line cards 202 act as the router's 102 interfaces to the rest of the network 100.
`
`In one embodiment, the trunks coupled to the line cards 202 are bi-directional; thus, each
`
`line card 202 mayreceive information from anotherrouter, or send information to
`another router. Put another way, each line card 202 is capable ofacting as an ingress line
`
`card (to receive information from another router) or an egress line card (to send
`
`Splunk Inc.
`
`Exhibit1002
`
`Page 9
`
`Splunk Inc. Exhibit 1002 Page 9
`
`

`

`60010-0020
`
`information to another router). Whether a particular line card 202 is acting as an ingress
`
`or an egress line card at any particular time depends uponthe flow of networktraffic.
`
`[0019]
`
`To couple the line cards 202 to each other within the router 102, there is
`
`provided an internal switching fabric 204. In one embodiment, the switching fabric 204
`
`comprises a plurality of interconnected fabric cards 206. Basically, the switching fabric
`
`204 provides a mechanism for coupling any line card 202 to any other line card 202
`
`within the router 102 so that information can betransported from anyingress line card
`
`202 to any egressline card 202. By transporting information from an ingressline card
`
`202 to an egress line card 202, the switching fabric 204 routes information through the
`
`router 102 and sendsit on its way to the next hop(i.e. the next router).
`
`Informationis
`
`thus received and routed by the router 102.
`
`[0020]
`
`To increasethe flexibility of the router 102 andto facilitate the process of
`
`failure recovery, each line card 202, in one embodiment, has multiple connections to the
`
`switching fabric 204. In addition, the switching fabric 204 provides multiple routes for
`
`connecting each line card connectionto every other line card connection. With such a
`
`setup, each line card 202 has multiple routes to every other line card 202 in the router
`
`102. For example, one possible route from line card 202d to line card 202a may pass
`
`throughfabric card 206c, while another route maypass through fabric card 206b. By
`
`providing multiple routes between the variousline cards 202, the switching fabric 204
`
`makesit possible to route around any internalfailures that mayarise.
`
`[0021]
`
`In addition to the line cards 202 and the switching fabric 204, the router 102
`
`further comprises an application processor 208. In one embodiment, the application -
`
`processor 208 determines the forwardingpaths, and hence, the egress line cards, that can
`
`Splunk Inc.
`
`Exhibit1002
`
`Page 10
`
`Splunk Inc. Exhibit 1002 Page 10
`
`

`

`60010-0020
`
`be used to forward information to any particular destination address. Put another way,
`
`given a destination address, the application processor 208 determines whichline card 202
`
`or line cards are mostsuitable to act as the egress line card to forward informationto that
`
`destination address. For example, supposethat the router 102 in Fig. 2 is router 102b in
`
`network 100, and that the destination is a machine coupled to router 102d. Suppose
`
`furtherthat line card 202c is coupled to router 102c andline card 202d is coupledto
`
`router 102f. In such a case, because the most direct routes to router 102d are through
`
`either router 102c or 102f, the most suitable egress line cards for forwarding information
`
`to the destination router 102d are probably line cards 202c and 202d. Accordingly, the
`
`application processor 208 designatestheseline cards 202c, 202d as potential egress line
`
`cards for destination router 102d, with one being designated as the primaryegressline
`
`card and the other being the alternate.
`
`[0022]
`
`Oncethe egress line card determinations are madebythe application
`
`processor 208 for each destination address, they are communicated to each ofthe line
`
`cards 202 in the router 102. In turn, each line card 202 stores the information into a
`
`forwarding table residing on the line card 202. Thereafter, when a line card 202acts as
`
`an ingress line card and receivesa set of information, it can use the forwardingtable to
`
`determine the appropriate egress line card 202 to which to forward the information.
`
`Because the egressline card information is predetermined and storedin the forwarding
`
`table, the ingress line card simply has to perform a table lookup to determine the proper
`
`egress line card. No on-the-fly calculation needs to be performed. Sincetable lookup
`
`operationscan becarried outvery quickly,the process of determining the proper egress
`
`line card requiresrelativelylittle time.
`
`Splunk Inc.
`
`Exhibit1002
`
`Page 11
`
`Splunk Inc. Exhibit 1002 Page 11
`
`

`

`60010-0020
`
`Information Routing
`
`[0023]
`
`In one embodiment, information is routed from router to router, and from line
`
`card 202 to line card 202, in the form of information packets. Each packet represents a
`
`set of information that is sent by a source to a destination. To enable it to be properly
`
`routed, a packet typically comprises a header portion. The header portion contains
`
`information that is used by the line cards 202 to determine the next hop for the packet.
`
`Depending uponthe routing protocol used, the information contained in the header
`
`portion may differ. In one embodiment, the header portion comprisesthe followingsets
`
`of information: (1) a source address(i.e. the network addressofthe entity sending the
`
`packet); (2) a source port number; (3) a destination address(i.e. the network address of
`
`the entity that is to receive the packet); (4) a destination port number; and (5) an
`
`indication of the routing protocolthat is to be used. These sets of information may be
`
`referred to as the "five tuple". Using this header information, an ingress line card 202 can
`
`determine to which egress line card 202 the packet should be routed.
`
`[0024]
`
`In addition to the headerportion, a packet also comprises a payload. The
`
`payload comprisesthe actual data that the source is trying to send to the destination. In
`
`addition to the actual data, the payload mayalso include other information, such as
`
`information inserted by otherprotocols (e.g. P2P protocols). This additional information
`
`may be needed bythe destination to properly process the packet.
`
`[0025]
`
`In one embodiment, one or more packets may be groupedinto a flow. For
`
`purposesof the present invention,a flow is a series of packets that are related in some
`
`manner. In one embodiment, packets are groupedinto a flow if they share a sufficient
`
`Splunk Inc.
`
`Exhibit1002
`
`Page 12
`
`Splunk Inc. Exhibit 1002 Page 12
`
`

`

`60010-0020
`
`amountof headerinformation. Morespecifically, in one embodiment, packets belong to
`
`the sameflow if they havethe five tuple in common. Thus,if two or more packets have
`
`the same source address, the same source port number, the samedestination address, the
`
`samedestination port number, and the same protocol, they are grouped into the same
`
`flow. Usually, barring some failure that requires rerouting,all of the packets belonging
`
`to a flow are received by the sameingress line card 202 and forwarded to the sameegress
`
`line card 202. By grouping packets into flows,it is possible to aggregate individual
`
`packets in a meaningful wayto enable a higherlevel understandingofthetraffic flowing
`
`through the router 102 to be derived.
`
`[0026]
`
`The flows that pass through a router 102 may represent manydifferent types
`
`oftraffic. For example, the flows may contain web browsingtraffic, TCPtraffic, P2P
`
`traffic, etc. As noted previously, some traffic is more abusive/misbehaving than others.
`
`P2Ptraffic, for example,is often considered to be abusive. Other typesoftraffic may
`
`also be considered abusive. To makethebest use ofavailable resources, and to best
`
`control thetraffic that passes through the router 102, it is desirable for the router 102 to
`
`be able to identify abusive/misbehavingtraffic, and to penalize and even rehabilitate that
`
`traffic. In one embodiment,the line cards 202 of router 102 have been enhancedto give
`
`the router 102 such capability. Morespecifically, the line cards 202 have been adaptedto
`
`include a misbehaving flow manager (MFM)210 for keeping track offlows, determining
`
`whetherthe flows are exhibiting undesirable behavior, and enforcing a penalty on the
`
`flowsif they are exhibiting undesirable behavior.
`
`[0027]
`
`For purposesofthe present invention, the MFM 210 oftheline cards 202 may
`
`be implementedin any desired manner. For example, the functionality of the MFM 210
`
`10
`
`Splunk Inc.
`
`Exhibit1002
`
`Page 13
`
`Splunk Inc. Exhibit 1002 Page 13
`
`

`

`60010-0020
`
`mayberealized by having one or moreprocessors ona line card 202 execute one or more
`
`sets of instructions. Alternatively, the MFM 210 maybe implemented using hardwired
`
`logic components(e.g. in the form of one or more ASIC's on a line card 202). These and
`
`other implementations are within the scope of the present invention.
`
`Functional Overview of MEM on Line Card
`
`[0028]
`
`With reference to Figs. 2 and 3, a functional overview ofthe operation of an
`
`MFM210 in accordance with one embodimentofthe present invention will now be
`
`described. In the following discussion,it will be assumed that the MFM 210 is onaline
`
`card 202that is acting as an egressline card(i.e. the line card is receiving packets from
`
`an ingress line card and sending packets out to another router). However, it should be
`
`noted that the MFM 210 onaline card mayprocessflows in the same manner even when
`
`the line card 202 is acting as an ingressline card(i.e. the line card is receiving packets
`
`from another router and sending them to an egress line card).
`
`[0029]
`
`Initially, an MFM 210 receives and processes one or more packets belonging
`
`to a flow. Processing a packet may,but does not necessarily, involve forwarding the
`
`packet to another router. As the packets of a flow are processed, a set of behavioral
`
`statistics are maintained (block 302 of Fig. 3) for the flow. These behavioralstatistics
`
`reflect the empirical behavior of the flow. In one embodiment, the behavioralstatistics
`
`includea total byte count (sum ofall of the bytesin all of the packets of the flow that
`
`have been processedup to the currenttime), a life duration (how long the flow has been
`
`in existence since inception), a flow rate (derived bydividing the total byte count by the
`
`life duration of the flow), and an average packet size (derived by dividingthetotal byte
`
`11
`
`Splunk Inc.
`
`Exhibit1002
`
`Page 14
`
`Splunk Inc. Exhibit 1002 Page 14
`
`

`

`60010-0020
`
`count by the total numberof packets in the flow that have been processed). These
`
`behavioralstatistics are stored by the line card 202 in a flow block associated with the
`
`flow,and are updated as information packets belongingto the flow are processed; thus,
`
`these behavioralstatistics provide an up to date reflection of the flow's behavior.
`
`(0030)
`
`Based uponthe behavioralstatistics, the MFM 210 determines (block 304)
`
`whether the flow is exhibiting undesirable behavior. In one embodiment,this
`
`determination is made by computing a badnessfactor for the flow. This badnessfactor is
`computed based upon the behavioralstatistics ofthe flow, and provides an indisation as
`
`to whetherthe flow is exhibiting undesirable behavior. In one embodiment, the badness
`
`factor also provides an indication of the degree to which the flow is misbehaving.
`
`[0031]
`
`If the flow is exhibiting undesirable behavior, then the MFM 210 enforces
`
`(block 306) a penalty on the flow. In one embodiment, the penalty to be enforcedis
`
`determined based upon the badness factor. This penalty may be an increased droprate.
`
`Whenenforcedontheflow,this increased drop rate causes the information packets
`
`belongingto the flow to have a higher probability of being dropped than information
`
`packets belongingto other flows that do not exhibit undesirable behavior. Thus, more
`
`packets may be dropped from theflow than from other non-misbehaving flows. In one
`
`embodiment, the MFM 210 enforcesthis penalty on the flow only if a congestion
`
`condition is encountered. If there is no congestion, the flow (evenifit is exhibiting
`
`undesirable behavior) is not penalized.
`
`[0032]
`
`In one embodiment, enforcing the penalty on the flow hastheeffect of
`
`correcting the flow's behavior. That is, enforcing the penalty causes the badness factor of
`
`the flow to improve(e.g. decrease). As a result, by application of the penalty, a currently
`
`12
`
`Splunk Inc.
`
`Exhibit1002
`
`Page 15
`
`Splunk Inc. Exhibit 1002 Page 15
`
`

`

`60010-0020
`
`misbehaving flow can be turned into a non-misbehaving flow in the future. Oncethe
`
`flow is no longer misbehaving,it is no longer subject to penalty. In this manner, an
`
`MFM 210 onaline card 202 can identify, penalize, and even rehabilitate a misbehaving
`
`flow.
`
`Sample Operation
`
`[0033]
`
`The above discussion provides a high level overview of the operation of an
`
`MFM 210. To facilitate a complete understandingof the invention, a specific sample
`
`operation of an MFM 210 in accordance with one embodimentofthe present invention
`
`will now be described. In the following discussion,it will be assumedthat line card 202d
`
`of Fig. 2 is acting as an egressline card, and that line card 202b is acting as an ingress
`
`line card, which is sending packets to the egress line card 202d. The following
`
`discussion describes the operation of the MFM 210d onthe egress line card 202d.
`
`[0034]
`
`Initially, MFM 210d receives a packet from the ingress line card 202b. In
`
`processing this packet, the MFM 210d determines whether the packet belongsto an
`
`existing flow. In one embodiment, the MFM 210d makesthis determination by
`
`processing the five tuple contained in the headerportionofthe packet(e.g. using a
`
`hashing function) to derive a flow ID. The MFM 210dthen determines whether this flow
`
`ID is associated with a flow block thatis already stored (e.g. in a memory, not shown) on
`
`the egress line card 202d. If so, then the packet