Software apparatus for distributing and providing fault-tolerance to path-vector routing protocols

• US 7,155,535 B2
• Filed: 09/10/2004
• Issued: 12/26/2006
• Est. Priority Date: 09/15/2000
• Status: Expired due to Fees

• Current Assignee: Parity Networks LLC
• Original Assignee: Pluris, Inc
• Inventors: Agarwal, Puneet, Menezes, Vivek, Basturk, Erol
• Primary Examiner(s): Jaroenchonwanit, Bunjob
• Assistant Examiner(s): DOAN, DUYEN MY
• Application Number:
  US10/861,079
• Publication Number:
  US 20040260825A1
• Time in Patent Office: 837 Days
• Field of Search: 709/238, 709/239, 709/240, 709/242, 709/243, 370352-356
• US Class Current: 709/238
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/127 based on intermediate node capabilities
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/44 Distributed routing
• CPC Class Codes: H04L 45/56 Routing software
• CPC Class Codes: H04L 45/583 Stackable routers

Abstract

An inter-network method for distributing a path-vector routing protocol within a multi-processor router has steps of running an instance of a router-distributed Border Gateway Protocol (rdBGP) on each of a plurality of processors of the multi-processor router, establishing routing sessions between individual instances of rdBGP running on separate processors of the multi-processor router, and between individual ones of the instances of rdBGP and external protocol peers, exchanging routing information between instances of rdBGP and the external protocol peers, wherein the instances of rdBGP learn, from the external protocol peers, routes for a plurality of destinations, calculating independently, by each instance of rdBGP, a set of routes, including a best route, from each of the plurality of destinations learned from the external protocol peers, and sharing route information determined with the other instances of rdBGP running on separate processors in the multi-processor router, and updating route information according to information received from the other instances of rdBGP. Routing information is further shared with the external protocol peers, and fault tolerance is provided in some embodiments by establishing redundant communication sessions with external protocol peers.

Claims

1. A fault-tolerant router, comprising:

a first instance of inter-network routing software resident on a first processor of the fault-tolerant router;

a second instance of inter-network routing software resident on a second processor of the fault-tolerant router;

an internal fabric through which the processors communicate; and

ports through which the instances of inter-network routing software communicate with external routers;

characterized in that each instance of inter-network routing software establishes a routing session with at least one external router, learns routes from the external routers, and determines a set of routes, including a best route, from the routes learned and the separate instances of software each maintain a routing session with each external router, providing fault-tolerance thereby.

2. The router of claim 1 wherein each instance of inter-network routing software also establishes routing sessions with each instance of inter-network routing software, and shares route information thereby.

3. The router of claim 2 wherein each instance of inter-network routing software re-determines best route information after sharing with other instances of inter-network routing software, and shares route information with any external router with which it has a routing session.

4. The router of claim 1 wherein a routing session is established between every instance of inter-network routing software and every other instance of inter-network routing software.

5. The router of claim 4 wherein each of the plurality of instances of inter-network routing software are in full-mesh communication with each other via a reliable communication mechanism.

6. The router of claim 1, wherein the instances of inter-network routing software are dynamically assigned to the plurality of external routers based on a metric selected from the group consisting of CPU usage and memory usage.

7. A system providing distributed path-vector routing within a single router, comprising:

a first instance of inter-network routing software resident on a first processor of the router;

a second instance of inter-network routing software resident on a second processor of the router;

a communication network enabling routing sessions to occur between the first and second instances of routing software on the first and second processors and a plurality of external routers;

wherein the first and second instances of inter-network routing software exchange routing information between each other and at least one of the external routers, and the inter-network routing software instances learn from the at least one external router, routes for a plurality of destinations and calculate, independently, a set of routes, including a best route, for each of the plurality of destinations learned from the at least one external router, and wherein the inter-network software instances share the determined route information with each other, and update route information in their respective processors according to the shared route information.

8. The system of claim 7 wherein the instances of inter-network software share the determined routing information with the external router.

9. The system of claim 7 wherein, the instances of inter-network software communicate with additional processors each having an instance of inter-network software resident.

10. The system of claim 9 wherein the first and second instances of inter-network software duplicate routing sessions with external routers, providing fault-tolerance thereby.

11. The method of claim 9 wherein each of the instances of inter-network software is in full-mesh communication with each other via a reliable communication mechanism.

12. The method of claim 9 wherein the instances of inter-network software are dynamically assigned to the plurality of external routers based on a metric selected from the group consisting of CPU usage and memory usage.