Systems and methods for controlling network switches using a switch modeling interface at a controller

The controller may include a switch modeling interface that maintains switch models of switches in a network. The switch modeling interface may receive a desired network configuration from application modules that respond to network events. The switch modeling interface may compare the desired network configuration with the current network configuration represented by the switch models. The switch modeling interface may generate control messages to the switches for only identified differences between the desired network configuration and the current network configuration as identified by the switch models. The differences may be identified based on digest values retrieved from the switches. The switch modeling interface may determine whether the control messages were successfully received and processed by a switch and may indicate success or failure to the application module that provided the desired network configuration.

BACKGROUND

This relates to communication networks, and more particularly, to communication networks having network switches that are controlled by a controller.

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. The packets may be sometimes referred to as frames. For example, data is forwarded over layer 2 of the Open Systems Interconnection (OSI) model as frames (e.g., Ethernet frames), whereas data is forwarded over layer 3 of the OSI model as packets (e.g., Internet Protocol packets).

It can be difficult or impossible to configure 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.

It can be challenging for a controller to ensure that switches are successfully configured as the controller intended. Consider the scenario in which a controller provides thousands of control packets to a switch, but the switch processing capacity is insufficient to process the control packets at the rate they are provided by the controller. As another example, configuration storage capacity at a switch may be filled and the switch may be incapable of storing any additional configuration data without overwriting existing configuration data. As yet another example, a new switch may connect or an existing switch may disconnect from the network, which may lead to mismatch between the controller's view of the network and the actual configuration state of the network.

SUMMARY

A controller may control switches in a network having end hosts that are coupled to the switches. The controller may include a switch modeling interface that maintains switch models of the switches in the network and uses the switch models in generating control messages for the switches to implement desired network configurations. The switch modeling interface may receive a desired network configuration from application modules that respond to network events such as connection or disconnection of a switch or new network policies. The desired network configuration may include a set of tables and a function. The switch modeling interface may operate the function on the set of tables to produce the desired network configuration. For example, the set of tables may include a host table identifying end host attachment points and an inter-switch forwarding table. In this scenario, the switch modeling interface may operate the function on the host table and the inter-switch forwarding table to produce switch-specific forwarding tables for each of the switches.

The switch modeling interface may compare the desired network configuration (e.g., the switch-specific forwarding tables) with the current network configuration represented by the switch models. The switch modeling interface may generate control messages to the switches for only identified differences between the desired network configuration and the current network configuration as identified by the switch models. The switch modeling interface may determine whether the control messages were successfully received and processed by a switch by sending a synchronization request message (e.g., a barrier request message) along with the control messages and waiting for a synchronization reply message (e.g., barrier reply message), an error message, or failure of the switch to respond (e.g., expiration of a timer). The switch modeling interface may indicate success or failure to the application module that provided the desired network configuration.

The switch modeling interface may update the switch models by communicating with the switches. To help reduce the traffic load on network control paths, the switches may be configured to maintain digest tables. A digest table maintained by a switch may include a plurality of entries (e.g., buckets) each associated with a respective digest value. Switch configuration data such as forwarding table entries received at the switch (e.g., via control messages from the controller) may be hashed by the switch and assigned to a selected table entry based on the hashed value. The switch may compute the digest value of each table entry as an XOR of the hashed values assigned to that table entry. The digest values maintained by a switch may be retrieved by the controller and compared to digest values computed by the controller for a desired network configuration. The switch modeling interface at the controller may determine what switch configuration data should be updated in implementing a desired network configuration based on the comparison.

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 such as portable electronic devices that access the network using wired or wireless technologies.

Network switches range in capability from relatively small Ethernet switches and wireless access points to large rack-based systems that include multiple line cards, redundant power supplies, and supervisor capabilities. It is not uncommon for networks to include equipment from multiple vendors. 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 such as a controller server or distributed controller server may interact with each of the control clients over respective network links. The use of a cross-platform controller 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. Controller 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 server18can 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 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 packet 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. As another example, rules20may include service insertion policies identifying network traffic and services that are to be performed on the identified network traffic. 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 (e.g., each packet forwarding system)14may have input-output ports34(sometimes referred to as network switch interfaces). 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 server18may be compliant with a network switch protocol such as the OpenFlow protocol (see, e.g., OpenFlow Switch Specification version 1.0.0, 1.3.1, or other versions of the OpenFlow protocol). 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).

The example of flow tables28storing data that determines how switch14is to process incoming packets are merely illustrative. If desired, any packet forwarding decision engine may be used in place of or in addition to flow tables28to assist packet forwarding system14to make decisions about how to forward network packets. As an example, packet forwarding decision engines may direct packet forwarding system14to forward network packets to predetermined ports based on attributes of the network packets (e.g., based on network protocol headers).

Any desired switch may be provided with controller clients that communicate with and are controlled by a controller server. For example, switch14may be implemented using a general purpose processing platform that runs control software and that omits packet processing circuitry32. As another example, switch14may be implemented using control circuitry that is coupled to one or more high-speed switching integrated circuits (“switch ICs”). As yet another example, switch14may be implemented as a line card in a rack-based system having multiple line cards each with its own packet processing circuitry. The controller server may, if desired, be implemented on one or more line cards in the rack-based system, in another rack-based system, or on other computing equipment that is coupled to the network.

As shown inFIG. 2, 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 backbone path in a rack-based system. Arrangements in which path66is a 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. 2, 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 corresponding 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. 3. As shown inFIG. 3, table28may have flow table entries (rows)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) identification (sometimes referred to as a VLAN tag), 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. For example, a network protocol field and a protocol port field may be used.

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 forwarding 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 (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 VLAN tag, 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. The modify-field actions may be used in rewriting portions of network packets that match on the flow table entry.

FIG. 4is 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. Additional fields may match additional packet information (e.g., packet header information of network packets).

The entry of the first row of theFIG. 4table 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 port 3.

The entry of the second row of table ofFIG. 4illustrates 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. 4contains 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 of 80, 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. 4may 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 switches such as 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. 5. 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 (e.g., 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 (e.g., 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., completely wildcarded field).

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

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. 6is a diagram of an illustrative network100in which switches may be controlled by a controller18. Controller18may be a controller server or a distributed controller implemented across multiple computing equipment. As shown inFIG. 6, network100may include switches SW1and SW2. Controller18may be coupled to the switches of network100via control paths66. Controller18may control the switches using control paths66(e.g., by providing flow table entries such as flow table entries68of FIG.3). The switches may include switch ports that are coupled to end hosts or to other switches. In the example ofFIG. 6, end hosts EH1and EH3are coupled to respective ports P1and P3of switch SW1, end hosts EH2and EH4are coupled to respective ports P1and P2of switch SW2, and switches SW1and SW2are coupled via port P2of switch SW1and port P3of switch SW2.

Controller18may include one or more application modules102that control the operations of switches in a network. For example, a first application module102may organize switches into virtual switches formed from groups of end hosts or ports on the switches. In this scenario, the first application module may control underlying switches SW1and SW2of the network in enforcing network policy and forwarding at the virtual switch level (e.g., the network policies may be defined for virtual switches and not the underlying switches). As another example, a second application module102may handle network monitoring functions such as analyzing network traffic to generate network traffic reports. The application modules may generate and provide desired network configurations (e.g., of the entire network) to switch modeling interface104. Switch modeling interface104may use switch models108in implementing the desired network configurations and may indicate to the application modules whether the implementation is successful or has failed.

Modules such as modules102may be implemented at controller18as software on general-purpose or application-specific computing equipment or dedicated hardware. For example, modules102may be implemented as software modules on shared computing equipment. As another example, modules102may be implemented on different computing equipment in a distributed controller arrangement.

Application modules102may control switches based on network topology information maintained at the application modules or maintained by other modules of controller18. However, there may be hundreds, thousands, or more switches in a network. It can be challenging for application modules102to ensure that control messages sent to the switches of a network are successfully received or executed by the switches. In addition, multiple application modules102may be implemented at a controller18and potentially conflict each other. Consider the scenario in which a switch fails to implement a flow table entry received from controller18. In this scenario, the state of the switch may not match the expected state and subsequent flow table entries provided by the controller may produce an undesired network configuration.

Controller18may be provided with a switch modeling interface module104that handles communications with the switches and maintenance of switch states. Switch modeling interface module104may help to ensure that application modules102are synchronized with the switches of the network. Switch modeling interface104may implement models108that represent each switch in the network. For example, switch model MSW1may represent switch SW1, whereas switch model MSW2may represent switch SW2. Switch models MSW1and MSW2may maintain information on the current state of respective switches SW1and SW2. For example, switch model MSW1may maintain information identifying the forwarding rules or policies that are implemented at switch SW1, whereas switch model MSW2may identify the state of switch SW2.

Switch models108may be controlled by control module106. Control module106may control switch models108and issue control messages to switches of the network in fulfilling network control requests from application modules102. Switch models108may be implemented as a data construct as a set of tables.FIG. 7is a diagram of an illustrative switch model for switch SW1(e.g., switch model MSW1ofFIG. 6). As shown inFIG. 7, switch model112includes information on the state of corresponding switch SW1. The switch state may include end host attachment points, forwarding rules, or other tables storing information on the state of switch MSW1. (e.g., the current switch configuration).

With reference to the exemplary network ofFIG. 6, switch model112for switch SW1may include information identifying end hosts and which switch ports are coupled to the end hosts. End host EH1may be identified as being attached to port P1of switch SW1, whereas end host EH3may be identified as connected to port P3of switch SW1. End hosts that are not directly attached to switch SW1may be identified by a port through which those end hosts may be reached from switch SW1. For example, end hosts EH2and EH4may be identified as being coupled to port P2of switch SW1, because packets forwarded from port P2of switch SW1may reach end hosts EH2and EH4through port P2. Switch model112may include forwarding rules that govern how network traffic is to be forwarded by switch SW1. As an example, the forwarding rules may be stored as a table that includes entries defining how switch SW1is to forward network packets for each end host. The forwarding rules may be stored in the switch model as per-switch forwarding rules or may be stored as global, network-wide rules (e.g., tables) that are converted to switch-specific rules via one or more functions that operate on the global rules.

Switch model112may include any information on the state of the corresponding switch (e.g., switch SW1). For example, switch model112may include a link aggregation group (LAG) table having entries that define link aggregation groups. Each link aggregation group may be assigned a group of ports of the switch that serves as a logical port (e.g., multiple physical ports of the switch may form a link aggregation group through which network traffic is forwarded and received).

Switch modeling interface104may communicate with switches to monitor the status of the network. For example, control module106may send control messages to the switches and/or receive status messages from the switches in monitoring the status of the network. Control module106may update switch models in response to updated status information from the switches.FIG. 8is a diagram illustrating how switch model112ofFIG. 7may be updated in response to a status update identifying that end host EH1has been disconnected from switch SW1. For example, switch SW1may send a port down message to control module104over control paths66. In this scenario, the port down message may identify that port P1of switch SW1is disconnected and may be sent immediately in response to electrical sensor data at switch SW1or in response to a control message sent from controller18to switch SW1.

As shown inFIG. 8, modified switch model114does not include any status information for end host EH1. In other words, control module104may remove end host EH1from any attachment point information, forwarding rules, or other tables.

Illustrative forwarding tables including entries that may be provided to switches are shown inFIG. 9. In the example ofFIG. 9, forwarding tables122and124are OSI layer-2 (L2) forwarding tables that operate on Ethernet Media Access Control addresses. Forwarding tables122and124may serve as flow tables or as subsets (e.g., portions) of flow tables for switches SW1and SW2. For example, control module106may provide flow table entries to switches SW1and SW2in populating forwarding tables122and124. Forwarding table122may be stored and used by switch SW1in determining how to forward network packets. Similarly, switch SW2may store and use forwarding table124in forwarding network packets.

Each entry of L2 forwarding table122for switch SW1may identity an end host Ethernet address and a port of switch SW1to which network traffic destined for the identified Ethernet address should be forwarded. A first L2 forwarding table entry may direct switch SW1to forward network packets destined for Ethernet address MACEH1(i.e., end host EH1) to port P1of switch SW1, because end host EH1is connected to port P1of switch SW1. Similarly, an L2 forwarding table entry may identify that network packets destined for end host EH3should be sent from port P3(i.e., the port to which end host EH3is attached). For end hosts such as end hosts EH2and EH4that are not directly attached to switch SW1, L2 forwarding table entries may be provided that direct switch SW1to forward network packets along a network path to the end hosts (e.g., port P2). Similarly, L2 forwarding table124for switch SW2includes entries identifying that network packets destined for Ethernet addresses MACEH1, MACEH2, MACEH3, and MACEH4should be forward to ports P3, P1, P3, and P2of switch SW2, respectively.

Copies of forwarding tables122and124may be stored by a switch modeling interface (e.g., as part of forwarding rules in switch model112ofFIG. 7). Control module106may maintain the local copies to help interface between application modules102and switches of the network. For example, control module106may use the local copies to simulate the effect of control messages that are provided to the switches. Control module106may, as a part of providing control messages to the switches, additional communicate with the switches to verify that the post-control message state at the switches matches the simulated state at switch models108.

It can be challenging for switch modeling interface104to maintain local copies of the state at all switches in a network. Consider the scenario in which a network includes hundreds of switches each having multiple forwarding tables (e.g., L2 forwarding tables, IP forwarding tables etc.). In this scenario, each switch may include hundreds of thousands of table entries that define the current state of that switch (e.g., forwarding table entries, address resolution table entries, link aggregation group table entries, etc.). Due to limited resources such as available memory at the controller, it may be difficult or impossible for the switch modeling interface to store each table entry of each switch.

The switch modeling interface at a controller may be configured to store one or more switch states as a global data construct and a per-switch function that operates on the global data to produce switch-specific state information.FIG. 10is an illustrative diagram showing how the switch state information in switch-specific forwarding tables ofFIG. 9may be stored as a global data construct including host table132and inter-switch forwarding table136.

Host table132includes host table entries134. that identify attachment points for end hosts. In the example ofFIG. 10, Ethernet address MACEH1of end host EH1is defined in a first host table entry134as being attached to port P1of switch SW1. Similarly, Ethernet address MACEH2is identified as being attached to port P1of switch SW2, Ethernet address MACEH3is identified as being attached to port P3of switch SW1, and Ethernet address MACEH4is identified as being attached to port P2of switch SW2. Host table132is not specific to any particular switch (e.g., host table132is a global table).

Inter-switch forwarding table136includes inter-switch forwarding table entries138that identify links between switches of the network. A first entry138may identify that network packets from switch SW1(e.g., a source switch) that are to be forwarded to switch SW2(e.g., a destination switch) should be forwarded from port P2of source switch SW1. A second entry138may identify that network packets from source switch SW2that are to be forwarded to destination switch SW1should be forwarded from port P3of switch SW2.

The example ofFIG. 10in which inter-switch forwarding links are identified based on traffic direction is merely illustrative. If desired, each pair of switches may be identified by the ports of the switches that are connected by a network link. For example, an entry138may identify a first switch SW1, a second switch SW2, and that port P2of first switch SW1is connected to port P3of second switch SW2. Inter-switch forwarding table136may therefore sometimes be referred to herein as an inter-switch link table or an inter-switch connections table, because table136identifies connections between switches of the network.

Host table132and inter-switch forwarding table136represent a global view of the network, thereby helping to remove redundancy of switch state information stored at the controller. For example, switch specific L2 forwarding tables122and124ofFIG. 9contain redundant information, because each table includes information that identifies where end hosts are connected from the perspective of the corresponding switch (i.e., table122identifies where end hosts are connected relative to switch SW1, whereas table124identifies where end hosts are connected relative to switch SW2). In a network with many switches (e.g., tens, hundreds, or more), the global tables ofFIG. 10may provide a substantial reduction in the number of entries that are stored by the controller (e.g., because the location of each end host is identified only once).

The switch modeling interface at a controller may be provided with a function that operates on one or more global tables to obtain switch-specific tables for switch models.FIG. 11is an illustrative diagram of a L2 forwarding table function (FL2TABLE)142that receives input data including an input switch and an input address and operates on host table132and inter-switch forwarding table136ofFIG. 10to produce switch-specific forwarding tables such as tables122and124ofFIG. 9.

To produce a switch-specific forwarding table entry for a particular end host of a switch, the switch modeling interface may provide the Ethernet address of that end host and identify that switch as the input address and input switch for function FL2TABLE. Function FL2TABLE may direct the switch modeling interface to examine the input address and the input switch. If an entry of host table132identifies that the input address is attached at the input switch, the corresponding port of that input switch may be retrieved from that entry and returned as the output of FL2TABLE. If the entry for the input address does not identify the input switch, function FL2TABLE may direct the switch modeling interface to return the port from the inter-switch forwarding table entry that matches the input switch and the switch identified by the host table entry.

Consider the scenario in which the switch modeling interface provides switch SW1and Ethernet address MACEH1as the inputs to function FL2TABLE. In this scenario, function FL2TABLE directs the switch modeling interface to retrieve the host table entry at input address MACEH1. The retrieved host table entry identifies switch SW1and port P1(seeFIG. 10), which matches the input switch and therefore port P1may be returned as the output of function FL2TABLE. A switch-specific L2 forwarding table entry for table122may be thereby generated that identifies Ethernet address MACEH1as being attached to port P1of switch SW1.

As another example, consider the scenario in which the switch modeling interface generates an L2 forwarding table entry for switch SW1and end host EH2by providing switch SW1and Ethernet address MACEH2as the inputs to function FL2TABLE. In this scenario, the switching modeling interface may retrieve the host table entry at input address MACEH2as instructed by function FL2TABLE. The retrieved host table entry identifies that Ethernet address MACEH2is attached at port P1of switch SW2, which does not match input switch SW1. In response, function FL2TABLE may instruct the switch modeling interface to retrieve the inter-switch connection table entry that matches input switch SW1and identified switch SW2. The retrieved entry138may identify that port P2of switch SW1is connected to switch SW2(see, e.g., the first entry of table136ofFIG. 10). Identified port P2of switch SW1may be returned as the output of function FL2TABLE. A switch-specific L2 forwarding table entry for table122may be thereby generated that identifies Ethernet address MACEH2as being coupled to port P2of switch SW1.

The example ofFIGS. 10 and 11in which global tables are used to help reduce the storage footprint of L2 forwarding information is merely illustrative. Controller18can be configured with global data constructs for any desired switch-specific information such as address resolution protocol tables, link aggregation group tables, or other information maintained at individual switches of a network. Controller18may be configured with any number of functions that operate on inputs and the global data constructs to reconstruct the switch-specific information.

Application modules such as application modules102ofFIG. 6may indicate desired modification to a network configuration by providing a network snapshot to the switch modeling interface. The switch modeling interface may communicate with the switches to implement the desired modifications while helping to ensure correctness using switch models.FIG. 12is an illustrative network snapshot152that may be provided by an application module to the switch modeling interface. Network snapshot152may include a set of desired switch states. In the example ofFIG. 12, snapshot152includes layer 2 forwarding tables L2TABLESW1and L2TABLESW2for switches SW1and SW2of the network (e.g., tables122and124ofFIG. 9). This example is merely illustrative. Snapshot152may include any desired switch-specific information that identifies desired states of switches in the network. In other words, snapshot152may define a desired network configuration to be implemented.

Application modules may be configured to provide global data constructs in addition to or instead of switch-specific state information to help reduce the amount of storage required at the controller. As shown inFIG. 13, a network snapshot162may include a host table and an inter-switch forwarding table (e.g., host table132and inter-switch forwarding table136ofFIG. 10). Network snapshot162may include function FL2TABLE that generates switch-specific state information from the global data structures (e.g., FL2TABLE142ofFIG. 11).

A network snapshot may include only switch-specific state information (e.g., snapshot152ofFIG. 12), only global state information, or a combination of switch specific and global state information. The information included in a network snapshot identifies a desired state of the network, which may be processed by the switch modeling interface to generate switch control messages for implementing the desired state of the network.FIG. 14is a flow chart200of illustrative steps that may be performed by a switch modeling interface in implementing desired changes to the configuration of a network based on network snapshots.

During step202, the switch modeling interface may receive a new snapshot indicating desired changes to be made to the configuration of the network (e.g., a desired network configuration). For example, snapshot152ofFIG. 12or snapshot162ofFIG. 13may be received.

During step204, the switch modeling interface may perform the operations of step206for each switch in the network (e.g., the switch modeling interface may select a switch, perform the operations of step206for the selected switch, select additional switch, and so on).

During step206, the switch modeling interface may perform the operations of step208-224for each table (e.g., switch-specific or global construct) in the received snapshot.

During step208, the switch modeling interface may determine whether the state of the selected switch is known (e.g., the switch selected during step204for processing). For example, the switch modeling interface may store information identifying when the information in each switch model108was last updated. The information may be stored as a timestamp on each table or on table entries in the switch models. In this scenario, the switch modeling interface may compare the timestamps associated with the selected switch with the current system time. If the difference in time exceeds a threshold, the switch modeling interface may determine that the current state of the selected switch should be updated.

In response to determining that the state of the selected switch is known from the switch models, the current switch state may be retrieved (e.g., from the corresponding switch model108) during step210and the operations of step214may be subsequently performed. In response to determining that the state of the selected switch is not known (e.g., the corresponding switch model108does not store up-to-date information), the switch modeling interface may communicate with the selected switch to retrieve its current switch state for updating the corresponding switch model before proceeding to step214. For example, the switch modeling interface may send control messages that direct the switch to respond with requested switch state information (e.g., an L2 forwarding table, an ARP table, etc.). The switch state information received from the switch may be used to update switch models108.

During step214, the switch modeling interface may compute the difference (Δ) between the current switch state and the new switch state defined in the received network snapshot. In scenarios in which the network snapshot and/or switch models are defined using a function that operates on global data constructs, the switch modeling interface may compute the switch-specific state information for the selected switch using the function and the global data constructs. The switch-specific information from the switch models and from the received snapshot may be compared directly. Alternatively, global constructs may be compared directly and differences identified in the global constructs may be used to identify differences in the corresponding switch-specific state information.

During step216, the switch modeling interface may use any computed differences between the current switch state and the new switch state to generate switch control messages that implement the desired new switch state. For example, the switch modeling interface may generate OpenFlow control messages that direct the selected switch to replace one or more current L2 forwarding table entries at the switch with L2 forwarding table entries from the desired switch state.

During step218, the switch modeling interface may provide the generated switch control messages along with a synchronization request message to the switch. The synchronization request message may direct the switch to provide a synchronization reply message in response to successful processing of the control messages. In other words, if the switch state modifications of the switch control messages are successfully implemented by the switch, the switch must respond with a synchronization reply message that may be received at the switch modeling interface of the controller during step220. If the switch control messages are not successfully processed at the switch, the switch may provide error messages or may fail to respond to the synchronization request. Error messages that may be received from a switch may identify the type of error that occurred at the switch. For example, an error message may identify that a table at the switch is full and new entries provided in the switch control messages cannot be stored. As another example, an error message may identify that the switch is incapable of performing the operations specified in the control message (e.g., an unsupported operations error). If desired, the control module may maintain a timer that is enabled when switch control messages are sent during step218. The timer may be configured with a value representative of the time period within which the switch is expected to provide a response (e.g., a synchronization reply or error message). In this scenario, the control module may identify an error in response to expiration of the timer.

The example ofFIG. 14in which switch control messages are sent out upon generation is merely illustrative. If desired, the switch control messages generated during step216may be accumulated and sent out in groups. In this scenario, a synchronization request may be sent out for each group of switch control messages and any synchronization reply messages may confirm a successful response for this entire corresponding group.

FIG. 15is a flow chart300of illustrative steps that may be performed by a controller having a switch modeling interface in controlling switches in a network (e.g., performed by controller18ofFIG. 6).

During step302, the controller may identify a network event. Network events may be identified or detected based on information received from a switch or from a user such as a network administrator. For example, connection or disconnection of an end host may be identified from a message received from a switch over control paths. As another example, a user may provide a new network policy that identifies a new desired network configuration (e.g., new forwarding table values, link aggregation group assignments, etc.).

During step304, an application module at the controller may generate a new network snapshot based on the network event (e.g., an application module102ofFIG. 6). For example, network snapshots such as snapshot152ofFIG. 12or snapshot162ofFIG. 13may be generated that indicates a desired network configuration in response to the network event. In response to end host disconnecting, an application module may generate a network snapshot that removes the end host from the network configuration. In response to an end host connecting, an application module may generate a network snapshot that adds the end host to the network configuration (e.g., adding the end host to forwarding tables while ensuring that the forwarding table entries satisfy existing network forwarding rules). In response to a new network policy, an application module may generate a network snapshot that applies the network policy to the existing network configuration (e.g., replacing or modifying existing table entries such as forwarding table entries).

During step306, the application module may send the new network snapshot to the switch modeling interface. During subsequent step308, the switch modeling interface may compute the difference (Δ) between the current network snapshot and the new snapshot. The current network snapshot may be stored at the controller or may be generated by communicating with the switches. During step310, the switch modeling interface may, for each switch in the network, reconcile the new snapshot with the current state at the switch to implement the new network snapshot. For example, the switch modeling interface may, in performing steps308and310, perform the steps of flow chart200ofFIG. 14. During step312, the switch modeling interface may notify the application module of success or failure in implementing the new network snapshot.

It can be challenging for the switch modeling interface to determine differences Δ between current switch states and a desired new network snapshot. For example, the state at a switch may include hundreds of thousands of table entries. It can be time consuming to transfer these table entries to the controller over control paths and calculate differences Δ. Switches in the network may be provided with hash capabilities that may be used by the controller to help with determining differences between current switch states and desired network snapshots.

FIG. 16is a flow chart400of illustrative steps that may be performed by a switch in generating digest identifiers from table entries that may help to improve performance of the switch modeling interface at the controller. The steps of flow chart400may, for example, be performed by circuitry at control unit24of switch14ofFIG. 1.

During step402, the switch may receive or otherwise process a table entry such as a forwarding table entry, link aggregation group table entry, address resolution protocol table entry, or other table entry that at least partially defines the configuration of the switch. For example, the table entry may be a flow table entry or a portion of a flow table entry provided by a controller.

During step404, the switch may compute a hash value for the table entry. The hash may be computed using any desired hashing algorithm. For example, the switch may use the Secure Hashing Algorithm (SHA) on the binary data of the table entry to produce the hash value.

The switch may maintain buckets (e.g., groups of zero or more entries) for organizing the table entries based on the hash values. During step406, the switch may assign the table entry to a bucket based on a portion of the hash value. For example, the first two, three, four, or any selected N number of bits of the hash may be used in determining which bucket to assign the table entry.

During step408, the switch may compute a digest value (e.g., a digest identifier) for the assigned bucket. The digest value may be computed by calculating a per-bit logic XOR over all of the entries in the assigned bucket. The switch may store the digest value for the assigned bucket and may, in response to requests from a controller, provide the digest values of the buckets.

FIG. 17is a diagram of an illustrative digest table412that includes buckets414. Digest table412may be maintained by a switch (e.g., at storage at the switch). Buckets414may be assigned table entries based on calculated hash values (e.g., during the operations of flow chart400ofFIG. 16). In the example ofFIG. 17, hashed table entries are assigned to buckets414based on the first two bits of the hash values for the hashed table entries. The number of hash value bits associated with each bucket may correspond to the number of buckets.

Each bucket414may include zero or more hashed table entries and a digest value calculated from the per-bit XOR of the hashed table entries (e.g., an XOR value of each bit position across all of the hashed table entries is computed to produce a digest value having the same total number of bits as each hashed table entry). Bucket 0 corresponds to a binary value of 00 and may have been assigned hashed table entries H1and H2starting with “00.” Similarly, bucket 1 (binary 01) may be assigned any entries starting with “01”, bucket 2 (binary 10) may be assigned entry H3that starts with “10”, and bucket 3 (binary 11) may be assigned entry H4that starts with “11.”

The digest of bucket 0 may be the XOR of hash values H1and H2. As an example, hash values H1and H2may be the hashed values of the first two L2 forwarding table entries of the table122ofFIG. 9. The digest of bucket 1 (binary value 01) may be zero, as no table entries have been assigned to bucket 1. Buckets H3and H4may have digests equal to respective hash values H3and H4, as only one table entry has been assigned to each of buckets H3and H4.

The example ofFIG. 17is which an XOR is computed from the hashed table entries of bucket414is merely illustrative. If desired, any logic function such as another hash function may be computed on the entries of each bucket414to produce a digest value for that bucket. The logic XOR function may be desirable because any one-bit change in the hashed table entries produces a different digest value. In addition, the digest value may be updated in response to addition or removal of hashed table entries by computing the XOR of the current digest value with the hash value to be added or removed (e.g., it is not necessary to re-compute the digest value from all of the hashed table entries in the bucket).

Digest values on network state (e.g., tables such as forwarding tables) maintained by switches may be used in determining whether a network snapshot of a desired network configuration is different from the existing network configuration.FIG. 18is a flow chart500of illustrative steps that may be performed by a switch modeling interface at a controller to use switch-computed digest values in identifying differences between a desired network snapshot and an existing network configuration. The steps of flow chart500may, for example, be performed during steps212and214ofFIG. 14or during step308ofFIG. 15.

During step502, a control module at the switch modeling interface may compute one or more digest tables for a desired network snapshot (e.g., a network snapshot received from an application module indicating a desired network configuration for the switches of the network). The control module may compute a digest table for each switch similarly to how that switch computes its own digest table. For example, the control module may perform steps404-406ofFIG. 16for each switch using the table entries in the network snapshot that are associated with that switch (e.g., a separate digest table may be computed for each switch in the network).

During step504, the control module may select a switch and request the digest table maintained by the selected switch (e.g., the digest table maintained by the switch in performing the steps of flow char400ofFIG. 16).

During step506, the control module may compare the digest values computed by the controller with the retrieved digest values from the switch to identify differences in the digest values. Buckets of the computed digest table of the selected switch for which the retrieved digest values from the switch are not matching may be identified as requiring updates. Conversely, buckets of the computed digest table of the selected switch that match the retrieved digest values may be identified as not requiring updates.

During step508, the control module may communicate with the selected switch to retrieve the table entries of only the selected bucket (e.g., the table entries that were used in calculating the hash values assigned to the selected bucket). The control module may compare the retrieved table entries to the desired table entries in the network snapshot and provide corrective table entries to the selected switch that implement the desired network configuration of the network snapshot.

Use of digest values as shown inFIG. 18to determine what modifications need to be made in implementing a desired network configuration may help to reduce the amount of traffic over control paths between the controller and switches in the network, because only table entries of buckets having non-matching digest values are transferred. By transferring only table entries associated with non-matching digest values, storage resources (e.g., memory) at the controller may be more efficiently utilized, as it is not necessary to store the entire switch state at the controller at any given time.