Hierarchical metering in a virtual router-based network switch

• US 8,848,718 B2
• Filed: 05/18/2009
• Issued: 09/30/2014
• Est. Priority Date: 06/04/2002
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Hussain, Zahid, Desai, Sachin, Alam, Naveed, Cheng, Joseph, Millet, Tim
• Primary Examiner(s): PHAN, MAN U
• Application Number:
  US12/467,609
• Publication Number:
  US 20090225759A1
• Time in Patent Office: 1,961 Days
• Field of Search: 370230-236, 370252-257, 370392-412, 370465-468, 709220-229
• US Class Current: 370/395.1
• 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 packet flow using a second MCB.

Claims

1. A method comprising:

storing, within a shared memory system a routing platform, a plurality of metering contexts, each of the plurality of metering contexts containing information regarding a status and a state of one or more packet flows of a plurality of packet flows;

applying, by a metering procedure operable within the routing platform, a first level of metering of a set of hierarchical levels of metering associated with a first packet flow of the plurality of packet flows to the first packet flow by comparing a packet rate of the first packet flow against a first set of traffic rate parameters established for the first packet flow and stored in a first metering context of the plurality of metering contexts;

applying, by the metering procedure, a next level of metering of the set of hierarchical levels of metering associated with the first packet flow to the first packet flow and a second packet flow of the plurality of packet flows by comparing packet rates of both the first packet flow and the second packet flow against a second set of traffic rate parameters established for the first packet flow and the second packet flow and stored in a second metering context of the plurality of metering contexts;

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

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

whereby a metering policy of the routing platform may allow packets at lower levels of the set of hierarchical levels of metering to exceed a predefined packet profile provided that a higher-level packet profile has not been exceeded.

2. The method of claim 1, further comprising

applying, by the metering procedure, a first level of metering of the set of hierarchical levels of metering associated with the second packet flow to the second packet flow by comparing a packet rate of the second packet flow against a third set of traffic rate parameters established for the second packet flow and stored in a third metering context of the plurality of metering contexts;

applying, by the metering procedure, a next level of metering of the set of hierarchical levels of metering associated with the second packet flow to the first packet flow and the second packet flow by comparing packet rates of both the first packet flow and the second packet flow against the second set of traffic rate parameters;

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

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

3. The method of claim 1, wherein the routing platform comprises a virtual routing platform in which a plurality of virtual router contexts are represented within the memory system, 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.

4. The method of claim 1, wherein traffic rate parameters of the first set of traffic rate parameters and the second set of traffic 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.

5. The method of claim 1, further comprising:

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

applying, by the metering procedure, 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.

6. A method comprising:

storing, within a shared memory system a routing platform, a plurality of metering contexts, each of the plurality of metering contexts containing information regarding a status and a state of one or more categories of packets of a plurality of categories of packets;

applying, by a metering procedure operable within the routing platform, a first level of metering of a set of hierarchical levels of metering associated with a first category of packets of the plurality of categories of packets to the first category of packets by comparing a packet rate of the first category of packets against a first set of traffic rate parameters established for the first category of packets and stored in a first metering context of the plurality of metering contexts;

applying, by the metering procedure, a next level of metering of the set of hierarchical levels of metering associated with the first category of packets to the first category of packets and a second category of packets of the plurality of categories of packets by comparing packet rates of both the first category of packets and the second category of packets against a second set of traffic rate parameters established for the first category of packets and the second category of packets and stored in a second metering context of the plurality of metering contexts;

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

refraining from dropping, by the routing platform, packets of the first category of packets when (i) the packet rate of the first category of packets exceeds the traffic rate parameter of the first set of traffic rate parameters, and (ii) the packet rates of the first category of packets and the second category of packets when combined together do not exceed the traffic rate parameter of the second set of rate parameters;

whereby a metering policy of the routing platform may allow packets at lower levels of the set of hierarchical levels of metering to exceed a predefined packet profile provided that a higher-level packet profile has not been exceeded.

7. The method of claim 6, further comprising:

applying, by the metering procedure, a first level of metering of the set of hierarchical levels of metering associated with the second category of packets to the second category of packets by comparing a packet rate of the second category of packets against a third set of traffic rate parameters established for the second category of packets and stored in a third metering context of the plurality of metering contexts;

applying, by the metering procedure, a next level of metering of the set of hierarchical levels of metering associated with the second category of packets to the first category of packets and the second category of packets by comparing packet rates of both the first category of packets and the second category of packets against the second set of traffic rate parameters;

selectively dropping, by the routing platform, packets of the second category of packets when (i) the packet rate of the second category of packets exceeds a traffic rate parameter of the third set of traffic rate parameters, and (ii) the packet rates of the first category of packets and the second category of packets when combined together exceed the traffic rate parameter of the second set of traffic rate parameters; and

refraining from dropping, by the routing platform, packets of the second category of packets when (i) the packet rate of the second category of packets exceeds the traffic rate parameter of the third set of traffic rate parameters, and (ii) the packet rates of the first category of packets and the second category of packets when combined together do not exceed the traffic rate parameter of the second set of rate parameters.

8. The method of claim 6, wherein the first category of packets comprises packets associated with a first packet flow, packets associated with a first group of packet flows, packets originated by or destined for a first communication device, packets originated by or destined for a first group of communication devices, packets associated with a first service or packets associated with a first group of services.

9. The method of claim 8, wherein the second category of packets comprises packets associated with a second packet flow, packets associated with a second group of packet flows, packets originated by or destined for a second communication device, packets originated by or destined for a second group of communication devices, packets associated with a second service or packets associated with a second group of services.

10. The method of claim 9, wherein the routing platform comprises a virtual routing platform in which a plurality of virtual router contexts are represented within the memory system, and wherein the first category of packets is associated with a first virtual router context of the plurality of virtual router contexts and the second category of packets is associated with a second virtual router context of the plurality of virtual router contexts.

11. The method of claim 7, wherein traffic rate parameters of the first set of traffic rate parameters and the second set of traffic 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 category of packets.

12. The method of claim 7, wherein the first category of packets comprises a first packet flow and the second category of packets comprises a second packet flow and wherein the method further comprises:

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

applying, by the metering procedure, 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. A non-transitory computer-readable storage medium tangibly embodying a set of instructions, which when executed by one or more processors of a routing platform, cause the one or more processors to perform a method for applying hierarchically metering to categories of packets, the method comprising:

storing, within a shared memory system the routing platform, a plurality of metering contexts, each of the plurality of metering contexts containing information regarding a status and a state of one or more categories of packets of a plurality of categories of packets;

applying a first level of metering of a set of hierarchical levels of metering associated with a first category of packets of the plurality of categories of packets to the first category of packets by comparing a packet rate of the first category of packets against a first set of traffic rate parameters established for the first category of packets and stored in a first metering context of the plurality of metering contexts;

applying a next level of metering of the set of hierarchical levels of metering associated with the first category of packets to the first category of packets and a second category of packets of the plurality of categories of packets by comparing packet rates of both the first category of packets and the second category of packets against a second set of traffic rate parameters established for the first category of packets and the second category of packets and stored in a second metering context of the plurality of metering contexts;

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

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

14. The computer-readable medium of claim 13, wherein the method further comprises:

applying, by the metering procedure, a first level of metering of the set of hierarchical levels of metering associated with the second category of packets to the second category of packets by comparing a packet rate of the second category of packets against a third set of traffic rate parameters established for the second category of packets and stored in a third metering context of the plurality of metering contexts;

applying, by the metering procedure, a next level of metering of the set of hierarchical levels of metering associated with the second category of packets to the first category of packets and the second category of packets by comparing packet rates of both the first category of packets and the second category of packets against the second set of traffic rate parameters;

selectively dropping, by the routing platform, packets of the second category of packets when (i) the packet rate of the second category of packets exceeds a traffic rate parameter of the third set of traffic rate parameters, and (ii) the packet rates of the first category of packets and the second category of packets when combined together exceed the traffic rate parameter of the second set of traffic rate parameters; and

refraining from dropping, by the routing platform, packets of the second category of packets when (i) the packet rate of the second category of packets exceeds the traffic rate parameter of the third set of traffic rate parameters, and (ii) the packet rates of the first category of packets and the second category of packets when combined together do not exceed the traffic rate parameter of the second set of rate parameters.

15. The computer-readable medium of claim 13, wherein the first category of packets comprises packets associated with a first packet flow, packets associated with a first group of packet flows, packets originated by or destined for a first communication device, packets originated by or destined for a first group of communication devices, packets associated with a first service or packets associated with a first group of services.

16. The computer-readable medium of claim 15, wherein the second category of packets comprises packets associated with a second packet flow, packets associated with a second group of packet flows, packets originated by or destined for a second communication device, packets originated by or destined for a second group of communication devices, packets associated with a second service or packets associated with a second group of services.

17. The computer-readable medium of claim 16, wherein the routing platform comprises a virtual routing platform in which a plurality of virtual router contexts are represented within the memory system, and wherein the first category of packets is associated with a first virtual router context of the plurality of virtual router contexts and the second category of packets is associated with a second virtual router context of the plurality of virtual router contexts.

18. The computer-readable medium of claim 14, wherein traffic rate parameters of the first set of traffic rate parameters and the second set of traffic 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 category of packets.

19. The computer-readable medium of claim 14, wherein the first category of packets comprises a first packet flow and the second category of packets comprises a second packet flow and wherein the method further comprises:

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

applying, by the metering procedure, 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.