`
`
`
`
`
`
`
`US008243593B2
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`US 8,243,593 B2
`(10) Patent No.:
`a2) United States Patent
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`(45) Date of Patent:
`Aug. 14, 2012
`Natchu
`
`
`
`
`
`(56)
`
`
`
`
`References Cited
`
`
`
`
`
`
`
`
`(54) MECHANISM FOR IDENTIFYING AND
`PENALIZING MISBEHAVING FLOWSIN A
`
`
`
`
`
`NETWORK
`
`
`(75)
`
`
`
`Inventor: Vishnu Natchu, Santa Clara, CA (US)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`(73) Assignee: Sable Networks, Inc., Santa Clara, CA
`(US)
`
`
`
`
`
`
`(*) Notice:
`
`
`
`
`
`
`
`
`
`
`Subject to any disclaimer, the term ofthis
`
`
`
`
`
`
`
`patent is extended or adjusted under 35
`U.S.C. 154(b)
`by 1098 days.
`(b)
`by
`y
`
`
`
`
`
`(21) Appl. No.: 11/022,599
`
`
`
`
`(22)
`Filed:
`Dee. 22, 2004
`
`
`
`
`
`
`
`
`
`(65)
`
`
`
`Prior Publication Data
`
`
`US 2006/0133280 Al
`Jun. 22, 2006
`
`
`
`
`
`
`
`U.S. PATENT DOCUMENTS
`
`
`
`
`
`
`
`
`
`
`6,167,041 A * 12/2000 Afanador bese eeeeeseensenseeee 370/353
`
`
`
`
`
`
`
`6,252,848 B1*
`6/2001 Skirmont «0... 370/229
`6,310,881 B1* 10/2001 Zikan etal. oo. . 370/401
`
`
`
`
`
`
`
`
`
`6,934,250 BI1*
`8/2005 Kejriwaletal. oo... 370/229
`
`
`
`
`
`
`
`
`7,113,990 B2*
`9/2006 Scifres et al. ou. 709/224
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`2002/0032717 Al*
`3/2002 Malanetal. wo. 709/105
`2005/0141426 AL*
`6/2005 Hou wees 370/235
`
`
`
`
`
`
`
`2005/0226149 A1* 10/2005 Jacobsonet al. ww... 370/229
`
`
`
`
`
`
`
`
`5/2010 Yazakietal. oo... 370/230
`2010/0110889 AL1*
`
`
`
`
`
`
`
`
`* cited by examiner
`
`
`
`
`Primary Examiner — Xavier Szewai Wong
`
`
`
`
`
`(7A)Attorney, agent vr arn West & Associates, A PC;
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ABSTRACT
`(67)
`
`
`
`
`
`
`
`
`
`A mechanism is disclosedfor identifying and penalizing mis-
`behaving flows in a network. In one implementation,a set of
`
`
`
`
`
`
`
`
`
`behavioral statistics are maintained for each flow. These
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`behavioral statistics are updated as information packets
`
`
`
`
`
`
`
`
`
`belonging to a flow are processed. Based upon these behav-
`ioral statistics, a determination is made as to whethera flow is
`Int.Cl
`51)
`
`
`
`
`
`
`
`
`
`
`2006.01
`OD) Gt01R 31/08
`exhibitingundesirablebehavior.Ifso, apenalty is imposedon
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`(
`01)
`the flow. In one implementation, this penalty causes packets
`
`
`
`
`
`
`
`
`
`
`
`
`
`(2006.01)
`belonging to the flow to have a higher probability of being
`GO06F 11/00
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`(2006.01)
`dropped than packets belonging to other flows that do not
`GO8C 15/00
`
`
`
`
`
`
`
`
`
`
`
`
`
`(2006.01)
`exhibit undesirable behavior. In one implementation, in addi-
`HO4S 1/16
`
`
`
`
`
`
`
`
`
`(2006.01)
`tion to penalizing the flow, this penalty also has the effect of
`HO4J 3/14
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`(2006.01)
`correcting the flow’s behavior such thatthe flow exhibits less
`HOAL 1/00
`
`
`
`
`
`
`
`
`
`
`:
`undesirable behavior alter the
`penalty
`than before.
`cor-
`
`
`
`(2006.01)
`desirable
`behavior
`the penalty than
`before.
`HOAL 12/26
`after
`By
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`(52) US. CD. cocecccecceccccecssessessssssseessesseessnessseesene 370/229_recting the flow’s behavior, the penalty makesit possible for
`
`
`
`
`
`(58) Field of Classification Search......... 370/229-236__the How to become a non-misbehaving flow.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`See application file for complete search history.
`44 Claims, 5 Drawing Sheets
`
`
`
`TO/FROM
`
`OTHER
`
`ROUTER
`
`
`TO/FROM
`
`
`OTHER
`
`ROUTER
`
`PROCESSOR
`
`
`
`TO/FROM
`OTHER
`
`ROUTER
`
`
`
`TO/FROM
`
`OTHER
`
`ROUTER
`
`ROUTER
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`SWITCHING
`
`FABRIC
`206a
`
`
`FABRIC
`
`CARD
`
`
`206b
`
`
`
`>
`
`
`FABRIC
`
`CARD
`
`:
`> 206
`
`
`
`FABRIC
`
`CARD
`
`
`
`
`APPLICATION
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Splunk Inc.—Exhibit 1001 Page 1
`
`Splunk Inc. Exhibit 1001 Page 1
`
`

`

`
`U.S. Patent
`
`
`
`
`
`Aug.14, 2012
`
`
`
`
`
`Sheet 1 of 5
`
`
`
`US 8,243,593 B2
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`lPup
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`SplunkInc.
`
`Exhibit 1001
`
`Page 2
`
`Splunk Inc. Exhibit 1001 Page 2
`
`

`

`
`
`
`U.S. Patent
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Aug. 14, 2012
`
`
`
`Sheet 2 of 5
`
`
`
`
`
`US 8,243,593 B2
`
`
`
`
`
`WOusd/OL
`
`YySaLNOY
`
`YSHLO
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`WOYS/OL
`
`Y4aLNOY
`
`YSHLO
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`YSaLNOY
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`YOSS390Nd
`
`
`
`
`
`YSHLO
`
`YySLNouy
`
`WOYs/OL
`
`WOYs/OL
`
`YSHLO
`
`daLNow
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`cOL
`
`2902
`
`ONIHOLIMS
`
`oluavs
`
`Oluavs
`
`
`
`duvo
`
`
`
`
`
`
`
`qgoz:
`
`
`
`
`
`
`og02¢
`
`
`
`dYVO
`
`
`
`oldavs
`
`
`
`Oldavs
`
`duvo
`
`
`
`NOILVONdd¥
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`CPip
`
`
`
`
`
`Splunk Inc. Exhibit 1001 Page 3
`
`

`

`
`U.S. Patent
`
`
`
`
`
`Aug. 14, 2012
`
`
`
`
`
`Sheet 3 of 5
`
`
`
`US 8,243,593 B2
`
`
`
`
`
`MAINTAIN BEHAVIORAL
`
`
`
`STATISTICS FOR FLOW
`
`BEHAVIOR
`
`
`
`
`
`
`
`
`
`DETERMINE WHETHER
`
`
`
`FLOW IS EXHIBITING
`
`
`UNDESIRABLE BEHAVIOR
`
`
`
`
`
`ENFORCE PENALTY ON
`
`
`
`
`FLOW IF FLOW IS
`
`
`EXHIBITING UNDESIRABLE
`
`
`
`Fig. 3
`
`
`
`Splunk Inc.
`
`Exhibit1001
`
`Page 4
`
`Splunk Inc. Exhibit 1001 Page 4
`
`

`

`
`U.S. Patent
`
`
`
`
`
`Aug. 14, 2012
`
`
`
`
`
`
`Sheet 4 of 5
`
`
`
`US 8,243,593 B2
`
`
`
`
`
`FLOW ID
`
`
`
`BEHAVIORAL STATISTICS
`
`OTHER FLOW INFORMATION
`
`
`
`
`
`
`* TOTAL (T) BYTE COUNT
`
`
`
`
`
`
`* LIFE (L) DURATION SINCE INCEPTION
`
`
`
`
`
`
`* RATE (R) OF INFORMATION FLOW
`
`
`
`
`
`
`* NUMBER (N) OF PACKETS PROCESSED
`
`
`
`
`
`- AVERAGE (A) PACKET SIZE
`
`
`
`
`* BADNESS FACTOR(B)
`
`
`+ TIMESTAMP
`
`
`
`* OTHER
`
`
`
`
`
`
`
`
`Fig. 4
`
`
`
`Splunk Inc.
`
`Exhibit1001
`
`Page 5
`
`Splunk Inc. Exhibit 1001 Page 5
`
`

`

`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`U.S. Patent
`
`Aug. 14, 2012
`
`Sheet 5 of 5
`
`
`
`US 8,243,593 B2
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` QIOHSSYHL|LNANOdWODLNNODSLAPWLOL—T_
`
`
`
`
`
`YOLOVISSSNQVEWAWIXVW9}
`
`
`
`
`
`YOLOVASSANGVELINVASC|
`
`
`
`LNANOdWO9SSLVa—
`
`QTOHS3YHL
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`CIOHSSYHL
`
`
`
`
`
`
`
`
`
`INANOdWODNOILVYNG—T
`
`
`NIW=YOLOVASSSNQVE
`
`
`
`y-yLaMOVdADVYSAVCnOHSSUHL
`
`
`
`INSNOdWOO3ZIS=GIOHSSYHLW-NLIN
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`¢Ap
`
`Splunk Inc. Exhibit 1001 Page 6
`
`

`

`
`
`US 8,243,593 B2
`
`
`
`
`1
`MECHANISM FOR IDENTIFYING AND
`
`
`
`
`PENALIZING MISBEHAVING FLOWSIN A
`
`
`
`
`
`NETWORK
`
`
`BACKGROUND
`
`
`
`
`
`
`
`
`
`
`
`
`
`With the adventoffile sharing applications such as KaZaA,
`
`
`
`
`
`
`
`
`Gnutella, BearShare, and Winny, the amount of 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 percent of the total traffic on the
`
`
`
`
`
`
`
`
`
`
`
`
`Internet. This is so despite the fact that the number of P2P
`
`
`
`
`
`
`
`
`
`
`
`
`users is quite small compared to the numberofnon P2Pusers.
`
`
`
`
`
`
`
`
`
`
`
`
`Thus, it appears that most of the bandwidth on the Internet is
`
`
`
`
`
`
`
`
`
`
`
`being consumed by just a minority of the users. For this and
`
`
`
`
`
`
`
`
`
`
`other reasons, P2Ptraffic is viewed by ISP’s (Internet service
`
`
`
`
`
`
`
`providers) and others as being abusive/misbehaving traffic
`
`
`
`
`
`
`that should be controlled and penalized.
`In order to control P2P traffic, however,it first needs to be
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`identified. Earlier generations of P2P protocols used fixed
`
`
`
`
`
`
`
`
`TCPport numbersfor their transmissions. For example, Fast-
`
`
`
`
`
`
`
`
`
`
`
`Track used TCP port 1214. This made P2Ptraffic easy to
`
`
`
`
`
`
`
`
`
`identify. Current P2P protocols, however, no longer have to
`
`
`
`
`
`
`
`
`
`
`
`use fixed port numbers. Rather, they can be configured to use
`
`
`
`
`
`
`
`
`
`
`
`random dynamic port numbers so that P2P traffic can now be
`
`
`
`
`
`
`
`
`
`
`masqueraded as other types of traffic, such as HTTP web
`
`
`
`
`
`
`
`
`
`browsing and unspecified TCPtraffic. As a result, the current
`
`
`
`
`
`
`
`P2P protocols have rendered the port-based identification
`
`
`techniques ineffective.
`
`
`
`
`
`
`
`
`
`
`Another technique that has been usedto identify P2Ptraffic
`
`
`
`
`
`
`
`
`
`involves the use of signatures. Specifically, it was observed
`
`
`
`
`
`
`
`
`that some P2P protocols inserted distinct information into
`
`
`
`
`
`
`
`
`their data packets. Using this distinct information as a signa-
`
`
`
`
`
`
`
`
`
`ture, it was possible to identify packets that were assembled
`
`
`
`
`
`
`
`
`using those P2P protocols. This technique has several prob-
`
`
`
`
`
`
`
`
`
`
`
`lems. First, it usually is effective for only a relatively short
`
`
`
`
`
`
`
`
`
`
`period of time. As the P2P protocols evolve and mutate
`
`
`
`
`
`
`
`
`
`
`(which they do on a fairly constant basis), 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 prob-
`
`
`
`
`
`
`
`
`
`
`
`
`lem is that the P2P protocols are now evolvingto the point that
`
`
`
`
`
`
`
`
`
`they either leave no signature or they obfuscate their signa-
`
`
`
`
`
`
`
`
`
`tures (e.g. by encryption). This makes it extremely difficult if
`
`
`
`
`
`
`
`
`not impossible to identify P2P traffic using signatures.
`
`
`
`
`
`
`
`
`Overall, P2P protocals have gotten quite sophisticated, and
`
`
`
`
`
`
`
`
`
`
`
`the more sophisticated they become, the moredifficult it is to
`
`
`
`
`
`
`
`
`
`
`identify P2P traffic. Unless P2P traffic can be identified, it
`
`
`
`
`cannot be effectively controlled.
`
`
`
`
`
`
`
`SUMMARY
`
`
`
`
`
`
`
`
`
`
`
`In accordance with one embodimentof the present inven-
`
`
`
`
`
`
`
`
`tion, there is provided a mechanism foreffectively identifying
`
`
`
`
`
`
`
`
`and penalizing misbehaving information packet flows in a
`
`
`
`
`
`
`
`
`
`
`network. This mechanism may be applied to any type of
`
`
`
`
`
`
`
`
`
`networktraffic including, but certainly not limited to, P2P
`
`
`
`
`
`
`
`
`traffic. In one embodiment, misbehaving flowsare identified
`
`
`
`
`
`
`
`
`based upon their observed behavior. Unlike the prior
`
`
`
`
`
`
`
`
`approaches, they are not identified based upon ancillary fac-
`
`
`
`
`
`
`
`
`tors, suchas port numbers and signatures. Because misbehav-
`
`
`
`
`
`
`
`
`
`ing flows are identified based upon their observed behavior,
`
`
`
`
`
`
`
`
`and because their behavior cannot be hidden, misbehaving
`
`
`
`
`
`
`
`
`flows cannot avoid detection. Thus, regardless of which pro-
`
`
`
`
`
`
`
`
`
`tocols they use, or how those protocols try to hide/obfuscate
`
`
`
`
`
`
`
`
`their nature, misbehaving flows can be identified. Once iden-
`
`
`
`
`
`
`
`tified/detected, they can be controlled and/or penalized.
`
`
`
`
`
`
`
`20
`
`
`
`25
`
`
`
`
`
`
`
`40
`
`
`
`45
`
`
`
`50
`
`
`
`55
`
`
`
`60
`
`
`
`65
`
`
`
`
`2
`
`
`
`
`
`
`
`
`
`
`In one embodiment,a flow is processed as follows. One or
`
`
`
`
`
`
`
`
`
`more information packets belonging to the flow are received
`
`
`
`
`
`
`
`
`
`and processed. As the information packets are processed,a set
`of behavioral statistics are maintained for the flow. These
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`behavioralstatistics reflect the empirical behaviorofthe flow.
`In one embodiment, the behavioral statistics include a total
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`byte count (sum ofall of the bytes in all of the packets of the
`
`
`
`
`
`
`
`
`
`
`
`
`flow that have been processed up to the current time), a life
`
`
`
`
`
`
`
`
`
`
`duration (how long theflow has beenin existencesince incep-
`
`
`
`
`
`
`
`
`
`
`
`
`tion), a flow rate (derived by dividing the total byte count by
`
`
`
`
`
`
`
`
`
`
`
`the life duration of the flow), and an average packet size
`
`
`
`
`
`
`
`
`
`
`
`
`(derived by dividing the total byte count by the total number
`
`
`
`
`
`
`
`
`
`
`ofpacketsin the flow that have been processed). These behav-
`
`
`
`
`
`
`
`
`ioral statistics are updated as information packets belonging
`
`
`
`
`
`
`
`
`
`
`
`
`to the flow are processed; thus, they provide an up to date
`reflection of the flow’s behavior.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Based at 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 factor for the flow. This
`
`
`
`
`
`
`
`
`
`
`badness factor is computed based, at leastpartially, upon the
`
`
`
`
`
`
`
`
`behavioralstatistics, and this badness factor provides an indi-
`
`
`
`
`
`
`
`
`
`cation as to whetherthe flow is exhibiting undesirable behav-
`
`
`
`
`
`
`
`
`
`ior. In one embodiment, the badness factor also provides an
`
`
`
`
`
`
`
`
`
`
`indication of the degree to which the flow is misbehaving.
`
`
`
`
`
`
`
`
`If the flow is exhibiting undesirable behavior, then a pen-
`
`
`
`
`
`
`
`
`
`
`
`alty 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 onthe flow,this increased drop rate
`
`
`
`
`
`
`
`
`
`
`causes the information packets belonging to the flow to have
`
`
`
`
`
`
`
`
`a higher probability of being dropped than information pack-
`
`
`
`
`
`
`
`
`
`
`ets belonging to other flows that 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
`
`
`
`
`
`
`
`
`
`
`condition is encountered. Thus, if there is no congestion, the
`
`
`
`
`
`
`
`
`
`
`flow (even if it is exhibiting undesirable behavior) is not
`
`penalized.
`
`
`
`
`
`
`
`
`
`
`In one embodiment, enforcing the penalty on the flow has
`
`
`
`
`
`
`
`
`
`
`the effect 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 misbehaving flow can be turned into a non-misbe-
`
`
`
`
`
`
`
`
`
`
`
`having flow in the future. Once the flow is no longer misbe-
`
`
`
`
`
`
`
`
`
`
`
`having, it is no longer subject to penalty. In this manner, a
`
`
`
`
`
`
`
`
`
`misbehavingflow can beidentified, penalized, and even reha-
`
`
`
`
`
`
`
`
`bilitated in accordance with one embodimentof the present
`invention.
`
`
`
`
`
`
`
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`
`
`
`
`
`
`FIG. 1 shows an overview of a network in which one
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`embodimentof the present invention may be implemented.
`
`
`
`
`
`FIG.2 is a block diagram of a router in which one embodi-
`
`
`
`
`
`
`
`
`ment of the present invention may be implemented.
`
`
`
`
`
`
`
`
`
`FIG. 3 is an operational flow diagram showing the opera-
`
`
`
`
`
`
`
`tion of a misbehaving flow manager (MFM) in accordance
`
`
`
`
`
`
`
`with one embodimentofthe present invention.
`
`
`
`
`
`
`
`
`
`
`FIG.4 is a diagram of a sample flow block in accordance
`
`
`
`
`
`
`
`with one embodimentofthe present invention.
`
`
`
`
`
`
`
`
`FIG. 5 showsone possible function for computing a bad-
`ness factor for a flow in accordance with one embodimentof
`
`
`
`
`
`
`
`
`
`
`
`
`the present invention.
`
`
`
`
`
`
`
`
`
`
`
`Splunk Inc.—Exhibit 1001 Page 7
`
`Splunk Inc. Exhibit 1001 Page 7
`
`

`

`
`
`US 8,243,593 B2
`
`
`
`
`3
`DETAILED DESCRIPTION OF
`
`
`
`EMBODIMENT(S)
`
`
`
`Network Overview
`
`
`
`
`
`
`With reference to FIG. 1, there is shown an overview of a
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`network 100 in which one embodimentof the present inven-
`
`
`
`
`
`
`
`
`
`tion may be implemented. As shown,the network 100 com-
`
`
`
`
`
`
`
`
`
`prises a plurality of routers 102 interconnected to each other
`
`
`
`
`
`
`
`
`
`
`
`
`
`by trunks or links in such a way that cach router 102 has
`
`
`
`
`
`
`
`
`
`multiple possible paths to every other router 102. For
`
`
`
`
`
`
`
`
`example, information from router 102@ may reach router
`
`
`
`
`
`
`
`
`
`
`
`102d by going throughrouters 1026 and 102c, or routers 102¢
`
`
`
`
`
`
`
`
`
`
`and 102f and information from router 102c may reach router
`
`
`
`
`
`
`
`
`
`102a by going through router 1024 or router 102e. Intercon-
`
`
`
`
`
`
`
`
`
`necting the routers 102 in this way provides flexibility in
`
`
`
`
`
`
`
`
`determining how information from one router 102 is deliv-
`
`
`
`
`
`
`
`
`
`
`
`ered to another, and makesit possible to route around any
`
`
`
`
`
`
`
`
`
`
`
`failures 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.
`
`
`
`
`
`
`
`
`
`
`
`In addition to being coupled to each other, each router 102
`
`
`
`
`
`
`
`
`
`
`mayfurther be coupled to various machines (not shown), such
`
`
`
`
`
`
`
`
`
`as clients and servers, from which information originates and
`
`
`
`
`
`
`
`
`
`to which information is destined. By going through the rout-
`
`
`
`
`
`
`
`
`
`
`ers 102, each of these machines may send information to any
`of the other machinesin the network 100.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Information is conveyed from one router 102 to another via
`
`
`
`
`
`
`
`
`
`
`
`a physical link 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
`
`
`
`
`
`
`
`
`
`
`purposesofthe present invention, network 100 may use any
`
`
`
`
`type of transport medium.
`
`
`
`Router Overview
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`FIG. 2 showsa block diagram of a sample router 102 that
`
`
`
`
`
`
`
`
`
`
`
`
`
`may be used to implementone or moreofthe routers 102 in
`
`
`
`
`
`
`
`
`
`
`
`network 100. As shownin FIG.2, the router 102 comprises a
`
`
`
`
`
`
`
`
`
`
`
`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, assumingthat the router 102 in FIG.2 is router 1025
`
`
`
`
`
`
`
`
`
`
`
`in network 100, line card 202d may couple router 1025 to
`
`
`
`
`
`
`
`
`
`
`
`router 102 line card 202c may couple router 1024 to router
`
`
`
`
`
`
`
`
`
`
`
`102c, line card 2025 may couple router 102to router 102e,
`
`
`
`
`
`
`
`
`
`
`
`and line card 202@ may couple router 1026 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
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`coupledto the line cards 202 are bi-directional; thus, each line
`
`
`
`
`
`
`
`
`
`card 202 may receive information from another router, 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 information to another router). Whethera particular line
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`card 202 is acting as an ingress or an egress line card at any
`
`
`
`
`
`
`
`
`
`particular time depends uponthe flow of networktraffic.
`
`
`
`
`
`
`
`
`
`
`
`
`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 be transported from any ingress line card 202
`
`
`
`
`
`
`
`
`
`
`to any egress line card 202. By transporting information from
`
`
`
`
`
`
`
`
`
`
`
`
`an ingress line card 202 to an egress line card 202, the switch-
`
`
`
`
`
`4
`
`
`
`
`
`
`
`
`
`
`ing fabric 204 routes information throughthe router 102 and
`
`
`
`
`
`
`
`
`
`
`
`
`
`sends it on its way to the next hop (i.e. the next router).
`
`
`
`
`
`
`
`
`
`
`Information is thus received and routed by the router 102.
`
`
`
`
`
`
`
`
`
`
`
`To increasethe flexibility of the router 102 andto facilitate
`
`
`
`
`
`
`
`
`
`
`
`the process of failure recovery, each line card 202, in one
`
`
`
`
`
`
`
`
`embodiment, has multiple connectionsto the switching fabric
`
`
`
`
`
`
`
`
`
`204. In addition, the switching fabric 204 provides multiple
`
`
`
`
`
`
`
`
`
`
`routes for connecting each line card connection to 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 maypass through fabric card 206c, while another
`
`
`
`
`
`
`
`
`
`route may pass through fabric card 2065. By providing mul-
`
`
`
`
`
`
`
`
`
`tiple routes between the variousline cards 202, the switching
`
`
`
`
`
`
`
`
`
`fabric 204 makes it possible to route around any internal
`
`
`
`
`failures that mayarise.
`
`
`
`
`
`
`
`
`
`
`
`In addition to the line cards 202 and the switching fabric
`
`
`
`
`
`
`
`
`204, the router 102 further comprises an application proces-
`
`
`
`
`
`
`
`
`
`sor 208. In one embodiment, the application processor 208
`
`
`
`
`
`
`
`
`
`determines the forwarding paths, and hence, the egress line
`
`
`
`
`
`
`
`
`
`
`cards, that can be used to forward information to any particu-
`
`
`
`
`
`
`
`
`lar destination address. Put another way, given a destination
`
`
`
`
`
`
`
`
`address, the application processor 208 determines which line
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`card 202or line cards are mostsuitable to act as the egress line
`card to forward information to that destination address. For
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`example, supposethat the router 102 in FIG. 2 is router 1025
`
`
`
`
`
`
`
`
`
`
`in network 100, and that the destination is a machine coupled
`
`
`
`
`
`
`
`
`
`
`
`to router 102d. Supposefurtherthat line card 202c is coupled
`
`
`
`
`
`
`
`
`
`
`
`
`
`to router 102c andline card 202d is coupled to router 102 In
`
`
`
`
`
`
`
`
`
`
`
`such a case, because the mostdirect routes to router 102d are
`
`
`
`
`
`
`
`
`
`
`through either router 102c or 102/; the most suitable egress
`
`
`
`
`
`
`
`
`
`line cards for forwarding informationto the destination router
`
`
`
`
`
`
`
`
`
`
`102d are probably line cards 202c and 202d. Accordingly, the
`
`
`
`
`
`
`
`
`application processor 208 designates these line cards 202c,
`
`
`
`
`
`
`
`
`
`
`202d as potential egress line cards for destination router 102d,
`
`
`
`
`
`
`
`
`
`
`
`with one being designated as the primary egress line card and
`
`
`
`
`
`the other being the alternate.
`
`
`
`
`
`
`
`
`
`
`Oncethe egress line card determinations are made by the
`
`
`
`
`
`
`
`
`application processor 208 for each destination address, they
`are communicated to each of the 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,
`
`
`
`
`
`
`
`
`
`
`
`
`whena line card 202 acts as an ingress line card and receives
`
`
`
`
`
`
`
`
`
`
`
`a set of information, it can use the forwarding table to deter-
`
`
`
`
`
`
`
`
`
`
`
`mine the appropriate egress line card 202 to which to forward
`
`
`
`
`
`
`
`
`
`the information. Because the egress line card information is
`
`
`
`
`
`
`
`
`
`predetermined andstored in the forwardingtable, the ingress
`
`
`
`
`
`
`
`
`
`
`line card simply has to perform a table lookup to determine
`
`
`
`
`
`
`
`
`
`
`the properegressline card. No on-the-fly calculation needs to
`
`
`
`
`
`
`
`
`
`be performed. Since table lookup operations can be carried
`
`
`
`
`
`
`
`
`
`
`out very quickly, the process of determining the proper egress
`
`
`
`
`
`
`line card requires relatively little time.
`
`
`Information Routing
`
`
`
`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 informa-
`
`
`
`
`
`
`
`
`
`
`
`
`tion that is sent by a source to a destination. To enableit to be
`
`
`
`
`
`
`
`
`properly routed, a packet typically comprises a header por-
`
`
`
`
`
`
`
`
`
`
`tion. The header portion contains information that is used by
`
`
`
`
`
`
`
`
`
`
`
`
`the line cards 202 to determine the next hop for the packet.
`
`
`
`
`
`
`
`
`Depending upon the routing protocol used, the information
`
`
`
`
`
`
`
`
`
`contained in the header portion may differ. In one embodi-
`
`
`
`
`
`
`
`
`
`ment, the header portion comprises the following sets of
`
`
`
`
`
`
`
`
`
`information: (1) a source address (i.e. the network address of
`
`
`
`
`
`
`
`
`
`
`the entity sending the packet); (2) a source port number; (3) a
`
`
`
`16
`
`
`
`15
`
`
`
`20
`
`
`
`25
`
`
`
`30
`
`
`
`35
`
`
`
`40
`
`
`
`45
`
`
`
`50
`
`
`
`55
`
`
`
`60
`
`
`
`65
`
`
`
`
`
`Splunk Inc.—Exhibit 1001 Page 8
`
`Splunk Inc. Exhibit 1001 Page 8
`
`

`

`
`
`US 8,243,593 B2
`
`
`
`
`5
`
`
`
`
`
`
`
`
`
`
`destination address(i.e. the network address ofthe entity that
`
`
`
`
`
`
`
`
`
`
`
`is to receive the packet); (4) a destination port number;and (5)
`
`
`
`
`
`
`
`
`
`
`
`
`an indication of the routing protocol that is to be used. These
`
`
`
`
`
`
`
`
`
`
`
`sets of information may bereferred 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.
`
`
`
`
`
`
`
`
`
`
`In addition to the header portion, a packet also comprises a
`
`
`
`
`
`
`
`
`
`payload. The payload comprises the 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 other protocols (e.g. P2P
`
`
`
`
`
`
`
`
`
`protocols). This additional information may be needed by the
`
`
`
`
`
`
`destination to properly process the packet.
`
`
`
`
`
`
`
`
`
`
`In one embodiment, one or more packets may be grouped
`
`
`
`
`
`
`
`
`
`
`
`
`into a flow. For purposes of 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 amount ofheader information. More specifically, in
`
`
`
`
`
`
`
`
`
`
`
`one embodiment, packets belong to the sameflow ifthey have
`
`
`
`
`
`
`
`
`
`
`
`
`the five tuple in common.Thus, if two or more packets have
`
`
`
`
`
`
`
`
`
`
`the same source address, the same source port number, the
`
`
`
`
`
`
`
`
`samedestination address, the same destination port number,
`
`
`
`
`
`
`
`
`
`
`
`and the sameprotocol, they are grouped into the same flow.
`
`
`
`
`
`
`
`
`
`
`Usually, barring somefailure that requires rerouting,all ofthe
`
`
`
`
`
`
`
`
`
`
`packets belonging to a flow are received by the same ingress
`
`
`
`
`
`
`
`
`
`
`
`
`line card 202 and forwardedto the same egress line card 202.
`
`
`
`
`
`
`
`
`
`
`By grouping packets into flows, it is possible to aggregate
`
`
`
`
`
`
`
`
`
`
`individual packets in a meaningful way to enable a higher
`
`
`
`
`
`
`
`
`
`level understanding ofthe traffic flowing through the router
`102 to be derived.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`The flows that pass through a router 102 may represent
`
`
`
`
`
`
`
`
`
`
`many different types oftraffic. For example, the flows may
`
`
`
`
`
`
`
`
`
`
`contain web browsingtraffic, TCP traffic, P2P traffic, etc. As
`
`
`
`
`
`
`
`noted previously, sometraffic is more abusive/misbehaving
`
`
`
`
`
`
`
`
`
`
`
`than others. P2Ptraffic, for example, is often considered to be
`
`
`
`
`
`
`
`
`
`abusive. Other types oftraffic may also be considered abu-
`sive. To make the best use of available resources. and to best
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`control the traffic 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 enhanced to give the router 102 such capability.
`
`
`
`
`
`
`
`
`
`
`Morespecifically, the line cards 202 have been adapted to
`
`
`
`
`
`
`
`
`
`include a misbehaving flow manager (MFM)210 for keeping
`
`
`
`
`
`
`
`
`
`track of flows, determining whether the flows are exhibiting
`
`
`
`
`
`
`
`
`
`undesirable behavior, and enforcing a penalty on the flows if
`
`
`
`
`
`they are exhibiting undesirable behavior.
`
`
`
`
`
`
`
`
`
`
`
`For purposesof the present invention, the MFM 210 of the
`
`
`
`
`
`
`
`
`
`
`line cards 202 may be implemented in any desired manner.
`
`
`
`
`
`
`
`
`
`
`For example, the functionality of the MFM 210 maybereal-
`
`
`
`
`
`
`
`
`
`
`
`ized by having one or more processors on a line card 202
`
`
`
`
`
`
`
`
`execute one or more sets of instructions. Alternatively, the
`
`
`
`
`
`
`
`
`MFM210 may be implemented using hardwired logic com-
`
`
`
`
`
`
`
`
`
`
`
`ponents(e.g. in the form of one or more ASIC’s ona line card
`
`
`
`
`
`
`
`
`202). These and other implementations are within the scope
`
`
`
`
`of the present invention.
`
`
`
`
`
`
`
`Functional Overview of MFM on Line Card
`
`
`
`
`
`
`
`
`
`With reference to FIGS. 2 and 3, a functional overview of
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`the operation ofan MFM 210 in accordance with one embodi-
`
`
`
`
`
`
`
`
`
`
`
`ment of the present invention will now be described. In the
`
`
`
`
`
`
`
`
`
`
`
`following discussion, it will be assumedthat the MFM 210 is
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ona line card 202that is acting as an egress line 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
`
`
`
`
`
`
`
`
`6
`
`
`
`
`
`
`
`
`
`
`
`
`noted that the MFM 210 ona line card may process flows in
`
`
`
`
`
`
`
`
`
`
`
`
`
`the same manner even whentheline card 202 is acting as an
`
`
`
`
`
`
`
`
`
`
`
`ingress line card (i.e. the line card is receiving packets from
`
`
`
`
`
`
`
`
`
`
`another router and sending them to an egress line card).
`
`
`
`
`
`
`
`
`
`Initially, an MFM 210 receives and processes one or more
`
`
`
`
`
`
`
`
`
`packets belonging to a flow. Processing a packet may, but
`
`
`
`
`
`
`
`
`doesnot necessarily, involve forwardingthe packet to another
`
`
`
`
`
`
`
`
`
`
`router. As the packets of a flow are processed, a set of behav-
`
`
`
`
`
`
`
`
`
`
`
`ioral statistics are maintained (block 302 of FIG. 3) for the
`
`
`
`
`
`
`
`
`flow. These behavioralstatistics reflect the empirical behavior
`of the flow. In one embodiment, the behavioral statistics
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`include a total byte count (sum ofall of the bytesin all of the
`
`
`
`
`
`
`
`
`
`
`
`
`packets of the flow that have been processed up to the current
`
`
`
`
`
`
`
`
`
`
`
`time), a life duration (how longthe flow has been in existence
`
`
`
`
`
`
`
`
`
`
`since inception), a flow rate (derived by dividingthetotal byte
`
`
`
`
`
`
`
`
`
`
`
`
`countby the life duration of the flow), and an average packet
`
`
`
`
`
`
`
`
`
`
`
`
`size (derived by dividing the total byte count by the total
`
`
`
`
`
`
`
`
`
`
`number of packets in the flow that have been processed).
`
`
`
`
`
`
`
`
`
`
`
`These behavioralstatistics are stored by the line card 202 ina
`
`
`
`
`
`
`
`
`
`
`flow block associated with the flow, and are updated as infor-
`
`
`
`
`
`
`
`
`
`mation packets belonging to the flow are processed; thus,
`
`
`
`
`
`
`
`
`
`
`these behavioralstatistics provide an up to date reflection of
`the flow’s behavior.
`
`
`
`
`
`
`
`
`
`
`
`Based upon the behavioral statistics, the MFM 210 deter-
`
`
`
`
`
`
`
`
`
`mines(block 304) whether the flow is exhibiting undesirable
`
`
`
`
`
`
`
`
`
`behavior. In one embodiment, this determination is made by
`
`
`
`
`
`
`
`
`
`c