Non-stop forwarding in a multi-chassis router

A method for distributing state information within a multi-chassis router comprising a first local routing engine and a second local routing engine, wherein the second local routing engine acts as a standby routing engine for the first local routing engine, the multi-chassis router further comprising a third routing engine configured as a master routing engine for the multi-chassis router, the method comprising:

• utilizing a commit proposal and a commit marker to identify portions of the state information;
• receiving updates to the state information with the first local routing engine of the multi-chassis router from the third routing engine of the multi-chassis router,
• communicating the updates from the first local routing engine to the second local routing engine;
• and
• after communicating the updates from the first local routing engine to the second local routing engine, communicating the updates from the first local routing engine to one or more consumers of the state information, wherein the one or more consumers receive and utilize state information from the first local routing engine, and wherein at least one of the consumers comprises a forwarding component for the first local routing engine,
• wherein the updates are received according to a hierarchically-ordered and temporally-linked data structure, and
• wherein utilizing a commit proposal and a commit marker comprises:
• setting the commit proposal to identify a most recent object of the hierarchically-ordered and temporally-linked data structure that is the subject of an acknowledgement request sent to one of the consumers;
• and
• setting the commit marker to identify a most recent object of the hierarchically-ordered and temporally-linked data structure that has been communicated to the one of the consumers and for which an acknowledgement has been received from the one of the consumers.

A multi-chassis network device comprising:

• a first master routing engine;
• a second master routing engine configured as a standby master routing engine for the first master routing engine;
• and
• a first plurality of consumers of state information from the first master routing engine, wherein a first one of the first plurality of consumers comprises a first local routing engine, and wherein a second one of the first plurality of consumers comprises a second local routing engine configured as a standby routing engine for the first local routing engine;
• and
• a second plurality of consumers, wherein at least one of the second plurality of consumers comprises a forwarding component for the first local routing engine,
• wherein the first master routing engine manages state information and communicates updates to the state information to the second master routing engine before communicating the updates to the first local routing engine,
• wherein the first local routing engine communicates the updates to the second local routing engine before communicating the updates to the second plurality of consumers,
• wherein the first local routing engine issues a communication that causes the second local routing engine to set a commit proposal to identify a most recent portion of the state information that is the subject of an acknowledgement request sent to at least one of the second plurality of consumers, and
• wherein the first local routing engine issues a communication that causes the second local routing engine to set a commit marker to identify a most recent portion of the state information that has been communicated to the first the consumers and for which an acknowledgement has been received from the at least one of second plurality of consumers.

A multi-chassis network device comprising:

• a first master routing engine storing state information within a hierarchically-ordered and temporally-linked data structure within the first local routing engine;
• a second master routing engine configured as a standby master routing engine for the first master routing engine;
• and
• a plurality of consumers of state information from the first master routing engine,
• wherein the first routing engine manages the state information and communicates updates to the state information to the second routing engine before communicating the updates to a first one of the plurality of consumers,
• wherein the first routing engine communicates the updates to the second master routing engine by replicating the hierarchically-ordered and temporally-linked data structure within the first one of the plurality of consumers, and
• wherein the first routing engine sets a commit proposal to identify a most recent object of the hierarchically-ordered and temporally-linked data structure for the updates for which an acknowledgement request has been sent to the one or more consumers and sets a commit marker to identify a most recent object of the hierarchically-ordered and temporally-linked data structure for the updates that have been communicated to the one of the consumers and for which an acknowledgement has been received from the one of the consumers.

A computer-readable storage medium being a non-transitory medium of a multi-chassis routing device, the device comprising a first local routing engine, a second local routing engine, and one or more consumers of state information, wherein the second local routing engine acts as a standby routing engine for the first local routing engine, wherein the one or more consumers receive and utilize state information from the first local routing engine, and wherein at least one of the consumers comprises a forwarding component for the first local routing engine, the device further comprising a master routing engine, the computer-readable storage medium comprising instructions for causing the first local routing engine to:

• receive state information from the master routing engine and store the state information within a hierarchically-ordered and temporally-linked data structure;
• communicate updates to the state information in accordance with an order that requires the updates to be communicated to the second local routing engine before communicating the updates to the one or more consumers of the state information;
• set a commit proposal to identify a most recent object of the hierarchically-ordered and temporally-linked data structure for the updates for which an acknowledgement request has been sent to the one or more consumers;
• and
• set a commit marker to identify a most recent object of the hierarchically-ordered and temporally-linked data structure for the updates that have been communicated to the one of the consumers and for which an acknowledgement has been received from the one of the consumers.

A computer-readable storage medium being a non-transitory medium of a multi-chassis routing device, the device comprising a first local routing engine, a second local routing engine, and one or more consumers of state information, wherein the second local routing engine acts as a standby routing engine for the first local routing engine, wherein the one or more consumers receive and utilize state information from the first local routing engine, and wherein at least one of the consumers comprises a forwarding component for the first local routing engine, the device further comprising a master routing engine, the computer-readable storage medium comprising instructions for causing the first local routing engine to:

• receive state information from the master routing engine;
• and
• communicate updates to the state information in accordance with an order that requires the updates to be communicated to the second local routing engine before communicating the updates to the one or more consumers of the state information,
• wherein the instructions cause the first local routing engine to:
• utilize a commit proposal to identify a most recent portion of the updates that is the subject of an acknowledgement request sent to the one or more consumers;
• and
• utilize a commit marker to identify a most recent portion of the updates that has been communicated to the one or more consumers and for which an acknowledgement has been received from the one or more consumers.

A method comprising:

• receiving state updates with a first control unit of a first chassis of a multi-chassis network system from a control unit of a control node of the multi-chassis network system and storing the state updates within a hierarchically-ordered and temporally-linked data structure;
• forwarding the state updates from the first control unit to a consumer, wherein forwarding the state updates includes replicating a least a portion of the hierarchically-ordered and temporally-linked data structure to the consumer, and wherein the consumer comprises a processor of the multi-chassis router that consumes state information from the first control unit;
• setting a commit proposal to identify a most recent object of the hierarchically-ordered and temporally-linked data structure for the updates for which an acknowledgement request has been sent to the consumer;
• setting a commit marker to identify a most recent object of the hierarchically-ordered and temporally-linked data structure for the updates that have been communicated to the one of the consumers and for which an acknowledgement has been received from the consumer;
• transferring state update operations from the first control to a second control unit of the first chassis;
• and
• substantially maintaining network functions during the transfer.