Methods & apparatus for distributing, & providing fault-tolerance to path-vector routing protocols

• US 20040260825A1
• Filed: 09/10/2004
• Published: 12/23/2004
• Est. Priority Date: 09/15/2000
• Status: Active Grant

• Current Assignee: Parity Networks LLC
• Original Assignee: Sherwood Partners Incorporated
• Inventors: Agarwal, Puneet, Basturk, Erol, Menezes, Vivek
• Granted Patent: US 7,155,535 B2
• Time in Patent Office: Days
• US Class Current: 709/230
• 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. In an internetwork, a method for operating a distributed path-vector routing protocol within a multi-processor router, comprising the steps of:

a) running instances of a router-distributed Border Gateway Protocol (rdBGP) on each of a plurality of processors of the multi-processor router;

b) establishing routing sessions between individual instances of rdBGP running on the router, and between individual ones of the instances of rdBGP and external protocol peers;

c) 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;

d) calculating independently, by each instance of rdBGP, a set of routes, including a best route, for each of the plurality of destinations learned from the locally handled external protocol peers; and

e) sharing route information determined with the other instances of rdBGP of the router, and updating route information according to information received from the other instances of rdBGP.

2. The method of claim 1 comprising a further step (f) for sharing route information with the external protocol peers.

3. The method of claim 1 wherein, in step (b), a routing session is established between every instance of rdBGP and every other instance of rdBGP.

4. The method of claim 1 wherein two or more instances of rdBGP maintain a routing session with each external protocol peer, providing fault-tolerance thereby.

5. The method of claim 3 wherein each of the plurality of instances of rdBGP are in full-mesh communication with each other via a reliable communication mechanism.

6. The method of claim 1, wherein the instances of rdBGP are dynamically assigned to the plurality of external protocol peers based on a metric selected from the group consisting of CPU usage and memory usage.

7. A multi-processor router, comprising:

a plurality of instances of a router-distributed Border Gateway Protocol (rdBGP) executing on each of a plurality of processors;

an internal fabric through which the plurality of processors may communicate; and

ports through which the rdBGP instances may communicate with external routers;

characterized in that each instance of rdBGP establishes a routing session with an external router, learns routes from the external router, and determines a set of routes, including a best route, from the routes learned.

8. The router of claim 7 wherein each instance of rdBGP also establishes routing sessions with each instance of rdBGP, and shares route information thereby.

9. The router of claim 8 wherein each instance of rdBGP re-determines best route information after sharing with other instances of rdBGP, and shares route information with any external router with which it has a routing session.

10. The router of claim 7 wherein a routing session is established between every instance of rdBGP and every other instance of rdBGP.

11. The router of claim 7 wherein two or more instances of rdBGP maintain a routing session with each external router, providing fault-tolerance thereby.

12. The router of claim 10 wherein each of the plurality of instances of rdBGP are in full-mesh communication with each other via a reliable communication mechanism.

13. The router of claim 7, wherein the instances of rdBGP are dynamically assigned to the plurality of external protocol peers based on a metric selected from the group consisting of CPU usage and memory usage.