Apparatus and method for multi-protocol route redistribution in a massively parallel router

• US 20050220123A1
• Filed: 04/28/2004
• Published: 10/06/2005
• Est. Priority Date: 04/02/2004
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Wybenga, Jack C., Sturm, Patricia Kay
• Granted Patent: US 7,660,314 B2
• Time in Patent Office: Days
• US Class Current: 370/400
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/60 Router architectures
• CPC Class Codes: H04L 49/25 Routing or path finding in a switch fabric
• CPC Class Codes: H04L 49/3009 Header conversion, routing tables or routing tags

Abstract

A router for interconnecting external devices coupled to the router. The router comprises: i) a switch fabric; ii) a plurality of routing nodes coupled to the switch fabric, wherein each of the plurality of routing nodes is capable of exchanging data packets with the external devices and with other ones of the plurality of routing nodes via the switch fabric; and iii) a first control processor associated with a first one of the plurality of routing nodes capable of generating a first refined redistribution metric associated with a first route in a routing table of the first routing node. The first control processor generates the first refined redistribution metric based on 1) a first default redistribution metric associated with a first routing protocol associated with the first route and 2) a first routing protocol metric received from the first routing protocol associated with the first route.

Claims

1. A router for interconnecting external devices coupled to said router, said router comprising:

a switch fabric;

a plurality of routing nodes coupled to said switch fabric, wherein each of said plurality of routing nodes is capable of exchanging data packets with said external devices and with other ones of said plurality of routing nodes via said switch fabric; and

a first control processor associated with a first one of said plurality of routing nodes capable of generating a first refined redistribution metric associated with a first route in a routing table of said first routing node, wherein said first control processor generates said first refined redistribution metric based on a first default redistribution metric associated with a first routing protocol associated with said first route.

2. The router as set forth in claim 1, wherein said first control processor generates said first refined redistribution metric based on a first routing protocol metric received from said first routing protocol associated with said first route.

3. The router as set forth in claim 2, wherein said first control processor is further capable of generating a second refined redistribution metric associated with a second route in said routing table of said first routing node, wherein said first control processor generates said second refined redistribution metric based on a second default redistribution metric associated with a second routing protocol associated with said second route.

4. The router as set forth in claim 3, wherein said first control processor generates said second refined redistribution metric based on a second routing protocol metric received from said second routing protocol associated with said second route.

5. The router as set forth in claim 4, wherein said first and second routes are associated with the same destination address.

6. The router as set forth in claim 5, wherein said first control processor compares said first refined redistribution metric and said second refined redistribution metric and, based on said comparison, selects one of said first and second refined redistribution metrics to be stored in an entry in said routing table associated with said first route.

7. The router as set forth in claim 6, wherein said first control processor distributes said selected one of said first and second refined redistribution metrics to said other ones of said plurality of routing nodes.

8. The router as set forth in claim 7, wherein said first control processor distributes an advertised route metric derived from said selected one of said first and second refined redistribution metrics to said external devices.

9. The router as set forth in claim 8, further comprising a second control processor associated with said switching fabric capable of comparing said selected refined redistribution metric received from said first routing node with a second selected refined redistribution metric received from a second routing node.

10. The router as set forth in claim 9, wherein said second control processor, based on said comparison, selects one of said selected refined redistribution metric received from said first routing node and said second selected refined redistribution metric received from said second routing node to be distributed to said other ones of said plurality of said routing nodes.

11. A communication network comprising a plurality of routers that communicate data packets to one another and to interfacing external devices, each of said plurality of routers comprising:

a switch fabric;

a plurality of routing nodes coupled to said switch fabric, wherein each of said plurality of routing nodes is capable of exchanging data packets with said external devices and with other ones of said plurality of routing nodes via said switch fabric; and

a first control processor associated with a first one of said plurality of routing nodes capable of generating a first refined redistribution metric associated with a first route in a routing table of said first routing node, wherein said first control processor generates said first refined redistribution metric based on a first default redistribution metric associated with a first routing protocol associated with said first route.

12. The communication network as set forth in claim 11, wherein said first control processor generates said first refined redistribution metric based on a first routing protocol metric received from said first routing protocol associated with said first route.

13. The communication network as set forth in claim 12, wherein said first control processor is further capable of generating a second refined redistribution metric associated with a second route in said routing table of said first routing node, wherein said first control processor generates said second refined redistribution metric based on a second default redistribution metric associated with a second routing protocol associated with said second route.

14. The communication network as set forth in claim 13, wherein said first control processor generates said second refined redistribution metric based on a second routing protocol metric received from said second routing protocol associated with said second route.

15. The communication network as set forth in claim 14, wherein said first and second routes are associated with the same destination address.

16. The communication network as set forth in claim 15, wherein said first control processor compares said first refined redistribution metric and said second refined redistribution metric and, based on said comparison, selects one of said first and second refined redistribution metrics to be stored in an entry in said routing table associated with said first route.

17. The communication network as set forth in claim 16, wherein said first control processor distributes said selected one of said first and second refined redistribution metrics to said other ones of said plurality of routing nodes.

18. The communication network as set forth in claim 17, wherein said first control processor distributes an advertised route metric derived from said selected one of said first and second refined redistribution metrics to said external devices.

19. The communication network as set forth in claim 18, further comprising a second control processor associated with said switching fabric capable of comparing said selected refined redistribution metric received from said first routing node with a second selected refined redistribution metric received from a second routing node.

20. The communication network as set forth in claim 19, wherein said second control processor, based on said comparison, selects one of said selected refined redistribution metric received from said first routing node and said second selected refined redistribution metric received from said second routing node to be distributed to said other ones of said plurality of said routing nodes.

21. A method for distributing routing information for use in a router comprising a switch fabric and a plurality of routing nodes coupled to the switch fabric, wherein each of the plurality of routing nodes is capable of exchanging data packets with external devices and with other routing nodes via the switch fabric, the method comprising the steps of:

receiving in a first of the plurality of routing nodes a first routing protocol metric from a first routing protocol associated with a first route in a routing table of the first routing node;

determining a first default redistribution metric associated with the first routing protocol; and

generating a first refined redistribution metric from the first routing protocol metric and the first default redistribution metric.

22. The method as set forth in claim 21, further comprising the steps of:

receiving in the first routing node a second routing protocol metric from a second routing protocol associated with a second route in the routing table of the first routing node;

determining a second default redistribution metric associated with the second routing protocol; and

generating a second refined redistribution metric from the second routing protocol metric and the second default redistribution metric.

23. The method as set forth in claim 22, wherein the first and second routes are associated with the same destination address.

24. The method as set forth in claim 23, further comprising the steps of:

comparing the first refined redistribution metric and the second refined redistribution metric; and

selecting one of the first and second refined redistribution metrics based on the comparison to be stored in an entry in the routing table associated with the first route.

25. The method as set forth in claim 24, further comprising the step of distributing the selected one of the first and second refined redistribution metrics to the other ones of the plurality of routing nodes.

26. The method as set forth in claim 25, further comprising the step of distributing an advertised route metric derived from the selected one of the first and second refined redistribution metrics to the external devices.

27. The method as set forth in claim 26, further comprising the step of comparing in the switching fabric the selected refined redistribution metric received from the first routing node with a second selected refined redistribution metric received from a second routing node.

28. The method as set forth in claim 27, further comprising the step, based on the comparison, of selecting one of the selected refined redistribution metric received from the first routing node and the second selected refined redistribution metric received from the second routing node to be distributed to the other ones of the plurality of the routing nodes.