Scalable and fault-tolerant link state routing protocol for packet-switched networks

• US 20040258065A1
• Filed: 07/13/2004
• Published: 12/23/2004
• Est. Priority Date: 11/30/2000
• Status: Active Grant

• Current Assignee: Parity Networks LLC
• Original Assignee: Sherwood Partners Incorporated
• Inventors: Agarwal, Puneet, Akyol, Bora, Ginsberg, Les
• Granted Patent: US 7,583,603 B2
• Time in Patent Office: Days
• US Class Current: 370/389
• CPC Class Codes: H04L 41/0663 Performing the actions predefined by failover planning, e.g. switching to standby network elements
• CPC Class Codes: H04L 41/0803 Configuration setting
• CPC Class Codes: H04L 43/0811 by checking connectivity
• CPC Class Codes: H04L 43/0817 by checking functioning
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/586 of virtual routers
• CPC Class Codes: H04L 45/60 Router architectures
• CPC Class Codes: H04L 49/555 Error detection
• CPC Class Codes: H04L 69/40 for recovering from a failure of a protocol instance or entity, e.g. service redundancy protocols, protocol state redundancy or protocol service redirection management of faults, events, alarms or notifications in data switching networks H04L41/06

Abstract

A distributed Link-State Routing Protocol (LSRP) system in a packet switch having external communication ports has a first card executing Update process of the LSRP, making database updates, a second card executing Decision process(Shortest Path First (SPF)) of the LSRP, and a communication fabric coupling the cards with each other and the external ports. The LSRP may be an IS-IS system. In some embodiments there are additional cards involved, and the distribution of Link-State functions is over a set of multiple cards. Also in some embodiments there is a Location Service (LS) controller monitoring and configuring cards in the system.

Claims

1. A distributed Link-State Routing Protocol (LSRP) system in a packet switch having external communication ports, comprising:

a first card executing an update process of the LSRP, making database updates;

a second card executing Decision (Shortest Path First (SPF)) process of the LSRP; and

a communication fabric coupling the cards with each other and the external ports.

2. The system of claim 1 wherein the LSRP is one of an Intermediate System to Intermediate System (IS-IS) LSRP, or an Open Shortest Path First (OSPF) LSRP.

3. The system of claim 1 further comprising a third card communicating through the fabric with the first and second cards and the ports, wherein the first card updates both the second and third cards, maintaining synchronized copies of the Link State, Adjacency, and Circuit databases.

4. The system of claim 3 further comprising a location service (LS) controller operating external to the LSRP-related processes on the three cards, wherein the LS controller configures and monitors the LSRP system.

5. The system of claim 4 wherein the LS controller configures one of the three cards to execute the LSRP Update process, another to execute the LSRP Decision process, and the third to act as a backup, and reassigns roles according to monitored condition of the three cards.

6. A distributed Link-State Routing Protocol (LSRP) system in a packet switch having external communication ports, comprising:

a set of two or more cards in communication with one another and with the external communication ports; and

a location service (LS) controller separate from but in communication with the cards;

wherein the LS controller monitors and configures the cards, assigning LSRP functions and backup functions to individual cards.

7. The system of claim 6 wherein the LS controller reassigns functions to cards in the system in response to failures of cards in the system, providing fault tolerance.

14. The packet switch of claim 6 wherein the LS controller reassigns LSRP processes to card in the system in response to failures of cards in the system, providing fault tolerance.

8. A packet switch, comprising:

a plurality of cards, some of which have one or more communication ports;

a first card executing update process of a Link-State Routing Protocol LSRP, making database updates;

a second card executing Decision process(Shortest Path First (SPF)) of the LSRP; and

a communication fabric coupling the cards.

9. The packet switch of claim 8 wherein the LSRP is one of an Intermediate System to Intermediate System (IS-IS) LSRP or an Open Shortest Path First (OSPF) LSRP.

10. The packet switch of claim 8 further comprising a third card communicating through the fabric with the first and second cards and the communication ports, wherein the first card updates both the second and third cards, maintaining synchronized copies of a the Adjacency, Circuit, and Link-State databases.

11. The packet switch of claim 10 further comprising a location service (LS) controller operating external to the first, second and third cards, wherein the LS controller configures and monitors the LSRP system.

12. The packet switch of claim 11 wherein the LS controller configures one of the three cards to execute the LSRP Update process, another to execute the LSRP Decision process, and the third to act as a backup, and reassigns roles according to monitored condition of the three cards.

13. A packet switch, comprising a set of cards, some of which have external communication ports;

and

a location service (LS) controller separate from but in communication with the set of cards;

wherein the LS controller monitors and configures the cards, assigning LSRP functions and backup functions to individual ones of the cards.

15. A method for distributing a Link-State Routing Protocol in a packet switch having more than a single card, comprising the steps of:

(a) configuring a first card to execute update process of the protocol;

(b) configuring a second card to execute Decision process(Shortest-Path First (SPF)) of the protocol; and

(c) executing the configured functions on the cards, and synchronizing copies of a the Adjacency, Circuit, and Link State databases on the cards.

16. The method of claim 15 wherein the LSRP is one of an Intermediate System to Intermediate System (IS-IS) LSRP or an Open Shortest Path First LSRP.

17. The method of claim 15 further comprising a location service (LS) controller operating external to the card executing LSRP process, wherein the LS controller configures and monitors the LSRP system.

18. The method of claim 17 further comprising at least a third card, wherein the LS controller configures one of the three to execute the LSRP Update process, another to execute the LSRP Decision(SPF) process, and the third to act as a backup, and reassigns roles according to monitored condition of the three cards.

19. The method of claim 15 wherein two or more cards are configured to execute the Update functions of the protocol.