System and method for router data distribution

• US 20030072271A1
• Filed: 09/17/2001
• Published: 04/17/2003
• 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: Li, Qiang, Liu, Bing, Visser, Lance Arnold, Kleiner, Jim, Simmons, Steve M.
• Granted Patent: US 7,483,433 B2
• Time in Patent Office: Days
• US Class Current: 370/255
• 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;

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, and such that said messages from said distributor to said multiple consumers are paced at said distributor, such that message congestion and message storms are avoided.

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 timers in said distributor minimize bandwidth saturation of said consumers.

5. The method of claim 4 wherein said distributor broadcasts different classes of messages to said multiple consumers for reliably maintaining said dynamically changing routing tables.

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

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

8. The method of claim 4 wherein said distributor uses a collection of timer intervals that are not integral multiples of one another, thereby assisting message load balancing by avoiding cyclical patterns.

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

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

11. The method of claim 9 wherein an update message contains a sequence number to define an instance of time of said update message relative to said snapshot.

12. The method of claim 11 wherein said distributor uses sequence numbers to reorder messages that are received out of order at said multiple consumers.

13. The method of claim 12 wherein said consumer sends a negative acknowledgement message to said distributor when said consumer detects that update messages are out of order.

14. The method of claim 13 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.

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

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

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

18. The method of claim 6 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.

19. The method of claim 6 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.

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

port up”

message from said consumer at said distributor.

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

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

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

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

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

26. 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 server having as clients said at least one source and said multiple consumers.

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

28. The method of claim 1 wherein said multiple consumers run on multiple router ports.

29. 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 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.

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

31. The protocol of claim 29 wherein timers in said distributor minimize bandwidth saturation of said consumers.

32. The protocol of claim 31 wherein timer intervals of said timers in said distributor are not integral multiples of one another, thereby avoiding cyclical patterns, such that message load balancing is improved and message storms are minimized.

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

34. The protocol of claim 29 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.

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

36. The protocol of claim 34 wherein each said update message contains a sequence number that defines an instance of time of said update message relative to said snapshot.

37. The protocol of claim 36 wherein said consumer uses said sequence numbers to reorder update messages that are received out of order.

38. The protocol of claim 37 wherein said consumer sends a negative acknowledgement message to said distributor after said consumer detects that said update messages are out of order.

39. The protocol of claim 38 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.

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

41. The protocol of claim 29 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.