Patent Description:
A forwarding information base (FIB) may be a data structure that includes forwarding data, such as information identifying a destination, information identifying a next hop in a route to the destination, and/or the like. A network device may perform a lookup in the FIB to identify forwarding data and use the forwarding data to forward a packet to a destination. <CIT> relates to fast reroute for common network routes. <CIT> relates to programming a network device to perform routing of data packets between and/or within networks. However, neither of these documents discloses at least: processing forwarding data, associated with a multi-level hybrid hierarchy forwarding information base of the network device, to generate transformed group next hop entries and a first set of transformed forwarding next hop entries; processing, based on default forwarding classes, the transformed group next hop entries and the first set of transformed forwarding next hop entries, associated with the default forwarding classes, to generate a second set of transformed forwarding next hop entries; processing the transformed group next hop entries and the first set of transformed forwarding next hop entries, associated with all classes of traffic, to generate a third set of transformed forwarding next hop entries; grouping the first set of transformed forwarding next hop entries, the second set of transformed forwarding next hop entries, and the third set of transformed forwarding next hop entries, based on the transformed group next hop entries, to generate a final set of transformed forwarding next hop entries; and transforming the final set of transformed forwarding next hop entries into a particular format.

According to some implementations, a method may include receiving, by a network device, forwarding data associated with a multi-level hybrid hierarchy forwarding information base of the network device; processing, by the network device, the forwarding data to generate transformed group next hop entries and a first set of transformed forwarding next hop entries; processing, by the network device, the transformed group next hop entries and the first set of transformed forwarding next hop entries, associated with default forwarding classes, to generate a second set of transformed forwarding next hop entries; processing, by the network device, the transformed group next hop entries and the first set of transformed forwarding next hop entries, associated with all classes of traffic, to generate a third set of transformed forwarding next hop entries; grouping, by the network device, the first set of transformed forwarding next hop entries, the second set of transformed forwarding next hop entries, and the third set of transformed forwarding next hop entries, based on the transformed group next hop entries, to generate a final set of transformed forwarding next hop entries; transforming, by the network device, the final set of transformed forwarding next hop entries into a particular format; and storing, by the network device, the final set of transformed forwarding next hop entries, in the particular format, in the forwarding information base.

According to some implementations, a network device may include one or more memories and one or more processors. In some implementations, the one or more processors are communicatively coupled to the one or more memories. The one or more processors may be configured to: receive forwarding data associated with a multi-level hybrid hierarchy forwarding information base of the network device; process the forwarding data to generate transformed group next hop entries and a first set of transformed forwarding next hop entries; process the transformed group next hop entries and the first set of transformed forwarding next hop entries, associated with default forwarding classes, to generate a second set of transformed forwarding next hop entries; process the transformed group next hop entries and the first set of transformed forwarding next hop entries, associated with all classes of traffic, to generate a third set of transformed forwarding next hop entries; group the first set of transformed forwarding next hop entries, the second set of transformed forwarding next hop entries, and the third set of transformed forwarding next hop entries, based on the transformed group next hop entries, to generate a final set of transformed forwarding next hop entries; transform the final set of transformed forwarding next hop entries into a particular format; receive traffic associated with a network; and forward the traffic based on the final set of transformed forwarding next hop entries in the particular format.

According to some implementations, a computer-readable medium may store or convey one or more instructions. The one or more instructions, when executed by one or more processors of a network device, may cause the one or more processors to: receive forwarding data associated with a multi-level hybrid hierarchy forwarding information base of the network device; process the forwarding data to generate transformed group next hop entries and a first set of transformed forwarding next hop entries; process the transformed group next hop entries and the first set of transformed forwarding next hop entries, associated with default forwarding classes, to generate a second set of transformed forwarding next hop entries; process the transformed group next hop entries and the first set of transformed forwarding next hop entries, associated with all classes of traffic, to generate a third set of transformed forwarding next hop entries; group the first set of transformed forwarding next hop entries, the second set of transformed forwarding next hop entries, and the third set of transformed forwarding next hop entries, based on the transformed group next hop entries, to generate a final set of transformed forwarding next hop entries; transform the final set of transformed forwarding next hop entries into a particular format; store the final set of transformed forwarding next hop entries, in the particular format, in the forwarding information base; receive traffic associated with a network; and forward the traffic based on the final set of transformed forwarding next hop entries in the particular format.

A FIB on a network device may store forwarding data associated with a large quantity (e.g., on the order of millions) of destinations. The FIB may be a hierarchical FIB that includes multiple levels. Incoming traffic received by the network device may be classified into different forwarding classes. The incoming traffic may be routed to different outbound interfaces at different levels in the hierarchy. The network device may distribute the traffic (e.g., make load sharing decisions) at different levels in the hierarchy.

In some hierarchical FIBs, such as multi-level hybrid hierarchical FIBs, there may be one or more sub-hierarchies. Certain sub-hierarchies may be configured to process certain forwarding classes of the incoming traffic (e.g., different sub-hierarchies may be configured to process different forwarding classes), certain sub-hierarchies may be configured without a forwarding class configuration, and/or the like. As a result, the network device may be unable to determine traffic distribution across outbound interfaces of the network device for a route, since certain sub-hierarchies of the FIB may not identify traffic distribution for all forwarding classes for traffic to be forwarded via the route. This may waste computing resources (e.g., processing resources, memory resources, and/or the like), networking resources, and/or the like associated with determining traffic distribution across outbound interfaces of the network device when using such a multi-level hybrid hierarchical FIB.

Some implementations described herein enable a network device to transform a multi-level hybrid hierarchical FIB format. For example, the network device may process forwarding data associated with a multi-level hybrid hierarchy FIB of the network device to generate transformed group next hop entries and/or a set of transformed forwarding next hop entries. The network device may process the transformed group next hop entries and/or the set of transformed forwarding next hop entries to generate one or more addition sets of transformed forwarding next hop entries (e.g., that include one or more missing transformed next hop entries from the set of transformed forwarding next hop entries, one or more new transformed next hop entries of the set of transformed forwarding next hop entries, and/or the like). The sets of transformed forwarding next hop entries may be grouped together based on the transformed group next hop entries (e.g., based on a forwarding class associated with the transformed forwarding next hop entries) to form a final set of transformed forwarding next hop entries. The network device may transform the final set of transformed forwarding next hop entries into a particular format (e.g., that is configured to represent all traffic distribution for all forwarding classes).

The network device may receive traffic and may forward the traffic based on the final set of transformed forwarding next hop entries in the particular format. As a result, the network device may be enabled to determine traffic distribution across outbound interfaces for all forwarding classes of traffic associated with the network. This may conserve computing resources and/or network resources that would have otherwise been used determining traffic distribution for a given destination and a specific forwarding class using a multi-level hybrid hierarchical FIB format (e.g., that may not include a full traffic distribution for all forwarding classes for a destination).

<FIG> are diagrams of one or more example(s) <NUM> associated with determining traffic distribution in a hybrid hierarchical forwarding information base (FIB). As shown in <FIG>, example <NUM> includes one or more endpoint devices and one or more network device devices communicating via a network.

As shown in <FIG>, a network device of the one or more network devices may include an FIB for storing forwarding data for a plurality of destinations, such as an endpoint device, another network device, and/or the like. The FIB may be a data structure that stores forwarding data associated with one or more destinations in the network, in another network, and/or the like. The forwarding data associated with a destination may include information identifying an address of the destination (e. , an Internet protocol (IP) address, a port address, and/or the like), information identifying a next hop in a route to the destination, information identifying an interface associated with the destination (e. , a media access control (MAC) identifier), and/or the like. A destination may be an endpoint device, another network device, and/or the like.

The network device may receive, process, and/or transmit packets. The packets may be data plane packets (e.g., packets that travel through the network device, and are not originated or terminated at the network device), control plane packets (e.g., packets that are originated in the control plane of the network device (e.g., generated by the network device) or terminated in the control plane of the network device (e.g., the network device is the destination of the packet)), and/or the like. The network device may receive a packet, perform a lookup in the FIB on the network device to identify forwarding data associated with the packet (e. , information identifying a destination of the packet, information identifying a next hop in a route to the destination, and/or the like), and transmit the packet to the next hop based on the forwarding data.

The network device may populate and maintain the forwarding data in the FIB based on various techniques. For example, the network device may learn routes in the network and/or updates to the routes in the network based on one or more routing protocols, such as a routing information protocol (RIP), an open shortest path first (OSPF) protocol, a border gateway protocol (BGP), an interior gateway routing protocol (IGRP), an enhanced IGRP (EIGRP), a distance-vector routing protocol, an intermediate system to intermediate system (IS-IS) protocol, and/or the like, and may store information identifying the routes and/or the updates to the routes, as forwarding data, in the FIB. In some implementations, the FIB may be populated with static forwarding data, which may be forwarding data configured and/or maintained by a user such as a network administrator.

The network device and/or the FIB may include one or more classifier tables for determining a forwarding class of a packet received by the network device. The forwarding class may be a group and/or an identifier assigned to an incoming packet based on one or more of the parameters of the incoming packet (e.g., packet code-point values and/or the like). The forwarding class may enable the network device to group packets into different categories, which may then be used to define per-hop behaviour (PHB), assign the packets to output queues for transmission, and/or the like. The forwarding classes may enable the network device to group packets for transmission and to assign packets to one or more output queues. The forwarding classes may identify a priority of a packet, identify a delivery protocol (e.g., best-effort delivery and/or the like) for the packet, and/or the like. The network device may determine a forwarding class for a packet by identifying an entry in a header of the packet (e.g., a differentiated services code point (DSCP) entry, a type of service (ToS) entry, and/or the like). The network device may identify (e.g., using a lookup operation) an entry in the classifier table, corresponding to the entry in the header of the packet, that identifies a forwarding class (e.g., the classifier table may associate the entry in the header of the packet to a forwarding class). The network device and/or the FIB may include classifier tables associated with certain incoming interfaces, certain destinations, and/or the like. Upon receiving a packet, the network device may determine a forwarding class associated with the packet, as described above. The network device may generate forwarding class information (e.g., indicating the forwarding class) and may include the forwarding class information within the packet (e.g., within a header of the packet).

Incoming packets to the network device may be split into multiple paths of a route at different levels of a hierarchy of the FIB. For example, the network device may determine, based on forwarding data stored in the FIB, to segregate outgoing paths based on a forwarding class of the packet. In some implementations, certain hierarchies of the FIB may be configured for processing a subset of all forwarding classes, or certain hierarchies of the FIB may be configured without a forwarding class-based forwarding protocol. For example, the FIB may have a hybrid hierarchical FIB (e.g., including a hybrid class-based forwarding hierarchy) format.

As shown in <FIG>, an example hybrid hierarchical FIB format may include forwarding data associated with a route to a destination. For example, the FIB may store forwarding data associated with a destination prefix (e.g., an IP route, such as <NUM>. <NUM>/<NUM>) associated with a route (e.g., route R1). The forwarding data may identify a top level next hop associated with the route prefix (e.g., unilist1) that is a first next hop associated with the route. The forwarding data may identify one or more types of forwarding next hops (e.g., to other network devices or network entities) for the route. The one or more types of forwarding next hops may include aggregate next hops, indirect next hops, indexed next hops, forwarding next hops, and/or the like.

An aggregate next hop may be an equal-cost multi-path (ECMP) next hop. An aggregate next hop may identify one or more next hops (e.g., next hops after the aggregate next hop). Paths to the one or more next hops from the aggregate next hop may be associated with one or more parameters (e.g., weight, balance, and/or the like). A weight parameter may identify a priority of a path (e.g., a lowest weight value may identify a primary path, a higher weight value may identify a backup or inactive path, and/or the like). A balance parameter may identify a load balance to be applied for traffic among the paths with the same weight (e.g., a balance value of <NUM> associated with a path may indicate that <NUM>% of traffic from the aggregate next hop should be transmitted via the path). A sum of balance parameters for all paths from an aggregate next hop may be equal to the total balance of traffic entering the aggregate next hop (e.g., if a balance of traffic entering the aggregate next hop is <NUM>, the sum of balance parameters for all paths from the aggregate next hop may be <NUM>).

An indirect next hop may identify indirect next hop forwarding data (e.g., from the indirect next hop to an aggregate next hop, an indexed next hop, and/or the like). The indirect next hop may be common to a plurality of routes. An indexed next hop may identify one or more paths from the indexed next hop to a forwarding next hop. A path of the one or more paths may be associated with a forwarding class. For example, the forwarding data may identify <NUM> paths from the indexed next hop to <NUM> forwarding next hops. A first path may be associated with a first forwarding class, a second path may be associated with a second forwarding class, and a third path may be associated with the remaining forwarding classes (e.g., all other forwarding classes except the first and second forwarding classes). A forwarding next hop may be associated with an outbound interface (e.g., associated with a destination for traffic) of the network device. For example, the forwarding next hop may be associated with a unicast transmission (e.g., a one-to-one transmission) to a destination. A forwarding next hop may be associated with an outgoing computed weight. The outgoing computed weight may indicate a balance of traffic associated with the forwarding next hop and/or the corresponding outbound interface (e.g., may indicate a percentage or ratio of traffic that is to be distributed to the forwarding next hop).

For example, as shown in <FIG>, the example multi-level hybrid hierarchical FIB format may include forwarding data for a primary path for route R1 identifying the top level next hop (e.g., unilist1). The forwarding data may identify three indirect next hops after the top level next hop (e.g., indirect1, indirect2, and indirect3). The forwarding data may identify that a path from unilist1 to indirect1 has a balance of <NUM> (e.g., indicating that <NUM>% of traffic from unilist1 is associated with the path), a path from unilist1 to indirect2 has a balance of <NUM> (e.g., indicating that <NUM>% of traffic from unilist1 is associated with the path), and a path from unilist1 to indirect3 has a balance of <NUM> (e.g., indicating that <NUM>% of traffic from unilist1 is associated with the path).

The forwarding data may identify that traffic from indirect1 should be forwarded to unilist2. As unilist2 may be an aggregate next hop, unilist2 may split traffic to different paths from unilist2 to forwarding next hops (e.g., unicast1 and unicast2) equally (e.g., a balance of <NUM> for each path). In some implementations, a split of traffic between unicast1 and unicast2 may not be equal (e.g., where a different balance is indicated by the forwarding data). As the balance of traffic entering unilist2 is <NUM>, a path from unilist2 to unicast1 may have an outgoing computed weight of <NUM> (e.g., <NUM>% of <NUM>) and a path from unilist2 to unicast2 may have an outgoing computed weight of <NUM> (e.g., totaling <NUM> between both paths). The paths from unilist2 may not conform to class-based forwarding. That is, the paths from unilist2 may not be associated with any specific forwarding class (e.g., the paths may be for all forwarding classes).

The forwarding data may identify that traffic from indirect2 should be sent to indexed!. The forwarding data may identify that paths from indexed1 to forwarding next hops (e.g., unicast3, unicast4, and unicast5) are associated with specific forwarding classes. For example, a path from indexed1 to unicast3 may be associated with a first forwarding class (e.g., FC <NUM>), a path from indexed1 to unicast4 may be associated with a second forwarding class (e.g., FC <NUM>), and a path from indexed1 to unicast5 may be associated with a default forwarding class (e.g., all forwarding classes not specifically identified by indexed1). The paths from indexed1 may be associated with a same balance as the balance of traffic entering indexed1 (e.g., each of the three paths from indexed1 may be associated with outgoing computed weights of <NUM>).

The forwarding data may identify that traffic from indirect3 should be sent to indexed3. The forwarding data may identify that paths from indexed3 to forwarding next hops (e.g., unicast6, unicast7, and unicast8) are associated with specific forwarding classes. For example, a path from indexed2 to unicast6 may be associated with the first forwarding class (e.g., FC <NUM>), a path from indexed2 to unicast7 may be associated with a third forwarding class (e.g., FC <NUM>), and a path from indexed1 to unicast5 may be associated with a default forwarding class (e.g., all forwarding classes not specifically identified by indexed2). The paths from indexed2 may be associated with a same balance as the balance of traffic entering indexed2 (e.g., each of the three paths from indexed2 may be associated with outgoing computed weights of <NUM>).

In some implementations, the forwarding data may identify one or more additional paths that are not shown in <FIG>. The additional paths may be associated with backup or inactive paths (e.g., the forwarding data may identify that a weight of the additional paths is greater than <NUM>). The example multi-level hybrid hierarchical FIB format may be hybrid in that the FIB includes class-based forwarding (e.g., from the indexed next hops) and non-class-based forwarding (e.g., from the aggregate next hops, such as unilist2). The multi-level hybrid hierarchical FIB format may include <NUM> levels (e.g., a first level of unilist1; a second level of indirect1, indirect2, and indirect3; a third level of unilist2, indexed <NUM>, and indexed2; and a fourth level of unicast1 - unicast8). In some implementations the multi-level hybrid hierarchical FIB format may include more than or less than <NUM> levels.

As shown in <FIG>, and by reference number <NUM>, the network device may receive forwarding data associated with a multi-level hybrid hierarchy FIB (e.g., the multi-level hybrid hierarchy FIB described above with respect to <FIG>). As shown by reference number <NUM>, the network device may process the forwarding data to identify a top level next hop entry, create a conditional transformed group next hop (CTGNH) entry, and generate transformed group next hop entries (TGs) and transformed forwarding next hop entries (Ts). As described above, the forwarding data for route R1 may identify that the top level next hop entry is unilist1. The conditional transformed group next hop entry may be based on the identified top level next hop entry (e.g., the conditional transformed group next hop entry may be the identified top level next hop entry).

The transformed group next hop entries may identify one or more transformed forwarding next hop entries. A transformed group next hop entry may include one or more transformed forwarding next hop entries that are associated with a same forwarding class. For example, a first transformed group next hop entry may include one or more transformed forwarding next hop entries that are associated with a first forwarding class (e.g., FC <NUM>), a second transformed group next hop entry may include one or more transformed forwarding next hop entries that are associated with a second forwarding class (e.g., FC <NUM>), and so forth.

The transformed forwarding next hop entries may identify an outgoing computed weight, a forwarding class, an outbound interface, and/or other forwarding information (e.g., one or more next hops from the top level next hop to the forwarding next hop). For example, a transformed forwarding next hop entry may be a path associated with route R1.

The network device may process the forwarding data based on a type of the forwarding next hop identified in the forwarding data. For example, if the type of the forwarding next hop is an indirect next hop, the network device may process the forwarding data to identify a next entry in the forwarding data after the indirect next hop. If the type of the forwarding next hop is an indexed next hop, the network device may determine one or more child next hop(s) (e.g., next hops after the indexed next hop). The network device may determine a forwarding class associated with a path from the indexed next hop to the child next hop(s). The network device may determine one or more forwarding classes associated with a default forwarding class of the indexed next hop (e.g., the network device may determine one or more forwarding classes that the indexed next hop is not explicitly configured to handle). If the type of the forwarding next hop is a forwarding next hop, the network device may create a transformed forwarding next hop associated with the forwarding next hop.

For example, the network device may process the forwarding data associated with a first type of next hop (e.g., aggregate next hops) to generate a first subset of transformed forwarding next hop entries. The network device may process the forwarding data associated with a second type of next hop (e.g., indirect next hops) to generate a second subset of transformed forwarding next hop entries. The network device may process the forwarding data associated with a third type of next hop (e.g., indexed next hops) to generate a third subset of transformed forwarding next hop entries. The network device may process the forwarding data associated with a fourth type of next hop (e.g., forwarding next hops) to generate a fourth subset of transformed forwarding next hop entries. The network device may combine the first subset of transformed forwarding next hop entries, the second subset of transformed forwarding next hop entries, the third subset of transformed forwarding next hop entries, and the fourth subset of transformed forwarding next hop entries to generate the first set of transformed forwarding next hop entries. The first set of transformed forwarding next hop entries may identify each next hop associated with a path to an outbound interface (e.g., to a forwarding next hop or a unicast, as shown in <FIG>). A transformed forwarding next hop entry may be associated with a corresponding outbound interface of the network device.

As shown in <FIG>, a first set of transformed forwarding next hop entries may include T4 (e.g., associated with unicast1), T8 (e.g., associated with unicast2), T9 (e.g., associated with unicast3), T10 (e.g., associated with unicast4), T12 (e.g., associated with unicast5), T13 (e.g., associated with unicast6), T14 (e.g., associated with unicast7), and T16 (e.g., associated with unicast8). A transformed forwarding next hop entry may identify an associated path. For example, T4 may identify a path from unilist1 to indirect1 to unilist2 to unicast1, T10 may identify a path from unilist1 to indirect2 to indexed1 to unicast4, and so forth. A transformed forwarding next hop entry may identify an associated outgoing computed weight. For example, T4 may identify an outgoing computed weight of <NUM>, T10 may identify an outgoing computed weight of <NUM>, T14 may identify an outgoing computed weight of <NUM>, and so forth. A transformed forwarding next hop entry may identify an associated forwarding class. For example, T4 may identify that all forwarding classes are associated with T4, T9 may identify an associated forwarding class of FC <NUM>, T10 may identify an associated forwarding class of FC <NUM>, T14 may identify an associated forwarding class of FC <NUM>, and so forth.

The transformed group next hop entries may include a first transformed group next hop entry associated with the first forwarding class (e.g., FC <NUM>), a second transformed group next hop entry associated with the second forwarding class (e.g., FC <NUM>), a third transformed group next hop entry associated with the third forwarding class (e.g., FC <NUM>), a fourth transformed group next hop entry associated with the default forwarding class (e.g., FC D), and/or the like. The first transformed group next hop entry may include one or more transformed forwarding next hop entries associated with the first forwarding class (e.g., T9 and T13). The second transformed group next hop entry may include one or more transformed forwarding next hop entries associated with the second forwarding class (e.g., T10). The third transformed group next hop entry may include one or more transformed forwarding next hop entries associated with the third forwarding class (e.g., T14). The fourth transformed group next hop entry may include one or more transformed forwarding next hop entries associated with the default forwarding class (e.g., T12 and T16). T4 and T8 may not be included in a transformed group next hop entry as T4 and T8 may not be associated with a specific forwarding class.

As shown in <FIG>, and by reference number <NUM>, the network device may process the transformed group next hop entries and the transformed forwarding next hop entries associated with default forwarding classes to generate missing transformed forwarding next hop entries. For example, the network device may determine the forwarding classes associated with the default forwarding classes. The network device may compare transformed forwarding next hop entries associated with an indexed next hop entry to determine missing forwarding classes. For example, the network device may identify T9 and T10 associated with indexed1. The network device may determine that T9 is associated with the first forwarding class (e.g., FC <NUM>) and T10 is associated with the second forwarding class (e.g., FC <NUM>). The network device may determine that a transformed forwarding next hop entry associated with indexed1 and the third forwarding class (e.g., FC <NUM>) is missing. As a result, the network device may generate a transformed forwarding next hop entry associated with indexed1 and the third forwarding class that has the same forwarding information as the transformed forwarding next hop entry associated with indexed1 and the default forwarding class (e.g., T12). Similarly, the network device may determine that a transformed forwarding next hop entry associated with indexed2 and the second forwarding class (e.g., FC <NUM>) is missing. As a result, the network device may generate a transformed forwarding next hop entry associated with indexed2 and the second forwarding class that has the same forwarding information as the transformed forwarding next hop entry associated with indexed2 and the default forwarding class (e.g., T16).

As shown in <FIG>, the network device may determine a second set of transformed forwarding next hop entries. The second set of transformed forwarding next hop entries may include the missing transformed forwarding next hop entries (e.g., T11 and T15). The network device may update the transformed group next hop entries based on the second set of transformed forwarding next hop entries. For example, the network device may add T11 to the third transformed group next hop entry (e.g., associated with the third forwarding class) and may add T15 to the second transformed group next hop entry (e.g., associated with the second forwarding class).

As shown in <FIG>, and by reference number <NUM>, the network device may process the transformed group next hop entries and the transformed forwarding next hop entries associated with all classes of traffic to generate new transformed forwarding next hop entries. For example, the network device may process the transformed forwarding next hop entries associated with aggregate next hops (e.g., unilist2 and/or the like). The network device may generate new transformed forwarding next hop entries for each forwarding class that have the same forwarding information as the transformed forwarding next hop entries associated with all classes of traffic. For example, the network device may generate new transformed forwarding next hop entries by transforming T4 into four new transformed forwarding next hop entries that have the same forwarding information as T4, but are associated with a specific forwarding class. Similarly, the network device may generate new transformed forwarding next hop entries by transforming T8 into four new transformed forwarding next hop entries. The quantity of new transformed forwarding next hop entries may be based on the quantity of forwarding classes.

As shown in <FIG>, the network device may determine a third set of transformed forwarding next hop entries. The third set of transformed forwarding next hop entries may include the new transformed forwarding next hop entries. For example, the new transformed forwarding next hop entries may include T1 (e.g., associated with unicast1 and the first forwarding class), T2 (e.g., associated with unicast1 and the second forwarding class), T3 (e.g., associated with unicast1 and the second forwarding class), T4 (e.g., associated with unicast1 and the default forwarding class), T5 (e.g., associated with unicast2 and the first forwarding class), T6 (e.g., associated with unicast2 and the second forwarding class), T7 (e.g., associated with unicast2 and the third forwarding class), and T8 (e.g., associated with unicast2 and the default forwarding class). The network device may create a final set of transformed forwarding next hop entries that includes all transformed forwarding next hop entries from the first set of transformed forwarding next hop entries, the second set of transformed forwarding next hop entries, and the third set of transformed forwarding next hop entries (e.g., T1 - T16).

The network device may update the transformed group next hop entries based on the third set of transformed forwarding next hop entries. For example, the network device may add T1 and T5 to the first transformed group next hop entry (e.g., associated with the first forwarding class), T2 and T6 to the second transformed group next hop entry (e.g., associated with the second forwarding class), T3 and T7 to the third transformed group next hop entry (e.g., associated with the third forwarding class), and T4 and T8 to the fourth transformed group next hop entry (e.g., associated with the default forwarding class).

As a result, the final set of transformed forwarding next hop entries may include a first subset of transformed forwarding next hop entries associated with the first forwarding class (e.g., FC <NUM>) and the first entry of the transformed group next hop entries (e.g., the first transformed group next hop entry), a second subset of transformed forwarding next hop entries associated with the second forwarding class (e.g., FC <NUM>) and the second entry of the transformed group next hop entries (e.g., the second transformed group next hop entry), a third subset of transformed forwarding next hop entries associated with the third forwarding class (e.g., FC <NUM>) and the third entry of the transformed group next hop entries (e.g., the third transformed group next hop entry), and a fourth subset of transformed forwarding next hop entries associated with the fourth forwarding class (e.g., the default forwarding class) and a fourth entry of the transformed group next hop entries (e.g., the fourth transformed group next hop entry).

As shown in <FIG>, and by reference number <NUM>, the network device may group the transformed forwarding next hop entries (e.g., the first set of transformed forwarding next hop entries), the missing transformed forwarding next hop entries (e.g., the second set of transformed forwarding next hop entries), and the new transformed forwarding next hop entries (e.g., the third set of transformed forwarding next hop entries) based on the transformed group next hop entries. For example, the network device may group the transformed forwarding next hop entries included in the final set of transformed forwarding next hop entries based on the transformed group next hop entries (e.g., based on a forwarding class of each transformed group next hop entry).

As shown in <FIG>, the network device may transform the multi-level hybrid hierarchy FIB format of <FIG> (e.g., the four level (or more) multi-level hybrid hierarchy FIB format) into a three level hierarchy FIB format. The three levels may include a conditional transformed group next hop level (e.g., indicating the conditional transformed group next hop entries), a transformed group next hop level (e.g., indicating the transformed group next hop entries), and a transformed forwarding next hop level (e.g., indicating the transformed forwarding next hop entries). The transformed forwarding next hop entries may be grouped by an associated transformed group next hop entry and/or an associated forwarding class. For example, the three level hierarchy FIB format may indicate a path from the conditional transformed group next hop to the first transformed group next hop (e.g., TG1) and paths to each of the transformed forwarding next hop entries associated with the first transformed group next hop (e.g., T1, T5, T9, and T13). The three level hierarchy FIB format may indicate an outgoing computed weight associated with paths from the first transformed group next hop to an associated transformed forwarding next hop. For example, a path from the first transformed group next hop to transformed forwarding next hop T1 may have an outgoing computed weight of <NUM>, a path from the first transformed group next hop to transformed forwarding next hop T5 may have an outgoing computed weight of <NUM>, a path from the first transformed group next hop to transformed forwarding next hop T9 may have an outgoing computed weight of <NUM>, and a path from the first transformed group next hop to transformed forwarding next hop T13 may have an outgoing computed weight of <NUM>. A sum of the outgoing computed weights of paths from the first transformed group next hop may be <NUM> (e.g., indicating that the paths from the first transformed group next hop include all potential paths for traffic associated with the first forwarding class (e.g., FC <NUM>).

As a result, the network device may arrange the three level hierarchy FIB format such that traffic distribution over the network to corresponding outbound interfaces may be determined for all forwarding classes. For example, for the second forwarding class (e.g., FC <NUM>), the three level hierarchy FIB format may indicate that <NUM>% (e.g., indicated by an outgoing computed weight of <NUM>) of traffic associated with the second forwarding class may be distributed via transformed forwarding next hop T2, <NUM>% (e.g., indicated by an outgoing computed weight of <NUM>) of traffic associated with the second forwarding class may be distributed via transformed forwarding next hop T6, <NUM>% (e.g., indicated by an outgoing computed weight of <NUM>) of traffic associated with the second forwarding class may be distributed via transformed forwarding next hop T10, and <NUM>% (e.g., indicated by an outgoing computed weight of <NUM>) of traffic associated with the second forwarding class may be distributed via transformed forwarding next hop T15. Similarly, incoming traffic associated with the third forwarding class (e.g., FC <NUM>) may be distributed across outbound interfaces corresponding to transformed forwarding next hop T3, transformed forwarding next hop T7, transformed forwarding next hop T11, and transformed forwarding next hop T14 in the ratio of <NUM>, <NUM>, <NUM>, and <NUM>, respectively. The network device may determine traffic distribution for other forwarding classes in a similar manner.

As shown in <FIG>, and by reference number <NUM>, the network device may transform the grouped transformed forwarding next hop entries into a particular format. The particular format may be a three level hierarchy address forwarding table format, an openconfig address forwarding table format (OC-AFT), and/or the like. The particular format may include condition identifiers that define ingress classification criteria to apply to a packet received by the network device. For example, the network device may include a condition identifier with a packet (e.g., in a header of the packet) when the packet is received by the network device. The network device may determine the condition identifiers based on the forwarding data, information received from another network device, information contained within a packet received by the network device, information stored within the FIB, and/or the like. The condition identifiers may be used by the network device and/or other network devices to determine a distribution (e.g., a path) for a packet.

As shown in <FIG>, the network device may associate paths from the conditional transformed group next hop to one or more (or all) of the transformed group next hop with one or more condition identifiers. For example, condition identifiers <NUM>, <NUM>, and <NUM> may be associated with the first transformed group next hop (e.g., TG1), condition identifiers <NUM>, <NUM>, and <NUM> may be associated with the second transformed group next hop (e.g., TG2), condition identifiers <NUM>, <NUM>, and <NUM> may be associated with the third transformed group next hop (e.g., TG3), and condition identifier <NUM> may be associated with the fourth transformed group next hop (e.g., TG4).

The network device may perform the processing of the forwarding data as described above based on a configuration (e.g., a setting and/or the like) of the network device. For example, the configuration may indicate that the network device is to transform forwarding data associated with a multi-level hybrid hierarchy FIB format. In some implementations, the network device may selectively perform the processing of the forwarding data based on an indication in the forwarding data, based on a configuration, based on a user input (e.g., from an administrator of the network), and/or the like.

The network device may store the transformed forwarding next hop entries in the particular format (e.g., as shown in <FIG>) in the FIB of the network device. The network device may receive traffic (e.g., a packet) associated with the network. The network device may forward the traffic based on the transformed forwarding next hop entries in the particular format. For example, the network device may determine a forwarding class and/or a condition identifier associated with the traffic. The network device may include the forwarding class and/or the condition identifier with the traffic (e.g., in a header of a packet). The network device may forward the traffic according to the distribution indicated by the transformed forwarding next hop entries in the particular format. The network device may expose the transformed forwarding next hop entries in the particular format to one or more other devices (e.g., one or more other network devices and/or the like) for use consumption purposes (e.g., for monitoring via telemetry).

As a result, the network device may be enabled to determine traffic distribution across outbound interfaces for all forwarding classes of traffic associated with the network. The network device may be enabled to trace traffic distribution for a given destination and a specific forwarding class of the traffic. This may conserve computing resources and/or network resources that would have otherwise been used determining traffic distribution for a given destination and a specific forwarding class using a multi-level hybrid hierarchical FIB format (e.g., that may not include a full traffic distribution for all forwarding classes for a destination).

In practice, there may be additional devices, fewer devices, different devices, or differently arranged than those shown in <FIG>.

<FIG> is a diagram of an example environment <NUM> in which systems and/or methods described herein may be implemented. As shown in <FIG>, environment <NUM> may include one or more endpoint devices <NUM>, a group of network devices <NUM> (shown as network device <NUM>-<NUM> through network device <NUM>-N), and a network <NUM>. Devices of environment <NUM> may interconnect via wired connections, wireless connections, or a combination of wired and wireless connections.

Endpoint device <NUM> includes one or more devices capable of receiving, generating, storing, processing, and/or providing information, such as information described herein. For example, endpoint device <NUM> may include a mobile phone (e.g., a smart phone, a radiotelephone, and/or the like), a laptop computer, a tablet computer, a desktop computer, a handheld computer, a gaming device, a wearable communication device (e.g., a smart watch, a pair of smart glasses, a heart rate monitor, a fitness tracker, smart clothing, smart jewelry, a head mounted display, and/or the like), a network device, or a similar type of device. In some implementations, endpoint device <NUM> may receive network traffic from and/or may provide network traffic to other endpoint devices <NUM> via network <NUM> (e.g., by routing packets using network devices <NUM> as intermediaries).

Network device <NUM> includes one or more devices capable of receiving, processing, storing, routing, and/or providing traffic (e.g., a packet, other information or metadata, and/or the like) in a manner described herein. For example, network device <NUM> may include a router, such as a label switching router (LSR), a label edge router (LER), an ingress router, an egress router, a provider router (e.g., a provider edge router, a provider core router, and/or the like), a virtual router, and/or the like. Additionally, or alternatively, network device <NUM> may include a gateway, a switch, a firewall, a hub, a bridge, a reverse proxy, a server (e.g., a proxy server, a cloud server, a data center server, and/or the like), a load balancer, and/or a similar device. In some implementations, network device <NUM> may be a physical device implemented within a housing, such as a chassis. In some implementations, network device <NUM> may be a virtual device implemented by one or more computer devices of a cloud computing environment or a data center. In some implementations, a group of network devices <NUM> may be a group of data center nodes that are used to route traffic flow through network <NUM>.

Network <NUM> includes one or more wired and/or wireless networks. For example, network <NUM> may include a packet switched network, a cellular network (e.g., a fifth generation (<NUM>) network, a fourth generation (<NUM>) network, such as a long-term evolution (LTE) network, a third generation (<NUM>) network, a code division multiple access (CDMA) network, a public land mobile network (PLMN), a local area network (LAN), a wide area network (WAN), a metropolitan area network (MAN), a telephone network (e.g., the Public Switched Telephone Network (PSTN)), a private network, an ad hoc network, an intranet, the Internet, a fiber optic-based network, a cloud computing network, or the like, and/or a combination of these or other types of networks.

<FIG> is a diagram of example components of a device <NUM>. Device <NUM> may correspond to endpoint device <NUM>, network device <NUM>, and/or the like. In some implementations, endpoint device <NUM>, network device <NUM>, and/or the like may include one or more devices <NUM> and/or one or more components of device <NUM>. As shown in <FIG>, device <NUM> may include one or more input components <NUM>-<NUM> through <NUM>-B (B ≥ <NUM>) (hereinafter referred to collectively as input components <NUM>, and individually as input component <NUM>), a switching component <NUM>, one or more output components <NUM>-<NUM> through <NUM>-C (C ≥ <NUM>) (hereinafter referred to collectively as output components <NUM>, and individually as output component <NUM>), and a controller <NUM>.

Controller <NUM> may perform one or more processes described herein. Controller <NUM> may perform these processes in response to executing software instructions provided from a computer-readable medium. A computer readable medium may include storage media and/or transmission media. A computer-readable storage medium is referred to herein as a non-transitory memory device. A memory device includes memory space within a single physical storage device or memory space spread across multiple physical storage devices. A transmission medium conveys instructions to the processor (or a storage medium) from another location, and as such may occur between computer systems and/or between components of one computer system.

<FIG> is a diagram of example components of a device <NUM>. Device <NUM> may correspond to endpoint device <NUM>, network device <NUM>, and/or the like. In some implementations, endpoint device <NUM>, network device <NUM>, and/or the like may include one or more devices <NUM> and/or one or more components of device <NUM>. As shown in <FIG>, device <NUM> may include a bus <NUM>, a processor <NUM>, a memory <NUM>, a storage component <NUM>, an input component <NUM>, an output component <NUM>, and a communication interface <NUM>.

Bus <NUM> includes a component that permits communication among the components of device <NUM>. Processor <NUM> is implemented in hardware, firmware, or a combination of hardware and software. Processor <NUM> is a central processing unit (CPU), a graphics processing unit (GPU), an accelerated processing unit (APU), a microprocessor, a microcontroller, a digital signal processor (DSP), a field-programmable gate array (FPGA), an application-specific integrated circuit (ASIC), or another type of processing component. In some implementations, processor <NUM> includes one or more processors capable of being programmed to perform a function. Memory <NUM> includes a random-access memory (RAM), a read only memory (ROM), and/or another type of dynamic or static storage device (e.g., a flash memory, a magnetic memory, and/or an optical memory) that stores information and/or instructions for use by processor <NUM>.

For example, storage component <NUM> may include a hard disk (e.g., a magnetic disk, an optical disk, a magneto-optic disk, and/or a solid state disk), a compact disc (CD), a digital versatile disc (DVD), a floppy disk, a cartridge, a magnetic tape, and/or another type of non-transitory computer-readable storage medium, along with a corresponding drive.

Output component <NUM> includes a component that provides output information from device <NUM> (e.g., a display, a speaker, and/or one or more LEDs).

Communication interface <NUM> includes a transceiver-like component (e.g., a transceiver and/or a separate receiver and transmitter) that enables device <NUM> to communicate with other devices, such as via a wired connection, a wireless connection, or a combination of wired and wireless connections. Communication interface <NUM> may permit device <NUM> to receive information from another device and/or provide information to another device. For example, communication interface <NUM> may include an Ethernet interface, an optical interface, a coaxial interface, an infrared interface, an RF interface, a universal serial bus (USB) interface, a wireless local area interface, a cellular network interface, and/or the like.

Device <NUM> may perform one or more processes described herein. Device <NUM> may perform these processes based on processor <NUM> executing software instructions provided from a computer-readable medium. A computer readable medium may include storage media and/or transmission media. A computer-readable storage medium is referred to herein as a non-transitory memory device. A memory device includes memory space within a single physical storage device or memory space spread across multiple physical storage devices. A transmission medium conveys instructions to the processor (or a storage medium) from another location, and as such may occur between computer systems and/or between components of one computer system.

<FIG> is a flow chart of an example process <NUM> associated with transforming a multi-level hybrid hierarchical forwarding information base (FIB) format. In some implementations, one or more process blocks of <FIG> may be performed by a network device (e.g., network device <NUM>). In some implementations, one or more process blocks of <FIG> may be performed by another device or a group of devices separate from or including the network device, such as an endpoint device (e.g., endpoint device <NUM>), and/or the like. Additionally, or alternatively, one or more process blocks of <FIG> may be performed by one or more components of a device <NUM> (e.g., input component <NUM>, switching component <NUM>, output component <NUM>, controller <NUM>, and/or the like), a device <NUM> (e.g., processor <NUM>, memory <NUM>, storage component <NUM>, input component <NUM>, output component <NUM>, communication interface <NUM>, and/or the like), and/or the like.

As shown in <FIG>, process <NUM> may include receiving forwarding data associated with a multi-level hybrid hierarchy forwarding information base of the network device (block <NUM>). For example, the network device may receive forwarding data associated with a multi-level hybrid hierarchy forwarding information base of the network device, as described above.

As further shown in <FIG>, process <NUM> may include processing the forwarding data to generate transformed group next hop entries and a first set of transformed forwarding next hop entries (block <NUM>). For example, the network device may process the forwarding data to generate transformed group next hop entries and a first set of transformed forwarding next hop entries, as described above.

As further shown in <FIG>, process <NUM> may include processing the transformed group next hop entries and the first set of transformed forwarding next hop entries, associated with default forwarding classes, to generate a second set of transformed forwarding next hop entries (block <NUM>). For example, the network device may process the transformed group next hop entries and the first set of transformed forwarding next hop entries, associated with default forwarding classes, to generate a second set of transformed forwarding next hop entries, as described above.

As further shown in <FIG>, process <NUM> may include processing the transformed group next hop entries and the first set of transformed forwarding next hop entries, associated with all classes of traffic, to generate a third set of transformed forwarding next hop entries (block <NUM>). For example, the network device may process the transformed group next hop entries and the first set of transformed forwarding next hop entries, associated with all classes of traffic, to generate a third set of transformed forwarding next hop entries, as described above.

As further shown in <FIG>, process <NUM> may include grouping the first set of transformed forwarding next hop entries, the second set of transformed forwarding next hop entries, and the third set of transformed forwarding next hop entries, based on the transformed group next hop entries, to generate a final set of transformed forwarding next hop entries (block <NUM>). For example, the network device may group the first set of transformed forwarding next hop entries, the second set of transformed forwarding next hop entries, and the third set of transformed forwarding next hop entries, based on the transformed group next hop entries, to generate a final set of transformed forwarding next hop entries, as described above.

As further shown in <FIG>, process <NUM> may include transforming the final set of transformed forwarding next hop entries into a particular format (block <NUM>). For example, the network device may transform the final set of transformed forwarding next hop entries into a particular format, as described above.

As further shown in <FIG>, process <NUM> may include storing the final set of transformed forwarding next hop entries, in the particular format, in the forwarding information base (block <NUM>). For example, the network device may store the final set of transformed forwarding next hop entries, in the particular format, in the forwarding information base, as described above.

In a first implementation, process <NUM> includes processing the forwarding data to identify a top level next hop entry in the forwarding data and to create a conditional transformed group next hop entry.

In a second implementation, alone or in combination with the first implementation, process <NUM> includes receiving traffic associated with a network, and forwarding the traffic based on the final set of transformed forwarding next hop entries in the particular format.

In a third implementation, alone or in combination with one or more of the first and second implementations, the particular format includes a three-level hierarchy address forwarding table format.

In a fourth implementation, alone or in combination with one or more of the first through third implementations, processing the forwarding data to generate the transformed group next hop entries and the first set of transformed forwarding next hop entries comprises processing the forwarding data associated with a first type of next hop to generate a first subset of transformed forwarding next hop entries; processing the forwarding data associated with a second type of next hop to generate a second subset of transformed forwarding next hop entries; processing the forwarding data associated with a third type of next hop to generate a third subset of transformed forwarding next hop entries; processing the forwarding data associated with a fourth type of next hop to generate a fourth subset of transformed forwarding next hop entries; and combining the first subset of transformed forwarding next hop entries, the second subset of transformed forwarding next hop entries, the third subset of transformed forwarding next hop entries, and the fourth subset of transformed forwarding next hop entries to generate the first set of transformed forwarding next hop entries.

In a fifth implementation, alone or in combination with one or more of the first through fourth implementations, the first type of next hop corresponds to an aggregate next hop, the second type of next hop corresponds to an indirect next hop, the third type of next hop corresponds to an indexed next hop, and the fourth type of next hop corresponds to a forwarding next hop.

In a sixth implementation, alone or in combination with one or more of the first through fifth implementations, the final set of transformed forwarding next hop entries includes next hop entries that are each associated with a corresponding outbound interface of the network device.

<FIG> is a flow chart of an example process <NUM> associated with transforming a multi-level hybrid hierarchical FIB format. In some implementations, one or more process blocks of <FIG> may be performed by a network device (e.g., network device <NUM>). In some implementations, one or more process blocks of <FIG> may be performed by another device or a group of devices separate from or including the network device, such as an endpoint device (e.g., endpoint device <NUM>), and/or the like. Additionally, or alternatively, one or more process blocks of <FIG> may be performed by one or more components of a device <NUM> (e.g., input component <NUM>, switching component <NUM>, output component <NUM>, controller <NUM>, and/or the like), a device <NUM> (e.g., processor <NUM>, memory <NUM>, storage component <NUM>, input component <NUM>, output component <NUM>, communication interface <NUM>, and/or the like), and/or the like.

As further shown in <FIG>, process <NUM> may include receiving traffic associated with a network (block <NUM>). For example, the network device may receive traffic associated with a network, as described above.

As further shown in <FIG>, process <NUM> may include forwarding the traffic based on the final set of transformed forwarding next hop entries in the particular format (block <NUM>). For example, the network device may forward the traffic based on the final set of transformed forwarding next hop entries in the particular format, as described above.

In a first implementation, the second set of transformed forwarding next hop entries includes transformed forwarding next hop entries that are missing from the first set of transformed forwarding next hop entries.

In a second implementation, alone or in combination with the first implementation, the third set of transformed forwarding next hop entries includes new transformed forwarding next hop entries associated with forwarding classes included in the first set of transformed forwarding next hop entries.

In a third implementation, alone or in combination with one or more of the first and second implementations, the final set of transformed forwarding next hop entries includes: a first subset of transformed forwarding next hop entries associated with a first forwarding class and a first entry of the transformed group next hop entries, a second subset of transformed forwarding next hop entries associated with a second forwarding class and a second entry of the transformed group next hop entries, a third subset of transformed forwarding next hop entries associated with a third forwarding class and a third entry of the transformed group next hop entries, and a fourth subset of transformed forwarding next hop entries associated with a fourth forwarding class and a fourth entry of the transformed group next hop entries.

In a fourth implementation, alone or in combination with one or more of the first through third implementations, the particular format includes openconfig address forwarding table format.

In a fifth implementation, alone or in combination with one or more of the first through fourth implementations, the final set of transformed forwarding next hop entries in the particular format includes condition identifiers that define ingress classification criteria to apply to a packet.

In a sixth implementation, alone or in combination with one or more of the first through fifth implementations, the multi-level hybrid hierarchy forwarding information base includes four or more levels.

<FIG> is a flow chart of an example process <NUM> associated with transforming a multi-level hybrid hierarchical FIB format. In some implementations, one or more process blocks of <FIG> may be performed by a network device (e.g., network device <NUM>). In some implementations, one or more process blocks of <FIG> may be performed by another device or a group of devices separate from or including the network device, such as an endpoint device (e.g., endpoint device <NUM>) and/or the like. Additionally, or alternatively, one or more process blocks of <FIG> may be performed by one or more components of a device <NUM> (e.g., input component <NUM>, switching component <NUM>, output component <NUM>, controller <NUM>, and/or the like), a device <NUM> (e.g., processor <NUM>, memory <NUM>, storage component <NUM>, input component <NUM>, output component <NUM>, communication interface <NUM>, and/or the like), and/or the like.

In a second implementation, alone or in combination with the first implementation, processing the forwarding data to generate the transformed group next hop entries and the first set of transformed forwarding next hop entries includes processing the forwarding data associated with a first type of next hop to generate a first subset of transformed forwarding next hop entries; processing the forwarding data associated with a second type of next hop to generate a second subset of transformed forwarding next hop entries; processing the forwarding data associated with a third type of next hop to generate a third subset of transformed forwarding next hop entries; processing the forwarding data associated with a fourth type of next hop to generate a fourth subset of transformed forwarding next hop entries; and combining the first subset of transformed forwarding next hop entries, the second subset of transformed forwarding next hop entries, the third subset of transformed forwarding next hop entries, and the fourth subset of transformed forwarding next hop entries to generate the first set of transformed forwarding next hop entries.

In a third implementation, alone or in combination with one or more of the first and second implementations, the final set of transformed forwarding next hop entries includes next hop entries that are each associated with a corresponding outbound interface of the network device.

In a fourth implementation, alone or in combination with one or more of the first through third implementations, the second set of transformed forwarding next hop entries includes transformed forwarding next hop entries that are missing from the first set of transformed forwarding next hop entries, and the third set of transformed forwarding next hop entries includes new transformed forwarding next hop entries associated with forwarding classes included in the first set of transformed forwarding next hop entries.

In a fifth implementation, alone or in combination with one or more of the first through fourth implementations, the multi-level hybrid hierarchy forwarding information base includes four or more levels.

Therefore, from one perspective, there has been described a network device that can receive forwarding data associated with a multi-level hybrid hierarchy forwarding information base of the network device. The network device may process the forwarding data to generate a first set of transformed forwarding next hop entries. The network device may process the first set of transformed forwarding next hop entries, associated with default forwarding classes, to generate a second set of transformed forwarding next hop entries. The network device may process the first set of transformed forwarding next hop entries, associated with all classes of traffic, to generate a third set of transformed forwarding next hop entries. The network device may group the sets of transformed forwarding next hop entries, based on transformed group next hop entries, to generate a final set of transformed forwarding next hop entries. The network device may transform the final set of transformed forwarding next hop entries into a particular format.

As used herein, traffic or content may include a set of packets. A packet may refer to a communication structure for communicating information, such as a protocol data unit (PDU), a service data unit (SDU), a network packet, a datagram, a segment, a message, a block, a frame (e.g., an Ethernet frame), a portion of any of the above, and/or another type of formatted or unformatted unit of data capable of being transmitted via a network.

Claim 1:
A network device (<NUM>-<NUM>, ..., <NUM>-N), comprising:
one or more memories (<NUM>); and
one or more processors (<NUM>) configured to:
process (<NUM>) forwarding data, associated with a multi-level hybrid hierarchy forwarding information base of the network device, to generate (<NUM>) transformed group next hop entries and a first set of transformed forwarding next hop entries;
process (<NUM>), based on default forwarding classes, the transformed group next hop entries and the first set of transformed forwarding next hop entries, associated with the default forwarding classes, to generate a second set of transformed forwarding next hop entries;
process (<NUM>) the transformed group next hop entries and the first set of transformed forwarding next hop entries, associated with all classes of traffic, to generate a third set of transformed forwarding next hop entries;
group (<NUM>) the first set of transformed forwarding next hop entries, the second set of transformed forwarding next hop entries, and the third set of transformed forwarding next hop entries, based on the transformed group next hop entries, to generate a final set of transformed forwarding next hop entries; and
transform (<NUM>) the final set of transformed forwarding next hop entries into a particular format.