Systems and methods for determining network forwarding paths with a controller

• US 9,356,838 B1
• Filed: 03/15/2013
• Issued: 05/31/2016
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: Arista Networks, Inc.
• Original Assignee: Big Switch Networks, Inc. (Arista Networks, Inc.)
• Inventors: Wang, Kuang-Ching, Ramasubramanian, Srinivasan
• Primary Examiner(s): Nguyen, Phuongchau Ba
• Application Number:
  US13/843,138
• Time in Patent Office: 1,173 Days
• Field of Search: 370/238, 370/235, 370/389, 370/392, 370/256, 370/221, 370/225, 370/401, 370/252, 370/400, 370/217, 370/248, 370/254, 709/241, 709/203, 709/220, 709/223
• US Class Current: 1/1
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 41/122 of virtualised topologies, e.g. software-defined networks [SDN] or network function virtualisation [NFV]

Abstract

A controller may control switches in a network that forwards network packets between end hosts. The controller may generate a directed acyclic graph based on maintained network topology information. The directed acyclic graph may include multiple network paths between any given pair of switches. For a given network packet received from an end host, the controller may generate an identifier or otherwise classify the network packet based on network attributes of the network packet. The network attributes may include packet header information retrieved from the network packet, information maintained by the controller such as which virtual switch is associated with the network packet, and/or other network attributes. The controller may use the network packet identifier to select a network forwarding path for the network packet from the directed acyclic graph.

Claims

1. A method of using a controller that controls switches in a network, the method comprising:

with the controller, receiving a network packet;

generating an identifier based on network attributes of the network packet;

based on the identifier, determining a network forwarding path for the network packet;

with the controller, maintaining network topology information for the network;

generating a directed acyclic graph based on the network topology information, wherein the switches include ports; and

generating a plurality of virtual switches, wherein at least one virtual switch of the plurality of virtual switches includes ports from multiple switches, wherein generating the identifier based on the network attributes of the network packet comprises;

identifying which virtual switch of the plurality of virtual switches is associated with the network packet; and

generating the identifier based on the identified virtual switch.

2. The method defined in claim 1 further comprising:

identifying source and destination switches from the network packet, wherein the directed acyclic graph includes a set of at least one forwarding path between the source and destination switches.

3. The method defined in claim 2 wherein determining the network forwarding path for the network packet comprises:

selecting a forwarding path from the set based on the identifier.

4. The method defined in claim 3 wherein the set of at least one forwarding path between the source and destination switches includes a plurality of forwarding paths between the source and destination switches.

5. The method defined in claim 4 wherein the plurality of forwarding paths between the source and destination switches comprises a plurality of equal-cost forwarding paths.

6. The method defined in claim 4 further comprising:

assigning indices to the plurality of forwarding paths between the source and destination switches, wherein generating the identifier comprises generating an integer value, and wherein selecting the forwarding path from the set based on the identifier comprises matching the integer value to the indices of the plurality of forwarding paths.

7. The method defined in claim 1 further comprising:

generating the network forwarding path by providing flow table entries to the switches.

8. The method defined in claim 1 wherein generating the identifier based on the network attributes of the network packet comprises:

retrieving packet header information from the network packet; and

generating the identifier based on the retrieved packet header information.

9. The method defined in claim 8 wherein retrieving packet header information from the network packet comprises retrieving a destination network address from the network packet.

10. The method defined in claim 8 wherein retrieving packet header information from the network packet comprises retrieving a virtual local area network identifier from the network packet.

11. The method defined in claim 1 wherein the network packet includes data that is sent between end hosts of the network and wherein generating the identifier comprises generating the identifier based at least partly on the data of the network packet.

12. A method of using a controller that controls switches in a network, the method comprising:

with the controller, selecting first and second switches of the network;

with the controller, selecting a plurality of forwarding paths between the first and second switches;

with the controller, assigning an identifier to each selected path;

with the controller, controlling the switches to generate a forwarding path of the plurality of forwarding paths based on the assigned identifiers, wherein the switches include ports; and

generating a plurality of virtual switches, wherein at least one virtual switch of the plurality of virtual switches includes ports from multiple switches, wherein assigning the identifier comprises;

identifying which virtual switch of the plurality of virtual switches is associated with a network packet received by the controller; and

generating the identifier based on the identified virtual switch.

13. The method defined in claim 12 further comprising:

with the controller, identifying all forwarding paths between the first and second switches based on network topology information maintained at the controller, wherein selecting the plurality of forwarding paths between the first and second switches comprises selecting a subset of the identified forwarding paths.

14. The method defined in claim 13 further comprising:

with the controller, calculating a cost metric for each forwarding path between the first and second switches, wherein selecting the subset of the identified forwarding paths between the first and second switches comprises;

determining which forwarding paths of the identified forwarding paths are minimum-cost forwarding paths.

15. The method defined in claim 13 further comprising:

with the controller, receiving the network packet;

with the controller, identifying network attributes associated with the network packet; and

with the controller, calculating a network packet identifier based on the identified network attributes, wherein the forwarding path has an identifier that matches the network packet identifier.

16. The method defined in claim 12, further comprising:

with the controller, maintaining network topology information for the network.

17. A method of using a controller that controls switches in a network, the method comprising:

with the controller, identifying network topology information for the network;

based on the network topology information, generating a directed acyclic graph including nodes corresponding to the switches and including directed edges between the nodes using the controller;

with the controller, receiving and classifying a network packet to produce a classification based on network attributes associated with the network packet;

with the controller, controlling the switches to generate a network forwarding path for the network packet based on the directed acyclic graph and the classification of the network packet, wherein the switches include ports; and

generating a plurality of virtual switches, wherein at least one virtual switch of the plurality of virtual switches includes ports from multiple switches, and wherein classifying the network packet comprises generating an identifier based on the network attributes associated with the network packet comprises;

identifying which virtual switch of the plurality of virtual switches is associated with the network packet; and

generating the identifier based on the identified virtual switch.

18. The method defined in claim 17 further comprising:

with the controller, identifying a network source and network destination from the network packet, wherein the directed acyclic graph includes a plurality of paths between the network source and network destination and wherein generating the network forwarding path based on the directed acyclic graph and the classification comprises;

based on the classification of the network packet, selecting a path from the plurality of paths between the network source and network destination; and

controlling the switches to generate the selected path.