Determining whether to rate limit traffic

Some embodiments provide a method for a gateway datapath that executes on a gateway device to implement logical routers for a set of logical networks and process traffic between the logical networks and an external network. The method receives a data message at the gateway device. To process the data message, the method executes a set of processing stages that includes a processing stage for a particular logical router. As part of the processing stage for the particular logical router, the method (i) uses an access control list (ACL) table to determine whether the data message is subject to rate limiting controls defined for the particular logical router and (ii) only when the data message is subject to rate limiting controls, determines whether to allow the data message according to a rate limiting mechanism for the particular logical router.

BACKGROUND

Quality of service (QoS) mechanisms are important in datacenters, in order to guarantee contracted-for levels of performance. However, rate-limiting mechanisms are generally performed in hardware (e.g., at the network interface controller (NIC) level), which aggregates all tenants of a datacenter together. Traffic is typically tenant-independent at the hardware level, and therefore difficult to disaggregate. In addition, not necessarily all traffic should be rate limited. For instance, control traffic typically should not be subject to rate limiting.

BRIEF SUMMARY

Some embodiments provide a gateway datapath, executing on a gateway device, that manages quality of service (QoS) for multiple different logical networks (e.g., for different tenant logical networks). The gateway datapath implements logical routers for the different logical networks to process traffic between the logical networks and an external network. In some embodiments, upon receiving a data message (either from the external network or from one of the logical networks), the gateway datapath executes a set of processing stages to process (e.g., forward, drop, etc.) the data message. This set of processing stages may include multiple stages corresponding to different logical forwarding elements (such as logical switches and logical routers), including a stage for a specific logical router of the logical network with which the data message is associated. As part of the processing for the logical router, the gateway datapath (i) uses a table (e.g., an access control list (ACL) table) to determine whether the data message is subject to rate limiting controls defined for the logical router, and only if the data message is subject to such rate limiting controls, (ii) determines whether to allow the data message according to a rate limiting mechanism for the logical router.

In some embodiments, the logical router is associated with a particular tenant (e.g., the logical router is an ingress/egress point for the tenant logical network). In some such embodiments, the gateway datapath implements logical routers for numerous different tenant logical networks, and the gateway device stores ACL tables for at least a subset of these logical routers. This allows each tenant to configure specific rate limiting (e.g., quality of service (QoS)) policy for ingress and/or egress traffic. In some embodiments, each ACL table is a set of rules that each match on a set of header fields and specify (for data messages matching the rule) whether to perform rate limiting. In case a particular data message matches multiple rules in a single ACL table, the rules are ordered based on priority so that only the highest priority matched rule will be followed. The tenant network administrator can specify in some embodiments how to treat data messages that do not match any of the rules (e.g., always apply the rate limiting mechanism or never apply the rate limiting mechanism).

Rather than store a single ACL table for each logical router, some embodiments store multiple ACL tables. For instance, some embodiments use separate tables for ingress data messages and egress data messages to ensure that ingress data messages don't accidentally match rules meant for egress and vice versa. In addition, some embodiments use a fixed length data structure generated from data message header fields (as explained further below) for matching against the ACL table rules. Because different protocols may have different length header fields (e.g., IPv4 addresses compared to IPv6 addresses), some embodiments use different ACL tables for these different protocols. Thus, for example, a gateway device might store four ACL tables for a specific logical router (IPv4 ingress, IPv4 egress, IPv6 ingress, IPv6 egress).

As mentioned, to perform a lookup in the ACL table to determine whether to apply a rate limiting mechanism to a data message, some embodiments extract a particular set of header field values from the data message and match this (fixed-length) particular set of header field values against the rules. For instance, some embodiments use the transport layer protocol field (of the network layer header), source and destination network layer addresses (e.g., IPv4 or IPv6 addresses), source and destination transport layer ports, a type of service (ToS) value or differentiated services code point (DSCP) value, and a class of service (CoS) value.

Along with the extracted header field values, some embodiments include a presence bit for each header field that indicates whether the field is actually present in the data message. Certain fields (e.g., the ToS, DSCP, and/or CoS fields) may not be present in some data messages. Because some embodiments require a fixed-length set of header field values for the table lookup, a value is filled in for the non-present header field and this default value should not accidentally lead to a match against a rule requiring a specific value for that field. The use of a presence bit for each of the fields ensures that such an accidental match will not happen.

It should be noted that, in some embodiments, the entire set of processing stages is typically only performed for the first data message of a data message flow. The gateway datapath generates a flow cache entry based on this processing, and subsequent data messages match the flow cache entry rather than requiring the more resource-intensive set of processing stages. To ensure that the ACL table does not need to be looked up for each subsequent data message in the data message flow, all of the fields on which the ACL table matches are also incorporated into the flow cache entry (including at least some of the presence bits, in some embodiments). While the lookups to determine whether subsequent data messages of a flow are subject to rate limiting controls are handled by the flow cache entry, the actual application of the rate limiting mechanism is applied separately for each data message. Thus, for instance, a first data message in a flow might be allowed, but a later data message in the same flow could be dropped due to congestion.

In some embodiments, this rate limiting mechanism involves the application of a set of QoS data structures for the particular logical router, which is described in greater detail in U.S. Patent Publication 2021/0218677, which is incorporated herein by reference. The gateway datapath compares a size of the data message that is subject to rate limiting to a current token bucket value stored for the logical router. If the data message is smaller than the current token bucket value, then the data message is allowed. Some embodiments also enable the network administrator to configure the gateway device to modify the DSCP value for allowed data messages (e.g., in order to indicate that the data message is a high priority data message). Similarly, if the data message is larger than the current token bucket value, then some embodiments either drop the data message or modify the DSCP value of the data message to indicate that the data message is a low priority data message.

DETAILED DESCRIPTION

Some embodiments provide a gateway datapath, executing on a gateway device, that manages quality of service (QoS) for multiple different logical networks (e.g., for different tenant logical networks). The gateway datapath implements logical routers for the different logical networks to process traffic between the logical networks and an external network. In some embodiments, upon receiving a data message (either from the external network or from one of the logical networks), the gateway datapath executes a set of processing stages to process (e.g., forward, drop, etc.) the data message. This set of processing stages may include multiple stages corresponding to different logical forwarding elements (such as logical switches and logical routers), including a stage for a specific logical router of the logical network with which the data message is associated. As part of the processing for the logical router, the gateway datapath (i) uses a table (e.g., an access control list (ACL) table) to determine whether the data message is subject to rate limiting controls defined for the logical router, and only if the data message is subject to such rate limiting controls, (ii) determines whether to allow the data message according to a rate limiting mechanism for the logical router.

FIG.1conceptually illustrates a logical network architecture100with multiple logical routers. In some embodiments, a logical network is a conceptualization of a network (e.g., for a datacenter tenant) that is defined by a network administrator. Such logical networks may include logical forwarding elements (e.g., logical routers, logical switches) as well as various other logical network entities (e.g., firewalls, load balancers, etc.). In the physical network (e.g., a datacenter network), these logical networks are implemented by various physical forwarding elements (e.g., software forwarding elements such as virtual switches, hardware forwarding elements such as top-of-rack switches, etc.), such that data messages sent by logical network endpoints (e.g., virtual machines, containers, or other data compute nodes) are processed as though sent through a physical network with the structure of the logical network. This formulation allows for many logical networks to be implemented (e.g., as overlay networks) by the physical network elements. That is, a single software switch, software router, gateway datapath, etc. might implement many logical networks for many different tenants.

As shown, the logical network architecture100includes a tier-0(T0) logical router105that provides access to external networks. In addition, multiple tier-1 (T1) logical routers110-120connect to the T0 logical router105, and logical switches125-150each connect to one of these T1 logical routers110-120. In addition, various logical network endpoints such as virtual machines (VMs), containers, physical computing devices, or other data compute nodes (DCNs) may be attached to the logical switches.

In some embodiments, each T1 logical router is configured by a different datacenter tenant (e.g., via an application that only allows the tenant to manage their own logical network), while the T0 logical router is configured by a datacenter administrator (e.g., a cloud provider). Each of the tenants also configures the logical switches that connect to their respective T1 logical routers. In some embodiments, any number of T1 logical routers may be attached to a T0 logical router such as the T0 logical router105. In other embodiments, one tenant or other entity may configure multiple T1 logical routers to connect to the same T0 logical router (which may be configured by the same entity or a different entity). Some datacenters may have only a single T0 logical router to which all T1 logical routers implemented in the datacenter attach, whereas other datacenters may have numerous T0 logical routers. For instance, a large datacenter may want to use different T0 logical router policies for different tenants, or may have too many different tenants to attach all of the T1 logical routers to a single T0 logical router. Part of the routing table for a T0 logical router includes routes for all of the logical switch domains of its connected T1 logical routers, so attaching numerous T1 logical routers to a T0 logical router creates several routes for the routing table of the T0 logical router just based on the subnets attached to each of the T1 logical routers.

A network control system of some embodiments (e.g., a set of network controller applications and/or network management applications) is responsible for receiving the logical network configurations from the administrators, generating configuration data for allowing the various physical network elements to implement the logical networks, and distributing this data to these physical network elements. In some embodiments, the network control system receives configuration data for a logical router from a network administrator and defines multiple routing components for the logical router. For instance, some embodiments define a distributed routing component (DR) and one or more centralized routing components (also referred to as service routers, service routing components, or SRs), each of which has a separate routing table and separate set of interfaces. In addition, the network control system defines transit logical switches for logically switching data messages between the routing components in some embodiments, as well as between the T1 logical routers and the T0 logical routers.

For instance, the network control system of some embodiments would receive configuration data for the T1 logical router110and generate a DR and two SRs (one active and one standby). In addition, the network control system would generate a first transit logical switch to connect these routing components with each other and a second transit logical switch to connect the T1 logical router110to the T0 logical router105. Further discussion of the different routing components and transit logical switches can be found in U.S. Pat. No. 9,787,605, which is incorporated herein by reference.

The DRs and logical switches are implemented in a distributed manner in some embodiments. That is, a single DR or logical switch is implemented by many different physical forwarding elements. For instance, a virtual switch executing on a host computer that hosts a DCN connected to logical switch125might implement at least logical switches125and130as well as the DR for T1 logical router110(and the transit logical switch internal to the implementation of the T1 logical router).

Each SR, on the other hand, is implemented on a single physical computer in some embodiments. Such a physical computer might implement multiple SRs, as well as the various DRs and logical switches. For instance, some embodiments designate gateway devices for implementing the SRs of the TLRs, as well as the SRs of the PLRs. In some embodiments, these gateway devices implement a gateway datapath (e.g., using the data plane development kit (DPDK), a set of libraries and network interface controller (NIC) drivers for packet processing) that performs the data message processing for the SRs (as well as the distributed network entities of the logical networks).

FIG.2conceptually illustrates such a gateway device200that executes a gateway datapath205. The gateway datapath, in different embodiments, may execute in virtualization software of the gateway device200(e.g., if the gateway device is a host computer that also hosts various DCNs), as an application/daemon on a bare metal device, within a virtual machine, etc. As shown, various host computers210that host one or more logical network DCNs connect (through the physical network of the datacenter) to the gateway device200. These logical network DCNs exchange data traffic with each other (which may not require processing by the gateway datapath205) as well as with external endpoints.

Data traffic between the logical network DCNs and the external endpoints is transmitted through the gateway datapath205of the device200. In some embodiments, at least for the first packet of a data flow in each direction, the gateway datapath executes a multi-stage processing pipeline. This processing pipeline is described in further detail in U.S. Pat. No. 10,084,726, which is incorporated herein by reference. At each stage, the gateway datapath205of some embodiments reads configuration data for the stage and performs processing according to that configuration data (e.g., to determine how to switch and/or route a data message, to perform load balancing and/or network address translation, etc.).

As described in U.S. Pat. Nos. 9,787,605 and 10,084,726, which are incorporated by reference above, the packet processing pipeline is different for ingress and egress packet processing pipelines in some embodiments, as the physical forwarding elements implementing the logical networks perform first-hop processing. For egress packets (originating at the logical network DCNs and directed outside the logical network), a software forwarding element executing on the host computer that hosts the source DCN is the first-hop forwarding element. This software forwarding element would perform logical processing for the initial logical switch and the DR of the T1 logical router, before determining (based on processing for the transit logical switch of the T1 logical router) that (i) the data message is to be sent to the SR of the T1 logical router and (ii) that this requires transmission through the physical datacenter network to the gateway device200. As such,FIG.2illustrates that for an outgoing (egress) data message for tenant1, the processing at the gateway datapath205begins with the SR of the T1 logical router110. As part of this processing, the gateway datapath performs a lookup in an ACL table associated with the T1 logical router110to determine whether rate limiting controls apply to the data message (described in greater detail below) and, if rate limiting controls apply, also performs a QoS (rate limiting) operation. Assuming the data message is allowed (i.e., not dropped), the processing pipeline for this data message also includes stages for the DR and SR of the T0 logical router105(in addition to the transit logical switches between these routing components, which are not shown in the figure). In this description, the ACL lookup and rate limiting controls are applied at the T1 logical router level, but it should be understood that some embodiments also (or only) apply these operations at the T0 logical router.

For incoming messages, the gateway device200is the first-hop forwarding element, so the gateway datapath205performs more extensive logical processing. As shown, when the gateway datapath205receives a data message for tenant1, the processing pipeline includes stages for the SR and DR of the T0 logical router105as well as the SR and DR of the T1 logical router110(in addition to the three transit logical switches between these various routing components), then the logical switch125. As part of this processing for the SR of the T1 logical router, the gateway datapath performs a lookup in an ACL table associated with the T1 logical router110to determine whether rate limiting controls apply to the data message and, if rate limiting controls apply, also performs a QoS operation. A similar processing pipeline is executed by the gateway datapath205for incoming data messages for tenant2, except that the T1 logical router and logical switch stages use configuration data for T1 logical router115and logical switch135. In addition, as part of the processing for the SR of the T1 logical router, the gateway datapath performs a lookup in an ACL table associated with the T1 logical router115to determine whether rate limiting controls apply to the data message and, if rate limiting controls apply, also performs a QoS operation. In some embodiments, the gateway device stores multiple separate ACL tables for each logical router (e.g., separate tables for ingress and egress and/or for different protocols, such as IPv4 and IPv6).

It should be noted that in some other embodiments, there is no T0 logical router (i.e., the T1 logical routers connect directly to physical routers of the external network). In this case, the datapath uses other mechanisms (e.g., associating different T1 logical routers with different interfaces) to determine which T1 logical router configuration to use for processing incoming data messages. In yet other embodiments, the T0 logical router SR is implemented on a different gateway device. In this case, the T0 logical router DR processing stage is executed as part of the gateway datapath with the T1 logical router SR for egress data messages, but as part of the gateway datapath on the other device with the T0 logical router SR for ingress data messages. The use of different ACL tables for different logical routers is not dependent on whether or not a T0 logical router is part of the logical processing pipeline.

In addition, it should be noted that in some embodiments the T0 logical routers and T1 logical routers do not necessarily correspond to datacenter providers and tenants. In some embodiments, the T0 logical routers are a tier of logical routers that provide a direct connection to the external networks while the T1 logical routers are a tier of logical routers that are not allowed to directly connect to external networks, but which can provide services for data compute nodes that connect to sets of logical switches. In some such embodiments, the use of different ACL tables for determining whether to apply rate limiting controls for different logical routers is not dependent on whether or not these different logical routers actually correspond to different tenants.

The gateway device200of some embodiments includes a network interface controller (NIC) via which data messages are sent and received (e.g., a NIC connected to an external router), and a set of processing units such as one or more CPUs. Such a set of CPUs may have multiple cores for processing data messages, with data messages load balanced between the cores (e.g., using receive side scaling (RSS) or another load balancing technique). In some embodiments, the load balancing technique computes a hash value of various data message headers that are independent of the tenant logical router (e.g., both source and destination network addresses), such that data messages for one tenant logical network are distributed across all four of the cores as shown in the figure. Some such embodiments track the cores to which ingress data messages for various data flows are assigned, and assign egress data messages for corresponding data flows to the same core.

The gateway datapath, in some embodiments, executes multiple packet-processing threads, each of which executes on a different core of the CPU set of the gateway device.FIG.3conceptually illustrates the threads executed by a datapath daemon300of some embodiments. As mentioned, the gateway datapath is a daemon or other application that can execute in virtualization software of a host computer, on a bare-metal device, in a virtual machine, etc. This daemon300in some embodiments uses DPDK to provide accelerated data message processing using the NIC of the gateway device.

As shown inFIG.3, the datapath daemon300executes one packet-processing thread305-320for each core of the CPU set that is assigned for packet processing. In some embodiments, these are run-to-completion threads that can process data messages simultaneously (i.e., each of the cores can simultaneously process a separate data message). In addition, the datapath daemon300executes other threads325(e.g., a QoS thread that handles QoS data structures for the various logical routers, as well as threads for other purposes such as BFD, MAC learning, etc.). In some embodiments, these other threads are scheduled among the cores of the CPU that are not assigned for packet processing.

As mentioned, the gateway device of some embodiments stores separate ACL tables (or other types of match tables) for each of at least a subset of the logical routers implemented by the gateway datapath. This allows each tenant (or other entity that configures the logical router) to configure specific rate limiting policy for ingress and/or egress traffic. In some embodiments, each ACL table is a set of rules that each match on a set of header fields and specify (for data messages matching the rule) whether to perform rate limiting. In case a particular data message matches multiple rules in a single ACL table, the rules are ordered based on priority so that only the highest priority matched rule will be followed. The network administrator can specify in some embodiments how to treat data messages that do not match any of the rules (e.g., always apply the rate limiting mechanism or never apply the rate limiting mechanism).

Rather than store a single ACL table for each logical router, some embodiments store multiple ACL tables.FIG.4conceptually illustrates the ACL tables400stored for a logical router (LR1) of some embodiments. In this example, the ACL tables400include an IPv4 ingress ACL table405, an IPv4 egress ACL table410, an IPv6 ingress ACL table415, and an IPv6 egress ACL table420. Some embodiments use separate tables for ingress data messages and egress data messages (e.g., tables405and410) to ensure that ingress data messages do not accidentally match rules meant for egress and vice versa. For example, the network administrator might want to treat data messages with a particular DSCP value differently on ingress and egress, and if only one ACL table was used then a match on just this DSCP value would not differentiate between ingress data messages and egress data messages.

In addition, some embodiments store (or instantiate in memory) multiple copies of each ACL table (e.g., multiple memory allocations), so that different threads executing on different cores can access different copies. Other embodiments store (or instantiate in memory) a single copy (e.g., a single memory allocation) for each ACL table. The ACL tables are instantiated in memory as a set of multi-bit tries in some embodiments. Some embodiments split the rules of a table into several non-intersecting subsets when possible and construct a separate trie for each of these subsets so as to reduce the required memory (at the cost of increasing the time required to find a match while processing a data message).

Some embodiments use a fixed length data structure generated from data message header fields, as explained in greater detail below by reference toFIG.6, for matching against the ACL table rules. Because different protocols may have different length header fields (e.g., IPv4 addresses compared to IPv6 addresses), some embodiments use different ACL tables for these different protocols (e.g., the ingress ACL tables405and415). Thus, in this example, the gateway device stores four ACL tables405-420for a single logical router (IPv4 ingress, IPv4 egress, IPv6 ingress, IPv6 egress).

FIG.5conceptually illustrates a process500of some embodiments for processing a data message at a gateway. The process500is performed by the gateway datapath (e.g., the datapath daemon300) in some embodiments upon receipt of a data message. Specifically, in some embodiments, much of the process (once a data message has been assigned to a core) is performed by one of the packet processing threads of the gateway datapath. The process500will be described in part by reference toFIGS.6-8, which illustrate the generation of ACL match table keys for different data messages as well as an example ACL table.

As shown, the process500begins by receiving (at505) a data message at the gateway. This data message may be an ingress data message (e.g., received from an external network) for which the gateway is the first hop for logical network processing or an egress data message (e.g., received from a host computer at which the source logical network endpoint for the data message operates) for which the gateway is not the first hop for logical network processing.

Next, the process500assigns (at510) the data message to one of the cores of the gateway device. As mentioned, this operation may use a hash-based load balancing technique such as receive side scaling (RSS) that distributes data messages across the different cores. Such techniques may assign different data messages belonging to the same logical network (and thus that will be processed by the same logical router) to different cores (while consistently assigning data messages belonging to the same data flow to the same core).

Once the data message has been assigned to a core, in some embodiments the datapath thread for that core performs the remainder of the process500. In some embodiments, the data message is assigned to a queue associated with that core, and thus there may be a short latency while earlier data messages in the queue are processed, before the process500continues for the data message.

As shown, the process500performs (at515) logical processing to identify a centralized routing component of a logical router (e.g., a T1 logical router) as the next stage of the processing pipeline for the data message. This processing may involve one or more stages of processing depending on (i) the direction of the data message (ingress or egress) and (ii) the architecture of the logical network to which the data message belongs. For example, this logical processing might involve various logical switches, other logical routers (e.g., multiple components of a T0 logical router, a distributed routing component of the same T1 logical router), distributed firewall, NAT, and/or load balancing.

Next, the process500performs processing for the centralized routing component of the logical router as the next stage of the processing pipeline for the data message. As part of this processing, the process500extracts (at520) header fields and presence bits for the appropriate ACL table lookup. As mentioned, the datapath performs a lookup into one of several ACL tables in some embodiments, with the gateway device storing separate tables for ingress and egress ACL and for different protocols with different address lengths (e.g., IPv4 and IPv6).

As mentioned, to perform a lookup in the ACL table to determine whether to apply a rate limiting mechanism to a data message, some embodiments extract a particular set of header field values from the data message and match this (fixed-length) particular set of header field values against the rules.FIG.6conceptually illustrates the extraction of such a set of header values into an ACL match key from a data message600. As shown, the data message600includes a payload and a set of header fields that are populated with values. Not all of the header fields are shown here, with the figure only highlighting the values that are used for the ACL match key of some embodiments. In addition, it should be noted that the size of the various data message fields is not shown to scale. In this example, the datapath extracts the header field values of seven different fields from the data message600to generate the ACL match key605. As shown here, in some embodiments these fields are (from the layer 2 VLAN header, if present) the class of service (CoS) field, (from the layer 3 header) the differentiated services code point (DSCP) field, the transport layer protocol field, and the source and destination network layer addresses, and (from the layer 4 header), the source and destination transport layer ports. Some embodiments extract the type of service (ToS) field value rather than the DSCP field value for data messages that use the ToS field rather than the DSCP field.

In some embodiments, the ACL match key605is a fixed-length buffer or other data structure. However, certain fields (e.g., the ToS, DSCP, and/or CoS fields) may not be present in some of the data messages. For instance,FIG.7illustrates a data message700that has all of the same layer 3 and layer 4 fields as the data message600, but does not include a ToS field (e.g., because there is no VLAN header present). However, when generating the ACL match key705, a value still needs to be filled in for this field so that the ACL match key705is the appropriate length, so some embodiments use a default value in the match key. As described below, an ACL rule might match on a value or range of values that includes this default value, but a data message that does not actually have the field should not necessarily match such a rule. Accordingly, when generating the ACL match key, the gateway datapath of some embodiments includes a presence bit for each header field that indicates whether the field is actually present in the data message. The use of these presence bits in the ACL match key and the ACL table rules ensures that an accidental match will not occur as a result of the default value.

After extracting the header fields, the process500performs (at525) a lookup on the appropriate ACL table associated with the logical router using the extracted set of header fields. The appropriate ACL table, as noted above, is the ACL table with rules for the direction of the data message (ingress or egress) as well as for the correct network layer protocol (e.g., IPv4 or IPv6).

FIG.8conceptually illustrates an ACL table800of some embodiments with several rules. Each of these rules includes a set of match conditions as well as an action specifying whether or not data messages matching the rule are subject to rate limiting controls. The match conditions include, for each field (in this case, the same seven fields mentioned above), either a specific value, a range of values, or a wildcard (i.e., any value satisfies the rule, represented in the figure by “**”). In addition, the match conditions include a set of presence bits specifying whether each header field is required. When a specific header field is required for a rule (e.g., indicated by a “1” in the presence bit), only data messages that include that header field can match that rule. On the other hand, when a specific header field is not required for a rule (e.g., indicated by a “0” in the presence bit), data messages can match that rule irrespective of whether they include the specific header field. Typically, if a field is wildcarded in a rule, then the presence of the field is not required. Some embodiments, however, allow for rules such as the fourth rule shown in the ACL table800, which requires data messages to carry a DSCP field in order to match the rule (the second presence bit is ‘1’) but does not care what value is carried in that field. Other embodiments always set the presence bit for any wildcard field in the match conditions to ‘0’; in such embodiments, an administrator can require the presence of the field but any value in that field by matching on a range for the field that encompasses the entire possible range of values for the field.

The rules in the ACL table are arranged in priority order. A data message might satisfy the match conditions of more than one rule, but only the highest priority matched rule will govern whether or not the data message is subject to rate limiting controls. For instance, any data message between IP_A and IP_B (which could be specific individual addresses or ranges of addresses) with a destination TCP port of179and DSCP value of 0 satisfies the match conditions of both the second and fourth rules. However, a lookup for such a data message would match the higher-priority second rule, indicating that the data message is not subject to rate limiting controls. Other data messages between the same IP addresses but with different transport layer protocols, destination ports, and/or DSCP values would match the fourth rule, indicating that these data messages are subject to rate limiting controls.

Returning toFIG.5, the process500determines (at530) whether to apply a rate limiting mechanism to the data message (i.e., whether the data message is subject to rate limiting controls). As described, in some embodiments this is determined by the highest-priority matching rule in the relevant ACL table for the data message. In addition, some data messages might not match any of the ACL rules. Some embodiments subject such data messages to rate limiting controls, while in other embodiments these data messages are not subject to rate limiting controls (i.e., are automatically allowed without affecting the rate limiting). If the data message is not subject to rate limiting controls, the process500proceeds to560, described below. This decision as to whether to apply rate limiting controls allows for certain traffic to always be passed through without being subject to rate controls. For instance, in some embodiments, control traffic such as routing protocol messages (e.g., BGP, OSPF messages), bidirectional forwarding protocol (BFD) messages, etc. should always be allowed.

If the data message is subject to rate limiting controls, the process500applies these controls to determine (at535) whether the data message is conforming. In some embodiments, this rate limiting mechanism involves the application of a set of QoS data structures for the particular logical router, which is described in greater detail in U.S. Patent Publication 2021/0218677, which is incorporated herein by reference. The gateway datapath compares a size of the data message that is subject to rate limiting to a current token bucket value stored for the logical router. The QoS data structure for a logical router of some embodiments tracks the amount of data processed (in both ingress and egress directions) by each core of the gateway device for the logical router and subtracts these amounts from a token bucket value, in addition to regularly adding to the token bucket value a committed rate (based on an allowed bandwidth for the particular logical router). Additional details of the token bucket value computations are described in U.S. Patent Publication 2021/0218677. When a data message is smaller than the current token bucket value, the data message is conforming; when the data message is larger than the current token bucket value, the data message is not conforming.

If the data message is conforming, then this data message is allowed and the process500modifies (at540) the DSCP value of the data message if such modification is specified by the rate limiting configuration, and proceeds to560. In some embodiments, the administrator can configure the gateway datapath (e.g., as part of the logical router rate limiting configuration) to set conforming data messages to a DSCP value (typically a value indicating that the data message is high priority). This operation is not required in some embodiments, as the administrator can also choose to forego this DSCP marking and allow the data message without modification.

If the data message is not conforming, the process determines (at545) whether to drop the non-conforming data message. Just as the logical network administrator can opt to modify the DSCP value of conforming data messages, some embodiments allow the administrator to configure the rate limiting mechanism to either drop non-conforming data messages or to modify the DSCP value of these data messages (typically to a value indicating that the data message is low priority). If the gateway datapath is configured to modify the data message, the process500modifies (at550) the DSCP value of the data message and proceeds to560. Otherwise, the process500drops (at555) the data message and ends.

So long as the data message is not dropped, the process500completes (at560) logical processing and transmits the data message to its destination. This includes the routing for the logical router as well as other logical processing stages, again depending on the direction of the data message (ingress or egress) and the architecture and configuration of the logical network. As at operation515, these logical processing stages might include various logical switches, other logical routers (e.g., multiple components of a different logical router, a distributed routing component of the same logical router), distributed firewall, NAT, and/or load balancing. In addition, for ingress data messages, transmitting the data message often involves encapsulating the data message (e.g., using VXLAN, GENEVE, STT, or other encapsulation).

It should be noted that, in some embodiments, the entire set of processing stages (and thus the process500) is typically only performed for the first data message of a data message flow. The gateway datapath generates a flow cache entry based on this processing, and subsequent data messages match the flow cache entry rather than requiring the more resource-intensive set of processing stages. To ensure that the ACL table does not need to be looked up for each subsequent data message in the data message flow, all of the fields on which the ACL table matches are also incorporated into the flow cache entry (e.g., the seven fields described above). In general, the protocol field, source and destination network addresses, and source and destination transport layer ports would be part of the flow cache, as these are the values often used to define a data message flow. DSCP (or ToS) and CoS fields are added to the flow cache entries when using the above-described ACL tables to determine whether to rate limit data messages.

In addition, some embodiments incorporate at least some of the presence bits into the flow cache entry. Some embodiments allocate one byte to store the presence bits (e.g., 7 bits). Other embodiments allocate one byte in the flow cache entry for the DSCP field (a 6-bit field) and one byte for the CoS field (a 3-bit field). As both of these fields are less than 8 bits, the allocated byte can also store a presence bit for the field indicating whether the field is required.

In addition, within the flow cache, a data message that carries a particular field may not be allowed to match an entry with a presence bit of ‘0’ for that particular field (as opposed to in the ACL table, where the ‘0’ presence bit indicates matching is allowed whether or not the field is present). This forces a data message that carries the particular field to be processed through the full set of processing stages, including the ACL table, as the data message might actually match a higher priority rule that requires the presence of the field. If the data message that carries the particular field does match the rule with the presence bit of ‘0’ for the particular field as the highest-priority rule when processed through the set of stages, some embodiments generate a new cache entry with this presence bit set to ‘1’. That is, the presence bit in the cache entry matches the data message for which the cache entry was generated rather than the ACL rule that was matched. Thus, for example, two data flows that match all of the same rules during processing and otherwise have all of the same relevant header field values, but only one of which carries a specific field (e.g., the CoS field), will be represented with two different entries in the cache in some such embodiments.

While the lookups to determine whether subsequent data messages of a flow are subject to rate limiting controls are handled by the flow cache entry, the actual application of the rate limiting mechanism is applied separately for each data message in the flow. Thus, for instance, a first data message in a flow might be allowed, but a later data message in the same flow could be dropped due to congestion (i.e., because the current token bucket value is smaller when the later data message is received).

FIG.9conceptually illustrates an electronic system900with which some embodiments of the invention are implemented. The electronic system900may be a computer (e.g., a desktop computer, personal computer, tablet computer, server computer, mainframe, a blade computer etc.), phone, PDA, or any other sort of electronic device. Such an electronic system includes various types of computer readable media and interfaces for various other types of computer readable media. Electronic system900includes a bus905, processing unit(s)910, a system memory925, a read-only memory930, a permanent storage device935, input devices940, and output devices945.

The bus905collectively represents all system, peripheral, and chipset buses that communicatively connect the numerous internal devices of the electronic system900. For instance, the bus905communicatively connects the processing unit(s)910with the read-only memory930, the system memory925, and the permanent storage device935.

The read-only-memory (ROM)930stores static data and instructions that are needed by the processing unit(s)910and other modules of the electronic system. The permanent storage device935, on the other hand, is a read-and-write memory device. This device is a non-volatile memory unit that stores instructions and data even when the electronic system900is off. Some embodiments of the invention use a mass-storage device (such as a magnetic or optical disk and its corresponding disk drive) as the permanent storage device935.

Other embodiments use a removable storage device (such as a floppy disk, flash drive, etc.) as the permanent storage device. Like the permanent storage device935, the system memory925is a read-and-write memory device. However, unlike storage device935, the system memory is a volatile read-and-write memory, such a random-access memory. The system memory stores some of the instructions and data that the processor needs at runtime. In some embodiments, the invention's processes are stored in the system memory925, the permanent storage device935, and/or the read-only memory930. From these various memory units, the processing unit(s)910retrieve instructions to execute and data to process in order to execute the processes of some embodiments.

The bus905also connects to the input and output devices940and945. The input devices enable the user to communicate information and select commands to the electronic system. The input devices940include alphanumeric keyboards and pointing devices (also called “cursor control devices”). The output devices945display images generated by the electronic system. The output devices include printers and display devices, such as cathode ray tubes (CRT) or liquid crystal displays (LCD). Some embodiments include devices such as a touchscreen that function as both input and output devices.

Finally, as shown inFIG.9, bus905also couples electronic system900to a network965through a network adapter (not shown). In this manner, the computer can be a part of a network of computers (such as a local area network (“LAN”), a wide area network (“WAN”), or an Intranet, or a network of networks, such as the Internet. Any or all components of electronic system900may be used in conjunction with the invention.

Hypervisor kernel network interface modules, in some embodiments, is a non-VM DCN that includes a network stack with a hypervisor kernel network interface and receive/transmit threads. One example of a hypervisor kernel network interface module is the vmknic module that is part of the ESXi™ hypervisor of VMware, Inc.

It should be understood that while the specification refers to VMs, the examples given could be any type of DCNs, including physical hosts, VMs, non-VM containers, and hypervisor kernel network interface modules. In fact, the example networks could include combinations of different types of DCNs in some embodiments.