Methods for determining network topologies

A network may include switches that have controller clients that are controlled from one or more controller servers. Clusters of the switches that have the controller clients may be isolated from other clusters by switches without the controller clients. The controller server may use graph searches to identify the clusters. The controller server may use information on the cluster topology of switches containing controller clients along with information in per-switch forwarding databases to generate per-cluster forwarding databases. The controller server may use the per-cluster forwarding databases in generating flow tables for the network switches that direct the switches to forward packets along desired paths through the network.

BACKGROUND

This relates to communications networks, and more particularly, to obtaining information on network topologies in communications networks.

Packet-based networks such as the internet and local data networks that are connected to the internet include network switches. Network switches are used in forwarding packets from packet sources to packet destinations.

It can be difficult or impossible to control the switches of one vendor using the equipment of another vendor. This is because the switch equipment of one vendor may use a different operating system and set of control procedures than the switch equipment of another vendor. To address the challenges associated with controlling different types of switch platforms, cross-platform protocols have been developed. These protocols allow centralized control of otherwise incompatible switches.

Cross-platform controller clients can be included on the switches in a network. The controller clients are able to communicate with a corresponding controller server over network paths. Because the controller clients can be implemented on a variety of switch hardware, it is possible for a single controller to control switch equipment that might otherwise be incompatible.

Each network switch on which a controller client has been implemented may be provided with a flow table with entries that specify how packets are to be forwarded by that switch. To provide network switches with appropriate flow tables, the controller server may need to gather information on the topology of the network in which the network switches are operating. Without information on the topology of the network, the controller server may not be able to determine how to construct appropriate flow tables.

It would therefore be desirable to be able to provide improved arrangements for gathering information on the topology of a communications network from the network switches in a communications network.

SUMMARY

Network switches may be configured using flow tables. Flow table entries may contain header fields and associated actions. When a packet is received by a network switch, the network switch can compare fields in the packet to fields in the flow table entries. The network switch can take appropriate actions when matches are detected. For example, the network switch can forward packets to an appropriate switch port.

A controller server can be used to control the network switches. Each of the network switches may contain a controller client. The controller server and the controller clients may use network protocol stacks to communicate over network connections. For example, the controller server can distribute flow table entries to the controller clients that direct the network switches to perform desired packet processing operations.

The controller server can determine the topology of a network and can gather information on the capacities of network switches and other network switch capabilities. The controller server may use graph searches to determine the cluster topology of switches containing controller clients. The controller server may use the cluster topology of switches containing controller clients along with information in per-switch forwarding databases to generate per-cluster forwarding databases. The controller server may use the cluster topology of switches containing controller clients along with per-cluster forwarding databases to assist in generating flow tables for the network switches that direct the switches to forward packets along desired paths through the network.

DETAILED DESCRIPTION

Networks such as the internet and the local and regional networks that are coupled to the internet rely on packet-based switches. These switches, which are sometimes referred to herein as network switches, packet processing systems, or packet forwarding systems can forward packets based on address information. In this way, data packets that are transmitted by a packet source may be delivered to a packet destination. In network terms, packet sources and destinations are sometimes referred to as end hosts. Examples of end hosts are personal computers, servers, and other computing equipment.

It is not uncommon for networks to include equipment from multiple vendors. As an example, a network for a university or corporate campus might include core switches from one vendor, edge switches from another vendor, and aggregation switches from yet another vendor. Network switches from different vendors can be interconnected to form a packet forwarding network, but can be difficult to manage in a centralized fashion due to incompatibilities between their operating systems and control protocols.

These potential incompatibilities can be overcome by incorporating a common cross-platform control module (sometimes referred to herein as a controller client) into each network switch. A centralized cross-platform controller server may interact with each of the control clients over respective network links. The use of a cross-platform controller server and corresponding controller clients allows potentially disparate network switch equipment to be centrally managed.

With one illustrative configuration, which is sometimes described herein as an example, centralized control is provided by one or more controller servers such as controller server18ofFIG. 1. Control server18may be implemented on a stand-alone computer, on a cluster of computers, on a set of computers that are distributed among multiple locations, on hardware that is embedded within a network switch, or on other suitable computing equipment12. Controller server10can run as a single process on a single computer or can be distributed over several hosts for redundancy. The use of a distributed arrangement may help provide network10with resiliency against unexpected network partitions (e.g., a situation in which a network link between two campuses is disrupted).

In distributed controller arrangements, controller nodes can exchange information using an intra-controller protocol. For example, if a new end host connects to network hardware (e.g., a switch) that is only connected to a first controller node, that first controller node may use the intra-controller protocol to inform other controller nodes of the presence of the new end host. If desired, a switch or other network component may be connected to multiple controller nodes. Arrangements in which a single controller server is used to control a network of associated switches are sometimes described herein as an example.

Controller server18ofFIG. 1may gather information about the topology of network10. For example, controller server18may send Link Layer Discovery Protocol (LLDP) probe packets through the network to discover the topology of network10. Controller server18may use information on network topology and information on the capabilities of network equipment to determine appropriate paths for packets flowing through the network. Once appropriate paths have been identified, controller server18may send corresponding settings data to the hardware in network10to ensure that packets flow through the network as desired. Network configuration operations such as these may be performed during system setup operations, continuously in the background, or in response to the appearance of newly transmitted data packets (i.e., packets for which a preexisting path has not been established).

Controller server18may be used to implement network configuration rules20. Rules20may specify which services are available to various network entities. As an example, rules20may specify which users (or type of users) in network10may access a particular server. Rules20may, for example, be maintained in a database at computing equipment12.

Controller server18and controller clients30at respective network switches14may use network protocol stacks to communicate over network links16.

Each switch (packet forwarding system)14may have input-output ports34. Cables may be used to connect pieces of equipment to ports34. For example, end hosts such as personal computers, web servers, and other computing equipment may be plugged into ports34. Ports34may also be used to connect one of switches14to other switches14.

Packet processing circuitry32may be used in forwarding packets from one of ports34to another of ports34and may be used in performing other suitable actions on incoming packets. Packet processing circuit32may be implemented using one or more integrated circuits such as dedicated high-speed switch circuits and may serve as a hardware data path. If desired, packet processing software26that is running on control unit24may be used in implementing a software data path.

Control unit24may include processing and memory circuits (e.g., one or more microprocessors, memory chips, and other control circuitry) for storing and running control software. For example, control unit24may store and run software such as packet processing software26, may store flow table28, and may be used to support the operation of controller clients30.

Controller clients30and controller server18, may be compliant with a network switch protocol such as the OpenFlow protocol (see, e.g., OpenFlow Switch Specification version 1.0.0). One or more clients among controller clients30may also be compliant with other protocols (e.g., the Simple Network Management Protocol). Using the OpenFlow protocol or other suitable protocols, controller server18may provide controller clients30with data that determines how switch14is to process incoming packets from input-output ports34.

With one suitable arrangement, flow table data from controller server18may be stored in a flow table such as flow table28. The entries of flow table28may be used in configuring switch14(e.g., the functions of packet processing circuitry32and/or packet processing software26). In a typical scenario, flow table28serves as cache storage for flow table entries and a corresponding version of these flow table entries is embedded within the settings maintained by the circuitry of packet processing circuitry32. This is, however, merely illustrative. Flow table28may serve as the exclusive storage for flow table entries in switch14or may be omitted in favor of flow table storage resources within packet processing circuitry32. In general, flow table entries may be stored using any suitable data structures (e.g., one or more tables, lists, etc.). For clarity, the data of flow table28(whether maintained in a database in control unit24or embedded within the configuration of packet processing circuitry32) is referred to herein as forming flow table entries (e.g., rows in flow table28).

If desired, switch14may be implemented using a general purpose processing platform that runs control software and that omits packet processing circuitry32ofFIG. 2. This type of configuration is shown inFIG. 2. As shown in the illustrative arrangement ofFIG. 2, controller server18on computing equipment12may communicate with controller clients30on switch (packet forwarding system)14over network link16. Controller server18may, for example, convey flow table entries to controller clients30that are maintained in flow table28. Packet processing software40may use network interface38to forward and otherwise process packets (e.g., packets transmitted and received using ports34). Network interface38may be implemented using one or more network interface cards that are plugged into a system board in switch14(as an example).

Another illustrative type of network switch is shown inFIG. 3. In the example ofFIG. 3, computing equipment42is being used to implement virtual machines44. Computing equipment42may be, for example, a server that is based on one or more computers and virtual machines44may be used to implement web servers or other online services. In a typical scenario, a customer who has purchased virtual machine services may be assigned a number of virtual machines44. To ensure that these virtual machines can communicate with each other, some of the resources of computing equipment42are used to implement network switch (e.g., a packet processing system based on software such as packet processing software40, flow table28, and controller clients30). Switch14, which may sometimes be referred to as a virtual switch, forms a type of packet forwarding system that can forward packets between respective virtual machines44.

Network switches such as network switch14ofFIG. 1may be implemented using control circuitry that is coupled to one or more high-speed switching integrated circuits (“switch ICs”). This type of configuration is shown inFIG. 4. As shown inFIG. 4, controller server18on computing equipment12may communicate with network switch14via path16. Switch14may include processing circuitry24and one or more associated switch ICs32such as switch IC32-1. . . switch IC32-N. Control circuitry24may be, for example, based on a microprocessor and memory. Switch ICs32-1. . .32-N may be dedicated switching circuits that are capable of handling packet processing tasks at high speeds. As an example, control circuitry24may be based on a 500 MHz microprocessor and switch ICs32-1. . .32-N may be capable of handling data from 48 of input-output ports34, each of which has an associated data rate of 1-10 Gbps (as an example).

Another illustrative switch architecture that may be used in implementing network switch14ofFIG. 1is shown inFIG. 5. In theFIG. 5example, switch (packet forwarding system)14may include a master processor such as processor24-1and one or more associated slave processors such as slave processor24-2. Switch ICs32and slave processors such as processor24-2may be implemented on line cards such as line card48. One or more line cards such as line card50may contain processing circuitry (e.g., a microprocessor and memory). Line cards48and50may be interconnected using backplane52.

With an arrangement of the type shown inFIG. 5, the controller server may be implemented using the processing resources of a line card. For example, the controller server may be implemented on line card50as illustrated by controller server18-B ofFIG. 5. If desired, the controller server may be implemented on computing equipment12(e.g., as controller server18-A ofFIG. 5). Controller server18-A or controller server18-B may communicate with controller clients30that are implemented using processors such as processor24-1and/or24-2. Communications between controller server18-A and the controller clients may take place over network connection16. Communications between controller server18-B and the controller clients may take place over backplane52(e.g., over a network connection using a protocol such as TCP/IP).

As shown inFIG. 6, controller server18and controller client30may communicate over network path66using network protocol stacks such as network protocol stack58and network protocol stack60. Stacks58and60may be, for example Linux TCP/IP stacks or the TCP/IP stack in the VxWorks operating system (as examples). Path66may be, for example, a path that supports a network connection between switch14and external equipment (e.g., network path16ofFIG. 1) or may be a path that supports a network connection in backplane52in switch14, as shown inFIG. 5. Arrangements in which path66is network path such as path16are sometimes described herein as an example.

Control protocol stack56serves as an interface between network protocol stack58and control software54. Control protocol stack62serves as an interface between network protocol stack60and control software64. During operation, when controller server18is communicating with controller client30, control protocol stacks56generate and parse control protocol messages (e.g., control messages to activate a port or to install a particular flow table entry into flow table28). By using arrangements of the type shown inFIG. 6, a network connection is formed over the link between controller server18and controller client30. Controller server18and controller client30can communicate using a Transmission Control Protocol (TCP) or User Datagram Protocol (UDP) over Internet Protocol (IP) network connection. Examples of control protocols that may be used when communicating between controller server18and controller clients30over the network connection include SNMP and OpenFlow protocol stack version 1.0.0 (as examples).

Flow table28contains flow table entries (e.g., rows in the table) that have multiple fields (sometimes referred to as header fields). The fields in a packet that has been received by switch14can be compared to the fields in the flow table. Each flow table entry may have associated actions. When there is a match between the fields in a packet and the fields in a flow table entry, the corresponding action for that flow table entry may be taken.

An illustrative flow table is shown inFIG. 7. As shown inFIG. 7A, table28may have flow table entries (row)68. Each flow table entry may be associated with header70, action72, and statistics74. Headers70may each include multiple header fields76. The action in each flow table entry indicates what action switch14is to perform on the packet when a match is detected between the fields in the packet and the corresponding fields in the header of that flow table entry. Switch14may maintain statistical data (counter values) in the statistics portion of flow table28that can be queried by controller server18when it is desired to obtain information on the performance of switch14.

The header fields in header70(and the corresponding fields in each incoming packet) may include the following fields: ingress port (i.e., the identity of the physical port in switch14through which the packet is being received), Ethernet source address, Ethernet destination address, Ethernet type, virtual local area network (VLAN) id, VLAN priority, IP source address, IP destination address, IP protocol, IP ToS (type of service) bits, Transport source port/Internet Control Message Protocol (ICMP) Type (sometimes referred to as source TCP port), and Transport destination port/ICMP Code (sometimes referred to as destination TCP port). Other fields may be used if desired.

Each flow table entry (flow entry) is associated with zero or more actions that dictate how the switch handles matching packets. If no forward actions are present, the packet is preferably dropped. The actions that may be taken by switch14when a match is detected between packet fields and the header fields in a flow table entry may include the following actions: forward (e.g., ALL to send the packet out on all interfaces, not including the incoming interface, CONTROLLER to encapsulate and send the packet to the controller server, LOCAL to send the packet to the local networking stack of the switch, TABLE to perform actions in flow table28, IN_PORT to send the packet out of the input port, NORMAL to process the packet with a default forwarding path that is supported by the switch using, for example, traditional level 2, VLAN, and level 3 processing, and FLOOD to flood the packet along the minimum spanning tree, not including the incoming interface). Additional actions that may be taken by switch14include: an enqueue action to forward a packet through a queue attached to a port and a drop action (e.g., to drop a packet that matches a flow table entry with no specified action). Modify-field actions may also be supported by switch14. Examples of modify-field actions that may be taken include: Set VLAN ID, Set VLAN priority, Strip VLAN header, Modify Ethernet source MAC (Media Access Control) address, Modify Ethernet destination MAC address, Modify IPv4 source address, Modify IPv4 ToS bits, Modify transport destination port.

FIG. 7Bis an illustrative flow table having three flow table entries. The entries include fields with wildcards (e.g., “*” symbols). When a wildcard is present in a particular field, all incoming packets will be considered to form a “match” with respect to the field, regardless of the particular value of the field in the incoming packet.

The entry of the first row of theFIG. 7Btable directs the switch in which the flow table entry is operating to perform Ethernet switching. In particular, incoming packets with matching Ethernet destination addresses are forwarded to port3.

The entry of the second row of table ofFIG. 7Billustrates how a switch may be configured to perform internet routing (i.e., packets are forwarded based on their destination IP address).

The third row of the table ofFIG. 7Bcontains an entry that illustrates how a switch may be configured to perform firewalling. When a packet is received that has a destination IP port value of80, that packet is dropped (i.e., the switch is configured to serve as a firewall that blocks port80traffic).

Flow table entries of the type shown inFIG. 7Bmay be loaded into a switch14by controller server18during system setup operations or may be provided to a switch14from controller server18in real time in response to receipt and processing of packets at controller server18from switch14. In a network with numerous switches14, each switch can be provided with appropriate flow table entries to form a path through the network.

Illustrative steps that may be performed by switch14in processing packets that are received on input-output ports34are shown inFIG. 8. At step78, switch14receives a packet on one of its ports (e.g., one of input-output ports34ofFIG. 1).

At step80, switch14compares the fields of the received packet to the fields of the flow table entries in the flow table28of that switch to determine whether there is a match. Some fields in a flow table entry may contain complete values (i.e., complete addresses). Other fields may contain wildcards (i.e., fields marked with the “don't care” wildcard character of “*”). Yet other fields may have partially complete entries (i.e., a partial address that is partially wildcarded). Some fields may use ranges (e.g., by restricting a TCP port number to a value between 1 and 4096) and in effect use the range to implement a type of partial wildcarding. In making field-by-field comparisons between the received packet and the flow table entries, switch14can take into account whether or not each field in the flow table entry contains a complete value without any wildcarding, a partial value with wildcarding, or a wildcard character (i.e., a completely wildcarded field).

If it is determined during the operations of step80that there is no match between the fields of the packet and the corresponding fields of the flow table entries, switch14may send the packet to controller server18over link16(step84).

If it is determined during the operations of step80that there is a match between the packet and a flow table entry, switch14may perform the action that is associated with that flow table entry and may update the counter value in the statistics field of that flow table entry (step82). Processing may then loop back to step78, so that another packet may be processed by switch14, as indicated by line86.

FIG. 9is a diagram of an illustrative network showing how controller server18may control multiple switches14using multiple associated network connections16. In the illustrative network shown inFIG. 9, a first end host (the end host88on the left side ofFIG. 9) is communicating with a second end host (the end host88on the right side ofFIG. 9). End hosts88may be computers (e.g., personal computers), servers, clusters of computers, set-top boxes, handheld devices, or any other computing equipment. During part of the communications between end hosts88, the first end host may be serving as a packet source and the second end host may be serving as a packet destination. At other times, roles may be reversed, so that the second end host is serving as a packet source while the first end host is serving as a packet destination.

To ensure that packets are forwarded correctly through the network, controller18may provide each of the switches shown inFIG. 9with appropriate flow table entries. With one suitable arrangement, controller server18may supply switches14with flow table entries in response to receipt of a packet that has been sent to controller server18from a switch that did not detect a match between an incoming packet and its flow table entries. When controller server18receives the packet, controller server18can use network configuration rules20(FIG. 1), information from the packet, network topology information, and other information in determining appropriate entries for flow tables28for switches14. Controller server18may then provide the flow table entries to switches14to configure the switches for forwarding packets through the network. With another suitable arrangement, controller server18provides flow tables28to switches28during setup operations.

Regardless of whether controller server18provides switches14with flow table entries in advance or in real time in response to receipt of a packet from a switch, once each switch14has been provided with the flow table entries, the flow table entries will ensure that the switches14will forward the packets along a satisfactory path through the network.

The ability of controller server18to provide switches14with appropriate flow table entries relies on knowledge of the topology of the network. Controller server18may obtain network topology information by gathering information from switches14on the types of connections each of switches14has made with nearby switches. This information may then be processed by controller server18to determine the topology of the network. For example, controller server18can determine whether switches14are organized in clusters that are separated by network equipment that is not configured by controller server18.

An illustrative network100of the type that may contain switches14that are configured by controller server200and switches (e.g., switch106) that are not configured by controller server200is shown inFIG. 10. Network100may include end hosts such as end hosts EH1and EH2. Network100may also include switches such as switches14that are configured by controller server200. Switches14contain controller clients that communicate with controller server200, so switches such as switches14are sometimes referred to herein as client switches. Switches such as switch106do not contain a controller client that communicates with controller server200and are not configured by controller server200. Switches such as switch106are therefore sometimes referred to as switches without controller clients (non-client switches).

As shown inFIG. 10, client switches14in network100may be organized into client switch clusters that are separated by networks comprised of non-client switches such as switch106. Client switch clusters may sometimes be referred to herein as switch clusters or clusters. In the example ofFIG. 10, switches SW1, SW2, and SW3form client switch cluster102and switches SW4and SW5form client switch cluster104. Client switch clusters102and104may be separated by network106(e.g., packets sent between switch cluster102and switch cluster104must traverse network106). Network106may include one or more non-client switches configured in a network topology that routes packets between switch cluster102and switch cluster104. For illustrative purposes, network106is shown inFIG. 10as a single non-client switch SW6, but, in general, network106may include numerous switches. The example ofFIG. 10is merely illustrative.

When network100is first created, controller server200may require initialization of connections to the client switches in network100(e.g., controller server200may require address information from the client switches). The address information of controller server200may be well known, and client switches SW1, SW2, SW3, SW4, and SW5may initiate TCP/IP connections with controller server200over network paths66. Controller server200may maintain independent Transmission Control Protocol/Internet Protocol (TCP/IP) connections with each client switch. These connections, which may pass through one or more switches in the network, are illustrated as paths66inFIG. 10andFIG. 6. Controller server200may communicate with client switches SW1, SW2, SW3, SW4, and SW5of network100using the independent TCP/IP connections with each client switch.

Controller server200may communicate with each switch in network100to obtain information about available switch ports, switch port speed, and other switch characteristics. Client switches may respond with messages such as switch features reply message150ofFIG. 11. As shown inFIG. 11, the switch features reply message150that is sent by each client switch may include fields containing information such as switch identification information (e.g., a switch identifier DPID that identifies the switch) and information on the ports of the switch (i.e., a port list of physical input-output ports).

Controller server200may issue commands to individual switches in network100that direct each switch to complete specific tasks. For example, to determine the direct links between switches in the network, controller server200may use the Link Layer Discovery Protocol (LLDP). The LLDP protocol may require client switches to send controller-generated messages out of specific ports. These messages may then be processed by controller server200to determine the topology of the network.

As an example, controller server200may send messages to each client switch instructing the switch to send a controller-generated packet such as LLDP message152ofFIG. 12to a specific port on the switch. LLDP message152may contain fields with information such as the identification of controller server200(controller ID), the source switch (switch ID), and the source port (port ID). As an example, controller server200may send a “packet out” message154to switch SW1that directs switch SW1to send a controller-generated LLDP packet to port A on switch SW1. “Packet out” message154may contain fields with information such as the controller's command (e.g., “packet out”), the port to send the controller-generated packet to (e.g., port ID), the controller-generated packet (e.g., LLDP message), and other pertinent information.

Controller server200may instruct each client switch to forward all network packets from unmapped sources (e.g., switches that have not been mapped in the network topology) to the controller server. Switches may forward network packets to the controller server using messages such as “packet in” message156. “Packet in” message156may include fields with information such as the source switch ID (e.g., source switch identifier DPID), source port, message identifier describing the type of message (e.g., “packet in”), and a payload (e.g., the packet received from an unmapped source). For example, an LLDP message received by switch SW3of network100ofFIG. 10on port Q from unmapped switch SW1may be forwarded from switch SW3to controller server200using a “packet in” message156with source switch ID SW3, source port Q, message identifier “packet in,” and the entire received LLDP message as the payload.

Non-client switches do not have an open TCP/IP connection with controller server200and will not recognize the controller identifier (controller ID) of LLDP messages152received from client switches. Non-client switches that receive LLDP messages generated by controller server200may not respond. Controller server200will not receive messages from non-client switches in response to controller-generated LLDP packets.

Using the information obtained from the client switches (e.g., “packet-in” messages containing LLDP messages from each switch), controller server200may generate databases describing the topology of the network. For example, controller server200may generate network topology data structure (database)250for network100, as shown inFIG. 15. Each entry in network topology data structure250contains information describing a pair of connected network client switches. For example, the first entry of network topology data structure250represents how source port A of switch SW1is connected to destination port Q of switch SW3, and the second entry of network topology data structure250represents how source port Q of switch SW3is connected to destination port A of switch SW1.

Network topology data structure250may be formed from a table, multiple tables, arrays, trees, or one or more other data structure suitable for storing network topology information. Arrangements in which network topology data structure250is formed from a table (i.e., a network topology table) are sometimes described herein as an example. This is, however, merely illustrative. Any suitable type of data structure(s) may be used in forming network topology data structure250. Network topology data structure(s)250may be stored at a single location. If desired, network topology data structure250may be stored at multiple locations or formed from data structures stored at multiple locations. For example, network topology data structure250may be partitioned into two or more sections that are stored at two or more controller servers200.

To assist controller server200in creating flow table entries for network switches14, controller server200may provide table250with information on the clustering of client switches. Controller server200may use information obtained from each client switch along with information in the network topology data structure to determine how the client switches are clustered. In particular, controller server20may determine how the client switches are organized into independent clusters (islands) of switches separated by non-client switches. Controller server200may determine that switches SW1, SW2, and SW3of network100belong to a first cluster I, and that switches SW4and SW5belong to a second cluster II. As shown inFIG. 16, controller server200may update network topology data structure250to reflect the clustering of switches (i.e., to assign cluster identifiers to the switch entries that indicate which cluster each switch is located in).

During operation, network switches14may use their control resources (e.g., control unit24ofFIG. 1, etc.) to collect information about end hosts that communicate with the switch. This information may be stored in databases on the switches. These databases, which are sometimes referred to as per-switch forwarding databases, reflect which end hosts are associated with each port in each switch. A respective per-switch forwarding database may be stored in storage at each switch.

In the example ofFIG. 17, per-switch forwarding databases260for switches SW1, SW2, and SW3of network100contain routing information for end hosts EH1and EH2that is specific to each switch. For example, per-switch forwarding database260for switch SW1may contain an entry that reflects that traffic for end host EH1is handled using port D and an entry that reflects that traffic for end host EH2is handled using port A. Per-switch forwarding database260for switch SW2may contain an entry that reflects that traffic for end host EH1is handled using port Q and an entry that reflects that traffic for end host EH2is handled using port R. Per-switch forwarding database260for switch SW3may contain an entry that reflects that traffic destined for end host EH1is handled using port W and an entry that reflects that traffic destined for end host EH2is handled using port X. The tables ofFIG. 10are merely illustrative. Per-switch forwarding databases260for switches SW1, SW2, and SW3may contain routing information for many end hosts and switch ports. This information may change in response to the addition or removal of end hosts.

To assist in determining the topology of network100and using this information in generating flow table entries, controller server200may request that switches14provide controller server200with information regarding the connections between clusters. For example, to identify a network path between end host EH1in cluster I and end host EH2in cluster II, network controller200may obtain information from switches14regarding the network connection between cluster I and cluster II.

In particular, controller server200may use per-switch forwarding databases from each client switch along with information from network topology data structure250to identify the network connections between clusters. The cluster connection information may then be stored in databases such as per-cluster forwarding databases270ofFIG. 18. In the example ofFIG. 18, per-cluster forwarding database270for cluster I indicates that traffic for end host EH1uses port C of switch SW1and traffic for end host EH2uses port X of switch SW2. Per-cluster forwarding database270for cluster II indicates that traffic for end host EH1uses port Y of switch SW4and traffic for end host EH2uses port F of switch SW5.

The messages and tables described in connection withFIGS. 11-18may be used to identify client switch clusters and create per-cluster forwarding databases for generating flow table entries for each client switch. The flow chart inFIGS. 19A and 19Billustrates a process that may be used in identifying client switch clusters and generating per-cluster forwarding databases for the identified clusters.

During the operations of initialization step302ofFIG. 19A, controller server200may power on and wait for incoming connections from client switches14.

During the operations of connection setup step304, after each client switch is manually initialized with the internet protocol (IP) address of the controller, each individual client switch may initiate and establish a separate TCP/IP connection with the controller server. The established TCP/IP connections with the controller server may be left open until the client switch is disconnected from the network or the controller server terminates the connection.

During the operations of step306, controller server200may obtain information regarding the capabilities of each client switch (e.g., a switch identifier and a list of physical ports). To obtain switch capabilities information, controller server200may send a “switch features” request message to each client switch. Upon receiving a “switch features” request message, each client switch may send a “switch features” reply message150containing the requested information to controller server200.

During the operations of step308, upon receiving all of the “switch features” reply messages, controller server200may generate a link layer discovery protocol (LLDP) message152for each port of each client switch. Each LLDP message may contain information such as the controller server's identifier (controller ID), the source client switch (switch ID), and the source client port (port ID). For example, an LLDP message for port A of client switch SW1may have a switch ID of “SW1” and port ID of “A.” Controller server200may then send a “packet out” message154with port ID set to the source client port of the LLDP message and the respective LLDP message as the payload. Each client that receives a “packet out” message may send the payload of the received “packet out” message (e.g., the respective LLDP message) to the port specified by the port ID field of the received “packet out” message.

During the operations of step310, upon receiving an LLDP message from another client switch, each client switch may forward the received LLDP message to controller server200. Each client switch may forward the LLDP message as the payload of a “packet in” message156.

During the operations of step312, controller server200may use the received “packet in” messages156from each client switch of network100to generate network topology data structure250. As an example, an LLDP message that controller server directed switch SW1to send out through port A (step308) may be received by switch SW3through port Q and forwarded to controller server200(step310). Controller server200may then add an entry to network topology data structure250showing that source port A of source switch SW1is connected to destination port Q of destination switch SW3(FIG. 15).

During the operations of step314, controller server200may produce information identifying the clusters of switches14in network100using network topology data structure250. Controller server200may then update network topology data structure250with this cluster information.

During the operations of step316, controller server200may generate per-cluster forwarding databases using updated network topology data structure250and the per-switch forwarding databases.

During the operations of step318, controller server200may use updated network topology data structure250and per-cluster forwarding databases to assist in generating flow tables for each client switch.

To determine the cluster information in step314ofFIG. 19B, controller server200may follow the steps shown in the flowchart ofFIG. 20.

During the operations of step402, controller server200creates a list of unvisited switches (nodes) and places all client switches in the list of unvisited switches. In step404, controller server200creates a new empty cluster list and assigns a new cluster ID to the new empty cluster list (e.g., the first empty cluster list may be assigned cluster ID I). The network topology data in data structures such as data structure250corresponds to a graph in which graph nodes represent switches and graph edges represent links between switches. The graph may be a directed graph (i.e., a graph in which the links are directional) or an undirected graph (i.e., a graph in which the links represent connections between switches, but not the directions of the links). In steps406and408, controller server200chooses a switch from the list of unvisited switches and performs a graph search on the chosen switch (i.e., a directed graph search or an undirected graph search) to identify all switches that are directly and indirectly connected to the selected switch. The graph search may be a depth first search (DFS), a breadth first search (BFS), or any other suitable graph search in which the connections between switches serve as graph edges and the switches serve as graph nodes. In step410, controller server200adds the switches identified by the graph search to the current empty cluster list, updates network topology data structure250to reflect the identified cluster, and removes the identified switches from the list of unvisited switches. In step412, the controller server checks whether all client switches have been assigned a cluster ID (i.e., controller server200determines whether the list of unvisited switches is empty). Until the list of unvisited switches is empty, controller server200repeats steps404to412.

As an example, controller server200may select switch SW1from the list of unvisited switches created from network100. Controller server200may perform a DFS search on switch SW1that may identify switches SW2and SW3as being connected to SW1. Switches SW1, SW2, and SW3may then be assigned cluster ID I, and network topology data structure250and the list of unvisited switches may be updated accordingly. The list of unvisited switches for network100may still have members (e.g., SW4and SW5may still be in the list). Controller server200may therefore select SW4and perform a DFS search on SW4, identifying SW5as being connected to SW4. Controller server200may then assign cluster ID II to SW4and SW5and update network topology data structure250and the list of unvisited switches. The use of distinct cluster IDs for each cluster reflects how the clusters of client switches are isolated from one another by interposed non-client switches. Following the identification of all switches in cluster II, the list of unvisited switches will be empty (i.e., all clusters will have been identified in this example).

To generate per-cluster forwarding tables270during the operations of step316, controller server may follow the steps illustrated in the flow chart ofFIG. 21.

During the operations of step450, controller server200may select a first switch in the network topology data structure.

During the operations of step452, controller server200may use network topology data structure250to determine the cluster ID of the selected switch (e.g., switch SW1belongs to cluster ID I).

During the operations of step454, the controller server may select the first entry in per-switch forwarding database260associated with the selected switch (e.g., the first entry of per-switch forwarding database260associated with switch SW1).

During the operations of step456, the controller server may search network topology data structure250for an entry containing both the selected switch and the port described in the selected entry of per-switch forwarding database260(e.g., the controller server may search network topology data structure250for entries containing either a source switch-port pair or destination switch-port pair that matches the switch-port pair “switch SW1, port D” from the per-switch forwarding database). In this way, controller server200processes the per-switch forwarding table entries by attempting (for each per-switch forwarding table entry) to match a switch-port pair associated with that entry with a corresponding switch-port pair in an entry in the network topology data structure.

If network topology data structure250contains the selected switch and port pair (i.e., the switch is connected to another client switch on the specified port), controller server200may select the next entry in the per-switch forwarding database260associated with the selected switch (as described in step462) and return to step456.

During the operations of step458, in response to a determination by controller server200that network topology data structure250does not contain the selected switch-port pair (i.e., the switch is connected to either an end host or a non-client network on the specified port), controller server200may add an entry to per-cluster forwarding database270associated with the cluster ID of the selected switch. In other words, in response to a determination that the switch-port pair associated with an entry in the per-switch forwarding database entry does not correspond to a switch-port pair in the network topology data structure, that switch-port pair is added to an appropriate per-cluster forwarding database. The entry added may include the destination host from the selected entry of per-switch forwarding database260associated with the selected switch. The entry added may include the selected switch and port pair. For example, network topology data structure may not contain the switch and port pair “switch SW1, port D.” Controller server200may add an entry to per-cluster forwarding database270for cluster I with the information “end host EH1, switch SW1, port D.” The entry added may be used in generating flow table entries that forward network traffic in cluster I that is destined for end host EH1to port D of switch SW1.

During the operations of step460, the controller server may determine whether all of the entries in per-switch forwarding database260associated with the selected switch have been analyzed during the operations of step456and step458. If unprocessed entries remain, controller server200may perform the operations of step462(e.g., select the next entry in per-switch forwarding database associated with the selected switch) and return to step456.

During the operations of step464, controller server200may determine whether all of the client switches in network topology data structure250have been processed in steps452through460. If unprocessed switches remain, controller server200may perform the operations of step466(e.g., controller server200may select the next remaining switch in network topology data structure250) and return to step452.