`
`111111111111111111111111111111111111121111°11,11111I1,1i1),1,111111111111111111111111111111111
`
`(19) United States
`(12) Patent Application Publication (10) Pub. No.: US 2002/0186661 Al
`Dec. 12, 2002
`Santiago et al.
`(43) Pub. Date:
`
`(54)
`
`(75)
`
`SYSTEM AND METHOD FOR
`HIERARCHICAL POLICING OF FLOWS
`AND SUBFLOWS OF A DATA STREAM
`
`Inventors: Rodolfo A. Santiago, St. Louis Park,
`MN (US); Scott A. Sarkinen, Mounds
`View, MN (US)
`
`Correspondence Address:
`ALTERA LAW GROUP, LLC
`6500 CITY WEST PARKWAY
`SUITE 100
`MINNEAPOLIS, MN 55344-7704 (US)
`
`(73) Assignee: Terago Communications, Inc., Maple
`Grove, MN (US)
`
`(21) Appl. No.:
`
`09/849,810
`
`(22) Filed:
`
`May 4, 2001
`
`Publication Classification
`
`Int. CI.7
`(51)
`(52) U.S. CI.
`
`HO4J 1/16
`370/252; 370/386
`
`(57)
`
`ABSTRACT
`
`A system and method for policing individual flows and
`subflows of a data stream. Data traffic streams are classified
`into separate traffic flows, which in turn can be further
`classified into subflows, thereby providing for different
`priority levels of subsets of the flow. The subflows may be
`still further classified into additional subflows, creating a
`hierarchical, layered prioritization that can be metered at
`each vertical and horizontal level of the hierarchy. A packet
`flow rate of each of the subflows is compared to a predefined
`rate limit to allow subflows of a flow to have different
`priorities therebetween.
`
`10
`
`/
`
`140
`
`122
`
`011
`
`110
`
`DESTINATION
`
`102
`
`100
`
`SOURCE
`
`104
`
`112
`
`126
`
`I 11 102
`
`124
`
`120
`
`114
`
`118
`
`116
`
`128
`
`Cloudflare - Exhibit 1024, page 1
`
`Cloudflare - Exhibit 1024, page 1
`
`

`

`Patent Application Publication Dec. 12, 2002 Sheet 1 of 15
`
`US 2002/0186661 Al
`
`NV,
`
`0 0o y
`
`H
`
`z
`
`C I
`
`O
`
`CC
`
`O
`C
`
`0
`
`O
`
`Cloudflare - Exhibit 1024, page 2
`
`Cloudflare - Exhibit 1024, page 2
`
`_1-
`

`

`IV 1999810/ZOOZ Sfl
`
`dig. 2
`
`202
`
`/
`
`SWITCH
`FABRIC
`
`200
`
`•
`•
`•
`
`206
`
`208
`
`LINE CARD-n
`
`LINE CARD-1
`
`204
`
`LINE CARD-0
`
`232
`
`MEMORY
`
`I
`
`INGRESS
`PROCESSING
`
`A
`
` 214
`
`230
`
`220
`
`/
`
`FIC
`
`PROCESSOR
`
`224
`
`/
`
`EGRESS
`PROCESSING
`
`222
`
`/
`
`FIC
`
`234
`
`MEMORY
`
`210
`
`\
`
`212
`
`216
`,./
`
`OC-192
` .;
`
`0C- 92
`228 /
`
`INGRESS
`
`EGRESS
`
`226
`
`Cloudflare - Exhibit 1024, page 3
`
`Cloudflare - Exhibit 1024, page 3
`
`

`

`Patent Application Publication Dec. 12, 2002 Sheet 3 of 15
`
`US 2002/0186661 Al
`
`300
`
`
`
`302
`
`OC 192 Framer
`OIF Rx_Data (64) 200Mhz
`
`306
`
`OIF Core
`
`Stats
`Memory
`
`Receive Elasticity FIFO
`
`I---
`
`Pre-Processor
`
`315
`
`Address
`(19)125Mhz
`
`Instructions
`Data
`
`312
`
`Programmable
`Parsing Engine
`
`Policing
`RAM
`
`Data
`(72)125Mhz
`
`SRAM
`IF
`
`Policing Engine
`
`308
`
`310
`
`CAM/
`IF
`
`SRAM
`IF
`
`313
`
`SRAM
`IF
`
`304
`
`330
`
`(72) 100Mhz
`
`(32) 100Mhz
`
`CAM
`
`(20) Addr
`125Mhz
`
`(36) Data
`125Mhz
`
`
`
`V ?
`
`(201 125Mhz
`
`(72) 125Mhz
`
`TLB
`SRAM
`
`332
`
`Editor
`SRAM
`
`318
`
`322
`
`340
`
`Co-
`Processor/
`Buffer
`
`CPU
`I/F
`
`(201125Mhz
`
`(72)125Mhz
`
`Data
`(32) 66Mhz
`
`<
`
`>
`
`Address
`(I6) 66Mhz
`
`314 H
`
`341
`
`SRAM
`IF
`
`High Speed Editor
`
`I ABI FD1 1 TRAFFIC
`
`Traffic Director
`
`Config
`Reg /
`IF
`
`Test
`Gen.
`
`
`
`CPU
`TX
`Buffer
`
`Output Buffer
`
`
`Traffic Director
`
`
`
`320
`
`JTAG
`
`342
`
`344
`
`OIF Core
`
`OIF Output_Data (64) 200Mhz
`Switch Fabric Interface
`
`316
`
`Mg. 3
`
`Cloudflare - Exhibit 1024, page 4
`
`Cloudflare - Exhibit 1024, page 4
`
`

`

`Patent Application Publication Dec. 12, 2(K)2 Sheet 4 of 15
`
`US 2002/0186661 Al
`
`412
`
`410
`
`414
`
`416
`
`CAM
`
`SRAM
`
`SRAM
`
`SRAM
`
`400
`
`7
`
`OIF SPI4
`
`CLASSIFIER
`402
`
`POLICER
`404
`
`EDITOR
`406
`
`OIF SPI4 >
`
`COPROCESSOR/CPU INTERFACE
`
`408
`
`Mg. 4
`
`422
`
`SRAM
`
`420
`
`CPU
`
`412
`
`410
`
`CAM
`
`SRAM
`
`OIF SPI4
`
`CLASSIFIER
`402
`
`COPROCESSOR
`
`wig. 5
`
`414
`
`416
`
`SRAM
`
`SRAM
`POLICER 404
`CPU INTERFACE
`
`EDITOR
`
`OIF SPI4 >
`
`406
`
`420
`
`CPU
`
`Cloudflare - Exhibit 1024, page 5
`
`Cloudflare - Exhibit 1024, page 5
`
`

`

`Patent Application Publication
`
`SI Jo S laal-S
`
`IV 1999810/ZOOZ Sfl
`
`706
`,*'--
`SUBFLOW-A
`.e. 708
`
`SUBFLOW-B
`710
`.4--
`SUBFLOW-C
`
`A, ...,.... 600
`
`606
`
`604
`TCP
`
`----Ii- PORI#
`
`602
`612
`
`ETH
`
`608
`
`610
`
`IPv4
`
`SA
`DA
`
`Mg. 6
`
`702
`
`FLOW-A
`
`700
`
`SA
`
`SA
`
`SA
`
`SA
`
`SA SA SA
`
`SA SA
`
`DATA STREAM
`
`-1
`P-1 P-2 P-1
`
`P-2
`
`P-1
`
`P-1
`
`P-1
`
`FLOW-B
`
``..' s"--- 704
`
`Jig. 7
`
`Cloudflare - Exhibit 1024, page €
`
`Cloudflare - Exhibit 1024, page 6
`
`

`

`Patent Application Publication
`
`S f Jo 9 riags
`
`IV 1999810/ZOOZ Sfl
`
` (800
`
`FLOW-1
`
`FLOW-2
`
` x802
`
`•
`•
`•
`
`FLOW-n
`
` r 804
`
`814
`
`806
`
`808
`
`SUBFLOW-A
`
`SUBFLOW-B
`
`SUBFLOW-A
`RATE LIMIT
`
`7 810
`
`DISCARD
`
`812
`
`FORWARD
`
` )
`
`816
`
`SUBFLOW-B
`RATE LIMIT
`
`Sig. 8
`
`Cloudflare - Exhibit 1024, page 7
`
`Cloudflare - Exhibit 1024, page 7
`
`

`

`Patent Application Publication
`
`IV 1999810/ZOOZ Sfl
`
`901
`
`906
`
`MELEIOODELIEEJ
`
`•
`•
`•
`
`FLOW / SUBFLOW
`CLASSIFIER
`
`904
`
`•
`•
`•
`
`•
`•
`•
`
`900
`
`920
`
`922
`
`924
`
`POLICING
`ENGINE
`
`EDITOR
`
`SHAPER/
`DROPPER
`
`908
`
`•
`•
`•
`
`A A A A
`
`B B B B
`
`C C C C
`
`910
`
`912
`
`902
`
`ACAB B Al C B
`
`914
`
`Mg. 9
`
`Cloudflare - Exhibit 1024, page 8
`
`Cloudflare - Exhibit 1024, page 8
`
`

`

`Patent Application Publication
`
`SI Jo g pails
`
`IV I9998I0/ZOOZ Sfl
`
`1010
`
`1014
`
`1018
`
`CLOCK
`
`MEMORY
`
`1012
`
`1016
`
`COMPARE
`
`PROCESSOR
`(METER)
`
`1020
`
`/
`
`EDITOR
`
`
`
`FLOW/
`SUBFLOW
`ID
`
`1004
`
`FRAME
`HEADER
`
` J
`
`1002
`
`SIZE;
`DS FIELDS
`
`FRAME
`HEADER
`
`1004
`
`•
`
`1002 ,-'
`
`7 1000
`
`MULTIPLEXED FLOWS
`
`Mg. 10
`
`1006
`
`SUBFLOW
`A
`
`FRAME
`HEADER
`
`1006
`
`B s,
`
`A
`
`- 1008
`
`SUBFLOW
`B
`
`FRAME
`HEADER
`
`Cloudflare - Exhibit 1024, page 9
`
`Cloudflare - Exhibit 1024, page 9
`
`

`

`Patent Application Publication
`
`Ike. 12, 2002 Sheet 9 of 15
`
`US 2002/0186661 Al
`
`1100
`
`CLASSIFY INTO FLOWS /
`SUBFLOWS
`
`METER
`FLOW(S)
`
`1102
`
`1104
`
`NO
`
`FLOW
`BANDWIDTH EXCEED
`THRESHOLD?
`
`YES
`
`METER SUBFLOWS
`(AND OPTIONALLY FURTHER
`SUBFLOWS OF SUBFLOWS)
`
`1106
`
`Mg 11
`
`Cloudflare - Exhibit 1024, page 10
`
`Cloudflare - Exhibit 1024, page 10
`
`

`

`Patent Application Publication Dec. 12, 2002 Sheet 10 of 15
`
`US 2002/0186661 Al
`
`CLASSIFY THE NEXT PACKET IN DATA STREAM
`INTO FLOW/SUBFLOW
`
`1200
`
`METER FLOW
`
`1202
`
`1204
`
`FLOW RATE LIMIT
`EXCEEDED?
`
`YES
`
`DISCARD
`PACKET
`
`1206
`
`NO
`
`1208
`
`NO
`
`SUBFLOW
`POLICING THRESHOLD
`RATE EXDEEDED?
`
`YES
`
`
`METER SUBFLOW
`
` 1210
`
`1212
`
`NO
`
`SUBFLOW RATE
`LIMIT EXCEEDED?
`
`YES
`
`Mg. 12
`
`Cloudflare - Exhibit 1024, page 11
`
`Cloudflare - Exhibit 1024, page 11
`
`

`

`Patent Application Publication Dec. 12, 2002 Sheet 11 of 15
`
`US 2002/0186661 Al
`
`1300
`
`1302
`
`/
`
`at time 0
`
`For all flows:
`SET CBT = CBS;
`SET SCBT = SCBS
`
`1304
`
` v 1306
`
`1
`
`1308
`
`C Upon arrival of a
`packet
`
`determine the packet's
`associated flow and
`subflow
`
`retrieve CIR, CBS, CBL, PIR,
`PBS, PBL, SCBS, CBT,
`PBT, SCBT and SPBT;
`
`Earn credits for time idle
`SET CBT = min (CBS, time idle * CIR);
`SET SCBT = min (SCBS, time idle * CIR);
`
`1312
`
`NO
`
`CBT > no. of bytes in
`the packet
`
`YES
`
`1316
`
`NO
`
`CBT > CBL,
`OR
`SCBT > no. of bytes
`in the packet?
`
`YES
`
`Charge CBT and SCBT for packet's use of
`bandwidth:
`SET CBT = CBT - bytes in packet;
`SET SCBT —
`max (0, SCBT - no. of bytes in packet)
`
`1310
`
`1318
`
`( packet is
`
`non-conforming
`
`1314
`
`1
`packet is
`conforming
`
`C.
`
`
`
`1320
`
`Mg. 13
`
`Cloudflare - Exhibit 1024, page 12
`
`Cloudflare - Exhibit 1024, page 12
`
`

`

`Patent Application Publication Dec. 12, 2002 Sheet 12 of 15
`
`US 2002/0186661 Al
`
`Cloudflare - Exhibit 1024, page 13
`
`Cloudflare - Exhibit 1024, page 13
`
`

`

`Patent Application Publication
`
`Si Jo £i lams
`
`IV 19998I0/ZOOZ Sf1
`
`1406
`
`1410
`
`1404
`
`( on packet arrival
`
`determine the packet's associated flow and subflow
`
`retrieve:
`CIR, CBS, CBL, PIR, PBS, PBL,
`SCBS, SPBS, CBT, PBT, SCBT, and
`SPBT;
`
` r 1408
`
`1400
`
` L1402
`
`1412
`
`earn credits for time idle
`SET CBT = min(CBS,time idle*CIR);
`SET SCBT = min(SCBS, time idle * CIR);
`SET PBT = min(PBS, time idle *PIR);
`SET SPBT = min(SPBS, time idle * PIR);
`
`NO
`
`PBT < no. of bytes in
`packet
`
`YES
`
`1414
`
`( mark the packet
`red
`
`Mg. 14a
`
`C
`
`time 0
`
`SET CBT = CBS;
`SET PBT = PBS;
`SET SCBT = SCBS;
`SET SPBT = SPBS;
`
`Cloudflare - Exhibit 1024, page 14
`
`Cloudflare - Exhibit 1024, page 14
`
`

`

`1416
`
`YES
`
`CBT < no. of bytes in
`packet
`
`NO
`
`1426
`
`NO
`
`CBT <= CBL
`AND
`SCBT < bytes in
`packet
`
`YES
`
`1418
`
`YES
`
`PBT <= PBL
`AND
`SPBT < bytes in
`packet
`
`NO
`
`1422
`
`IV 1999810/ZOOZ SI
`
`SET CBT = CBT - bytes in packet;
`SET SCBT = max(0, SCBT - no. of bytes in packet)
`
`SET PBT = PBT - bytes in packet;
`SET SPBT = max(0, SPBT - no. of bytes in packet)
`
`1428
`
`143
`
`1432
`
`mark the packet
`green
`
`SET PBT = PBT - bytes in packet;
`SET SPBT = max(0, SPBT - bytes in packet)
`
`C mark the packet
`
`red
`
`1420
`
`1424
`
`mark the packet
`yellow
`
`Mg. 14b
`
`Cloudflare - Exhibit 1024, page 15
`
`Cloudflare - Exhibit 1024, page 15
`
`

`

`Patent Application Publication Dec. 12, 2002 Sheet 15 of 15
`
`US 2002/0186661 Al
`
`1500
`
`1502
`
`1506
`
`1508
`
`1510
`
`CLASSIFY PACKET IN DATA STREAM
`INTO FLOW/SUBFLOW
`
`ENABLE SUBFLOW POLICING UPON FLOW
`REACHING PREDETERMINED THRESHOLD
`BANDWIDTH
`
`1504
`
`POLICE
`SUBFLOWS
`
`GUARANTEE BANDWIDTH TO HIGH-PRIORITY
`SUBFLOW REGARDLESS OF WHETHER THE
`FLOW STAYS IN CONFORMANCE
`
`BEGIN TO MARK PACKETS OF OTHER SUB-
`FLOWS AS NON-CONFORMING IF FLOW
`BECOMES NON-CONFORMING
`
`V
`
`ADJUST BANDWIDTH OF OTHER SUBFLOWS
`TO BRING FLOW INTO CONFORMANCE
`
`Mg. 15
`
`Cloudflare - Exhibit 1024, page 16
`
`Cloudflare - Exhibit 1024, page 16
`
`

`

`US 2002/0186661 Al
`
`Dec. 12, 2002
`
`1
`
`SYSTEM AND METHOD FOR HIERARCHICAL
`POLICING OF FLOWS AND SUBFLOWS OF A
`DATA STREAM
`
`CROSS-REFERENCE TO OTHER PATENT
`APPLICATIONS
`
`[0001] The following co-pending patent applications of
`common assignee contains some common disclosure:
`
`[0002] "System And Method For Providing Transfor-
`mation Of Multi-Protocol Packets In A Data
`Stream," Attorney Docket No. 1305.1-US-01, filed
`concurrently herewith, which is incorporated herein
`by reference in its entirety;
`
`[0003] "A Method And Apparatus For Providing
`Multi-Protocol, Multi-Stage, Real-lime Frame Clas-
`sification", Attorney Docket No. 1305.4-US-01, filed
`concurrently herewith, which is incorporated herein
`by reference in its entirety;
`
`[0004] "System And Method For Policing Multiple
`Data Flows And Multi-Protocol Data Flows," Attor-
`ney Docket No. 1305.6-US-01, filed concurrently
`herewith, which is incorporated herein by reference
`in its entirety.
`
`FIELD OF THE INVENTION
`
`[0005] This invention relates in general to communication
`networks, and more particularly to a method and apparatus
`for providing policing of individual flows and subflows of a
`data stream.
`
`BACKGROUND OF THE INVENTION
`
`[0006] Enhancing today's networking technology is a per-
`petual goal in the communications industry. As the raw
`speeds of large-scale and personal computing devices soar,
`the tremendous increase in data transmission demands con-
`tinue to push the networking bandwidth envelope to capac-
`ity. As bandwidth-intensive multimedia content continues to
`gain popularity and course the veins of the Internet, the
`unrelenting bandwidth dilemma is no less urgent today than
`yesterday.
`[0007]
`In order to make the most efficient use of the
`communication paths and routing equipment possible, polic-
`ing methods were devised. Users of various levels could
`obtain different qualities of service (QoS), which would then
`require "policing" to ensure conformance with the con-
`tracted QoS. Policing generally refers to the packet-by-
`packet monitoring function at a network border, such as an
`ingress point at a network node. This monitoring function
`ensures that the promised QoS is not violated. The amount
`of traffic flowing into or out of a particular interface may
`therefore require limiting actions to achieve a specific policy
`goal.
`
`[0008] Currently, varying data protocols require different
`methods for policing traffic flows. For example, the ATM
`Forum's FAST (Frame Based ATM over Sonet/SDH Trans-
`port) data link protocol and the Internet Engineering Task
`Force (IETF)'s IP data link protocol require different meth-
`ods for policing traffic flows. FAST, being based on ATM
`cells, recommends the use of a variant of the GCRA,
`referred to as the Frame Based GCRA (F-GCRA). F-GCRA
`
`is the policing method provided in the ATM Forum's speci-
`fication of FAST, and the Internet Engineering Task Force
`(IETF)'s IP packet policing generally involves the use of
`either Single Rate Three Color Marker (srTCM) or Two Rate
`Three Color Marker (trTCM) techniques.
`[0009] At a particular network node or other ingress point,
`individual packets that make up a communications traffic
`stream can be classified into several flows or connections.
`Different qualities of service (QoS) can be committed per
`flow by metering packets arriving at a given interface on a
`flow-by-flow basis. Flows whose effective bit rate exceeds
`what is committed in the service contract will be classified
`as non-conforming, and packets arriving at a time when its
`corresponding flow is non-conforming will be marked as
`non-conforming. Whether packets are marked as non-con-
`forming affects the likelihood of the packets being dis-
`carded. This metering of packets, i.e., policing, for the
`purpose of providing differentiated service per flow helps to
`regulate the bandwidth.
`[0010] When within bandwidth constraints, policing by
`flow results in a common drop probability for all packets
`associated with that same flow. There are, however, circum-
`stances where packets associated with certain types of
`messages within a flow should be afforded a higher prob-
`ability of completing their routes. For example, in a resi-
`dential broadband Internet connection, multiple services,
`such as video on demand, may be provided on the same
`connection. In such a case, it may be desirable to provide
`video packets a higher priority than the HTML packets, but
`within the bandwidth constraints committed to the house-
`hold by the service provider.
`
`[0011] Accordingly, there is a need in the communications
`industry for a method and apparatus for providing a layered
`approach to policing. A further need exists to provide
`policing of individual flows, as well as subflows of a data
`stream. The present invention fulfills these and other needs,
`and offers other advantages over the prior art policing
`approaches.
`
`SUMMARY OF THE INVENTION
`
`[0012] To overcome limitations in the prior art described
`above, and to overcome other limitations that will become
`apparent upon reading and understanding the present speci-
`fication, the present invention discloses a system, apparatus
`and method for policing of individual flows and subflows of
`a data stream. The present invention allows prioritizing and
`policing of communications packets using multiple levels of
`classification and metering, by classifying traffic streams
`into separate traffic flows, and further classifying these flows
`into "subflows" providing for different priority levels of
`subsets of the flow. The subflows may be still further
`classified into additional subflows, creating a hierarchical,
`layered prioritization that can be metered at each vertical
`and horizontal level of the hierarchy. Thus, during periods of
`high transfer rates from a flow, the allocation of remaining
`bandwidth for that particular flow may be biased towards
`packets associated with subflows of higher priority.
`[0013]
`In accordance with one embodiment of the inven-
`tion, a method is provided for policing communications
`packets. The method includes classifying the data stream
`into at least one traffic flow, and classifying at least one of
`the traffic flows into a plurality of first level subflows. The
`
`Cloudflare - Exhibit 1024, page 17
`
`Cloudflare - Exhibit 1024, page 17
`
`

`

`US 2002/0186661 Al
`
`Dec. 12, 2002
`
`2
`
`method includes measuring a rate of each of the first level
`subflows associated with the traffic flow, when the traffic
`flow reaches a predetermined bandwidth threshold. The
`packets associated with each of the first level subflows are
`marked with one of a plurality of conformance indicators
`based on the measured rate of the respective first level
`subflow. In a more particular embodiment, a rate limit may
`be associated with each of the first level subflows, which can
`then be compared to the packet rate of the respective first
`level subflow in order to determine whether or not that
`subflow is conforming, non-conforming, or some stage of
`conformance therebetween. Addition subflow levels may be
`derived from the existing subflow levels, such as classifying
`a first level subflow into a plurality of second level subflows,
`classifying one or more of the second level subflows into a
`plurality of third level subflows, and so forth. A computer-
`readable medium having computer-executable instructions
`for performing such policing functions is also provided.
`[0014]
`In accordance with another embodiment of the
`invention, a method is provided for facilitating layered
`policing of packets of a data stream. The method includes
`parsing the data stream into a plurality of flows. For any of
`the flows, at least one characteristic common to a first subset
`of the flow is identified. A first drop probability is associated
`with each of the packets of the first subset having the
`common characteristic, and a second drop probability is
`associated with at least one other subset of the flow. In this
`manner, different drop probabilities for different subsets of
`the flow is provided.
`[0015]
`In accordance with another embodiment of the
`invention, a packet policing system for providing layered
`policing of packets of a data stream is provided. A classifier
`receives and parses the data stream into a plurality of traffic
`flows, and parses at least one of the traffic flows into a
`plurality of subflows. A policing engine is coupled to the
`classifier to receive each of the subflows, and to individually
`meter each of the subflows associated with each traffic flow
`in accordance with predefined subflow priorities assigned to
`each of the subflows.
`[0016] In accordance with another embodiment of the
`invention, a method is provided for maximizing exploitation
`of a contracted bandwidth for a flow. The flow is parsed into
`a high-priority subflow and at least one standard subflow.
`Rate limits are assigned to the high-priority subflow and the
`standard subflow. Packet conformance is monitored on a
`subflow level when the flow decreases to a predetermined
`bandwidth capacity. Guaranteed bandwidth is provided to
`the high-priority subflow while providing best effort band-
`width to the at least one standard subflow, regardless of
`whether the flow has exceeded its contracted bandwidth. If
`the flow has exceeded its contracted bandwidth, the band-
`width of the standard subflow is adjusted to bring the flow
`into conformance, while maintaining the guaranteed band-
`width to the high-priority subflow.
`[0017] These and various other advantages and features of
`novelty which characterize the invention are pointed out
`with particularity in the claims annexed hereto and form a
`part hereof. However, for a better understanding of the
`invention, its advantages, and the objects obtained by its use,
`reference should be made to the drawings which form a
`further part hereof, and to accompanying descriptive matter,
`in which there are illustrated and described specific
`examples of an apparatus in accordance with the invention.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`[0018] The invention is described in connection with the
`embodiments illustrated in the following diagrams.
`
`[0019] FIG. 1 is a block diagram illustrating a networking
`environment in which the principles of the present invention
`may be applied;
`
`[0020] FIG. 2 is a block diagram of an embodiment of a
`router system in which the present invention may be applied;
`
`[0021] FIG. 3 is a block diagram of an exemplary embodi-
`ment of an ingress processing system in accordance with the
`present invention;
`
`[0022] FIG. 4 is a block diagram illustrating selected
`functional blocks of an ingress processing system in accor-
`dance with the invention;
`
`[0023] FIG. 5 is a block diagram illustrating selected
`functional blocks of an ingress processing system utilizing
`embedded memory in accordance with the invention;
`
`[0024] FIG. 6 illustrates an example of a packet having
`fields in which flow and subflow classification can be based;
`
`[0025] FIG. 7 illustrates an example of how a data stream
`can be classified into flows and subflows;
`
`[0026] FIG. 8 is a block diagram illustrating how flows
`and subflows may be individually policed;
`
`[0027] FIG. 9 is a block diagram illustrating an ingress
`processing system employing the principles of the present
`invention;
`
`[0028] FIG. 10 is a block diagram illustrating a more
`detailed embodiment of the policing of flows and subflows
`in accordance with one embodiment of the invention;
`
`[0029] FIG. 11 is a flow diagram illustrating one embodi-
`ment of a policing methodology for providing hierarchical
`policing of flows and subflows of a data stream;
`
`[0030] FIGS. 12 and 13 illustrate particular embodiments
`of policing methodologies for providing hierarchical polic-
`ing of flows and subflows of a data stream in accordance
`with the invention;
`
`[0031] FIG. 14 is an embodiment of a three color marker
`policing methodology for providing hierarchical policing of
`flows and subflows of a data stream; and
`
`[0032] FIG. 15 is a flow diagram illustrating an embodi-
`ment as described above, where exploitation of the available
`bandwidth of the flow can be maximized by guaranteeing
`conformance for one subflow, while using best efforts for
`other subflows beyond their respective rate limits.
`
`DETAILED DESCRIPTION OF THE
`INVENTION
`
`In the following description of an exemplary
`[0033]
`embodiment, reference is made to the accompanying draw-
`ings which form a part hereof, and in which is shown by way
`of illustration specific embodiments in which the invention
`may be practiced. It is to be understood that other embodi-
`ments may be utilized, as structural and operational changes
`may be made without departing from the scope of the
`present invention.
`
`Cloudflare - Exhibit 1024, page 18
`
`Cloudflare - Exhibit 1024, page 18
`
`

`

`US 2002/0186661 Al
`
`Dec. 12, 2002
`
`3
`
`[0034] Generally, the present invention is directed to a
`system and method for prioritizing and policing communi-
`cations packets using multiple levels of classification and
`metering. The invention provides for classification of traffic
`streams into separate traffic flows, and for the further clas-
`sification of each traffic flow into subflows which can have
`different levels of priorities within the flow. The subflows
`may be further classified into additional subflows. Thus,
`during periods of high transfer rates from a flow, the
`allocation of remaining bandwidth for that flow will be
`biased towards packets associated to subflows of higher
`priority.
`[0035] A significant portion of the ensuing description is
`presented in terms of an exemplary policing engine embodi-
`ment according to the invention, in which particular
`examples of packet protocols and policing methodologies
`may be described in order to facilitate an understanding of
`various aspects of the invention. It should be recognized
`however, and will become readily apparent to those skilled
`in the art from a reading of the following description, that
`different packet protocols and policing methodologies other
`than those presented in the illustrated embodiments are
`contemplated by the invention. Therefore, the following
`references to the exemplary embodiments are illustrative
`examples, and the invention is clearly not limited thereto.
`
`In order to gain a better understanding of the
`[0036]
`invention, a description of an exemplary networking envi-
`ronment in which the present invention is applicable is
`provided.
`
`[0037] Data transmitted over networks such as the Internet
`10 may be in the form of e-mail messages, file transfers and
`downloads, web page loading, and the like. The data is
`generally broken up into a number of data packets, each of
`which is assigned a header to direct the data packet to the
`desired destination, among other things. Each packet is
`separately dispatched to the destination, although more than
`one different route may be taken by the different packets
`associated with the data.
`
`[0038] For example, the source computer 100 of FIG. 1
`may be configured in a local area network (LAN) and
`coupled to other computers 102 via a hub 104. A first one or
`more data packets may reach the hub 110 of the destination
`LAN via a first path, through routers 112, 114, 116, 118, 120
`and 122. A second one or more data packets may reach the
`hub 110 via a second path, such as through routers 112, 124,
`126, 116, 128 and 122. These different packets may take
`alternative routes due to equipment congestion or failure of
`a node, or to load share where possible. The routers asso-
`ciated with the core of the Internet can reconfigure the paths
`that these packets follow. This is due to the router's ability
`to analyze the header information corresponding to the data
`packet, and to communicate line condition and other infor-
`mation between routers. The routers handling data at the
`major traffic points on large networks, such as the Internet,
`are generally large stand-alone systems. After transmitting
`the data from node to node through the network, the packets
`are reassembled at the receiving end, and availed to the
`desired destination system 140.
`
`network traffic. The goal of implementing quality of service
`parameters is to prioritize certain flows over other flows
`based on some criteria. For example, priority may include
`dedicated bandwidth, controlled jitter and latency, improved
`loss characteristics, and the like. This can be performed, for
`example, by raising the priority of a flow or limiting the
`priority of another flow. Thus, each flow traversing the
`switches/routers shown in FIG. 1 may be subject to a quality
`of service parameter that affects the speed and reliability in
`which the packets are transmitted.
`
`[0040] Networking that implements such quality of ser-
`vice parameters is often referred to as policy-based network-
`ing. Policy-based networking is the management of the
`network so that various kinds of traffic (e.g., data, voice,
`video, etc.) obtains the availability and bandwidth needed to
`serve the network's users effectively. Using policy state-
`ments, network administrators can specify which kinds of
`service to give priority, at what times, and at what parts of
`their IP-based network. A policy-based network may include
`a network management console where policies are entered,
`modified, or retrieved from a policy repository. A policy
`decision point (PDP) is typically a server that retrieves
`policies from the policy repository, and acts on the policies
`on behalf of routers, switches, and other network devices
`that enforce the policies throughout the network.
`
`[0041] As will be described more fully below, the present
`invention may be used in connection with such routers,
`switches, and other network devices that enforce such poli-
`cies. Such a module is referred to herein as a policing engine
`or politer, and refers to the structural and/or operational
`module used to carry out the policing functions according to
`the present invention. Further, the present invention may be
`used in connection with multiprotocol flow classifying/
`parsing systems, as well as appropriate editing (also referred
`to as "packet transformation") systems to carry out marking
`where required. In one embodiment of the invention, the
`policing engine in accordance with the present invention is
`housed in a package or chip common to the classifier and
`editing functionalities. The device enables advanced ser-
`vices to be applied at speeds of 10 Gbps or more. Tightly
`coupled parsing, policing, and packet transformation allows
`the collective device to perform dynamic packet transfor-
`mation for quality of service (QoS) based on the current flow
`state and also effectively handles dynamic header processing
`such as required by multiprotocol label switching (MPLS)
`routers.
`
`[0042] Referring now to FIG. 2, one embodiment of a
`router system 200 is illustrated in which the present inven-
`tion may be applied. One or more line cards are provided,
`each of which are coupled to a switch fabric 202. In the
`present example, a plurality of line cards are provided,
`including line card-0204, line card-1206 through a finite
`number of line cards represented by line card-n 208. In one
`embodiment of the invention, each of the line cards utilize
`analogous circuitry. Line card-0204 will therefore be
`described, with the understanding that one or more of the
`remaining line cards in the router system may implement
`analogous circuitry.
`
`In connection with the transmission of packets
`[0039]
`through the network is the concept of quality of service
`(QoS) and policing. The QoS refers to the ability of the
`network to accommodate different service levels to selected
`
`[0043] The line card-0204 of the illustrated embodiment
`receives as input packet-over-SONET/SDH (POS) frames
`via the network. As is known in the art, SONET/SDH is a
`high-speed time division multiplexing (TDM) physical-
`
`Cloudflare - Exhibit 1024, page 19
`
`Cloudflare - Exhibit 1024, page 19
`
`

`

`US 2002/0186661 Al
`
`Dec. 12, 2002
`
`4
`
`layer transport technology. POS provides a means for using
`the speed and management capabilities of SONET/SDH to
`optimize data transport, although originally optimized for
`voice. A SONET/SDH frame is 810 bytes and is normally
`represented as a two-dimensional byte-per-cell grid of 9
`rows and 90 columns. The SONET/SDH frame is divided
`into transport overhead and payload bytes. The transport
`overhead bytes include section and line overhead bytes,
`while the payload bytes are made up of the payload capacity
`and some more overhead bytes referred to as path overhead.
`The overhead bytes are responsible for the management
`capabilities of SONET/SDH. The basic transmission rate of
`SONET (51.840 Mbps), referred to as Synchronous Trans-
`port Signal level 1 (STS-1), is achieved by sampling the
`810-byte frames at 8000 frames per second. SONET features
`an octet-synchronous multiplexing scheme with transmis-
`sion rates in multiples of 51.840 Mbps, whereby STS-192
`thereby provides transmission at approximately 10 Gbps.
`Packet Over SONET/SDH (POS) allows core routers to send
`native IP packets directly over SONET/SDH frames. POS
`provides a relatively low packet overhead and cost per Mbit
`than other data transport methods, which allows POS to
`efficiently support increases in IP traffic over existing and
`new fiber networks.
`
`[0044] As shown in the exemplary embodiment of FIG. 2,
`incoming POS OC-192 frames 210 originate from an
`OC-192 framer (not shown) and arrive at the line card-0204
`at the ingress interface 212. The frames are transferred to the
`ingress processing circuit 214 via an interface 216, such as
`the Optical Intemetworking Forum (OIF) System Packet
`Interface-4 (SPI-4). OW SPI-4 describes a data path inter-
`face between the physical and link layers to support physical
`line data rates up to 10 Gb/s, and may be used in connection
`with the present invention, as may other interfaces of
`appropriate speed.
`
`[0045] Ingress processing circuit 214, which in one
`embodiment of the invention is housed in a single chip,
`performs the necessary lookups, policing, and editing of the
`packet. If necessary, the frame can be redirected to the host.
`The frames are fed out of the ingress processing circuit 214
`via an OIF SPI-4 interface 218 to a Fabric Interface Chip
`(FIC) circuit 220. The FIC 220 converts the stream from one
`format to another, such as from POS frames to Common
`Switch Interface (CSIX) cells, and distributes the cells over
`the switch fabric 202.
`
`[0046] Similarly, cells switched at the switch fabric 202
`may be received at the FIC 222 and provided to the egress
`processing circuit 224. Frames are transferred to the egress
`interface 226 and output as POS OC-192 frames 228. A
`processor 230 may be coupled to the ingress processing
`circuit 214 and the egress processing circuit 224 to perform
`a variety of functions, including providing coprocessor
`support. Memories 232, 234 represent one or more memo-
`ries associated with the ingress processing module 214 and
`the egress processing module 224 respectively.
`
`[0047] Referring now to FIG. 3, an