FORWARDING TABLE PRECEDENCE IN SDN

• US 20160072696A1
• Filed: 09/05/2014
• Published: 03/10/2016
• Est. Priority Date: 09/05/2014
• Status: Active Grant

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: He, Jiang, Wang, He, Zhao, Zhenning, Li, Xianmin
• Granted Patent: US 9,692,684 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: H04L 45/021 Ensuring consistency of routing table updates, e.g. by using epoch numbers
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 45/64 using an overlay routing layer

Abstract

Exemplary methods for maintaining a shared forwarding table in a forwarding plane include a first network device operating in a forwarding plane receiving information associated with a first forwarding table from a second network device operating in a control plane, the information including a plurality of entries and precedence information, the precedence information indicating a priority of the plurality of entries of the first forwarding table. The methods further include for each entry of the first forwarding table, determining whether the entry should be inserted in the shared forwarding table based on the precedence information of the first forwarding table and precedence information contained in the shared forwarding table, wherein the precedence information contained in the shared forwarding table indicates a priority of each corresponding entry stored in the shared forwarding table.

Claims

1. A method in a first network device operating in a forwarding plane for maintaining a shared forwarding table based on forwarding table precedence information received from a second network device operating in a control plane, wherein the shared forwarding table implements a plurality of forwarding tables, the method comprising:

receiving information associated with a first forwarding table from the second network device, the information including a plurality of entries and precedence information, the precedence information indicating a priority of the plurality of entries of the first forwarding table; and

for each entry of the first forwarding table, determining whether the entry should be inserted in the shared forwarding table based on the precedence information of the first forwarding table and precedence information contained in the shared forwarding table, wherein the precedence information contained in the shared forwarding table indicates a priority of each corresponding entry stored in the shared forwarding table.

2. The method of claim 1, wherein for each entry of the first forwarding table, determining whether the entry should be inserted in the shared forwarding table comprises:

determining a first candidate location in the shared forwarding table for a first entry of the first forwarding table; and

in response to determining the first candidate location is occupied by a first entry stored in the shared forwarding table, determining whether the first entry stored in the shared forwarding table should be evicted from the first candidate location based on the precedence information of the first entry of the first forwarding table and precedence information of the first entry stored in the shared forwarding table.

3. The method of claim 2, further comprising:

in response to determining the precedence information of the first entry stored in the shared forwarding table indicating it has a priority that is higher than or equal to a priority of the first entry of the first forwarding table, determining a second candidate location in the shared forwarding table for the first entry of the first forwarding table.

4. The method of claim 2, further comprising:

in response to determining the precedence information of the first entry of the first forwarding table indicating it has a higher priority than the first entry stored in the shared forwarding table;

evicting the first entry stored in the shared forwarding table from the first candidate location,

inserting the first entry of the first forwarding table in the first candidate location, and

determining a second candidate location in the shared forwarding table for the evicted first entry that was stored in the first candidate location.

5. The method of claim 3, further comprising:

prior to determining each candidate location, determining whether a number of attempts at determining the candidate location has reached a predetermined threshold; and

in response to determining the number of attempts has reached the predetermined threshold, discarding an entry for which the candidate location is being determined.

6. A first network device operating in a forwarding plane for maintaining a shared forwarding table based on forwarding table precedence information received from a second network device operating in a control plane, wherein the shared forwarding table implements a plurality of forwarding tables, the first network device comprising:

a set of one or more processors; and

a non-transitory machine-readable storage medium containing code, which when executed by the set of one or more processors, cause the first network device to;

receive information associated with a first forwarding table from the second network device, the information including a plurality of entries and precedence information, the precedence information indicating a priority of the plurality of entries of the first forwarding table, and

for each entry of the first forwarding table, determine whether the entry should be inserted in the shared forwarding table based on the precedence information of the first forwarding table and precedence information contained in the shared forwarding table, wherein the precedence information contained in the shared forwarding table indicates a priority of each corresponding entry stored in the shared forwarding table.

7. The first network device of claim 6, wherein for each entry of the first forwarding table, determining whether the entry should be inserted in the shared forwarding table comprises the first network device:

determine a first candidate location in the shared forwarding table for a first entry of the first forwarding table; and

in response to determining the first candidate location is occupied by a first entry stored in the shared forwarding table, determine whether the first entry stored in the shared forwarding table should be evicted from the first candidate location based on the precedence information of the first entry of the first forwarding table and precedence information of the first entry stored in the shared forwarding table.

8. The first network device of claim 7, wherein for each entry of the first forwarding table, determining whether the entry should be inserted in the shared forwarding table further comprises the first network device to:

in response to determining the precedence information of the first entry stored in the shared forwarding table indicating it has a priority that is higher than or equal to a priority of the first entry of the first forwarding table, determine a second candidate location in the shared forwarding table for the first entry of the first forwarding table.

9. The first network device of claim 7, wherein for each entry of the first forwarding table, determining whether the entry should be inserted in the shared forwarding table further comprises the first network device to:

in response to determining the precedence information of the first entry of the first forwarding table indicating it has a higher priority than the first entry stored in the shared forwarding table;

evict the first entry stored in the shared forwarding table from the first candidate location,

insert the first entry of the first forwarding table in the first candidate location, and

determine a second candidate location in the shared forwarding table for the evicted first entry that was stored in the first candidate location.

10. The first network device of claim 8, wherein the non-transitory machine-readable storage medium further contains code, which when executed by the set of one or more processors, cause the first network device to:

prior to determining each candidate location, determine whether a number of attempts at determining the candidate location has reached a predetermined threshold; and

in response to determining the number of attempts has reached the predetermined threshold, discard an entry for which the candidate location is being determined.

11. A non-transitory computer-readable storage medium having computer code stored therein, which when executed by a processor of a first network device operating in a forwarding plane for maintaining a shared forwarding table based on forwarding table precedence information received from a second network device operating in a control plane, wherein the shared forwarding table implements a plurality of forwarding tables, cause the first network device to perform operations comprising:

receiving information associated with a first forwarding table from the second network device, the information including a plurality of entries and precedence information, the precedence information indicating a priority of the plurality of entries of the first forwarding table; and

for each entry of the first forwarding table, determining whether the entry should be inserted in the shared forwarding table based on the precedence information of the first forwarding table and precedence information contained in the shared forwarding table, wherein the precedence information contained in the shared forwarding table indicates a priority of each corresponding entry stored in the shared forwarding table.

12. The non-transitory computer-readable storage medium of claim 11, wherein for each entry of the first forwarding table, determining whether the entry should be inserted in the shared forwarding table comprises:

determining a first candidate location in the shared forwarding table for a first entry of the first forwarding table; and

in response to determining the first candidate location is occupied by a first entry stored in the shared forwarding table, determining whether the first entry stored in the shared forwarding table should be evicted from the first candidate location based on the precedence information of the first entry of the first forwarding table and precedence information of the first entry stored in the shared forwarding table.

13. The non-transitory computer-readable storage medium of claim 12, further comprising:

in response to determining the precedence information of the first entry stored in the shared forwarding table indicating it has a priority that is higher than or equal to a priority of the first entry of the first forwarding table, determining a second candidate location in the shared forwarding table for the first entry of the first forwarding table.

14. The non-transitory computer-readable storage medium of claim 12, further comprising:

in response to determining the precedence information of the first entry of the first forwarding table indicating it has a higher priority than the first entry stored in the shared forwarding table;

evicting the first entry stored in the shared forwarding table from the first candidate location,

inserting the first entry of the first forwarding table in the first candidate location, and

determining a second candidate location in the shared forwarding table for the evicted first entry that was stored in the first candidate location.

15. The non-transitory computer-readable storage medium of claim 13, further comprising:

prior to determining each candidate location, determining whether a number of attempts at determining the candidate location has reached a predetermined threshold; and

in response to determining the number of attempts has reached the predetermined threshold, discarding an entry for which the candidate location is being determined.

16. A method in a first network device operating in a control plane for distributing precedence information of a plurality of forwarding tables to a second network device operating in a forwarding plane, wherein the precedence information is used by the second network device to maintain a shared forwarding table that implements the plurality of forwarding tables, the method comprising:

sending information associated with a first forwarding table to the second network device, the information including a plurality of entries and precedence information, the precedence information indicating a priority of the plurality of entries of the first forwarding table, wherein the information of the first forwarding table causes the second network device to, for each entry of the first forwarding table, determine whether the entry should be inserted in the shared forwarding table based on the precedence information of the first forwarding table and precedence information contained in the shared forwarding table, wherein the precedence information contained in the shared forwarding table indicates a priority of each corresponding entry stored in the shared forwarding table.

17. The method of claim 16, wherein the information of the first forwarding table causes the second network device to perform operations comprising:

determining a first candidate location in the shared forwarding table for a first entry of the first forwarding table; and

in response to determining the first candidate location is occupied by a first entry stored in the shared forwarding table, determining whether the first entry stored in the shared forwarding table should be evicted from the first candidate location based on the precedence information of the first entry of the first forwarding table and precedence information of the first entry stored in the shared forwarding table.

18. The method of claim 17, wherein the information of the first forwarding table causes the second network device to perform operations further comprising:

in response to determining the precedence information of the first entry stored in the shared forwarding table indicating it has a priority that is higher than or equal to a priority of the first entry of the first forwarding table, determining a second candidate location in the shared forwarding table for the first entry of the first forwarding table.

19. The method of claim 17, wherein the information of the first forwarding table causes the second network device to perform operations further comprising:

in response to determining the precedence information of the first entry of the first forwarding table indicating it has a higher priority than the first entry stored in the shared forwarding table;

evicting the first entry stored in the shared forwarding table from the first candidate location,

inserting the first entry of the first forwarding table in the first candidate location, and

determining a second candidate location in the shared forwarding table for the evicted first entry that was stored in the first candidate location.

20. A first network device operating in a control plane for distributing precedence information of a plurality of forwarding tables to a second network device operating in a forwarding plane, wherein the precedence information is used by the second network device to maintain a shared forwarding table that implements the plurality of forwarding tables, the first network device comprising:

a set of one or more processors; and

a non-transitory machine-readable storage medium containing code, which when executed by the set of one or more processors, cause the first network device to;

send information associated with a first forwarding table to the second network device, the information including a plurality of entries and precedence information, the precedence information indicating a priority of the plurality of entries of the first forwarding table, wherein the information of the first forwarding table causes the second network device to, for each entry of the first forwarding table, determine whether the entry should be inserted in the shared forwarding table based on the precedence information of the first forwarding table and precedence information contained in the shared forwarding table, wherein the precedence information contained in the shared forwarding table indicates a priority of each corresponding entry stored in the shared forwarding table.

21. The first network device of claim 20, wherein the information of the first forwarding table causes the second network device to perform operations comprising:

determining a first candidate location in the shared forwarding table for a first entry of the first forwarding table; and

in response to determining the first candidate location is occupied by a first entry stored in the shared forwarding table, determining whether the first entry stored in the shared forwarding table should be evicted from the first candidate location based on the precedence information of the first entry of the first forwarding table and precedence information of the first entry stored in the shared forwarding table.

22. The first network device of claim 21, wherein the information of the first forwarding table causes the second network device to perform operations further comprising:

in response to determining the precedence information of the first entry stored in the shared forwarding table indicating it has a priority that is higher than or equal to a priority of the first entry of the first forwarding table, determining a second candidate location in the shared forwarding table for the first entry of the first forwarding table.

23. The first network device of claim 21, wherein the information of the first forwarding table causes the second network device to perform operations further comprising:

in response to determining the precedence information of the first entry of the first forwarding table indicating it has a higher priority than the first entry stored in the shared forwarding table;

evicting the first entry stored in the shared forwarding table from the first candidate location,

inserting the first entry of the first forwarding table in the first candidate location, and

determining a second candidate location in the shared forwarding table for the evicted first entry that was stored in the first candidate location.

24. A non-transitory computer-readable storage medium having computer code stored therein, which when executed by a processor of a first network device operating in a control plane for distributing precedence information of a plurality of forwarding tables to a second network device operating in a forwarding plane, wherein the precedence information is used by the second network device to maintain a shared forwarding table that implements the plurality of forwarding tables, cause the first network device to perform operations comprising:

sending information associated with a first forwarding table to the second network device, the information including a plurality of entries and precedence information, the precedence information indicating a priority of the plurality of entries of the first forwarding table, wherein the information of the first forwarding table causes the second network device to, for each entry of the first forwarding table, determine whether the entry should be inserted in the shared forwarding table based on the precedence information of the first forwarding table and precedence information contained in the shared forwarding table, wherein the precedence information contained in the shared forwarding table indicates a priority of each corresponding entry stored in the shared forwarding table.

25. The non-transitory computer-readable storage medium of claim 24, wherein the information of the first forwarding table causes the second network device to perform operations comprising:

determining a first candidate location in the shared forwarding table for a first entry of the first forwarding table; and

in response to determining the first candidate location is occupied by a first entry stored in the shared forwarding table, determining whether the first entry stored in the shared forwarding table should be evicted from the first candidate location based on the precedence information of the first entry of the first forwarding table and precedence information of the first entry stored in the shared forwarding table.

26. The non-transitory computer-readable storage medium of claim 25, wherein the information of the first forwarding table causes the second network device to perform operations further comprising:

in response to determining the precedence information of the first entry stored in the shared forwarding table indicating it has a priority that is higher than or equal to a priority of the first entry of the first forwarding table, determining a second candidate location in the shared forwarding table for the first entry of the first forwarding table.

27. The non-transitory computer-readable storage medium of claim 25, wherein the information of the first forwarding table causes the second network device to perform operations further comprising:

in response to determining the precedence information of the first entry of the first forwarding table indicating it has a higher priority than the first entry stored in the shared forwarding table;

evicting the first entry stored in the shared forwarding table from the first candidate location,

inserting the first entry of the first forwarding table in the first candidate location, and

determining a second candidate location in the shared forwarding table for the evicted first entry that was stored in the first candidate location.

28. A method in a virtual machine operating in a forwarding plane for maintaining a shared forwarding table based on forwarding table precedence information received from a second network device operating in a control plane, wherein the shared forwarding table implements a plurality of forwarding tables, the method comprising:

receiving information associated with a first forwarding table from the second network device, the information including a plurality of entries and precedence information, the precedence information indicating a priority of the plurality of entries of the first forwarding table; and

for each entry of the first forwarding table, determining whether the entry should be inserted in the shared forwarding table based on the precedence information of the first forwarding table and precedence information contained in the shared forwarding table, wherein the precedence information contained in the shared forwarding table indicates a priority of each corresponding entry stored in the shared forwarding table.

29. The method of claim 28, wherein for each entry of the first forwarding table, determining whether the entry should be inserted in the shared forwarding table comprises:

determining a first candidate location in the shared forwarding table for a first entry of the first forwarding table; and

in response to determining the first candidate location is occupied by a first entry stored in the shared forwarding table, determining whether the first entry stored in the shared forwarding table should be evicted from the first candidate location based on the precedence information of the first entry of the first forwarding table and precedence information of the first entry stored in the shared forwarding table.

30. The method of claim 29, further comprising:

in response to determining the precedence information of the first entry stored in the shared forwarding table indicating it has a priority that is higher than or equal to a priority of the first entry of the first forwarding table, determining a second candidate location in the shared forwarding table for the first entry of the first forwarding table.

31. The method of claim 29, further comprising:

in response to determining the precedence information of the first entry of the first forwarding table indicating it has a higher priority than the first entry stored in the shared forwarding table;

evicting the first entry stored in the shared forwarding table from the first candidate location,

inserting the first entry of the first forwarding table in the first candidate location, and

determining a second candidate location in the shared forwarding table for the evicted first entry that was stored in the first candidate location.

32. The method of claim 30, further comprising:

prior to determining each candidate location, determining whether a number of attempts at determining the candidate location has reached a predetermined threshold; and

in response to determining the number of attempts has reached the predetermined threshold, discarding an entry for which the candidate location is being determined.