Dynamic route profile storage in a hardware trie routing table

• US 10,404,596 B2
• Filed: 10/03/2017
• Issued: 09/03/2019
• Est. Priority Date: 10/03/2017
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Ghosh, Ankan, Bacthu, Nataraj, Chevuru, Apurup Reddy, Agrawal, Laxmi Kant, Narayanan, Swaminathan
• Primary Examiner(s): Siddiqui, Kashif
• Application Number:
  US15/723,713
• Publication Number:
  US 20190104067A1
• Time in Patent Office: 700 Days
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0638 Organizing or formatting or addressing of data
• CPC Class Codes: G06F 3/0673 Single storage device
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/7453 using hashing

Abstract

The present disclosure involves systems and methods for managing a trie routing table for a networking device of a communication or computer network. In one implementation, the networking device may utilize a dynamic algorithm for associating hashing functions with pivot tiles of the routing table to improve hash utilization and avoid hash collisions. Further, route prefixes may be relocated from pivot tiles in an attempt to free the tiles for reallocation to other prefix base width or may be relocated to other possible pivot tiles or to a general storage space when a hash collision is detected. This provides for even distribution of pivots within tiles which have base widths in range of a pivot route. The above implementations may occur together or separately to improve the operation of the networking device and provide faster route lookup.

Claims

1. A method for managing a routing table of a networking device, the method comprising:

maintaining a plurality of pivot tiles in memory for storing pivot entries each comprising a plurality of received route prefixes of a routing table, each of the plurality of pivot tiles associated with a hash function and a prefix base width;

selecting a first of the plurality of pivot tiles for grooming; and

grooming the first of the plurality of pivot tiles by;

relocating at least a first pivot entry from the first of the plurality of pivot tiles to a Ternary Content-Addressable Memory (TCAM);

moving at least a second pivot entry from the first of the plurality of pivot tiles to a second of the plurality of pivot tiles; and

returning the first of the plurality of pivot tiles to a shared pool of pivot tiles for reallocation when the plurality of received route prefixes of the routing table stored in the first of the plurality of pivot tiles are removed.

2. The method of claim 1, further comprising:

dynamically associating a first hash function with the first of the plurality of pivot tiles and a second hash function with the second of the plurality of pivot tiles, the first hash function different than the second hash function.

3. The method of claim 2, wherein the first hash function provides a storage location within the first of the plurality of pivot tiles based at least on a portion of a prefix to be stored in the first of the plurality of pivot tiles.

4. The method of claim 2, further comprising:

selecting the first hash function for the first of the plurality of pivot tiles based at least on a distribution of each hash function for the plurality of pivot tiles.

5. The method of claim 4, wherein selecting of the first hash function for the first of the plurality of pivot tiles is further based on a utilization factor for the distribution of each hash function for the plurality of pivot tiles.

6. The method of claim 2, wherein moving the second pivot entry from the first of the plurality of pivot tiles to the second of the plurality of pivot tiles comprises calculating a location for the second pivot entry in the second of the plurality of the pivot tiles based on the second hash function associated with the second of the plurality of the pivot tiles.

7. The method of claim 6, further comprising:

detecting a hash collision at the location for the second pivot entry in the second of the plurality of the pivot tiles between the second pivot entry and an occupying pivot entry of the second of the plurality of the pivot tiles.

8. The method of claim 7, further comprising:

copying the occupying pivot entry of the second of the plurality of the pivot tiles to the TCAM; and

relocating the second pivot entry to the location for the second pivot entry in the second of the plurality of the pivot tiles.

9. The method of claim 7, further comprising:

copying the occupying pivot entry of the second of the plurality of the pivot tiles to a third of the plurality of the pivot tiles; and

relocating the second pivot entry to the location for the second pivot entry in the second of the plurality of the pivot tiles.

10. The method of claim 1, wherein moving the second pivot entry from the first of the plurality of pivot tiles to the second of the plurality of pivot tiles is based at least on a base width of the second pivot entry and the second of the plurality of pivot tiles.

11. A networking device comprising:

at least one communication port for receiving route prefixes of a network for inclusion in a trie routing table;

a processing device; and

a computer-readable medium connected to the processing device configured to store a plurality of pivot tiles in memory for maintaining pivot entries each comprising a plurality of received route prefixes and associated with a hash function and a prefix base-width and instructions that, when executed by the processing device, causes the device to perform operations comprising;

selecting a first of the plurality of pivot tiles for grooming, and

grooming the first of the plurality of pivot tiles by;

relocating at least a first pivot entry from the first of the plurality of pivot tiles to a Ternary Content-Addressable Memory (TCAM);

moving at least a second pivot entry from the first of the plurality of pivot tiles to a second of the plurality of pivot tiles; and

returning the first of the plurality of pivot tiles to a shared pool of pivot tiles for reallocation when the plurality of received route prefixes of the trie routing table stored in the first of the plurality of pivot tiles are removed.

12. The device of claim 11, wherein the instructions are further executed to:

dynamically associate a first hash function with the first of the plurality of pivot tiles and a second hash function with the second of the plurality of pivot tiles, the first hash function different than the second hash function.

13. The device of claim 12, wherein the first hash function provides a storage location within the first of the plurality of pivot tiles based at least on a portion of a prefix to be stored in the first of the plurality of pivot tiles.

14. The device of claim 12, wherein the instructions are further executed to:

select the first hash function for the first of the plurality of pivot tiles based at least on a distribution of each hash function for the plurality of pivot tiles.

15. The device of claim 14, wherein selecting of the first hash function for the first of the plurality of pivot tiles is further based on a utilization factor for the distribution of each hash function for the plurality of pivot tiles.

16. The device of claim 12, wherein moving the second pivot entry from the first of the plurality of pivot tiles to the second of the plurality of pivot tiles comprises calculating a location for the second pivot entry in the second of the plurality of the pivot tiles based on the second hash function associated with the second of the plurality of the pivot tiles.

17. The device of claim 16, wherein the instructions are further executed to:

detect a hash collision at the location for the second pivot entry in the second of the plurality of the pivot tiles between the second pivot entry and an occupying pivot entry of the second of the plurality of the pivot tiles.

18. The device of claim 17, wherein the instructions are further executed to:

copy the occupying pivot entry of the second of the plurality of the pivot tiles to the TCAM; and

relocate the second pivot entry to the location for the second pivot entry in the second of the plurality of the pivot tiles.

19. The device of claim 17, wherein the instructions are further executed to:

copy the occupying pivot entry of the second of the plurality of the pivot tiles to a third of the plurality of the pivot tiles; and

relocate the second pivot entry to the location for the second pivot entry in the second of the plurality of the pivot tiles.

20. The device of claim 11, wherein moving the second pivot entry from the first of the plurality of pivot tiles to the second of the plurality of pivot tiles is based at least on a base width of the second pivot entry and the second of the plurality of pivot tiles.