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

Patent metadata

Field	Value
Publication number	US-9979651-B2
Application number	US-201715585119-A
Country	US
Kind code	B2
Filing date	May 2, 2017
Priority date	Feb 27, 2015
Publication date	May 22, 2018
Grant date	May 22, 2018

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 to load an exact match table and a longest prefix match table, the method comprising:
receiving a plurality of prefixes, wherein at least one pair of the plurality of prefixes are a first set of adjacent prefixes;
generating an exact match table key for the first set of adjacent prefixes;
generating a second set of exact match table keys for others of the plurality of prefixes;
storing the exact match table key and a first set of indications of one or more forwarding results associated with each of the first set of adjacent prefixes in an entry of the exact match table; and
storing the set of exact match table keys and a second set of indications of one or more forwarding results associated with each of the others of the plurality of prefixes in a set of entries of the exact match table, wherein another set of indications of forwarding results for another set of prefixes is stored in the longest prefix match table and the exact match table and the longest prefix match table are used to produce one resolved forwarding result.

2. The non-transitory machine-readable medium of claim 1 , wherein the exact match table key is a prefix.

3. The non-transitory machine-readable medium of claim 2 , wherein the exact match table key is a union of the first set of adjacent prefixes.

4. The non-transitory machine-readable medium of claim 3 , wherein the first set of adjacent prefixes each have a prefix length N and differ in the N th bit.

5. The non-transitory machine-readable medium of claim 3 , wherein the exact match table key includes a netmask of 23 and each of the adjacent prefixes has a netmask of 24.

6. The non-transitory machine-readable medium of claim 1 , wherein the forwarding results for the first set of prefixes are different.

7. The non-transitory machine-readable medium of claim 1 , wherein the storing the set of exact match table keys comprises:
storing another one of the plurality of prefixes in an entry in the exact match table when this prefix is more specific than any corresponding prefix stored in a longest prefix match table that covers that same range as this prefix.

8. The non-transitory machine-readable medium of claim 1 , further comprising:
splitting at least another one of the plurality of prefixes into a second set of two adjacent prefixes;
generating a plurality of keys for the second set of two adjacent prefixes; and
for each prefix in the second set of adjacent prefixes,
storing a key of the plurality of keys that corresponds to this prefix in another entry in the exact match table.

9. A method to load an exact match table and a longest prefix match table, the method comprising:
receiving a plurality of prefixes, wherein at least one pair of the plurality of prefixes are a first set of adjacent prefixes;
generating an exact match table key for the first set of adjacent prefixes;
generating a second set of exact match table keys for others of the plurality of prefixes;
storing the exact match table key and a first set of indications of one or more forwarding results associated with each of the first set of adjacent prefixes in an entry of the exact match table; and
storing the set of exact match table keys and a second set of indications of one or more forwarding results associated with each of the others of the plurality of prefixes prefixes in a set of entries of the exact match table, wherein another set of indications of forwarding results for another set of prefixes is stored in the longest prefix match table and the exact match table and the longest prefix match table are used to produce one resolved forwarding result.

10. The method of claim 9 , wherein the exact match table key is a prefix.

11. The method of claim 10 , wherein the exact match table key is a union of the first set of adjacent prefixes.

12. The method of claim 10 , wherein the first set of adjacent prefixes each have a prefix length N and differ in the N th bit.

13. The method of claim 10 , wherein each prefix of the first set of adjacent prefixes represents a forwarding result.

14. A non-transitory machine-readable medium having executable instructions to cause one or more processing units to perform a method to load an exact match table and a longest prefix match table, the method comprising:
receiving a prefix;
splitting the received prefix into a plurality adjacent prefixes;
generating a plurality of keys for a set of two adjacent prefixes; and
for each prefix in the set of adjacent prefixes,
storing an indication of a forwarding result for this prefix and a key of the plurality of keys that corresponds to this prefix in different entry in the exact match table, wherein another set of indications of forwarding results for another set of prefixes is stored in the longest prefix match table and the exact match table and the longest prefix match table are used to produce one resolved forwarding result.

15. A non-transitory machine-readable medium having executable instructions to cause one or more processing units to perform a method to load a first exact match table and a longest prefix match table, the method comprising:
receiving a plurality of prefixes to store in the first exact match table having different prefix lengths, wherein each of the plurality of prefixes represents multiple addresses;
storing a first set of forwarding indications for a first set of the plurality prefixes in the first exact match table that have a prefix length equal to a first desired prefix length;
storing a second set of forwarding indications for a second set of the plurality of prefixes in the longest prefix match table and the exact match table and the longest prefix match table are used to produce one resolved forwarding result; and
storing a third set of forwarding indications for a third set of the plurality of prefixes in a second exact match table, wherein each of the third subset of the plurality of prefixes has a prefix length equal to a second desired prefix of the second exact match table.

16. The machine-readable medium claim of 15 , wherein the storing the first set of forwarding indications comprises:
deriving a set of longer prefixes from a shorter prefix selected from the plurality of prefixes, wherein each of the set of longer prefixes has a prefix length equal to the first desired prefix length; and
storing a subset of the first set of forwarding result indications that correspond to the set of longer prefixes in the first exact match table.

17. The machine-readable medium claim of 16 , wherein the shorter prefix has a prefix length of N−1 and there are two prefixes in the set of longer prefixes, each of the two prefixes having a prefix length of N.

18. The machine-readable medium claim of 16 , wherein the shorter prefix has a prefix length of N−2 and there are four prefixes in the set of longer prefixes, each of the four prefixes having a prefix length of N.

19. The machine-readable medium claim of 15 , wherein a forwarding indication is selected from the group consisting of a nexthop indication, a transmitting interface indication, and a transmitting virtual interface indication.

20. A non-transitory machine-readable medium having executable instructions to cause one or more processing units to perform a method to load an exact match table and a longest prefix match table, the method comprising:
receiving a plurality of prefixes to store in

Assignees

• Arista Networks Inc

Inventors

• Labonte Francois
• Holbrook Hugh W

Classifications

• H04L45/748 Primary

  using longest matching prefix · CPC title

• H04L45/741

  Routing in networks with a plurality of addressing schemes, e.g. with both IPv4 and IPv6 · CPC title

• H04L47/17

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

• H04L45/586

  of virtual routers · CPC title

• H04L61/6095

  Electricity · mapped topic