US 12,184,491 B1 · Causal, in-place network updates

Abstract

According to an update procedure for a network of interconnected nodes, a node keeps track of markers received on the node's incoming channels, transmits a marker on each outgoing channel (if any exist), and updates its node configuration from an old configuration to a new configuration. In one version of the update procedure, the node updates its configuration and transmits markers after receiving its initial incoming marker. In another version for acyclic networks, the node updates its configuration and transmits markers after receiving its final incoming marker. The node determines how to handle (i.e., process, queue, or drop) each incoming data packet based on (i) whether or not it has updated its node configuration yet and (ii) whether or not it has received a marker on the corresponding incoming channel yet. A controller initiates the update process at a subset of nodes that ensures eventual completion of the update process.

Claims25

Dependent claims

A node for a network comprising a plurality of interconnected nodes, the node comprising:

one or more links connecting the node to one or more other nodes of the network, wherein each link corresponds to an incoming channel and/or an outgoing channel;
at least one processor;
and
at least one memory storing instructions that, upon being executed by the at least one processor, cause the node at least to:
keep track of incoming markers received on the node's one or more incoming channels;
transmit an outgoing marker on each outgoing channel, if any exist, based upon receipt of the one or more incoming markers;
and
update its configuration from an old node configuration to a new node configuration based upon the receipt of the one or more incoming markers.

5 more elements

A method for a node for a network comprising a plurality of interconnected nodes, the node comprising one or more links connecting the node to one or more other nodes of the network, wherein each link corresponds to an incoming channel and/or an outgoing channel, the method comprising the node:

keeping track of incoming markers received on the node's one or more incoming channels;
transmitting an outgoing marker on each outgoing channel, if any exist, based upon receipt of the one or more incoming markers;
and
updating its configuration from an old node configuration to a new node configuration based upon the receipt of the one or more incoming markers.

1 more element

A controller for a network comprising a plurality of interconnected nodes, each node comprising one or more links connecting the node to one or more other nodes of the network, wherein each link corresponds to an incoming channel and/or an outgoing channel, where each node is configured to perform an update procedure in which the node (i) keeps track of incoming markers received on the node's one or more incoming channels, (ii) transmits an outgoing marker on all outgoing channels, if any exist, based upon receipt of the one or more incoming makers, and (iii) updates its configuration from an old node configuration to a new node configuration based upon the receipt of the one or more incoming markers, the controller comprising:

at least one processor;
and
at least one memory storing instructions that, upon being executed by the at least one processor, cause the controller at least to:
provide a new node configuration to at least one of the nodes;
and
instruct a subset of the nodes to initiate the update procedure.

3 more elements

Dependencies are inferred from the claim text.

Causal, in-place network updates

Life of this patent

Causal, in-place network updates

Life of this patent

Abstract

Claims25