Specifying and utilizing paths through a network

• US 10,659,252 B2
• Filed: 01/26/2018
• Issued: 05/19/2020
• Est. Priority Date: 01/26/2018
• Status: Active Grant

• Current Assignee: Nicira Incorporated (Broadcom, Inc.)
• Original Assignee: Nicira Incorporated (Broadcom, Inc.)
• Inventors: Boutros, Sami, Dubey, Ankur, Parsa, Mike, Cidon, Israel, Venugopal, Prashanth
• Primary Examiner(s): Patel, Hardikkumar D
• Application Number:
  US15/881,652
• Publication Number:
  US 20190238363A1
• Time in Patent Office: 844 Days
• CPC Class Codes: H04L 12/4633 Interconnection of networks using encapsulation techniques, e.g. tunneling
• CPC Class Codes: H04L 2212/00 Encapsulation of packets
• CPC Class Codes: H04L 45/306 Route determination based on the nature of the carried application
• CPC Class Codes: H04L 45/34 Source routing
• CPC Class Codes: H04L 45/38 Flow based routing
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering
• CPC Class Codes: H04L 49/9057 Arrangements for supporting packet reassembly or resequencing
• CPC Class Codes: H04L 61/103 across network layers, e.g. resolution of network layer into physical layer addresses or address resolution protocol [ARP]
• CPC Class Codes: H04L 61/2592 using tunnelling or encapsulation

Abstract

For a multi-tenant environment, some embodiments of the invention provide a novel method for (1) embedding a specific path for a tenant'"'"'s data message flow through a network in tunnel headers encapsulating the data message flow, and then (2) using the embedded path information to direct the data message flow through the network. In some embodiments, the method selects the specific path from two or more viable such paths through the network for the data message flow.

Claims

1. A method of specifying a path for a data message flow through a network comprising a plurality of forwarding elements, the method comprising:

at a host computer executing a source machine sending the data message flow,

using a set of attributes associated with the data message flow to identify one path-defining rule from a plurality of path-defining rules each of which (i) is stored on the host computer and (ii) specifies a different candidate path from a plurality of candidate paths for the data message flow through the network to a destination of the data message flow, the path specified by the identified path-defining rule traversing through a set of forwarding elements in a particular sequence;

with an outer tunnel header that is placed outside of layers 2 and 3 headers of each data message of the flow, encapsulating each data message in the flow, each outer tunnel header comprising (i) an outer portion that stores a destination network address that is a network address of a forwarding element that is the first forwarding element in the particular sequence, and (ii) an inner portion that stores a set of forwarding element identifiers identifying the set of forwarding elements on the path specified by the identified path-defining rule and a next forwarding-element identifier that identifies a next hop forwarding element along the path and is adjusted by each subsequent forwarding element in the specified path to identify the next hop forwarding element without removing the identifier of the subsequent forwarding element from the set of identifiers stored in the inner portion; and

forwarding the data messages encapsulated with their tunnel headers along the path specified by the identified path-defining rule.

2. The method of claim 1, wherein each data message has an original header and a payload, and the outer tunnel header of each data message encapsulates the data message'"'"'s payload and original header.

3. The method of claim 2, wherein the tunnel headers are based on a tunneling protocol that allows the tunnel headers to have a variable size.

4. The method of claim 1, wherein the network is a multi-tenant network and the data message flow is associated with a particular tenant, the method further comprising embedding a tenant identifier identifying the particular tenant in the tunnel headers, said embedded tunnel identifier allowing multiple different tenants to use a same set of tunnels between the forwarding elements.

5. The method of claim 4, wherein each tunnel header comprises a base tunnel header to store the tenant identifier, and the inner portion is a variable sized option header to store the set of forwarding-element identifiers.

6. The method of claim 1, wherein at each subsequent forwarding element in the path specified by the identified path rule that is not the last forwarding element in the path specified by the identified path rule, the forwarding element processes a received encapsulated data message by:

identifying the next forwarding-element identifier in the forwarding-element identifier set to identify the next forwarding element along the path specified by the identified path rule;

identifying a tunnel to the next forwarding element; and

adjusting the tunnel header of the encapsulated data message for forwarding along the identified tunnel by adjusting a network address of the next forwarding element as the destination network address stored in the tunnel header'"'"'s outer portion and adjusting the next hop identifier in the inner portion to identify the forwarding element identifier of the next forwarding element.

7. The method of claim 1, wherein the forwarding-element identifiers are the network addresses of the forwarding elements.

8. The method of claim 1, wherein the set of attributes comprises attributes other than layer 2 to layer 4 header values of the data message flow.

9. A non-transitory machine readable medium storing a program for specifying a path for a data message flow through a network comprising a plurality of forwarding elements, the program for execution by a set of hardware processing units of a host computer executing a source machine sending the data message flow, the program comprising sets of instructions for:

using a set of attributes associated with the data message flow to identify one path-defining rule from a plurality of path-defining rules each of which (i) is stored on the host computer and (ii) specifies a different candidate path from a plurality of candidate paths for the data message flow through the network to a destination of the data message flow, the path specified by the identified path-defining rule traversing through a set of forwarding elements in a particular sequence;

with an outer tunnel header that is placed outside of layers 2 and 3 headers of each data message of the flow, encapsulating each data message in the flow, each outer tunnel header comprising (i) an outer portion that stores a destination network address that is a network address of a forwarding element that is the first forwarding element in the particular sequence, and (ii) an inner portion that stores a set of forwarding element identifiers identifying the set of forwarding elements on the path specified by the identified path-defining rule and a next forwarding-element identifier that identifies a next hop forwarding element along the path and is adjusted by each subsequent forwarding element in the specified path to identify the next hop forwarding element without removing the identifier of the subsequent forwarding element from the set of identifiers stored in the inner portion; and

forwarding the data messages encapsulated with their tunnel headers along the path specified by the identified path-defining rule.

10. The non-transitory machine readable medium of claim 9, wherein each data message has an original header and a payload, the original header including a layer 2 header and a layer 3 header, and the tunnel header of each data message encapsulates the data message'"'"'s payload and original header including the layers 2 and 3 headers.

11. The non-transitory machine readable medium of claim 10, wherein the tunnel headers are based on a tunneling protocol that allows the tunnel headers to have a variable size.

12. The non-transitory machine readable medium of claim 9, wherein the network is a multi-tenant network and the data message flow is associated with a particular tenant, the method further comprising embedding a tenant identifier identifying the particular tenant in the tunnel headers, said embedded tunnel identifier allowing multiple different tenants to use a same set of tunnels between the forwarding elements.

13. The non-transitory machine readable medium of claim 12, wherein each tunnel header comprises a base tunnel header to store the tenant identifier, and the inner portion is a variable sized option header to store the set of forwarding-element identifiers.

14. The non-transitory machine readable medium of claim 9, wherein at each subsequent forwarding element in the path specified by the identified path rule that is not the last forwarding element in the path specified by the identified path rule, the forwarding element processes a received encapsulated data message by:

identifying the next forwarding-element identifier in the forwarding-element identifier set to identify the next forwarding element along the path specified by the identified path rule;

identifying a tunnel to the next forwarding element; and

adjusting the tunnel header of the encapsulated data message for forwarding along the identified tunnel, said adjusting comprising adjusting the outer portion of the tunnel header to include a network address of the next forwarding element as the destination network address.

15. The non-transitory machine readable medium of claim 9, wherein the forwarding-element identifiers are the network addresses of the forwarding elements.

16. The non-transitory machine readable medium of claim 9, wherein the set of attributes comprises attributes other than layer 2 to layer 4 header values of the data message flow.