Hierarchical metering in a virtual router-based network switch

• US 7,668,087 B2
• Filed: 01/08/2007
• Issued: 02/23/2010
• Est. Priority Date: 06/04/2002
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Fortinet Inc.
• Inventors: Cheng, Joseph, Desai, Sachin, Hussain, Zahid, Millet, Tim, Alam, Naveed
• Primary Examiner(s): PHAN, MAN U
• Application Number:
  US11/621,102
• Publication Number:
  US 20070109968A1
• Time in Patent Office: 1,142 Days
• Field of Search: 370230-236, 370252-255, 370392-468, 709220-225
• US Class Current: 370/230
• CPC Class Codes: H04L 43/026 using flow identification
• CPC Class Codes: H04L 43/0829 Packet loss
• CPC Class Codes: H04L 43/0894 Packet rate
• CPC Class Codes: H04L 45/586 of virtual routers
• CPC Class Codes: H04L 45/60 Router architectures
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/11 Identifying congestion

Abstract

Methods and systems are provided for applying metering and rate-limiting in a virtual router environment and supporting a hierarchy of metering/rate-limiting contexts per packet flow. According to one embodiment, multiple first level metering options and multiple second level metering options associated with a hierarchy of metering levels are provided. A virtual routing engine receives packets associated with a first packet flow and packets associated with a second packet flow. The virtual routing engine performs a first type of metering of the first level metering options on the packets associated with the first packet flow using a first metering control block (MCB) and performs a second type of metering of the second level metering options on the packets associated with the first packet flow and the packets associated with the second flow using a second MCB.

Claims

1. A method comprising:

providing a plurality of first level metering options and a plurality of second level metering options associated with a hierarchy of metering levels;

receiving, by a virtual routing engine of a virtual routing platform, packets associated with a first packet flow and packets associated with a second packet flow;

the virtual routing engine performing a first type of metering from the plurality of first level metering options on the packets associated with the first packet flow using a first metering control block (MCB);

the virtual routing engine performing a second type of metering from the plurality of second level metering options on the packets associated with the first packet flow and the packets associated with the second packet flow using a second MCB;

measuring a packet rate of the first packet flow against a first set of rate parameters established for the first packet flow and stored in the first MCB;

marking packets of the first packet flow in accordance with a result of the measuring;

measuring packet rates of both the first packet flow and the second packet flow against a second set of rate parameters established for the first packet flow and the second packet flow and stored in the second MCB;

selectively dropping packets of the first packet flow when (i) the packet rate of the first packet flow exceeds a parameter of the first set of rate parameters, and (ii) the packet rates of the first packet flow and the second packet flow when combined together exceed a parameter of the second set of rate parameters; and

refraining from dropping packets of the first packet flow when (i) the packet rate of the first packet flow exceeds the parameter of the first set of rate parameters, and (ii) the packet rates of the first packet flow and the second packet flow when combined together do not exceed a parameter of the second set of rate parameters.

2. The method of claim 1, wherein parameters of the first set of rate parameters and the second set of rate parameters include at least one of either a peak information rate (PIR) parameter or a committed information rate (CIR) parameter established for the associated packet flow, and wherein measuring comprises removing tokens from a token bucket established based on the measured packet rate, the token bucket having a size based on one of either the PIR or CIR for the associated packet flow.

3. The method of claim 1, further comprising:

identifying the packets associated with the first packet flow, the first packet flow having the first MCB associated therewith stored in a cache memory; and

placing a cache-lock on the first MCB prior to performing the first type of metering.

4. The method of claim 3, wherein the first MCB and the second MCBs comprise data structures stored in a shared memory of the virtual routing engine, and where the method further comprises placing a cache-lock on the second MCB prior to performing the second type of metering of the packets associated with either the first packet flow or the second packet flow using the second MCB.

5. The method of claim 4, further comprising:

releasing the cache-lock on the first MCB after performing the first type of metering on the packets associated with the first packet flow using the first MCB; and

releasing the cache-lock on the second MCB after performing the second type of metering on either the packets associated with the first packet flow or the packets associated with the second packet flow using the second MCB.

6. The method of claim 1, further comprising performing a third type of metering from the plurality of first level metering options on the packets associated with the second packet flow using a third MCB prior to performing the second type of metering on the packets associated with the second packet flow.

7. The method of claim 6, further comprising placing a cache-lock on the third MCB prior to performing the third type of metering on the packets associated with the second packet flow using the third MCB.

8. The method of claim 3, wherein placing the cache-lock on the first MCB comprises setting a clock-bit of a first cache line index in a cache tag store, the first cache line index identifying the first MCB in the cache memory.

9. The method of claim 6, wherein the virtual routing engine comprises a multiprocessor system utilizing a shared memory, and wherein a first processor performs the first type of metering on the packets associated with the first packet flow and a second processor performs the third type of metering on the packets associated with the second packet flow, and wherein the first MCB and the third MCB are stored in a memory shared by the first processor and the second processor.

10. The method of claim 9, wherein the virtual routing engine is shared by a plurality of virtual router contexts running in a memory system of a central processing unit (CPU) of the virtual routing engine, and wherein the first packet flow is associated with a first virtual router context of the plurality of virtual router contexts and the second packet flow is associated with a second virtual router context of the plurality of virtual router contexts.

11. The method of claim 10, wherein the first type of metering for the packets associated with the first packet flow is performed concurrently with the third type of metering for the packets of the second packet flow as part of a parallel processing operation.

12. The method of claim 1, further comprising:

identifying packets associated with the first packet flow and the second packet flow that support a service;

performing a third level of metering on packets identified as supporting the service, wherein the service comprises one or more of Internet Protocol (IP) security (IPSec) packets, access control list (ACL) packets, video packets, Voice over IP (VoIP) packets and multicast packets.

13. The method of claim 1, further comprising identifying packets associated with the first packet flow by performing a hash on a received packet to determine an index corresponding with a flow classification block for the first packet flow.

14. A method comprising:

receiving, by a virtual routing engine of a virtual routing platform, packets of a first packet flow and packets of a second packet flow;

the virtual routing engine performing a plurality of metering functions associated with a hierarchy of metering levels on the first packet flow and the second packet flow by

performing a first level of metering on the packets of the first packet flow;

performing a different first level of metering on the packets of the second packet flow; and

performing a second level of metering for packets of the first and second packet flows, the second level of metering applying to both the first and second packet flows;

wherein the first level of metering includes applying a first set of individual level traffic parameters for the first packet flow to determine when the first packet flow exceeds a first profile;

wherein the different first level of metering includes applying a second set of individual level traffic parameters for the second packet flow to determine when the second packet flow exceeds a second profile;

wherein the second level of metering includes applying a set of group level traffic parameters for at least both the first and second packet flows to determine when the first and second packet flows together exceed a group profile;

wherein the individual level traffic parameters of the first and second sets and the group level traffic parameters are comprised of a peak information rate (PIR) and a committed information rate (CIR);

dropping packets of the first packet flow by the virtual routing engine when one or more of the individual level traffic parameters of the first set is exceeded and when one or more of the group level traffic parameters is exceeded;

dropping packets of the second packet flow by the virtual routing engine when one or more of the individual level traffic parameters of the second set is exceeded and when one or more of the group level traffic parameters is exceeded; and

refraining from dropping packets of the first and second packet flows by the virtual routing engine when none of the group level traffic parameters are exceeded.

15. The method of claim 14, further comprising:

identifying the first and second packet flows for received packets;

performing ingress metering on the packets based on a virtual interface from where the packets are received;

transforming a header of the packets; and

performing egress metering on the packets subsequent to transforming the header, wherein the egress metering comprises performing the first and second levels of metering.

16. The method of claim 14, further comprising refraining from dropping packets of the first and second packet flows when bandwidth of an external network is available.

17. The method of claim 14, wherein:

applying the first set of individual level traffic parameters includes marking a field in a packet header of packets of the first packet flow to indicate whether either a peak information rate (PIR) or a committed information rate (CIR) associated with the first profile is exceeded,

applying the second set of individual level traffic parameters includes marking a field in a packet header of packets of the second packet flow to indicate whether either the PIR or CIR for the second profile is exceeded, and

applying the group level traffic parameters includes marking a field in a packet header of packets of the first and second packet flows to indicate whether either the PIR or CIR for the group profile is exceeded.

18. The method of claim 17, wherein a packet of the first packet flow has a first number of bytes, and wherein applying the first set of individual level traffic parameters includes subtracting the first number of bytes from a token bucket maintained for the first packet flow,

wherein a packet of the second packet flow has a second number of bytes, and wherein applying the second set of individual level traffic parameters includes subtracting the second number of bytes from a token bucket maintained for the second packet flow,

and wherein applying the group level traffic parameters includes subtracting a sum of the first and second number of bytes from a token bucket maintained for the group profile.

19. The method of claim 15, wherein identifying the first and second packet flows comprises performing a hash on a received packet to generate an index corresponding with a flow classification block (FCB), the FCB defining either the first or second packet flow for associated packets.

20. The method of claim 15, wherein the virtual routing engine comprises a multiprocessor system utilizing a shared memory, and wherein a first processor performs the first level of metering for the first flow and a second processor performs a first level of metering for the second packet flow, the first and second MCBs being stored in a memory shared by the first and second processors,

and wherein the virtual routing engine is shared by a plurality of virtual router contexts running in a memory system of a central processing unit (CPU) of the virtual routing engine, and wherein the first packet flow is associated with one virtual router context and the second packet flow is associated with a second virtual context, the first and second routing contexts being of a plurality of virtual router contexts resident in the virtual routing engine.

21. A method comprising:

receiving, by a virtual routing engine of a virtual routing platform, packets of a first packet flow and packets of a second packet flow;

the virtual routing engine performing a plurality of metering functions associated with a hierarchy of metering levels on the first packet flow and the second packet flow by

performing a first level of metering on the packets of the first packet flow;

performing a different first level of metering on the packets of the second packet flow; and

performing a second level of metering for packets of the first and second packet flows, the second level of metering applying to both the first and second packet flows;

wherein the first level of metering includes applying a first set of individual level traffic parameters for the first packet flow to determine when the first packet flow exceeds a first profile;

wherein the different first level of metering includes applying a second set of individual level traffic parameters for the second packet flow to determine when the second packet flow exceeds a second profile;

wherein the second level of metering includes applying a set of group level traffic parameters for at least both the first and second packet flows to determine when the first and second packet flows together exceed a group profile;

wherein applying the first set of individual level traffic parameters includes marking a field in a packet header of packets of the first packet flow to indicate whether either a peak information rate (PIR) or a committed information rate (CIR) associated with the first profile is exceeded;

wherein applying the second set of individual level traffic parameters includes marking a field in a packet header of packets of the second packet flow to indicate whether either the PIR or CIR for the second profile is exceeded; and

wherein applying the group level traffic parameters includes marking a field in a packet header of packets of the first and second packet flows to indicate whether either the PIR or CIR for the group profile is exceeded.

22. The method of claim 21, further comprising:

identifying the first and second packet flows for received packets;

performing ingress metering on the packets based on a virtual interface from where the packets are received;

transforming a header of the packets; and

performing egress metering on the packets subsequent to transforming the header, wherein the egress metering comprises performing the first and second levels of metering.

23. The method of claim 21, wherein the individual level traffic parameters of the first and second sets and the group level traffic parameters are comprised of a peak information rate (PIR) and a committed information rate (CIR).

24. The method of claim 23, further comprising:

dropping packets of the first packet flow when one or more of the individual level traffic parameters of the first set is exceeded and when one or more of the group level traffic parameters is exceeded;

dropping packets of the second packet flow when one or more of the individual level traffic parameters of the second set is exceeded and when one or more of the group level traffic parameters is exceeded; and

refraining from dropping packets of the first and second packet flows when none of the group level traffic parameters are exceeded.

25. The method of claim 24, further comprising refraining from dropping packets of the first and second packet flows when bandwidth of an external network is available.

26. The method of claim 21, wherein a packet of the first packet flow has a first number of bytes, and wherein applying the first set of individual level traffic parameters includes subtracting the first number of bytes from a token bucket maintained for the first packet flow,

wherein a packet of the second packet flow has a second number of bytes, and wherein applying the second set of individual level traffic parameters includes subtracting the second number of bytes from a token bucket maintained for the second packet flow,

and wherein applying the group level traffic parameters includes subtracting a sum of the first and second number of bytes from a token bucket maintained for the group profile.

27. The method of claim 22, wherein identifying the first and second packet flows comprises performing a hash on a received packet to generate an index corresponding with a flow classification block (FCB), the FCB defining either the first or second packet flow for associated packets.

28. The method of claim 22, wherein the virtual routing engine comprises a multiprocessor system utilizing a shared memory, and wherein a first processor performs the first level of metering for the first flow and a second processor performs a first level of metering for the second packet flow, the first and second MCBs being stored in a memory shared by the first and second processors,

and wherein the virtual routing engine is shared by a plurality of virtual router contexts running in a memory system of a central processing unit (CPU) of the virtual routing engine, and wherein the first packet flow is associated with one virtual router context and the second packet flow is associated with a second virtual context, the first and second routing contexts being of a plurality of virtual router contexts resident in the virtual routing engine.