Techniques for next-hop optimization
View Patent ↗Techniques for efficiently storing and using routing and associated next-hop information in a network device. The amount of next-hop information that is stored for routes in a routing table is reduced by reducing the amount of duplicate next-hop information that is stored by a network device.
1. A network device comprising:
a memory configurable to:
store a routing table comprising a plurality of routes; and
store next-hop information associated with the routing table, the next-hop information comprising a set of two or more next-hops, each next-hop associated with an attribute, each next-hop associated with a set of one or more pairs, each pair identifying a link and an address, the set of two or more next-hops comprising a first next-hop associated with a first route in the plurality of routes, the first next-hop stored in a first portion of the memory, the attribute associated with the first next-hop set to a first value; and
a processor communicatively coupled to the memory, the processor configurable to:
associate a second route in the plurality of routes with the first next-hop stored in the first portion of the memory; and
associate a third route in the plurality of routes with a second next-hop stored in a second portion of the memory,
wherein the set of one or more pairs associated with the second next-hop is identical to the set of one or more pairs associated with the first next-hop, and the attribute associated with the second next-hop is set to a second value that is different from the first value, and
wherein when the set of one or more pairs associated with the second next-hop changes, the set of one or more pairs associated with the first next-hop does not change due to the second value being different from the first value.
2. The network device of claim 1 wherein the processor is configurable to:
determine a first set of pairs for the second route; and
determine whether the set of two or more next-hops comprises a next-hop that comprises exactly the first set of pairs.
3. The network device of claim 2 wherein the processor is configurable to determine that the first next-hop comprises exactly the first set of pairs.
4. The network device of claim 1 wherein the number of next-hops in the set of two or more next-hops is less than the number of routes in the plurality of routes.
5. A computer-readable memory comprising a plurality of instructions for controlling a processor to store information used for forwarding data packets received by a network device, the plurality of instructions comprising:
instructions that cause the processor to store a routing table comprising a plurality of routes;
instructions that cause the processor to store next-hop information associated with the routing table, the next-hop information comprising a set of two or more next-hops, each next-hop associated with an attribute, each next-hop associated with a set of one or more pairs, each pair identifying a link and an address, the set of two or more next-hops comprising a first next-hop associated with a first route in the plurality of routes, the first next-hop stored in a first memory portion, the attribute associated with the first next-hop set to a first value;
instructions that cause the processor to associate a second route in the plurality of routes with the first next-hop stored in the first memory portion; and
instructions that cause the processor to associate a third route in the plurality of routes with a second next-hop stored in a second memory portion,
wherein the set of one or more pairs associated with the second next-hop is identical to the set of one or more pairs associated with the first next-hop, and the attribute associated with the second next-hop is set to a second value that is different from the first value, and
wherein when the set of one or more pairs associated with the second next-hop changes, the set of one or more pairs associated with the first next-hop does not change due to the second value being different from the first value.
6. The computer-readable memory of claim 5 wherein the plurality of instructions comprises:
instructions that cause the processor to determine a first set of pairs for the second route; and
instructions that cause the processor to determine whether the set of two or more next-hops comprises a next-hop that comprises exactly the first set of pairs.
7. The computer-readable memory of claim 6 wherein the instructions that cause the processor to determine whether the set of two or more next-hops comprises a next-hop that comprises exactly the first set of pairs comprises instructions that cause the processor to determine that the first next-hop comprises exactly the first set of pairs.
8. The computer-readable memory of claim 5 wherein the number of next-hops in the set of two or more next-hops is less than the number of routes in the plurality of routes.
9. A method comprising:
storing, in a network device, a routing table comprising a plurality of routes;
storing, in the network device, next-hop information associated with the routing table, the next-hop information comprising a set of two or more next-hops, each next-hop associated with an attribute, each next-hop associated with a set of one or more pairs, each pair identifying a link and an address, the set of two or more next-hops comprising a first next-hop associated with a first route in the plurality of routes, the first next-hop stored in a first memory portion of the network device, the attribute associated with the first next-hop set to a first value;
associating, by the network device, a second route in the plurality of routes with the first next-hop stored in the first memory portion of the network device; and
associating, by the network device, a third route in the plurality of routes with a second next-hop stored in a second memory portion of the network device,
wherein the set of one or more pairs associated with the second next-hop is identical to the set of one or more pairs associated with the first next-hop, and the attribute associated with the second next-hop is set to a second value that is different from the first value, and
wherein when the set of one or more pairs associated with the second next-hop changes, the set of one or more pairs associated with the first next-hop does not change due to the second value being different from the first value.