`
`
`
`
`
`
`
`US 7,342,929 B2
`(10) Patent No.:
`a2) United States Patent
`
`
`
`
`
`
`
`(45) Date of Patent:
`Bremler-Barretal.
`Mar. 11, 2008
`
`
`
`
`US007342929B2
`
`
`
`
`
`
`(54) WEIGHTED FAIR QUEUING-BASED
`
`
`
`
`METHODS AND APPARATUS FOR
`
`
`PROTECTING AGAINST OVERLOAD
`
`
`CONDITIONS ON NODES OF A
`DISTRIBUTED NETWORK
`
`
`
`
`
`
`
`(75)
`
`
`
`
`
`
`
`
`
`Inventors: Anat Bremler-Barr, Holon (IL); Dan
`
`
`
`
`Touitou, Ramat-Gan (IL); Keren
`
`
`
`
`
`Horvitz, Hod Hasharon dL); Rephael
`
`
`
`
`
`Tzadikario, Kefar Sava (IL); Yehuda
`
`
`
`Afek, Hod-HaSharon (IL)
`
`
`
`
`
`
`
`(73) Assignee: (us) Technology, Inc., San Jose, CA
`
`
`
`
`
`
`
`
`Subject to any disclaimer, the term ofthis
`(*) Notice:
`
`
`
`
`patent is extended or adjusted under 35
`
`
`
`
`U.S.C. 154(b) by 1030 days.
`
`
`
`
`(21) Appl. No.: 10/134,048
`
`
`
`
`
`Apr. 26, 2002
`,
`oo.
`
`
`
`
`Prior Publication Data
`
`
`
`
`
`
`US 2003/0076848 Al
`Apr. 24, 2003
`
`
`
`
`Related U.S. Application Data
`(60) Provisional application No. 60/286,943,filed on Apr.
`
`
`
`
`
`
`97. 2001.
`
`
`°
`(51)
`Int. Cl.
`
`
`(2006.01)
`HOAL 1228
`
`
`370/395.4: 370/412
`(52) US. Cl
`
`
`
`
`
`
`”
`eesveeDoreen
`
`
`
`
`
`
`(58) Field of Classification Search 0.0.0.0.ee None
`
`
`
`
`
`
`
`See application file for complete search history.
`
`
`References Cited
`
`
`U.S. PATENT DOCUMENTS
`
`
`
`
`
`5,689,508 A
`11/1997) Lyles woe eeeeeeee 370/391
`
`
`
`
`
`
`5,905,730 A
`5/1999 Yang etal. wee 370/429
`
`
`
`Filed:
`
`(22)
`
`(65)
`
`
`
`(56)
`
`
`
`
`
`
`
`
`5,917,822 A *
`
`5,956,340 A *
`
`6,041,059 A *
`
`
`
`
`
`6/1999 Lyles etal. we. 370/395.4
`
`
`
`
`9/1999 Afek et al. oo 370/412
`
`
`
`
`
`3/2000 Joffe et al... 370/412
`(Continued)
`
`FOREIGN PATENT DOCUMENTS
`
`
`
`
`
`
`
`
`
`
`
`wo
`
`
`
`
`
`
`4/2002
`WO 02/33870
`OTHER PUBLICATIONS
`
`
`
`
`
`
`
`
`
`
`Bennett, J.C.R. et al. “Hierarchical Packet Fair Queueing Algo-
`
`
`
`
`rithms.”, IEEE (Oct. 1997).
`(Continued)
`
`
`
`
`Primary Examiner—Edan Orgad
`
`
`
`
`Assistant Examiner—lung Park
`
`
`
`
`
`
`(74) Attorney, Agent, or Firm—David J. Powsner; DanielJ.
`
`Kligler
`
`
`
`
`
`
`
`
`
`ABSTRACT
`(57)
`
`
`
`
`
`
`
`An improved network device that controls throughput of
`
`
`
`
`
`
`packets received thereby, e.g., to downstream devices or to
`
`
`
`
`
`
`
`downstream logic contained within the same network
`
`
`
`
`
`
`
`device. The network device comprises a scheduler that
`
`
`
`
`
`
`
`
`
`schedules one or more packets of a selected class for
`
`
`
`
`
`
`
`
`
`throughput as a function of a weight of that class and
`
`
`
`
`
`
`
`
`Weights ofone or more other classes, The weight of at least
`
`
`
`
`
`
`
`the selected class is dynamic and is a function ofa history
`
`
`
`
`
`
`
`
`of volume of packets received by the network device in the
`
`
`
`
`
`
`
`selected class. An apparatus for protecting against overload
`
`
`
`
`
`
`
`
`conditions on a network, e.g., of the type caused by DDoS
`
`
`
`
`
`
`
`
`attacks, has a scheduler and a token bucket mechanism,e.g.,
`
`
`
`
`
`
`
`
`as described above. Such apparatus can also include a
`
`
`
`
`
`
`
`
`
`plurality of queues into which packets of the respective
`
`
`
`
`
`
`
`classes are placed on receipt by the apparatus. Those packets
`
`
`
`
`
`
`
`
`are dequeued by the scheduler, e.g., in the manner described
`
`
`
`
`
`
`
`above, for transmittal to downstream devices(e.g., potential
`
`
`
`
`victim nodes) on the network.
`
`
`
`
`37 Claims, 6 Drawing Sheets
`
`
`
`
`
`
`
`
`
`User-Source
`(dentifier
`
`
`
`
`Drop
`
`
`
`Rate-Limiter
`
`
`
`(e.g., token
`
`
`leaky bucket)
`
`Authenticator
`
`ingMechanism
`
`Cookie-Mark-
`
`
`
`
`Q3 >_>
`
`
`
`Filters:
`Input from
`
`
`
`
`
`
`1, Anti-Spoof
`Network
`.
`
`
`Classify
`r—>) Classify
`
`
`
`
`
`
`-
`Recognition
`
`
`
`
`
`
`
`
`
`Drop
`
`Back to Client
`
`(Source)
`
`
`
`
`Qo
`|__|
`
`Q1
`Q2
`te}
`
`
`
`
`
`
`
`
`
`
`
`Overall Rate
`
`Limiter
`
`
`
`
`Splunk Inc.
`
`Exhibit 1030
`
`Page 1
`
`Splunk Inc. Exhibit 1030 Page 1
`
`

`

`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`6/2000 Lee .....eceeeeeeseseereceeeeeee 370/412
`6,072,800 A
`
`
`
`
`
`
`
`10/2000 Stiliadis et al.
`wee 370/232
`6,134,217 A
`
`
`
`
`
`
`
`1/2001 Win etal. .........
`wee 709/229
`6,182,142 B1*
`
`
`
`
`
`
`
`3/2001 Stephens etal. ..
`wee 370/395
`6,208,652 Bl
`
`
`
`
`
`
`
`4/2001 Ghanietal. ......
`we 370/230
`6,215,769 B1*
`
`
`
`
`
`
`
`3/2005 Appala etal.
`wee 370/235
`6,862,265 B1*
`....
`
`
`
`
`
`
`
`...
`3/2005 Talpade et al.
`we 370/412
`6,862,291 B2*
`
`
`
`
`
`
`
`6,975,638 B1* 12/2005 Chen etal.
`....
`we 370/412
`
`
`
`
`
`
`7,058,974 B1*
`6/2006 Maheretal. ..... 726/13
`2001/0012272 Al*
`8/2001 Aubert et al.
`.......0.00.. 370/230
`
`
`
`
`
`
`
`2002/0097726 A1l*
`7/2002 Garcia-Luna-Aceves
`
`
`
`
`et al. ee eeeeee 370/395.31
`
`
`
`
`
`
`
`
`8/2002 Yang....
`wee 370/395.1
` 8/2005 Patrick «0.0... 370/395.43
`
`
`
`
`
`
`
`
`2002/0114334 Al*
`2005/0175014 Al*
`
`
`
`
`
`
`
`OTHER PUBLICATIONS
`
`
`
`
`
`
`
`
`
`
`
`Bennett, J.C.R. et al. “High Speed, Scalable, and Accurage Imple-
`
`
`
`
`
`
`
`mentation of Fair Queueing Algorithms in ATM Networks.”, ICNP
`
`(1997).
`
`
`
`
`
`
`
`
`
`Bennett, J.C.R. et al. “WFQ: Worst-case Fair Weighted Fair
`
`
`Queueing.”, Infocom’96.
`
`
`
`
`
`
`
`
`Chiussi, F.M. et al. “Implementing Fair Queueing in ATM Switches:
`
`
`
`
`
`The Discrete-Rate Approach.”, IEEE’ 1997.
`
`
`
`
`
`
`Chiussi, F.M. et al. “Minimum-Delay Self-Clocked Fair Queueing
`
`
`
`
`
`Algorithm for Packet-Switched Networks.”IEEE 1998.
`
`
`
`
`
`
`
`Demers, A. et al. “Analysis and Simulation of a Fair Queueing
`
`
`
`
`
`
`Algorithm,” © 1989 Association for Computing Machinery.
`
`
`
`
`
`
`
`Eckhardt, D.A. et al. “Effort-limited Fair (ELF) Scheduling for
`
`
`
`
`
`Wireless Networks,” IEEE Infocom 2000.
`
`
`
`
`
`
`
`Golestani, S.J. “Network Delay Analysis of a Class of Fair Queue-
`
`
`
`
`
`
`ing Algorithms,” IEEE Journal on Selected Areas in Communica-
`
`
`
`
`
`
`
`
`tions, vol. 13 No. 6 (Aug. 1995) pp. 1057-1070.
`
`
`
`
`
`
`
`Golestani, S.J. “A Self-Clocked Fair Queueing Scheme for Broad-
`
`
`
`
`
`
`
`
`band Applications,” IEEE © 1994 pp. Sce.1.1-Sel.11.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`US 7,342,929 B2
`
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Greenberg, Albert G. et al. “How Fair is Fair Queuing?” Journal of
`
`
`
`
`
`
`
`
`
`the Association for Computing Machinery vol. 39 No. 3 (Jul. 1992)
`
`
`pp. 568-598.
`
`
`
`
`
`
`Parekh, A.K.J. “A Generalized Processor Sharing Approach to Flow
`
`
`
`
`
`
`Control in Integrated Services Networks,” Ph.D. Dissertation Mas-
`
`
`
`
`
`sachusetts Institute of Technology (Feb. 1992).
`
`
`
`
`
`
`
`
`Parekh, A.K.et al. “A Generalized Processor Sharing Approach to
`
`
`
`
`
`
`
`
`Flow Control in Integrated Services Networks: The Multiple Node
`
`
`
`
`
`
`
`Case,” IEEE/ACM Transactions on Networking vol. 2 No. 2 (Apr.
`
`
`
`1994) pp. 137-150.
`
`
`
`
`
`
`
`
`Parekh, A.K.et al. “A Generalized Processor Sharing Approach to
`
`
`
`
`
`
`
`Flow Control in Integrated Services Networks: The Single-Node
`
`
`
`
`
`
`
`Case,” IEEE/ACM Transactions on Networking vol. 1, No. 3 (Jun.
`
`
`
`1993) pp. 344-357.
`
`
`
`
`
`
`
`“Quality of Service Networking,” downloaded from the web
`
`(address:
`http://www.cisco.com/univered/cc/td/doc/cisintwk/
`
`
`
`
`
`
`ito__doc/qos.htm) © Cisco Systems, Inc., 1999.
`
`
`
`
`
`
`
`
`Rexford, J.L. et al. “Hardware-Efficient Fair Queueing Architec-
`
`
`
`
`
`
`
`
`tures for High-Speed Networks,” IEEE © 1996 pp. 5d.2.1-5d.2.9.
`
`
`
`
`
`
`
`
`Shreedhar M. et al. “Efficient Fair Queuing Using Deficit Round-
`
`
`
`
`
`
`
`Robin,” IEEE/ACM Transactions on Networking vol. 4 No. 3 (Jun.
`
`
`
`1996) pp. 375-385.
`
`
`
`
`
`
`
`Stiliadis, D. et al. “Frame-based Fair Queueing: A New Traffic
`
`
`
`
`
`
`Scheduling Algorithm for Packet-Switched Networks,” (Jul. 18,
`
`
`
`1995) pp. 1-43.
`
`
`
`
`
`
`
`
`
`U.S. Appl. No. 09/929,877, filed Aug. 14, 2001, entitled: “Method
`
`
`
`
`
`
`
`and apparatusfor protecting against overloaded conditions on nodes
`of a distributed network”.
`
`
`
`
`
`
`
`
`
`
`
`
`U.S. Appl. No. 60/286,943, filed Apr. 27, 2001, entitled: ““Weighted-
`
`
`
`
`
`
`
`fair queuing based apparatus for defending against distributed.
`denial of service attacks”.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`* cited by examiner
`
`
`
`Splunk Inc.
`
`Exhibit 1030
`
`Page 2
`
`Splunk Inc. Exhibit 1030 Page 2
`
`

`

`
`U.S. Patent
`
`
`
`
`Mar.11, 2008
`
`
`
`
`
`Sheet 1 of6
`
`
`
`US 7,342,929 B2
`
`
`he
`
`
`o
`
`
`fs
`
`R|iN
`
`CJ
`
`sno re
`
`Splunk Inc.
`
`Exhibit 1030
`
`Page 3
`
`1 F
`
`
`IG.
`
`
`
`
`oo
`
`Splunk Inc. Exhibit 1030 Page 3
`
`

`

`
`U.S. Patent
`
`
`
`
`Mar. 11, 2008
`
`
`
`
`Sheet 2 of 6
`
`
`
`US 7,342,929 B2
`
`WY
`
`
`
`ro(aonanayof]Z‘Ol4
`vASLnovd&a|&:a#SIDIOVd
`N:]Asons)ar
`ncne,x
`jn/fpecsn
`
`nt8
`
`
`
`Splunk Inc.
`
`Exhibit 1030
`
`Page 4
`
`Splunk Inc. Exhibit 1030 Page 4
`
`
`

`

`U.S. Patent
`
`Mar. 11, 2008
`
`Sheet 3 of 6
`
`US 7,342,929 B2
`
`Udy0}*3°9)
`
`(joyongAye9]
`
`CoonJBINPOLYOS
`
`801NOS-J8Sf
`
`JayUsp|
`
`WISTUBYS|{ Ut
`RIA-anjoeD
`
`esto
`
`Ea
`
`joodg-nuy‘T
`
`‘STON
`
`
`
`Ayssej|j¢#-————
`
`tolinduy
`
`YIOMION
`
`JOUWWTTWs]01Yoe|
`
`deyT]eI9AO
`
`UIEdoigdoiq
`
`(a0mos)
`
`Fig. 3A
`
`Splunk Inc.
`
`Exhibit 1030
`
`Page 5
`
`Splunk Inc. Exhibit 1030 Page 5
`
`
`
`
`
`
`

`

`
`U.S. Patent
`
`
`
`Mar. 11, 2008
`
`Sheet 4 of 6
`
`
`
`US 7,342,929 B2
`
`Joyeonusyny
`
`8OINOS-J9S/)
`
`Jeynuap]
`
`wsTURYapy Bui
`IeW-oryjoo
`
`woTTUsOONY
`
`
`
`
`
`yndyng
`
`081ey
`
`peiee
`
`AjIsseyD
`
`Joodg-nuy"J
`
`
`Ayisse]Q|¢——
`
`YIOMION
`
`SLO)UT
`
`woryuduy
`
`JOU]Wl]OFPed
`
`
`
`SEYTEISAQOWUEdoiq
`
`dog
`
`(200s)
`
`Fig. 3B
`
`Splunk Inc.
`
`Exhibit 1030
`
`Page 6
`
`Splunk Inc. Exhibit 1030 Page 6
`
`
`
`
`
`

`

`
`U.S. Patent
`
`
`
`
`Mar.11, 2008
`
`
`
`
`Sheet 5 of6
`
`
`
`US 7,342,929 B2
`
` Single user
`
`
`source
`
`
`
`
`
`
`
`
`
`A proxy with no
`
`
`malicous source
`
`
`
`Before Queue Decomposition:
`
`
`
`A proxy with
`
`
`
`
`
`
`malicous sources
`
`
`
`After Queue Decomposition:
`
`
`
`
`
`
`
`
`
` Innocent sources
`
`
`
`
`malicous sources
`
`
`
`
`
`
`
`
`
` Single user
`
`
`
`
`
`
`
`source
`
`W=1
`
` We=1,1,1,
`
`W=1,1,1, Wel
`
`W=1
`
`W=1
`
`
`Fig. 4
`
`Splunk Inc.
`
`Exhibit1030
`
`Page 7
`
`Splunk Inc. Exhibit 1030 Page 7
`
`

`

`
`U.S. Patent
`
`
`
`
`Mar.11, 2008
`
`
`
`
`Sheet 6 of6
`
`
`
`US 7,342,929 B2
`
`
`FIG. 5
`
`OF HISTORY
`
`
`
`
`
`ASSIGN BUCKET TO EACH PACKET
`
`
`
`
`CLASS WITH VOLUME A FUNCTION
`
`
`
`V
`
`
`
`
`
`
`MODEL BUCKET FILL RATE, MAX
`
`
`
`
`
`AND MIN CAPACITY FOR EACH CLASS
`
`
`
`1
`
`
`
`
`REDUCE BUCKET PROPORTIONALLY
`
`
`
`
`TO PACKET THROUGHPUT OF CLASS
`
`1
`
`
`
`
`
`DETERMINE DYNAMIC WEIGHT FOR
`
`
`
`EACH CLASS BUCKET VOLUME/HISTORY
`
`
`
`
`
`Mu
`
`
`
`
`
`
`
`
`SCHEDULE PACKETS FOR THROUGHPUT
`
`
`
`BASED ON DYNAMIC WEIGHTS,
`
`
`BUCKET VOLUME/CONTENT:
`
`
`
`
`
`
`
`* ALLOW BURSTS AS LONG AS AVG
`
`
`
`
`CLASS RATE<PEAK
`
`
`
`
`
`¢ DISCRIMINATE STREAMS>AVG FOR
`
`
`
`
`
`
`LONG PERIODS
`
`
`
`
`
`e APPLY CONSTRAINTS ONLY AS NEEDED
`
`
`
`
`TO KEEP OVERALL THROUGHPUT<C
`
`
`
`
`Splunk Inc.
`
`Exhibit1030
`
`Page8
`
`Splunk Inc. Exhibit 1030 Page 8
`
`

`

`
`1
`
`
`
`WEIGHTED FAIR QUEUING-BASED
`METHODS AND APPARATUS FOR
`
`
`
`
`PROTECTING AGAINST OVERLOAD
`
`
`CONDITIONS ON NODES OF A
`
`
`DISTRIBUTED NETWORK
`
`
`
`
`
`
`
`US 7,342,929 B2
`
`
`2
`
`
`
`
`
`
`operation thereof as can be used in existing networks, such
`
`
`
`
`
`
`as the Internet, as well as in other networks.
`
`
`
`
`
`
`
`Yeta still further object of the invention is to provide data
`
`
`
`
`
`
`
`networks, nodes, devices and methods of operation thereof
`
`
`
`
`
`
`
`
`as can be implemented at low cost andare scalable.
`
`
`
`
`
`
`
`
`
`
`
`This application claims the benefit of U.S. Provisional
`
`
`
`
`
`
`
`
`
`Patent Application Ser. No. 60/286,943 filed Apr. 27, 2001,
`
`
`
`
`
`entitled “Weighted-Fair-Queuing Based Apparatus For
`
`
`
`
`
`
`Defending Against Distributed Denial Of Service Attacks,”
`
`
`
`
`
`
`
`the teachings of which are incorporated herein by reference.
`
`BACKGROUND OF THE INVENTION
`
`
`
`
`
`
`
`
`
`
`
`
`The invention pertains to distributed data networks and,
`
`
`
`
`
`
`moreparticularly, protecting against overload conditions at
`
`
`
`
`
`
`
`
`nodes of such networks.
`It has application, by way of
`
`
`
`
`
`
`
`non-limiting example, in protecting servers, sites and other
`
`
`
`
`
`
`
`
`
`elements of networks, such as the Internet and the like, from
`
`
`
`
`
`
`
`
`distributed denial of service (DDoS) attacks and flash
`crowds.
`
`
`
`
`
`
`
`Early computer
`systems were typically stand-alone
`
`
`
`
`
`
`
`
`
`devices that processed only commands and data entered via
`
`
`
`
`
`
`
`
`dedicated local keyboards, tape drives, disk drives, card
`
`
`
`
`
`
`
`
`
`
`readers, or the like. Remote access waspossible, but only via
`
`
`
`
`
`
`
`
`phone lines and modems, which essentially served as sur-
`
`
`
`
`
`
`rogates or proxies to remote users’ keyboards. By the early
`
`
`
`
`
`
`
`
`1980’s, a national network had been developed for carrying
`
`
`
`
`
`
`data communications between university, defense depart-
`
`
`
`
`
`
`
`
`
`ment and other large computer systems. This early Internet
`
`
`
`
`
`
`
`(known then as the ARPANET), which relied on a mix of
`
`
`
`
`
`
`
`
`dedicated lines and modems, was inaccessible to the public
`
`
`
`
`
`
`
`
`
`
`at large and, hence, subject to outages and espionage but, for
`
`
`
`
`
`
`
`
`
`the most part, not wide scale attack from “hackers.”
`
`
`
`
`
`
`
`Through the 1990’s,
`that national network expanded
`
`
`
`
`
`
`
`around the globe adding millions of governmental, research
`and commercial nodes. The latter included so-called Internet
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`service providers (ISPs) that afforded low-cost access to the
`
`
`
`
`
`
`
`
`masses. People being as they are, this included a mischie-
`
`
`
`
`
`
`
`vous if not downright scurrilous element intent—at least
`
`
`
`
`
`
`
`insofar as their time, resources and interests permitted—on
`
`
`
`
`
`
`
`
`blocking access to popular nodes(or “sites”) on the network.
`
`
`
`
`
`
`
`
`The most
`insidious form of this cybervandalism is the
`
`
`
`
`
`
`
`
`distributed denial of service (DDoS) attack, in which the
`
`
`
`
`
`
`
`
`computers that service requests coming in to a node are
`
`
`
`
`
`
`
`
`swamped by millions of fake requests that may seem to
`
`
`
`
`
`
`
`
`come from many sources but, ultimately, emanate from a
`
`
`
`few hackers’ computers.
`
`
`
`
`
`
`
`
`Despite numerous DDoS attacks that have taken place
`
`
`
`
`
`
`
`
`
`over the past few years, with a surge of attacks on YAHOO,
`
`
`
`
`
`
`
`
`
`
`CNN, and many other major sites, there is still no known
`
`
`
`
`
`
`online solution for defense against them.
`
`
`
`
`
`
`In view of the foregoing, an object of this invention is to
`
`
`
`
`
`
`
`provide improved distributed data networks and methods of
`
`
`
`
`
`
`
`
`operation thereof. A related object of the invention is to
`
`
`
`
`
`
`
`provide improved nodes, devices and methods of operation
`thereof for use on such distributed data networks.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Further related objects are to provide such improved data
`
`
`
`
`
`
`
`networks, nodes, devices and methods of operation thereof
`
`
`
`
`
`
`
`that provide enhanced protection from overload conditions,
`
`
`
`malicious, legitimate or otherwise.
`
`
`
`
`
`
`
`
`A still further related object is to provide such improved
`
`
`
`
`
`
`
`
`data networks, nodes, devices and methods of operation
`
`
`
`
`
`
`
`thereof that provide enhanced protection from DDoS
`attacks.
`
`
`
`
`
`
`
`
`Yet a still further object of the invention is to provide such
`
`
`
`
`
`
`
`
`improved data networks, nodes, devices and methods of
`
`
`
`
`
`20
`
`25
`
`
`
`30
`
`
`
`35
`
`
`
`40
`
`
`
`45
`
`
`
`50
`
`
`
`55
`
`
`
`60
`
`
`
`65
`
`
`
`SUMMARY OF THE INVENTION
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`The foregoing are among the objects attained by the
`
`
`
`
`
`
`
`invention which provides, in one aspect, an improved net-
`
`
`
`
`
`
`
`work device that controls throughput of packets received
`
`
`
`
`
`
`thereby, e.g., to downstream devices or to downstream logic
`contained within the same network device. The network
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`device comprises a scheduler that schedules one or more
`
`
`
`
`
`
`packets of a selected class for throughput as a function of a
`
`
`
`
`
`
`
`
`
`weight of that class and weights of one or more otherclasses.
`
`
`
`
`
`
`
`
`The weightofat least the selected class is dynamic and is a
`
`
`
`
`
`
`function of a history of volume of packets received by the
`network device in the selected class.
`
`
`
`
`
`
`
`
`
`
`
`Related aspects of the invention provide a network device
`
`
`
`
`
`
`
`as described above in which the scheduler is substantially a
`
`
`
`
`
`
`
`
`weighted fair queuing (WFQ) scheduler that uses, as a
`
`
`
`
`
`
`
`
`
`weight for the one or more packets of the selected class, the
`
`
`
`
`
`
`dynamic weight of the class. Further related aspects of the
`
`
`
`
`
`
`
`
`invention provide such a network device in which the
`
`
`
`
`
`
`
`
`scheduler is a round robin or deficit round robin (DRR)
`
`
`
`
`
`
`
`
`
`scheduler which, again, uses as a weight for the one or more
`
`
`
`
`
`
`
`
`packets of the selected class, the dynamic weight of that
`class.
`
`
`
`
`
`
`
`
`Still further aspects of the invention provide a network
`
`
`
`
`
`
`device as described above comprising a rate-limiter that
`
`
`
`
`
`
`
`
`determines the dynamic weightof at least the selected class.
`
`
`
`
`
`
`
`That rate-limiter can be any of a leaky bucket mechanism
`
`
`
`
`
`
`
`and a token bucket mechanism (collectively, “token bucket
`
`
`
`
`
`
`
`
`mechanism”) which uses a bucket for each of at least the
`
`
`
`
`
`
`
`
`
`selected class and one or more other classes, and which
`
`
`
`
`
`
`
`
`models each bucket as (i) filling at a rate associated with the
`
`
`
`
`
`
`
`respective class, (11) having a minimum capacity associated
`
`
`
`
`
`
`
`
`
`with that class, and a maximum capacity associated with that
`class.
`
`
`
`
`
`
`
`
`
`
`Still other aspects of the invention provide a network
`device as described above in which the token bucket mecha-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`nism reduces each bucket proportionally to a volume of
`
`
`
`
`
`
`
`packets throughput for the respective class by the scheduler.
`
`
`
`
`
`
`Related aspects of the invention provide for determining a
`
`
`
`
`
`
`
`
`volume ofa bucketfor at least a class i for an epoch t, during
`
`
`
`
`
`
`
`
`
`
`which one or more packets for that class are actually or
`
`
`
`
`
`
`
`theoretically pending for throughput as a function of a
`relation
`
`
`Li(h)=
`
`
`
`masa minBi, Lit) -(2-4)e
`
`
`
`
`W(t)
`
`x
`Wy(t1)
`J active at ty
`
`
`
`t+(h -un}
`
`
`
`where
`
`
`
`
`
`
`
`
`L,(t,) is the volumeofthe bucket for class i during epoch
`
`ty;
`
`
`
`
`
`
`
`L,(t,) is the volumeofthe bucket for class i during epoch
`
`t;
`
`
`
`
`
`
`
`
`B,/”” is a minimum capacity for the bucket for class i;
`
`
`
`
`
`
`
`
`B, is a maximum capacity for the bucket for class i;
`
`
`
`
`
`
`
`C is a measure of overall traffic throughputby the device;
`Splunk Inc.
`Exhibit 1030
`Page 9
`
`
`
`Splunk Inc. Exhibit 1030 Page 9
`
`

`

`
`
`US 7,342,929 B2
`
`
`3
`
`
`
`
`
`
`W,(t,) is a weight assigned to class i during epoch t,;
`
`
`
`
`
`
`W{t,) is a weight assigned to class j during epoch t,;
`
`
`
`
`
`
`r,s a filling rate of the bucket for class 1.
`
`
`
`
`
`
`Related aspects of the invention provide for determining
`
`
`
`
`
`
`
`
`a volume of a bucket for at least a class i for an epoch t,
`
`
`
`
`
`
`
`
`
`
`during which one or more packets for that class are not
`
`
`
`
`
`
`actually or theoretically pending for throughputas a function
`of a relation
`
`
`
`
`
`E,{to)=max{B"" min{B, Lt)+(ta-t)r; }}
`
`
`4
`
`
`
`
`
`
`
`Further aspects of the invention provide a network appa-
`
`
`
`
`
`
`
`ratus as described abovethat includes a marking mechanism
`
`
`
`
`
`
`which transmits a cookie to a packet source on the network
`
`
`
`
`
`
`
`
`and causes that source to include the cookie in packets
`
`
`
`
`
`transmitted by it to on the network to a destination associ-
`
`
`
`
`
`
`
`
`
`ated with the apparatus. The marking mechanism can, more-
`
`
`
`
`
`
`
`
`
`over, strip the cookie from any packets transmitted by the
`
`
`
`
`
`
`
`
`source to the destination. It can also determine the suspi-
`
`
`
`
`
`
`ciousness of a packet based on a cookie, if any, therein. As
`
`
`
`
`
`
`
`
`above, that suspiciousness can be used by a classifier in
`
`
`
`
`determining placement of a packet in a queue.
`
`
`
`
`
`
`
`
`Related aspects of the invention can utilize such cookies
`
`
`
`
`
`
`
`
`
`to discern individual user session from among stream of
`
`
`
`
`
`
`
`
`
`packets that have the same source and destination IP
`
`
`
`
`
`addresses, ports and/or packet types.
`
`
`
`
`
`
`
`
`Still further aspects of the invention provide methods
`
`
`
`
`
`
`
`
`paralleling the operations described above. These and other
`
`
`
`
`
`
`
`
`aspects of the invention are evident in the drawings and in
`
`
`
`
`the description that follows.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`
`
`
`
`
`
`
`
`
`
`
`
`A more complete understanding of the invention may be
`
`
`
`
`
`attained by reference to the drawings, in which:
`
`
`
`
`
`
`FIG. 1 depicts a distributed network of the type with
`
`
`
`
`which the invention is practiced;
`
`
`
`
`
`
`
`FIG.2 depicts packettraffic generated by nodes NO-N3 in
`
`
`
`the network of FIG. 1;
`
`
`
`
`
`
`FIGS. 3A-3B depict a network apparatus according to one
`
`
`
`practice of the invention;
`
`
`
`
`
`
`
`FIG. 4 depicts a result of use of the marking/cookie
`
`
`
`
`
`
`
`mechanism to segregate flows in an apparatus of FIGS.
`
`
`3A-3B; and
`
`
`
`
`
`
`that schematically illustrate a
`FIG. 5 is a flow chart
`
`
`
`
`
`
`method for controlling throughout of a network device, in
`
`
`
`
`
`
`accordance with an embodiment of the present invention.
`DETAILED DESCRIPTION OF THE
`
`
`ILLUSTRATED EMBODIMENT
`
`
`
`
`
`
`
`
`
`
`
`
`
`Terminology
`Information transfers on the Internet are broken into
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`variable size packets, each of which contains, in addition to
`
`
`
`
`
`
`
`
`
`its data (payload), control information to be used for its
`
`
`
`
`
`
`
`
`
`routing and scheduling over the network.In the sections that
`
`
`
`
`
`
`
`
`
`follow, the terms below are used in the conventional sense
`
`
`
`
`
`
`
`
`(also provided below), except where otherwise evident from
`
`
`
`
`
`context, to characterize information transfers of the Internet
`
`
`
`
`
`and, more generally, over IP networks.
`
`
`
`
`
`
`IP address: A 32 bit label that uniquely identifies a device.
`
`
`
`
`
`
`TCP/IP port number: A 16 bit label that uniquely identifies
`
`
`
`
`an application within a device.
`
`
`
`
`
`
`Packet Labels (Identifiers): Each IP packet is labeled by
`
`
`
`
`
`
`
`
`
`the following five labels: 1) Source IP address, 2)
`
`
`
`
`
`
`Source TCP/IP port number, 3) Destination IP address,
`
`
`
`
`
`
`
`4) Destination TCP/IP port number, and 5) Protocol
`
`
`
`
`
`
`
`type. These labels are used by TCP/IP for controlling
`
`
`
`
`and routing the packet.
`
`
`
`
`
`IP connection: A source application/destination applica-
`
`
`
`
`
`
`
`
`tion pair which exchange data. The connection can be
`
`
`
`
`
`
`
`uniquely identified by the five packet labels described
`above.
`
`
`
`
`
`
`
`
`IP flow: The packets transmitted over an IP connection.
`
`
`
`
`
`
`
`HTTP: A protocol running over TCP/IP supporting the
`
`
`
`
`
`
`
`retrieval of web pages by clients from Web servers.
`
`
`
`
`
`
`HTTP Proxy: A mediator server that is used to mediate
`between a collection of HTTP clients and HTTP serv-
`
`
`
`
`
`
`
`
`
`
`
`
`
`SplunkInc.
`
`Exhibit 1030
`
`Page 10
`
`
`
`
`
`
`
`where
`
`
`
`
`
`
`
`
`
`
`L,(t,) is the volumeofthe bucket for class 1 during epoch
`
`t,;
`
`
`
`
`
`
`
`L,(t,) is the volumeofthe bucket for class 1 during epoch
`
`ts
`
`
`
`
`
`
`
`
`B/”” is a minimum capacity for the bucketforclass i;
`
`
`
`
`
`
`
`
`B, is a maximum capacity for the bucket for class 1;
`
`
`
`
`
`
`
`r, is a filling rate of the bucket for class 1.
`
`
`
`
`
`
`
`Still further related aspects of the invention provide for
`
`
`
`
`
`
`
`
`determining a volume of the bucket for class 1 at epoch t
`
`
`
`
`
`
`
`during which one or more packets are throughput as a
`function of the relation
`
`
`
`
`
`
`20
`
`25
`
`
`
`30
`
`
`
`
`
`
`
`L(®=max{B7"™,min{B, L,()\-D}
`where
`
`
`
`
`
`
`
`
`
`L,(t) is the volume of the bucket for class 1 during epoch
`
`t
`
`
`
`
`
`
`
`
`B/”” is a minimum capacity for the bucketforclass i;
`
`
`
`
`
`
`
`
`B, is a maximum capacity for the bucket for class 1;
`
`
`
`
`
`
`D is an actualor estimated size of the one or more packets
`
`throughput.
`
`
`
`
`
`
`
`Yet still further related aspects of the invention provide
`network devices as described above in which the scheduler
`
`
`
`
`
`
`
`
`
`
`
`
`
`35
`schedules for throughputat a time t a volumeofpackets of
`
`
`
`
`
`
`
`
`the selected class that is proportional to a content of the
`bucket for that class at that time. The scheduler can schedule
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`for throughput only whole packets of a class and, if there are
`
`
`
`
`
`
`
`
`partial packets that would otherwise be scheduled for
`
`
`
`
`
`
`
`
`
`throughput, it can credit the bucket associated with that class
`
`accordingly.
`
`
`
`
`
`
`
`
`In other aspects the invention provides apparatus for
`
`
`
`
`
`
`protecting against overload conditions on a network,e.g., of
`
`
`
`
`
`
`
`
`the type caused by DDoS attacks, having a scheduler and a
`
`
`
`
`
`
`
`
`token bucket mechanism, e.g., as described above. Such
`
`
`
`
`
`
`
`
`apparatus can also include a plurality of queues into which
`
`
`
`
`
`
`packets of the respective classes are placed on receipt by the
`
`
`
`
`
`
`
`apparatus. Those packets are dequeued by the scheduler,
`
`
`
`
`
`
`
`
`
`in the manner described above,
`for transmittal
`to
`e.g.,
`
`
`
`
`
`
`
`
`downstream devices (e.g., potential victim nodes) on the
`network.
`
`
`
`
`
`
`
`
`Still other aspects of the invention provide apparatus as
`
`
`
`
`
`
`
`
`described above having one or moreclassifiers that classify
`
`
`
`
`
`
`
`
`
`packets for placement in the queues. This can be on the
`
`
`
`
`
`
`
`basis, for example, of source IP addresses, source TCP/IP
`
`
`
`
`
`
`
`ports, destination IP addresses, destination TCP/IP port
`
`
`
`
`
`
`
`numbers, protocol types, and/or other parameters, associated
`
`
`
`with the packets.
`
`
`
`
`
`
`
`Related aspects of the invention provide such apparatus
`
`
`
`
`
`
`with functionality that determines
`suspiciousness of a
`
`
`
`
`
`
`
`
`packet. The classifiers, according to these aspects, place the
`
`
`
`
`
`
`
`packets in the queues based both on classification and on
`
`
`
`
`
`suspiciousness. Packets of a higher degree of suspiciousness
`
`
`
`
`
`
`
`
`are placed, for example, in different queues from packets of
`
`
`
`
`
`
`
`a lower degree of suspiciousness. The scheduler schedules
`
`
`
`
`
`
`
`
`
`with lowerpriority queues allocated to the former, and with
`
`
`
`
`
`
`higher priority queues allocated to the latter.
`
`40
`
`
`
`45
`
`
`
`50
`
`
`
`55
`
`
`
`60
`
`
`
`65
`
`
`
`Splunk Inc. Exhibit 1030 Page 10
`
`

`

`
`5
`
`
`
`
`
`
`
`
`
`ers. The HTTP proxy receives the HTTP requests from
`
`
`
`
`
`
`
`
`the clients associated with it, and serves them either by
`
`
`
`
`
`
`
`retrieving the requested documents from its own
`
`
`
`
`
`
`memory or by requesting them (and retrieving them)
`
`
`
`
`
`
`
`
`
`from the network (the proper HTTPserver). Note that
`
`
`
`
`
`
`
`
`when an HTTPproxyserver conducts the retrieval from
`
`
`
`
`
`
`
`
`the network it sends a request whose source ID (IP
`
`
`
`
`
`
`
`
`
`address and port) is that of the HTTP proxy server.
`
`
`
`
`
`
`
`
`in this event the traffic shipped to the HTTP
`Thus,
`
`
`
`
`
`
`
`
`
`server over the network does not carry the IP address/
`
`
`
`
`
`
`
`port of the client who madethe request; ratherit carries
`
`
`
`
`
`
`the IP address/port of the HTTP proxyserver.
`
`
`
`
`
`
`Cookie: A label that is used by HTTPservers to identify
`
`
`
`
`
`
`
`
`HTTP clients, typically with unique codes (such as user
`
`
`
`
`
`
`
`
`
`IDs). The HTTPserver assigns the label to each client,
`which the latter uses in further accesses to the server.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Note that when a client sends a cookie via a proxy
`
`
`
`
`
`
`
`
`server, the cookie is preserved; that is, when the proxy
`
`
`
`
`
`
`
`server issues the request to the server it includes in it
`
`
`
`
`
`
`
`
`
`the cookie as placed on the original request by the
`client.
`
`
`
`
`
`
`
`
`Session: A series of requests and responses between a
`
`
`
`
`
`
`
`
`website, server, or other target and a human end-user,
`
`
`
`
`
`
`
`typically, over period of of a few minutes to a few
`25
`
`
`
`
`
`
`
`hours, for purposes of browsing, carrying out a “web
`
`
`
`
`
`
`
`transaction” or conducting some other activity. An
`
`
`
`
`
`
`example is visiting an on-line “bookstore,” browsing,
`
`
`
`
`
`
`
`adding items to the shopping cart and paying—all,
`
`
`
`
`
`together, which constitutes a sample session.
`30
`
`
`
`
`
`
`
`FIG. 1 depicts a distributed network of the type with
`
`
`
`
`
`
`
`which the invention is practiced. Illustrated are nodes N
`
`
`
`
`
`
`
`(including nodes N0-N4) configured as local area networks
`
`
`
`
`
`
`
`(LANs), wide area networks (WANs), data-centers, metro-
`
`
`
`
`
`
`
`politan area networks (MANs) or other subnetworks or
`
`
`
`
`
`
`portions interconnected by switching elements R. TheIIlus-
`
`
`
`
`
`
`
`trated network comprises an IP network,such as the Internet.
`
`
`
`
`
`
`
`
`
`
`However, those skilled in the art will appreciate that the
`
`
`
`
`
`
`
`teachings herein maybe applied to networks operating under
`
`
`
`other protocols, as well.
`
`
`
`
`
`
`
`Illustrated nodes N comprise hosts and servers of the type
`
`
`
`
`
`
`
`commonly used on an IP network, such as the Internet. In
`
`
`
`
`
`
`
`
`addition, the nodes may comprise any device or collection of
`
`
`
`
`
`
`
`devices capable of directly or indirectly interfacing with the
`
`
`
`
`
`
`
`network or portion thereof, e.g., though an interface card,
`
`
`
`
`
`gateway or other network interface apparatus.
`
`
`
`
`
`Illustrated switching elements R are of the type commer-
`
`
`
`
`
`
`
`cially available in the marketplace and commonly used on
`
`
`
`
`
`
`
`
`
`an IP network, such as the Internet, to route data between
`
`
`
`
`
`
`
`nodes and/or within and between portions of the network.
`
`
`
`
`
`
`These
`switching elements
`include routers, gateways,
`
`
`
`
`
`
`
`
`
`switches, bridges, and other digital data apparatus of the
`
`
`
`
`
`
`
`
`
`
`type known in the art for the aforesaid purpose. The ele-
`
`
`
`
`
`
`
`
`ments R may also include “guard machines” of the type
`
`
`
`
`
`
`
`described in copending commonly assigned U.S. Pat. No.
`55
`
`
`
`
`
`
`
`09/929,877, filed Aug. 14, 2001, PCT PCT/US01/32273,
`
`
`
`
`
`
`
`
`
`filed Oct. 16, 2001, entitled “Methods and Apparatus for
`
`
`
`
`
`
`
`Protecting Against Overload Conditions on Nodes of a
`
`
`
`
`
`
`
`Distributed Network,” the teachings of which are incorpo-
`
`
`
`
`
`
`
`rated herein by reference, particularly, for example, at FIGS.
`
`
`
`
`
`1-3, and the accompanyingtext.
`
`
`
`
`
`
`
`FIG.1 also depicts apparatus D according to the invention
`
`
`
`
`
`
`
`
`
`that protects a node, here, node N4, from an networktraffic
`
`
`
`
`
`
`
`overload condition. That condition,
`in the illustrated
`
`
`
`
`
`
`
`embodiment, is a DDoSattack; however, those skilled in the
`
`
`
`
`
`
`
`
`
`art will appreciate that the teachings hereof may be applied
`
`
`
`
`
`
`
`
`
`in the protection of nodes against other network traffic-
`
`
`
`
`
`
`related overload conditions. The apparatus D may be located
`
`
`
`
`
`
`
`6
`
`
`
`
`
`
`
`
`between associated node N4 andthe sourcesoftraffic to it,
`
`
`
`
`
`
`
`such that part or all of the traffic destined to that victim N4
`
`
`
`
`
`
`
`
`passes through the apparatus D before reaching the N4
`
`
`
`
`
`
`
`
`
`(hereinafter, typically referred to as the “victim”). In the
`
`
`
`
`
`illustration, apparatus D is positioned immediately upstream
`
`
`
`
`
`
`
`
`
`from victim N4 and, hence, all traffic destined from N4
`
`
`
`
`
`passes through D. In another embodiment, apparatus D may
`
`
`
`
`
`
`
`
`be positioned to receive traffic destined for N4 only during
`
`
`
`
`
`
`
`
`an actual or apparent DDoS attack. Such