l||||||||||||||||||||||||||||||l|l||||||||l|||||l||||||||||||||||||||||||||
`
`U800i342929B2
`
`(12}
`
`United States Patent
`Bremler—Barr er a1.
`
`[IO] Patent No.:
`
`(45} Date of Patent:
`
`US 7,342,929 32
`Mar. 11, 2008
`
`(54)
`
`WEIGHTED FAIR QUEUINGw-BASED
`METHODS AND APPARATUS FOR
`PROTECTING AGAINST OVERLOAI)
`
`CONDITIONS 0N NODES OF A
`nisrRiBUi‘Ei) NIC‘IWORK
`
`(75)
`
`(73)
`
`Inventors: Anat Bremler—Barr. I-lolon (IL): Dan
`Touitou. Ramat-Gan (IL); Koren
`Illorvitz. HOd HZISilfll'Ol‘l (IL): Raphael
`lzadikario. Kefar Sava (IL); Yehuda
`Afek. llod-IIaShamn (1L)
`
`Assignee: 3:)” Technology. Inc., San Jose. CA
`
`V“)
`
`Notice:
`
`Subject to any disclaimer. the term of this
`patent i5 extended 0" adjusted “Edi-‘1' 35
`U.s.(:. 154(k)) by 1030 days.
`
`5.917.822 A * @1999 Iyles et at.
`5.956.340 A *
`951999 Afek et a1.
`6.041.059 A *
`3»"2000
`Jott‘c etal.
`
`
`
`five-"395.4
`370.:‘412
`BTU-412
`
`ed
`.
`C
`J
`( ““1““
`FOREIGN RATE-3N1" DOCUMENTS
`
`W0
`
`I
`_I
`_
`_
`4"2002
`W0 02’3““;
`OTHER PUBLICATIONS
`
`.l.C.R. et a]. “Hierarchical Packet Iiaii' Queueing Algo-
`Bennett.
`rithms”. IEEF. (Oct. 1997).
`{Continued}
`
`Primary Examiner Edan Orgad
`Assistant Examiner—Jung Park
`(74) Answer: Agent. or Firm David J. Powsner; Daniel J.
`Kligiur
`
`(21)
`
`(22)
`
`(65)
`
`(60}
`
`(51)
`
`(52)
`(58)
`
`(56)
`
`Appl. No: 101134.048
`
`(57)
`
`ABSTRACT
`
`“13d:
`
`AP“ 26., 2002
`.
`.
`.
`Prior Publication Data
`US 20(l3i'0076848 A1
`Apr. 24. 2003
`
`Related U.S. Application Data
`.
`.
`.
`.
`Prowstonal application NO‘ 6W286,943. filed on Apr.
`27‘ 2001‘
`Int. Cl.
`H041. 12/28
`3701395 4. WWI-112
`U S (‘l
`‘
`‘
`' " None
`l-‘i
`lid of (lassihcatlon Search.
`Se: application file for COIDpiClChtal‘ClIl'tlbttDI'y
`References Cited
`
`(2006.01)
`
`“-3- PAillliN—l‘ DOCUMHN'I‘S
`5.689.508 A
`ll-'l997 Lylcs
`5.905.730 A
`531999 Yang et a].
`
`3TU'39I
`370.429
`
`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
`wei hts clone or more other classes. The wei ht ol'at least
`the gselected class is dynamic and is a functiofi 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 lay [3008
`attacks. has a scheduler and a token bucket mechanism. e.g..
`as described above.ySueh apparatus can also include a
`plurality ol queues intonhich packets ot
`the respective
`classes are placed on receipt by the apparatus. I‘hose packets
`are dequeued by the scheduler. e.g.. in the manner described
`above. for transmittal to downstream devices (egg... potential
`victim nodes) on the network.
`
`37 Claims. 6 Drawing Sheets
`
`
`
`8%
`
`
`Authenticator —I mI-5:. E
`“599394“
`Identmer
`m
`
`on
`
`‘.
`Rates
`
`-IB— Irmter
`(63.. token
`leaky bucket)
`
`Rccngiailinn
`-
`
`Input from
`
`ml {Jamil}
`[
`Drop
`
`Filters:
`
`01
`
`
`]' Anti-Spoor —> Classify A 02
`
`‘
`I
`03
`Drop
`Permit
`
`Back to Client
`(Source)
`
`all!!!” .
`Victim
`N4
`Overall Rate
`Limiter
`
`Palo Alto Networks V. Sable Networks
`
`IPR2020-01712
`
`EX1030
`
`EX1030
`Palo Alto Networks v. Sable Networks
`IPR2020-01712
`
`

`

`US 7,342,929 B2
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`61'2000 Lee ............................ 3705412
`6.072.800 A
`1032000 Stiliadis et a].
`370-"232
`6.134.217 A
`
`“200] Win et al.
`7097229
`6,l82.l42 Bl “‘
`6.208.652 Bl
`372001 Stephens et al.
`3703395
`4:200] Ghani et a1.
`3701030
`6.215.769 Bl ‘V
`
`..
`332005 Appala et a1.
`370E235
`6.862.265 Bl "
`.
`3.52005 Talpade et a].
`370-412
`6.862.291 B2“3
`
`6.975.638 131" 122005 (Then etal.
`..
`3703412
`7.058.974 Bl ‘1'
`6."2006 Maher ct a].
`.. 726313
`
`200130012272 Al"
`89'2001 Aubert Ct 211.
`3703230
`7i’2002 Garcia~l..tlna~Aceves
`200230097726 Al '8
`370.-'395.3l
`et a].
`37033951
`8.52002 Yang
`872005 Patrick .................. 370539543
`
`2002:"01l4334 A17
`20050175014 Al"
`
`OTHER PUBLICATIONS
`
`Bennett. J.C.R. et a]. “High Speed. Scalable. and Accurage Imple-
`mentation of Fair Queueing Algorithms in ATM Networks“. lCNP
`(1997).
`Bennett. J LR. et a]. “WI“JQ: Worst-case Fair Weighted Fair
`Queueing". lat'ocom’QIS.
`Chiu ssi. FM. et a1. "Implementing 1“air Queueing in ATM Switches:
`The Discrete-Rate Approach”. lEEE‘ 1997.
`Chiussi. FM. et al. “Minimum-Delay Self-clocked Fair Queueing
`Algorithm for Packet-Switched Networks.".IEEE 1998.
`Delners. A. el al. “Analysis and Simulation of a Fair Queueing
`Algorithm." at: 1989 Association for Computing Machinery.
`Lickhardt. D.A. et a]. “Eflott-lunitcd Fair (ELF) Scheduling for
`Wireless Networks.” IEEE Infoeom 2000.
`Golestani. SJ. “Network Delay Analysis of a Class of Fair Queue-
`ing Algorithms." IEEE Journal on Selected Areas in C communica-
`tions. vol. 13 No. 6 (Aug. 1995) pp. 1057-1070.
`Golestani. SJ. "A Self-Clocked Fair Queueing Scheme for Broad-
`band Applications.” IEEE Q 1994 pp. 5c.1.1-Sc1.11.
`
`Greenberg. Albert G. et at. “How Fair is Fair Queuing?" Journal of
`the Association for Computing Machinery vol. 39 No. 3 (Jul. 1992)
`pp. 558-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. AK. el al. “A Generalized Processor Sharing Approach to
`Flow Control in Integrated Services Networks: The Multiple Node
`Case.” 1EEE.-’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.” IEEFJACM Transactions on Networking vol. ]. No. 3 (Jun.
`1993) pp. 344-357.
`“Quality of Service Networking.” downloaded from the web
`(address:
`http:.-'Iwww.cisco.comJunivercd-“cc.-"td-"doc-'cisintwlc"
`ito_docr'qos.htm) © (Tisco Systems. inc. 1999.
`Rexford.
`.11.. et a1. “Hardware-Elficient Fair Queueing Architec-
`tures for High-Speed Networks." IEEE D 1996 pp. 5d.2.1-5d.2.9.
`Shreedhar M. et a]. “Liflicient Fair Queuing Using Deficit Round-
`Robin.“ IEEEIACM Transactions on Networking vol. 4 No. 3 (Jun.
`1996) pp. 375-385.
`Sliliadis. D. et a]. "Frame-based Fair Queueing: A New Traflic
`Scheduling Algorithm for Packet-Switched Networks." (Jul. 18,
`[995) pp. 1-43.
`U.S. Appl. No. 09829377. filed Aug. 14. 2001. entitled: “Method
`and apparatus for protecting against overloaded conditions on nodes
`01' a distributed networ “.
`
`US. Appl. No. 607286.943. filed Apr. 27. 2001. entitled: "Weighted-
`fair queuing based apparatus for defending against distributed
`denial of service attacks".
`
`* cited by examiner
`
`

`

`US. Patent
`
`Mar. 11,2003
`
`Sheet 1 of6
`
`US 7,342,929 B2
`
`E
`
`E
`
`E
`
`m 1
`
`FIG.
`
`

`

`US. Patent
`
`e
`
`US 7,342,929 B2
`
`....\...km\‘ma.g0.Mafih§e§o¢m%
`
`\%%We§o¢m
`
`“x
`
`a
`
`000H—M—N.0:m,EU”EHIB...amEEE
`
`56maaa
`
`\megofifl
`
`
`
`

`

`US. Patent
`
`000m
`
`(Df03teehS
`
`US 7,342,929 BZ
`
`9Quinn,
`
`.
`
`
`Emo—H5&3swab6:625
`
`
`
`
`om:EW.LLH_m.Lowmozcmfisim_
`
`
`
`r.“BE:-35l.I655%..m._a$509.63wmMmA].
`
`8mmdune/O
`
`6:55
`
`+Illlllll
`
`@230
`
`
`
`E
`
`
`
`.ECQEE.H
`
`£35
`
`€36
`LII-ill
`
`#53E280¢59.:
`
`E259xowm
`
`30.50%
`
`Fig. 3A
`
`
`
`
`

`

`US. Patent
`
`Mar. 11, 2008
`
`Sheet 4 of 6
`
`US 7,342,929 B2
`
`5:03933:0
`
`«z
`
`mafia.@
`
`083:9532
`
`2mm=w5>c
`
`5:55
`
`:ESmnopD
`
`
`
`LOHWOSC@cuzdx
`
`muhsowrhmma
`
`6:252
`
`wagunqaaw Bu]
`- '11} —3I. OD
`
`E
`
`
`
`“83.53.H
`
`5.825
`
`:558x23
`
`30.50%
`
`8.6a€36
`All!!!
`
`#533Z£on:55
`
`Fig. 3B
`
`
`
`
`
`

`

`US. Patent
`
`Mar. 11, 2008
`
`Sheet 5 of6
`
`US 7,342,929 B2
`
`
`
`source
`
`
`
` ‘ Before Queue Decomposition: I Singie user
`
`A proxy with
`
`A proxy with no
`malicous source
`
`malicous sources
`
`“=1
`
`W=3
`
`W=4
`
`I”=1
`
`W=l
`
`=1
`
`After Queue Decomposition:
`
`Innocent sources
`
`
`
`malicous sources
`
`
`
` Single user
`
`source
`
`=1
`
`w=1,1,1,
`
`W=1,1,1,
`
`w=1
`
`W=1
`
`=1
`
`Fig. 4
`
`

`

`US. Patent
`
`Mar. 11, 2008
`
`Sheet 6 of6
`
`US 7,342,929 B2
`
`FIG. 5
`
`ASSIGN BUCKET TO EACH PACKET
`CLASS WITH VOLUME A FUNCTION
`
`OF HISTORY
`
`MODEL BUCKET FILL RATE. MAX
`AND MIN CAPACITY FOR EACH CLASS
`
`REDUCE BUCKET PROPORTIONALLY
`
`TO PACKET THROUGHPUT OF CLASS
`
`DETERMINE DYNAMIC WEIGHT FOR
`EACH CLASS BUCKET VOLUME/HISTORY
`
`SCHEDULE PACKETS FOR THROUGHPUT
`BASED ON DYNAMIC WEIGHTS,
`BUCKET VOLUME/CONTENT:
`
`TO KEEP OVERALL TI-[ROUGHPUT<C
`
`° ALLOW BURSTS AS LONG AS AVG
`
`CLASS RATEKPEAK
`
`- DISCRIMINATE STREAMS>AVG FOR
`
`LONG PERIODS
`- APPLY CONSTRAINTS ONLY AS NEEDED
`
`

`

`US 1342929 B2
`
`1
`WEIGHTED FAIR QUEUING-BASED
`METHODS AND APPARATUS FOR
`PROTECTING AGAINST OVERLOAD
`CONDITIONS ON NODES OF A
`DISTRIBUTED NETWORK
`
`This application claims the benefit of US. Provisional
`Patent Application Ser. No. 60t286.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 INVI'EN'I‘ION
`
`The invention pertains to distributed data networks and,
`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
`crowds.
`
`systems were typically stand—alone
`Early computer
`devices that processed only commands zmd data entered via
`dedicated local keyboards. tape drives. disk drives. card
`readers. or the like. Remote access was possible, but only via
`phone lilies 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 conununications 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-callcd 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 cybervandalisni
`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 litany 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, m1 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
`
`3o
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`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
`as can be implemented at low cost and are scalable.
`
`SUMMARY OI“ Till-i 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 ofthat class and weights of one 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.
`
`Related aspects of the invention provide a network device
`as described above in which the scheduler is substantially a
`weighted fair quelling (Wl’Q) 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 ofthe
`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 mecht —
`
`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 12 during
`which one or more packets for that class are actually or
`theoretically pending for throughput as a function of a
`relation
`
`£1113} =
`
`max{Bf-’“°. min{B,-. [1-111 I—ll'g — r; )C
`
`E
`jean-1 at :1
`
`where
`
`Lrttzj is the volume of the bucket for class i during epoch
`1'1:
`
`l.,-(t.} is the volume of the bucket for class i during epoch
`t,:
`Bf’i" is a minimum capacity for the bucket for class i:
`BI is a maximum capacity for the bucket for class i;
`C is a [treasure of overall tratlic throughput by the device;
`
`

`

`US 7,342,929 BZ
`(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)
`Wi(t1) 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)
`VVj(tl) 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)
`riis 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
`of a relation
`(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)
`Li(l2):maX{Bimin>min{Bix Li(ll)+(l2_ll)ri }}
`
`(cid:6)(cid:8)
`
`(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
`1.
`(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)
`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: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: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: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: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)
`addresses, ports and/or packet types.
`(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: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: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: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.
`BRIEF DESCRIPTION OF THE DRAWINGS
`(cid:22)(cid:35)(cid:29)(cid:25)(cid:26)(cid:88)(cid:24)(cid:25)(cid:36)(cid:23)(cid:35)(cid:29)(cid:34)(cid:37)(cid:29)(cid:33)(cid:32)(cid:88)(cid:33)(cid:26)(cid:88)(cid:37)(cid:28)(cid:25)(cid:88)(cid:24)(cid:35) (cid:20)(cid:39)(cid:29)(cid:32)(cid:27)(cid:36)(cid:88)
`
`25
`(cid:3)(cid:6)(cid:8)
`
`where
`(cid:83)(cid:57)(cid:45)(cid:71)(cid:45)(cid:88)
`(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:2)(cid:19)(cid:88)
`t2;
`(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)
`15
`L,(t1) is the volume of the bucket for class i during epoch
`(cid:76)(cid:1)(cid:19)(cid:88)
`t1;
`(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)
`Bi'm" is a minimum capacity for the bucket for class i;
`(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: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.
`2.
`(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 finther 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)(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:41)(cid:71)(cid:45)(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)
`during which one or more packets are throughput as a
`function of the relation
`(cid:48)(cid:78)(cid:65)(cid:43)(cid:76)(cid:58)(cid:67)(cid:65)(cid:88)(cid:67)(cid:47)(cid:88)(cid:76)(cid:57)(cid:45)(cid:88)(cid:71)(cid:45)(cid:62)(cid:41)(cid:76)(cid:58)(cid:67)(cid:65)(cid:88)
`Li(l):max{Bi’"i",min{Bl-, Li(l)—D}
`where
`(cid:83)(cid:57)(cid:45)(cid:71)(cid:45)(cid:88)