Hierarchical multi-rate multi-precedence policer

• US 7,738,382 B2
• Filed: 12/21/2004
• Issued: 06/15/2010
• Est. Priority Date: 12/21/2004
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Bajaj, Sandeep, Charny, Anna, Le Faucheur, Francois
• Primary Examiner(s): Rao; Seema S
• Assistant Examiner(s): Wu; Jianye
• Application Number:
  US11/019,915
• Publication Number:
  US 20060133279A1
• Time in Patent Office: 2,002 Days
• Field of Search: 370/235, 370/235.1
• US Class Current: 370/235.1
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/20 Traffic policing
• CPC Class Codes: H04L 47/215 using token-bucket
• CPC Class Codes: H04L 47/2416 Real-time traffic
• CPC Class Codes: H04L 47/31 by tagging of packets, e.g. using discard eligibility [DE] bits
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames
• CPC Class Codes: H04L 47/41 by acting on aggregated flows or links

Abstract

A hierarchical multi-rate multi-precedence policer is disclosed. The policer discards packets based on assigned precedence levels. When traffic exceeds an available service rate, the policer drops packets of lower precedence levels to make room for packets of higher precedence levels. In certain implementations, the policer also guarantees bandwidth to each level, thus preventing complete loss of lower precedence traffic when there is a large amount of higher precedence traffic.

Claims

1. A method for operating a network device comprising a multi-rate multi-precedence policer, said method comprising:

providing a plurality of packet precedence levels;

providing a token bucket for each of said packet precedence levels;

receiving a packet comprising a precedence level;

determining a credit available in the token bucket associated with said received packet'"'"'s precedence level;

determining a policer operation for said received packet based on the token bucket associated with said received packet'"'"'s precedence level, wherein determining a policer operation comprises determining whether to keep, drop, or remark said received packet; and

upon receipt of said received packet having precedence j and length L, if token counts T(j)−

L>

=0, changing token counts T(k) for all k<

=j;

wherein said received packet affects traffic measured by said token bucket associated with said received packet'"'"'s precedence level and all token buckets associated with precedence levels below said received packet'"'"'s precedence level.

2. The method of claim 1 wherein each of said token buckets is programmed with a maximum allowed rate NesR(i) representing a maximum allowed rate of traffic aggregated over all the precedence levels above and including precedence level i and further programmed with a depth NesB(i), and token counts T(i) of said token buckets Bi are updated every INT seconds, DEF(i) is the number of tokens missing in said token bucket Bi to fill said token bucket Bi, MaxT(i)=NesR(i)*INT, and INC(i)=Min [Max T(i), DEF(i)];

and further comprising;

incrementing all the token counts T(i) by INC(i) every INT seconds; and

upon receipt of said received packet, said received packet having precedence j and length L, determining whether T(j)−

L>

0;

if T(j)−

L<

0, dropping said received packet;

if T(j)−

L>

=0 setting T(k)=T(k)−

L for all k<

=j.

3. The method of claim 1 wherein each of said token buckets is programmed with a maximum allowed rate NesR(i) representing a maximum allowed rate of traffic aggregated over all the precedence levels above and including precedence level i and further programmed with a depth NesB(i), and LastTime is a time of last update of said token buckets, CurrentTime is a current real time, DeltaTime is a difference between CurrentTime and LastTime, MaxT(i)=NesR(i)*DeltaTime, T(i) is a token count of bucket (i), DEF(i)=NesB(i)−

T(i), and INC(i)=Min [Max T(i), DEF(i)]; and

further comprising;

upon receipt of said received packet, said received packet having precedence j and length L performing the following;

setting T(k)=T(k)+INC(k) for all of said token buckets;

if T(j)−

L<

0, dropping said received packet;

if T(j)−

L>

=0 setting T(k)=T(k)−

L for all k<

=j.

4. A method for operating a network device comprising a multi-rate multi-precedence policer, said method comprising:

providing a plurality of packet precedence levels;

providing a token bucket for each of said packet precedence levels;

receiving a packet comprising a precedence level;

determining a credit available in the token bucket associated with said received packet'"'"'s precedence level;

determining a policer operation for said received packet based on the token bucket associated with said received packet'"'"'s precedence level, wherein determining a policer operation comprises determining whether to keep, drop, or remark said received packet; and

for each of the token buckets (i), starting with a highest precedence level and continuing to a lowest precedence level, setting DEF(i)=B(i)−

T(i), wherein DEF(i) is a number of tokens missing in the token bucket (i) to fill the token bucket, B(i) is a depth of the token bucket (i) corresponding to precedence level (i), and T(i) is a token counter for token bucket Bi;

wherein said received packet affects traffic measured by said token bucket associated with said received packet'"'"'s precedence level and all token buckets associated with precedence levels below said received packet'"'"'s precedence level.

5. The method of claim 4 wherein R(i) is a maximum allowed rate of traffic for precedence level (i), R is a maximum allowed aggregate rate across all precedence levels, INT is an update interval, RemT is a variable that tracks remaining tokens to be allocated across precedence levels in a given interval, MaxT(i)=R(i)×

INT, INC(i)=a number of tokens actually added to a token bucket (i) in a given interval, B(i) is the depth of the token bucket Bi;

and further comprising;

every interval INT,

initializing RemT=R*INT; and

for each token bucket i, starting from a highest precedence level and continuing to a lowest precedence level;

setting INC(i)=Min [DEF(i), MaxT(i), RemT];

T(i)=T(i)+INC(i); and

RemT=Max [RemT−

INC(i), 0].

6. The method of claim 5 further comprising:

upon receipt of said received packet, said received packet having precedence j and length L, determining whether T(j)−

L>

0;

if T(j)−

L<

0, dropping said received packet;

if T(j)−

L>

=0 setting T(j)=T(j)−

L.

7. The method of claim 4 wherein R(i) is a maximum allowed rate of traffic for precedence level (i), R is a maximum allowed aggregate rate across all precedence levels, LastTime is a time of last update of said token buckets, CurrentTime is a current real time, DeltaTime is a difference between CurrentTime and LastTime, MaxT(i)=R(i)*DeltaTime, RemT is a variable that tracks tokens to be allocated across precedence levels in a given interval;

and further comprising;

upon receipt of said received packet, said received packet having precedence j and length L,

determining whether T(j)−

L>

0;

setting RemT=R*DeltaTime;

for each of said token buckets, starting with a highest precedence level and continuing to a lowest precedence level;

setting INC(i)=Min [DEF(i), MaxT(i), RemT];

setting RemT=Max [RemT−

INC (i), 0];

setting LastTime=CurrentTime;

determining whether T(j)−

L>

0;

if T(j)−

L<

0, dropping said received packet;

if T(j)−

L>

=0 setting T(j)=T(j)−

L.

8. A method for operating a network device comprising a multi-rate multi-precedence policer, said method comprising:

providing a plurality of packet precedence levels;

providing a token bucket for each of said packet precedence levels;

receiving a packet comprising a precedence level;

determining a credit available in the token bucket associated with said received packet'"'"'s precedence level;

determining a policer operation for said received packet based on the token bucket associated with said received packet'"'"'s precedence level, wherein determining a policer operation comprises determining whether to keep, drop, or remark said received packet; and

wherein said received packet affects traffic measured by said token bucket associated with said received packet'"'"'s precedence level and all token buckets associated with precedence levels below said received packet'"'"'s precedence level; and

wherein R(i) is a maximum allowed rate of traffic for precedence level (i), r(i) is a guaranteed rate of traffic for precedence level (i), R is a maximum allowed aggregate rate across all precedence levels, and B(i) is a depth of token bucket (i) corresponding to precedence level (i).

9. The method of claim 8 wherein

wherein LastTime is a time of last update of said token buckets, CurrentTime is a current real time, and T(i) is a token counter for token bucket (i);

and further comprising;

upon receipt of said received packet, said received packet having precedence j and length L,

setting DeltaTime=CurrentTime−

LastTime;

setting RemT=R*DeltaTime;

for each of said token buckets, starting with a highest precedence level and continuing to a lowest precedence level,

setting DEF(i)=B(i)−

T(i);

setting MaxT(i)=R(i)*DeltaTime;

setting MinT(i)=r(i)*DeltaTime;

setting DiffT(i)=MaxT(i)−

MinT(i);

setting INC(i)=Min (DEF(i), MinT(i), RemT);

setting T(i)=T(i)+INC(i);

setting DEF(i)=B(i)−

T(i);

setting RemT=Max[RemT−

INC(i), 0];

for each of said token buckets, starting with a highest precedence level and continuing to a lowest precedence level,

setting INC(i)=Min (DEF(i), DiffT(i), RemT);

setting T(i)=T(i)+INC(i); and

setting RemT=Max [RemT−

INC(i), 0]; and

setting LastTime=CurrentTime; and

determining whether T(j)−

L>

0;

if T(j)−

L<

0, dropping said received packet; and

if T(j)−

L>

=0 setting T(j)=T(j)−

L.

10. The method of claim 8 wherein INT is an update interval, T(i) is a token counter for token bucket (i), RemT is a variable that tracks remaining tokens to be allocated across precedence levels in a given interval, Def(i) is a number of tokens missing in token bucket B(i) to fill the bucket, MaxT(i)=R(i)×

INT, MinT(i)=r(i)*INT, and INC(i)=a number of tokens actually added to a token bucket (i) in a given interval; and

further comprising;

every interval INT,

initializing RemT=R*INT; and

for each token bucket i, starting from a highest precedence level and continuing to a lowest precedence level;

setting DEF(i)=B(i)−

T(i);

setting DiffT(i)=MaxT(i)−

MinT(i);

setting INC(i)=Min (DEF(i), MinT(i), RemT);

setting T(i)=T(i)+INC(i);

setting DEF(i)=B(i)−

T(i); and

setting RemT=Max [RemT−

INC(i), 0];

for each token bucket i, starting from a highest precedence level and continuing to a lowest precedence level;

INC(i)=Min (DEF(i), DiffT(i), RemT)

T(i)=T(i)+INC(i); and

RemT=Max[RemT−

INC(i), 0].

11. The method of claim 10 further comprising:

upon receipt of said received packet, said received packet having precedence j and length L, determining whether T(j)−

L>

0;

if T(j)−

L<

0, dropping said received packet;

if T(j)−

L>

=0 setting T(j)=T(j)−

L.

12. A computer readable storage medium encoded with a computer program for operating a packet policer, said computer program comprising:

code that provides a token bucket corresponding to each of a plurality of packet precedence levels;

code that causes received traffic to be limited in accordance with rates corresponding to precedence levels to which packets of said received traffic are assigned;

code that causes received traffic to affect the token buckets associated with precedence levels below said precedence level to which packets of said received traffic are assigned such that credit in the token buckets associated with precedence levels below said received packet'"'"'s precedence level is available for use by said received packet; and

code that causes packets of the lowest possible precedence levels to be dropped or remarked to assure conformance to said rates.

13. The computer readable storage medium of claim 12 wherein said rates comprise a maximum rate R for each of said precedence levels.

14. The computer readable storage medium of claim 12 wherein said rates comprise a maximum rate R(i) for each precedence level (i).

15. The computer readable storage medium of claim 12 wherein said rates comprise a maximum rate R(i) and a guaranteed rate r(i) for each of said precedence levels.

16. The computer readable storage medium of claim 12 wherein said rates comprise a maximum rate NesR(i) representing a maximum allowed traffic over all precedence levels (i) and above.

17. The computer readable storage medium of claim 12 wherein said rates comprise a maximum rate NesR(i) representing a maximum allowed traffic over all precedence levels (i) and above and a guaranteed rate Nesr(i) representing a guaranteed rate over all precedence levels (i) and above.

18. A method of operating a network, said method comprising:

assigning a plurality of calls to a plurality of precedence levels such that packets belong to a call are assigned a corresponding precedence levels, wherein a token bucket corresponds to each of said packet precedence levels;

operating a policer to police traffic generated by said calls by;

limiting said received traffic in accordance with rates corresponding to said precedence levels; and

dropping or remarking packets of the lowest possible precedence levels to assure conformance to said rates;

wherein received traffic affects the token buckets associated with precedence levels below said precedence level to which packets of said received traffic are assigned such that credit in the token buckets associated with precedence levels below said received packet'"'"'s precedence level is available for use by said received packet.

19. The method of claim 18 wherein said rates comprise a maximum rate R for each of said precedence levels.

20. The method of claim 18 wherein said rates comprise a maximum rate R(i) for each precedence level (i).

21. The method of claim 18 wherein said rates comprise a maximum rate R(i) and a guaranteed rate r(i) for each of said precedence levels.

22. The method of claim 18 wherein said rates comprise a maximum rate NesR(i) representing a maximum allowed traffic over all precedence levels (i) and above.

23. The method of claim 18 wherein said rates comprise a maximum rate NesR(i) representing a maximum allowed traffic over all precedence levels (i) and above and a guaranteed rate Nesr(i) representing a guaranteed rate over all precedence levels (i) and above.

24. Apparatus for operating a packet policer, said apparatus comprising:

a processor;

a memory device that stores;

code that provides a token bucket corresponding to each of a plurality of packet precedence levels;

code that causes received traffic to be limited in accordance with rates corresponding to said precedence levels to which packets of said received traffic have been assigned;

code that causes received traffic to affect the token buckets associated with precedence levels below said precedence level to which packets of said received traffic are assigned such that credit in the token buckets associated with precedence levels below said received packet'"'"'s precedence level is available for use by said received packet; and

code that causes packets of the lowest possible precedence levels to be dropped or remarked to assure conformance to said rates.

25. The apparatus of claim 24 wherein said rates comprise a maximum rate R for each of said precedence levels.

26. The apparatus of claim 24 wherein said rates comprise a maximum rate R(i) for each precedence level (i).

27. The apparatus of claim 24 wherein said rates comprise a maximum rate R(i) and a guaranteed rate r(i) for each of said precedence levels.

28. The apparatus of claim 24 wherein said rates comprise a maximum rate NesR(i) representing a maximum allowed traffic over all precedence levels (i) and above.

29. The apparatus of claim 24 wherein said rates comprise a maximum rate NesR(i) representing a maximum allowed traffic over all precedence levels (i) and above and a guaranteed rate Nesr(i) representing a guaranteed rate over all precedence levels (i) and above.