Secondary input queues for maintaining a consistent network state

• US 10,091,120 B2
• Filed: 06/26/2014
• Issued: 10/02/2018
• Est. Priority Date: 05/05/2014
• Status: Active Grant

• Current Assignee: Nicira Incorporated (Broadcom, Inc.)
• Original Assignee: Nicira Incorporated (Broadcom, Inc.)
• Inventors: Yip, Alexander, Hinrichs, Timothy L., Padmanabhan, Amar, Gude, Natasha, Ganichev, Igor, Chalvadi, Anuprem
• Primary Examiner(s): Abedin, Normin
• Application Number:
  US14/316,783
• Publication Number:
  US 20150319096A1
• Time in Patent Office: 1,559 Days
• Field of Search: 709220, 709224, 709226, 709230
• CPC Class Codes: H04L 41/042 comprising distributed management centres cooperatively managing the network
• CPC Class Codes: H04L 41/046 comprising network management agents or mobile agents therefor
• CPC Class Codes: H04L 41/0873 Checking configuration conflicts between network elements
• CPC Class Codes: H04L 43/08 Monitoring or testing based on specific metrics, e.g. QoS, energy consumption or environmental parameters
• CPC Class Codes: H04L 43/0811 by checking connectivity
• CPC Class Codes: H04L 43/20 the monitoring system or the monitored elements being virtualised, abstracted or software-defined entities, e.g. SDN or NFV
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/56 implementing delay-aware scheduling
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46

Abstract

Some embodiments provide a novel network control system that uses secondary input queues to receive and store inputs from multiple input sources prior to moving the inputs to a primary input queue for processing. The secondary input queues provide a separate storage for each input source so that the inputs from the different sources do not get mixed with each other to ensure that fixed points and barriers sent to the controller maintain their integrity.

Claims

1. A host computer for executing a network controller for computing forwarding rules in a distributed network control system, the host computer comprising:

at least one processing unit for executing instructions;

a non-transitory machine readable medium storing sets of instructions for implementing the network controller, the sets of instructions for;

defining a primary input queue and a plurality of secondary input queues for storing inputs received at the network controller;

storing inputs regarding configurations of logical forwarding elements implemented by a plurality of physical forwarding elements, said stored inputs received from a plurality of input sources in the plurality of secondary input queues, each secondary input queue for storing inputs from one of the plurality of input sources;

inserting barriers between the stored inputs in each secondary input queue of the plurality of secondary input queues, each of the barriers indicating an end to a set of the inputs to be processed together, the barriers for preventing partial changes to the forwarding rules propagating to the physical forwarding elements;

detecting the barriers on the secondary input queues and moving each of the sets of inputs as a group to the primary input queue; and

sending a set of forwarding rules to a set of the physical forwarding elements in the distributed network control system, the forwarding rules computed by processing together each set of inputs in the primary input queue.

2. The host computer of claim 1, wherein the set of instructions for inserting the barriers comprises a set of instructions for inserting a barrier on a particular secondary input queue after detecting that the corresponding input source for the particular secondary input queue has reached a fixed point that indicates that processing of the received inputs will result in a consistent view of a network state.

3. The host computer of claim 2, wherein the set of instructions for detecting that the corresponding input source for the particular secondary input queue has reached a fixed point comprises a set of instructions for determining that the particular secondary input queue has not received any inputs from the input source for a threshold period of time.

4. The host computer of claim 1, wherein the non-transitory machine readable medium further stores a set of instructions for receiving the barriers from the input sources.

5. The host computer of claim 1, wherein the plurality of input sources comprises at least one of a publisher controller and a configuration database.

6. The host computer of claim 1, wherein the set of forwarding rules is computed by a table mapping rule engine.

7. The host computer of claim 1, wherein the set of forwarding rules defines a set of states for the distributed network control system.

8. For a network controller that computes forwarding rules in a distributed network control system, a method comprising:

storing inputs regarding configurations of logical forwarding elements implemented by a plurality of physical forwarding elements, said stored inputs received from a plurality of input sources in a plurality of secondary input queues, each secondary input queue for storing inputs from a one of a plurality of input sources in the network;

inserting barriers between the stored inputs in each secondary input queue of the plurality of secondary input queues, each of the barriers indicating an end to a set of the inputs to be processed together, the barriers for preventing partial changes to the forwarding rules propagating to the physical forwarding elements;

detecting the barriers on the secondary input queues and moving each of the sets of the inputs as a group to a primary input queue; and

sending a set of forwarding rules to a set of the physical forwarding elements in the distributed network control system, the forwarding rules computed by processing together each set of inputs in the primary input queue.

9. The method of claim 8, wherein inserting the barriers comprises inserting a barrier on a particular secondary input queue after detecting that the corresponding input source for the particular secondary input queue has reached a fixed point that indicates that processing of the received inputs will result in a consistent view of a network state.

10. The method of claim 9, wherein detecting that the corresponding input source for the particular secondary input queue has reached a fixed point comprises determining that the particular secondary input queue has not received any inputs from the input source for a threshold period of time.

11. The method of claim 8, wherein receiving the barriers comprises receiving barriers from the input sources.

12. The method of claim 8, wherein the plurality of input sources comprises at least one of a publisher controller and a configuration database.

13. The method of claim 8, wherein the set of forwarding rules is computed by a table mapping rule engine.

14. The method of claim 8, wherein the set of forwarding rules defines a set of states for a set of physical forwarding elements in the distributed network control system.

15. A non-transitory machine readable medium storing sets of instructions for implementing a network controller for computing forwarding rules in a distributed network control system, the sets of instructions executable by a processing unit, the sets of instructions for:

storing inputs regarding configurations of logical forwarding elements implemented by a plurality of physical forwarding elements, said stored inputs received from a plurality of input sources in a plurality of secondary input queues, each secondary input queue for storing inputs from one of the plurality of input sources;

inserting barriers between the stored inputs in each secondary input queue of the plurality of secondary input queues, each of the barriers indicating an end to a set of inputs to be processed together, the barriers for preventing partial changes to the forwarding rules propagating to the physical forwarding elements;

detecting the barriers on the secondary input queues and moving each of the sets of inputs as a group to a primary input queue; and

sending a set of forwarding rules to a set of the physical forwarding elements in the distributed network control system, the forwarding rules computed by processing together each set of inputs in the primary input queue.

16. The non-transitory machine readable medium of claim 15, wherein the set of instructions for inserting the barriers comprises a set of instructions for inserting a barrier on a particular secondary input queue after detecting that the corresponding input source for the particular secondary input queue has reached a fixed point that indicates that processing of the received inputs will result in a consistent view of a network state, wherein the set of instructions for detecting that the corresponding input source for the particular secondary input queue has reached a fixed point comprises a set of instructions for determining that the particular secondary input queue has not received any inputs from the corresponding input source for a threshold period of time.

17. The non-transitory machine readable medium of claim 15, wherein the non-transitory machine readable medium further stores a set of instructions for receiving barriers from the input sources.

18. The non-transitory machine readable medium of claim 15, wherein the plurality of input sources comprises at least one of a publisher controller and a configuration database.

19. The non-transitory machine readable medium of claim 15, wherein the set of forwarding rules is computed by a table mapping rule engine.

20. The non-transitory machine readable medium of claim 15, wherein the set of forwarding rules defines a set of states for the distributed network control system.