Granted Patent B2

US 7,739,404 · App. 11/616,380 · Granted Jun 15, 2010

Abstract

Claims (32)

1. A method of distributing routing information from a Border Gateway Protocol (BGP) network device to a plurality of BGP peers over a network, the method comprising:

forming at least one group into which to place the BGP peers;

placing each BGP peer into one group of the at least one group; and

generating a BGP update message for each BGP peer individually in a select group of the at least one group during a time interval of specified duration, each update message containing a number of routes based on the duration of that time interval, the routes included in the update message for each BGP peer being determined for that BGP peer based on an outbound routing policy for that BGP peer.

2. The method of claim 1 , further comprising the step of automatically and dynamically determining a number of groups.

3. The method of claim 2 , wherein the number of groups is based on a number of withdrawn routes and a number of advertisement routes to be distributed.

4. The method of claim 3 , wherein the number of groups is smaller when the number of withdrawn routes exceeds the number of advertisement routes than for when the number of advertisement routes exceeds the number of withdrawn routes.

5. The method of claim 1 , wherein the time interval has a duration of approximately 50 ms.

6. The method of claim 1 , further comprising the step of releasing a central processing unit of the BGP device for use in processing other tasks after the time interval expires if other tasks need CPU.

7. The method of claim 1 , wherein each BGP peer may be placed into any group of the at least one group irrespective of the outbound routing policy of each BGP peer.

8. The method of claim 1 , wherein two or more of the BGP peers in the select group can have different outbound routing policies.

9. A method of accelerating convergence for updating routing tables at a plurality of border gateway protocol (BGP) peers, the method comprising:

dynamically calculating, by a BGP network device, a number of groups and a number of peers in each group based on routing information to be distributed;

specifying a time interval within which to generate an update message for each BGP peer in a select one of the groups;

generating an update message for each BGP peer in the select group during the time interval, each update message containing a number of routes based on the duration of the time interval; and

forwarding the update messages for transmission to the BGP peers in the select group after the time interval expires.

10. The method of claim 9 wherein the step of generating includes the step of adding one or more routes to the update message for each peer in the select group based on an outbound routing policy of that peer.

11. The method of claim 9 further comprising the step of releasing processor resources, after the time interval expires, so that such resources can be used to process tasks other than for generating the update messages.

12. The method of claim 9 further comprising the step of repeating the steps of generating and forwarding update messages for each peer in the select group during subsequent time intervals until the BGP device has completely processed the routing information to be distributed to each BGP peer in the select group.

13. The method of claim 9 , further comprising the steps of:

selecting a next group of peers;

generating an update message for each peer in the selected next group during a subsequent time interval; and

forwarding the update messages generated for each peer in the selected next group to the peers in the selected next group when the subsequent time interval expires.

14. A border gateway protocol (BGP) network device in communication with a plurality of BGP peers over a network, the BGP network device comprising:

memory storing a routing table and program code with computer-readable instructions for distributing changes to the routing table to the BGP peers; and

a processor executing the program code to determine a number of groups into which to place the BGP peers and to place each BGP peer into one group in the number of groups, the processor generating a BGP update message individually for each BGP peer in a select group in the number of groups during a time interval of specified duration, each update message containing a number of routes based on the duration of that time interval, the routes included in the update message for each BGP peer being determined for that BGP peer based on an outbound routing policy for that BGP peer.

15. The BGP network device of claim 14 , wherein the number of groups is based on a number of withdrawn routes and a number of advertisement routes to be distributed.

16. The BGP network device of claim 15 , wherein the number of groups is smaller when the number of withdrawn routes exceeds the number of advertisement routes than for when the number of advertisement routes exceeds the number of withdrawn routes.

17. The BGP network device of claim 14 , wherein the time interval has a duration of approximately 50 ms.

18. The BGP network device of claim 14 , wherein after the time interval expires the processor becomes available to process other tasks than generating update messages.

19. The BGP network device of claim 14 , wherein each BGP peer may be placed into any group in the number of groups irrespective of the outbound routing policy of each BGP peer.

20. The BGP network device of claim 14 , wherein two or more of the BGP peers in the select group can have different outbound routing policies.

Assignments (23)