Method for optimizing IP route table size through IP route aggregation
A subset of route entries having the same next hop is identified in a route table. The subset of entries falls within a range of prefixes. Gaps in the subset of route entries that prevent the subset from being contiguous are identified. The gaps in the subset are filled with route entries to make the subset contiguous. All of the route entries in the contiguous subset of route entries have the same next hop, thus the contiguous subset can be aggregated into a single route entry in a forwarding table. For each gap-filling entry added to the route table, an additional route entry having forwarding priority over the gap-filling entry is added to the forwarding table.
1. A method for reducing the size of a route table having a plurality of route entries, the method comprising:
identifying a subset of route entries having a same next hop in a route table, the route entries within a range of prefixes;
identifying a missing route for which no route entry exists within the subset of route entries, wherein the missing route prevents the subset of route entries within the range of prefixes from being contiguous in the route table;
adding the missing route as a route entry to the route table to create a contiguous subset of route entries within the range of prefixes;
adding a new route entry to the route table, the new route entry having a prefix corresponding to and longer than a prefix of the route entry of the missing route, wherein the new route entry has forwarding priority over the route entry for the missing route; and
aggregating, by a processor, the contiguous subset of route entries into a single aggregated route entry in the route table.
2. The method of claim 1 , further comprising:
receiving an indication of a route entry deleted from the contiguous subset;
maintaining an equivalent route entry in the route table corresponding to the deleted route entry;
adding an additional route entry in the route table corresponding to the deleted route entry, the additional route entry having a prefix corresponding to and longer than a prefix of the equivalent route entry in the route table corresponding to the deleted route entry, wherein the additional route entry has forwarding priority over the equivalent route entry for the route entry deleted from the contiguous subset.
3. The method of claim 1 , wherein each additional route corresponds to a different next hop than the next hop of the route entries in the contiguous subset of route entries.
4. The method of claim 2 , wherein the additional route entry corresponding to the deleted route corresponds to a different next hop in the route table than the next hop of the equivalent route entry in the route table.
5. The method of claim 1 , further comprising aggregating aggregated route entries into a single route entry to further compress the route table.
6. The method of claim 1 , wherein identifying the subset of route entries having the same next hop in a route table further comprises identifying a subset of equal cost multi-path (ECMP) route entries in the route table having a same set of ECMP paths.
7. A non-transitory computer-readable storage medium having content stored thereon to provide instructions that, when executed by a processor in an electronic device, result in the electronic device performing a method for reducing the size of a route table having a plurality of route entries, wherein the method comprises:
identifying a subset of route entries having a same next hop in a route table, the route entries within a range of prefixes;
identifying a missing route for which no route entry exists within the subset of route entries, wherein the missing route prevents the subset of route entries within the range of prefixes from being contiguous in the route table;
adding the missing route as a route entry to the route table to create a contiguous subset of route entries within the range of prefixes;
adding a new route entry to the route table, the new route entry having a prefix corresponding to and longer than a prefix of the route entry of the missing route, wherein the new route entry has forwarding priority over the route entry for the missing route; and
aggregating the contiguous subset of route entries into a single aggregated route entry in the route table.
8. The non-transitory computer-readable storage medium article of manufacture of claim 7 , wherein the method further comprises:
receiving an indication of a route entry deleted from the contiguous subset;
maintaining an equivalent route entry in the route table corresponding to the deleted route entry;
adding an additional route entry in the route table corresponding to the deleted route entry, the additional route entry having a prefix corresponding to and longer than a prefix of the equivalent route entry in the route table corresponding to the deleted route entry, wherein the additional route entry has forwarding priority over the equivalent route entry for the route entry deleted from the contiguous subset.
9. The non-transitory computer-readable storage medium of claim 7 , wherein each additional route entry corresponds to a different next hop than the next hop of the route entries in the contiguous subset of route entries.
10. The non-transitory computer-readable storage medium of claim 8 , wherein the additional route entry corresponding to the deleted route entry corresponds to a different next hop than the next hop of the equivalent route entry in the route table.
11. The non-transitory computer-readable storage medium of claim 7 , wherein the method further comprises:
aggregating aggregated route entries into a single route entry to further compress the route table.