IP Library › Granted Patent US 10,341,218

Granted Patent B2

US 10,341,218 · App. 15/056,334 · Granted Jul 2, 2019

Forwarding information base entry priority

Inventor: Kenneth James Duda (Santa Clara, CA)

Assignee: Arista Networks, Inc.

H04L45/02

View Patent ↗

Loading inventors, assignments & file history…

Monitor This Case

Get email alerts when status or documents change.

Order Certified Copies

Most orders are placed with the USPTO same day — all within 24 business hours.

Order via The Patent Place →

Pre-filled with this patent's details

Quick Facts

Patent No.: US 10,341,218
App. No.: 15/056,334
Granted: Jul 2, 2019
Kind: B2

External Links

USPTO Patent Center↗ Full Patent PDF↗

Abstract

In general, embodiments of the invention relate to a method of programming a data plane forwarding information base (FIB). The method includes obtaining, by a FIB entry optimizer in a control plane, a new entry to be loaded into the data plane FIB, making a first determination, by the FIB entry optimizer, that the data plane FIB is not full; and based on the first determination: loading, by the FIB entry optimizer, the new entry into the data plane FIB.

Claims (109)

1. A method of programming a data plane forwarding information base (FIB), comprising:

obtaining, by a FIB entry optimizer executing on circuitry of a network processor, a to-be-unloaded entry, wherein the to-be-unloaded entry is a control plane FIB entry that has been removed from a control plane FIB;

making a first determination, by the FIB entry optimizer, that a data plane FIB includes a matching entry that matches the to-be-unloaded entry;

making a second determination, by the FIB entry optimizer, that the data plane FIB is full;

in response to the first determination and second determination:

obtaining, by the FIB entry optimizer, an identified control plane FIB entry of the control plane FIB that does not have a corresponding data plane FIB entry and has the highest priority among a set of control plane FIB entries that do not have corresponding data plane FIB entries;

unloading, by the FIB entry optimizer, the matching entry from the data plane FIB; and

loading, by the FIB entry optimizer, the identified control plane FIB entry into the data plane FIB.

2. The method of claim 1 , wherein there are at least two entries in the control plane FIB having the highest priority.

3. The method of claim 1 , further comprising:

making a third determination, by the FIB entry optimizer, that a second to-be-unloaded entry is in the data plane FIB;

making a fourth determination, by the FIB entry optimizer, that the data plane FIB is not full;

unloading, by the FIB entry optimizer, the second to-be-unloaded entry from the data plane FIB.

4. The method of claim 1 , further comprising:

making a third determination, by the FIB entry optimizer, that a second to-be-unloaded entry is not in the data plane FIB;

making a fourth determination, by the FIB entry optimizer, that the second to-be-unloaded entry is not to be unloaded from the data plane FIB.

5. The method of claim 1 , wherein the to-be-unloaded entry comprises a route prefix, a next hop information, and a priority.

6. A method of programming a data plane forwarding information base (FIB), comprising:

obtaining, by a FIB entry optimizer in a control plane executing on circuitry of a network processor, a change to a priority of an entry of a control plane FIB;

making a first determination, by the FIB entry optimizer, that the entry of the control plane FIB is in the data plane FIB;

identifying, by the FIB entry optimizer, a highest priority of any entry of the control plane FIB that is not in the data plane FIB;

making a second determination, by the FIB entry optimizer, that the change to the priority of the entry of the control plane FIB changed the priority to a value lower than the highest priority;

unloading, by the FIB entry optimizer, the entry of the control plane FIB from the data plane FIB; and

loading, by the FIB entry optimizer, the entry of the control plane FIB having the highest priority of any entry of the control plane FIB that is not in the data plane FIB.

7. The method of claim 6 , further comprising:

obtaining, by the FIB entry optimizer in a control plane, a second change to a priority of a second entry of the control plane FIB;

making a third determination, by the FIB entry optimizer, that the second entry of the control plane FIB is in the data plane FIB;

making a fourth determination, by the FIB entry optimizer, that the second change to the priority of the second entry of the control plane FIB changes the priority to a value higher than the highest priority; and

making a fifth determination, by the FIB entry optimizer, that the second entry of the control plane FIB is not to be unloaded from the data plane FIB.

8. The method of claim 6 , further comprising:

obtaining, by the FIB entry optimizer in a control plane, a second change to a priority of a second entry of the control plane FIB;

making a third determination, by the FIB entry optimizer, that the second entry of the control plane FIB is not in the data plane FIB;

identifying, by the FIB entry optimizer, a lowest priority of any entry of the data plane FIB;

making a fourth determination, by the FIB entry optimizer, that second change to the priority of the second entry of the control plane FIB changes the priority of the second entry of the control plane FIB to be less than the lowest priority; and

making a fifth determination, by the FIB entry optimizer, that the second entry of the control plane FIB is not to be unloaded from the data plane FIB based on the fourth determination.

9. The method of claim 6 , further comprising:

obtaining, by the FIB entry optimizer in a control plane, a second change to a priority of a second entry of the control plane FIB;

making a third determination, by the FIB entry optimizer, that the second entry of the control plane FIB is not in the data plane FIB;

identifying, by the FIB entry optimizer, a lowest priority of any entry of the data plane FIB;

unloading, by the FIB entry optimizer, an entry of the data plane FIB having the lowest priority; and

loading, by the FIB entry optimizer, the second entry of the control plane FIB into the data plane FIB.

10. A non-transitory computer readable medium (CRM) comprising computer readable program code, which when executed by a computer processor, enables the computer processor to:

making a first determination, by the FIB entry optimizer, that a data plane FIB includes a matching entry that matches the to-be-unloaded entry;

making a second determination, by the FIB entry optimizer, that the data plane FIB is full;

in response to the first determination and second determination:

unloading, by the FIB entry optimizer, the matching entry from the data plane FIB; and

loading, by the FIB entry optimizer, the identified control plane FIB entry into the data plane FIB.

11. The non-transitory CRM of claim 10 , wherein there are at least two entries in the control plane FIB having the highest priority.

12. The non-transitory CRM of claim 10 , further comprising computer readable program code, which when executed by the computer processor, enables the computer processor to:

make a third determination, by the FIB entry optimizer, that a second to-be-unloaded entry is in the data plane FIB;

make a fourth determination, by the FIB entry optimizer, that the data plane FIB is not full;

unload, by the FIB entry optimizer, the second to-be-unloaded entry from the data plane FIB.

13. The non-transitory CRM of claim 10 , further comprising computer readable program code, which when executed by the computer processor, enables the computer processor to:

make a third determination, by the FIB entry optimizer, that a second to-be-unloaded entry is not in the data plane FIB;

make a fourth determination, by the FIB entry optimizer, that the second to-be-unloaded entry is not to be unloaded from the data plane FIB.

14. The non-transitory CRM of claim 10 , wherein the to-be-unloaded entry comprises a route prefix, a next hop information, and a priority.

15. A network device, comprising:

a processor;

a memory;

a control plane forwarding information base (FIB);

a data plane FIB; and

a FIB entry optimizer operatively connected to the control plane FIB and the data plane FIB, and programmed to:

obtain, by a FIB entry optimizer executing on circuitry of a network processor, a to-be-unloaded entry, wherein the to-be-unloaded entry is a control plane FIB entry that has been removed from a control plane FIB;

make a first determination, by the FIB entry optimizer, that a data plane FIB includes a matching entry that matches the to-be-unloaded entry;

make a second determination, by the FIB entry optimizer, that the data plane FIB is full;

in response to the first determination and second determination:

obtain, by the FIB entry optimizer, an identified control plane FIB entry of the control plane FIB that does not have a corresponding data plane FIB entry and has the highest priority among a set of control plane FIB entries that do not have corresponding data plane FIB entries;

unload, by the FIB entry optimizer, the matching entry from the data plane FIB; and

load, by the FIB entry optimizer, the identified control plane FIB entry into the data plane FIB.

16. A non-transitory computer readable medium (CRM) comprising computer readable program code, which when executed by a computer processor, enables the computer processor to:

obtain, by a FIB entry optimizer in a control plane executing on circuitry of a network processor, a change to a priority of an entry of a control plane FIB;

make a first determination, by the FIB entry optimizer, that the entry of the control plane FIB is in the data plane FIB;

identify, by the FIB entry optimizer, a highest priority of any entry of the control plane FIB that is not in the data plane FIB;

make a second determination, by the FIB entry optimizer, that the change to the priority of the entry of the control plane FIB changed the priority to a value lower than the highest priority;

unload, by the FIB entry optimizer, the entry of the control plane FIB from the data plane FIB; and

load, by the FIB entry optimizer, the entry of the control plane FIB having the highest priority of any entry of the control plane FIB that is not in the data plane FIB.

17. The non-transitory CRM of claim 16 , further comprising computer readable program code, which when executed by the computer processor, enables the computer processor to:

obtain, by the FIB entry optimizer in a control plane, a second change to a priority of a second entry of the control plane FIB;

make a third determination, by the FIB entry optimizer, that the second entry of the control plane FIB is in the data plane FIB;

make a fourth determination, by the FIB entry optimizer, that the second change to the priority of the second entry of the control plane FIB changes the priority to a value higher than the highest priority; and

make a fifth determination, by the FIB entry optimizer, that the second entry of the control plane FIB is not to be unloaded from the data plane FIB.

18. The non-transitory CRM of claim 16 , further comprising computer readable program code, which when executed by the computer processor, enables the computer processor to:

obtain, by the FIB entry optimizer in a control plane, a second change to a priority of a second entry of the control plane FIB;

make a third determination, by the FIB entry optimizer, that the second entry of the control plane FIB is not in the data plane FIB;

identify, by the FIB entry optimizer, a lowest priority of any entry of the data plane FIB;

make a fourth determination, by the FIB entry optimizer, that second change to the priority of the second entry of the control plane FIB changes the priority of the second entry of the control plane FIB to be less than the lowest priority; and

make a fifth determination, by the FIB entry optimizer, that the second entry of the control plane FIB is not to be unloaded from the data plane FIB based on the fourth determination.

19. The non-transitory CRM of claim 16 , further comprising computer readable program code, which when executed by the computer processor, enables the computer processor to:

obtain, by the FIB entry optimizer in a control plane, a second change to a priority of a second entry of the control plane FIB;

make a third determination, by the FIB entry optimizer, that the second entry of the control plane FIB is not in the data plane FIB;

identify, by the FIB entry optimizer, a lowest priority of any entry of the data plane FIB;

unload, by the FIB entry optimizer, an entry of the data plane FIB having the lowest priority; and

load, by the FIB entry optimizer, the second entry of the control plane FIB into the data plane FIB.

20. A network device, comprising:

a processor;

a memory;

a control plane forwarding information base (FIB);

a data plane FIB; and

a FIB entry optimizer operatively connected to the control plane FIB and the data plane FIB, and programmed to:

obtain a change to a priority of an entry of the control plane FIB;

make a first determination that the entry of the control plane FIB is in the data plane FIB;

identify a highest priority of any entry of the control plane FIB that is not in the data plane FIB;

make a second determination that the change to the priority of the entry of the control plane FIB changed the priority to a value lower than the highest priority;

unload the entry of the control plane FIB from the data plane FIB; and

load the entry of the control plane FIB having the highest priority of any entry of the control plane FIB that is not in the data plane FIB.

Assignments (1)

ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Apr 13, 2016

From: DUDA, KENNETH JAMES

To: ARISTA NETWORKS, INC.

Reel/Frame 038265/0944 →

Continuity (1)

Related Publication 20170250893A1 · Aug 31, 2017