System and method for router data distribution

• US 7,483,433 B2
• Filed: 09/17/2001
• Issued: 01/27/2009
• Est. Priority Date: 09/17/2001
• Status: Expired due to Fees

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Foundry Networks Incorporated (Broadcom, Inc.)
• Inventors: Li, Qiang, Liu, Bing, Simmons, Steve M., Visser, Lance Arnold, Kleiner, Jim
• Primary Examiner(s): Moe; Aung S
• Assistant Examiner(s): Mered; Habte
• Application Number:
  US09/954,362
• Publication Number:
  US 20030072271A1
• Time in Patent Office: 2,689 Days
• Field of Search: 370/254, 370351-356, 370465-467, 370/255, 370/389, 370/390, 370/394, 370/432, 370/395.31, 709/214, 709/203, 709238-244
• 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 sends current tables to the distributor using a snapshot mechanism. Messages 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. In a router network, a reliable method of broadcasting dynamically changing routing tables incrementally from at least one source to multiple consumers in accordance with a protocol, comprising:

maintaining a copy of the current contents of said routing tables on said at least one source, said routing tables defining a destination of data packets as it arrives, and centrally maintained on a master control processor (MCP) by a routing protocol application;

communicating said dynamic changes in said routing tables from said at least one source to a single active distributor;

buffering said dynamic changes at said distributor; and

broadcasting said dynamic changes in messages from said distributor to said multiple consumers, such that said broadcast dynamic changes are received and applied consistently across said multiple consumers, the set of routes received from a given peer temporarily stored in memory so that the broadcast dynamic changes provide said copy of the current contents from the one source to each routing table, such that the routing tables contain at least one unique session identifier associated with each specific source dynamic routing protocol (DRP) application, and contain consistently identical dynamic changes, such that each routing table contains the same external routing data and said messages from said distributor to said multiple consumers are paced at said distributor, while avoiding message congestion and message storms, wherein timers in said distributor minimize bandwidth saturation of said consumers, and wherein said distributor uses a collection of timer intervals, in broadcasting of said dynamic changes in messages, that are not integral multiples of one another, thereby assisting message load balancing by avoiding cyclical patterns.

2. The method of claim 1 wherein said distributor rebroadcasts each said message multiple times, thereby minimizing lost messages.

3. The method of claim 2 wherein said distributor broadcasts each said message at least three times.

4. The method of claim 1 wherein:

said distributor broadcasts different classes of messages to said multiple consumers for reliably maintaining said dynamically changing routing tables.

5. The method of claim 4 wherein said different classes of messages comprise initialization, update, resend, and keepalive messages.

6. The method of claim 5 wherein said timers in said distributor allocate bandwidth for each class of message.

7. The method of claim 5 further comprising using a snapshot mechanism, thereby allowing said at least one source to continue sending update messages while said routing table changes are being initialized.

8. The method of claim 7 wherein said snapshot mechanism is used when said distributor has too many update messages to send to said consumers.

9. The method of claim 7 wherein:

an update message contains a sequence number to define an instance of time of said update message relative to said snapshot;

said distributor uses sequence numbers to reorder messages that are received out of order at said multiple consumers; and

said consumer sends a negative acknowledgement message to said distributor when said consumer detects that update messages are out of order.

10. The method of claim 9 wherein said consumer can send said negative acknowledgement only after receiving a keepalive message from said distributor, thereby avoiding network saturation from having too many consumers replying.

11. The method of claim 9 wherein said distributor resends said out of order update messages to said consumers after receiving said negative acknowledgement message from said consumer.

12. The method of claim 10 wherein said out of order update messages are marked in a history buffer prior to resending.

13. The method of claim 10 wherein said out of order update messages are resent only after firing a resend timer at said distributor.

14. The method of claim 5 wherein said initialization messages include a segment identifier and a segment total, such that said consumers are permitted to join in the middle of a broadcast scenario.

15. The method of claim 5 wherein said initialization messages and said update messages include a session ID, such that said multiple sources and multiple consumers can share a common broadcast distributor.

16. The method of claim 1 wherein said broadcasting is initialized after receiving a “

port up”

message from said consumer at said distributor.

17. The method of claim 1 wherein said protocol is asymmetric.

18. The method of claim 1 wherein said at least one source comprises at least one Dynamic Routing Protocol (DRP) routing software application.

19. The method of claim 1 wherein said at least one source runs on a control processor.

20. The method of claim 1 wherein said at least one source comprises four said sources.

21. The method of claim 1 wherein said distributor runs on a control processor.

22. The method of claim 1 wherein said distributor comprises a multi-threaded server which communicates bidirectionally with said at least one source on one thread, which communicates bidirectionally with said multiple consumers on a second thread, and which operates timers on a third thread, said distributor having as clients said at least one source and said multiple consumers.

23. The method of claim 22 wherein said distributor comprises a Reliable Table Distribution (RTD) Daemon.

24. The method of claim 1 wherein said multiple consumers run on multiple router ports, whereby each port receives only its own set of routing table updates and excludes all others.

25. In a router system, an asymmetric reliable table distribution protocol comprising:

a distributor including multiple senders including timers, buffers, and history queues;

multiple consumers including update queues and tables;

said distributor broadcasting three different classes of messages including initialization, incremental update, and keepalive messages to said consumers;

and said consumer sending, in a broadcast of dynamic changes in messages, two different classes of messages including initialization start messages and negative acknowledgement messages to said distributor, such that identical copies of a dynamically changing routing table are maintained across all of said multiple consumers, wherein timers in said distributor minimize bandwidth saturation of said consumers, and wherein timer intervals of said timers in said distributor are not integral multiples of one another, thereby avoiding cyclical patterns , the messages containing routes received from a given peer temporarily stored in the memory so that the broadcast dynamic changes provide said copy of the current contents from the one source to each routing table, such that the routing tables contain at least one unique session identifier associated with each specific source dynamic routing protocol (DRP) application, and contain consistently identical dynamic changes and each routing table contains the same external routing data, and improving message load balancing and minimizing message storms, said routing tables defining a destination of data packets as it arrives, and centrally maintained on a master control processor (MCP) by a routing protocol application.

26. The protocol of claim 25 wherein said distributor broadcasts messages multiple times, thereby minimizing lost messages.

27. The protocol of claim 25 wherein timers in the distributor allocate bandwidth for each said class of messages.

28. The protocol of claim 25 further comprising using a snapshot mechanism, thereby allowing said senders to continue sending incremental update messages to said consumers while said routing tables are being initialized.

29. The protocol of claim 28 wherein said snapshot mechanism is used when said distributor has too many update messages to send to said consumers.

30. The protocol of claim 28 wherein:

each said update message contains a sequence number that defines an instance of time of said update message relative to said snapshot;

said consumer uses said sequence numbers to reorder update messages that are received out of order; and

said consumer sends a negative acknowledgement message to said distributor after said consumer detects that said update messages are out of order.

31. The protocol of claim 30 wherein said consumer sends said negative acknowledgement message only after receiving a keepalive message from said distributor, thereby minimizing network saturation from having too many consumers replying concurrently.

32. The protocol of claim 25 wherein said initialization messages include a segment identifier and a segment total, such that receivers can join in the middle of a broadcast scenario.

33. The protocol of claim 25 wherein said update messages and said initialization messages each include a session ID, such that multiple sources and multiple consumers can share a common broadcast distributor.

34. In a router network, a reliable method of broadcasting dynamically changing routing tables incrementally from at least one source to multiple consumers in accordance with a protocol, comprising:

maintaining a copy of the current contents of said routing tables on said at least one source, said routing tables defining a destination of data packets as it arrives, and centrally maintained on a master control processor (MCP) by a routing protocol application;

communicating said dynamic changes in said routing tables from said at least one source to a single active distributor;

buffering said dynamic changes at said distributor; and

broadcasting a plurality of classes of messages to said multiple consumers, including broadcasting said dynamic changes in at least one of said plurality of classes of messages, such that said broadcast dynamic changes are received and applied consistently across said multiple consumers, and wherein each of said classes of messages is assigned a budgeted time interval for broadcasting the set of routes received from a given peer temporarily stored in the memory, the broadcast dynamic changes providing said copy of the current contents from the one source to each routing table, such that the routing tables contain at least one unique session identifier associated with each specific source dynamic routing protocol (DRP) application, and contain consistently identical dynamic changes and each routing table contains the same external routing data, and avoiding message congestion and message storms.