WWWWWMMH
`
` IMWWWWWWMWW
`
`US 20020186661A1
`
`(19) United States
`(12) Patent Application Publication (10) Pub. No.: US 2002/0186661 A1
`(43) Pub. Date: Dec. 12, 2002
`
`Santiago et al.
`
`(S4) SYSTEM AND METHOD FOR
`HIERARCHICAL POLICING 0F FLOWS
`AND SUBFLOWS 01“ A DATA STREAM
`
`Publication Classification
`
`int. c1? ........................................................ H04J 1m;
`(51)
`
`(52) U.S. Cl.
`.. 3701252; 3703386
`
`(75)
`
`Inventors: Rodolfo A. Santiago. St. Innis Park,
`MN (US); Scott A. Sarkinen, Mounds
`View, MN (US)
`
`(57)
`
`ABSTRACT
`
`Correspondence Address:
`AIII‘ERA LAW GROUP, LLC
`6500 CITY WEST PARKWAY
`SUITE 100
`MINNEAPOLIS, MN 55344-7704 (US)
`
`(73) Assignee:
`
`'l‘erago Communications, Inc.,
`Grove, MN (US)
`
`Maple
`
`(21) App}. No:
`
`091849310
`
`(22
`
`l-‘iled:
`
`Ma}r 4, 2001
`
`A system and method [or policing individual flows and
`suhttows ofa data stream. Data traffic streams are classifier]
`into separate traflie flows, which in turn can be further
`classified into subllows,
`thereby providing for dillerent
`priority levels of subsets ol‘ the flow. 'Ihe subflowrs may be
`still further classified into additional subllows. creating a
`hierarchical, layered prioritization that can be metered at
`each vertical and horizontal level of the hierarchy. A packet
`[low rate ot'eacli ot' the subllows is compared to a predefined
`rate limit
`to allow suhfiows of a flow to have clitferent
`priorities therebetween.
`
`
`
`
`
`Palo Alto Networks V. Sable Networks
`
`IPR2020-01712
`
`EX1024
`
`EX1024
`Palo Alto Networks v. Sable Networks
`IPR2020-01712
`
`

`

`Patent Application Publication Dec. 12, 2002 Sheet 1 of 15
`
`US 2002/0186661 A1
`
`DESTINATION
`
`
`
` 102
` =| Isl-l!
`
`100
`
`

`

`51f02w
`
`US 2002/0186661 A1
`
`0..A
`
`c
`
`n.mm
`
`22’1a
`
`mSN
`
`DEEm5:3
`
`muzamuoE
`m$252M0-35“2:
`m..25was
`%comma?
`m-Ioe.c2.3wz:8N
` ozammuofi
`
`mama;
`
`mmwmum
`
`>moEmE
`
`

`

`Patent Application Publication Dec. 12, 2002 Sheet 3 of 15
`
`US 2002/0186661 A1
`
`300
`
`\
`
`0C 192 Framer
`
`302
`
`
`
`I DIF nLData (54} 200mm
`DIF Cure
`._
`
`304
`
`am
`
`.-
`
`3—12
`
`iIUI125MhZ
`
`
`
`- 38AM
`
`315
`
`Co-
`
`
`
`m CAM
`Programmable - (26)A_fldr
`_nstructions
`
`Address m Parsmg Engine -125M112
`
`[1.91125Mhz
`51AM” TLB
`
`I
`SHAM
`P ,1
`owing fi-SRAM Palicin E
`'ne
`“AME. [_2)IZEMhz
`IF
`9 fig!
`34”
`J3:Editor
`
`
`F’mcesswI
`
`
`
`~60“? Tesr
`
`TX
`
`34
`
`m "
`
`I DIF Dutput_Data (54) 200mm
`
`315
`
`_ f
`
`ig. 3
`
`

`

`Patent Application Publication Dec. 12, 2002 Sheet 4 of 15
`
`US 2002/0186661 A1
`
`412
`
`410
`
`414
`
`416
`
`l
`
`
`
`
`4.9.8
`
`EDITOR
`
`4o__s
`
`CDPBDCESSDR/CPU INTERFACE
`
` 42f]
`
`
`CLASSIFIEH
`an
`
`POLICER
`
`4_o4
`
`
`
`
`
`
`
`

`

`Patent Application Publication Dec. 12, 2002
`
`Sheet 5 of 15
`
`US 2002/0186661 A1
`
`IIIII
`
`xl'"Saga
`8Kgh/‘IIIIII'
`
`
`255255Haw“mafia“?aaaaa
`
`m-3%EEaWrEaWrE[raga
`\Nii?
`
`0
`
`E\
`
` 2%:DH23.,
`
`mmat
`
`
`
`
`

`

`Patent Application Publication Dec. 12, 2002
`
`US 2002/0186661 A1
`
`-
`
`
`
`imam<26in
`
`madam—n
`
`oE
`
`
`
`E2:Eam—
`
`255:8o
`
`N;o
`
`O
`
`s:2:NEE
`
`m58:agm
`
`
`
`
`
`
`

`

`Patent Application Publication Dec. 12, 2002
`
`Sheet 7 of 15
`
`US 2002/0186661 A1
`
`gm
`
`
`mummomosz—fi:wafimfiu
`
`
`
`
`Emmdzwwzfiofiomgodmzmx39”.
`
`I.l_E:EEEEE
`
`

`

`Patent Application Publication
`
`Dec. 12, 2002
`
`Sheet 8 of 15
`
`US 2002/0186661 A1
`
`
`
`man:85:52;
`
`.
`
`Neo—
`
`$25.”.
`
`$0de
`
`argue“—
`
`59m:
`
`mowmmuomn—
`
`Axum—E.
`
`9may“.we..Sodmzm
`
`mum\go:
`
`82x,
`\xxSS3282
`
`3982.
`
`Eng1
`
`
`
`.m§<¢u_33$an
`
`gdfiagfingadNENH
`
`"rm—wag:
`
`aggw‘gfinfihfififlnflh
`..«gflnfliflaafibuiflfiflfl.
`mfiqmmgommzmaw
`
`
`
`
`
`
`

`

`Patent Application Publication Dec. 12, 2002 Sheet 9 0f 15
`
`US 2002/0186661 A1
`
`1100
`
`SUBFLOWS
`
` CLASSIFY INTO FLOWS/
`l
`1102
`
`
`
` METER
`FLOW(S)
`
`
`
`
`
`
` FLOW
`
`BANDWIDTH EXCEED
`
`THRESHOLD?
`
`METER SUBFLOWS
`
`
`
`(AND OPTIONALLY FURTHER
`
`SUBFLUWS 0F SUBFLUWS)
`
`1106
`
`fig. 11
`
`

`

`Patent Application Publication Dec. 12, 2002 Sheet 10 0f 15
`
`US 2002/0186661 A1
`
`1200
`
`CLASSIFY THE NEXT PACKET IN DATA STREAM
`INTO FLOW/SUBFLOW
`
`METER FLUW
`
`1204
`
`EXCEEDED?
`
`DISCARD
`
` SUBFLOW
`PULICING THRESHOLD
`RATE EXDEEDED?
`
`
`
` FLOW RATE LIMIT
`PACKET
`
`
`
`
`
`
`METER SUBFLDW
`
` SUBFLOW RATE
`LIMIT EXCEEDED?
`
`fig. 12
`
`

`

`Patent Application Publication Dec. 12, 2002 Sheet 11 of 15
`
`US 2002/0186661 A1
`
`Upon arrival of a
`packet
`
`1304
`
`1306
`
`determine the packers
`associated flow and
`suhilaw
`
`1300
`
`1303
`
`m retrieve CIR, CBS, BBL, Plfi,
`
`PBS. PBL. SCBS. (331,
`PST, 8031 and SPBT:
`
`1302
`
`
`
`For all flows:
`SET CBT = CBS;
`
`SET SCBT = $083
`
`
`
`Earn credits for time idle
`
`SET CBT = min (CBS, time idle * CIR);
`
`
`SET SCBT = min {8633, time idle * CIR);
`
`1310
`
`
`
`N0
`
`1312
`
`
`CBT > no. of bytes in
`the packet
`
`
`YES
`
`1316
`
`
`GET > CBL.
`OR
`
`
`
`3081' > no. of bytes
`in the packet?
`
`
`
`YES
`
`NO
`
`1318
`
` Charge CBT and SCBT for packet's use of
`
`
`
`
`
`bandwidth:
`8131' BET = CBT - bytes in packet;
`SET 38131 =
`max (0, SCBT - no. of bytes in packet}
`
`1314
`
`1320
`
`packet is
`non-conforming
`
`packet is
`conforming
`
`fig. 13
`
`

`

`Patent Application Publication Dec. 12, 2002 Sheet 12 0f 15
`
`US 2002/0186661 A1
`
`Lg.
`
`14
`
`

`

`Patent Application Publication
`
`Dec. 12, 2002
`
`Sheet 13 0f 15
`
`US 2002/0186661 A1
`
`mow—
`
`DE:
`
`
`
`tamPmuw.5;.._.m0.mmmm.mmum
`
`
`
`
`
`we:
`
`_m>_:m“3qu:c
`
`mm:
`
`Jmm.wmn.ii759.30.59
`
`5:252
`
`
`
`32.5%Emas:859833363m5a:_E§mu
`
`EX3%
`
`“asx.2.:was$8.52u58mm
`
`”Ea*222%damageu5%mm
`
`”a?222%.mmmEEu5;mm
`
`
`
`“$.32;”55.3355nmamm
`
`
`
`£2wEfi.Ew3680Ema
`
`..._.mn_m
`
`33
`
`«$.082:{9:
`
`mm;
`
`H303EmetaE.o...VEm
`
`«:3~21.
`
`cow_.
`
`“mmuwHhmuwEm
`
`ummuH.59Em
`
`
`
`“mm”.H._.mn_.Em
`
`ozummmmHKimEm
`
`
`
`
`
`
`
`
`

`

`Patent Application Publication
`
`2.,mm:M“303Engm02E3%v5%m;=_3%v5%
`
`9,23:.
`
`m
`
`M
`
`US 2002/0186661 A1
`
`em”“93358%.E;nE;mm
`
`.b3353s8%a.2.5%.2meu5%mm
`
`
`
`m8:ragaE3%-5%gameu5%E“n33qu53%-an.nE;Es330858%a.8.5%5:5u5%mmm”is“.5m2:-:5n:5mm
`
`“E.mme
`
`“3qu2:{we
`
`:85
`
`«ma.F
`
`E039:{me
`
`2.2.3
`
`“3—939:fine
`
`um»
`
`Eng
`
`:_8:53d:VEu02mm;
`
`In
`
`E
`
`on:m;—
`
`.EuHV.Eu
`
`annv5;
`
`
`
`
`
`
`
`

`

`Patent Application Publication Dec. 12, 2002 Sheet 15 0f 15
`
`US 2002/0186661 A1
`
`CLASSIFY PACKET IN DATA STREAM
`
`INTO FLOW/SUBFLOW
`
`1500
`
`ENABLE SUBFLOW POLICING UPON FLOW
`
`REACHING PREDETERMINED THRESHOLD
`
`BANDWIDTH
`
`POLICE
`
`SUBFLOWS
`
` 1502
`
`I 506
`
`1508
`
`1510
`
`GUARANTEE BANDWIDTH TO HIGH-PRIORITY
`
`SUBFLOW REGARDLESS OF WHETHER THE
`
`FLOW STAYS IN CONFORMANCE
`
`BEGIN TO MARK PACKETS OF OTHER SUB-
`
`FLOWS AS NDN-CONFORMING IF FLOW
`
`BECOMES NON-CONFORMING
`
`ADJUST BANDWIDTH OF OTHER SUBFLOWS
`
`TO BRING FLOW INTO CONFORMANCE
`
`fig. 15
`
`

`

`US 2002/0186661 A1
`
`Dec. 12, 2002
`
`SYSTEM AND METHOD FOR HIERARCI-IICAL
`I’OLICING OF FLOWS AND SUBFI.()WS OF A
`DATA STREAM
`
`CROSS-REFERENCE TO OTHER PAI'ILN'I'
`APPLICATIONS
`
`[0001] The following co-pending patent applications of
`common assignee contains some common disclosure:
`
`“System And Method For Providing Transt‘orn
`[0002]
`matiort Of Multi-Pretoeol Packets
`In A Data
`Stream," Attorney Docket No. 1305.1—US—(t1, filed
`concurrentlyr herewith, which is incorporated herein
`by reference in its entirety;
`
`“A Method And Apparatus For Providing
`[0003]
`Multi-I’rotocol, Multi-Stage, Real-Time Frame Clas-
`sification”, Attorney Docket No. 1305.4-US-0't, tiled
`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.
`
`FIE-ID 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 sttbltows of a
`data stream.
`
`BACKGROUND OI: TIIE 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 ofservioe (005), which would then
`require “policing" to ensure conformance with the con-
`tractcd 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 008 is not violated. The amount
`of traflic flowing into or out of a particular interface may
`therefore require limiting actions to achieve a specific pol icy
`goal.
`
`[0008] Currently, varying data protocols require dilferent
`methods for policing traffic flows. For example, the ATM
`Forum’s FAST (Frame Based ATM over SonetiSDH 'l‘rans~
`port) data link protocol and the Internet Engineering Task
`Force (IE'I'I")’s [P data link protocol require different meth-
`ods for policing tratfic flows. FAST, being based on ATM
`cells, recommends the use of a variant ol’
`the GCRA,
`referred to as the Frame Based GCRA [F-GCRA). F-GCRA
`
`is the policing method provided in the ATM Forum’s specin
`tication of FAST, and the Internet Engineering Task Force
`(IETF)'s IIJ 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 (008) can be committed per
`flow by metering packets arriving at a given interface on a
`flow-byfifiow basis. Flows whose efi'ective bit rate exceeds
`what is committed in the service contract will be classified
`as nonconforming, 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-eon-
`I'orming affects the likelihood of the packets being dis-
`carded. This metering of packets.
`i.e., policing,
`for the
`purpose ofproviding 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 [low 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 he 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 "subilows" providing [or dilIerent priority levels of
`subsets ol‘
`the Ilow. The subllows may be still
`further
`classified into additional snbflows, creating a hierarchical,
`layered prioritization that can be metered at each vertical
`and horizontal level of the hierarchy. Thus, during periods oI~
`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.
`
`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 subflows. The
`
`

`

`US 2002/0186661 A1
`
`Dec. 12, 2002
`
`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 subliows are
`marked with one of a plurality of conformance indicators
`based on the measured rate of the respective first
`level
`subllow. In a more particular embodiment, a rate limit may
`be associated with each of the first level subliows, which can
`then be compared to the packet rate of the respective first
`level subflow in order to determine whether or not
`that
`subliow 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 suhilow into a plurality of second level subtlows,
`classifying one or more of the second level subllows 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.
`
`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 [or 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 subllows. and to individually
`meter each of the subflows associated with each traffic flow
`in accordance with predefined subllow priorities assigned to
`each of the subflows.
`
`In accordance with another embodiment of the
`[0016]
`invention, a method is provided for maximizing exploitation
`of a contracted bandwidth for a flow. ‘l'he flow is parsed into
`a high-priority subllow and at least one standard subllow.
`Rate limits are assigned to the high-priority subflow and the
`standard subllow. Packet conformance is monitored on a
`subllow 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 subllow is adjusted to bring the flow
`into conformance, while maintaining the guaranteed band-
`width to the high-priority subllow.
`
`[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 diagams.
`
`[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 he 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 subllow 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 suhflows 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 subllows of a data stream;
`
`[0030] FIGS. 12 and 13 illustrate particular embodiments
`of policing methodologies for providing hierarchical polic-
`ing of flows and subllows 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 subllows of a data stream; and
`
`[0032] FIG. 15 is a flow diagram illustrating an embodin
`menl as described above, where exploitation of the available
`bandwidth of the [low can be maximized by guaranteeing
`conformance for one subliow. while using best efforts for
`other subflows beyond their respective rate limits.
`
`DE'I'AILED DESCRIPTION 01" THE
`INVENTION
`
`In the following description of an exemplary
`[0033]
`embodiment, reference is made to the accompanying drawA
`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.
`
`

`

`US 2002/0186661 A1
`
`Dec. 12, 2002
`
`La.)
`
`invention is directed to a
`the present
`[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 subilows which can have
`different levels of priorities within the flow. The subllows
`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 suhftows 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 enviA
`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 dilferent route may be taken by the different packets
`associated with the data.
`
`For example, the source computer 100 of FIG. 1
`[0038]
`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 ofthe 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 traflic poian 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 005 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 How. Thus, each flow traversing the
`switchestrouters 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.
`
`implements such quality of ser-
`[0040] Networking that
`vice parameters is ot'ten referrer] to as policy-based network~
`ing. Policy-based networking is the management of the
`network so that various kinds of traiIic (cg, 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 [P—based network. Apolicy—hased network may include
`a network management console where policies are entered,
`modified, or retrieved from a policy repository. A policy
`decision point (PD?) 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 andior 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 (005) based on the current flow
`state and also elIectively 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 invenw
`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. Linc 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—SONE'USDI-I (PCS) frames
`via the network. As is known in the art, SONE’I‘XSDII is a
`high-speed time division multiplexing (TDM) physical-
`
`

`

`US 2002/0186661 Al
`
`Dcc. 12, 2002
`
`layer transport technology. POS provides a means for using
`the speed and management capabilities of SONETISDI-l to
`optimize data transport, although originally optimized for
`voice. A SONE’I‘r’SDH frame is 810 bytes and is normally
`represented as a two-dimensional byte-per-cell grid of 9
`rows and 90 columns. The SONETtSDH 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 SONE'l'r'SDH. The basic transmission rate of
`SONET ($1.840 Mbps), referred to as Synchronous Trans—
`port Signal level 1 (S’l‘S-l), is achieved by sampling the
`8 l tit-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-l92
`thereby provides transmission at approximately 10 Gbps.
`Packet Over SONETISDH (I’OS) allows core routers to send
`native IP packets directly over SONE'I‘fSDI-I 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 [’05 00192 frames 210 originate from an
`00192 framer (not shown) and arrive at the line card40204
`at the ingress interface 212. The frames are transferred to the
`ingreSs processing circuit 214 via an interface 216, such as
`the Optical lntcmetworking Forum (OIF) System Packet
`Interface-4 (SPI-4). 0117 SPI-4 describes a data path inter-
`face between the physical and link layers to support physical
`line data rates up to 10 (ibis, 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 PIC 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 OCT-192 fra met 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 eflicient and
`umful 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 pro-processor
`identifies each layer protocol using a multistage aigorithm
`coupled with a content—addressable memory (CAM) and
`memory (such as an SRAM) for resolving protocols. 'lhe
`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 [ire-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 rate flow, e.g., DiffServ 11’ and MPLS. The policing
`engine 313 works with memory, such as policing RAM 315
`which stores a drop policy for each connection. The policing
`engine, the subject of the present invention, is described in
`greater detail below.
`
`[0052] The editor 314, also referred to as a packet trans-
`formation cngine, utilizes the search results to index the
`appropriate editing instructions to be executed by an editing
`module. The editor 314 facilitates execution of multiple
`edits or “transformations” per packet as streaming data of
`various networking protocols associated with different net-
`working layers is input into the editing module. The editor
`314 supports comprehensive packet manipulation capability,
`including full MPLS labels, DAC operations such as mul-
`tiple push and pop operations, as well as traditional routing
`operations such as 'l‘l'L edits, checksum edits, and other
`routing operations. Asdescribed more fully below, the editor
`314 carries out the policing edits required by the policing
`engine's enforcemen