Graceful restart (GR) methods and devices

1. A Graceful Restart (GR) method for a network with multiple GR Restarters that include a first GR Restarter and at least one second GR Restarter corresponding to the first GR Restarter, the method comprising the first GR Restarter:

after receiving information on routes from all normal neighbor network devices of the first GR Restarter, performing route selection to determine first selected routes, and sending information on the first selected routes to the at least one second GR Restarter,

after receiving information on routes from the at least one second GR Restarter, performing route selection to determine second selected routes, updating a local Forwarding Information Base (FIB) at the first GR Restarter with information on the second selected routes, and sending the information on the second selected routes to all neighbor network devices of the first GR Restarter;

wherein the first GR Restarter directly connects with the at least one second GR Restarter corresponding to the first GR Restarter.

2. The method according to claim 1 , wherein the network implements a Border Gateway Protocol (BGP), and wherein the first GR Restarter and each second GR Restarter are selected from the multiple GR Restarters as master GR Restarter and slave GR Restarter respectively and the multiple GR Restarters form an aggregation.

3. The method according to claim 1 , wherein after the first selected routes are determined, the method further comprises:

determining whether complete routes from all neighbor network devices of the first GR Restarter are received, and if yes,

updating the local FIB with the information on the first selected routes; and

sending the information on the first selected routes to all second GR Restarters corresponding to the first GR Restarter.

4. The method according to claim 3 , wherein sending the information on the first selected routes to all second GR Restarters of the first GR Restarter comprises:

if information on complete routes from all normal neighbor network devices of the first GR Restarter are received and information on complete routes from at least two second GR Restarters corresponding to first GR Restarter are not received,

denoting the first selected routes as incomplete routes, and

sending the information on the first selected routes denoted as the incomplete routes to all second GR Restarters corresponding to first GR Restarter,

if the information on the complete routes from all normal neighbor network devices of the first GR Restarter are received but information on a complete route from at most one second GR Restarter corresponding to first GR Restarter is not received,

denoting the first selected routes as the complete routes, and

sending the information on the first selected routes denoted as the complete routes to the at most one second GR Restarter,

denoting the first selected routes as the incomplete routes, and

sending the information on the first selected routes denoted as the incomplete routes to any other second GR Restarter corresponding to first GR Restarter,

if the information on complete routes from all normal neighbor network devices of the first GR Restarter are not received,

denoting the first selected routes as the incomplete routes, and

sending the information on the first selected routes denoted as the incomplete routes to all second GR Restarters corresponding to first GR Restarter.

5. The method according to claim 1 , wherein after the first selected routes are determined, the method further comprises:

determining whether information on complete routes from all neighbor network devices of the first GR Restarter are received, and if yes, updating the local FIB with the first selected routes;

if the first GR Restarter does not receive information on a complete route from a second GR Restarter,

adding the second GR Restarter to a second GR Restarter aggregation; and

sending the information on the first selected routes to the at least one second GR Restarter corresponding to first GR Restarter, wherein sending the information on the first selected routes further comprises sending the information on the first selected routes to all second GR Restarters in the second GR Restarter aggregation of the first GR Restarter.

6. The method according to claim 4 , wherein denoting the first selected routes as the complete routes comprises:

generating a first End-of-RIB (EOR) message which does not carry a Partial flag; and

denoting the first selected routes as the incomplete routes, wherein denoting the first selected routes as the incomplete routes comprises generating a second EOR message carrying the Partial flag.

7. The method according to claim 2 , wherein each of the at least one first GR Restarter corresponding to the second GR Restarter is selected from one of two directly-connected GR Restarters in the multiple GR Restarters with the maximum or minimum ID.

8. A Graceful Restart (GR) method for a network with multiple GR Restarters that include a second GR Restarter and at least one first GR Restarter corresponding to the second GR Restarter, the method comprising the second GR Restarter:

after receiving information on routes from all neighbor network devices of the second GR Restarter, performing route selection to determine first selected routes,

if information on complete routes from all the neighbor network devices of the second GR Restarter are received, updating a local FIB at the second GR Restarter with information on the first selected routes;

otherwise, sending information on the first selected routes to the at least one first GR Restarter corresponding to second GR Restarter, performing route selection to determine second selected routes until information on complete routes from all neighbor network devices of the second GR Restarter are received, updating the local FIB with information on the second selected routes, and sending the information on the second selected routes to all the neighbor network devices of the second GR Restarter;

wherein the second GR Restarter directly connects with the at least one first GR Restarters corresponding to the second GR Restarter.

9. The method according to claim 8 , wherein the network implements a Border Gateway Protocol (BGP), and wherein the second GR Restarter and each first GR Restarter are selected from the multiple GR Restarters as slave GR Restarter and master GR Restarter respectively and the multiple GR Restarters form an aggregation.

10. The method according to claim 8 , wherein sending the information on the first selected routes to the at least one first GR Restarter corresponding to the second GR Restarter comprises sending the information on the first selected routes to all first GR Restarters corresponding to second GR Restarter.

11. The method according to claim 10 , wherein sending the information on the first selected routes to all first GR Restarters corresponding to second GR Restarter comprises:

if the second GR Restarter receives information on complete routes from all normal neighbor network devices of the second GR Restarter and if information on an incomplete route from one first GR Restarter corresponding to second GR Restarter is not received; or

if information on complete routes from all first GR Restarters are received but information on complete routes from at least two second GR Restarters are not received,

denoting the first selected routes as incomplete routes, and

sending the information on the first selected routes denoted as the incomplete routes to all first GR Restarters corresponding to second GR Restarter and any other GR Restarter,

if the second GR Restarter receives the information on complete routes from all normal neighbor network devices of the second GR Restarter and does not receive information on a complete route from at most one master GR Restarter corresponding to second GR Restarter,

denoting the first selected routes as the complete routes, and

sending the information on the first selected routes denoted as the complete routes to the at most one second GR Restarter,

denoting the first selected routes as the incomplete routes, and

sending the information on the first selected routes denoted as the incomplete routes to all first GR Restarters corresponding to second GR Restarter and any other GR Restarter.

12. The method according to claim 8 , wherein the method further comprises:

adding, if information on a complete route from a first GR Restarter is not received, the first GR Restarter to a first GR Restarter aggregation; and sending the information on the first selected routes to the first GR Restarters corresponding to second GR Restarter, wherein sending the information on the first selected routes comprises sending the information on the first selected routes to all first GR Restarters in the first GR Restarter aggregation of the second GR Restarter.

13. The method according to claim 11 , wherein denoting the first selected routes as the complete routes comprises:

generating a first End-of-RIB (EOR) message which does not carry the Partial flag; and

denoting the first selected routes as the incomplete routes, wherein denoting the first selected routes as the incomplete routes comprises generating a second EOR message carrying the Partial flag.

14. A device capable of acting as a first Graceful Restart (GR) Restarter in a network with multiple GR Restarters that include the first GR Restarter and at least one second GR Restarter corresponding to the first GR Restarter, the device comprising:

a memory and a processor to execute instructions in the memory to:

after receiving information on routes from all normal neighbor network devices of the first GR Restarter, perform route selection to determine first selected routes, and send information on the first selected routes to the at least one second GR Restarter,

after receiving information on routes from the at least one second GR Restarter, perform route selection to determine second selected routes, update a local Forwarding Information Base (FIB) at the first GR Restarter with information on the second selected routes, and send the information on the second selected routes to all neighbor network devices of the first GR Restarter;

wherein the first GR Restarter directly connects with the at least one second GR Restarter corresponding to the first GR Restarter.

15. The device according to claim 14 , wherein the network implements a Border Gateway Protocol (BGP), and wherein the first GR Restarter and each second GR Restarter are selected from the multiple GR Restarters as master GR Restarter and slave GR Restarter respectively, and the multiple GR Restarters form an aggregation.

16. The device according to claim 14 , wherein the processor further executes instructions to:

determine, after the first selected routes are determined, whether information on complete routes from all neighbor network devices of the first GR Restarter are received, and if yes,

update the local FIB with the information on the first selected routes; and

send the information on the first selected routes to all second GR Restarters corresponding to first GR Restarter.

17. The device according to claim 16 , wherein the processor further executes instructions to:

if information on complete routes from all the normal neighbor network devices of the first GR Restarter are received and if information on complete routes from at least two second GR Restarters corresponding to first GR Restarter are not received,

denote the first selected routes as incomplete routes, and

send the information on the first selected routes denoted as the incomplete routes to all second GR Restarters corresponding to first GR Restarter,

if the information on the complete routes from all the normal neighbor network devices of the first GR Restarter are received and information on a complete route from at most one second GR Restarter corresponding to first GR Restarter is not received,

denote the first selected routes as the complete routes, and

send the information on the first selected routes denoted as the complete routes to the at most one second GR Restarter,

denote the first selected routes as the incomplete routes, and

send the information on the first selected routes denoted as the incomplete routes to any other second GR Restarter corresponding to first GR Restarter,

if the information on complete routes from all normal neighbor network devices of the first GR Restarter are not received,

denote the first selected routes as the incomplete routes, and

send the information on the first selected routes denoted as the incomplete routes to all second GR Restarters corresponding to first GR Restarter.

18. The device according to claim 14 , wherein the processor further executes instructions to:

determine, after the first selected routes are determined, whether information on complete routes from all the neighbor network devices of the first GR Restarter are received, and if yes,

update the local FIB with the information on the first selected routes, and

add, if the first GR Restarter does not receive information on a complete route from a second GR Restarter, the second GR Restarter to a second GR Restarter aggregation; and

send the information on the first selected routes to all second GR Restarters in the second GR Restarter aggregation of the first GR Restarter.

19. The device according to claim 17 , wherein the processor further executes instructions to:

denote the first selected routes as the complete routes by generating a first EOR message which does not carry a Partial flag, and

denote the first selected routes as the incomplete routes by generating a second EOR message carrying the Partial flag.

20. A device capable of acting as a second Graceful Restart (GR) Restarter for a network with multiple GR Restarters that include the second GR Restarter and at least one first GR Restarter corresponding to the second GR Restarter, the device comprising:

a memory, and

a processor to execute instructions in the memory to:

after receiving information on routes from all neighbor network devices of the second GR Restarter, perform route selection to determine first selected routes,

if information on complete routes from all the neighbor network devices of the second GR Restarter are received, update a local FIB at the second GR Restarter with information on the first selected routes;

otherwise, send information on the first selected routes to the at least one first GR Restarter corresponding to second GR Restarter, perform route selection to determine second selected routes until information on complete routes from all neighbor network devices of the second GR Restarter are received, update the local FIB with information on the second selected routes, and send information on the second selected routes to all the neighbor network devices of the second GR Restarter;

wherein the second GR Restarter directly connects with the at least one first GR Restarters corresponding to the second GR Restarter.

21. The device according to claim 20 , wherein the network implements a Border Gateway Protocol (BGP), and wherein the second GR Restarter and each first GR Restarter are selected from the multiple GR Restarters as slave GR Restarter and master GR Restarter respectively, and the multiple GR Restarters form an aggregation.

22. The device according to claim 20 , wherein the processor further executes instructions to send the information on the first selected routes to all first GR Restarters corresponding to the second GR Restarter.

23. The device according to claim 22 , wherein the processor further executes instructions to:

if the second GR Restarter receives information on complete routes from all normal neighbor network devices of the second GR Restarter and if information on an incomplete route from one first GR Restarter corresponding to second GR Restarter is not received, or

if information on complete routes from all first GR Restarters are received but information on complete routes from at least two second GR Restarters are not received,

denote the first selected routes as incomplete routes, and

send information on the first selected routes denoted as the incomplete routes to all first GR Restarters corresponding to second GR Restarter and any other GR Restarter,

if the second GR Restarter receives the information on complete routes from all the normal neighbor network devices of the second GR Restarter and does not receive information on a complete route from at most one second GR Restarter corresponding to second GR Restarter,

denote the first selected routes as the complete routes, and

send the information on the first selected routes denoted as the complete routes to the at most one second GR Restarter,

denote the first selected routes as the incomplete routes, and

send the information on the first selected routes denoted as the incomplete routes to all first GR Restarters corresponding to second GR Restarter and any other GR Restarter.

24. The device according to claim 20 , wherein the processor further executes instructions to:

if information on a complete route from a first GR Restarter is not received,

add the first GR Restarter to a first GR Restarter aggregation; and

send the information on the first selected routes to all first GR Restarters in the first GR Restarter aggregation corresponding to second GR Restarter.

25. The device according to claim 23 , wherein the processor further executes instructions to denote the first selected routes as the complete routes by generating a first EOR message which does not carry the Partial flag, and denote the first selected routes as the incomplete routes by generating a second EOR message carrying the Partial flag.