Distributed network control system with a distributed hash table

• US 8,775,594 B2
• Filed: 08/25/2011
• Issued: 07/08/2014
• Est. Priority Date: 07/06/2010
• Status: Active Grant

• Current Assignee: Nicira Incorporated (Broadcom, Inc.)
• Original Assignee: Nicira Incorporated (Broadcom, Inc.)
• Inventors: Koponen, Teemu, Casado, Martin, Stribling, Jeremy, Gude, Natasha
• Primary Examiner(s): Patel, Chirag R
• Application Number:
  US13/218,433
• Publication Number:
  US 20130060738A1
• Time in Patent Office: 1,048 Days
• Field of Search: 709223-226, 714 41- 411, 707640-641
• US Class Current: 709/223
• CPC Class Codes: G06F 11/07 Responding to the occurrence of a fault, e.g. fault tolerance
• CPC Class Codes: G06F 15/17312 Routing techniques specific to parallel machines, e.g. wormhole, store and forward, shortest path problem congestion routing on a LAN H04L45/00
• CPC Class Codes: H04L 12/4633 Interconnection of networks using encapsulation techniques, e.g. tunneling
• CPC Class Codes: H04L 2101/622 Layer-2 addresses, e.g. medium access control [MAC] addresses
• CPC Class Codes: H04L 41/0816 the condition being an adaptation, e.g. in response to network events
• CPC Class Codes: H04L 41/0853 by actively collecting configuration information or by backing up configuration information
• CPC Class Codes: H04L 41/0893 Assignment of logical groups to network elements
• CPC Class Codes: H04L 41/0894 Policy-based network configuration management
• CPC Class Codes: H04L 41/0895 Configuration of virtualised networks or elements, e.g. virtualised network function or OpenFlow elements
• CPC Class Codes: H04L 41/0896 Bandwidth or capacity management, i.e. automatically increasing or decreasing capacities flow or congestion control using dynamic resource allocation, e.g. in-call renegotiation, H04L47/76
• CPC Class Codes: H04L 41/122 of virtualised topologies, e.g. software-defined networks [SDN] or network function virtualisation [NFV]
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/036 Updating the topology between route computation elements, e.g. between OpenFlow controllers
• CPC Class Codes: H04L 45/586 of virtual routers
• CPC Class Codes: H04L 45/76 Routing in software-defined topologies, e.g. routing between virtual machines
• CPC Class Codes: H04L 47/783 Distributed allocation of resources, e.g. bandwidth brokers
• CPC Class Codes: H04L 49/00 Packet switching elements
• CPC Class Codes: H04L 49/1546 using pipelined operation
• CPC Class Codes: H04L 49/3063 Pipelined operation
• CPC Class Codes: H04L 49/70 : Virtual switches
• CPC Class Codes: H04L 61/5007 : Internet protocol [IP] addresses

Abstract

A network control system that includes several controllers for managing several switching elements and a distributed hash table (DHT) formed across the controllers for storing data regarding the switching elements that is accessible by the controllers. Each hash table serves as a DHT instance. In some embodiments, the DHT instances of all controller instances collectively store one set of records that is indexed based on hashed indices for quick access. These records are distributed across the different controller instances to minimize the size of the records within each instance and to allow for the size of the DHT to be increased by adding other DHT instances. According to this scheme, each DHT record is not stored in each controller instance. In fact, in some embodiments, each DHT record is stored in at most one controller instance.

Claims

1. A non-transitory machine readable medium storing a program for a controller of a network control system, the network control system comprising (i) a plurality of controllers for managing a plurality of switching elements that forward data between a plurality of host computing devices and (ii) a distributed hash table (DHT) stored across the plurality of controllers, the DHT comprising a plurality of DHT instances each of which is stored on a different one of the plurality of controllers, the program comprising sets of instructions for:

receiving an update for a value of a particular data tuple stored on a local DHT instance;

updating the value of the particular data tuple in the local DHT instance, said local DHT instance storing for the particular data tuple a trigger list that identifies a set of modules on a set of controllers to notify when the value of the particular data tuple is updated; and

based on the trigger list for the particular data tuple, notifying the set of modules of the set of controllers regarding the update to the value of the particular data tuple, wherein said DHT is for storing data regarding the switching elements.

2. The non-transitory machine readable medium of claim 1, wherein the update is received from another controller that includes a remote DHT instance.

3. The non-transitory machine readable medium of claim 1, wherein the program further comprises a set of instructions for generating a hash index for the particular data tuple.

4. The non-transitory machine readable medium of claim 1, wherein each controller'"'"'s DHT instance stores data that is not stored in any other DHT instance.

5. The non-transitory machine readable medium of claim 1, wherein each controller'"'"'s DHT instance comprises a first overlapping portion that stores data that is also stored in another DHT instance and a second non-overlapping portion that stores data that is not stored in any other DHT instance.

6. The non-transitory machine readable medium of claim 1, wherein the local DHT instance is a first DHT instance and comprises (i) a first overlapping portion that stores data that is stored in a second DHT instance but not a third DHT instance and (ii) a second overlapping portion that stores data that is stored in the third DHT instance and not the second DHT instance.

7. The non-transitory machine readable medium of claim 1,

wherein each controller comprises a network information base (NIB) storage that stores data regarding the switching elements,

wherein the program further comprises a set of instructions for replicating at least a portion of the data stored in the NIB storages of the controllers in the DHT.

8. The non-transitory machine readable medium of claim 7, wherein the program further comprises a set of instructions for processing notifications that a data tuple has been modified in a NIB storage.

9. A non-transitory machine readable medium storing a program for a controller of a network control system, the network control system comprising a plurality of controllers for managing a plurality of switching elements that forward data between a plurality of host computing devices, the program comprising sets of instructions for:

receiving (i) a data tuple for storing in a distributed hash table (DHT), the DHT comprising a plurality of DHT instances each of which is stored on a different one of the plurality of controllers, and (ii) a trigger list identifying a set of modules executing on a set of controllers;

generating a hash index for the data tuple;

identifying a DHT instance for storing the data tuple; and

directing the identified DHT instance to store the data tuple along with the trigger list, the data tuple pertaining to the forwarding of data by the switching elements between the plurality of host computing devices, the trigger list for use by the identified DHT instance when the data tuple is subsequently modified in order to notify the set of modules executing on the set of controllers that the data tuple has been modified.

10. The non-transitory machine readable medium of claim 9,

wherein each controller comprises a network information base (NIB) storage that stores data pertaining to the forwarding of data by the switching elements between the plurality of host computing devices,

wherein the program further comprises a set of instructions for replicating at least a portion of the data stored in the NIB storages of the controllers in the DHT.

11. The non-transitory machine readable medium of claim 10, wherein the program further comprises a set of instructions for processing notifications that a data tuple has been modified in a NIB storage.

12. The non-transitory machine readable medium of claim 10, wherein the DHT is for storing rapidly changing network state data that is stored in the NIB storages.

13. The non-transitory machine readable medium of claim 9, wherein the DHT is for storing data that is re-generatable if lost.

14. The machine non-transitory readable medium of claim 12, wherein the rapidly-changing data comprises statistics regarding a network entity.

15. The non-transitory machine readable medium of claim 12, wherein the rapidly-changing data comprises flow entries that are to be written to the switching elements to implement logical datapath sets on the plurality of host computing devices.

16. For a controller of a network control system, the network control system comprising (i) a plurality of controllers for managing a plurality of switching elements that forward data between a plurality of host computing devices and (ii) a distributed hash table (DHT) stored across the plurality of controllers, the DHT comprising a plurality of DHT instances each of which is stored on a different one of the plurality of controllers, a method comprising:

receiving an update for a value of a particular data tuple stored on a local DHT instance;

updating the value of the particular data tuple in the local DHT instance, said local DHT instance storing for the particular data tuple a trigger list that identifies a set of modules on a set of controllers to notify when the value of the particular data tuple is updated; and

based on the trigger list for the particular data tuple, notifying the set of modules of the set of controllers regarding the update to the value of the particular data tuple, wherein said DHT is for storing data regarding the switching elements.

17. The method of claim 16, wherein the update is received from another controller that includes a remote DHT instance.

18. The method of claim 16, wherein each controller'"'"'s DHT instance comprises a first overlapping portion that stores data that is also stored in another DHT instance and a second non-overlapping portion that stores data that is not stored in any other DHT instance.

19. The method of claim 16, wherein the local DHT instance is a first DHT instance and comprises (i) a first overlapping portion that stores data that is stored in a second DHT instance but not a third DHT instance and (ii) a second overlapping portion that stores data that is stored in the third DHT instance and not the second DHT instance.

20. The method of claim 16,

wherein each controller comprises a network information base (NIB) storage that stores data regarding the switching elements,

wherein the method further comprises replicating at least a portion of the data stored in the NIB storages of the controllers in the DHT.

21. The method of claim 20 further comprising processing notifications that a data tuple has been modified in a NIB storage.

22. For a controller of a network control system, the network control system comprising a plurality of controllers for managing a plurality of switching elements that forward data between a plurality of host computing devices, a method comprising:

receiving (i) a data tuple for storing in a distributed hash table (DHT), the DHT comprising a plurality of DHT instances each of which is stored on a different one of the plurality of controllers, and (ii) a trigger list identifying a set of modules executing on a set of controllers;

generating a hash index for the data tuple;

identifying a DHT instance for storing the data tuple; and

directing the identified DHT instance to store the data tuple along with the trigger list, the data tuple pertaining to the forwarding of data by the switching elements between the plurality of host computing devices, the trigger list for use by the identified DHT instance when the data tuple is subsequently modified in order to notify the set of modules executing on the set of controllers that the data tuple has been modified.

23. The method of claim 22,

wherein each controller comprises a network information base (NIB) storage that stores data pertaining to the forwarding of data by the switching elements between the plurality of host computing devices,

wherein the method further comprises replicating at least a portion of the data stored in the NIB storages of the controllers in the DHT.

24. The method of claim 23 further comprising processing notifications that a data tuple has been modified in a NIB storage.

25. The method of claim 23, wherein the DHT is for storing rapidly changing network state data that is stored in the NIB storages.

26. The method of claim 25, wherein the rapidly-changing data comprises flow entries that are to be written to the switching elements to implement logical datapath sets on the plurality of host computing devices.