`111111111111
`
`I VIII IIIIII 11111
`
`(12) United States Patent
`Bremler-Barr et al.
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 7,342,929 B2
`Mar. 11, 2008
`
`(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 (IL); Rephael
`Tzadikario, Kefar Sava (IL); Yehuda
`Afek, Hod-I laSharon (IL)
`
`(73)
`
`Assignee: Cisco Technology, Inc., San Jose, CA
`(US)
`
`(*)
`
`Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 1030 days.
`
`(21) Appl. No.: 10/134,048
`
`(22) Filed:
`
`Apr. 26, 2002
`
`(65)
`
`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.
`27, 2001.
`
`(51) Int. Cl.
`(2006.01)
`HO4L 12/28
` 370/395.4; 370/412
`(52) U.S. Cl.
` None
`(58) Field of Classification Search
`See application file for complete search history.
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`5,689,508 A
`11/1997 Lyles
`5,905,730 A
`5/1999 Yang et al.
`
`370/391
`370/429
`
`5,917,822 A * 6/1999 Lyles et al.
`5,956,340 A * 9/1999 Afek et al.
`6,041,059 A * 3/2000 Joffe et al
`
`370/395.4
`370/412
`370/412
`
`(Continued)
`
`FOREIGN PATENT DOCUMENTS
`
`WO
`
`WO 02/33870
`
`4/2002
`
`OTHER PUBLICATIONS
`
`Bennett, J.C.R. et al. "Hierarchical Packet Fair Queueing Algo-
`rithms.", IEEE (Oct. 1997).
`
`(Continued)
`
`Primary Examiner—Edan Orgad
`Assistant Examiner—Jung Park
`(74) Attorney, Agent, or Firm—David J. Powsner; Daniel J.
`Kligler
`
`(57)
`
`ABSTRACT
`
`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 of one or more other classes. The weight of at 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. 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
`
`Recognition
`
`Filters:
`1. Anti-Spoo
`
`_ o Classify
`
`--1AuthentIcator
`
`-IUser-Scarce
`
`Identifier
`
`Drop
`
`00
`
`01
`
`Q2
`
`Q3
`
`Drop
`
`Permit
`
`Back to Client
`(Source)
`
`Input Iron
`Nclwork
`
`Oa. sift/
`
`Drop
`
`Emulator
`
`Scheduler
`
`Rate 0
`
`Rotel
`
`Rate2
`
`Rate3
`
`Rate-Limiter
`(e g token
`leaky bucket)
`
`Output
`to
`Victim
`
`Overall Rate
`Limiter
`
`Cloudflare - Exhibit 1030, page 1
`
`Cloudflare - Exhibit 1030, page 1
`
`
`
`US 7,342,929 B2
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`6/2000 Lee
`6,072,800 A
`10/2000 Stiliadis et al.
`6,134,217 A
`1/2001 Win et al.
`6,182,142 BI *
`3/2001 Stephens et al.
`6,208,652 B1
`6,215,769 B I * 4/2001 Ghani et al.
`6,862,265 BI *
`3/2005 Appala et al.
`6,862,291 132 * 3/2005 Talpade et al.
`6,975,638 B I * 12/2005 Chen et al.
`7,058,974 BI * 6/2006 Maher et al.
`2001/0012272 A I * 8/2001 Aubert et al.
`2002/0097726 Al * 7/2002 Garcia-Luna-Aceves
`et al.
` 370/395.31
`2002/0114334 Al * 8/2002 Yang
` 370/395.1
`2005/0175014 Al * 8/2005 Patrick
` 370/395.43
`
` 370/412
` 370/232
` 709/229
` 370/395
` 370/230
` 370/235
` 370/412
` 370/412
` 726/13
` 370/230
`
`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. "WF2Q: 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," C 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 C 1994 pp. 5c.1.1-5c1.11.
`
`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.cordunivercd/cc/td/doc/cisintwk/
`ito_doc/qos.htm) C Cisco Systems, Inc., 1999.
`Rexford, J.L. et al. "Hardware-Efficient Fair Queueing Architec-
`tures for High-Speed Networks," IEEE C 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 apparatus for 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
`
`Cloudflare - Exhibit 1030, page 2
`
`Cloudflare - Exhibit 1030, page 2
`
`
`
`U.S. Patent
`
`Mar. 11, 2008
`
`Sheet 1 of 6
`
`US 7,342,929 B2
`
`CC
`0
`
`LLI
`
`CC
`O
`
`C:C O
`
`CC
`O
`
`CC
`
`Cloudflare - Exhibit 1030, page 3
`
`Cloudflare - Exhibit 1030, page 3
`
`
`
`lualed 'SA
`
`9 Jo Z Jaaqs
`
`ZS 6Z6`Zb£`L Sf1
`
`NO
`
`PACKETS
`
`NETWORK
`
`NETWORK
`
`NI
`
`•
`
`•
`
`•
`
`NETWORK
`
`N
`
`R
`
`FIG. 2
`
`4.
`
`11
`PACKETS
`
`NETWORK
`
`N6
`
`NETWORK
`
`N
`
`PACKETS
`
`Wt
`
`.41
`
`N
`
`NETWORK
`
`PACKETS
`416
`
`N4
`
`N5
`
`NETWORK
`
`/
`
`Cloudflare - Exhibit 1030, page 4
`
`Cloudflare - Exhibit 1030, page 4
`
`
`
`lua1ud 'S'il
`
`•JRIAI
`
`sooz
`
`9 JO £ pails
`
`zs 6Z6‘ZPVL S11
`
`Recognition
`
`Input from
`Network
`
`Classify
`
`I. Anti-Spoof
`
`Classify
`
`Authenticator
`
`User-Source
`Identifier
`
`❑rop
`
`00
`
`01
`
`Q2
`
`Q3
`
`Drop
`
`)71
`
`Back to Client
`(Source)
`
`Drop
`
`Permit
`
`Emulator
`
`Scheduler
`
`Rate 0
`
`Ratel
`
`Rate2
`
`Rate3
`
`Rate-Limiter
`(e.g., token
`leaky bucket)
`
`Output
`to
`Victim
`N4
`
`Overali Rate
`Limiter
`
`Cloudflare - Exhibit 1030, page 5
`
`Cloudflare - Exhibit 1030, page 5
`
`
`
`lualud *S11
`
`sooz `ti•Juhi
`
`9 Jo
`
`ZEI 6Z6`Z17£`L Sil
`
`-HAuthenticator
`
`-I 6
`X 8
`
`;)
`
`'V
`User-Source
`Identifier
`
`Drop
`
`Recognition
`
`Filters:
`1. Anti-Spoof
`
`Classify
`
`QO
`
`Q1
`
`Q2
`
`Q3
`
`Drop
`
`Permit
`
`Back to Client
`(Source)
`
`Rate-Limiter
`(e.g., token
`leaky bucket)
`
`Rate 0
`
`Ratel
`
`Rate3
`
`Output
`to
`Victim
`N4
`
`Overall Rate
`Limiter
`
`Input from
`Network
`
`Classify
`
`Drop
`
`0
`
`0.
`
`tF
`
`cA)
`
`Cloudflare - Exhibit 1030, page 6
`
`
`
`U.S. Patent
`
`Mar. 11, 2008
`
`Sheet 5 of 6
`
`US 7,342,929 B2
`
`Before Queue Decomposition:
`
`A proxy with no
`malicous source
`
`A proxy with
`malicous sources
`
`Single user
`source
`
`W=1
`
`W=3
`
`W=4
`
`W=1
`
`W=1
`
`W=1
`
`After Queue Decomposition:
`
`Innocent sources
`
`malicous sources
`
`Single user
`source
`
`TT-
`
`W=1
`
`w=1,1,1,
`
`w=1,1,1. w=1
`
`w=1
`
`W=1
`
`Fig. 4
`
`Cloudflare - Exhibit 1030, page 7
`
`Cloudflare - Exhibit 1030, page 7
`
`
`
`U.S. Patent
`
`Mar. 11, 2008
`
`Sheet 6 of 6
`
`US 7,342,929 B2
`
`FIG. 5
`
`ASSIGN BUCKET TO EACH PACKET
`CLASS WITH VOLUME A FUNCTION
`
`MODEL BUCKET FILL RATE, MAX
`AND MIN CAPACITY FOR EACH CLASS
`
`REDUCE BUCKET PROPORTIONALLY
`TO PACKET THROUGHPUT OF CLASS
`
`OF HISTORY 4
`4
`1
`4
`
`DETERMINE DYNAMIC WEIGHT FOR
`EACH CLASS BUCKET VOLUME/HISTORY
`
`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
`• APPLY CONSTRAINTS ONLY AS NEEDED
`TO KEEP OVERALL THROUGHPUT<C
`
`Cloudflare - Exhibit 1030, page 8
`
`Cloudflare - Exhibit 1030, page 8
`
`
`
`US 7,342,929 B2
`
`1
`WEIGHTED FAIR QUEUING-BASED
`METHODS AND APPARATUS FOR
`PROTECTING AGAINST OVERLOAD
`CONDITIONS ON NODES OF A
`DISTRIBUTED NETWORK
`
`2
`operation thereof as can be used in existing networks, such
`as the Internet, as well as in other networks.
`Yet a still further object of the invention is to provide data
`networks, nodes, devices and methods of operation thereof
`5 as can be implemented at low cost and are 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.
`
`10
`
`BACKGROUND OF THE INVENTION
`
`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 other classes.
`The weight of at 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 weight of 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, (ii) 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 of a bucket for at least a class i for an epoch t2 during
`which one or more packets for that class are actually or
`theoretically pending for throughput as a function of a
`relation
`
`MO=
`
`max{ Bri°
`
`) —
`
`— )C
`
`WW1)
`Wi(ti)
`
`j active Ot
`
`+
`
`04}
`
`where
`L,(t2) is the volume of the bucket for class i during epoch
`t2;
`L,(t1) is the volume of the bucket for class i during epoch
`t1;
`B,min 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 throughput by the device:
`Cloudflare - Exhibit 1030, page 9
`
`25
`
`40
`
`45
`
`The invention pertains to distributed data networks and, 15
`more particularly, 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 20
`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 was possible, 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 30
`(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 35
`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, 50
`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 55
`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, 60
`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
`
`65
`
`Cloudflare - Exhibit 1030, page 9
`
`
`
`US 7,342,929 B2
`(cid:9)(cid:8)(cid:10) (cid:5)(cid:1)(cid:3)(cid:4)(cid:2)(cid:1)(cid:6)(cid:2)(cid:6)(cid:10) (cid:7)(cid:2)(cid:10)
`
`(cid:1)(cid:3)
`3
`(cid:39)(cid:5)(cid:1)(cid:76)(cid:1)(cid:1)(cid:3) (cid:58)(cid:75)(cid:88)(cid:41)(cid:88)(cid:83)(cid:45)(cid:58)(cid:56)(cid:57)(cid:76)(cid:88)(cid:41)(cid:75)(cid:75)(cid:58)(cid:56)(cid:65)(cid:45)(cid:44)(cid:88)(cid:76)(cid:67)(cid:88)(cid:43)(cid:62)(cid:41)(cid:75)(cid:75)(cid:88)(cid:58)(cid:88)(cid:44)(cid:78)(cid:71)(cid:58)(cid:65)(cid:56)(cid:88)(cid:45)(cid:69)(cid:67)(cid:43)(cid:57)(cid:88)(cid:76)(cid:1) (cid:2)(cid:3)
`W,(ti) is a weight assigned to class i during epoch t1 ;
`(cid:39)(cid:3)(cid:76)(cid:1)(cid:1)(cid:3) (cid:58)(cid:75)(cid:88)(cid:41)(cid:88)(cid:83)(cid:45)(cid:58)(cid:56)(cid:57)(cid:76)(cid:88)(cid:41)(cid:75)(cid:75)(cid:58)(cid:56)(cid:65)(cid:45)(cid:44)(cid:88)(cid:76)(cid:67)(cid:88)(cid:43)(cid:62)(cid:41)(cid:75)(cid:75)(cid:88)(cid:60)(cid:88) (cid:44)(cid:78)(cid:71)(cid:58)(cid:65)(cid:56)(cid:88)(cid:45)(cid:69)(cid:67)(cid:43)(cid:57)(cid:88)(cid:76)(cid:1) (cid:2)(cid:3)
`WW(t1) is a weight assigned to class j during epoch t1 ;
`(cid:71)(cid:5)(cid:58)(cid:75)(cid:88)(cid:41)(cid:88)(cid:50)(cid:59)(cid:62)(cid:62)(cid:58)(cid:65)(cid:56)(cid:88)(cid:71)(cid:41)(cid:76)(cid:45)(cid:88)(cid:67)(cid:47)(cid:88)(cid:76)(cid:57)(cid:45)(cid:88)(cid:42)(cid:78)(cid:43)(cid:61)(cid:45)(cid:76)(cid:88)(cid:49)(cid:68)(cid:71)(cid:88)(cid:43)(cid:62)(cid:41)(cid:75)(cid:75)(cid:88) (cid:58)(cid:8)
`;is a filling rate of the bucket for class i.
`(cid:35)(cid:45)(cid:62)(cid:41)(cid:76)(cid:45)(cid:44)(cid:88)(cid:41)(cid:75)(cid:69)(cid:45)(cid:43)(cid:76)(cid:75)(cid:88)(cid:67)(cid:47)(cid:88)(cid:76)(cid:57)(cid:45)(cid:88)(cid:58)(cid:65)(cid:81)(cid:45)(cid:65)(cid:76)(cid:58)(cid:67)(cid:65)(cid:88)(cid:69)(cid:71)(cid:67)(cid:81)(cid:58)(cid:44)(cid:45)(cid:88)(cid:49)(cid:68)(cid:71)(cid:88)(cid:44)(cid:45)(cid:76)(cid:45)(cid:73)(cid:58)(cid:65)(cid:58)(cid:65)(cid:56)
`Related aspects of the invention provide for determining
`(cid:41)(cid:88)(cid:81)(cid:67)(cid:62)(cid:78)(cid:64)(cid:45)(cid:88)(cid:67)(cid:47)(cid:88)(cid:41)(cid:88)(cid:42)(cid:78)(cid:43)(cid:61)(cid:45)(cid:76)(cid:88)(cid:49)(cid:68)(cid:71)(cid:88)(cid:41)(cid:76)(cid:88)(cid:62)(cid:45)(cid:41)(cid:75)(cid:76)(cid:88)(cid:41)(cid:88)(cid:43)(cid:62)(cid:41)(cid:75)(cid:75)(cid:88)(cid:58)(cid:88)(cid:49)(cid:68)(cid:71)(cid:88)(cid:41)(cid:65)(cid:88)(cid:45)(cid:69)(cid:67)(cid:43)(cid:57)(cid:88)(cid:76)(cid:1)(cid:2)
`a volume of a bucket for at least a class i for an epoch t2
`(cid:44)(cid:78)(cid:71)(cid:58)(cid:65)(cid:56)(cid:88) (cid:83)(cid:57)(cid:58)(cid:43)(cid:57)(cid:88) (cid:67)(cid:65)(cid:45)(cid:88) (cid:67)(cid:71)(cid:88) (cid:64)(cid:67)(cid:71)(cid:45)(cid:88) (cid:69)(cid:41)(cid:43)(cid:61)(cid:45)(cid:76)(cid:75)(cid:88) (cid:49)(cid:68)(cid:71)(cid:88) (cid:76)(cid:57)(cid:41)(cid:76)(cid:88) (cid:43)(cid:62)(cid:41)(cid:75)(cid:75)(cid:88) (cid:41)(cid:71)(cid:45)(cid:88) (cid:65)(cid:67)(cid:76)(cid:88)
`during which one or more packets for that class are not
`(cid:41)(cid:43)(cid:76)(cid:78)(cid:41)(cid:62)(cid:62)(cid:85)(cid:88)(cid:67)(cid:71)(cid:88)(cid:76)(cid:57)(cid:45)(cid:67)(cid:71)(cid:45)(cid:76)(cid:58)(cid:43)(cid:41)(cid:62)(cid:62)(cid:85)(cid:88)(cid:69)(cid:45)(cid:65)(cid:44)(cid:58)(cid:65)(cid:56)(cid:88)(cid:49)(cid:68)(cid:71)(cid:88)(cid:76)(cid:57)(cid:71)(cid:67)(cid:78)(cid:56)(cid:57)(cid:69)(cid:78)(cid:76)(cid:88)(cid:41)(cid:75)(cid:88)(cid:41)(cid:88)(cid:52)(cid:79)(cid:65)(cid:43)(cid:76)(cid:58)(cid:67)(cid:65)(cid:88)
`actually or theoretically pending for throughput as a function
`(cid:67)(cid:47)(cid:88)(cid:41)(cid:88)(cid:71)(cid:45)(cid:62)(cid:41)(cid:76)(cid:58)(cid:67)(cid:65)(cid:88)
`of a relation
`
`Li(t2)=max{Bi
`
`,min{B, Li(ti)+(t2-t
`
`}}
`
`(cid:2)(cid:3)
`4
`(cid:26)(cid:78)(cid:71)(cid:77)(cid:57)(cid:45)(cid:71)(cid:88)(cid:41)(cid:75)(cid:69)(cid:45)(cid:43)(cid:76)(cid:75)(cid:88)(cid:67)(cid:47)(cid:88)(cid:76)(cid:57)(cid:45)(cid:88)(cid:58)(cid:65)(cid:81)(cid:45)(cid:65)(cid:76)(cid:58)(cid:67)(cid:65)(cid:88)(cid:69)(cid:71)(cid:67)(cid:81)(cid:58)(cid:44)(cid:45)(cid:88)(cid:41)(cid:88)(cid:65)(cid:45)(cid:76)(cid:83)(cid:67)(cid:71)(cid:61)(cid:88)(cid:41)(cid:69)(cid:69)(cid:41)(cid:87)
`Further aspects of the invention provide a network appa-
`(cid:71)(cid:41)(cid:76)(cid:80)(cid:75)(cid:88)(cid:41)(cid:75)(cid:88)(cid:44)(cid:45)(cid:75)(cid:43)(cid:71)(cid:58)(cid:42)(cid:45)(cid:44)(cid:88)(cid:41)(cid:42)(cid:67)(cid:81)(cid:45)(cid:88)(cid:76)(cid:57)(cid:41)(cid:76)(cid:88)(cid:58)(cid:65)(cid:43)(cid:62)(cid:78)(cid:44)(cid:45)(cid:75)(cid:88)(cid:41)(cid:88)(cid:64)(cid:41)(cid:71)(cid:61)(cid:58)(cid:65)(cid:56)(cid:88)(cid:64)(cid:45)(cid:43)(cid:57)(cid:41)(cid:65)(cid:58)(cid:75)(cid:64)(cid:88)
`ratus as described above that includes a marking mechanism
`(cid:83)(cid:57)(cid:58)(cid:43)(cid:57)(cid:88)(cid:76)(cid:71)(cid:41)(cid:65)(cid:75)(cid:64)(cid:58)(cid:76)(cid:75)(cid:88)(cid:41)(cid:88)(cid:43)(cid:67)(cid:67)(cid:61)(cid:58)(cid:45)(cid:88)(cid:76)(cid:67)(cid:88)(cid:41)(cid:88)(cid:69)(cid:41)(cid:43)(cid:61)(cid:45)(cid:76)(cid:88)(cid:75)(cid:67)(cid:78)(cid:71)(cid:43)(cid:45)(cid:88)(cid:67)(cid:65)(cid:88)(cid:76)(cid:57)(cid:45)(cid:88)(cid:65)(cid:45)(cid:76)(cid:83)(cid:67)(cid:71)(cid:61)(cid:88)
`which transmits a cookie to a packet source on the network
`(cid:41)(cid:65)(cid:44)(cid:88) (cid:43)(cid:41)(cid:78)(cid:75)(cid:45)(cid:75)(cid:88) (cid:76)(cid:57)(cid:41)(cid:76)(cid:88) (cid:75)(cid:67)(cid:78)(cid:71)(cid:43)(cid:45)(cid:88) (cid:76)(cid:67)(cid:88) (cid:58)(cid:65)(cid:43)(cid:62)(cid:78)(cid:44)(cid:45)(cid:88) (cid:76)(cid:57)(cid:45)(cid:88) (cid:43)(cid:67)(cid:67)(cid:61)(cid:58)(cid:45)(cid:88) (cid:58)(cid:65)(cid:88) (cid:69)(cid:41)(cid:43)(cid:61)(cid:45)(cid:76)(cid:75)(cid:88)
`and causes that source to include the cookie in packets
`(cid:76)(cid:71)(cid:41)(cid:65)(cid:75)(cid:64)(cid:58)(cid:76)(cid:76)(cid:45)(cid:44)(cid:88)(cid:42)(cid:85)(cid:88)(cid:58)(cid:76)(cid:88)(cid:76)(cid:67)(cid:88)(cid:67)(cid:65)(cid:88)(cid:76)(cid:57)(cid:45)(cid:88)(cid:65)(cid:45)(cid:76)(cid:83)(cid:67)(cid:71)(cid:61)(cid:88)(cid:76)(cid:67)(cid:88)(cid:41)(cid:88)(cid:44)(cid:45)(cid:75)(cid:76)(cid:58)(cid:65)(cid:41)(cid:76)(cid:58)(cid:67)(cid:65)(cid:88)(cid:41)(cid:75)(cid:75)(cid:67)(cid:43)(cid:58)(cid:87)
`transmitted by it to on the network to a destination associ-
`(cid:41)(cid:76)(cid:45)(cid:44)(cid:88)(cid:83)(cid:58)(cid:76)(cid:57)(cid:88)(cid:76)(cid:57)(cid:45)(cid:88)(cid:41)(cid:69)(cid:69)(cid:41)(cid:71)(cid:41)(cid:76)(cid:80)(cid:75)(cid:8)(cid:88)(cid:37)(cid:57)(cid:45)(cid:88)(cid:64)(cid:41)(cid:71)(cid:61)(cid:58)(cid:65)(cid:56)(cid:88)(cid:64)(cid:45)(cid:43)(cid:57)(cid:41)(cid:65)(cid:58)(cid:75)(cid:64)(cid:88)(cid:43)(cid:41)(cid:65)(cid:6)(cid:88)(cid:64)(cid:67)(cid:71)(cid:45)(cid:7)
`ated with the apparatus. The marking mechanism can, more-
`(cid:67)(cid:81)(cid:45)(cid:71)(cid:6)(cid:88) (cid:75)(cid:76)(cid:71)(cid:58)(cid:69)(cid:88)(cid:76)(cid:57)(cid:45)(cid:88)(cid:43)(cid:67)(cid:67)(cid:61)(cid:58)(cid:45)(cid:88)(cid:49)(cid:72)(cid:67)(cid:64)(cid:88)(cid:41)(cid:65)(cid:85)(cid:88)(cid:69)(cid:41)(cid:43)(cid:61)(cid:45)(cid:76)(cid:75)(cid:88)(cid:76)(cid:71)(cid:41)(cid:65)(cid:75)(cid:64)(cid:58)(cid:76)(cid:77)(cid:45)(cid:44)(cid:88)(cid:42)(cid:85)(cid:88)(cid:76)(cid:57)(cid:45)(cid:88)
`over, strip the cookie from any packets transmitted by the
`(cid:75)(cid:67)(cid:78)(cid:71)(cid:43)(cid:45)(cid:88)(cid:76)(cid:67)(cid:88) (cid:76)(cid:57)(cid:45)(cid:88) (cid:44)(cid:45)(cid:75)(cid:76)(cid:58)(cid:65)(cid:41)(cid:76)(cid:58)(cid:67)(cid:65)(cid:8)(cid:88)(cid:29)(cid:76)(cid:88)(cid:43)(cid:41)(cid:65)(cid:88)(cid:41)(cid:62)(cid:75)(cid:67)(cid:88)(cid:44)(cid:45)(cid:76)(cid:45)(cid:71)(cid:64)(cid:58)(cid:65)(cid:45)(cid:88)(cid:76)(cid:57)(cid:45)(cid:88)(cid:75)(cid:78)(cid:75)(cid:69)(cid:58)(cid:87)
`source to the destination. It can also determine the suspi-
`(cid:43)(cid:58)(cid:67)(cid:78)(cid:75)(cid:65)(cid:45)(cid:75)(cid:75)(cid:88)(cid:67)(cid:47)(cid:88)(cid:41)(cid:88)(cid:69)(cid:41)(cid:43)(cid:61)(cid:45)(cid:76)(cid:88)(cid:42)(cid:41)(cid:75)(cid:45)(cid:44)(cid:88)(cid:67)(cid:65)(cid:88)(cid:41)(cid:88)(cid:43)(cid:67)(cid:67)(cid:61)(cid:58)(cid:45)(cid:6)(cid:88)(cid:58)(cid:47)(cid:88)(cid:41)(cid:65)(cid:85)(cid:6)(cid:88)(cid:76)(cid:57)(cid:45)(cid:71)(cid:45)(cid:58)(cid:65)(cid:8)(cid:88)(cid:20)(cid:75)(cid:88)
`ciousness of a packet based on a cookie, if any, therein. As
`(cid:2)(cid:1)(cid:8) (cid:41)(cid:42)(cid:67)(cid:81)(cid:45)(cid:6)(cid:88) (cid:76)(cid:57)(cid:41)(cid:76)(cid:88) (cid:75)(cid:78)(cid:75)(cid:69)(cid:58)(cid:43)(cid:58)(cid:67)(cid:78)(cid:75)(cid:65)(cid:45)(cid:75)(cid:75)(cid:88) (cid:43)(cid:41)(cid:65)(cid:88) (cid:42)(cid:45)(cid:88) (cid:78)(cid:75)(cid:45)(cid:44)(cid:88) (cid:42)(cid:85)(cid:88) (cid:41)(cid:88) (cid:43)(cid:62)(cid:41)(cid:75)(cid:75)(cid:58)(cid:50)(cid:59)(cid:45)(cid:71)(cid:88) (cid:58)(cid:65)(cid:88)
`is above, that suspiciousness can be used by a classifier in
`(cid:44)(cid:45)(cid:76)(cid:45)(cid:71)(cid:64)(cid:58)(cid:65)(cid:58)(cid:65)(cid:56)(cid:88)(cid:69)(cid:62)(cid:41)(cid:43)(cid:45)(cid:64)(cid:45)(cid:65)(cid:76)(cid:88)(cid:67)(cid:47)(cid:88)(cid:41)(cid:88)(cid:69)(cid:41)(cid:43)(cid:61)(cid:45)(cid:76)(cid:88)(cid:58)(cid:65)(cid:88)(cid:41)(cid:88)(cid:70)(cid:78)(cid:45)(cid:78)(cid:45)(cid:8)(cid:88)
`determining placement of a packet in a queue.
`(cid:83)(cid:57)(cid:45)(cid:71)(cid:45)(cid:88)
`where
`(cid:35)(cid:45)(cid:62)(cid:41)(cid:76)(cid:45)(cid:44)(cid:88)(cid:41)(cid:75)(cid:69)(cid:45)(cid:43)(cid:76)(cid:75)(cid:88)(cid:67)(cid:47)(cid:88)(cid:76)(cid:57)(cid:45)(cid:88)(cid:58)(cid:65)(cid:81)(cid:45)(cid:65)(cid:76)(cid:58)(cid:67)(cid:65)(cid:88)(cid:43)(cid:41)(cid:65)(cid:88)(cid:78)(cid:76)(cid:58)(cid:62)(cid:58)(cid:86)(cid:45)(cid:88)(cid:75)(cid:78)(cid:43)(cid:57)(cid:88)(cid:43)(cid:67)(cid:67)(cid:61)(cid:58)(cid:45)(cid:75)(cid:88)
`Related aspects of the invention can utilize such cookies
`(cid:30)(cid:5)(cid:1)(cid:76)(cid:1)
`(cid:1)(cid:2)(cid:58)(cid:75)(cid:88)(cid:76)(cid:57)(cid:45)(cid:88)(cid:81)(cid:67)(cid:62)(cid:78)(cid:64)(cid:45)(cid:88)(cid:67)(cid:47)(cid:88)(cid:76)(cid:57)(cid:45)(cid:88)(cid:42)(cid:78)(cid:43)(cid:61)(cid:45)(cid:76)(cid:88)(cid:49)(cid:68)(cid:71)(cid:88)(cid:43)(cid:62)(cid:41)(cid:75)(cid:75)(cid:88)(cid:58)(cid:88)(cid:44)(cid:78)(cid:71)(cid:58)(cid:65)(cid:56)(cid:88)(cid:45)(cid:69)(cid:67)(cid:43)(cid:57)(cid:88)
`L,(t2) is the volume of the bucket for class i during epoch
`(cid:76)(cid:67)(cid:88) (cid:44)(cid:58)(cid:75)(cid:43)(cid:45)(cid:74)(cid:88) (cid:58)(cid:65)(cid:44)(cid:58)(cid:81)(cid:58)(cid:44)(cid:78)(cid:41)(cid:62)(cid:88) (cid:78)(cid:75)(cid:45)(cid:71)(cid:88) (cid:75)(cid:45)(cid:75)(cid:75)(cid:58)(cid:67)(cid:65)(cid:88) (cid:49)(cid:72)(cid:67)(cid:64)(cid:88) (cid:41)(cid:64)(cid:67)(cid:65)(cid:56)(cid:88) (cid:75)(cid:76)(cid:71)(cid:45)(cid:41)(cid:64)(cid:88) (cid:67)(cid:47)(cid:88)
`to discern individual user session from among stream of
`(cid:76)(cid:2)(cid:19)(cid:88)
`t2;
`(cid:69)(cid:41)(cid:43)(cid:61)(cid:45)(cid:76)(cid:75)(cid:88) (cid:76)(cid:57)(cid:41)(cid:76)(cid:88) (cid:57)(cid:41)(cid:81)(cid:45)(cid:88) (cid:76)(cid:57)(cid:45)(cid:88) (cid:75)(cid:41)(cid:64)(cid:45)(cid:88) (cid:75)(cid:67)(cid:78)(cid:71)(cid:43)(cid:45)(cid:88) (cid:41)(cid:65)(cid:44)(cid:88) (cid:44)(cid:45)(cid:75)(cid:76)(cid:58)(cid:65)(cid:41)(cid:76)(cid:58)(cid:67)(cid:65)(cid:88) (cid:29)(cid:34)(cid:88)
`packets that have the same source and destination IP
`(cid:30)(cid:5)(cid:1)(cid:76)(cid:1) (cid:1)(cid:3) (cid:58)(cid:75)(cid:88)(cid:76)(cid:57)(cid:45)(cid:88)(cid:81)(cid:67)(cid:62)(cid:78)(cid:64)(cid:45)(cid:88)(cid:67)(cid:47)(cid:88)(cid:76)(cid:57)(cid:45)(cid:88)(cid:42)(cid:78)(cid:43)(cid:61)(cid:45)(cid:76)(cid:88)(cid:49)(cid:68)(cid:71)(cid:88)(cid:43)(cid:62)(cid:41)(cid:75)(cid:75)(cid:88)(cid:58)(cid:88)(cid:44)(cid:78)(cid:71)(cid:58)(cid:65)(cid:56)(cid:88)(cid:45)(cid:69)(cid:67)(cid:43)(cid:57)(cid:88) (cid:2)(cid:6)(cid:8)
`L,(ti) is the volume of the bucket for class i during epoch
`(cid:41)(cid:44)(cid:44)(cid:71)(cid:45)(cid:75)(cid:75)(cid:45)(cid:75)(cid:6)(cid:88)(cid:69)(cid:67)(cid:71)(cid:77)(cid:75)(cid:88)(cid:41)(cid:65)(cid:44)(cid:9)(cid:67)(cid:71)(cid:88)(cid:69)(cid:41)(cid:43)(cid:61)(cid:45)(cid:76)(cid:88)(cid:76)(cid:85)(cid:69)(cid:45)(cid:75)(cid:8)(cid:88)
`is addresses, ports and/or packet types.
`(cid:76)(cid:1)(cid:19)(cid:88)
`t1;
`(cid:36)(cid:76)(cid:58)(cid:62)(cid:62)(cid:88) (cid:48)(cid:78)(cid:71)(cid:76)(cid:57)(cid:45)(cid:71)(cid:88) (cid:41)(cid:75)(cid:69)(cid:45)(cid:43)(cid:76)(cid:75)(cid:88) (cid:67)(cid:47)(cid:88) (cid:76)(cid:57)(cid:45)(cid:88) (cid:58)(cid:65)(cid:81)(cid:45)(cid:65)(cid:76)(cid:58)(cid:67)(cid:65)(cid:88) (cid:69)(cid:71)(cid:67)(cid:81)(cid:58)(cid:44)(cid:45)(cid:88) (cid:64)(cid:45)(cid:76)(cid:57)(cid:67)(cid:44)(cid:75)(cid:88)
`Still further aspects of the invention provide methods
`(cid:3)(cid:2)(cid:4)(cid:1)(cid:5)(cid:6) (cid:58)(cid:75)(cid:88)(cid:41)(cid:88)(cid:64)(cid:58)(cid:65)(cid:58)(cid:64)(cid:78)(cid:64)(cid:88)(cid:43)(cid:41)(cid:69)(cid:41)(cid:43)(cid:58)(cid:76)(cid:85)(cid:88)(cid:49)(cid:68)(cid:71)(cid:88)(cid:76)(cid:57)(cid:45)(cid:88)(cid:42)(cid:78)(cid:43)(cid:61)(cid:45)(cid:76)(cid:88)(cid:49)(cid:68)(cid:71)(cid:88)(cid:43)(cid:62)(cid:41)(cid:75)(cid:75)(cid:88)(cid:58)(cid:19)(cid:88)
`B,""" is a minimum capacity for the bucket for class i;
`(cid:69)(cid:41)(cid:71)(cid:41)(cid:62)(cid:62)(cid:45)(cid:62)(cid:58)(cid:65)(cid:56)(cid:88)(cid:76)(cid:57)(cid:45)(cid:88)(cid:67)(cid:69)(cid:45)(cid:71)(cid:41)(cid:76)(cid:58)(cid:67)(cid:65)(cid:75)(cid:88)(cid:44)(cid:45)(cid:75)(cid:43)(cid:71)(cid:58)(cid:42)(cid:45)(cid:44)(cid:88)(cid:41)(cid:42)(cid:67)(cid:81)(cid:45)(cid:8)(cid:88)(cid:37)(cid:57)(cid:45)(cid:75)(cid:45)(cid:88)(cid:41)(cid:65)(cid:44)(cid:88)(cid:67)(cid:76)(cid:57)(cid:45)(cid:71)(cid:88)
`paralleling the operations described above. These and other
`(cid:22)(cid:5)(cid:88)(cid:58)(cid:75)(cid:88)(cid:41)(cid:88)(cid:64)(cid:41)(cid:84)(cid:58)(cid:64)(cid:78)(cid:64)(cid:88)(cid:43)(cid:41)(cid:69)(cid:41)(cid:43)(cid:58)(cid:76)(cid:85)(cid:88)(cid:49)(cid:68)(cid:71)(cid:88)(cid:76)(cid:57)(cid:45)(cid:88)(cid:42)(cid:78)(cid:43)(cid:61)(cid:45)(cid:76)(cid:88)(cid:49)(cid:68)(cid:71)(cid:88)(cid:43)(cid:62)(cid:41)(cid:75)(cid:75)(cid:88)(cid:58)(cid:19)(cid:88)
`B. is a maximum capacity for the bucket for class i;
`(cid:41)(cid:75)(cid:69)(cid:45)(cid:43)(cid:76)(cid:75)(cid:88)(cid:67)(cid:47)(cid:88)(cid:76)(cid:57)(cid:45)(cid:88)(cid:58)(cid:65)(cid:81)(cid:45)(cid:65)(cid:76)(cid:58)(cid:67)(cid:65)(cid:88)(cid:41)(cid:71)(cid:45)(cid:88)(cid:45)(cid:81)(cid:58)(cid:44)(cid:45)(cid:65)(cid:76)(cid:88)(cid:58)(cid:65)(cid:88)(cid:76)(cid:57)(cid:45)(cid:88)(cid:44)(cid:71)(cid:41)(cid:83)(cid:58)(cid:65)(cid:56)(cid:75)(cid:88)(cid:41)(cid:65)(cid:44)(cid:88)(cid:58)(cid:65)(cid:88)
`aspects of the invention are evident in the drawings and in
`(cid:71)(cid:5)(cid:88)(cid:58)(cid:75)(cid:88)(cid:41)(cid:88)(cid:50)(cid:59)(cid:62)(cid:62)(cid:58)(cid:65)(cid:56)(cid:88)(cid:71)(cid:41)(cid:76)(cid:45)(cid:88)(cid:67)(cid:47)(cid:88)(cid:76)(cid:57)(cid:45)(cid:88)(cid:42)(cid:78)(cid:43)(cid:61)(cid:45)(cid:76)(cid:88)(cid:49)(cid:68)(cid:71)(cid:88)(cid:43)(cid:62)(cid:41)(cid:75)(cid:75)(cid:88)(cid:58)(cid:8)(cid:88)
`r, is a filling rate of the bucket for class i.
`(cid:76)(cid:57)(cid:45)(cid:88)(cid:44)(cid:45)(cid:75)(cid:43)(cid:71)(cid:58)(cid:69)(cid:76)(cid:58)(cid:67)(cid:65)(cid:88)(cid:76)(cid:57)(cid:41)(cid:76)(cid:88)(cid:49)(cid:68)(cid:62)(cid:62)(cid:67)(cid:83)(cid:75)(cid:8)(cid:88)
`the description that follows.
`(cid:36)(cid:76)(cid:58)(cid:62)(cid:62)(cid:88)(cid:52)(cid:79)(cid:71)(cid:77)(cid:57)(cid:45)(cid:71)(cid:88)(cid:71)(cid:45)(cid:62)(cid:41)(cid:76)(cid:45)(cid:44)(cid:88)(cid:41)(cid:75)(cid:69)(cid:45)(cid:43)(cid:76)(cid:75)(cid:88)(cid:67)(cid:47)(cid:88)(cid:76)(cid:57)(cid:45)(cid:88)(cid:58)(cid:65)(cid:81)(cid:45)(cid:65)(cid:76)(cid:58)(cid:67)(cid:65)(cid:88)(cid:69)(cid:71)(cid:67)(cid:81)(cid:58)(cid:44)(cid:45)(cid:88)(cid:49)(cid:68)(cid:71)(cid:88) (cid:3)(cid:1)(cid:8)
`Still further related aspects of the invention provide for
`(cid:44)(cid:45)(cid:76)(cid:45)(cid:71)(cid:64)(cid:58)(cid:65)(cid:58)(cid:65)(cid:56)(cid:88) (cid:41)(cid:88)(cid:81)(cid:67)(cid:62)(cid:78)(cid:64)(cid:45)(cid:88)(cid:67)(cid:47)(cid:88)(cid:76)(cid:57)(cid:45)(cid:88)(cid:42)(cid:78)(cid:43)(cid:61)(cid:45)(cid:76)(cid:88)(cid:49)(cid:68)(cid:71)(cid:88)(cid:43)(cid:62)(cid:41)(cid:75)(cid:75)(cid:88) (cid:58)(cid:88) (cid:41)(cid:76)(cid:88) (cid:45)(cid:69)(cid:67)(cid:43)(cid:57)(cid:88)(cid:76)(cid:88)
`determining a volume of the bucket for class i at epoch t
`(cid:44)(cid:78)(cid:71)(