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

• US 9,548,900 B1
• Filed: 08/18/2015
• Issued: 01/17/2017
• 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, Adams, Robert Edward, Sherwood, Robert W., Banerjee, Subrata
• Primary Examiner(s): Kassim, Khaled
• Assistant Examiner(s): Ali, Syed S
• Application Number:
  US14/829,538
• Time in Patent Office: 518 Days
• 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 maintaining end host attachment point information in a network having client switches that are controlled by a controller and non-client switches, wherein end hosts are coupled to the client and non-client switches, the method comprising:

with the controller, maintaining network domain topology information that identifies client domains formed from client switches and non-client domains associated with non-client switches, wherein the non-client domains are interposed between the client domains;

with the controller, receiving a packet from an end host;

with the controller, identifying a network attachment point at the client switches for the end host based on the packet, wherein the client switches include ports and identifying the network attachment point for the end host comprises identifying, with the controller, a client switch and a port of the identified client switch to which the end host is coupled;

with the controller, determining whether to replace a previously identified network attachment point for the end host with the identified network attachment point based on network topology information maintained by the controller;

with the controller, retrieving the previously identified network attachment point for the end host from storage;

with the controller, identifying an inter-domain forwarding path from the identified client switch to the previously identified network attachment point using the network domain topology information;

with the controller, identifying a first-hop domain along the inter-domain forwarding path;

with the controller, identifying a domain that is associated with the identified network attachment point;

with the controller, determining whether the first-hop domain along the inter-domain forwarding path is the same as the domain of the identified network attachment point; and

with the controller, assigning the identified network attachment point to the end host in response to determining that the first-hop domain along the inter-domain forwarding path is the same as the domain of the identified network attachment point.

2. The method defined in claim 1 wherein identifying the inter-domain forwarding path comprises:

with the controller, determining which domain of the client and non-client domains includes the identified client switch;

with the controller, determining which domain of the client and non-client domains is associated with the previously identified network attachment point, wherein identifying the inter-domain forwarding path from the identified network attachment point to the previously identified network attachment point comprises;

determining the inter-domain forwarding path from the domain that includes the identified client switch to the domain that is associated with the previously identified network attachment point.

3. The method defined in claim 2 wherein the previously identified network attachment point is identified at a first time and wherein the identified network attachment point is identified at a second time, the method further comprising:

with the controller, determining a difference between the second time and the first time; and

with the controller, determining whether the difference between the second time and the first time exceeds a predetermined threshold, wherein assigning the identified network attachment point to the end host comprises;

assigning the identified network attachment point to the end host in response to determining that the difference between the second time and the first time exceeds the predetermined threshold.

4. The method defined in claim 2 further comprising:

with the controller, maintaining the previously identified network attachment point for the end host in response to determining that the first-hop domain along the inter-domain forwarding path is different from the domain of the identified network attachment point.

5. The method defined in claim 2, further comprising:

with the controller, identifying a domain that is associated with the identified network attachment point;

with the controller, determining whether the first-hop domain along the inter-domain forwarding path is the same as the domain of the identified network attachment point, wherein the previously identified network attachment point is identified at a first time and the identified network attachment point is identified at a second time after the first time; and

in response to determining that the first-hop domain along the inter-domain forwarding path is the same as the domain of the identified network attachment point, determining, with the controller, whether a difference between the second time and the first time exceeds a first predetermined threshold.

6. The method defined in claim 5, further comprising:

in response to determining that the difference exceeds the first predetermined threshold, assigning the identified network attachment point to the end host.

7. The method defined in claim 6, further comprising:

in response to determining that the difference does not exceed the first predetermined threshold, assigning the previously identified network attachment point to the end host.

8. The method defined in claim 6, further comprising:

in response to determining that the first-hop domain along the inter-domain forwarding path is not the same as the domain of the identified network attachment point, determining, using the controller, whether the identified network attachment point belongs to a client domain of switches that are controlled by the controller; and

in response to determining that the identified network attachment point belongs to the client domain, assigning, using the controller, the identified network attachment point to the end host.

9. The method defined in claim 6, further comprising:

in response to determining that the identified network attachment point does not belong to the client domain of switches, determining, using the controller, whether the identified network attachment point and the previously identified network attachment point both belong to a broadcast domain of switches that is not controlled by the controller;

in response to determining that the identified network attachment point and the previously identified network attachment point both belong to the broadcast domain, determining, using the controller, whether the difference exceeds a second predetermined threshold;

in response to determining that the difference exceeds the second predetermined threshold, assigning, using the controller, the identified network attachment point to the end host; and

in response to determining that the difference does not exceed the second predetermined threshold, assigning, using the controller, the previously identified network attachment point to the end host.

10. The method defined in claim 9, further comprising:

in response to determining that that the identified network attachment point and the previously identified network attachment point do not both belong to the broadcast domain, determining, using the controller, whether the identified network attachment point belongs to the broadcast domain and the previously identified network attachment point belongs to the client domain;

in response to determining that the identified network attachment point belongs to the broadcast domain and the previously identified network attachment point belongs to the client domain, determining, using the controller, whether the difference exceeds a third predetermined threshold;

in response to determining that the difference exceeds the third predetermined threshold, assigning, using the controller, the identified network attachment point to the end host; and

in response to determining that the difference does not exceed the third predetermined threshold, assigning, using the controller, the previously identified network attachment point to the end host.

11. A method of maintaining end host attachment point information in a network having client switches that are controlled by a controller and non-client switches, wherein end hosts are coupled to the client and non-client switches, the method comprising:

with the controller, receiving a packet from an end host;

with the controller, identifying a network attachment point at the client switches for the end host based on the packet, wherein identifying the network attachment point for the end host comprises identifying, with the controller, a client switch to which the end host is coupled;

with the controller, determining whether to replace a previously identified network attachment point for the end host with the identified network attachment point based on network topology information maintained by the controller, wherein receiving the packet from the end host comprises receiving a packet in message from a client switch that includes the packet and wherein identifying the network attachment point for the end host comprises identifying the network attachment point for the end host based on the packet in message;

with the controller, identifying an inter-domain forwarding path from the identified client switch to the previously identified network attachment point using the network domain topology information;

with the controller, identifying a first-hog domain along the inter-domain forwarding path;

with the controller, identifying a domain that is associated with the identified network attachment point;

with the controller, determining whether the first-hop domain along the inter-domain forwarding path is the same as the domain of the identified network attachment point; and

with the controller, assigning the identified network attachment point to the end host in response to determining that the first-hop domain along the inter-domain forwarding path is the same as the domain of the identified network attachment point.

12. The method defined in claim 11, wherein the packet in message comprises a message identifier that identifies the packet in message as the packet in message, a switch identifier that identifies the client switch, a source port identifier that identifies a switch port of the client switch over which the client switch received the packet from the end host, and a payload field that includes the packet.

13. The method defined in claim 12, wherein the payload field includes an entirety of the packet as received by the client switch from the end host.

14. The method defined in claim 12, wherein the payload field includes a portion of the packet as received by the client switch from the end host.