System and method for hierarchical metering in a virtual router based network switch

• US 20030223361A1
• Filed: 06/04/2002
• Published: 12/04/2003
• Est. Priority Date: 06/04/2002
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Fortinet Inc.
• Inventors: Millet, Tim, Alam, Naveed, Hussain, Zahid, Cheng, Joseph, Desai, Sachin
• Granted Patent: US 7,161,904 B2
• Time in Patent Office: Days
• 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

A virtual routing platform includes a line interface a plurality of virtual routing engines (VREs) to identify packets of different packet flows and perform a hierarchy of metering including at least first and second levels of metering on the packet flows. A first level of metering may be performed on packets of a first packet flow using a first metering control block (MCB). The first level of metering may be one level of metering in a hierarchy of metering levels. A second level of metering on the packets of the first packet flow and packets of a second flow using a second MCB. The second level of metering may be another level of metering in the hierarchy. A cache-lock may be placed on the appropriate MCB prior to performing the level of metering. The first and second MCBs may be data structures stored in a shared memory of the virtual routing platform. The cache-lock may be released after performing the level of metering using the MCB. The cache-lock may comprise setting a lock-bit of a cache line index in a cache tag store, which may identify a MCB in the cache memory. The virtual routing platform may be a multiprocessor system utilizing a shared memory having a first and second processors to perform levels of metering in parallel. In one embodiment, a virtual routing engine may be shared by a plurality of virtual router contexts running in a memory system of a CPU of the virtual routing engine. In this embodiment, the first packet flow may be associated with one virtual router context and the second packet flow is associated with a second virtual router context. The first and second routing contexts may be of a plurality of virtual router contexts resident in the virtual routing engine.

Claims

1. A method of metering packet flows in a virtual routing engine comprising:

performing a first level of metering on packets of a first packet flow using a first metering control block (MCB), the first level of metering being one level of metering in a hierarchy of metering levels; and

performing a second level of metering on the packets of the first packet flow and packets of a second flow using a second MCB, the second level of metering being another level of metering in the hierarchy.

2. The method of claim 1 further comprising:

identifying packets of the first packet flow, the 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 level of metering.

3. The method of claim 2 wherein the first and second MCBs are 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 level of metering of packets of either the first or second flow using the second MCB.

4. The method of claim 3 further comprising:

releasing the cache-lock on the first MCB after performing the first level of metering on the first packet flow using the first MCB; and

releasing the cache lock on the second MCB after performing the second level of metering on either the first or second packet flows using the second MCB.

5. The method of claim 1 further comprising performing a first level of metering on packets of the second flow using a third MCB prior to performing the second level of metering on packets of the second packet flow, the third MCB being associated with the first level of metering in the hierarchy.

6. The method of claim 5 further comprising placing a cache-lock on the third MCB prior to performing the first level of metering on the packets of the second flow using the third MCB.

7. The method of claim 6 further comprising:

retrieving the first MCB from memory prior to placing the cache lock on the first MCB;

retrieving the second MCB from memory prior to placing the cache lock on the second MCB;

retrieving the third MCB from memory prior to placing the cache lock on the third MCB; and

releasing the cache lock on the third MCB after performing the first level of metering on packets of the second packet flow using the third MCB.

8. The method of claim 2 wherein placing the cache-lock on the first MCB comprises setting a lock-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 1 wherein the virtual routing engine is 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 flow, the first and second MCBs being stored in a memory shared by the first and second processors.

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 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 router context, the first and second routing contexts being of a plurality of virtual router contexts resident in the virtual routing engine.

11. The method of claim 10 wherein the first level of metering for the first flow is performed concurrently with the first level of metering for the second flow as part of a parallel processing operation.

12. The method of claim 1 wherein performing the first level of metering comprises:

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; and

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

and wherein performing the second level of metering comprises;

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

dropping packets of both the first and second packet flows when packets of the first or second packet flows together exceed at least one of the parameters of the second set; and

refraining from dropping packets of the first packet flow when packets of the first flow exceed rate parameters of the first set and when packets of the first or second packet flows together do not exceed the at least one of the parameters of the second set.

13. The method of claim 12 wherein the rate parameters of the first and second set include at least one of either a peak information rate (PIR) or a committed information rate (CIR) 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.

14. The method of claim 1 further comprising:

identifying packets of the first and second packet flows that support a service;

performing a third level of metering on packets identified as supporting the service, wherein the service is comprised one of either IP security (IPSec) packets, ACL packets, or a video packets.

15. The method of claim 1 further comprising identifying packets of 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.

16. A virtual routing engine comprising:

a plurality of multiprocessor systems;

a line interface to receive packets of a plurality of packet flows; and

a switching fabric coupling the plurality of multiprocessor systems and the line interface, wherein

the line interface selects one of the multiprocessor systems for a first packet flow and directs packets through the switching fabric to the selected multiprocessor system,

the selected multiprocessor system performs a first level of metering on packets of the first packet flow using a first metering control block (MCB), the first level of metering being one level of metering in a hierarchy of metering levels, and performs a second level of metering on the packets of the first packet flow and packets of a second flow using a second MCB, the second level of metering being another level of metering in the hierarchy.

17. The virtual routing engine of claim 16 wherein the selected multiprocessor system performs a first level of metering on packets of the second flow using a third MCB prior to performing the second level of metering on packets of the second packet flow, the third MCB being associated with the first level of metering in the hierarchy.

18. The virtual routing engine of claim 17 wherein the first and second MCBs are data structures stored in a shared memory of the selected multiprocessor system, and wherein the selected multiprocessor system places a cache-lock on the first MCB prior to performing the first level of metering, places a cache-lock on the second MCB prior to performing the second level of metering of packets of either the first or second flow using the second MCB, releases the cache-lock on the first MCB after performing the first level of metering on the first packet flow using the first MCB, and releases the cache lock on the second MCB after performing the second level of metering on either the first or second packet flows using the second MCB.

19. The virtual routing engine of claim 17 wherein a first processor performs the first level of metering of the first packet flow and a second processor performs a first level of metering on the second packet flow, wherein the first level of metering for the first flow is performed concurrently with the first level of metering for the second flow as part of a parallel processing operation, and

wherein the virtual routing engine is shared by a plurality of virtual router contexts running in a memory system of a 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 router context, the first and second routing contexts being of a plurality of virtual router contexts resident in the virtual routing engine.

20. The virtual routing engine of claim 18 wherein the first level of metering comprises 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, and marking packets of the first packet flow in accordance with a result of the measuring,

and wherein performing the second level of metering comprises measuring packet rates of both the first and second packet flows against a second set of rate parameters established for the second level of metering and stored in the second MCB, dropping packets of both the first and second packet flows when packets of the first or second packet flows together exceed at least one of the parameters of the second set, and refraining from dropping packets of the first packet flow when packets of the first flow exceed rate parameters of the first set and when packets of the first or second packet flows together do not exceed the at least one of the parameters of the second set.

21. A method of metering packets in a virtual routing engine comprising:

performing a first level of metering for packets of a first packet flow;

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

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

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 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, and

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,

and 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.

24. The method of claim 23 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).

25. The method of claim 24 further comprising:

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

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

refraining from dropping packets of the first and second packet flows when the one of the group level traffic parameters is not exceeded.

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

27. The method of claim 23 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 PIR or CIR for 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.

28. The method of claim 27 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 include subtracting a sum of the first and second number of bytes from a token bucket maintained for the group profile.

29. 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.

30. The method of claim 22 wherein the virtual routing engine is 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 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 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 router context, the first and second routing contexts being of a plurality of virtual router contexts resident in the virtual routing engine.

31. A routing system comprising:

a line interface to receive packets of first and second packet flows;

a virtual routing engine (VRE) to perform metering on packets of the first and second packet flows, and to transform headers of the packets,

the VRE performing a first level of metering for packets of the first packet flow, a different first level of metering for packets of a second packet flow, and a second level of metering for packets of the first and second flows, the second level of metering applying to both the first and second packet flows.

32. The system of claim 31 wherein the VRE one of a plurality of VREs, and the routing system further comprises a switching fabric coupling the line interface and the plurality of VREs, the line interface identifying one of the VREs to process packets of the first packet flow based on a physical interface and virtual channel from which the packets of the first packet flow were received, the identified VRE to perform metering, and header transformation for packets of the first and second packet flows.

33. The system of claim 31 further comprising a hierarchy of metering control blocks to be utilized by the VRE in performing different levels of metering.

34. The system claim 32 wherein the virtual routing engine is 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 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 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 router context, the first and second routing contexts being of a plurality of virtual router contexts resident in the virtual routing engine.

35. The system of claim 34 wherein the VRE identifies the first and second packet flows for received packets, performs ingress metering on the packets based on a virtual interface from where the packets are received, transforms a header of the packets, and performs egress metering on the packets subsequent to transforming the header.

36. The system of claim 31 wherein for the first level of metering, the VRE applies a first set of individual level traffic parameters for the first packet flow to determine when the first packet flow exceeds a first profile, and

for the different first level of metering, the VRE applies a second set of individual level traffic parameters for the second packet flow to determine when the second packet flow exceeds a second profile,

and wherein for the second level of metering, the VRE applies 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.

37. The system of claim 36 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).

38. The system of claim 36 wherein the VRE drops packets of the first packet flow when one of the individual level traffic parameters of the first set is exceeded and when one of the group level traffic parameters is exceeded, drops packets of the second packet flow when one of the individual level traffic parameters of the second set is exceeded and when one of the group level traffic parameters is exceeded, and refrains from dropping packets of the first and second packet flows when the one of the group level traffic parameters is not exceeded.

39. The system of claim 38 wherein the VRE refrains from dropping packets of the first and second packet flows when bandwidth of an external network is available to support a rate of the first and second packet flows.

40. The system of claim 36 wherein:

the VRE marks a field in a packet header of packets of the first packet flow to indicate whether either a PIR or CIR for the first profile is exceeded,

the VRE marks 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

the VRE marks 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.

41. The system of claim 40 wherein a packet of the first packet flow has a first number of bytes, and wherein the VRE subtracts 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 the VRE subtracts the second number of bytes from a token bucket maintained for the second packet flow,

and wherein the VRE a sum of the first and second number of bytes from a token bucket maintained for the group profile.

42. The system of claim 41 wherein the VRE identifies the first and second packet flows by 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.

43. A computer readable medium having stored thereon instruction, that when executed by a computing platform, result in:

performing a first level of metering for packets of a first packet flow;

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

performing a second level of metering for packets of the first and second 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, and

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,

and 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.

44. The computer readable medium of claim 43 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), and wherein the instructions further result in:

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

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

refraining from dropping packets of the first and second packet flows when the one of the group level traffic parameters is not exceeded.