US 12,756,621 B2Granted

Causal, in-place network updates using acyclic decomposition

AssigneeNokia Solutions and Networks Oy

InventorKedar Namjoshi

Life of this patent

Estimating the term…

Loading patent…

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. 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. Packet drops may be reduced by either (i) decomposing one or more cyclic portions of the network into acyclic portions or (ii) processing backwards-compatible packets received at an updated node from an un-updated node when the processing rules for those packets were not changed by the new node configuration at the updated node or (iii) both.

Claims17

Dependent claims

A controller for a network comprising a plurality of interconnected nodes and having a cyclic portion, 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 at least one 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, if any exist, (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, if any, 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:
decompose the cyclic portion of the network into at least a first acyclic portion and at least a first feedback edge, wherein the first acyclic portion has at least one first node connected to the first feedback edge;
inform the at least one first node of the first feedback edge;
provide a new node configuration to at least one of the nodes;
and
instruct a subset of the nodes to initiate the update procedure, wherein:
the subset comprises the at least one first node of the first acyclic portion of the network;
and
during the update procedure, the at least one first node is configured to determine whether to process or drop a data packet received over the first feedback edge.

8 more elements

A first node in an acyclic portion of a network comprising a plurality of interconnected nodes, the first node comprising:

one or more links connecting the first 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 first node at least to:
receive information about at least a first feedback edge connected to the first node;
keep track of incoming markers received on the first 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
during the update procedure, determine whether to process or drop a data packet received over the first feedback edge.

6 more elements

Dependencies are inferred from the claim text.