Increasing multi-path size using hierarchical forwarding equivalent classes

Abstract

Techniques for operating a network device for increasing the logical multi-path size of a hardware forwarding table are provided. In some embodiments, the network device may determine that a number of data points in a first node is greater than a maximum node capacity; generate second nodes; update the first node to refer to the second nodes; distribute the data points among the second nodes; and program a hardware table with the updated first node and the second nodes.

What is claimed is: 
     
         1 . A method in a network device comprising:
 receiving data points;   when a number of the data points is less than a maximum node capacity:
 updating a first node with the data points; and 
 programming a hardware table in a packet processor with the updated first node; and 
   when a ceiling function of the number of the data points divided by the maximum node capacity is greater than a number of data points in the first node:
 generating second nodes, a number of the second nodes generated being the ceiling function of the number of the data points divided by the maximum node capacity; 
 updating the first node to refer to the second nodes; 
 distributing the data points among the second nodes; and 
 programming the hardware table with the updated first node and the second nodes.