System and method for router data distribution

• US 8,335,219 B2
• Filed: 12/11/2008
• Issued: 12/18/2012
• Est. Priority Date: 09/17/2001
• Status: Active Grant

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Foundry Networks LLC (Broadcom, Inc.)
• Inventors: Simmons, Steve M., Kleiner, Jim, Li, Qiang, Liu, Bing, Visser, Lance Arnold
• Primary Examiner(s): Mered, Habte
• Application Number:
  US12/333,029
• Publication Number:
  US 20090092135A1
• Time in Patent Office: 1,468 Days
• Field of Search: 709/203, 709/214, 709/242, 709/238, 709/244, 370/254, 370/255, 370351-356, 370/389, 370/390, 370/394, 370/432, 370465-467, 370/395.31
• US Class Current: 370/395.31
• CPC Class Codes: H04L 1/1614 using bitmaps
• CPC Class Codes: H04L 12/1868 Measures taken after transmission, e.g. acknowledgments
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/021 Ensuring consistency of routing table updates, e.g. by using epoch numbers
• CPC Class Codes: H04L 45/42 Centralised routing
• CPC Class Codes: H04L 47/12 Avoiding congestion; Recovering from congestion
• CPC Class Codes: H04L 47/15 in relation to multipoint traffic arrangements for broadcast or multicast in data networks H04L12/18
• CPC Class Codes: H04L 47/22 Traffic shaping

Abstract

Employing an asymmetric protocol, multiple sources reliably broadcast dynamically changing routing tables incrementally across multiple consumers from a single distributor. Each of multiple sources send current tables to the distributor using a snapshot mechanism. Message are buffered, segmented, paced by timers, and broadcast to the consumers repetitively at the distributor. Negative acknowledgments from the consumer request missing messages from the distributor after receipt of a keepalive message from the distributor. The distributor marks the missing messages and retransmits replacements from a history buffer only after firing of a resend timer. A unique Session ID included in all messages originating from each particular source facilitates reliable table distribution from multiple sources to multiple consumers via a single distributor.

Claims

1. A router, comprising:

one or more virtual routers, each maintaining a dynamic routing protocol application, wherein a respective dynamic routing protocol application is configurable to construct a routing table for the corresponding virtual router;

one or more line cards;

a routing table distribution application residing within the router and in communication with the one or more virtual routers and one or more line cards;

wherein the routing table distribution application is configurable to;

receive routing table updates from the one or more virtual routers;

and

construct a message containing the received updates to the one or more line cards.

2. The router of claim 1, wherein the dynamic routing application is further configurable to update the routing table.

3. The router of claim 1, wherein the routing table distribution application comprises one or more buffers;

wherein a respective buffer is configurable to receive routing table updates from a respective virtual router.

4. The router of claim 1, wherein the routing table distribution application comprises one or more timing modules configurable to regulate the distribution of routing table updates.

5. The router of claim 1, further comprising a backup routing table distribution application.

6. The router of claim 1, wherein a respective routing table update comprises a sequence number associated with the corresponding virtual router.

7. The router of claim 1, wherein the routing table distribution application is further configurable to re-broadcast the updates to the one or more line cards to ensure reliable delivery.

8. A method, comprising:

receiving at a routing table distribution application routing table updates from one or more virtual routers; and

constructing a message containing the received updates to one or more line cards;

wherein the routing table distribution application, one or more virtual routers, and one or more line cards are within a router; and

wherein each virtual router maintains a dynamic routing protocol application configurable to construct a routing table for the corresponding virtual router.

9. The method of claim 8, further comprising updating a routing table within a respective virtual router.

10. The method of claim 8, wherein receiving the routing table updates comprises receiving the routing table updates in one or more buffers;

wherein a respective buffer is configurable to store routing table updates from a respective virtual router.

11. The method of claim 8, wherein distributing the received updates to the one or more line cards comprises regulating the distribution of routing table updates by using one or more timing modules.

12. The method of claim 8, further comprising distributing the received updates to the one or more line cards by a backup routing table distribution application.

13. The method of claim 8, wherein a respective routing table update comprises a sequence number associated with the corresponding virtual router.

14. The method of claim 8, further comprising re-broadcasting the updates to the line cards by the routing table distribution application to ensure reliable delivery.

15. A computing system, comprising:

a processor; and

a non-transitory computer-readable storage medium storing instructions that when executed by the processor cause the computing system to perform a method for distributing routing tables, the method comprising;

maintaining a respective dynamic routing protocol application configurable to construct a routing table in a respective virtual router;

receiving at a routing table distribution application routing table updates from one or more virtual routers;

constructing a message containing the received updates to one or more line cards;

wherein the routing table distribution application, one or more virtual routers, and one or more line cards are within a router.

16. The computing system of claim 15, wherein the method further comprises updating a routing table within a respective virtual router.

17. The computing system of claim 15, wherein receiving the routing table updates comprises receiving the routing table updates in one or more buffers;

wherein a respective buffer is configurable to store routing table updates from a respective virtual router.

18. The computing system of claim 15, wherein the method further comprises regulating the distribution of routing table updates by using one or more timing modules.

19. The computing system of claim 15, wherein the method further comprises distributing the received updates to the one or more line cards by a backup routing table distribution application.

20. The computing system of claim 15, wherein a respective routing table update comprises a sequence number associated with the corresponding virtual router.

21. The computing system of claim 15, wherein the method further comprises re-broadcasting the updates to the line cards by the routing table distribution application to ensure reliable delivery.