Efficient updates of weighted cost multipath (WCMP) groups

• US 9,479,437 B1
• Filed: 12/20/2013
• Issued: 10/25/2016
• Est. Priority Date: 12/20/2013
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Zhou, Junlan, Vahdat, Amin
• Primary Examiner(s): Chu, Wutchung
• Application Number:
  US14/137,044
• Time in Patent Office: 1,040 Days
• Field of Search: 370/235, 370/229, 370/255, 709/241
• US Class Current: 1/1
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 47/122 by diverting traffic away from congested entities

Abstract

Exemplary embodiments provide changes to routing schemes, i.e. WCMP groups or WCMP sets, installed in a network traffic distribution table, e.g. multipath table. WCMP groups of a multipath table are updated to accommodate a new WCMP group. This can be achieved by reducing the size of the existing WCMP groups on the multipath table. The goal is to reduce the existing WCMP groups just enough to make room for the new WCMP group. An objective is to minimize the number of existing WCMP groups to be reduced before a new WCMP group can be installed in the multipath table.

Claims

1. A computer-implemented method comprising:

providing a network traffic distribution table (the “

table”

) storing a plurality of routing schemes for a forwarding device, each routing scheme occupying a corresponding number of entries in the table;

providing at least one additional routing scheme to be added to the table;

identifying one or more routing schemes of the plurality of routing schemes for reduction;

reducing a minimum number of the identified one or more routing schemes by, for each routing scheme to be reduced, reducing the corresponding number of entries in the table occupied by the respective routing scheme, such that the reducing releases enough storage space at the table for adding the at least one additional routing scheme while retaining, for each reduced routing scheme, at least one corresponding entry in the table; and

causing the forwarding device to forward network traffic using the at least one additional routing scheme by updating the network traffic distribution table of the forwarding device with the at least one additional routing scheme.

2. The method of claim 1, wherein each routing scheme defines how network traffic is to be distributed among multiple ports of the forwarding device in the network.

3. The method of claim 1, further comprising:

when more than one routing schemes are identified, determining oversubscription created by reducing each of the identified routing schemes;

comparing the oversubscription of each of the identified routing schemes to a threshold value; and

determining a subset of the identified routing schemes based on the comparing, wherein the subset of the identified routing schemes is equivalent to the minimum number of the identified one or more of the plurality of routing schemes.

4. The method of claim 3, wherein the subset of the identified routing schemes have lowest oversubscriptions among the identified routing schemes.

5. The method of claim 3, further comprising:

when the subset of the identified routing schemes includes more than one routing scheme, determining a reference count associated with each routing scheme of the subset, wherein the reference count identified for each routing scheme is equal to number of routes in the network using the routing scheme for forwarding the network traffic; and

determining one or more of the subset of the identified routing schemes with lowest reference counts, wherein the one or more of the subset of the identified routing schemes is equivalent to the minimum number of the identified one or more of the plurality of routing schemes.

6. The method of claim 1, wherein the routing schemes are weighted cost multipath (WCMP) groups.

7. A computer-implemented method comprising:

providing a network traffic distribution table (the “

table”

) storing routing schemes for a forwarding device, wherein each routing scheme occupies a corresponding number of entries using a storage space S in the table;

providing an additional routing scheme to be added to the table, wherein the additional routing scheme requires a storage space S₁;

identifying one or more of the routing schemes for reducing, wherein;

reducing a given routing scheme reduces the storage space S occupied by the given routing scheme to a reduced storage space S_R,

storage space S_i released by reducing the given routing scheme is equivalent to a difference between the storage space S and the reduced storage space S_R of the given routing scheme, and

for each of the identified one or more routing schemes, S_i is less than or equal to the required storage space S₁;

reducing a minimum number of the identified one or more routing schemes by, for each routing scheme to be reduced, reducing the corresponding number of entries in the table occupied by the respective routing scheme, such that the reducing releases enough storage space at the table for adding the at least one additional routing scheme while retaining, for each reduced routing scheme, at least one corresponding entry in the table; and

causing the forwarding device to forward network traffic-using the at least one additional routing scheme by updating the network traffic distribution table of the forwarding device with the at least one additional routing scheme.

8. The method of claim 7, wherein each routing scheme defines how network traffic is to be distributed among multiple ports of the forwarding device in the network.

9. The method of claim 7, further comprising:

when more than one routing schemes are identified, determining a magnitude of oversubscription created by reducing each of the identified routing schemes;

comparing the magnitude of oversubscription of each of the identified routing schemes to a threshold value; and

determining a subset of the identified routing schemes based on the comparing, wherein the subset of the identified routing schemes is equivalent to the minimum number of the identified one or more of the plurality of routing schemes.

10. The method of claim 9, wherein the subset of the identified routing schemes have lowest magnitudes of oversubscription among the identified routing schemes.

11. The method of claim 9, further comprising:

when the subset of the identified routing schemes includes more than one routing scheme, determine a reference count associated with each routing scheme of the subset, wherein the reference count is equal to number of routes using the routing scheme for forwarding the network traffic; and

determining one or more of the subset of the identified routing schemes with lowest reference counts, wherein the one or more of the subset of the identified routing schemes is equivalent to the minimum number of the identified one or more of the plurality of routing schemes.

12. The method of claim 7, wherein the routing schemes are weighted cost multipath (WCMP) groups.

13. A non-transitory medium storing instructions, that when executed by a processor, cause the processor to:

provide a network traffic distribution table (the “

table”

) storing routing schemes for a forwarding device, each routing scheme occupying a corresponding number of entries in the table;

provide an additional routing scheme to be added to the table;

identify a portion of the routing schemes for reducing, wherein reducing the portion of routing schemes releases enough storage space at the table for adding the additional routing scheme;

if the portion of the routing schemes includes a single routing scheme, reduce the single routing scheme while retaining at least one corresponding entry in the table for the single routing scheme;

if the portion of the routing scheme includes more than one routing schemes;

apply an elimination test to eliminate one or more routing schemes from the portion of the routing schemes, and

reduce at least one remaining routing scheme in the portion of the routing schemes while retaining, for each reduced routing scheme, at least one corresponding entry in the table; and

cause the forwarding device to forward network traffic using the additional routing scheme by updating the network traffic distribution table of the forwarding device with the additional routing scheme.

14. The medium of claim 13, wherein each routing scheme defines how network traffic is to be distributed among multiple paths through the network.

15. The medium of claim 13, where the elimination test comprises:

determining a magnitude of oversubscription created by reducing each of the portion of the routing schemes;

comparing the magnitude of oversubscription of each of the portion of the routing schemes to a threshold value; and

determining one or more routing schemes among the portion of the routing schemes based on the comparing.

16. The medium of claim 15, wherein the one or more determined routing schemes have lowest magnitudes of oversubscription among the magnitudes of oversubscription of the portion of the routing schemes.

17. The medium of claim 15, wherein more than one routing scheme is determined based on the comparing, the medium further storing one or more instructions that, when executed by the processor, cause the processor to:

determine a reference count associated with each of the determined routing schemes, wherein the reference count is equal to number of routes using each routing scheme for forwarding the network traffic; and

determine the remaining one or more routing schemes among the determined routing schemes such that the remaining one or more routing schemes have lowest reference counts.

18. The medium of claim 13, where the elimination test comprises:

determining a magnitude of oversubscription created by reducing each of the portion of the routing schemes;

comparing the magnitude of oversubscription of each of the portion of the routing schemes to a threshold value;

determining two or more routing schemes among the portion of the routing schemes based on the comparing, wherein the two or more routing schemes have lowest magnitudes of oversubscription among the magnitudes of oversubscription of the portion of the routing schemes;

determining a reference count associated with each of the two or more routing schemes, wherein the reference count is equal to number of routes using each routing scheme for forwarding the network traffic; and

determining the remaining one or more routing schemes among the two or more routing schemes such that the remaining one or more routing schemes have lowest reference counts.

19. The medium of claim 13, wherein the routing schemes are weighted cost multipath (WCMP) groups.

20. The medium of claim 13, wherein the additional routing scheme is added to the table and the network traffic is rerouted using the additional routing scheme before removing an old routing scheme from the table.