`
`Old'9093€€L
`
`
`
`70333Lllllllllllllllllllllllllll~
`
`UTILITY PATENT APPLICATION TRANSMITTAL
`
`ew Non u rovisional An lication Under 37 CFR 1.53 -
`
`Attomey Dooket No.
`60010—0020
`
`TO THE COMMISSIONER FOR PATENTS:
`
`) application identifier or (X) first named inventor, Vishnu Natchu, entitled
`Transmitted herewith is the patent application of (
`MECHANISM FOR IDENTIFYING AND PENALIZING MISBEHAVING FLOWS IN A NETWORK
`, for a(n):
`
`(X) Original Patent Application.
`
`(
`
`) Continuing Application (prior application not abandoned):
`(
`) Continuation
`(
`) Divisional
`(
`) Continuation-impart (CIP)
`of prior application No:
`Filed on:
`) A statement claiming priority under 35 USC § 120 has been added to the specification.
`(
`Enclosed are:
`
`113014u.s.pro11/022599lllllllllflllllllllllll
`
`Specification _30_ Total Pages; (X) Drawing(s) _5_ Total Sheets; (X) Cover SheetLPage
`(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 :1 Prior Application for Continuation/Divisional (37 CFR § 1.63(d)).
`(
`) Incorporation by Reference. The entire disclosure of the prior application, from which a copy of the
`oath or declaration is supplied, is considered as being part of the disclosure of the accompanying
`application and is hereby incorporated herein by reference in its entirety for all purposes.
`) Signed Statement Deleting Inventor(s) Named in the Prior Application. (37 CFR (j 163(d)(2)).
`(
`Power of Attorney.
`(X) Return Receipt Postcard.
`
`Associate Power of Attorney.
`()0 A Check in the amount of $ 2 240.00 for the Filing Fee.
`Preliminary Amendment.
`(
`)
`Information Disclosure Statement and Form PTO-1449.
`Request and 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 Small Entity Filed in Prior Application, Status Still Proper and Desired.
`Recordation of Assignment Cover Sheet and executed Assignment (2 pgs).
`
`(
`
`VVVVVVVVVV Other:
`
`><
`
`AAAAAAMAAA
`
`
`
`FOR
`Total Claims
`
`NO. FILED
`40
`
`CLAIMS AS FILED
`NO. EXTRA
`
`4 —
`lnde-endent Claims
`Multi le De-endent Claims if a licable
`Assi; ment Recordin; Fee
`Basic Filin Fee
`Search Fee
`Examination Fee
`Size Fee for each additional 50 sheets that exceeds IOO sheets
`
`RATE
`5 50-00
`$200.00
`
`Total Filin Fee
`pursuant to 37 CFR § 1.25.
`to Deposit Account
`Charge $
`(X) Throughout the pendency of this application, please charge any additional fees, including any required extension of time
`fees, and credit all overpayments to deposit account 50-1302. A duplicate of this sheet is enclosed.
`
`
`
`
`I hereby certify that this is being deposited with the US Postal
`
`Service “Express Mail Post Office to Addressee” service under
`37 CFR § 1.10 on the date indicated below and is addressed to:
`
`Respectfully submitted,
`
`Bobby K. Truong, Re . No. 37, 499
`
`Date: December 22, 2004
`
`
`Conespondence Address:
`
`29989
`
`
`
`
`By:W
`
`
`Date of Deposit: December 22, 2004
`
`
`Commissioner for Patents
`
`PO, Box 1450
`Alexandria, VA 22313-1450
`
`Typed Name: Carmen Frias
`
`Express Mail Label No.: EV56475807OUS
`
`Palo Alto Networks V. Sable Networks
`
`IPR2020-01712
`
`EX1002
`
`EX1002
`Palo Alto Networks v. Sable Networks
`IPR2020-01712
`
`
`
`‘
`
`ReductionAotof1995.no-
`
`-
`
`FEE TRANSMITTAL
`
`
`
`TOTAL AMOUNT OF PAYMENT
`
`($) 2,240.00
`
`PTO/SBI17 (12/04)
`Approved for use through 09/30/2005. OMB 0651-0032
`Patent and Trademark Office: US. DEPARTMENT OF COMMERCE
`are wuiredto an ,. toacoliectionofinfom'efionunlecsitd’ w avaiidOMBcontml number.
`
`
`
`—NYA
`Group/Art Unit
`NYA
`
`Attomey Docket No.
`
`60010-0020
`
`METHOD OF PAYMENT (check one)
`
`1
`
`'
`
`
`
`for FY 2005
`Patent fees are subject to annual revision,
`
`
`Small Entity paymentsM be supported by a small entity statement
`
`otherwise large entity fees must be paid. See Fonns PT06309-12
`
`
`See 37 C.F.R. §§ 1.27 AND 1. 28
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`3553331
`Number
`
`501302
`
`
`
`
`8'
`
`Check
`
`3.
`
`Fee Description
`
`1005
`
`200
`
`2005
`
`100
`
`1085
`
`250
`
`20835
`
`1463
`
`200
`
`1463
`
`1464
`
`1806
`8021
`
`130
`
`180
`40
`
`1464
`
`1806
`8021
`
`FEE CALCULATION continued
`
`
`
`meememyoffisamfiwfionfieasedmge
`3. ADDITIONAL FEES
`Fee Description
`Fee Paid
`anyadd‘itionalfees indudrnganylequiredextensionoftime
`Large Entity Small Entity
`
`feee.andaeditalloverpaymenistodeposiiatm1rit50-
`F88
`F39
`F69
`F99
`
`
`
`1302 Aduplitateomssheetisendosed.
`°°°°
`‘5’
`°°d°
`‘9
`
`1051
`130
`
`
`2051
`65 Surcharge — late filing fee or oath
` 1052
`50
`2052
`25 Surcharge - late provisional filing fee or
`cover sheet.
`
`
`
`3558:;
`Hickman Palemio Truong & Becker, LLP
`ame
`1251
`120
`2251
`60 Extension for reply within first month
`
`
`
`1252
`450
`2252
`225 Extension for reply within second month
`
`
`
`1253
`1,020
`2253
`510 Extension for reply within third month
`
`
`2-
`[2 Payment Enclosed:
`
`Money
`
` 1254 1,590 2254 795 Extension for reply within fourth month
`
`
`
`
`
`
`
`C] Other
`Order
`.
`.
`.
`.
`1255
`2,160
`2255
`1,080 Extension for re | within fifth month
`
`
`
`[I Appllwnt(s) is entitled to small entity status.
`p y
`
`
`See 37 CFR 1.27.
`
`
`
` 1401 2401 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
`Fee
`Fee
`Fee
`1453
`1,500
`2453
`750 Petition to revive — unintentional
`
`
`Code
`(5)
`Code
`(5)
`Paid
`
`1501
`1,400
`2501
`700 Utilityissuefee (or reissue)
`Utility filing fee
`1011
`300
`2011
`150
`3°°~°°
`
`
`
`
`Utility Search fee
`1111
`500
`2111
`250
`500-00
`1502
`800
`2502
`400 Design issue fee
`300 Publication Fee
`
`
`1504
`300
`2504
`
`Utility Examination fee
`1311
`200
`2311
`100
`200-00
`
`
`
`
`Utility Application Size
`1081
`250
`2081
`125
`
`400 Petitions Directornot specifically
`1462
`400
`1462
`
`
`
`
`Fee
`provided for Group l
`
`
`
`Provisional Application
`200 Petitions Director not specifically
`
`
`Fee
`provided for Group ll
`
`
`
`Provisional
`125
`130 Petitions Director not specifically
`Application Size Fee
`provided for Group III
`
`
`SUBTOTAL (1)
`
`180 Submission of information Disclosure Stmt
`
`
`
`
`2. EXTRA CLAIM FEES
`40 Recording each patent assignment per
`
`
`
`property (times number of properties)
`H‘ nest
`--
`-
`-
`1
`~
`Extra
`Feefrom
`
`
`
`
`2309
`790
`1809
`Plagid Claims Claims
`Below
`Fee Paid
`395 agngfggfimgggffle'fina'“gleam”
`
`
`
`Total Claims
`2810
`790
`1810
`-2o--= n x m =
`395 Foreach additional invention to be
`
`
`examined (37 CFR § 1.129(b))
`
`'"d'epende'"
`- X
`=
`Claims
`Other fee (specify)
`
`
`Multiple Dependent
`Other fee(spedfy)
`- =
`
`
`"or number previously paid, if greater; For Reissues, see below
`
`
`Large Entity Small Entity
`
`Fee Description
`Fee
`Fee
`Fee
`Fee
`Code
`(5)
`Code
`(5)
`1202
`50
`2202
`25
`Claims in excess of 20
`
`
`gidependent claims in excess of
`100
`2201
`200
`1201
`1203
`350
`2203
`130 Multiple dependent claim, if not paid
`
`“Reissue inde endent claims
`
`over original gatent
`1204
`200
`2204
`10°
`“Reissue claims in excess of 20
`
`
`25
`2205
`50
`1205
`and over original patent
`
`SUBTOTAL (2)
`($1,200.00
`‘Reduced by Basic Filing Fee Paid
`SUBTOTAL (3)
`
`
`
`
`summer) BY
`
`
`
`(Pint/ripe)
`31.499
`(408)414-1080
`__—oeoemberzzm
`
`information on this --nn may become pu . ic. Credit card information should not be
`
`
`Included on this f-
`. Provide credit can information and authorization on PTO-2038.
`Burden Hour Statement: This form is estimated to take 0.2 hours to camp! » e. 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 sent to the Chief Information Officer. Patent and Trademark Office, Washington, DC 20231.
`DO NOT SEND FEES 0R COMPLETED FORMS To THIS ADDRESS. SEND TO: Commissioner for Patents. PO. Box 1450. Alexandria. VA 22313-1450.
`
`
`
`1111111Ill1111111111111"
`
`,122204
`
`"
`
`UTILITY PATENT APPLICATION TRANSMITTAL
`
`Attomey DoCket No.
`
`60010—0020 l—
`
`ew Non rovisional A lication Under 37 CFR 1.53 I
`
`, 0.83
`”2 LO
`3%
`TO THE COMMISSIONER FOR PATENTS:
`'0‘,
`_
`V 0
`o:
`g Transmitted herewith is the patent application of (
`) application identifier or (X) first named inventor, Vishnu Natchu, entitled S :
`MECHANISM FOR IDENTIFYING AND PENALIZING MISBEHAVING FLOWS IN A NETWORK
`, for a(n):
`$2 ‘—
`C
`e—
`
`70338L
`
`.m (X) Original Patent Application.
`.0
`a (
`
`) Continuing Application (prior application not abandoned):
`(
`) Continuation
`(
`) Divisional
`(
`) Continuation-in-part(C1P)
`of prior application No:
`Filed on:
`.
`) A statement claiming priority under 35 USC § 120 has been added to the specification.
`
`(
`
`Enclosed are:
`
`(
`
`Specification ;0_ Total Pages; (X) Drawing(s) _5_ Total Sheets; (X) Cover Sheet 1 Page
`(X)
`(X) Oath or Declaration: A Pages
`(X) A Newly Executed Combined Declaration and Power of Attorney:
`(X) Signed.
`(
`) Unsigned.
`(
`) Partially Signed.
`) A Copy from 3 Prior Application for Continuation/Divisional (37 CFR § 1.63(d)).
`(
`) Incorporation by Reference. The entire disclosure of the prior application, from which a copy of the
`oath or declaration is supplied, is considered as being part of the disclosure of the accompanying
`application and is hereby incorporated herein by reference in its entirety for all purposes.
`) Signed Statement Deleting Inventor(s) Named in the Prior Application. (37 CFR § 163(d)(2)).
`(
`Power of Attorney.
`(X) Return Receipt Postcard.
`
`Associate Power of Attorney.
`(X) A Check in the amount of $ 2 240.00 for the Filing Fee.
`Preliminary Amendment.
`(
`)
`Information Disclosure Statement and Form PTO-1449.
`Request and Certification Under 35 USC. 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 Small Entity Filed in Prior Application, Status Still Proper and Desired.
`Recordation of Assignment Cover Sheet and executed Assignment (2 pgs).
`Other:
`
`
`
`><VvvvvvvvvvAAAAAAAAAA
`
`
`
`CLAIMS AS FILEDl
`FOR
`NO FILED
`NO. EXTRA
`TE
`Total Claims
`N0
`
`$1,000.00
`
`3 50.00
`$200.00
`
`4
`lnde endent Claims
`Multile De-endent Claims ifa- .licable
`Assi; ment Recordin; Fee
`Basie Filin_ Fee
`Search Fee
`Examination Fee
`
`Size Fee for each additional 50 sheets that exceeds 100 sheets
`Total Filin_ Fee
`l l
`pursuant to 37 CFR § 1.25.
`to Deposit Account
`Charge $
`(X) Throughout the pendency of this application, please charge any additional fees, including any required extension of time
`fees, and credit all overpayments to deposit account 50-1302. A duplicate of this sheet is enclosed.
`
`$0.00
`$2,240.00
`
`
`
`
`
`Bobby K. Truong, Re . No. 37, 499
`
`Commissioner for Patents
`
`
`PO. Box 1450
`
`
`
`
`
`Respectfully submitted,
`
`Date: December 22, 2004
`
`Correspondence Address:
`
`29989
`
`
`
`
`
`I hereby certify that this is being deposited with the US. Postal
`Service “Express Mail Post Office to Addressee” service under
`37 CFR § 1.10 on the date indicated below and is addressed to:
`
`Alexandria, VA 22313-1450
`
`1
`
`15'
`
`
`
`
`
`
`Typed Name: Carmen Frias
`
`Express Mail Label No.: EV564758070US
`
`Date of Deposit: December 22, 2004
`
`
`
`‘
`
`ReductionAotof1995.no-
`
`-
`
`FEE TRANSMITTAL
`
`
`
`TOTAL AMOUNT OF PAYMENT
`
`($) 2,240.00
`
`PTO/SBI17 (12/04)
`Approved for use through 09/30/2005. OMB 0651-0032
`Patent and Trademark Office: US. DEPARTMENT OF COMMERCE
`are wuiredto an ,. toacoliectionofinfom'efionunlecsitd’ w avaiidOMBcontml number.
`
`
`
`—NYA
`Group/Art Unit
`NYA
`
`Attomey Docket No.
`
`60010-0020
`
`METHOD OF PAYMENT (check one)
`
`1
`
`'
`
`
`
`for FY 2005
`Patent fees are subject to annual revision,
`
`
`Small Entity paymentsM be supported by a small entity statement
`
`otherwise large entity fees must be paid. See Fonns PT06309-12
`
`
`See 37 C.F.R. §§ 1.27 AND 1. 28
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`3553331
`Number
`
`501302
`
`
`
`
`8'
`
`Check
`
`3.
`
`Fee Description
`
`1005
`
`200
`
`2005
`
`100
`
`1085
`
`250
`
`20835
`
`1463
`
`200
`
`1463
`
`1464
`
`1806
`8021
`
`130
`
`180
`40
`
`1464
`
`1806
`8021
`
`FEE CALCULATION continued
`
`
`
`meememyoffisamfiwfionfieasedmge
`3. ADDITIONAL FEES
`Fee Description
`Fee Paid
`anyadd‘itionalfees indudrnganylequiredextensionoftime
`Large Entity Small Entity
`
`feee.andaeditalloverpaymenistodeposiiatm1rit50-
`F88
`F39
`F69
`F99
`
`
`
`1302 Aduplitateomssheetisendosed.
`°°°°
`‘5’
`°°d°
`‘9
`
`1051
`130
`
`
`2051
`65 Surcharge — late filing fee or oath
` 1052
`50
`2052
`25 Surcharge - late provisional filing fee or
`cover sheet.
`
`
`
`3558:;
`Hickman Palemio Truong & Becker, LLP
`ame
`1251
`120
`2251
`60 Extension for reply within first month
`
`
`
`1252
`450
`2252
`225 Extension for reply within second month
`
`
`
`1253
`1,020
`2253
`510 Extension for reply within third month
`
`
`2-
`[2 Payment Enclosed:
`
`Money
`
` 1254 1,590 2254 795 Extension for reply within fourth month
`
`
`
`
`
`
`
`C] Other
`Order
`.
`.
`.
`.
`1255
`2,160
`2255
`1,080 Extension for re | within fifth month
`
`
`
`[I Appllwnt(s) is entitled to small entity status.
`p y
`
`
`See 37 CFR 1.27.
`
`
`
` 1401 2401 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
`Fee
`Fee
`Fee
`1453
`1,500
`2453
`750 Petition to revive — unintentional
`
`
`Code
`(5)
`Code
`(5)
`Paid
`
`1501
`1,400
`2501
`700 Utilityissuefee (or reissue)
`Utility filing fee
`1011
`300
`2011
`150
`3°°~°°
`
`
`
`
`Utility Search fee
`1111
`500
`2111
`250
`500-00
`1502
`800
`2502
`400 Design issue fee
`300 Publication Fee
`
`
`1504
`300
`2504
`
`Utility Examination fee
`1311
`200
`2311
`100
`200-00
`
`
`
`
`Utility Application Size
`1081
`250
`2081
`125
`
`400 Petitions Directornot specifically
`1462
`400
`1462
`
`
`
`
`Fee
`provided for Group l
`
`
`
`Provisional Application
`200 Petitions Director not specifically
`
`
`Fee
`provided for Group ll
`
`
`
`Provisional
`125
`130 Petitions Director not specifically
`Application Size Fee
`provided for Group III
`
`
`SUBTOTAL (1)
`
`180 Submission of information Disclosure Stmt
`
`
`
`
`2. EXTRA CLAIM FEES
`40 Recording each patent assignment per
`
`
`
`property (times number of properties)
`H‘ nest
`--
`-
`-
`1
`~
`Extra
`Feefrom
`
`
`
`
`2309
`790
`1809
`Plagid Claims Claims
`Below
`Fee Paid
`395 agngfggfimgggffle'fina'“gleam”
`
`
`
`Total Claims
`2810
`790
`1810
`-2o--= n x m =
`395 Foreach additional invention to be
`
`
`examined (37 CFR § 1.129(b))
`
`'"d'epende'"
`- X
`=
`Claims
`Other fee (specify)
`
`
`Multiple Dependent
`Other fee(spedfy)
`- =
`
`
`"or number previously paid, if greater; For Reissues, see below
`
`
`Large Entity Small Entity
`
`Fee Description
`Fee
`Fee
`Fee
`Fee
`Code
`(5)
`Code
`(5)
`1202
`50
`2202
`25
`Claims in excess of 20
`
`
`gidependent claims in excess of
`100
`2201
`200
`1201
`1203
`350
`2203
`130 Multiple dependent claim, if not paid
`
`“Reissue inde endent claims
`
`over original gatent
`1204
`200
`2204
`10°
`“Reissue claims in excess of 20
`
`
`25
`2205
`50
`1205
`and over original patent
`
`SUBTOTAL (2)
`($1,200.00
`‘Reduced by Basic Filing Fee Paid
`SUBTOTAL (3)
`
`
`
`
`summer) BY
`
`
`
`(Pint/ripe)
`31.499
`(408)414-1080
`__—oeoemberzzm
`
`information on this --nn may become pu . ic. Credit card information should not be
`
`
`Included on this f-
`. Provide credit can information and authorization on PTO-2038.
`Burden Hour Statement: This form is estimated to take 0.2 hours to camp! » e. 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 sent to the Chief Information Officer. Patent and Trademark Office, Washington, DC 20231.
`DO NOT SEND FEES 0R COMPLETED FORMS To THIS ADDRESS. SEND TO: Commissioner for Patents. PO. Box 1450. Alexandria. VA 22313-1450.
`
`
`
`60010-0020
`
`Patent
`
`UNITED STATES PATENT APPLICATION
`
`FOR
`
`MECHANISM FOR IDENTIFYING AND PENALIZING
`MISBEHAVING FLOWS IN A NETWORK
`
`INVENTOR(S):
`
`VISHNU NATCHU
`\
`
`PREPARED BY:
`
`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 hereby certify that this paper or 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 above and is addressed to Commissioner for Patents,
`PO. Box 1450, Alexandria, VA 22313-1450.
`
`
`Carmen Frias
`
`(Typed or printed name of person mailing paper or fee)
`
`(Signgureofperson mailingpaperor fee)
`
`
`
`600 10-0020
`
`Background
`
`MECHANISM FOR IDENTIFYING AND PENALIZING
`
`MISBEHAVING FLOWS IN A NETWORK
`
`Inventor(s): Vishnu Natchu
`
`[0001]
`
`With the advent of file 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 number of non P2P users. 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, P2P traffic is viewed by ISP's (Internet service
`
`providers) and others as being abusive/misbehaving traffic 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 numbers for their transmissions. For
`
`example, FastTrack used TCP port 1214. This made P2P traffic 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 TCP
`
`traffic. As a result, the current P2P protocols have rendered the port-based identification
`
`techniques ineffective.
`
`
`
`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. Using this 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 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 more serious problem is that the P2P protocols are now evolving
`
`to the point that they either leave no signature or they obfuscate their signatures (e. g. by
`
`encryption). This makes it 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.
`
`Summg
`
`[0005]
`
`In accordance with one embodiment of the present invention, there is provided
`
`a mechanism for effectively identifying and penalizing misbehaving information packet
`
`flows in a network. This mechanism may be applied to any type of network traffic
`
`including, but certainly not limited to, P2P traffic. In one embodiment, misbehaving
`
`flows are identified based upon their observed behavior. Unlike the prior approaches,
`
`they are not identified based upon ancillary factors, such as port numbers and signatures.
`
`
`
`60010-0020
`
`Because misbehaving flows are 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 protocols try 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 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 behavioral
`
`statistics reflect the empirical behavior of the flow. In one embodiment, the behavioral
`
`statistics include a total byte count (sum of all 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 the flow
`
`has been in existence since inception), 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 of packets in the flow that have been processed).
`
`These behavioral 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.
`
`[0007]
`
`Based at least partially upon the behavioral statistics, 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 least partially, upon the behavioral statistics, and this
`
`badness factor provides an indication as to whether the flow is exhibiting undesirable
`
`behavior. In one embodiment, the badness factor also provides an indication of the
`
`degree to which the flow is misbehaving.
`
`
`
`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 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.
`
`[0009]
`
`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-misbehaving flow in the fiiture. Once the
`
`flow is no longer misbehaving, it is no longer subject to penalty. In this manner, a
`
`misbehaving flow can be identified, penalized, and even rehabilitated in accordance with
`
`one embodiment of the present invention.
`
`Brief Description of the Drawings
`
`[0010]
`
`Fig. 1 shows an overview of a network in which one embodiment of the
`
`present invention may be implemented.
`
`[0011]
`
`Fig. 2 is a block diagram of a router in which one embodiment of the present
`
`invention may be implemented.
`
`
`
`60010-0020
`
`[0012]
`
`Fig. 3 is an operational flow diagram showing the operation of a misbehaving
`
`flow manager (MFM) in accordance with one embodiment of the present invention.
`
`[0013]
`
`Fig. 4 is a diagram of a sample flow block in accordance with one
`
`embodiment of the present invention.
`
`[0014]
`
`Fig. 5 shows one possible fimction for computing a badness factor for a flow
`
`in accordance with one embodiment of the present invention.
`
`Detailed Description of Embodiment] 3)
`
`Network Overview
`
`[0015]
`
`With reference to Fig. 1, there is shown an overview of a network 100 in
`
`which one embodiment of the 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 may reach router 102d by going
`
`through routers 102b and 102C, or routers 102e and 102f, and information from router
`
`102e may reach router 102a by going through router 102b or router 102e.
`
`Interconnecting the routers 102 in this way provides flexibility in determining how
`
`information from one router 102 is delivered to another, and makes it 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.
`
`
`
`60010-0020
`
`[0016]
`
`In addition to being coupled to each other, each router 102 may further 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
`
`routers 102, each of these machines may send information to any of the other machines in
`
`the network 100.
`
`[0017]
`
`Information is conveyed from one router 102 to another via a physical link or
`
`trunk. Depending on the 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 of the
`
`present invention, network 100 may use any type of transport medium.
`
`Router Overview
`
`[0018]
`
`Fig. 2 shows a block diagram of a sample router 102 that may be used to
`
`implement one or more of the routers 102 in network 100. As shown in 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, assuming that the router 102 in
`
`Fig. 2 is router 102b in network 100, line card 202d may couple router 102b to router
`
`102f, line card 202C may couple router 102b to router 1020, line card 202b may couple
`
`router 102b. to router 1026, 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 may receive information from another router, or send information to
`
`another router. Put another way, each line card 202 is capable of acting as an ingress line
`
`card (to receive information from another router) or an egress line card (to send
`
`
`
`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 upon the flow of network traffic.
`
`[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 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 switching fabric 204 routes information through the
`
`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.
`
`[0020]
`
`To increase the flexibility of the router 102 and to 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 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 may pass
`
`through fabric card 206C, while another route may pass through fabric card 206b. By
`
`providing multiple routes between the various line cards 202, the switching fabric 204
`
`makes it possible to route around any internal failures that may arise.
`
`[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 forwarding paths, and hence, the egress line cards, that can
`
`
`
`60010-0020
`
`be used to forward information to any particular destination address. Put another way,
`
`given a destination address, the application processor 208 determines which line card 202
`
`or line cards are most suitable to act as the egress line card to forward information to that
`
`destination address. For example, suppose that the router 102 in Fig. 2 is router 102b in
`
`network 100, and that the destination is a machine coupled to router 102d. Suppose
`
`further that line card 2020 is coupled to router 1020 and line card 202d is coupled to
`
`router 102f. In such a case, because the most direct routes to router 102d are through
`
`either router 1020 or 102f, the most suitable egress line cards for forwarding information
`
`to the destination router 102d are probably line cards 2020 and 202d. Accordingly, the
`
`application processor 208 designates these line cards 2020, 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.
`
`[0022]
`
`Once the 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. Thereafier, when a line card 202 acts as
`
`an ingress line card and receives a set of information, it can use the forwarding table to
`
`determine the appropriate egress line card 202 to which to forward the information.
`
`Because the egress line card information is predetermined and stored in the forwarding
`
`table, the ingress line card simply has to perform a table lookup to detemiine the proper
`
`egress line 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.
`
`
`
`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 upon the routing protocol used, the information contained in the header
`
`portion may differ. In one embodiment, 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 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 protocol that 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 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 may also 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.
`
`[0025]
`
`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 grouped into a flow if they share a sufficient
`
`
`
`60010-0020
`
`amount of header information. More specifically, in one embodiment, packets belong to
`
`the same flow if they have the five tuple in common. Thus, if two or more packets have
`
`the same