Efficient updates of weighted cost multipath (WCMP) groups
First Claim
Patent Images
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 Assignments
0 Petitions
Accused Products
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.
-
Citations
20 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. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
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 S1; 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 SR, storage space Si released by reducing the given routing scheme is equivalent to a difference between the storage space S and the reduced storage space SR of the given routing scheme, and for each of the identified one or more routing schemes, Si is less than or equal to the required storage space S1; 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. - View Dependent Claims (8, 9, 10, 11, 12)
-
-
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. - View Dependent Claims (14, 15, 16, 17, 18, 19, 20)
-
Specification