Scalable router

• US 7,403,530 B2
• Filed: 07/27/2001
• Issued: 07/22/2008
• Est. Priority Date: 07/27/2001
• Status: Expired due to Fees

• Current Assignee: RPX Corporation
• Original Assignee: 4536631 Canada Incorporated (Lowe's Companies, Inc.)
• Inventors: Wickrema, Gamini, Goulet, Stephan, Duplaix, Jerome
• Primary Examiner(s): Moe, Aung S.
• Assistant Examiner(s): Mered, Habte
• Application Number:
  US09/915,332
• Publication Number:
  US 20030021232A1
• Time in Patent Office: 2,552 Days
• Field of Search: 370/236.1, 370/220, 370/395.31, 3703951-39572, 370386-432, 370/392, 370/236, 709238-240
• US Class Current: 370/395.31
• 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/28 using route fault recovery
• CPC Class Codes: H04L 45/52 Multiprotocol routers
• CPC Class Codes: H04L 45/583 Stackable routers
• CPC Class Codes: H04L 45/60 Router architectures
• CPC Class Codes: H04L 63/0227 Filtering policies mail message filtering H04L51/212
• CPC Class Codes: H04L 63/08 for authentication of entities cryptographic mechanisms or cryptographic arrangements for entity authentication H04L9/32

Abstract

A router with a routing layer that supports single or multiple routing protocols. The routing layer has at least two routing protocol computing entities, namely a first and a second routing protocol computing entities. Each routing protocol computing entity includes a CPU, a data storage medium in communication with the CPU and a program data stored in the data storage medium for execution by said CPU. The program data in each routing protocol computing entity implements different or the same routing protocols. This routing layer architecture is highly scalable.

Claims

1. A router supporting multiple routing protocols, said router comprising:

a. an interface layer including a plurality of I/O controllers, each I/O controller implementing an I/O port;

b. a switching layer in communication with said interface layer for selectively establishing signal pathways between said I/O ports; and

c. a routing layer in communication with said interface layer, said routing layer including a plurality of routing protocol computing entities, each routing protocol computing entity being associated with a set of at least one routing protocol and including;

i. a CPU; and

ii. a data storage medium in communication with said CPU and storing program data for execution by said CPU to cause said routing protocol computing entity to effect management of one or more peering sessions with remote routing devices according to the at least one routing protocol in the set associated with said routing protocol computing entity, said management of one or more peering sessions comprising maintaining in said data storage medium information on a plurality of routes;

wherein the set of at least one routing protocol associated with a first one of said routing protocol computing entities is different from the set of at least one routing protocol associated with a second one of said routing protocol computing entities;

wherein the data storage medium of said first one of said routing protocol computing entities contains information on at least one route for which there is no information in the data storage medium of said second one of said routing protocol computing entities.

2. A router as defined in claim 1, wherein each routing protocol computing entity is operative to maintain simultaneously a plurality of peering sessions with remote routing devices.

3. A router as defined in claim 1, wherein each routing protocol computing entity is operative to exchange data with a remote routing device through said interface layer during a peering session.

4. A router as defined in claim 3, wherein the peering session includes a transfer of route information data from said router to the remote routing device.

5. A router as defined in claim 4, wherein the peering session includes a transfer of route information data from the remote routing device to said router.

6. A router as defined in claim 5, wherein the information on a plurality of routes maintained in the data storage medium of each of at least one of said routing protocol computing entities is held in a local routing table stored in said data storage medium and including at least one inbound route database derived at least in part from route information data transferred from a remote routing device to said router.

7. A router as defined in claim 6, wherein each of said at least one of said routing protocol computing entities is operative to apply an inbound policy processing on the route information data transferred from a remote routing device during generation of said at least one inbound route database.

8. A router as defined in claim 5, wherein the data storage medium of at least one of said plurality of routing protocol computing entities stores a local routing table that holds a best route database, said at least one routing protocol computing entity being operative to apply an outbound policy processing on its best route database to generate at least one outbound route database, said at least one routing protocol computing entity being operative to transfer route information data from its said at least one outbound route database to a remote routing device.

9. A router as defined in claim 1, wherein the information on a plurality of routes maintained in the data storage medium of each routing protocol computing entity is held in a local routing table stored in said data storage medium and including at least one inbound route database derived from route information data transferred from a remote routing device to said router.

10. A router as defined in claim 9, wherein each routing protocol computing entity is operative to apply an inbound policy processing on the route information data transferred from a remote routing device during generation of said at least one inbound route database.

11. A router as defined in claim 10, wherein the local routing table of each routing protocol computing entity holds a best route database, each routing protocol computing entity being operative to apply an outbound policy processing on the best route database of said local routing table of said routing protocol computing entity to generate at least one outbound route database, each routing protocol computing entity being operative to transfer route information data from said at least one outbound route database of said routing protocol computing entity to a remote routing device.

12. A router as defined in claim 11, wherein said routing layer includes a control computing entity in data communicative relationship with each routing protocol computing entity, said control computing entity including:

a. a CPU; and

b. a data storage medium in communication with said CPU of said control computing entity and storing program data for execution by said CPU of said control computing entity and a master routing table.

13. A router as defined in claim 12, wherein the program data stored in the data storage medium of said control computing entity implements a routing table manager for managing said master routing table.

14. A router as defined in claim 13, wherein each routing protocol computing entity is in communication with said control computing entity to transfer to the data storage medium of said control computing entity data from the at least one inbound route database in said routing protocol computing entity.

15. A router as defined in claim 14, wherein said routing table manager is operative to apply a master policy processing on data received from the at least one inbound route database in each routing protocol computing entity to generate the master routing table.

16. A router as defined in claim 15, wherein said master policy processing includes merging the data in the inbound route databases of said routing protocol computing entities to produce merged routing data.

17. A router as defined in claim 16, wherein the merged routing data includes information mapping destinations and routes to the destinations.

18. A router as defined in claim 17, wherein the merged routing data includes a plurality of destinations and a set of routes associated with each destination of the plurality of destinations, said master policy processing includes discarding from each set of routes a plurality of routes and retaining only a subset of the set of routes.

19. A router as defined in claim 18, wherein said control computing entity is operative to transfer to the data storage medium of a first one of said routing protocol computing entities at least a portion of the merged routing data to form the best route database in the data storage medium of said first one of said routing protocol computing entities.

20. A router as defined in claim 19, wherein said control computing entity is operative to transfer to the data storage medium of a second one of said routing protocol computing entities at least a portion of the merged routing data to form the best route database in the data storage medium of said second one of said routing protocol computing entities.

21. A router as defined in claim 12, wherein each I/O controller includes a forwarding processor, when a data packet is received at the I/O controller, said forwarding processor determining an I/O port of said interface layer through which the data packet is to be released, said forwarding processor including a data storage medium holding a forwarding table, said forwarding table including data derived from said master routing table.

22. A router as defined in claim 1, wherein the set of at least one routing protocol associated with a first one of said routing protocol computing entities contains BGP, and wherein the set of at least one routing protocol associated with a second one of said routing protocol computing entities contains OSPF.

23. A router as defined in claim 1, wherein the set of at least one routing protocol associated with each of said routing protocol computing entities contains exactly one routing protocol.

24. A router as defined in claim 1, wherein the set of at least one routing protocol associated with said first one of said routing protocol computing entities and the set of at least one routing protocol associated with said second one of said routing protocol computing entities are mutually exclusive sets.

25. A router as defined in claim 1, wherein the data storage medium of each routing protocol computing entity holds a local routing table storing an inbound routing database derived from route information data transferred from a remote routing device during a peering session managed by said routing protocol computing entity, wherein said routing layer includes:

a control computing entity in data communicative relationship with each routing protocol computing entity, said control computing entity including;

i. a CPU; and

ii. a data storage medium in communication with the CPU of said control computing entity and storing;

a master routing table holding a master routing database derived at least in part from the inbound routing database of each routing protocol computing entity; and

program data for execution by the CPU of said control computing entity to implement a routing table manager to manage said master routing table;

a backup computing entity in data communicative relationship with each routing protocol computing entity and with said control computing entity, said backup computing entity including;

i. a CPU; and

ii. a data storage medium in communication with the CPU of said backup computing entity and storing program data for execution by the CPU of said backup computing entity to cause said backup computing entity to be responsive to an operational failure of said control computing entity to;

1. download the inbound routing database of each routing protocol computing entity; and

2. rebuild the master routing database at least in part from the inbound routing database downloaded from each routing protocol computing entity.

26. A router as defined in claim 1, wherein the data storage medium of each routing protocol computing entity holds a local routing table storing an inbound routing database derived from route information data transferred from a remote routing device during a peering session managed by said routing protocol computing entity, wherein said routing layer includes:

a control computing entity in data communicative relationship with each routing protocol computing entity, said control computing entity including;

i. a CPU; and

ii. a data storage medium in communication with the CPU of said control computing entity and storing;

a master routing table holding a master routing database derived at least in part from the inbound routing database of each routing protocol computing entity; and

program, data for execution by the CPU of said control computing entity to implement a routing table manager to manage said master routing table;

a backup computing entity in data communicative relationship with each routing protocol computing entity and with said control computing entity, said backup computing entity including;

i. a CPU; and

ii. a data storage medium in communication with the CPU of said backup computing entity and storing program data for execution by the CPU of said backup computing entity to cause said backup computing entity to be responsive to an operational failure of a particular one of said routing protocol computing entities to;

1. transfer information from said master routing table to the data storage medium of said backup computing entity to rebuild at least partially the local routing table of said particular one of said routing protocol computing entities; and

2. cause said backup computing entity to effect management of one or more peering sessions with remote routing devices according to the at least one routing protocol in the set associated with said particular one of said routing protocol computing entities.

27. A router as defined in claim 1, wherein said router is operative for:

merging routing data stored in the data storage medium of each of said routing protocol computing entities to produce merged routing data; and

transferring at least a portion of the merged routing data to the data storage medium of each of said routing protocol computing entities.

28. A router as defined in claim 27, wherein the merged routing data includes data regarding destinations and routes for the destinations, including, for each of at least one of the destinations, a plurality of routes for that destination.

29. A router as defined in claim 28, wherein said router is operative for, prior to said transferring, pruning the merged routing data by retaining, for each destination, at most a set number of routes for that destination.

30. A router as defined in claim 29, wherein said pruning comprises pruning the merged routing data based on a preference attribute associated with each of the routes.

31. A router as defined in claim 27, wherein said routing layer includes a control computing entity in data communicative relationship with each of said routing protocol computing entities, said control computing entity including:

a CPU; and

a data storage medium in communication with said CPU of said control computing entity and storing program data for execution by said CPU of said control computing entity to cause said control computing entity to effect said merging and said transferring.

32. A router as defined in claim 27, wherein said transferring comprises storing the at least a portion of the merged routing data in a best route database maintained in the data storage medium of each said routing protocol computing entities.

33. A router, comprising:

a. an interface layer including a plurality of I/O controllers, each I/O controller implementing an I/O port;

b. a switching layer in communication with said interface layer for selectively establishing signal pathways between said I/O ports; and

c. a routing layer in communication with said interface layer, said routing layer including a plurality of routing protocol computing entities, each routing protocol computing entity being associated with a routing protocol and including;

i. a CPU; and

ii. a data storage medium in communication with said CPU and storing program data for execution by said CPU to cause said routing protocol computing entity to effect management of one or more peering sessions with remote routing devices according to the routing protocol associated with said routing protocol computing entity, said management of one or more peering sessions comprising maintaining in said data storage medium information on a plurality of routes;

wherein the routing protocol associated with a first one of said routing protocol computing entities is the same as the routing protocol associated with a second one of said routing protocol computing entities;

wherein the data storage medium of said first one of said routing protocol computing entities contains information on at least one route for which there is no information in the data storage medium of said second one of said routing protocol computing entities.

34. A router as defined in claim 33, wherein the routing protocol associated with said first one of said routing protocol computing entities and the routing protocol associated with said second one of said routing protocol computing entities are distance vector protocols.

35. A router as defined in claim 33, wherein the routing protocol associated with said first one of said routing protocol computing entities and the routing protocol associated with said second one of said routing protocol computing entities are link state protocols.

36. A router as defined in claim 34, wherein the first one of said routing protocol computing entities is capable of establishing peering sessions with a first set of remote routing devices, the second one of said routing protocol computing entities is capable of establishing peering sessions with a second set of remote routing devices, the first set of remote routing devices excluding at least one routing device that belongs to the second set of routing devices.

37. A router as defined in claim 36, wherein the first set of remote routing devices excludes any remote routing device from the second set.

38. A router as defined in claim 37, wherein the first and the second sets of remote routing devices are mutually exclusive sets.

39. A router as defined in claim 35, wherein the first one of said routing protocol computing entities is capable of establishing peering sessions with remote routing devices from a first area, the second one of said routing protocol computing entities is capable of establishing peering sessions with remote routing devices from a second area, the first area being different from the second area.

40. A router as defined in claim 33, wherein the routing protocol associated with each of said first one of said routing protocol computing entities and said second one of said routing protocol computing entities is BGP.

41. A router as defined in claim 33, wherein the data storage medium of each routing protocol computing entity holds a local routing table storing an inbound routing database derived from route information data transferred from a remote routing device during a peering session managed by said routing protocol computing entity, wherein said routing layer includes:

a control computing entity in data communicative relationship with each routing protocol computing entity, said control computing entity including;

i. a CPU; and

ii. a data storage medium in communication with the CPU of said control computing entity and storing;

a master routing table holding a master routing database derived at least in part from the inbound routing database of each routing protocol computing entity; and

program data for execution by the CPU of said control computing entity to implement a routing table manager to manage said master routing table;

a backup computing entity in data communicative relationship with each routing protocol computing entity and with said control computing entity, said backup computing entity including;

i. a CPU; and

ii. a data storage medium in communication with the CPU of said backup computing entity and storing program data for execution by the CPU of said backup computing entity to cause said backup computing entity to be responsive to an operational failure of said control computing entity to;

1. download the inbound routing database of each routing protocol computing entity; and

2. rebuild the master routing database at least in part from the inbound routing database downloaded from each routing protocol computing entity.

42. A router as defined in claim 33, wherein the data storage medium of each routing protocol computing entity holds a local routing table storing an inbound routing database derived from route information data transferred from a remote routing device during a peering session managed by said routing protocol computing entity, wherein said routing layer includes:

a control computing entity in data communicative relationship with each routing protocol computing entity, said control computing entity including;

i. a CPU; and

ii. a data storage medium in communication with the CPU of said control computing entity and storing;

a master routing table holding a master routing database derived at least in part from the inbound routing database of each routing protocol computing entity; and

program data for execution by the CPU of said control computing entity to implement a routing table manager to manage said master routing table;

a backup computing entity in data communicative relationship with each routing protocol computing entity and with said control computing entity, said backup computing entity including;

i. a CPU; and

ii. a data storage medium in communication with the CPU of said backup computing entity and storing program data for execution by the CPU of said backup computing entity to cause said backup computing entity to be responsive to an operational failure of a particular one of said routing protocol computing entities to;

1. transfer information from said master routing table to the data storage medium of said backup computing entity to rebuild at least partially the local routing table of said particular one of said routing protocol computing entities; and

2. cause said backup computing entity to effect management of one or more peering sessions with remote routing devices according to the routing protocol associated with said particular one of said routing protocol computing entities.

43. A router comprising:

a. an interface layer including a plurality of I/O controllers, each I/O controller implementing an I/O port;

b. a switching layer in communication with said interface layer for selectively establishing signal pathways between said I/O ports; and

c. a routing layer in communication with said interface layer, said routing layer including a plurality of routing protocol computing entities, each routing protocol computing entity being associated with a set of at least one routing protocol and including;

i. a CPU; and

ii. a data storage medium in communication with said CPU and storing program data for execution by said CPU to cause said routing protocol computing entity to effect management of one or more peering sessions with remote routing devices according to the at least one routing protocol in the set associated with said routing protocol computing entity, said management of one or more peering sessions comprising maintaining in said data storage medium information on a plurality of routes;

wherein the data storage medium of a first one of said routing protocol computing entities contains information on at least one route for which there is no information in the data storage medium of a second one of said routing protocol computing entities;

said router being operative for;

merging routing data stored in the data storage medium of each of said routing protocol computing entities to produce merged routing data, the merged routine data mapping destinations and routes for the destinations;

pruning the merged routing data to discard a first subset of the routes for the destinations and retain a second subset of the routes for the destinations; and

transferring at least a portion of the merged routing data that has been pruned to the data storage medium of each of said routing protocol computing entities.

44. A router as defined in claim 43, wherein said pruning comprises pruning the merged routing data based on a preference attribute associated with each of the routes.

45. A router as defined in claim 43, wherein said routing layer includes a control computing entity in data communicative relationship with each of said routing protocol computing entities, said control computing entity including:

a CPU; and

a data storage medium in communication with said CPU of said control computing entity and storing program data for execution by said CPU of said control computing entity to cause said control computing entity to effect said merging and said pruning.

46. A router as defined in claim 43, wherein the set of at least one routing protocol associated with said first one of said routing protocol computing entities is different from the set of at least one routing protocol associated with said second one of said routing protocol computing entities.

47. A router as defined in claim 43, wherein the set of at least one routing protocol associated with said first one of said routing protocol computing entities is identical to the set of at least one routing protocol associated with said second one of said routing protocol computing entities.