Hierarchical policers for enforcing differentiated traffic behavior

RELATED APPLICATIONS

This application is a continuation of U.S. patent application Ser. No. 10/298,552 filed Nov. 19, 2002, the entire disclosure of which is incorporated herein by reference.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The invention relates generally to processing network traffic, and more particularly, to the policing of network traffic to confirm to a desired service.

2. Description of Related Art

Routers receive data on a physical media, such as optical fiber, analyze the data to determine its destination, and output the data on a physical media in accordance with the destination. Routers were initially designed using a general purpose processor executing large software programs. As line rates and traffic volume increased, however, general purpose processors could not scale to meet these new demands. For example, as functionality was added to the software, such as accounting and policing, these routers suffered performance degradation. In some instances, the routers failed to handle traffic at line rate when the new functionality was implemented.

To meet the new demands, purpose-built routers were designed with components optimized for routing. These routers not only handle higher line rates and higher network traffic volume, they also add functionality without compromising line rate performance.

A purpose-built router may include a number of input and output ports from which it transmits and receives information packets. A packet received at one port is typically directed to its appropriate output port based on an examination and processing of the packet's header information, which includes an indication of the packet's destination. A high-performance router must accordingly examine and process the information packets at a high speed.

It may be desirable to provide a certain level of service in a purpose-built router, for example using a policer, rather than a queue. <figref idref="DRAWINGS">FIG. 1</figref> is a block diagram illustrating an exemplary token bucket policer <b>100</b>. Policer <b>100</b> may include, conceptually, a token bucket <b>110</b> and a number of credits <b>120</b> in bucket <b>110</b>. Those skilled in the art will appreciate that policer <b>100</b> may be implemented using software, hardware, or some combination of both.

In practice, policer <b>100</b> may be used to impose some level of service on entering packets, for example by rate limiting traffic. In such a case, a packet is passed through policer <b>100</b> if a sufficient number of credits <b>120</b> (e.g., proportional to a size of the packet) is present in bucket <b>110</b>. If the sufficient number of credits <b>120</b> is present, this number of credits <b>120</b> is removed from bucket <b>110</b> when the packet is passed. If the sufficient number of credits <b>120</b> is not present, however, the packet may “fail” and may be dropped, marked as non-conforming, etc. More credits <b>120</b> may be perodically added to bucket <b>110</b> at a rate that corresponds to the overall bandwidth of policer <b>100</b>. Further, the size of bucket <b>110</b> (i.e., an upper limit on the number of credits <b>120</b> that will fit in bucket <b>110</b>, if applicable) may correspond to a maximum burst size allowed by policer <b>100</b>.

Such a policer <b>100</b> may create a bandwidth-limited service, or other type of desired service, within a purpose-built router or other network device. When differentiated levels of service (e.g., high priority, low priority, premium, ordinary, etc.) are desired, however, such policers may have difficulty in properly handling different types of packets.

Thus, it is desirable to police network traffic to confirm to desired levels of service in high-performance routers and other network devices.

SUMMARY OF THE INVENTION

Systems and methods consistent with the principles of the invention, among other things, provide for improved policing of traffic with different levels of service.

In accordance with one purpose of the invention as embodied and broadly described herein, a hierarchical policer may include a sorter configured to separate data of a first type from data of a second type. A first policer may be configured to police the data of the first type from the sorter. A second policer may be configured to selectively police the data of the second type from the sorter and data of the first type from the first policer.

In another implementation consistent with the principles of the invention, a hierarchical traffic policer may include a first policer configured to pass first packets when a first condition is met. The first policer also may alter selection information within the passed first packets. A second policer may be configured to pass second packets when a second condition is met. The second policer may be further configured to pass all of the passed first packets from the first policer based on the altered selection information within the passed first packets.

In a further implementation consistent with the principles of the invention, a method for policing traffic may include separating high priority data and low priority data and determining a threshold amount of high priority credit based on a unit of high priority data. The unit of high priority data may be approved to produce a unit of approved data when a present amount of high priority credit exceeds the threshold amount of high priority credit. A threshold amount of low priority credit may be ascertained based on a unit of low priority data. The unit of low priority data may be allowed when a present amount of low priority credit exceeds the threshold amount of low priority credit. The unit of approved data may be passed without considering the present amount of low priority credit.

In yet another implementation consistent with the principles of the invention, a method for policing traffic may include setting meta-data in a plurality of packets of information and policing a first set of the packets of information. The meta-data in packets of the first set that passed the policing may be changed. A second set of the packets of information may be selectively policed based on the meta-data in the second set of packets.

In still a further implementation consistent with the principles of the invention, a network device for processing packets may include a buffer configured to store the packets, including header data and payload data for the packets. A packet routing component may be coupled to the buffer. The packet routing component may be configured to perform packet routing based on header data from the buffer. The packet routing component may include a first policer configured to pass first header data when a first condition is met and to alter selection information within the passed first packets. The packet routing component also may include a second policer configured to pass second header data when a second condition is met. The second policer may be further configured to pass all of the passed first header data from the first policer based on the altered selection information within the passed first header data.

BRIEF DESCRIPTION OF THE DRAWINGS

The accompanying drawings, which are incorporated in and constitute a part of this specification, illustrate an embodiment of the invention and, together with the description, explain the invention. In the drawings,

<figref idref="DRAWINGS">FIG. 1</figref> is a block diagram conceptually illustrating a token bucket policer;

<figref idref="DRAWINGS">FIG. 2</figref> is a block diagram illustrating an exemplary routing system in which principles consistent with the invention may be implemented;

<figref idref="DRAWINGS">FIG. 3</figref> is an exemplary detailed block diagram illustrating portions of the routing system shown in <figref idref="DRAWINGS">FIG. 2</figref>;

<figref idref="DRAWINGS">FIG. 4</figref> is a diagram illustrating portions of <figref idref="DRAWINGS">FIG. 3</figref> in additional detail;

<figref idref="DRAWINGS">FIG. 5</figref> is a diagram illustrating a policer consistent with the principles of the invention; and

<figref idref="DRAWINGS">FIG. 6</figref> is a flow chart illustrating operation of the policer of <figref idref="DRAWINGS">FIG. 5</figref> consistent with the principles of the invention.

DETAILED DESCRIPTION

The following detailed description of the invention refers to the accompanying drawings. The same reference numbers may be used in different drawings to identify the same or similar elements. Also, the following detailed description does not limit the invention. Instead, the scope of the invention is defined by the appended claims and equivalents of the claim limitations.

As described herein, a hierarchical policer may include at least two policers that either normally police traffic or pass the traffic without policing based on certain data within the traffic. The certain data may be changed after normal policing.

System Configuration

<figref idref="DRAWINGS">FIG. 2</figref> is a block diagram illustrating an exemplary routing system <b>200</b> in which the present invention may be implemented. System <b>200</b> receives a data stream from a physical link, processes the data stream to determine destination information, and transmits the data stream out on a link in accordance with the destination information. System <b>200</b> may include packet forwarding engines (PFEs) <b>210</b><i>a</i>, <b>210</b><i>b</i>, . . . , <b>210</b><i>n </i>(collectively, <b>210</b>), a switch fabric <b>220</b>, and a routing engine (RE) <b>230</b>.

RE <b>230</b> performs high level management functions for system <b>200</b>. For example, RE <b>230</b> communicates with other networks and systems connected to system <b>200</b> to exchange information regarding network topology. RE <b>230</b> creates routing tables based on network topology information, creates forwarding tables based on the routing tables, and forwards the forwarding tables to PFEs <b>210</b>. PFEs <b>210</b> use the forwarding tables to perform route lookup for incoming packets. RE <b>230</b> also performs other general control and monitoring functions for system <b>200</b>.

PFEs <b>210</b> are each connected to RE <b>230</b> and switch fabric <b>220</b>. PFEs <b>210</b> receive data at ports on physical links connected to a network, such as a wide area network (WAN), a local area network (LAN), or a device. Each physical link could be one of many types of transport media, such as optical fiber or Ethernet cable. The data on the physical link is formatted according to one of several protocols, such as the synchronous optical network (SONET) standard or Ethernet.

PFEs <b>210</b> process incoming data by stripping off the data link layer. PFEs <b>210</b> convert header information from the remaining data into data structures referred to herein as “notifications” and “cells” (where a cell may be a fixed length data unit). For example, in one embodiment, the data remaining after the data link layer is stripped off is packet data. PFEs <b>210</b> include the layer 2 (L2) and layer 3 (L3) packet header information, some control information regarding the packets, and the packet data in a series of cells called “D” cells. In one embodiment, the L2, L3, and the control information are stored in the first two cells of the series of cells.

In general, L2 header information refers to header information used to steer packets within LANs. L3 header information, in contrast, provides connectivity between different LANs. In this sense, the L3 header information provides higher level destination information than the L2 header. An incoming packet may include both L2 and L3 header information. Router <b>200</b> may modify the packets L2 and L3 header information before transmitting the packet to its next destination.

PFEs <b>210</b> form a notification based on the L2, L3, and control information, and performs a route lookup using the notification and the routing table from RE <b>230</b> to determine destination information. PFEs <b>210</b> may also further process the notification to perform protocol-specific functions, policing, and accounting, and might even modify the notification to form a new notification.

If the determined destination indicates that the packet should be sent out on a physical link connected to a particular one of PFEs <b>210</b>, then the PFE retrieves the cells for the packet, converts the notification or new notification into header information, forms a packet using the packet data from the cells and the header information, and transmits the packet from the port associated with the physical link.

If the destination indicates that the packet should be sent to another PFE via switch fabric <b>220</b>, then the PFE retrieves the cells for the packet, modifies the first two cells with the new notification and new control information, if necessary, and sends the cells to the other PFE via switch fabric <b>220</b>. Before transmitting the cells over switch fabric <b>220</b>, PFEs. <b>210</b> append a sequence number to each cell, which allows the receiving PFE to reconstruct the order of the transmitted cells. Additionally, the receiving PFE uses the notification to form a packet using the packet data from the cells, and sends the packet out on the port associated with the appropriate physical link of the receiving PFE.

In summary, in one embodiment, RE <b>230</b>, PFEs <b>210</b>, and switch fabric <b>220</b> perform routing based on packet-level processing. PFEs <b>210</b> store each packet in cells while performing a route lookup using a notification, which is based on packet header information, including L2 and L3 layer header information. A packet might be received on one PFE and go back out to the network on the same PFE, or be sent through switch fabric <b>220</b> to be sent out to the network on a different PFE.

<figref idref="DRAWINGS">FIG. 3</figref> is an exemplary detailed block diagram illustrating portions of routing system <b>200</b>. PFEs <b>210</b> connect to one another through switch fabric <b>220</b>. Each of the PFEs may include one or more physical interface cards (PICs) <b>310</b><i>a</i>, <b>310</b><i>b </i>(collectively, <b>310</b>) and a flexible port concentrators (FPC) <b>320</b>.

Each of PICs <b>310</b> may transmit data between a physical link and FPC <b>320</b>. Different PICs are designed to handle different types of physical links. For example, one of PICs <b>310</b> may be an interface for an optical link while another PIC may be an interface for an Ethernet link.

FPC <b>320</b> performs routing functions and handle packet transfers to and from PICs <b>310</b> and switch fabric <b>220</b>. For each packet it handles, an FPC performs the previously-discussed route lookup function. Although <figref idref="DRAWINGS">FIG. 3</figref> shows two PICs connected to FPC <b>320</b> and three FPCs connected to switch fabric <b>220</b>, in other embodiments consistent with principles of the invention there can be more or fewer PICs <b>310</b> and FPCs.

<figref idref="DRAWINGS">FIG. 4</figref> is an exemplary configuration of FPC <b>320</b> according to an implementation consistent with the principles of the invention. FPC <b>320</b> may include processing units <b>432</b> and <b>434</b>, a first input/output (I/O) unit <b>436</b>, a second I/O unit <b>438</b>, a memory unit <b>440</b>, and an R unit <b>442</b>. Each processing unit <b>432</b> and <b>434</b> corresponds to one or more of PICs <b>310</b>.

As will be described in greater detail below, processing units <b>432</b> and <b>434</b> may process packet data flowing between PICs <b>310</b> and first I/O unit <b>436</b>. Each processing unit <b>432</b> and <b>434</b> may process packet data received from the PIC connected to it, and data received from first I/O unit <b>436</b>.

For example, processing unit <b>432</b> or <b>434</b> may process packets from PICs <b>310</b> to convert the packets into data cells, and transmit the data cells to first I/O unit <b>436</b>. Data cells are the data structure used by FPC <b>320</b> internally for transporting and storing data. In one implementation, data cells are 64 bytes in length.

In the other direction, processing unit <b>432</b> or <b>434</b> receives data cells and notifications from first I/O unit <b>436</b>, extracts certain information and packet data from the data cells, and creates a packet based on the extracted information. Processing unit <b>432</b> or <b>434</b> creates the packet header based on the information extracted from the data cells. In one embodiment, processing unit <b>432</b> or <b>434</b> creates L2 and L3 header information based on the extracted information. The created L2 and L3 header information constitutes a new header that the packet uses as it is subsequently transmitted through the physical link.

R unit <b>442</b> may receive notifications from first I/O unit <b>436</b> and second I/O unit <b>438</b>. R unit <b>442</b> may provide a variety of functions, such as route lookup, accounting, and policing functionality, based on the notifications. R unit <b>442</b> may receive one or more forwarding tables from RE <b>230</b> (<figref idref="DRAWINGS">FIG. 2</figref>) and use keys, forwarding table(s), and encapsulation tables to perform route or encapsulation lookups. R unit <b>442</b> may insert the lookup result into a notification, which it may store in memory unit <b>440</b>.

Memory unit <b>440</b> may temporarily store data cells from first I/O unit <b>436</b> and second I/O unit <b>438</b> and notifications from R unit <b>442</b>. Memory unit <b>440</b> may dispatch the notifications to first I/O unit <b>436</b> and second I/O unit <b>438</b>. In response, first I/O unit <b>436</b> and second I/O unit <b>438</b> may use address information in the notification to read out data cells from memory unit <b>440</b> that correspond to a notification. The notification received from memory unit <b>440</b> may have been modified by R unit <b>442</b> with route or encapsulation lookup results. First I/O unit <b>436</b> and second I/O unit <b>438</b> may update the data cells read out of memory unit <b>440</b> with information from the modified notification. The data cells, which now include information from the modified notification, are sent to processing unit <b>432</b>, processing unit <b>434</b>, or switch fabric <b>220</b>, depending on which of first I/O unit <b>436</b> or second I/O unit <b>438</b> is processing the notification.

Exemplary Traffic Policer

A hierarchical policer consistent with the principles of the invention herein may be used in system <b>200</b> described above, but could be used in any device (e.g., a network device) that polices traffic. For example, a policer consistent with the principles of the invention may be used at the ingress of system <b>200</b> (e.g., processing unit <b>432</b> or <b>434</b>) and/or in the route lookup part of the system <b>200</b> (e.g., R unit <b>442</b>). It may be used, however, anywhere in the path through a router or network device. The policer described herein may police packets or items representing packets, such as notifications.

One service example, in which context a policer consistent with the principles of the invention will be discussed, involves differentiation between “premium” traffic (e.g., high priority) and “ordinary” traffic (e.g., low priority). For the sake of discussion, suppose that one wishes to admit 1 Mbps of total traffic into a network (with 100 kb maximum burst size), and that within the total traffic, up to 200 kbps may be premium traffic (with 20 kb maximum burst size). Further, if the total traffic exceeds 1 Mbps, only the ordinary traffic should be dropped. The following exemplary traffic policer and its operation will be discussed in the context of this dual-priority example. It should be noted, however, that the principles of the invention are applicable to any number of differentiated traffic service levels.

<figref idref="DRAWINGS">FIG. 5</figref> is a diagram illustrating a hierarchical policer <b>500</b> consistent with the principles of the invention. Policer <b>500</b> may include a sorter <b>510</b>, a high priority policer <b>520</b>, and a low priority policer <b>530</b>. Policer <b>500</b> and its components may be implemented in logic, a general purpose processor, a special purpose processor, or some combination thereof

Sorter <b>510</b> may sort premium traffic from ordinary traffic, and route packets of each type accordingly. Although policer <b>500</b> will be described in terms of processing packets, it should be understood that in another embodiment policer <b>500</b> processes data (e.g., notifications) associated with respective packets. Sorter <b>510</b> also may be configured to set one or more bits of meta-data (i.e., data about the data in the packet) in each packet, called the Normal Policer Instruction (NPI), to a common value. The NPI may be referred to generically as “selection information” or a “flag” in the packet. With their respective NPIs set (e.g., to logical “1”), sorter <b>500</b> may be configured to send premium packets to the high priority policer <b>520</b> and ordinary packets to the low priority policer <b>530</b>. Sorter <b>510</b> need not set the NPI value; it may already be set by default when the header information is created.

High priority policer <b>520</b> may be configured to perform “normal” token bucket-type policing on premium packets, based on their NPI value of 1. That is, high priority policer <b>520</b> may be configured to pass on any premium packets that conform to its bandwidth/burst rate requirements (e.g., 200 kbps and 20 kb) to the low priority policer <b>530</b> and fail any packets that do not. High priority policer <b>520</b> may implement an appropriate bucket size, credit add rate, and proportional credit removal, as explained above with respect to <figref idref="DRAWINGS">FIG. 1</figref>. For example, its “bucket” may be a value in memory or a register that is adjusted upward and downward as appropriate. Failed premium packets may be dropped or marked as non-conforming, possibly in conjunction with other processing such as counting the number of such packets.

High priority policer <b>520</b> also may be configured to change (i.e., reset/toggle/clear) the NPI to a different value (e.g., logical “0”) for premium packets that it passes on to the low priority policer <b>530</b>.

Low priority policer <b>530</b> may be configured to perform “normal” token bucket-type policing on ordinary packets, based on their NPI value of 1. That is, low priority policer <b>530</b> may be configured to pass on any ordinary packets that conform to its bandwidth/burst rate requirements (e.g., 1 Mbps and 100 kb) and fail any ordinary packets that do not. Low priority policer <b>530</b> may implement an appropriate bucket size, credit add rate, and proportional credit removal, as explained above with respect to <figref idref="DRAWINGS">FIG. 1</figref>. Failed ordinary packets also may be dropped or marked as non-conforming, possibly in conjunction with other processing.

Low priority policer <b>530</b>, however, may be configured to “protect” premium packets from the high priority policer <b>520</b> based on their NPI value of 0. When the low priority policer <b>530</b> detects a “0” NPI bit, it may not perform “normal” policing. Rather, the low priority policer <b>530</b> may be configured to pass on the premium packets and remove an associated number of credits. In this manner, hierarchical policer <b>500</b> may ensure that the total traffic stays within bandwidth and burst size limits (e.g., 1 Mbps and 100 kb), while protecting premium packets by only dropping ordinary packets when these limits are exceeded.

Operation of Exemplary Policer

<figref idref="DRAWINGS">FIG. 6</figref> is a flow chart illustrating operation of hierarchical policer <b>500</b> consistent with the principles of the invention. To begin, sorter <b>510</b> may set one or more NPI bits (e.g., to “1”) in a received packet [act <b>610</b>]. Although <figref idref="DRAWINGS">FIG. 5</figref> only shows one NPI bit, if sorter <b>510</b> has more than two levels of service, additional NPI bits may be used. Alternately, a single NPI bit may be used if the sorter <b>510</b> has a sequentially cascading design. Sorter <b>510</b> may also determine whether the packet is premium (i.e., high priority) or ordinary (i.e., low priority) and send it to an appropriate policer <b>520</b>/<b>530</b> [act <b>620</b>].

If the packet is associated with a premium level of service, the high priority policer <b>520</b> may determine whether sufficient credit exists in its bucket to pass the packet [act <b>630</b>]. If not, high priority policer <b>520</b> may drop the premium packet, because it exceeded the premium bandwidth and/or burst size constraints [act <b>640</b>]. High priority policer <b>520</b> may also collect counts or other statistics on the dropped (or otherwise failed) packets.

If sufficient credit exists in the bucket of high priority policer <b>520</b>, credit proportional to the size of the premium packet may be removed, the NPI bit(s) may be changed (e.g., from “1” to “0”), and the premium packet may be passed to low priority policer <b>530</b> [act <b>650</b>].

Low priority policer <b>530</b> may check the state of the NPI bit(s) of an incoming packet to determine whether to perform normal policing or not [act <b>660</b>]. If the NPI bit(s) are set (i.e., the packet is an ordinary packet), low priority policer <b>530</b> may begin normal policing and determine whether sufficient credit exists in its bucket to pass the packet [act <b>670</b>]. If sufficient credit does not exist, low priority policer <b>530</b> may drop the packet, because it exceeded the total bandwidth and/or burst size constraints [act <b>640</b>].

If sufficient credit exists for the packet with the set NPI bit(s), the low priority policer <b>530</b> may remove a proportional amount of credit from its bucket, and pass the packet to another element for further processing [act <b>680</b>]. Because act <b>670</b> determined that sufficient credit was present, the bucket in the low priority policer <b>530</b> may be left with zero or more credits after the packet is passed on.

If the NPI bit(s) are determined not to be set (e.g., have a value of “0”) in act <b>660</b> (i.e., the packet is a premium packet in the example of <figref idref="DRAWINGS">FIG. 5</figref>), the low priority policer <b>530</b> still may remove a proportional amount of credit from its bucket, and pass the premium packet to another element for further processing [act <b>680</b>]. Because act <b>670</b> is not performed for such packets with NPI=0, the low priority policer <b>530</b> does not really “police” such packets, and its operation is “modified” for the packets with NPI=0. In other words, if the packet has already been passed by a policer (e.g., <b>520</b>), a subsequent policer may update the credit but not mark or drop the packet. In such a case, the bucket in the low priority policer <b>530</b> may start with zero or a small number of credits because credits may not have been added since removal due to a previous packet), and the premium packet may cause the credits in the bucket of the low priority policer <b>530</b> to “go negative” (e.g., become a negative number).

With a “negative” number of credits, the low priority policer <b>530</b> will drop ordinary packets, but not premium packets, until its number of credits is sufficiently replenished. One alternative to using a negative value is to relax the maximum burst size (i.e., increase the bucket size) when NPI=0. For example, a maximum burst of 120 kb may be allowed when the packet is a premium packet. Another alternative to using a negative value would be to tighten the maximum burst size (i.e., decrease the bucket size) when NPI=0. For example, a maximum burst of 80 kb may be allowed when the packet is an ordinary packet. Either of these two schemes would allow a 20 kb premium packet to immediately follow a large ordinary packet without incurring a negative credit.

Note that the high priority policer <b>520</b> (or more generally an earlier policer than the last policer) may also check the NPI bit(s) to determine whether to perform normal policing in other implementations. In <figref idref="DRAWINGS">FIG. 5</figref>, however, there are no elements available before the high priority policer <b>520</b> to toggle the NPI bit(s) for premium packets, so the high priority policer <b>520</b> performs normal policing every time. If the NPI bit(s) are reset/modified (e.g., to “0”) in a packet by an earlier policer, however, all subsequent policers may perform “modified” processing on the packet, because the NPI bit(s), once reset, may remain so. Hence, the high priority policer <b>520</b> may be referred to more generically as an example of a “normal” policer, and the low priority policer <b>530</b> (and any subsequent policers) may be referred to more generically as an example of a “modified” policer which may perform normal policing or modified processing on a packet based on its NPI bit(s).

Software Implementation of Exemplary Policer

A hierarchical policer consistent with the principles of the invention may also be implemented via software, for example as a set of general instructions performed by a processor or one or more specific instructions performed by a special purpose processor. These instructions may be stored on a computer-readable medium, such as magnetic media, optical media, non-volatile memory (e.g., ROM), volatile memory (e.g., RAM), etc.

The overall policing described above may be performed using two exemplary software instructions, presented below in pseudo-code. The first, “normal policer” instruction is: normal policer (bucket):

<tables id="TABLE-US-00001" num="00001"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="21pt" align="left" /><colspec colname="1" colwidth="196pt" align="left" /><thead><row><entry /><entry namest="offset" nameend="1" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>if (credit_avail ≧ packet_length) then</entry></row><row><entry /><entry>    credit_avail = credit_avail − packet_length;</entry></row><row><entry /><entry>    pass;</entry></row><row><entry /><entry>else</entry></row><row><entry /><entry>fail.</entry></row><row><entry /><entry namest="offset" nameend="1" align="center" rowsep="1" /></row></tbody></tgroup></table></tables><br /> This normal policer instruction determines whether the length of a packet is greater than or equal to the credit available in a bucket (e.g., a number in a register). If so, the normal policer instruction subtracts credit proportional to the packet length from the credit available and passes the packet. If not, the normal policer instruction fails (e.g., drops) the packet. Although not explicitly shown, an associated “bucket” function may also track and update the credit available number according to predetermined service information (e.g., bandwidth and maximum burst size).

The second, “policer update” instruction is:

<tables id="TABLE-US-00002" num="00002"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="21pt" align="left" /><colspec colname="1" colwidth="196pt" align="left" /><thead><row><entry /><entry namest="offset" nameend="1" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>policer update (bucket):</entry></row><row><entry /><entry>    credit_avail = credit_avail − packet_length;</entry></row><row><entry /><entry>    pass.</entry></row><row><entry /><entry namest="offset" nameend="1" align="center" rowsep="1" /></row></tbody></tgroup></table></tables><br /> This policer update instruction determines subtracts credit proportional to the packet length from the credit available and passes the packet, regardless of the amount of credit available. As with the normal policer instruction, an associated “bucket” function may also track and update the credit available number according to predetermined service information (e.g., bandwidth and maximum burst size).

Using these two instructions, the policing described in <figref idref="DRAWINGS">FIGS. 5 and 6</figref> may be implemented in software as follows:

<tables id="TABLE-US-00003" num="00003"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="35pt" align="left" /><colspec colname="1" colwidth="182pt" align="left" /><thead><row><entry /><entry namest="offset" nameend="1" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>hierarchical policing ( ):</entry></row><row><entry /><entry>  if (packet = premium) then</entry></row><row><entry /><entry>    normal policer (high priority bucket);</entry></row><row><entry /><entry>    if (pass) then</entry></row><row><entry /><entry>    policer update (low priority bucket);</entry></row><row><entry /><entry>else</entry></row><row><entry /><entry>  normal policer (low priority bucket).</entry></row><row><entry /><entry namest="offset" nameend="1" align="center" rowsep="1" /></row></tbody></tgroup></table></tables><br /> As described in greater detail above, if the packet is a premium (e.g., high priority) packet, it may be processed with the normal policer instruction and the “high priority bucket” parameters. In the example herein, the high priority bucket parameters correspond to 200 kbps bandwidth and 20 kb maximum burst size.

If the premium packet passes (e.g., and has its NPI bit changed), it may be processed with the policer update instruction and the “low priority bucket” parameters. In the example herein, the low priority bucket parameters correspond to 1 Mbps bandwidth and 100 kb maximum burst size. The size of the premium packet may cause the credits available in the low priority bucket to be totally depleted or become negative. The low priority bucket function may track “negative” credits until the periodic addition of credits replenishes the credits in the low priority bucket.

If the packet is not a premium packet (i.e., it is ordinary or some lower service level), it may be processed with the normal policer instruction and the “low priority bucket” parameters. If there are insufficient credits for the ordinary packet (e.g., due to credit depletion by a premium packet), the ordinary packet may be failed (e.g., dropped) by the normal policer instruction.

Conclusion

As described above, a hierarchical policer may include multiple policers that either normally police traffic or pass the traffic without policing based on meta-data within units of the traffic. The meta-data data may be changed to affect subsequent processing of a unit of traffic after normal policing of that unit.

The foregoing description of preferred embodiments of the invention provides illustration and description, but is not intended to be exhaustive or to limit the invention to the precise form disclosed. Modifications and variations are possible in light of the above teachings or may be acquired from practice of the invention. Moreover, while a series of acts has been presented with respect to <figref idref="DRAWINGS">FIG. 6</figref>, the order of the acts may be different in other implementations consistent with principles of the invention. Additionally, lines with arrows are used in the figures to generally illustrate the flow of data. In practice, embodiments consistent with the principles of the invention may send data on these lines in both directions.

Further, it is specifically contemplated that the principles of the invention may be extended to hierarchical policers beyond the two-level policer described herein. Three or more levels of service may be implemented by a given configuration of policers, with some of the services sharing bandwidth and possibly other services not sharing bandwidth. Those skilled in the art will appreciate various parallel and serial configurations of policers (e.g., <b>520</b>, <b>530</b>) needed to implement differentiation between an arbitrary number of related service levels. Also, although token-bucket policers have been described, it is specifically envisioned that any other type of policer may be used in accordance with the principles of the invention.

Also, although traffic differentiation based bandwidth has been discussed, traffic policing may be performed using other characteristics of the traffic, such as various conforming flags, traffic origin, traffic protocol, etc. It should also be understood that within the bandwidth-limited example herein, the specific bandwidth and burst size numbers used are purely exemplary.

PFEs <b>210</b> may be implemented in hardware, software, or some combination thereof For example, various portions of PFEs <b>210</b> may be implemented in application-specific integrated circuits (ASICs). The ASICs may be configured to perform some processing via dedicated logic, and may also be configured to perform some processing using microcode instructions that may be stored in memory. Those skilled in the router art will appreciate that the invention described herein might be practiced using a variety of hardware configurations in addition to, or instead of, ASICs. For example, some combination of general purpose processors, digital signal processors (DSPs), and programmable gate arrays (PGAs) may also be utilized to implement the functionality described herein.

No element, act, or instruction used in the description of the present application should be construed as critical or essential to the invention unless explicitly described as such. Also, as used herein, the article “a” is intended to include one or more items. Where only one item is intended, the term “one” or similar language is used.

The scope of the invention is defined by the claims and their equivalents.