Compression of route tables using key values

Patent metadata

Field	Value
Publication number	US-11706122-B2
Application number	US-202117195724-A
Country	US
Kind code	B2
Filing date	Mar 9, 2021
Priority date	Jan 5, 2021
Publication date	Jul 18, 2023
Grant date	Jul 18, 2023

Abstract

Described herein are systems, methods, and software to manage the compression of route tables for communication between networking elements. In one implementation, a network device identifies network keys for a route table by replacing attributes in the tables with values. The network device further generates a compressed route table using the route keys and associating each of the route keys with one or more additional attributes. The network device also generates a dictionary to associate each of the values for the route keys to a corresponding attribute of the attributes.

First claim

What is claimed:

1. A method of compressing a route table with a plurality of entries, wherein each entry in the plurality of entries comprises a plurality of attributes, the method comprising:
identifying one or more route keys to replace one or more attributes in each of the plurality of entries, wherein the plurality of attributes comprises at least a next hop IP address, wherein the one or more route keys each comprise one or more values that replace a corresponding one or more attributes of the plurality of attributes for one or more entries of the plurality of entries;
generating a compressed route table comprising at least the one or more route keys;
generating a dictionary to associate each value of the one or more values for the one or more route keys to a corresponding attribute from the route table that said value replaced; and
communicating the compressed route table and the dictionary to a peer network device.

2. The method of claim 1 , wherein generating the compressed route table comprises associating each of the one or more route keys with one or more second attributes from the plurality of entries not used for the one or more route keys.

3. The method of claim 1 further comprising:
compressing the compressed route table and the dictionary for communication to the peer network device.

4. The method of claim 1 , wherein each entry in the compressed route table comprises a route key of the one or more route keys.

5. The method of claim 4 , wherein at least one entry in the compressed route table represents two or more entries in the route table.

6. The method of claim 5 , wherein the at least one entry associates a route key of the one or more route keys with second attributes of the plurality of attributes associated with the two or more entries not replaced by the one or more values of the route key.

7. The method of claim 1 , wherein the plurality of attributes further comprise a route type, a routing port identifier, a routing component identifier, or a routing component type identifier.

8. The method of claim 1 , wherein each of the one or more values for the one or more route keys requires a lesser amount of storage than a corresponding attribute from the route table said value replaced.

9. A computing apparatus comprising:
a storage system;
a processing system operatively coupled to the storage system; and
program instructions stored on the storage system to compress a route table with a plurality of entries that each comprise a plurality of attributes that, when executed by the processing system, direct the computing apparatus to:
identify one or more route keys to replace one or more attributes in each of the plurality of entries, wherein the plurality of attributes comprises at least a next hop IP address, wherein the one or more route keys each comprise one or more values that replace a corresponding one or more attributes of the plurality of attributes for one or more entries of the plurality of entries;
generate a compressed route table comprising at least the one or more route keys; and
generate a dictionary to associate each value of the one or more values for the one or more route keys to a corresponding attribute from the route table that said value replaced.

10. The computing apparatus of claim 9 , wherein generating the compressed route table comprises associating each of the one or more route keys with one or more second attributes from the plurality of entries not used for the route keys.

11. The computing apparatus of claim 9 , wherein the program instructions further direct the computing apparatus to communicate the compressed route table and the dictionary to a peer network device.

12. The computing apparatus of claim 11 , wherein the program instructions further direct the computing apparatus to compress the compressed route table and the dictionary for communication to the peer network device.

13. The computing apparatus of claim 9 , wherein each entry in the compressed route table comprises a route key of the one or more route keys.

14. The computing apparatus of claim 13 , wherein at least one entry in the compressed route table represents two or more entries in the route table.

15. The computing apparatus of claim 14 , wherein the at least one entry associates a route key of the one or more route keys with second attributes of the plurality of attributes associated with the two or more entries not replaced by the one or more values of the route key.

16. The computing apparatus of claim 9 , wherein the plurality of attributes further comprise a route type, a routing port identifier, a routing component identifier, or a routing component type identifier.

17. The computing apparatus of claim 9 , wherein each of the one or more values for the one or more route keys requires a lesser amount of storage than a corresponding attribute from the route table said value replaced.

18. A system comprising:
a plurality of network devices;
a first network device in the plurality of network devices configured to:
identify one or more route keys for each entry of a plurality of entries in a route table, wherein each of the plurality of entries comprises a plurality of attributes, wherein the one or more route keys each comprise one or more values that replace a corresponding one or more attributes of the plurality of attributes for one or more entries of the plurality of entries;
generate a compressed route table by associating each of the one or more route keys with one or more second attributes from the route table not replaced by the one or more values;
generate a dictionary to associate each value of the one or more values for the one or more route keys to a corresponding attribute from the route table that said value replaced; and
communicate the compressed route table and the dictionary to a second network device in the plurality of network devices.

19. The system of claim 18 , wherein each of the one or more values for the one or more route keys requires a lesser amount of storage than a corresponding attribute from the route table said value replaced.

Assignees

• Vmware Inc

Inventors

• Singhal Ravi
• Malik Manish
• Wagle Ganesh Jayvant
• Batterywala Yusuf

Classifications

• H04L45/021 Primary

  Ensuring consistency of routing table updates, e.g. by using epoch numbers · CPC title

• H04L45/54 Primary

  Organization of routing tables · CPC title

• H04L45/7453

  using hashing · CPC title