System and method of loading an exact match table and longest prefix match table

Patent metadata

Field	Value
Publication number	US-10887233-B2
Application number	US-202016797221-A
Country	US
Kind code	B2
Filing date	Feb 21, 2020
Priority date	Feb 27, 2015
Publication date	Jan 5, 2021
Grant date	Jan 5, 2021

Abstract

A method and apparatus of a device that determines a match for a destination address using an exact match table and a longest prefix match table of a network element is described. In an exemplary embodiment, the network element receives a data packet that includes a destination address. The network element generates a key for the destination address, wherein the key represents more addresses than the destination address. The network element further performs an address lookup using the key in an exact match table. Furthermore, a match in the address lookup indicates a first transmitting interface of the network element. The network element additionally performs an address lookup using the destination address with a longest prefix match table, wherein a match in the address lookup indicates a second transmitting interface of the network element. In addition, the network element determines a resulting transmitting interface based on results from the exact match table address lookup and the longest prefix match address lookup. The network element forwards the data packet using the transmitting interface.

First claim

What is claimed is:

1. A non-transitory machine-readable medium having executable instructions to cause one or more processing units to perform a method comprising:
receiving, with a network element, a data packet that includes a destination address;
generating a key for the destination address, wherein the key represents more addresses than the destination address;
performing an exact match table address lookup using the key with an exact match table, wherein a match in the exact match table address lookup provides a first result;
performing a longest prefix match address lookup using the destination address with a longest prefix match table, wherein a match in the longest prefix match address lookup provides a second result comprising an encoded length of the longest prefix match;
selecting the first or second result based on a presence of the match in the exact match table address lookup and the encoded length of the longest prefix match;
determining a resulting transmitting interface from the selected first or second result; and
forwarding the data packet using the transmitting interface.

2. The medium of claim 1 , wherein the generating the key comprises:
determining a type of key; and
masking a plurality of lower bits of the destination address based on the type of key.

3. The medium of claim 1 , wherein the first result comprises a transmitting interface.

4. The medium of claim 3 , wherein the performing the exact match address lookup comprises:
matching the key to an exact match table key, wherein the exact match key is associated with a plurality of prefixes;
determining which of the plurality of prefixes matches the destination address; and
returning a first transmitting interface associated with the matching prefix as the transmitting interface of the first result.

5. The medium of claim 4 , wherein the plurality of prefixes corresponds to adjacent ranges of addresses.

6. The medium of claim 3 , wherein generating the key comprises generating a plurality of keys with different prefix lengths.

7. The medium of claim 6 , wherein the performing the exact match address lookup comprises:
matching the plurality of keys to a plurality of keys stored in the exact match table, wherein each of the plurality of keys stored in the exact match table is associated with a different prefix;
determining which of a plurality of prefixes matches the destination address; and
returning a first transmitting interface associated with the matching prefix as the transmitting interface of the first result.

8. A method to determine a match for a destination address using an exact match table and longest prefix match table, the method comprising:
receiving, with a network element, a data packet that includes a destination address;
generating a key for the destination address, wherein the key represents more addresses than the destination address;
performing an exact match table address lookup using the key with an exact match table, wherein a match in the exact match table address lookup provides a first result;
performing a longest prefix match address lookup using the destination address with a longest prefix match table, wherein a match in the longest prefix match address lookup provides a second result comprising an encoded length of the longest prefix match;
selecting the first or second result based on a presence of the match in the exact match table address lookup and the encoded length of the longest prefix match;
determining a resulting transmitting interface from the selected first or second result; and
forwarding the data packet using the transmitting interface.

9. The method of claim 8 , wherein the generating the key comprises:
determining a type of key; and
masking a plurality of lower bits of the destination address based on the key type of key.

10. The method of claim 8 , wherein the first result comprises a transmitting interface.

11. The method of claim 10 , wherein the performing the exact match address lookup comprises:
matching the key to an exact match table key, wherein the exact match key is associated with a plurality of prefixes;
determining which of the plurality of prefixes matches the destination address; and
returning a first transmitting interface associated with the matching prefix as the transmitting interface of the first result.

12. The method of claim 11 , wherein the plurality of prefixes corresponds to adjacent ranges of addresses.

13. The method of claim 10 , wherein generating the key comprises generating a plurality of keys with different prefix lengths.

14. The method of claim 13 , wherein the performing the exact match address lookup comprises:
matching the plurality of keys to a plurality of keys stored in the exact match table, wherein each of the plurality of keys stored in the exact match table is associated with a different prefix;
determining which of a plurality of prefixes matches the destination address; and
returning a first transmitting interface associated with the matching prefix as the transmitting interface of the first result.

Assignees

• Arista Networks Inc

Inventors

• Labonte Francois
• Holbrook Hugh W

Classifications

• H04L2101/695

  using masks or ranges of addresses · CPC title

• H04L2101/686

  using dual-stack hosts, e.g. in Internet protocol version 4 [IPv4]/Internet protocol version 6 [IPv6] networks · CPC title

• H04L45/586

  of virtual routers · CPC title

• H04L47/17

  Interaction among intermediate nodes, e.g. hop by hop · CPC title

• H04L45/748 Primary

  using longest matching prefix · CPC title