(19) United States
`(12) Patent Application Publication (10) Pub. No.: US 2002/0186661 A1
`(43) Pub. Date: Dec. 12, 2002
`
`Santiago et al.
`
`US 20020186661A1
`
`(54) SYSTEM AND METHOD FOR
`HIERARCHICAL POLICING OF FLOWS
`AND SUBFLOWS OF A DATA STREAM
`
`Publication Classification
`
`Int. Cl.7 ........................................................ H04J 1/16
`(51)
`(52) U.S.Cl.
`............................................ 370/252; 370/386
`
`(75)
`
`Inventors: Rodolfo A. Santiago, St. Louis Park,
`MN (US); Scott A. Sarkinen, Mounds
`View, MN (US)
`
`(57)
`
`ABSTRACT
`
`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. N0.:
`
`09/849,810
`
`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
`
`(22)
`
`Filed:
`
`May 4, 2001
`
`priorities therebetween.
`
`
`
`
`
`Microsoft
`
`Ex.1019- Page 1
`
`Microsoft
`Ex. 1019 - Page 1
`
`

`

`Patent Application Publication Dec. 12, 2002 Sheet 1 0f 15
`
`US 2002/0186661 A1
`
`=-EI-ILI
`
`DESTINATION
`
`E
`
`\‘
`
`a a M
`
`icrosoft
`
`Ex. 1019 - Page 2
`
`Microsoft
`Ex. 1019 - Page 2
`
`

`

`US 2002/0186661 A1
`
`EIo:33.8%
`
`mmmmOm
`
`:53:
`
`m
`
`.m
`
`m
`
`C
`
`2
`
`ae
`
`51
`
`.mcm
`
`w353E:w.tOnIoe.:25m2:SNmNmwfiu
`wEOE:ME.mN8925“2:
`
`
`
`
`eozamuoEDo:mama;
`
`J,o—N
`
`MNNNEN8N
`
`%uEmEmomma“:m55%cmammo;
`
`
`2a
`
`STUD
`
`mNN
`
`Nada
`
`05
`
`Microsoft
`
`Ex. 1019 - Page 3
`
`Microsoft
`Ex. 1019 - Page 3
`
`
`

`

`Patent Application Publication Dec. 12, 2002 Sheet 3 0f 15
`
`US 2002/0186661 A1
`
`300
`
`\
`
`315
`
`Policing
`RAM
`
`0C 192 Framer
`
`302
`
`I OlF RLData (54) 200Mhz
`OIF Core
`
`CAM/_ CAM
`_ . IF <—
`Programmable
`‘20) Adm
`Parsmg Engine Lb 125mm
`Address
`(19)125Mhz
`_ I
`Dta
`(7211;5Mhz
`‘—’
`
`I
`
`304
` I
`
`
`
`(201125an —mflil mm_
`
`
`mmml-
`
`Data
`(32) GGMhz
`
`h Config
`Add
`PI
`
`Test
`
`VF ’1'
`
`I
`
`Buffer
`
`fl
`
`JTAG -
`
`I
`OIF Core
`I OIF Output_Data (64) 200Mhz
`
`— f
`
`ig. 3
`
`Microsoft
`
`Ex. 1019 - Page 4
`
`TLB
`SRAM
`\ 332
`
`SRAM
`
`316
`
`Microsoft
`Ex. 1019 - Page 4
`
`

`

`Patent Application Publication Dec. 12, 2002 Sheet 4 0f 15
`
`US 2002/0186661 A1
`
`
`412
`410
`
`414
`
`415
`
`
`CLASSIFIER
`
`
`402
`
`4_Q_4
`
`POLICER
`
`COPRDCESSOR/CPU INTERFACE
`
`403
`
`
`
`
`420
`
`412
`
`410
`
`CLASSIFIER
`
`4_0_2
`
`
`
`:Fig. 5
`
`COPROCESSOR
`
`
`
`
`
`POLICER
`
`404
`
`CPU INTERFACE
`
`420
`
`Microsoft
`
`Ex. 1019 - Page 5
`
`Microsoft
`Ex. 1019 - Page 5
`
`

`

`Patent Application Publication Dec. 12, 2002 Sheet 5 0f 15
`
`
`
`_>_<m_m_._.w42.53
`
`mmg
`
`<I
`
`BKxiii-"‘-
`9%EE%Haw/,EZEEE
`
`
`
`
`ii?«mEma“mafia“?EEEWQ
`
`%%IIIII
`
`1A166%
`
`2\w'I2%DHDHUS\
`m2%EHumg
`
`Microsoft
`
`Ex. 1019 - Page 6
`
`Microsoft
`Ex. 1019 - Page 6
`
`
`
`
`

`

`Patent Application Publication Dec. 12, 2002 Sheet 6 0f 15
`
`US 2002/0186661 A1
`
`4558
`
`:2:NEE
`
`Sw
`
`a;~25:
`
`N8
`
`om<>>mE
`
`NE
`
`25%I
`
`:_>=._m:.<m
`
`
`
`m->>o._u_m:mEm
`
`
`
`Microsoft
`
`Ex. 1019 - Page 7
`
`Microsoft
`Ex. 1019 - Page 7
`
`
`
`
`

`

`Patent Application Publication Dec. 12, 2002 Sheet 7 0f 15
`
`US 2002/0186661 A1
`
`com
`
`in._,.w.»
`;vin/
`
`mom
`
`Emmdfim
`
`Emmomo
`
`mote
`
`wz_u_._o..._
`
`mZEZm
`
`Eodmzm\>>o._u_
`
`mm=n=mm<._o
`
`Microsoft
`
`Ex. 1019 - Page 8
`
`Microsoft
`Ex. 1019 - Page 8
`
`
`
`
`
`

`

`Patent Application Publication
`
`Dec. 12, 2002 Sheet 8 0f 15
`
`US 2002/0186661 A1
`
`
`
`$2.5m
`
`mommmuomm
`
`EmES:
`
`mod;825%.;
`
`gm:5:
`
`a.
`
`82\
`
`mszEm__>_<E
`
`
`
`E2“::35:
`
`L.Q;443A:agflgga,$93:“Mw“52$25%.;
`
`N_
`
`sowoo?
`
`83
`
`85:535.x\E:xx32was:
`2653mm
`
`S3%
`
`HNEE“.
`
`W59m:42W
`
`Microsoft
`
`Ex. 1019 - Page 9
`
`Microsoft
`Ex. 1019 - Page 9
`
`
`
`
`
`

`

`Patent Application Publication Dec. 12, 2002 Sheet 9 0f 15
`
`US 2002/0186661 A1
`
`1100
`CLASSIFY INTO FLOWS/
`
`SUBFLOWS
`
`
`
` FLOW
`
`BANDWIDTH EXCEED
`
`THRESHOLD?
`
`
`
`METER SUBFLOWS
`
`
`
`(AND OPTIONALLY FURTHER
`
`SUBFLOWS 0F SUBFLOWS)
`
`1106
`
`Microsoft
`
`Ex.1019- Page 10
`
`Microsoft
`Ex. 1019 - Page 10
`
`

`

`Patent Application Publication Dec. 12, 2002 Sheet 10 0f 15
`
`US 2002/0186661 A1
`
`CLASSIFY THE NEXT PACKET IN DATA STREAM
`INTO FLOW/SUBFLOW
`
`METER FLOW
`
`1204
`
`EXCEEDED?
`
`DISCARD
`
`
`
` FLOW RATE LIMIT
`PACKET
`
`
`
`
`
`
` SUBFLOW
`POLICING THRESHOLD
`RATE EXDEEDED?
`
`METER SUBFLOW
`
` SUBFLOW RATE
`LIMIT EXCEEDED?
`
`fig. 12
`
`Microsoft
`
`Ex.1019- Page 11
`
`Microsoft
`Ex. 1019 - Page 11
`
`

`

`Patent Application Publication Dec. 12, 2002 Sheet 11 0f 15
`
`US 2002/0186661 A1
`
`Upon arrival of a
`packet
`
`1304
`
`1 306
`
`determine the packet's
`associated flow and
`subflow
`
`1300
`
`1308
`
`PBS, PBL, SCBS, CBT,
`PBT, SCBT and SPBT:
`
`1302
`
`
`For all flows:
`
`SET CBT = CBS;
`
`SET SCBT = $088
`
`Earn credits for time idle
`SET CBT = min (CBS, time idle * CIR);
`SET SCBT = min (SCBS, time idle * CIR);
`
`
`
`
`
`
`
`
`
`
`1310
`
`1312
`
`
`CBT > no. of bytes in
`the packet
`
`
`
`
`
`SCBT > no. of bytes
`in the packet?
`
`
`CBT > CBL,
`0R
`
`
`
`
`Charge CBT and SCBT for packet's use of
`bandwidth:
`
`1318
`
`SET CBT = CBT - bytes in packet;
`
`SET SCBT =
`
`max (0, SCBT - no. of bytes in packet)
`
`
`
`1314
`
`1320
`
`packet is
`non-conforming
`
`packet is
`conforming
`
`fig. 13
`
`Microsoft
`
`Ex.1019- Page 12
`
`Microsoft
`Ex. 1019 - Page 12
`
`

`

`Patent Application Publication Dec. 12, 2002 Sheet 12 0f 15
`
`US 2002/0186661 A1
`
`
`
`ig.14a
`
`
`
`Mg,1419
`
`$ng14
`
`Microsoft
`
`Ex.1019- Page 13
`
`Microsoft
`Ex. 1019 - Page 13
`
`

`

`Patent Application Publication
`
`Dec. 12, 2002 Sheet 13 0f 15
`
`US 2002/0186661 A1
`
`mo:
`
`0::
`
`
`
`
`
`.._mn_.mmm.EmJmo.mmu.Eu
`
`we:
`
`_m>_:m“968:o
`
`me:
`
`65:me
`
`
`
`26:269325:85683£8382:2.53%
`
`Sww
`
`33
`
`H.9882:is:
`
`um:
`
`mm;
`
`“968E3:3B.o:vEm
`
`02
`
`uE5*£29::2%qu?HEowEm
`
`
`
`“Ea*222:;.mmmmvEEH5%Em
`
`
`
`“EFT220E:.mmmvEEHE;Em
`
`
`
`figure:wEswmovEEHEuEm
`
`22we:3.,£8558
`
`
`
`.25FmomHm;qu.wmmw.33
`
`mem
`
`N2:
`
`we:
`
`so:
`
`uwmowHhmuwEm
`
`ummEmH5mmEm
`
`u.mmu
`
`umm;
`
`EuEm
`
`EmEm
`
`Microsoft
`
`Ex. 1019 - Page 14
`
`Microsoft
`Ex. 1019 - Page 14
`
`
`
`
`
`
`
`

`

`Patent Application Publication
`
`Dec. 12, 2002 Sheet 14 0f 15
`
`US 2002/0186661 A1
`
`wNS
`
`33.m2:
`
`._moHVHmu.5;UV._.mn_
`
`02E313VHmummm;5m3>nV._.m_n_wmm;
`“9.02“9.08
`DZ<DZ<
`
`
`
`on::3qus3%-5%.258.u5%mm
`
`3.863E3:5-EmnE;Em
`
`3.838E8%B.o:.Eum.9va8HEuwEm
`
`“Egg53%.:3n50mmm:\oz
`
`5.08E3%B.o:vEuozmm;
`
`to
`
`E
`
`“NE@an
`
`
`
`29.08E3%.s.2..25ééen5%.E$0253%-E;u5:mm
`
`“$632:f3.
`
`58m
`
`NM:
`
`E089:ice
`
`26:?»
`
`«N3om:
`
`E082:x88
`
`be
`
`Microsoft
`
`Ex.1019- Page 15
`
`Microsoft
`Ex. 1019 - Page 15
`
`
`
`
`
`
`
`
`
`
`

`

`Patent Application Publication Dec. 12, 2002 Sheet 15 0f 15
`
`US 2002/0186661 A1
`
`CLASSIFY PACKET IN DATA STREAM
`
`INTO FLOW/SUBFLOW
`
`ENABLE SUBFLOW POLICING UPON FLOW
`
`REACHING PREDETERMINED THRESHOLD
`
`BANDWIDTH
`
`
`
`SUBFLOWS
`
`1504
`
`POLICE
`
`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 1F FLOW
`
`BECOMES NON-CONFORMING
`
`ADJUST BANDWIDTH OF OTHER SUBFLOWS
`
`
`
`TO BRING FLOW INTO CONFORMANCE
`
`1500
`
`1502
`
`1506
`
`1508
`
`1510
`
`cfig. 15
`
`Microsoft
`
`Ex.1019- Page 16
`
`Microsoft
`Ex. 1019 - Page 16
`
`

`

`US 2002/0186661 A1
`
`Dec. 12, 2002
`
`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:
`
`“System And Method For Providing Transfor-
`[0002]
`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;
`
`“A Method And Apparatus For Providing
`[0003]
`Multi-Protocol, Multi-Stage, Real-Time Frame Clas-
`sification”, Attorney Docket No. 1305.4-US-01, filed
`concurrently herewith, which is incorporated herein
`by reference in its entirety;
`
`“System And Method For Policing Multiple
`[0004]
`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 subfiows 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.
`
`In order to make the most efficient use of the
`[0007]
`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-fiow 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 subfiows 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
`
`To overcome limitations in the prior art described
`[0012]
`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 subfiows 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 “subfiows” providing for different priority levels of
`subsets of the flow. The subfiows may be still further
`classified into additional subfiows, 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 subfiows of higher priority.
`
`In accordance with one embodiment of the inven-
`[0013]
`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 subfiows. The
`
`Microsoft
`
`Ex.1019- Page 17
`
`Microsoft
`Ex. 1019 - Page 17
`
`

`

`US 2002/0186661 A1
`
`Dec. 12, 2002
`
`method includes measuring a rate of each of the first level
`subfiows associated with the traffic flow, when the traffic
`flow reaches a predetermined bandwidth threshold. The
`packets associated with each of the first level subfiows 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 subfiows, 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 subfiows,
`classifying one or more of the second level subfiows into a
`plurality of third level subfiows, and so forth. A computer-
`readable medium having computer-executable instructions
`for performing such policing functions is also provided.
`
`In accordance with another embodiment of the
`[0014]
`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.
`
`In accordance with another embodiment of the
`[0015]
`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 subfiows. A policing engine is coupled to the
`classifier to receive each of the subfiows, and to individually
`meter each of the subfiows associated with each traffic flow
`
`in accordance with predefined subflow priorities assigned to
`each of the subfiows.
`
`In accordance with another embodiment of the
`[0016]
`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 subfiow, 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 subfiows;
`
`[0026] FIG. 8 is a block diagram illustrating how flows
`and subfiows 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 subfiows
`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 subfiows of a data stream;
`
`[0030] FIGS. 12 and 13 illustrate particular embodiments
`of policing methodologies for providing hierarchical polic-
`ing of flows and subfiows 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 subfiows 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 subfiow, while using best efforts for
`other subfiows 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.
`
`Microsoft
`
`Ex.1019- Page 18
`
`Microsoft
`Ex. 1019 - Page 18
`
`

`

`US 2002/0186661 A1
`
`Dec. 12, 2002
`
`the present invention is directed to a
`[0034] Generally,
`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 subfiows which can have
`
`different levels of priorities within the flow. The subfiows
`may be further classified into additional subfiows. 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 subfiows 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. Afirst 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.
`
`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
`
`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. Apolicy-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 policer, 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.
`
`[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-
`
`Microsoft
`
`Ex.1019- Page 19
`
`Microsoft
`Ex. 1019 - Page 19
`
`

`

`US 2002/0186661 A1
`
`Dec. 12, 2002
`
`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 Internetworking Forum (OIF) System Packet
`Interface-4 (SPI-4). OIF 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.
`
`Ingress processing circuit 214, which in one
`[0045]
`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 exemplary embodi-
`ment of an ingress processing system 300 in accordance
`with the present invention is provided. The system 300 is
`described as an example of a system in which the principles
`of the present invention may be applied. The ingress pro-
`cessing system 300 interfaces to industry standard physical
`layer devices such as an OC-192 framer 302. In one embodi-
`
`ment of the invention, a portion of the ingress processing
`system 300 is housed on a single chip, illustrated in FIG. 3
`as chip 304. While the invention is equally applicable where
`the physical chip boundaries differ from that illustrated in
`FIG. 3, the present invention is particularly efficient and
`useful in such a tightly coupled arrangement.
`
`[0048] The interface 306, such as an OIF interface, pro-
`vides the interface between the ingress processing circuit
`304 and the framer 302. In one embodiment, the interface
`306 is a 200 MHZ OIF SPI-4 interface including a 64-bit
`data input. An elasticity buffer 308, which in one embodi-
`ment is a first-in-first-out (FIFO), allows table maintenance
`updates to be performed without dropping frames.
`
`[0049] The pre-processor 310 performs a variety of func-
`tions, including packet verification and discarding, packet
`protocol
`identification, statistics compilation, and others.
`The packet protocol identification includes classifying the
`type of frame that has been received. The pre-processor
`identifies each layer protocol using a multistage algorithm
`coupled with a content-addressable memory (CAM) and
`memory (such as an SRAM) for resolving protocols. The
`frame is then stored in a memory along with the result of the
`preprocessor, i.e., the protocol layer code.
`
`[0050] The parsing engine 312 performs layer classifica-
`tion and tagging via a search engine. One of the various
`functions of the parsing engine 312 is to parse the frames
`processed by the pre-processor, and generate search keys
`from data anywhere within the frame. The protocol layer
`code is used as a start vector into an instruction memory,
`which contains instructions for the parsing engine 312 and
`pointers to access selected words in a frame buffer. The
`parsing engine 312 receives the instruction and performs the
`functions selected by the corresponding instruction opera-
`tional code. The results are used with an extractor that builds
`
`search keys which can be applied against a CAM (or indexed
`directly to a memory) to generate “search results” that
`contain the frame classification.
`
`[0051] The policing engine 313 performs a variety of
`functions, including ensuring flow conformance to a maxi-
`mum allowed peak rate and a contractually obliged com-
`mitted rat