Patent Description:
<CIT> Zuo concerns data forwarding in a software-defined network. <CIT> concerns redirecting packets for egress from an autonomous system using tenant-specific routing and forwarding tables.

Further embodiments are set forth in the dependent claims.

For purposes of explanation, several examples are set forth in the following figures.

In the following detailed description, numerous details, examples, and examples are set forth and described. However, it will be clear and apparent to one skilled in the art that the invention is not limited to the examples set forth and that the invention may be practiced without some of the specific details and examples discussed.

For a multi -tenant environment, some examples provide a method for (<NUM>) embedding a specific path for a tenant's data message flow through a network in tunnel headers encapsulating the data message flow, and then (<NUM>) using the embedded path information to direct the data message flow through the network. In some examples, the encapsulating tunnel header is placed before (i.e., outside of) the layers <NUM>-<NUM> header of each data message in the flow.

According to the claimed invention, with an outer tunnel header that is placed outside of layers <NUM>, <NUM>, and <NUM> headers of each data message of a flow, each data message in the flow is encapsulated, each outer tunnel header storing the plurality of forwarding-element IP addresses identifying plurality of forwarding elements on a candidate first path specified by an identified path-defining rule.

In some examples, the method selects the specific path from two or more viable such paths through the network for the data message flow. To select the path from the set of viable paths between the source and destination of the data message flow, the method in some examples performs a classification operation on a data message flow. The classification operation in some examples can be based on the data message flow's layer <NUM>-<NUM> header values (e.g., five tuple identifier, i.e., protocol, source and destination ports, and source and destination IP addresses) and/or its associated contextual attributes, such as its traffic type (i.e., the type of content carried in the data message flow), QoS ratings, layer <NUM> parameters, process identifiers, user identifiers, group identifiers, etc. When the set of contextual attributes include the flow's traffic type, the method provides a novel way for selecting a traffic-engineered path for a data message flow, embedding information about this path in the tunnel headers of the data message flow, and using this information to direct the data message flow through a network.

After selecting the path for the data message flow, the method in some examples embeds the identified path in tunnel headers that it uses to encapsulate the flow's data messages. Also, in some examples, the method embeds in the tunnel headers a tenant identifier (e.g., embeds a VNI, virtual network identifier) to specify that the data messages are associated with a particular tenant (e.g., are emanating from a machine of the particular tenant). The method sends the encapsulated messages along a tunnel to a first intervening forwarding element that serves as the first hop along the selected path.

The method in some examples identifies the selected path, and embeds this path in the tunnel header, by identifying and embedding a list of network addresses (e.g., destination IP addresses) for the hops (e.g., intervening forwarding elements) along the path. Also, the method in some examples embeds a hop index value in the tunnel header that identifies one of the embedded network addresses as the network address of the"next" hop that is used to identify the next hop along the path. As further described below, each hop along the path decrements the hop index value as the hops along the path are embedded in the tunnel header in a reverse order (with the first hop appearing last in the list of hops and the last hop appearing first on the list of hops).

In some examples, the hops along the selected path are connected to each other through a set of tunnels. Some or all of the hops in some examples include software forwarding elements (SFEs) executing on host computers. Examples of such SFEs include software routers and switches in some examples. In some examples, one or more of the hops are hardware forwarding elements, such as top-of-rack switches, hardware routers, etc..

After selecting the path for a data message and encapsulating the data message with a tunnel header that contains the network addresses of the hops along the path, the method in some examples passes the encapsulated data message along a tunnel to the first hop (e.g., first SFE) along the path after forwarding element connected to the source machine (e.g., after the software forwarding element executing on the same host computer with the source machine). The outer portion of the tunnel header includes source and destination network addresses. At the ingress hop, the source address of the outer portion is the network address (e.g., IP address) of the ingress hop (or a virtual tunnel endpoint (VTEP) used by this hop) that initially sends the message along the tunnel and the destination address is the network address of the first hop (or its VTEP) that receives the message along the tunnel.

As used in this document, data messages refer to a collection of bits in a particular format sent across a network. One of ordinary skill in the art will recognize that the term data message is used in this document to refer to various formatted collections of bits that may be sent across a network, such as Ethernet frames, IP packets, TCP segments, UDP datagrams, etc. Also, as used in this document, references to L2, L3, L4, and L7 layers (or layer <NUM>, layer <NUM>, layer <NUM>, layer <NUM>) are references respectively to the second data link layer, the third network layer, the fourth transport layer, and the seventh application layer of the OSI (Open System Interconnection) layer model.

<FIG> illustrates an example of specifying and using a traffic-engineered path according to some examples. In this example, two paths <NUM> and <NUM> are specifically specified in a network between two guest virtual machines (GVMs) <NUM> and <NUM> executing on two hosts <NUM> and <NUM> in a multi -tenant datacenter. The GVMs belong to a tenant that is associated in the datacenter with a particular virtual network identifier VNI. Even though in the example illustrated in <FIG> the embedded path information allows the data message flow to take a particular path through one datacenter, one of ordinary skill will realize that in other examples this path information is used to specify a path between machines in two or more datacenters of the same enterprise, of the same public cloud provider, and/or of different public cloud providers. Similarly, in some examples, this path information can be used to specify a path between machines residing in one or more private datacenters or branch offices and one or more public cloud datacenters.

Each path <NUM> or <NUM> starts at an ingress SFE (e.g., software switch or router) <NUM> executing on the host <NUM>, and terminates at an egress SFE <NUM> executing on the host <NUM>. These SFEs <NUM> and <NUM> serve as the ingress and egress hops for each path. Each path also has one or more intervening hops, with path <NUM> having intervening hops <NUM> and <NUM>, and the path <NUM> having intervening hop <NUM>. Each path is formed by a series of tunnels <NUM>-<NUM> that are established between neighboring hops along the path. In this example, each hop includes a software forwarding element executing on a host computer, although this does not have to be the case. For instance, in some examples, one or more of the intervening hops can be top-of-rack switches, spine switches, hardware routers or any other kind of forwarding element.

In the example illustrated in <FIG>, the path <NUM> is selected for a data message flow from the GVM <NUM> to the GVM <NUM>. As shown, the ingress and intervening hops pass the data message along the path through the tunnels <NUM>, <NUM>, and <NUM> with an encapsulating tunnel header <NUM> that is placed before (i.e., outside of) the layers <NUM>-<NUM> header <NUM> of the data message <NUM>. Also, as the encapsulated data message is sent along each tunnel, the tunnel header's outer portion (not shown) identifies the IP addresses of the source and destination endpoints of the tunnel as the source and destination IP addresses of the encapsulated data message.

In some examples, the source and destination tunnel endpoints are VTEPs associated with the two hop endpoints of the tunnel. For example, for the tunnel <NUM>, the outer portion of the tunnel header <NUM> identifies the IP addresses of a VTEP of the ingress hop <NUM> as the encapsulated data message's source IP address, while identifying the IP addresses of a VTEP of the hop <NUM> as the encapsulated data message's destination IP address. In the encapsulated data message forwarded by the ingress hop <NUM> or either intervening hop <NUM> or <NUM>, the tunnel header <NUM> includes the tenant's VNI and a path description that specifies the remaining portion of the path at that hop. As shown, the path description in some examples is expressed in terms of a list of IP addresses of the remaining hops.

In some examples, the ingress hop <NUM> includes the SFE that receives the data message from the source GVM <NUM>, and a path processing filter that executes on the same host computer <NUM>. As further described below, a hook (e.g., a callback function) is defined in a port of the SFE to intercept the data message sent by the source GVM <NUM> and to forward the data message to the path-processing filter. This filter then performs a classification operation on the data message, in order to select the path <NUM> for the data message to its destination GVM <NUM>.

This classification operation selects the path <NUM> from the group of two candidate paths <NUM> and <NUM> that are viable candidate paths that have been specifically defined (e.g., by a controller or a forwarding element) to reach the destination GVM <NUM>. In some examples, the classification operation is based on a set of attributes associated with the data message flow. This attribute set in some examples just includes the data message flow's layer <NUM>-<NUM> header values. In other examples, however, the attribute set includes contextual attributes related to the data message flow, such as the data message flow's traffic type (i.e., the type of content carried in the data message flow), QoS ratings, layer <NUM> parameters, process identifiers, user identifiers, group identifiers, etc..

When the set of contextual attributes include the flow's traffic type, the ingress hop selects a traffic-engineered path for a data message flow, embeds information about this path in the tunnel headers of the data message flow, and uses this information to direct the data message flow through a network. For instance, based on deep packet inspection performed on host computer <NUM>, a first data message flow between the GVMs <NUM> and <NUM> might be identified as carrying video conference data for corporate executives, while a second data message flow between these two GVMs might be identified as carrying chat message data between two non executives. Based on this contextual data, path <NUM> is selected for the first message flow as this path might be more optimal for delay or latency, while path <NUM> is selected for the second message flow as this path might be more optimal for cost.

After selecting the path for the intercepted data message, the ingress hop's path processing filter in some examples embeds the selected path in the tunnel header <NUM> that it uses to encapsulate the data message <NUM>. As shown, the path-processing filter in some examples identifies and embeds the selected path in terms of the IP addresses of the intervening hops <NUM> and <NUM> and the egress hop <NUM>. In addition to the IP addresses of these hops, the ingress path-processing filter embeds in the tunnel header a tenant identifier (which in this case is the particular tenant's VNI) to specify that the data message <NUM> is associated with the particular tenant (e.g., are emanating from a GVM of the particular tenant).

The ingress path-processing filter in some examples embeds the network addresses of the endpoints of the first tunnel <NUM> in the outer portion of the tunnel header <NUM>. This path processing filter in some examples also embeds a next hop value in the tunnel header that identifies the embedded network address of the intervening hop <NUM> as the network address of the"next" hop. As further described below, subsequent hops along the path use this index in some examples to identify the next hop along the path.

After selecting the path for the data message <NUM> and encapsulating the data message with the tunnel header <NUM>, the ingress hop <NUM> passes the encapsulated data message along the tunnel <NUM> to the intervening hop <NUM>. As mentioned above, the outer portion of the tunnel header <NUM> in some examples identifies the IP addresses of a VTEP of the ingress hop <NUM> as the encapsulated data message's source IP address, while identifying the IP addresses of a VTEP of the first hop <NUM> as the encapsulated data message's destination IP address.

At each subsequent hop <NUM>, <NUM> or <NUM> along the path <NUM>, the hop inspects the tunnel header and determines that the received data message is addressed to it. Each particular hop makes this determination in some examples by extracting the hop index from the tunnel, using this index to retrieve the network address of the next hop from the tunnel header, and then determining that address is its network address. After determining that the received data message identifies it as the next hop, the particular hop determines whether it is specified as the last hop of the specified path.

If not, the particular hop forwards the encapsulated data message along another tunnel to another hop after adjusting the tunnel header parameters. Specifically, to forward the data message to the other hop, the particular hop in some examples (<NUM>) decrements the next hop index (extracted from the received data message's tunnel header) to identify the network address of the other hop as the network address of the next hop along the path, (<NUM>) resolves the next hop's network address to an underlay tunnel that starts at the particular hop and terminates at the next hop, and (<NUM>) embeds this decremented hop index value in the tunnel header along with the tenant identifier and the list of network addresses of the hops along the path.

<FIG> illustrates the adjustment to the next hop index by showing this index as (<NUM>) initially referencing the IP address of hop <NUM> when the encapsulated data message leaves the ingress hop, (<NUM>) referencing the IP address of hop <NUM> when the encapsulated data message leaves the hop <NUM>, and (<NUM>) referencing the IP address of hop <NUM> when the encapsulated data message leave the hop <NUM>. Each particular hop also adjusts the outer portion of the tunnel header so that the network address of the particular hop is the source network address, and the network address of the subsequent hop along the path <NUM> is the destination network address, of the encapsulated data message. For example, the hop <NUM> places its IP address as the source IP address of the outer header, and the IP address of hop <NUM> as the destination IP address in this header. Similarly, the hop <NUM> places its IP address as the source IP address of the outer header, and the IP address of egress hop <NUM> as the destination IP address in this header.

Instead of adjusting the tunnel header parameters, the particular hop in other examples decapsulates (i.e., removes) the tunnel header from the received data message, and re-encapsulates the data message with a new tunnel header. Also, other examples do not store a next hop index in the tunnel headers, as in these examples, each intervening hop is configured to select the next hop address (e.g., the first hop address) and to remove its network address from the list of path-hop network addresses embedded in the tunnel before passing the encapsulated data message to the next hop along the path.

When the encapsulated data message reaches the egress hop <NUM>, this hop determines that it is specified as the last hop along the path that is embedded in the tunnel header of the data message (e.g., determines that the next hop index is its smallest value and it identifies this hop's address). Hence, it removes the tunnel header and examines the destination network address embedded in the data message's header <NUM>. This destination network address (e.g., IP address) is the IP address of GVM <NUM> connected to it. Accordingly, egress hop provides the decapsulated data message to this machine.

In <FIG>, the egress hop communicatively connects to the destination machine of the data message without having to go through intervening routing/switching fabric. In other examples, the egress hop connects to the message's destination (e.g., destination computer, virtual machine or container) through an intervening fabric (i.e., through intervening routers/switches). In these cases, the egress hop forwards the data message through the intervening fabric.

Some examples use Generic Network Virtualization Encapsulation (Geneve) tunneling protocol, to carry the path information (e.g., the next hop index and the list of hops along the path) and the tenant identifier. In some examples, the path information is embedded in a Geneve option TLV (type, length, value) that is examined by the hops along the path in order to identify the next hop, if any.

<FIG> illustrates the Geneve tunnel header <NUM> used in some examples. In some examples, this tunnel header <NUM> is a standard Geneve tunnel header that has an option TLV to store the path information and next hop index. Specifically, as shown, this tunnel header includes an outer header <NUM>, a protocol field <NUM>, a Geneve base header <NUM>, and an option TLV <NUM>. As described above, the outer portion <NUM> of the tunnel header <NUM> includes the network addresses (e.g., source and destination IP addresses of the two endpoints of the tunnel, with the source and destination designation depending on the direction of the message flow) in the underlay network that allow the encapsulated data message to traverse the underlay network and reach the tunnel destination endpoint. The protocol field <NUM> specifies a UDP protocol as well as attributes associated with this protocol.

<FIG> illustrates the Geneve base header <NUM> of some examples. As shown, this header in some examples is <NUM>-bit wide and stores several tunnel parameters, including the tenant identifier and the option length. Its version field <NUM> is a <NUM>-bit value that specifies the current Geneve tunnel version being used. Tunnel endpoints that receive messages with unknown versions drop the messages. Non-terminating devices processing Geneve packets with an unknown version number treat them as UDP packets with an unknown payload.

The option length field <NUM> specifies the length of the options fields, expressed in four byte multiples, not including the eight byte fixed tunnel header. This results in a minimum total Geneve header size of <NUM> bytes and a maximum of <NUM> bytes. The start of the payload headers can be found using this offset from the end of the base Geneve header. The O bit <NUM> specifies whether the data message is an OAM frame that contains a control message instead of a data payload. Endpoints do not forward the payload of this message and transit devices do not attempt to interpret or process it. Since control messages are not frequent, the endpoints typically direct these messages to a high priority control queue. The transit devices do not alter forwarding behavior on the basis of this bit, such as ECMP link selection.

The C bit <NUM> is a critical option field that when set, indicates that the options are present. One or more options can have the critical bit set. If this bit is set then tunnel endpoints parses the options list to interpret any critical options. When this bit is set, endpoints must drop the encapsulated message if they do not recognize this option. On devices where option parsing is not supported, the frame is dropped on the basis of the"C" bit in the base header. If the bit is not set tunnel endpoints may strip all options using"Opt Len" and forward the decapsulated frame. Transit devices do not drop or modify packets on the basis of this bit.

The first set of reserved bits <NUM> are <NUM> bits that must be zero on transmission and ignored on receipt. The protocol type bits <NUM> are <NUM> bits that express the type of the protocol data unit appearing after the Geneve header. The VNI bits <NUM> express a <NUM>-bit identifier for a unique element of a virtual network. In many situations, this may represent an L2 segment, however, the control plane defines the forwarding semantics of decapsulated packets. The VNI may be used as part of ECMP forwarding decisions or may be used as a mechanism to distinguish between overlapping address spaces contained in the encapsulated packet when load balancing across CPETs. The second set of reserved bits <NUM> are <NUM> bits that must be zero on transmission and ignored on receipt.

The Geneve base header is followed by the option TLV <NUM>. This TLV includes a four-byte option header and a variable amount of option data interpreted according to the option type. The option data in some examples includes the IP addresses of the hops along the path plus a next hop index that identifies one of these IP addresses as the IP address of the next hop along the path.

<FIG> conceptually illustrates a process <NUM> performed by an ingress hop (like hop <NUM>) of some examples. This process selects a path for a data message sent by a tenant GVM on a host computer, and then embeds a path hop list, which defines this path, in a Geneve tunnel header that it uses to encapsulate the data message, before sending this encapsulated message along a tunnel to the first hop along the selected path. In some examples, the ingress hop includes an SFE (e.g., software switch) and a path processing filter that execute on the host computer (e.g., computer <NUM>) along with the tenant GVM (e.g., GVM <NUM>) that sends the data message. In some examples, the GVMs on the host computer communicatively connect with the SFE, which forwards data messages to and from the GVMs.

As shown, the process <NUM> initially receives (at <NUM>) a data message from the tenant GVM (e.g., GVM <NUM>) executing on its host (e.g., <NUM>). In some examples, the process <NUM> receives this data message from a callback function that is defined in the port of the SFE or VNIC of the GVM. This callback function intercepts data messages sent by the GVM and forwards the data messages to the path-processing filter.

Based on a set of attributes associated with the data message, the process (e.g., the path processing filter) performs (at <NUM>) a classification operation on the data message, in order to select a defined path through the network to the data message's destination. For at least some of the data messages, this classification operation selects the path from a group of two or more candidate paths that are viable candidate paths that have been specifically defined (e.g., by a controller or a forwarding element) to reach the destination of the data message.

In some examples, the classification operation is based on a set of attributes associated with the data message. This attribute set in some examples just includes the data message's layer <NUM>-<NUM> header values. In other examples, however, the attribute set includes contextual attributes related to the data message, such as the data message's traffic type (i.e., the type of content carried in the data message's flow), QoS ratings, layer <NUM> parameters, process identifiers, user identifiers, group identifiers, etc. When the set of contextual attributes include the data message's traffic type, the process selects (at <NUM>) a path that is defined for the data message's flow based on the traffic that is carried in this message flow. In some examples, the process <NUM> uses a deep packet inspector on host computer <NUM> to perform a deep packet inspection of the data message or its flow in order to identify the type of traffic carried in the data message or its flow.

Based on the data message's attributes, the process selects a path for the data message in some examples that is optimal from a perspective of one or more metrics, such as cost, delay, latency, loss etc. In some examples, the process performs the classification operation (at <NUM>) by comparing one or more attributes of the data message (e.g., the data message's <NUM>-tuple identifier and/or associated contextual attributes) with identifiers of several path-defining rules stored in a rule storage. Each rule specifies a path through a network, which in some examples are specified as IP addresses of hops along the path. Hence, after matching the data message's attributes to a set of identifiers of a rule, the process selects the path specified by the rule as the path for the data message.

It should be noted that the process <NUM> allows two different tenants of a multi-tenant network to optimize their traffic-engineered paths different. For instance, for two data message flows of two tenants that carry the same type of traffic (i.e., the same type of payload content) between the same source and destination computers (on which at least one source or destination machine of each tenant executes), the process <NUM> can select two different paths. This can occur because one tenant might wish to use a faster, lower-latency path for that type of content, while the other tenant might wish for a less expensive path for that type of content. To implement this, some examples define different path-selection rules for different tenants, while other examples use the tenant identifier as one of the attributes for performing the path-selection classification operation.

After identifying (at <NUM>) the path for the data message, the process <NUM> embeds (at <NUM>) the identified path in an option TLV <NUM> of a Geneve tunnel header <NUM> that it will use to encapsulate the received data message. As described above, the option TLV stores the path in terms of the IP addresses of the hops along the path. Also, as further described above, the option TLV stores these IP addresses in reverse order, with the first hop's address appearing last in the list while the last hop's address appears first in the list.

In the option TLV, the process also stores (at <NUM>) the next hop value. The process sets this value to identify the last network address in the path hop list, which is the address of the first hop. The next hop index value is used to identify the embedded network address of the"next" hop, and subsequent hops use this index in some examples to identify the next hop along the path. At <NUM>, the process <NUM> also embeds in the base header <NUM> of the Geneve tunnel header the VNI of the tenant associated with the source GVM that sent the received data message. The embedding of the VNI allows the same set of tunnels to be used to forward data messages for different tenants.

Next, at <NUM>, the process configures other parts of the Geneve tunnel header. For instance, the process stores in the outer portion header <NUM> of the tunnel header <NUM> the L2 and L3 network addresses of its VTEP (e.g., a VTEP associated with its SFE) and the VTEP of the first hop as the source and destination network addresses. At <NUM>, the process defines the UDP protocol in the Geneve tunnel header, and sets any other fields that need to be define, per the discussion above and the tunnel deployment configuration being used.

After finalizing the tunnel header configuration (at <NUM>), the process passes (at <NUM>) the encapsulated data message along a Geneve tunnel to the first hop (e.g., hop <NUM>) along the selected path. To send this data message, the process in some examples resolves the IP address of the first hop to the tunnel that connects the ingress hop to the first hop. After <NUM>, the process ends.

<FIG> illustrates a process <NUM> that a hop performs when it receives a Geneve-encapsulated data message. In some examples, this hop executes on a host computer along with one or more tenant machines (e.g., GVMs). As shown, the process inspects (at <NUM>) the tunnel header and determines that the received data message is addressed to it. The hop makes this determination in some examples by extracting the next hop index from the tunnel, using this index to retrieve the network address of the next hop along the path, and then determining that this address is the IP address of its own.

Once the process <NUM> determines (at <NUM>) that the received data message is addressed to it, the process determines whether it is the last hop in the path embedded in the tunnel header. In some examples, this would be the case when the next hop index is at is lowest value (e.g., it is <NUM> or <NUM>, depending on which is defined as the lowest value), which is indicative that the last hop has been reached. When the process <NUM> determines (at <NUM>) that it is the last hop in the embedded path, it removes the tunnel header (i.e., decapsulates the encapsulated tunnel header), and forwards the data message to the destination machine identified by the destination network address identified in the received data message's original header (e.g., header <NUM>).

In some examples, the process <NUM> is performed by a path-processing filter that executes on the same host computer as the destination machine. A port of a SFE executing on the host computer in some examples passes the encapsulated data message to the path processing filter. In these examples, the path-processing filter passes the decapsulated data message back to the SFE port (e.g., passes a handle to this message to this part) and the SFE port processes, or has the SFE process, this message so that it can be forwarded to the destination machine (e.g., the destination GVM or container) executing on the same host computer. In some examples, the egress hop connects to the data message's destination (e.g., destination computer, virtual machine or container) through an intervening fabric (i.e., through intervening routers/switches). In these cases, the egress hop forwards the data message through the intervening fabric to the data message's destination.

When the process <NUM> determines (at <NUM>) that it is not the last hop in the embedded path, the process adjusts (at <NUM>) the next hop index value in the tunnel header of the received encapsulated message, in order to identify the next hop in the path identified by the embedded path information. As mentioned above, the process adjusts the next hop index value in some examples by decrementing this value as the path is specified in the tunnel header by a reverse ordered list of hop IP addresses.

Next, at <NUM>, the process adjusts the outer header values of the tunnel header to identify its own IP address as the source IP address of the encapsulated message, and the IP address of the next hop (now identified by the adjusted next hop index value) as the destination IP address of the encapsulated message. At <NUM>, the process resolves the next hop's address to a tunnel between the current hop and the next hop, and sends the encapsulated data message along this tunnel to the next hop. Before sending the encapsulated data message along the resolved tunnel, the process <NUM> in some examples adjusts (at <NUM>) one or more parameters in the data message's tunnel header (e.g., option, ID or other attributes of the next tunnel) to reflect new attributes and/or identity of the new tunnel along which the data message will get sent. After <NUM>, the process ends.

<FIG> illustrates a host computer <NUM> that is used in some examples to execute the GVMs, hop-processing forwarding element and path-processing filter of some examples. This host computer also executes service engines that perform context-rich, attribute-based services in a datacenter. The host computer <NUM> includes several GVM <NUM>, a software forwarding element <NUM>, a context engine <NUM>, service engines <NUM>, context-based service rule storage <NUM>, context-attribute storage <NUM>, an attribute-mapping storage <NUM>, a connection state cache storage <NUM>, a MUX (multiplexer) <NUM>, and a context-engine policy storage <NUM>. The service engines <NUM> include a path processor <NUM>, a deep packet inspector <NUM>, a load balancer <NUM>, a firewall engine <NUM>, and one or more other service engines (not shown).

In <FIG>, the GVMs <NUM> execute on a hypervisor. In some examples, the context engine <NUM>, the software forwarding element <NUM>, the service engines <NUM>, the context-based service rule storages <NUM>, the connection state cache storage <NUM>, the context-engine policy storage <NUM>, and the MUX <NUM> operate in the kernel space of the hypervisor, while the VMs <NUM> operate in the hypervisor's user space. In other examples, one or more service engines and/or the context engine are user space modules (e.g., are service VMs).

In some examples, the GVMs <NUM> are tenant machines that serve as data end points for some or all tenant data message flows in the datacenter. Examples of such machines include webservers, application servers, database servers, etc. In some cases, all the VMs belong to one entity, e.g., an enterprise that operates the host. In other cases, the host <NUM> operates in a multi-tenant environment (e.g., in a multi -tenant data center), and different VMs <NUM> may belong to one tenant or to multiple tenants.

Each VM <NUM> includes a GI agent <NUM> that communicates with the context engine <NUM> to provide context attribute sets to this engine, and to receive instructions and queries from this engine. The communications between the context engine <NUM> and the GI agents <NUM> are relayed through the MUX <NUM>. One example of such a mux is the mux that is used by the Endpoint Security (EPSec) platform of ESX hypervisors of VMware, Inc. In some examples, the attributes collected by the context engine <NUM> from the GI agents <NUM> include a rich group of parameters (e.g., layer <NUM> parameters, process identifiers, user identifiers, group identifiers, etc.). <CIT>, further describes the capturing and use of these contextual attributes through the GI agent <NUM>.

As shown, each GVM <NUM> includes a virtual network interface card (VNIC) <NUM> in some examples. Each VNIC is responsible for exchanging messages between its VM and the SFE <NUM>. Each VNIC connects to a particular port <NUM> of the SFE <NUM>. The SFE <NUM> also connects to a physical network interface card (NIC) (not shown) of the host. In some examples, the VNICs are software abstractions created by the hypervisor of one or more physical NICs (PNICs) of the host.

In some examples, the SFE <NUM> maintains a single port <NUM> for each VNIC of each VM. The SFE <NUM> connects to the host PNIC (through a NIC driver (not shown)) to send outgoing messages and to receive incoming messages. In some examples, the SFE <NUM> is defined to include a port <NUM> that connects to the PNIC's driver to send and receive messages to and from the PNIC. The SFE <NUM> performs message-processing operations to forward messages that it receives on one of its ports to another one of its ports. For example, in some examples, the SFE tries to use data in the message (e.g., data in the message header) to match a message to flow based rules, and upon finding a match, to perform the action specified by the matching rule (e.g., to hand the message to one of its ports <NUM> or <NUM>, which directs the message to be supplied to a destination VM or to the PNIC).

In some examples, the SFE <NUM> is a software switch, while in other examples it is a software router or a combined software switch/router. The SFE <NUM> in some examples implements one or more logical forwarding elements (e.g., logical switches or logical routers) with SFE executing on other hosts in a multi-host environment. A logical forwarding element in some examples can span multiple hosts to connect VMs that execute on different hosts but belong to one logical network.

Different logical forwarding elements can be defined to specify different logical networks for different users, and each logical forwarding element can be defined by multiple software forwarding elements on multiple hosts. Each logical forwarding element isolates the traffic of the VMs of one logical network from the VMs of another logical network that is serviced by another logical forwarding element. A logical forwarding element can connect VMs executing on the same host and/or different hosts. In some examples, the SFE extracts from a data message a logical network identifier (e.g., a VNI) and a MAC address. The SFE in these examples uses the extracted VNI to identify a logical port group, and then uses the MAC address to identify a port within the port group.

Software switches (e.g., software switches of hypervisors) are sometimes referred to as virtual switches because they operate in software and they provide the VMs with shared access to the PNIC(s) of the host. However, in this document, software switches are referred to as physical switches because they are items in the physical world. This terminology also differentiates software switches from logical switches, which are abstractions of the types of connections that are provided by the software switches. There are various mechanisms for creating logical switches from software switches. VXLAN provides one manner for creating such logical switches. The VXLAN standard is described in <NPL>.

The ports of the SFE <NUM> in some examples include one or more function calls to one or more modules that implement special input/output (EO) operations on incoming and outgoing messages that are received at the ports. Examples of I/O operations that are implemented by the ports <NUM> include ARP broadcast suppression operations and DHCP broadcast suppression operations, as described in <CIT>. Other I/O operations (such as firewall operations, load-balancing operations, network address translation operations, etc.) can be so implemented in some examples. By implementing a stack of such function calls, the ports can implement a chain of I/O operations on incoming and/or outgoing messages in some examples. Also, in some examples, other modules in the data path (such as the VNICs <NUM>, port <NUM>, etc.) implement the I/O function call operations instead of, or in conjunction with, the ports <NUM>.

In some examples, one or more of function calls of the SFE ports <NUM> can be to one or more service engines <NUM> that process service rules on the data message flows sent to and received for the GVMs. Some of these service rules are context-based service rules in the context-based service rule storages <NUM>. Each service engine <NUM> in some examples has its own context-based service rule storage <NUM>, attribute-mapping storage <NUM>, and connection state cache storage <NUM>. <FIG> presents just one context-based service rule storage <NUM>, attribute-mapping storage <NUM>, and connection state cache storage <NUM> for all the service engines in order not to obscure the presentation in this figure with unnecessary detail. Also, in some examples, each VM can have its own instance of a service engine (e.g., its own instance of path processor <NUM>, deep packet inspector <NUM>, load balancer <NUM>, and firewall engine <NUM>). In other examples, one service engine can service data message flows for multiple VMs on a host (e.g., VMs for the same logical network).

To perform its service operation for a data message flow, a service engine <NUM> in some examples tries to match the flow identifier (e.g., the five-tuple identifier) and/or the flow's associated context attribute set to the rule identifiers of its service rules in its context-based service rule storage <NUM>. Specifically, for a service engine <NUM> to perform its service check operation for a data message flow, the SFE port <NUM> that calls the service engine supplies a set of attributes of a message that the port receives. In some examples, the set of attributes are message identifiers, such as traditional five-tuple identifiers. In some examples, one or more of the identifier values can be logical values that are defined for a logical network (e.g., can be IP addresses defined in a logical address space). In other examples, all of the identifier values are defined in the physical domains. In still other examples, some of the identifier values are defined in the logical domain, while other identifier values are defined in the physical domain.

The service engine in some examples then uses the received message's attribute set (e.g., the message's five-tuple identifier) to identify the context attribute set that the service engine has stored for this flow in the attribute-mapping storage <NUM>. The context engine <NUM> in some examples supplies the context attributes for new flows (i.e., new network connection events) to the service engines <NUM>, along with a flow identifier (e.g., a five-tuple identifier). The context-engine policy storage <NUM> contains the rules that control the operation of the context engine <NUM>. In some examples, these policies direct the context engine to generate rules for the service engines or to direct the service engines to generate rules. The service engines <NUM> in these examples store the context attributes that they receive from the context engine in the attribute-mapping storage <NUM>.

In some examples, a service engine <NUM> stores the context attribute set for each new flow with that flow's identifier (e.g., five-tuple identifier) in the attribute-mapping storage. In this manner, the service engine can identify the context attribute set for each new flow that it receives from the SFE ports <NUM> by searching its attribute-mapping storage <NUM> for a context record that has a matching flow identifier. The context record with the matching flow identifier includes the context attribute set for this flow.

Some or all of the service engines in some examples pull the context attribute sets for a new flow from the context engine. For instance, in some examples, a service engine supplies a new flow's five-tuple identifier that it receives from the SFE port <NUM>, to the context engine <NUM>. This engine <NUM> then examines its attribute storage <NUM> to identify a set of attributes that is stored for this five-tuple identifier, and then supplies this attribute set (or a subset of it that it obtains by filtering the identified attribute set for the service engine) to the service engine.

Some examples implement the pull model by using a service token to encode the attribute set for a new message flow. When notified of a new network connection event, the context engine <NUM> in some examples (<NUM>) collects the context attribute set for the new event, (<NUM>) filters this set to discard the attributes that are not relevant for performing one or more services on the flow, (<NUM>) stores the remaining filtering attribute subset in the attribute storage <NUM> along with a service token, and (<NUM>) provides the service token to the GI agent <NUM>. The GI agent <NUM> then causes this token to be passed to the service engine(s) in-band (e.g., in a header of the data message that the agent's VM sends to a destination) or out-of-band (i.e., separately from the data messages that the agent's VM sends to a destination).

When the service engine gets the new flow through the SFE port <NUM>, it supplies this flow's service token to the context engine, which uses this service token to identify in its attribute storage <NUM> the context attributes to supply to the service engine. In the examples that the SFE port does not provide this service token to the service engine, the service engine first has to identify the service token by searching its data stores using the flow's identifier before supplying the service token to the context engine.

After identifying the contextual attribute set for a data message flow, the service engine <NUM> in some examples performs its service operation based on service rules that are stored in the context-based service rule storage <NUM>. To perform its service operation, the service engine <NUM> matches the received attribute subset with corresponding attribute sets that are stored for the service rules. In some examples, each service rule in the context-based service rule storage <NUM> has a rule identifier and an action parameter set.

As mentioned above, the rule identifier of a service rule in some examples can be defined in terms of one or more contextual attributes that are not L2-L4 header parameters (e.g., are L7 parameters, user identifiers, group identifiers, process name, loaded module identifiers, consumption parameters, etc.). In some examples, a rule identifier can also include L2-L4 header parameters. Also, in some examples, one or more parameters in a rule identifier can be specified in terms of an individual value or a wildcard value. Also, in some examples, a rule identifier can include a set of individual values or a group identifier, such as a security group identifier, a compute construct identifier, a network construct identifier, etc..

To match a received attribute set with the rules, the service engine compares the received attribute set with the associated identifiers of the service rules stored in the context-based service rule storage <NUM>. ETpon identifying a matching rule, the service engine <NUM> performs a service operation (e.g., a path processing operation, a firewall operation, a load balancing operation, an encryption operation, other middlebox operation, etc.), based on the action parameter set (e.g., based on the path hop list, Allow/Drop parameters, the load balancing criteria, encryption parameters, etc.) of the matching rule.

In some examples, the context-based service rule storage <NUM> is defined in a hierarchical manner to ensure that a message rule check will match a higher priority rule before matching a lower priority rule, when the message's attribute subset matches multiple rules. Also, in some examples, the context-based service rule storage <NUM> contains a default rule that specifies a default action for any message rule check that cannot identify any other service rules; this default rule will be a match for all possible attribute subsets in some examples, and ensures that the service rule engine will return an action for all received attribute subsets. In some examples, the default rule will specify no service.

Multiple messages can have the same message identifier attribute sets, e.g., when the messages are part of one flow that is associated with one communication session between two machines. Accordingly, after matching a data message with a service rule in the context-based service rule storage <NUM> based on the message's identified context attribute set, the service engine of some examples stores the service rule (or a reference to the service rule) in the connection state cache storage <NUM>, so that it can later use this service rule for subsequent data messages of the same flow.

In some examples, the connection state cache storage <NUM> stores the service rule, or a reference to the service rule, that the service engine <NUM> identifies for different message identifier sets (e.g., for different five-tuple identifiers that identify different data message flows). In some examples, the connection state cache storage <NUM> stores each service rule, or reference to the service rule, with an identifier (e.g., a flow's five-tuple identifier) that is generated from the matching message identifier set.

Before checking with the context-based service rule storage <NUM> for a particular message, a service engine <NUM> of some examples checks the connection state cache storage <NUM> to determine whether this storage has previously identified a service rule for this message's flow. If not, the service engine <NUM> identifies the contextual attribute set for the message flow, and then checks the context-based service rule storage <NUM> for a service rule that matches the message's identified attribute set and/or its five-tuple identifier. When the connection state data storage has an entry for the particular message, the service engine performs its service operation (e.g., its path selection operation) based on this service rule's action parameter set (e.g., based on hop list identified by this service rule in the connection cache <NUM>).

At each hop along a path, a hop path processor in some examples processes the path information embedded in the data message's tunnel header. On the host computer, the software forwarding element <NUM> is associated with the VTEP that serves as a Geneve tunnel endpoint in some examples. For an ingress hop (e.g., hop <NUM>), the path processor performs the operations of the process <NUM> of <FIG> in some examples. For a data message sent by a GVM <NUM> on its host computer, the path processor <NUM> selects an engineered path through the network for the data message to its destination based on the data message's attributes.

As mentioned above, these attributes can just include the message's flow identifier (e.g., five tuple identifier) in some cases, just include this message's captured contextual metadata in other cases, or can include both the message's flow identifier and captured contextual metadata. To select a path, the path processor in some examples matches the message's flow identifier and/or contextual metadata attributes with the rule identifier attributes of path-specifying rules of the path processor that are stored in the rule storage <NUM>. In some examples, each path-specifying rule in the storage <NUM> specifies a path in terms of a list of IP addresses for the hops along the path.

In some examples, the captured context for a data message includes the traffic type for the data message's flow (i.e., the type of content carried in that flow). In some examples, the DPI engine <NUM> identifies this traffic type when an SFE port <NUM> calls the DPI engine for the data message and/or other data messages in the same flow. The DPI engine in some examples provides this traffic type to the context engine <NUM> to store in the attribute storage <NUM>, so that the context engine <NUM> can subsequently provide the traffic type to the path processor <NUM> when this processor asks for this information for the data message (e.g., by providing the message's flow identifier attributes, or service token). In other examples, the context engine <NUM> pushes the traffic type for a flow to the attribute storage <NUM> (through the path processor <NUM> or another service engine) so that the path processor can later retrieve the flow's traffic type when processing a data message of the flow.

When the captured contextual attributes include the data message's traffic type, the ingress hop can select between two or more traffic-engineered paths to the data message's destination, when two or more such paths are previously defined and stored in the rule storage <NUM>. For instance, as described above by reference to <FIG>, path <NUM> might be more optimal based on delay and/or latency considerations, while path <NUM> might be more optimal from a cost perspective. Hence, for a first data message flow between the GVMs <NUM> and <NUM> that carries video conference data for corporate executives, the path processor matches the data message flow's attributes to a path-specifying rule that identifies path <NUM> as the flow's path to the GVM <NUM>. On the other hand, for a second data message flow between these two GVMs that carries chat message data between two non-executives, the path processor matches the data message flow's attributes to a path-specifying rule that identifies path <NUM> as the flow's path to the GVM <NUM>.

After matching the message's attribute set with one of path-specifying rules, the path processor <NUM> of the ingress node embeds the path hop list of the of path-specifying rule in a Geneve tunnel header, along with other tunnel attributes described above (e.g., outer header parameters, next hop index, etc.). In some examples, the path processor <NUM> has another one of the service engines <NUM> perform the tunnel encapsulation. After encapsulating the data message with a Geneve tunnel header <NUM>, the path processor returns the data message to the SFE (e.g., provides a handle for the location in memory at which the encapsulated data message is stored) so that the SFE can forward the data message along the Geneve tunnel to the hop associated with the first service machine in the specified path hop list.

When the path processor <NUM> is performing the operations of a non-ingress hop, the path processor performs the operations of the process <NUM> of <FIG> in some examples. For instance, it determines that a tunnel encapsulated data message has a path hop list that identifies the IP address of its SFE VTEP as the address of the next hop.

Once the path processor <NUM> determines that the received data message is addressed to it, the processor determines whether it is the last hop in the path embedded in the tunnel header. In some examples, this would be the case when the next hop index identifies the current hop's address as the first address in the path hop address list (i.e., when the next hop index has its lowest value). When the path processor <NUM> determines that it is the last hop in the embedded path, it removes the tunnel header (i.e., decapsulates the encapsulated tunnel header), and passes the decapsulated data message back to the SFE port (e.g., passes a handle to this message to this part) and the SFE port processes, or has the SFE process, this message so that it can be forwarded to the destination machine (e.g., the destination GVM or container) executing on the same host computer. In some examples, the egress hop connects to the data message's destination (e.g., destination computer, virtual machine or container) through an intervening fabric (i.e., through intervening routers/switches). In these cases, the egress hop forwards the data message through the intervening fabric to the data message's destination.

When the path processor is not the last hop in the embedded path, the path processor adjusts the next hop index value in the tunnel header of the received encapsulated message, in order to identify the next hop in the path identified by the embedded path information. As mentioned above, the path processor adjusts the next hop index value in some examples by decrementing this value as the path is specified in the tunnel header by an reverse ordered list of hop IP addresses.

The path processor <NUM> adjusts the outer header values of the tunnel header to identify its hop's IP address as the source IP address of the encapsulated message, and the IP address of the next hop (now identified by the adjusted next hop index value) as the destination IP address of the encapsulated message. The path processor resolves the next hop's address to a tunnel between the current hop and the next hop. Before sending the encapsulated data message along the resolved tunnel, the path processor in some examples adjusts one or more parameters in the data message's tunnel header to reflect the attributes and/or identity of the new tunnel along which the data message will get sent. It then provides the encapsulated data message to its SFE to forward long a tunnel to the next hop.

<FIG> illustrates an example of how the path-processing filters <NUM> are managed in some examples. This figure illustrates multiple hosts <NUM> in a datacenter. As shown, each host includes several service engines <NUM>, a context engine <NUM>, a path-processing filter <NUM>, several GVMs <NUM>, and an SFE <NUM>. It also illustrates a set of controllers <NUM> for managing the path-processing filters <NUM> and the service engines <NUM>, GVMs <NUM>, and SFEs <NUM>. The hosts and controllers communicatively connect to each other through a network <NUM>, which can be a local area network, a wide area network, a network of networks (such as the Internet), etc..

The controller set provides a user interface for the administrators to define context-based service rules in terms of contextual attributes, and communicates with the hosts through the network <NUM> to provide these policies. In some examples, the context engines <NUM> collect contextual attributes that are passed to management servers in the controller set through a network <NUM> so that these contextual attributes can be used to define policies. The management servers in some examples interact with discovery engines executing on the host computers <NUM> in the datacenter to obtain and refresh inventory of all processes and services that are running on the GVMs on the hosts. The management plane in some examples then provides a rule creation interface for allowing administrators to create context-based service rules for the service engines and the path processors <NUM>.

Once the high-level service policies are defined in the management plane, the management plane directly supplies some or all of these policies to the management proxies (not shown) on the hosts <NUM>, and/or indirectly supplies some or all of these policies to these proxies through a set of configuring controllers. In some examples, the management proxies publish the received policies as rules to the context-based service rule storages <NUM>. In some examples, the proxies transform these policies before publishing them to the context-based service rule storages <NUM>. Also, the context engines <NUM> on the hosts <NUM> in some examples resolve the policies based on collected contextual attributes, in order to generate rules for the service engines.

In some examples, different policies are specified for different data message flows from a source GVM based on different traffic content carried by these flows. For instance, one policy might define a path hop list that use low-latency path for a data message flow between two GVMs that is for a video conference involving the executive staff of a corporation, while another policy might define a path hop list that uses low cost path for a data message flow from the same two GVMs when this message flow pertains to a chat between two non executives.

Many of the above-described features and applications are implemented as software processes that are specified as a set of instructions recorded on a computer readable storage medium (also referred to as computer readable medium). When these instructions are executed by one or more processing unit(s) (e.g., one or more processors, cores of processors, or other processing units), they cause the processing unit(s) to perform the actions indicated in the instructions. Examples of computer readable media include, but are not limited to, CD-ROMs, flash drives, RAM chips, hard drives, EPROMs, etc. The computer readable media does not include carrier waves and electronic signals passing wirelessly or over wired connections.

In this specification, the term"software" is meant to include firmware residing in read-only memory or applications stored in magnetic storage, which can be read into memory for processing by a processor. Also, in some examples, multiple software inventions can be implemented as sub-parts of a larger program while remaining distinct software inventions. In some examples, multiple software inventions can also be implemented as separate programs. Finally, any combination of separate programs that together implement a software invention described here is within the scope of the invention. In some examples, the software programs, when installed to operate on one or more electronic systems, define one or more specific machine implementations that execute and perform the operations of the software programs.

<FIG> conceptually illustrates a computer system <NUM> with which some examples are implemented. The computer system <NUM> can be used to implement any of the above-described hosts, controllers, and managers. As such, it can be used to execute any of the above described processes. This computer system includes various types of non-transitory machine readable media and interfaces for various other types of machine readable media. Computer system <NUM> includes a bus <NUM>, processing unit(s) <NUM>, a system memory <NUM>, a read-only memory <NUM>, a permanent storage device <NUM>, input devices <NUM>, and output devices <NUM>.

The bus <NUM> collectively represents all system, peripheral, and chipset buses that communicatively connect the numerous internal devices of the computer system <NUM>. For instance, the bus <NUM> communicatively connects the processing unit(s) <NUM> with the read-only memory <NUM>, the system memory <NUM>, and the permanent storage device <NUM>.

From these various memory units, the processing unit(s) <NUM> retrieve instructions to execute and data to process in order to execute the processes described herein. The processing unit(s) may be a single processor or a multi-core processor in different examples. The read-only-memory (ROM) <NUM> stores static data and instructions that are needed by the processing unit(s) <NUM> and other modules of the computer system. The permanent storage device <NUM>, 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 computer system <NUM> is off. Some examples use a mass-storage device (such as a magnetic or optical disk and its corresponding disk drive) as the permanent storage device <NUM>.

Other examples use a removable storage device (such as a flash drive, etc.) as the permanent storage device. Like the permanent storage device <NUM>, the system memory <NUM> is a read-and-write memory device. However, unlike storage device <NUM>, 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 examples, the processes are stored in the system memory <NUM>, the permanent storage device <NUM>, and/or the read-only memory <NUM>. From these various memory units, the processing unit(s) <NUM> retrieve instructions to execute and data to process in order to execute the processes of some examples.

The bus <NUM> also connects to the input and output devices <NUM> and <NUM>. The input devices enable the user to communicate information and select commands to the computer system. The input devices <NUM> include alphanumeric keyboards and pointing devices (also called "cursor control devices"). The output devices <NUM> display images generated by the computer system. The output devices include printers and display devices, such as cathode ray tubes (CRT) or liquid crystal displays (LCD). Some examples include devices such as a touchscreen that function as both input and output devices.

Finally, as shown in <FIG>, bus <NUM> also couples computer system <NUM> to a network <NUM> through 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 computer system <NUM> may be used in conjunction with the examples.

Some examples include electronic components, such as microprocessors, storage and memory that store computer program instructions in a machine-readable or computer-readable medium (alternatively referred to as computer-readable storage media, machine-readable media, or machine-readable storage media). Some examples of such computer-readable media include RAM, ROM, read-only compact discs (CD-ROM), recordable compact discs (CD-R), rewritable compact discs (CD-RW), read-only digital versatile discs (e.g., DVD-ROM, dual-layer DVD-ROM), a variety of recordable/rewritable DVDs (e.g., DVD-RAM, DVD-RW, DVD+RW, etc.), flash memory (e.g., SD cards, mini-SD cards, micro-SD cards, etc.), magnetic and/or solid state hard drives, read-only and recordable Blu-Ray® discs, ultra-density optical discs, and any other optical or magnetic media. The computer-readable media may store a computer program that is executable by at least one processing unit and includes sets of instructions for performing various operations. Examples of computer programs or computer code include machine code, such as is produced by a compiler, and files including higher-level code that are executed by a computer, an electronic component, or a microprocessor using an interpreter.

While the above discussion primarily refers to microprocessor or multi-core processors that execute software, some examples are performed by one or more integrated circuits, such as application specific integrated circuits (ASICs) or field programmable gate arrays (FPGAs). In some examples, such integrated circuits execute instructions that are stored on the circuit itself.

As used in this specification, the terms "computer", "server", "processor", and "memory" all refer to electronic or other technological devices. As used in this specification, the terms "computer readable medium," "computer readable media," and "machine readable medium" are entirely restricted to tangible, physical objects that store information in a form that is readable by a computer. These terms exclude any wireless signals, wired download signals, and any other ephemeral or transitory signals.

Claim 1:
A method of specifying a path (<NUM>, <NUM>) for a data message flow through a network (<NUM>) comprising a plurality of forwarding elements (<NUM>-<NUM>), the method comprising:
at a host computer (<NUM>, <NUM>) executing a source machine (<NUM>) sending the data message flow (<NUM>):
using a set of attributes associated with the data message flow to identify one path-defining rule from a plurality of path-defining rules (<NUM>) each of which (i) is stored on the host computer (<NUM>, <NUM>) and (ii) specifies a different candidate path from a plurality of candidate paths (<NUM>, <NUM>) for the data message flow through the network to a destination (<NUM>) of the data message flow, the identified path-defining rule (<NUM>) specifying a candidate first path (<NUM>, <NUM>) by reference to a plurality of forwarding-element internet protocol (IP) addresses of the plurality of forwarding elements (<NUM>-<NUM>) on the candidate first path (<NUM>, <NUM>);
with an outer tunnel header (<NUM>, <NUM>) that is placed outside of layers <NUM>, <NUM>, and <NUM> headers (<NUM>) of each data message (<NUM>) of the flow, encapsulating each data message (<NUM>) in the flow, each outer tunnel header storing (<NUM>, <NUM>) the plurality of forwarding-element IP addresses identifying the plurality of forwarding elements (<NUM>-<NUM>) on the candidate first path (<NUM>, <NUM>) specified by the identified path-defining rule (<NUM>); and
forwarding the encapsulated data messages along the candidate first path (<NUM>, <NUM>) specified by the identified path-defining rule (<NUM>).