Systems and methods for forwarding network packets in a network using network domain topology information

• US 9,331,930 B1
• Filed: 09/04/2012
• Issued: 05/03/2016
• Est. Priority Date: 09/04/2012
• Status: Active Grant

• Current Assignee: Arista Networks, Inc.
• Original Assignee: Big Switch Networks, Inc. (Arista Networks, Inc.)
• Inventors: Ramasubramanian, Srinivasan, Jiang, Kanzhe, Sherwood, Robert W., Banerjee, Subrata, Adams, Robert Edward
• Primary Examiner(s): Smith, Marcus R
• Assistant Examiner(s): Ali, Syed S
• Application Number:
  US13/603,160
• Time in Patent Office: 1,337 Days
• Field of Search: 370/351
• US Class Current: 1/1
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing

Abstract

A controller may be used to control client switches in a network that includes non-client switches. The controller may form client domains from groups of client switches that are separated by intervening non-client domains formed from non-client switches. The controller may determine a network domain topology from the client domains and non-client domains. The controller may determine a spanning tree that interconnects the nodes of the network domain topology. The controller may control client switches of the client domains to allow only network traffic between the client domains and the non-client domains along the spanning tree. The controller may use the network domain topology to generate inter-domain forwarding maps. The inter-domain forwarding maps may be used to determine network forwarding paths between end hosts in the network.

Claims

1. A method of using a controller that controls client switches in a network having non-client switches and end hosts that are coupled to the client and non-client switches, the method comprising:

with the controller, forming client domains from groups of the client switches, wherein the client domains are separated by non-client domains formed from the non-client switches;

with the controller, determining a network domain topology from the client domains and non-client domains;

with the controller, receiving a network packet from a source end host that is destined for a destination end host;

with the controller, identifying the source end host and destination end host from the received network packet;

identifying a source domain that is associated with the source end host from the client and non-client domains;

identifying a destination domain that is associated with the destination end host from the client and non-client domains;

determining an inter-domain forwarding path from the source domain to the destination domain based on the network domain topology, wherein the inter-domain forwarding path includes the source domain, the destination domain, and a list of intervening domains between the source domain and the destination domain;

for each client domain in the list of intervening domains, determining an intra-domain forwarding path from a previous domain to a subsequent domain in the list of domains; and

controlling the client switches in each client domain of the inter-domain forwarding path to forward the network packet from the source end host to the destination host along the inter-domain forwarding path and the intra-domain forwarding path of each client domain of the inter-domain forwarding path.

2. The method defined in claim 1 further comprising:

with the controller, determining a spanning tree from the client domains and the non-client domains based on the network domain topology.

3. The method defined in claim 2 further comprising:

with the controller, controlling the client switches of the client domains to allow only network traffic between the client domains and the non-client domains along the spanning tree.

4. The method defined in claim 3 wherein controlling the client switches of the client domains to allow only network traffic between client domains and non-client domains along the spanning tree comprises:

with the controller, providing flow table entries to the client switches that direct the client switches to drop network packets that do not traverse the spanning tree.

5. The method defined in claim 2, wherein the spanning tree comprises a loop free spanning tree.

6. The method defined in claim 5, wherein determining the spanning tree comprises generating the loop free spanning tree by removing network links identified by the network domain topology.

7. The method defined in claim 1 wherein the non-client domains are connected to ports of the client switches, the method further comprising:

with the controller, generating an inter-domain forwarding map for each client domain based on the network domain topology, wherein the inter-domain forwarding map of each client domain identifies which port and which client switch of that client domain should be used to forward network packets from a given source network location to a neighboring domain.

8. The method defined in claim 7 wherein generating the inter-domain forwarding map based on the network domain topology comprises:

selecting a given one of the client domains;

selecting a client switch of the selected client domain; and

determining intra-domain forwarding paths from the selected client switch throughout the selected client domain.

9. The method defined in claim 8 wherein determining intra-domain forwarding paths from the selected client switch throughout the selected client domain comprises:

determining a client domain exit path from the selected client switch through the selected client domain to each non-client domain that is connected to the selected client domain in the network domain topology.

10. The method defined in claim 8 wherein generating the inter-domain forwarding map based on the network domain topology further comprises:

determining a shortest path through the client domain between each pair of non-client domains that are connected to the selected client domain in the network domain topology.

11. The method defined in claim 7 wherein controlling the client switches in each client domain of the inter-domain forwarding path comprises:

providing the client switches in each client domain of the inter-domain forwarding path with flow table entries that direct the client switches to forward the network packet from the source end host to the destination host along the inter-domain forwarding path and the intra-domain forwarding path of each client domain of the inter-domain forwarding path.

12. The method defined in claim 7 further comprising:

with the controller, maintaining information identifying network attachment points of each of the end hosts that are coupled to the client and non-client switches, wherein identifying the source end host and destination end host from the received network packet comprises;

comparing network attachment point information determined from the received network packet to the maintained information identifying network attachment points of each of the end hosts that are coupled to the client and non-client switches.

13. The method defined in claim 1 wherein the non-client domains are connected to ports of the client switches, the method further comprising:

storing the network domain topology, wherein storing the network domain topology comprises storing information that identifies which client switches are assigned to each client domain and which ports of the client switches are assigned to each non-client domain.

14. The method defined in claim 1, further comprising:

with the controller, forming a plurality of client domains using the groups of the client switches, wherein each of the client domains in the plurality of client domains are separated by at least one non-client domain formed from the non-client switches.

15. The method defined in claim 1, wherein the non-client domains comprise non-client broadcast domains.

16. The method defined in claim 1, wherein the client domains are each separated by the non-client domains formed from the non-client switches without any direct network links between the client domains.

17. A method of using a controller that controls client switches in a network having non-client switches and end hosts that are coupled to the client and non-client switches, wherein groups of the client switches form respective client domains and wherein groups of the non-client switches form respective non-client domains that are interposed between the client domains, the method comprising:

with the controller, identifying a plurality of the client domains and a plurality of the non-client domains;

with the controller, receiving a network packet from a source end host;

with the controller, identifying a source domain associated with the network packet from the identified plurality of client domains and the identified plurality of non-client domains;

with the controller, identifying a destination domain associated with the network packet from the client and non-client domains;

determining an inter-domain forwarding path from the source domain to the destination domain, wherein the inter-domain forwarding path includes the source domain, the destination domain, and a list of intervening domains between the source domain and the destination domain;

for each client domain in the list of intervening domains, determining an intra-domain forwarding path from a previous domain to a subsequent domain in the list of domains; and

controlling the client switches in each client domain of the inter-domain forwarding path to forward the network packet from the source end host to the destination host along the inter-domain forwarding path and the intra-domain forwarding path of each client domain of the inter-domain forwarding path.

18. The method defined in claim 17 further comprising:

with the controller, determining the inter-domain forwarding path from the source domain to the destination domain based on network topology information maintained by the controller.

19. The method defined in claim 17 further comprising:

with the controller, directing the client switches to forward the network packet from the source domain to the destination domain along the inter-domain forwarding path.

20. The method defined in claim 19 wherein directing the client switches to forward the network packet from the source domain to the destination domain along the inter-domain forwarding path comprises:

for each client domain in the inter-domain forwarding path, providing flow table entries to the client switches of that client domain that direct the client switches of that client domain to forward the network packet to a subsequent domain in the inter-domain forwarding path.