Increasing multi-path size using hierarchical forwarding equivalent classes
AssigneeArista Networks, Inc.
InventorsTrevor Siemens, Mayukh Saubhasik, Vahab Akbarzadeh
Life of this patent
Estimating the term…
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.
Claims20
A method for increasing a multi-path size using hierarchical forwarding equivalent classes (HFECs) in a network device comprising:
- receiving a plurality of data points representing a set of next-hops for a multi-path route;
- wherein when a number of the plurality of data points is less than a maximum node capacity:
- updating a first node with the plurality of data points;
- and
- programming a hardware table in a packet processor with the updated first node;
- and
- wherein when a ceiling function of the number of the plurality of data points divided by the maximum node capacity is greater than the number of plurality of data points in the first node:
- generating at least one second node, a number of the at least one second node generated being the ceiling function of the number of the plurality of data points divided by the maximum node capacity;
- updating the first node to refer to the at least one second node in a hierarchy model;
- distributing the data points among the at least one second node;
- and
- programming the hardware table with the updated first node and the at least one second node,
- wherein at least one of the first node and the second nodes are forwarding equivalence classes.
A network device comprising:
- a processor;
- and
- a memory communicatively coupled to the processor, the processor storing instructions executable by the memory to perform a method for increasing a multi-path size using hierarchical forwarding equivalent classes (HFECs), the method comprising:
- receiving a number of data points representing a set of next-hops for a multi-path route;
- determining that the number of data points in a first node is greater than a maximum node capacity;
- generating at least one second node;
- updating the first node to refer to the at least one second node in a hierarchy model;
- distributing the data points among the at least one second node;
- and
- programming a hardware forwarding table with the updated first node and the at least one second node,
- wherein at least one of the first node and the second nodes are forwarding equivalence classes.
A non-transitory computer-readable storage medium having embodied thereon a program, the program being executable by a processor to perform a method for increasing a multi-path size using hierarchical forwarding equivalent classes (HFECs), the method comprising:
- receiving a multi-path route having a plurality of next hops for a plurality of paths;
- determining if the number of next hops in the plurality of next hops is greater than a limit;
- when the number of next hops is greater than the limit, calculating a number of sub-groups;
- distributing the plurality of next hops among the sub-groups;
- generating forwarding equivalence classes (FECs) for the sub-groups, the FECs including the next hops of the sub-group;
- and
- programming a hardware forwarding table with the generated FECs.
Dependencies are inferred from the claim text.