Scalable router

• US 20030021232A1
• Filed: 07/27/2001
• Published: 01/30/2003
• Est. Priority Date: 07/27/2001
• Status: Active Grant

• Current Assignee: RPX Corporation
• Original Assignee: Hyperchip Incorporated
• Inventors: Duplaix, Jerome, Wickrema, Gamini, Goulet, Stephan
• Granted Patent: US 7,403,530 B2
• Time in Patent Office: Days
• US Class Current: 370/238
• 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, 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;

c. a routing layer in communication with said interface layer, said routing layer having at least first and second routing protocol computing entities, each routing protocol computing entity including;

i. a CPU,

ii. a data storage medium in communication with said CPU;

iii. program data stored in said data storage medium for execution by said CPU;

d. the program data in the data storage medium of said first routing protocol computing entity effecting management of one or more peering sessions with remote routing devices according to a first routing protocol, when executed by the CPU of said first routing protocol computing entity,

e. the program data in the data storage medium of said second routing protocol computing entity effecting management of one or more peering sessions with remote routing devices according to a second routing protocol when executed by the CPU of said second routing protocol computing entity; and

f. said first routing protocol being different from said second routing protocol.

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 2, wherein each routing protocol computing entity exchanges 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 a remote routing device.

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

6. A router as defined in claim 5, wherein the data storage medium of said first routing protocol computing entity stores a local routing table holding 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 said first routing protocol computing entity applies an inbound policy processing on the route information data transferred from a remote routing device during generation of the inbound route database.

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

9. A router as defined in claim 8, wherein the data storage medium of each routing protocol computing entity stores a local routing table holding 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 applies an inbound policy processing on the route information data transferred from a remote routing device during generation of the 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, the routing protocol of each routing protocol computing entity applies an outbound policy processing on the best route database to generate at least one outbound route database, each routing protocol computing entity being operative to transfer route information data from said outbound route database 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;

b. a data storage medium in communication with said CPU;

c. a program data stored in sad data storage medium for execution by said CPU;

d. a master routing table stored in said data storage medium.

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 inbound route database.

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 inbound routing 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 routing databases from said first and said second routing protocol computing entities to produce merged inbound routing data.

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

18. A router as defined in claim 17, wherein the merged inbound 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 said first routing protocol computing entity at least a portion of the master routing data to form the best route database in the data storage medium of said first routing protocol computing entity.

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

21. A router as defined in claim 18, 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 trough 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 said first routing protocol is BGP, and said second routing protocol is OSPF.

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

c. a routing layer in communication with said interface layer, said routing layer having at least first and second routing protocol computing entities, each routing protocol computing entity including;

i. a CPU;

ii. a data storage medium in communication with said CPU;

iii. a program data stored in said data storage medium for execution by said CPU;

d. the program data in the storage medium of said first routing protocol computing effecting management of one or more peering sessions with remote routing devices according to a first routing protocol, when executed by the CPU of said first routing protocol computing entity;

e. the program data in the storage medium of said second routing protocol computing entity effecting management of one or more peering sessions with remote routing devices according to a second routing protocol when executed by the CPU of said second routing protocol computing entity; and

f. the first routing protocol being the same as the second routing protocol.

24. A router as defined in claim 23, wherein the first routing protocol and the second routing protocol are distance vector protocols.

25. A router as defined in claim 24, wherein the first routing protocol and the second routing protocol are link state protocols.

26. A router as defined in claim 25, wherein the first routing protocol computing entity is capable of establishing peering sessions with a first set of remote routing devices, the second routing protocol computing entity 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.

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

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

29. A router as defined in claim 26, wherein the first routing protocol computing entity is capable of establishing peering sessions remote routing devices from a first area, the second routing protocol computing entity is capable of establishing peering sessions with remote routing devices from a second area, the first area being different from the second area.

30. A router as defined in claim 23, wherein said first and second routing protocols are BGP.

31. A router, comprising:

a. an interface layer including 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;

c. a routing layer in communication with said interface layer, said routing layer being capable of managing at least one peering session with a remote routing device, the peering session including the exchange of messages with the remote routing device through one of the I/O controllers, the peering session being comprised of a plurality of tasks;

d. the one I/O controller implementing a peering session assist module,

e. said peering session assist module being capable of performing some of the tasks of the peering session autonomously from said routing layer;

f. said routing layer being capable of performing tasks of the peering session other than the tasks performed by the peering session assist module.

32. A router as defied in claim 31, wherein the tasks performed by the peering session assist module include monitoring a state of a connection with the remote routing device.

33. A router as defined in claim 32, wherein the monitoring of the state of the connection with the remote routing device includes supervising the reception of keepalive or hello messages.

34. A router as defined in claim 33, wherein the monitoring of the state of the connection with the remote routing device includes sending keepalive or hello messages to the remote routing device.

35. A router as defined in claim 31, wherein the tasks performed by the peering session assist module include authenticating messages received from the remote routing device.

36. A router as defined in claim 31, wherein one of the tasks performed by said routing layer is applying an inbound policy processing on route information received from the remote routing device.

37. A router as defined in claim 31, wherein one of the tasks performed by said routing layer is applying an outbound policy processing on route information.

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

c. a routing layer in communication with said interface layer;

d. each I/O controller implementing an LSA entity, said LSA entity including an LS database, said LSA entity being responsive to an LSA message from a remote routing device including LS information to;

i. update said LS database;

ii. forward the LS information to said routing layer;

iii. forward the LS information to at least another I/O controller of said interface layer.

39. A router as defined in claim 38 wherein said LSA entity is operative to verify, upon reception of the LSA message, whether the LS information is already present in said LS database and in the affirmative to discard the LSA message.

40. A router as defined in claim 39, wherein said LSA entity is responsive to reception of LS information received from another I/O controller of said interface layer to forward an LSA message including the LS information to a remote routing device.

41. A router as defined in claim 38, wherein said routing layer includes:

a. a control computing entity in data communicative relationship with each I/O controller, said control computing entity, including;

i. a CPU;

ii. a data storage medium in communication with said CPU;

iii. a master routing table stored in said data stowage medium, said master routing table holding a master routing database derived at least in part from the LS database of at least one of said I/O controllers;

iv. program data in said data storage medium to implement a main routing table manager to manage said master routing table;

b. a backup computing entity in data communicative relationship with at least one of said I/O controller, said backup computing entity including;

i. a CPU;

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

iii. program data in the data storage medium of said backup computing entity for execution by the CPU of said backup computing entity to implement a main routing table manager;

iv. said backup computing entity being responsive to an operational failure of said control computing entity to;

1. transfer information from at least one of said I/O controllers to re-build the LS database;

2. enable the program data in the data storage medium of said backup computing entity to act as a main routing table manager.

42. A router, comprising;

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

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

c. a routing layer in communication wit said interface layer, said routing layer having at least first and second routing protocol computing entities, each routing protocol computing entity including;

i. a CPU;

ii. a data storage medium in communication with said CPU;

iii. a program data stored in said data storage medium for execution by said CPU;

d. the program data in the storage medium of said first routing protocol computing entity effecting management of one or more peering sessions with remote routing devices according to a first routing protocol, when executed by the CPU of said first routing protocol computing entity;

e. the program data in the storage medium of said second routing protocol computing entity effecting management of one or more peering sessions with remote routing devices according to a second routing protocol when executed by the CPU of said second routing protocol computing entity;

f. the data storage medium of said first routing protocol computing entity holding a local routing table storing an inbound routing database derived from route information transferred from a remote routing device during a peering session managed by said first routing protocol computing entity;

g. the data storage medium of said second routing protocol computing entity holding a local routing table storing an inbound routing database derived from route information transferred from a remote routing device during a peering session managed by said second routing protocol computing entity;

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

i. a CPU;

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

iii. a master routing table stored in the data storage medium of said control computing entity, said master routing table holding a master routing database derived at least in part from the inbound routing database of said first routing protocol computing entity and from the inbound routing database of said second routing protocol computing entity;

iv. program data in the data storage medium of said control computing entity for execution by the CPU of said control computing entity to implement a main routing table manager to manage said master routing table;

i. a backup computing entity in data communicative relationship with said first and second routing protocol computing entities and with said control computing entity, said backup computing entity including;

i. a CPU;

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

iii. program data in the data storage medium of said backup computing entity for execution by the CPU of said backup computing entity to implement a main routing table manager;

iv. said backup computing entity being responsive to an operational failure of said control computing entity to;

1. dowwnload the inbound routing databases from said first and second routing protocol computing entities;

2. re-build the master routing database at least in part from the inbound routing databases downloaded from said first and second routing protocol computing entities.

43. A router as defined in claim 42, wherein said first routing protocol is different from said second routing protocol.

44. A router as defined in claim 42, wherein said first routing protocol is the same as said second routing protocol.

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

c. a routing layer in communication with said interface layer, said routing layer having at least first and second routing protocol computing entities, each routing protocol computing entity including;

i. a CPU;

ii. a data storage medium in communication with said CPU;

iii a program data stored in said data storage medium for execution by said CPU;

d. the program data in the storage medium of said first routing protocol computing entity effecting management of one or more peering sessions with remote routing devices according to a first routing protocol, when executed by the CPU of said first routing protocol computing entity;

e. the program data in the storage medium of said second routing protocol computing entity effecting management of one or more peering sessions with remote routing devices according to a second routing protocol when executed by the CPU of said second routing protocol computing entity;

f. the data storage medium of said first routing protocol computing entity holding a local routing table storing an inbound routing database derived from route information transferred from a remote routing device during a peering session managed by said first routing protocol computing entity;

g. the data storage medium of said second routing protocol computing entity holding a local routing table storing an inbound routing database derived from route information transferred from a remote routing device during a peering session managed by said second routing protocol computing entity;

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

i. a CPU;

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

iii. a master routing table stored in the data storage medium of said control computing entity, said master routing table holding a master routing database derived at least in part from the inbound routing database of said first routing protocol computing entity and from the inbound routing database of said second routing protocol computing entity;

iv. a program data in the data storage medium of said control computing entity for execution by the CPU of said control computing entity to implement a main routing table manager to manage said master routing table;

i. a backup computing entity in data communicative relationship with said first and second routing protocol computing entities and with said control computing entity, said backup computing entity including;

i. A CPU;

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

iii. a program data in the data storage medium of said backup computing entity for execution by the CPU of said backup computing for effecting management of one or more peering sessions with remote routing devices according to a first routing protocol;

iv. said backup computing entity being responsive to an operational failure of said first routing protocol computing entity to;

1. transfer information from said master routing table to the data storage medium of said backup computing entity to re-build at least partially the local routing table of said first routing protocol computing entity;

2. enable the program data in the data storage medium of said backup computing entity to effect management of one or more peering sessions with remote routing devices according to a first routing protocol.

46. A router as defined in claim 45, wherein said fist routing protocol is different from said second routing protocol.

47. A router as defined in claim 45, wherein said first routing protocol is the same as said second routing protocol.