Routing table selection based on utilization

Patent metadata

Field	Value
Publication number	US-2021075724-A1
Application number	US-201916562366-A
Country	US
Kind code	A1
Filing date	Sep 5, 2019
Priority date	Sep 5, 2019
Publication date	Mar 11, 2021
Grant date	—

Abstract

In some embodiments, a method sets a threshold for utilization of a first table, wherein the utilization is based on layer 3 addresses and layer 2 addresses being stored in the first table. When a utilization of the first table does not meet the threshold, the method stores a layer 3 address in the first table. The first table uses a first type of lookup to determine a next hop address for the layer 3 addresses or the layer 2 addresses, and the first table also stores one or more layer 2 addresses. When the utilization of the first table meets the threshold, the method stores the layer 3 address in a second table where the second table uses a second type of lookup to determine the next hop address for layer 3 addresses.

First claim

1 . A method comprising:
determining, by a computing device, whether the utilization of a first table meets a threshold for utilization wherein the utilization is based on usage of memory allotted for storage of layer 3 addresses and layer 2 addresses in the first table; when the utilization of the first table does not meet the threshold, storing, by the computing device, a layer 3 address associated with an incoming packet received by the computing device in the first table; and; and when the utilization of the first table meets the threshold, storing, by the computing device, the layer 3 address associated with the incoming packet in a second table, wherein: a first type of lookup is done by the computing device in the first table to determine next hop information for a received packet, and a second type of lookup is done by the computing device in the second table to determine the next hop information for a received packet.

2 . The method of claim 1 , wherein:
the computing device uses an exact match table address lookup in the first table to determine an exact match of the layer 3 address or the layer 2 address to determine the next hop information , and the computing device uses a longest prefix address lookup in the second table to determine a longest prefix that matches the layer 3 address to determine the next hop information.

3 . The method of claim 1 , wherein the threshold for the first table comprises a first threshold for the first table, the method further comprising:
determining whether the utilization of the first table meets a second threshold for the first table, wherein the first threshold is greater than the second threshold; and when utilization of the first table meets the second threshold, evaluating layer 3 addresses in the second table to determine if any layer 3 address stored in the second table should be moved to the first table.

4 . The method of claim 3 , further comprising:
determining whether to change a table designation for a layer 3 address from the second table to the first table based on the evaluating.

5 . The method of claim 4 , further comprising:
when the table designation is changed, moving the layer 3 address from the second table to the first table.

6 . The method of claim 3 , further comprising:
moving a layer 3 address from the second table to the first table based on the evaluating.

7 . The method of claim 1 , wherein the threshold for the first table comprises a first threshold for the first table, the method further comprising:
after meeting the first threshold: determining when the utilization of the first table meets a second threshold for the first table, wherein the first threshold is greater than the second threshold; and when utilization of the first table meets the second threshold, storing a layer 3 address in the first table.

8 . The method of claim 1 , wherein the layer 3 address includes a prefix length that is eligible to be stored in the first table.

9 . The method of claim 1 , wherein the layer 3 address that is stored in the first table meet a criterion.

10 . The method of claim 9 , wherein the criterion comprises one or more prefix lengths that are specified for lengths of layer 3 addresses to be stored in the first table.

11 . The method of claim 1 , further comprising:
when the utilization of the first table meets the threshold, storing newly received layer 3 addresses in the second table.

12 . The method of claim 1 , wherein when the utilization of the first table meets the threshold, stopping the storing of layer 3 addresses in the first table.

13 . The method of claim 1 , wherein when the utilization of the first table meets the threshold, continuing to store layer 2 addresses in the first table.

14 . A non-transitory computer-readable storage medium having stored thereon computer executable instructions, which when executed by a computing device, cause the computing device to be operable for:
determining whether the utilization of a first table meets a threshold for utilization, wherein the utilization is based on usage of memory allotted for storage of layer 3 addresses and layer 2 addresses in the first table; when the utilization of the first table does not meet the threshold, storing a layer 3 address associated with an incoming packet received by the computing device in the first table; and when the utilization of the first table meets the threshold, storing the layer 3 address associated with the incoming packet in a second table, wherein: a first type of lookup is done by the computing device in the first table to determine next hop information for a received packet, and a second type of lookup is done by the computing device in the second table to determine the next hop information for a received packet.

15 . The non-transitory computer-readable storage medium of claim 14 , wherein:
the computing device uses an exact match table address lookup in the first table to determine an exact match of the layer 3 address or the layer 2 address to determine the next hop information , and the computing device uses a longest prefix address lookup in the second table to determine a longest prefix that matches the layer 3 address to determine the next hop information.

16 . The non-transitory computer-readable storage medium of claim 14 , wherein the threshold for the first table comprises a first threshold for the first table, further operable for:
determining whether the utilization of the first table meets a second threshold for the first table, wherein the first threshold is greater than the second threshold; and when utilization of the first table meets the second threshold, evaluating layer 3 addresses in the second table to determine if any layer 3 address stored in the second table should be moved to the first table.

17 . The non-transitory computer-readable storage medium of claim 14 , wherein the threshold for the first table comprises a first threshold for the first table, further operable for:
after meeting the first threshold: determining when the utilization of the first table meets a second threshold for the first table, wherein the first threshold is greater than the second threshold; and when utilization of the first table meets the second threshold, storing a layer 3 address in the first table.

18 . The non-transitory computer-readable storage medium of claim 14 , wherein the layer 3 address includes a prefix length that is eligible to be stored in the first table.

19 . The non-transitory computer-readable storage medium of claim 14 , wherein the layer 3 address that is stored in the first table meet a criterion.

20 . An apparatus comprising:
one or more computer processors; and a computer-readable storage medium comprising instructions for controlling the one or more computer processors to be operable for: determining whether the utilization of a first table meets a threshold for utilization, wherein the utilization is based on usage of memory allotted for storage of layer 3 addresses and layer 2 addresses in the first table; when the utilization of the first table does not meet the threshold, storing a layer 3 address associated with an incoming packet received by the apparatus in the first table; and when the utilization of the first table meets the threshold, storing the layer 3 address associated with the incoming packet in a second table, wherein: a first type of lookup is done by the apparatus in the first table to determine next hop information for a recei

Assignees

• Arista Networks Inc

Inventors

• Nagre Dhanashree
• Sellappa Sriram
• Gupta Rajnish

Classifications

• H04L45/741 Primary

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

• H04L45/66 Primary

  Layer 2 routing, e.g. in Ethernet based MAN's · CPC title

• H04L45/20

  Hop count for routing purposes, e.g. TTL · CPC title

• H04L45/748

  using longest matching prefix · CPC title