Non-stop forwarding in a multi-chassis router

• US 8,483,048 B2
• Filed: 09/23/2010
• Issued: 07/09/2013
• Est. Priority Date: 12/01/2005
• Status: Expired due to Fees

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Tuplur, Raj, Chadalavada, Bharani, Apte, Manoj, Sivaramakrishnan, Rajagopalan, Raghunathan, Sriram, Krishnaswamy, Umesh
• Primary Examiner(s): Ton, Dang
• Assistant Examiner(s): KAVLESKI, RYAN C
• Application Number:
  US12/889,209
• Publication Number:
  US 20110013508A1
• Time in Patent Office: 1,020 Days
• Field of Search: 370/217, 370/218, 370/238
• US Class Current: 370/218
• 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/58 Association of routers
• CPC Class Codes: H04L 45/60 Router architectures

Abstract

State information is synchronized between a plurality of routing engines in a multi-chassis router according to a synchronization gradient. An example multi-chassis router is described that includes a primary routing engine and a standby routing engine in each chassis. According to the synchronization gradient, the primary routing engine of a control node updates state information on the standby routing engine of the control node prior to updating the primary routing engines of the other chassis. The primary routing engines of the other chassis update state information in respective standby routing engines prior to updating state information in consumers. If a primary routing engine fails, the corresponding standby routing engine assumes control of the primary routing engine'"'"'s duties. Upon assuming control, a standby routing engine resumes updating state information without having to resend state information or interrupt packet forwarding.

Claims

1. A method for distributing state information within a multi-chassis router comprising a first master routing engine and a second master routing engine, wherein the second master routing engine acts as a standby routing engine for the first master routing engine, the multi-chassis router further comprising a local routing engine, wherein the first master routing engine, the second master routing engine, and the local routing engine are physically coupled within the multi-chassis router and configured to operate as a single router within a network, the method comprising:

communicating updates to the state information with the first master routing engine to the second master routing engine of the multi-chassis router, wherein the updates are communicated according to a hierarchically-ordered and temporally-linked data structure, wherein communicating the updates to the second master routing engine comprises replicating the hierarchically-ordered and temporally-linked data structure within the second master routing engine; and

after communicating the updates from the first master routing engine to the second master routing engine, communicating the updates from the first master routing engine to the local routing engine.

2. The method of claim 1, wherein the local routing engine comprises a first local routing engine, wherein the multi-chassis router further comprises a second local routing engine, wherein the second local routing engine acts as a standby routing engine for the first local routing engine, the method further comprising:

receiving the updates to the state information with the first local routing engine of the multi-chassis router from the first master routing engine, wherein the updates are received according to the hierarchically-ordered and temporally-linked data structure;

communicating the updates from the first local routing engine to the second local routing engine, wherein communicating the updates to the second local routing engine comprises replicating the hierarchically-ordered and temporally-linked data structure within 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 comprise a processor or module within the multi-chassis router that receives and utilizes state information from the first local routing engine.

3. The method of claim 2, further comprising receiving an acknowledgement for the updates from the second local routing engine prior to communicating the updates to the one or more consumers, wherein communicating the updates from the first local routing engine to the one or more consumers comprises communicating the updates to the one or more consumers in response to the acknowledgement from the second local routing engine.

4. The method of claim 1, wherein communicating the updates to the second master routing engine comprises communicating the updates in accordance with an order that requires the updates to be communicated to the second master routing engine prior to communicating the updates to the local routing engine.

5. The method of claim 1, wherein communicating the updates to the local routing engine comprises communicating the updates to the local routing engine in accordance with the hierarchically-ordered and temporally-linked data structure.

6. The method of claim 5, further comprising:

setting a 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 or more consumers that comprise a processor or module within the multi-chassis router; and

after receiving an acknowledgement from each of the one or more consumers in response to the acknowledgement request, setting a commit marker to identify the object of the hierarchically-ordered and temporally-linked data structure identified by the commit proposal.

7. The method of claim 6, further comprising:

replicating the commit proposal and the commit marker to the second master routing engine; and

communicating a portion of the hierarchically-ordered and temporally-linked data structure following the replicated commit marker to the local routing engine from the second master routing engine in the event the first master routing engine fails.

8. The method of claim 7, further comprising issuing a communication from the first master routing engine to cause the second master routing engine to set the replicated commit proposal to identify a most recent portion of the hierarchically-ordered and temporally-linked data structure that is the subject of the acknowledgement request.

9. The method of claim 7, further comprising issuing a communication from the first master routing engine to cause the second master routing engine to set the replicated commit marker to identify a most recent portion of the hierarchically-ordered and temporally-linked data structure that has been communicated to the local routing engine and for which an acknowledgement has been received from the local routing engine.

10. The method of claim 6, further comprising sending an acknowledgement of the received updates to the master routing engine for a most recent portion of the hierarchically-ordered and temporally-linked data structure prior to the commit marker, after receiving the acknowledgement from each of the one or more consumers.

11. The method of claim 5, further comprising:

receiving, with the local routing engine, an acknowledgement request from the first master routing engine; and

inserting, with the local routing engine, a marker in the hierarchically-ordered and temporally-linked data structure to store the acknowledgement request.

12. The method of claim 11, further comprising:

receiving, with the local routing engine, a first acknowledgement for all objects less recent than the marker; and

sending, with the local routing engine, a second acknowledgement to the master routing engine in response to the acknowledgement request, after receiving the first acknowledgement.

13. The method of claim 5, further comprising receiving, with the local routing engine from the first master routing engine, instructions to delete a portion of the hierarchically-ordered and temporally-linked data structure.

14. The method of claim 1, further comprising:

receiving an acknowledgement for the updates from the second local routing engine; and

marking objects in the hierarchically-ordered and temporally linked data structure to indicate the updates have been acknowledged by the second local routing engine.

15. The method of claim 1, further comprising receiving, with the first local routing engine, a first acknowledgement request from the first master routing engine to acknowledge receipt of the updates to the state information, the first acknowledgement including a sequence number, wherein the sequence number represents the first acknowledgement request in a count of acknowledgement requests received from the first master routing engine.

16. The method of claim 15, further comprising:

counting, with the first master routing engine, the number of acknowledgement requests sent to the first local routing engine from the first master routing engine; and

storing, with the first master routing engine, a value representing the count within objects that store the acknowledgement requests.

17. The method of claim 1,

wherein the multi-chassis router comprises a chassis comprising the local routing engine,

wherein the local routing engine comprises a primary local routing engine for the chassis of the multi-chassis router, and

wherein the first master routing engine comprises a primary master routing engine for the control node within the multi-chassis router.

18. The method of claim 2, wherein at least one of the consumers comprises an interface card for the local routing engine or a packet forwarding component for the first local routing engine.

19. 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;

a first local routing engine;

a second local routing engine configured as a standby routing engine for the first local routing engine; and

a plurality of consumers, wherein at least one of the plurality of consumers comprises a packet forwarding component for the first local routing engine,

wherein the first master routing engine, the second master routing engine, the first local routing engine, and the second local routing engine are physically coupled within the multi-chassis network device and configured to operate as a single router within a network,

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 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 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 the portion of the state information identified by the commit proposal after an acknowledgement has been received from the at least one of plurality of consumers in response to the acknowledgement request.

20. The multi-chassis network device of claim 19,

wherein the first master routing engine manages the state information within a hierarchically-ordered and temporally-linked data structure and communicates the updates by replicating the hierarchically-ordered and temporally-linked data structure within the first local routing engine, and

wherein the first local routing engine replicates the commit proposal and the commit marker to the second local routing engine, and the second local routing engine communicates a portion of the replicated hierarchically-ordered and temporally-linked data structure after the commit marker to the at least one of the plurality of consumers in the event the first local routing engine fails.

21. The multi-chassis network device of claim 20, wherein the first local routing engine communicates the updates to the second local routing engine in accordance with the hierarchically-ordered and temporally-linked data structure.

22. The multi-chassis network device of claim 21, wherein the first local routing engine utilizes a commit proposal and a commit marker to identify the portion of the state information within the hierarchically-ordered and temporally-linked data structure that has been communicated to the second local routing engine.

23. The multi-chassis network device of claim 22,

wherein the first local routing engine sets the commit proposal to identify a most recent potion of the updates that is the subject of an acknowledgement request sent to the second local routing engine, and

sets the commit marker to identify the portion of the updates that has been communicated to the second local routing engine and for which an acknowledgement has been received from the second local routing engine in response to the acknowledgement request.