Prefix compression routes in exact match using redirection and mirroring FECs in hardware
Prefix compression routes provided via exact match using redirection and mirroring Forwarding Equivalence Class entries in hardware. In a network device, a first table is stored having a first entry, a second table is stored having a second entry, and a third table is stored having a third entry including routing information for routing data packets. The first entry references a first memory location in the second table, the second memory location stores the second entry, and the second entry referencing a second memory location in the third table. A data packet is received, and the first entry is accessed based on a destination address of the data packet. Routing information is obtained as a result of accessing the first entry. The data packet is sent by the network device according to the routing information.
1. A network device routing a data packet using prefix compression comprising:
a plurality of network interfaces;
at least one processor; and
at least one memory that stores:
an exact match (EM) table having a first plurality of entries;
an equal cost multi-path (ECMP) table having a second plurality of entries; and
a forwarding equivalence class (FEC) table having a third plurality of entries,
wherein entries in the EM table are used to access entries in the ECMP table and entries in the ECMP table are used to access entries in the FEC table;
said network device configured to:
receive the data packet on one of the plurality of network interfaces;
access an EM entry in the EM table using at most a subset of bits that constitute a destination address of the data packet, wherein the accessed EM entry comprises a plurality of indices to the ECMP table;
access an ECMP entry in the ECMP table using one of the plurality of indices in the accessed EM entry;
access a FEC entry in the FEC table using the ECMP entry;
obtain routing information contained in the FEC entry; and
transmit the data packet on one of the plurality of network interfaces according to the routing information in the FEC entry.
2. The network device of claim 1 , wherein the ECMP entry references an intermediate entry in the FEC table, wherein accessing the FEC entry using the ECMP entry includes:
accessing the intermediate entry in the FEC table using the reference in the ECMP entry; and
accessing the FEC entry using a reference in the intermediate entry.
3. The network device of claim 1 , wherein a source entry in the ECMP table includes a reference to the FEC entry, the network device further configured to:
mirror content of the source entry in the ECMP table to the ECMP entry, wherein the routing information is obtained as a result of the content in the source entry being mirrored to the ECMP entry.
4. A network device comprising:
a plurality of network interfaces comprising a first network interface;
at least one processor; and
at least one memory that stores:
an exact match (EM) table having a first plurality of entries that include a first entry;
an equal cost multi-path (ECMP) table having a second plurality of entries that include a second entry; and
a forwarding equivalence class (FEC) table having a third plurality of entries,
said network device configured to:
receive a data packet via the first network interface;
access the first entry in the EM table based on at most a subset of bits that constitute a destination address of the data packet, wherein the accessed first entry comprises a plurality of indices into the ECMP table;
access the second entry in the ECMP table using one of the plurality of indices in the accessed first entry;
access a third entry in the FEC table using the second entry;
obtain routing information contained in the third entry; and
transmit the data packet on one of the plurality of network interfaces according to the routing information.
5. The network device of claim 4 , wherein said one of the plurality of network interfaces is a second network interface different from the first network interface.
6. The network device of claim 4 , wherein the at least one memory further stores:
a fourth entry in the FEC table referencing the third entry in the FEC table, wherein the second entry references the fourth entry, the network device configured to: access the third entry via the fourth entry using the second entry.
7. The network device of claim 4 , wherein the at least one memory further stores:
a fourth plurality of entries in the ECMP table that includes a source entry that references the third entry in the FEC table, the network device configured to:
mirror content of the source entry to the second entry, wherein the routing information is obtained as a result of the content being mirrored to the second entry.
8. The network device of claim 4 , the network device further configured to:
multiply the subset of bits by a defined value to obtain a result, wherein the first entry is accessed based on the result.
9. The network device of claim 4 , wherein the data packet is received over a Layer 3 network, and the data packet is sent over a Layer 2 network.
10. A method for routing a data packet using prefix compression comprising:
configuring at least one non-transitory computer-readable media of a network device to store:
an exact match (EM) table having a first entry;
an equal cost multi-path (ECMP) table having a second entry; and
a forwarding equivalence class (FEC) table having a third entry,
wherein the first entry is used to access the second entry, and the second entry is used to access the third entry, the third entry including routing information;
receiving, by the network device, the data packet;
accessing the first entry based on at most a subset of bits that constitute a destination address of the data packet, wherein the accessed first entry comprises a plurality of indices into the ECMP table;
accessing the routing information via the second entry, wherein the second entry is accessed using one of the plurality of indices in the accessed first entry; and
sending the data packet over a network using the routing information.
11. The method of claim 10 , further comprising:
configuring the at least one non-transitory computer-readable media of the network device to include:
a fourth entry in the FEC table, the fourth entry referencing the third entry in the FEC table; and
accessing the third entry via the fourth entry as a result of accessing the first entry.
12. The method of claim 11 , wherein the fourth entry is stored in a first forwarding equivalence class (FEC) level of the FEC table, and the third entry is stored in a second FEC level of the FEC table separate from the first FEC level.
13. The method of claim 10 , further comprising:
configuring the memory to include a source entry in the ECMP table that references the third entry in the FEC table; and
mirroring content of the source entry to the second entry so that the second entry can be used to access the third entry.
14. The method of claim 10 , further comprising:
accessing the second entry as a result of redirection from the first entry; and
accessing the third entry as a result of redirection from the second entry.
15. The method of claim 10 , further comprising:
determining a first subset of bits and a second subset of bits of the destination address; and
accessing the first entry in the EM table based on the first subset of bits and the second subset of bits.
16. The method of claim 15 , further comprising multiplying a value of the second subset of bits to access the first entry.
17. The method of claim 10 , wherein the data packet is received over a Layer 3 network, and the data packet is sent over a Layer 2 network.