Forwarding table performance control in SDN

• US 9,450,866 B2
• Filed: 07/11/2014
• Issued: 09/20/2016
• Est. Priority Date: 07/11/2014
• Status: Active Grant

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Lai, Xiaobing, He, Jiang
• Primary Examiner(s): Nguyen, Hanh N
• Application Number:
  US14/329,037
• Publication Number:
  US 20160014023A1
• Time in Patent Office: 802 Days
• Field of Search: 370/395.21, 370/400, 370/389, 370/392, 370/351, 370/252, 370/386, 370/384, 370/382, 370/410, 370/411, 370/412, 370/390, 370/360
• US Class Current: 1/1
• 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 controlling forwarding table performance include a first network device in a control plane determining a first performance requirement of a first forwarding table in a forwarding plane based on an overall performance requirement of a plurality forwarding tables in the forwarding plane. In one embodiment, in response to determining the first forwarding table in the forwarding plane can be generated to satisfy the first performance requirement, the methods include the first network device sending a first message that includes the first performance requirement to a second network device in the forwarding plane, causing the second network device to generate the first forwarding table that satisfies the first performance requirement. In one embodiment, the exemplary methods include the second network device generating the first forwarding table that satisfies the first performance requirement included in the first message.

Claims

1. A method in a first network device operating in a control plane for distributing performance requirements to a second network device operating in a forwarding plane, the method comprising:

determining a first performance requirement of a first forwarding table in the forwarding plane based on a performance requirement of a plurality forwarding tables in the forwarding plane;

determining whether the first forwarding table in the forwarding plane can be generated to satisfy the first performance requirement; and

in response to determining the first forwarding table in the forwarding plane can be generated to satisfy the first performance requirement, sending a first message that includes the first performance requirement to the second network device, wherein the first performance requirement in the first message indicates a time complexity, the first message causing the second network device to generate the first forwarding table that satisfies the first performance requirement.

2. The method of claim 1, wherein the first forwarding table is a trie tree, and wherein the first message causes the second network device to generate the trie tree with a depth such that the trie tree satisfies the first performance requirement.

3. The method of claim 1, wherein the first forwarding table is a hash table, and wherein the first message causes the second network device to generate the hash table with a load factor such that the hash table satisfies the first performance requirement.

4. The method of claim 1, wherein the first forwarding table is a hash table, and wherein the first message causes the second network device to generate the hash table with a collision resolution algorithm such that the hash table satisfies the first performance requirement.

5. The method of claim 1, further comprising:

in response to determining the first forwarding table is causing the plurality of forwarding tables in the forwarding plane to fail to satisfy the performance requirement of the plurality forwarding tables after the first forwarding table has been generated based on the first performance requirement, determining a second performance requirement of the first forwarding table, wherein the second performance requirement requires a lower time complexity than the first performance requirement; and

sending a second message that includes the second performance requirement to the second network device, the second message causing the second network device to re-generate the first forwarding table to satisfy the second performance requirement.

6. A first network device operating in a control plane for distributing performance requirements to a second network device operating in a forwarding plane, 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;

determine a first performance requirement of a first forwarding table in the forwarding plane based on a performance requirement of a plurality forwarding tables in the forwarding plane,

determine whether the first forwarding table in the forwarding plane can be generated to satisfy the first performance requirement, and

in response to determining the first forwarding table in the forwarding plane can be generated to satisfy the first performance requirement, send a first message that includes the first performance requirement to the second network device, wherein the first performance requirement in the first message indicates a time complexity, the first message causing the second network device to generate the first forwarding table that satisfies the first performance requirement.

7. The first network device of claim 6, wherein the first forwarding table is a trie tree, and wherein the first message causes the second network device to generate the trie tree with a depth such that the trie tree satisfies the first performance requirement.

8. The first network device of claim 6, wherein the first forwarding table is a hash table, and wherein the first message causes the second network device to generate the hash table with a load factor such that the hash table satisfies the first performance requirement.

9. The first network device of claim 6, wherein the first forwarding table is a hash table, and wherein the first message causes the second network device to generate the hash table with a collision resolution algorithm such that the hash table satisfies the first performance requirement.

10. The first network device of claim 6, 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:

in response to determining the first forwarding table is causing the plurality of forwarding tables in the forwarding plane to fail to satisfy the performance requirement of the plurality forwarding tables after the first forwarding table has been generated based on the first performance requirement, determine a second performance requirement of the first forwarding table, wherein the second performance requirement requires a lower time complexity than the first performance requirement; and

send a second message that includes the second performance requirement to the second network device, the second message causing the second network device to re-generate the first forwarding table to satisfy the second performance requirement.

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 control plane for distributing performance requirements to a second network device operating in a forwarding plane, cause the first network device to perform operations comprising:

determining a first performance requirement of a first forwarding table in the forwarding plane based on a performance requirement of a plurality forwarding tables in the forwarding plane;

determining whether the first forwarding table in the forwarding plane can be generated to satisfy the first performance requirement; and

in response to determining the first forwarding table in the forwarding plane can be generated to satisfy the first performance requirement, sending a first message that includes the first performance requirement to the second network device, wherein the first performance requirement in the first message indicates a time complexity, the first message causing the second network device to generate the first forwarding table that satisfies the first performance requirement.

12. The non-transitory computer-readable storage medium of claim 11, wherein the first forwarding table is a trie tree, and wherein the first message causes the second network device to generate the trie tree with a depth such that the trie tree satisfies the first performance requirement.

13. The non-transitory computer-readable storage medium of claim 11, wherein the first forwarding table is a hash table, and wherein the first message causes the second network device to generate the hash table with a load factor such that the hash table satisfies the first performance requirement.

14. The non-transitory computer-readable storage medium of claim 11, wherein the first forwarding table is a hash table, and wherein the first message causes the second network device to generate the hash table with a collision resolution algorithm such that the hash table satisfies the first performance requirement.

15. The non-transitory computer-readable storage medium of claim 11, wherein the computer code, when executed by the processor of the first network device, cause the first network device to perform further operations comprising:

in response to determining the first forwarding table is causing the plurality of forwarding tables in the forwarding plane to fail to satisfy the performance requirement of the plurality forwarding tables after the first forwarding table has been generated based on the first performance requirement, determining a second performance requirement of the first forwarding table, wherein the second performance requirement requires a lower time complexity than the first performance requirement; and

sending a second message that includes the second performance requirement to the second network device, the second message causing the second network device to re-generate the first forwarding table to satisfy the second performance requirement.

16. A method in a first network device operating in a forwarding plane for generating forwarding tables based on performance requirements received from a second network device operating in a control plane, the method comprising:

receiving a first message that includes a first performance requirement of a first forwarding table from the second network device, wherein the first performance requirement in the first message indicates a time complexity; and

generating the first forwarding table that satisfies the first performance requirement included in the first message.

17. The method of claim 16, wherein generating the first forwarding table comprises:

generating a trie tree with a depth such that the trie tree satisfies the first performance requirement included in the first message.

18. The method of claim 16, wherein generating the first forwarding table comprises:

generating a hash table with a load factor such that the hash table satisfies the first performance requirement included in the first message.

19. The method of claim 16, wherein generating the first forwarding table comprises:

generating a hash table with a collision resolution algorithm such that the hash table satisfies the first performance requirement included in the first message.

20. A first network device operating in a forwarding plane for generating forwarding tables based on performance requirements received from a second network device operating in a control plane, 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 a first message that includes a first performance requirement of a first forwarding table from the second network device, wherein the first performance requirement in the first message indicates a time complexity, and

generate the first forwarding table that satisfies the first performance requirement included in the first message.

21. The first network device of claim 20, wherein generating the first forwarding table comprises the first network device to:

generate a trie tree with a depth such that the trie tree satisfies the first performance requirement included in the first message.

22. The first network device of claim 20, wherein generating the first forwarding table comprises the first network device to:

generate a hash table with a load factor such that the hash table satisfies the first performance requirement included in the first message.

23. The first network device of claim 20, wherein generating the first forwarding table comprises the first network device to:

generate a hash table with a collision resolution algorithm such that the hash table satisfies the first performance requirement included in the first message.

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 forwarding plane for generating forwarding tables based on performance requirements received from a second network device operating in a control plane, cause the first network device to perform operations comprising:

receiving a first message that includes a first performance requirement of a first forwarding table from the second network device, wherein the first performance requirement in the first message indicates a time complexity; and

generating the first forwarding table that satisfies the first performance requirement included in the first message.

25. The non-transitory computer-readable storage medium of claim 24, wherein generating the first forwarding table comprises:

generating a trie tree with a depth such that the trie tree satisfies the first performance requirement included in the first message.

26. The non-transitory computer-readable storage medium of claim 24, wherein generating the first forwarding table comprises:

generating a hash table with a load factor such that the hash table satisfies the first performance requirement included in the first message.

27. The non-transitory computer-readable storage medium of claim 24, wherein generating the first forwarding table comprises:

generating a hash table with a collision resolution algorithm such that the hash table satisfies the first performance requirement included in the first message.

28. A method in a virtual machine operating in a control plane for distributing performance requirements to a network device operating in a forwarding plane, the method comprising:

determining a first performance requirement of a first forwarding table in the forwarding plane based on a performance requirement of a plurality forwarding tables in the forwarding plane;

determining whether the first forwarding table in the forwarding plane can be generated to satisfy the first performance requirement; and

in response to determining the first forwarding table in the forwarding plane can be generated to satisfy the first performance requirement, sending a first message that includes the first performance requirement to the network device, wherein the first performance requirement in the first message indicates a time complexity, the first message causing the network device to generate the first forwarding table that satisfies the first performance requirement.

29. The method of claim 28, wherein the first forwarding table is a trie tree, and wherein the first message causes the network device to generate the trie tree with a depth such that the trie tree satisfies the first performance requirement.

30. The method of claim 28, wherein the first forwarding table is a hash table, and wherein the first message causes the network device to generate the hash table with a load factor such that the hash table satisfies the first performance requirement.

31. The method of claim 28, wherein the first forwarding table is a hash table, and wherein the first message causes the network device to generate the hash table with a collision resolution algorithm such that the hash table satisfies the first performance requirement.

32. The method of claim 28, further comprising:

in response to determining the first forwarding table is causing the plurality of forwarding tables in the forwarding plane to fail to satisfy the performance requirement of the plurality forwarding tables after the first forwarding table has been generated based on the first performance requirement, determining a second performance requirement of the first forwarding table, wherein the second performance requirement requires a lower time complexity than the first performance requirement; and

sending a second message that includes the second performance requirement to the network device, the second message causing the network device to re-generate the first forwarding table to satisfy the second performance requirement.