US20220124038A1
Active / In Force
US
⏱️ 15.1 years remaining
Device and method for improved load balancing with limited forwarding rules in software defined networks
Assignee: Huawei Technologies Co Ltd
•
Filing: 2021-12-23
•
Granted: —
•
Expires: 2041-12-23
Abstract
Abstract The present disclosure relates to a device and method for a traffic forwarding network device and proposes a solution for imbalance issues by adapting load balancing to real traffic conditions. The network device tries to solve imbalance issues locally by readjusting the traffic of problematic flows and in case the issues cannot be solved locally, notifies a central network controller to reconfigure the network in order to solve the imbalance issue.
Inventors
- 👤 Jeremie Leguay
- 👤 Paolo Medagliani
- 👤 Jinhua Zhao
- 👤 Jie Zhang
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 07:20
CPC Classifications
H; H04; H04L; H04L47/00; H04L47/10; H04L47/12; H04L47/125; H04L45/00; H04L45/12; H04L45/123; H04L45/24; H04L45/42; H04L47/24; H04L47/2441; H04L47/2483; H04L49/00; H04L49/30; H04L49/50
Claims Analysis
Total Claims: 22
Claim 1
Independent Claim
143 words
1 . A network device for forwarding traffic, the network device comprising: a plurality of output ports; a storage system storing forwarding rules including a first rule for forwarding packets of flows of an aggregated flow according to a given flow distribution to the plurality of output ports; and a circuitry configured to: in a case where a load on a first output port of the plurality of output ports does not match a target load for the first port, exclude at least one of the flows from the aggregated flow and modify the forwarding rules to generate modified forwarding rules by establishing a second rule associating the at least one of the flows of the aggregated flow with a second output port so as to reduce the load on the first output port; and perform routing according to the modified forwarding rules.
Claim 2
Dependent Claim
143 words
1 . A network device for forwarding traffic, the network device comprising: a plurality of output ports; a storage system storing forwarding rules including a first rule for forwarding packets of flows of an aggregated flow according to a given flow distribution to the plurality of output ports; and a circuitry configured to: in a case where a load on a first output port of the plurality of output ports does not match a target load for the first port, exclude at least one of the flows from the aggregated flow and modify the forwarding rules to generate modified forwarding rules by establishing a second rule associating the at least one of the flows of the aggregated flow with a second output port so as to reduce the load on the first output port; and perform routing according to the modified forwarding rules.
Claim 3
Dependent Claim
78 words
2 . The network device according to claim 1 , wherein the circuitry is further configured to: observe the load on the plurality of output ports; in a case where the load on the first output port does not match the target load for the first port, identify the flow with a heaviest load among the flows forwarded to the first output port according to the forwarding rules; and associate the identified flow to the second output port.
Claim 4
Dependent Claim
80 words
3 . The network device according to claim 1 , wherein the circuitry is further configured to: predict future load on the plurality of output ports; in a case where the future load on the first output port does not match the target load for the first port, identify the flow with a heaviest future load among the flows forwarded to the first output port according to the forwarding rules; and associate the identified flow to the second output port.
Claim 5
Dependent Claim
137 words
4 . The network device according to claim 1 , wherein the circuitry is further configured to: in a case where the load or predicted load on the first output port does not match the target load for the first port, identify a set of largest flows forwarded to the first output port, wherein a number of flows in the set of largest flows is chosen such that if one more flow was added to the set of largest flows, then a total data rate of the flows of the set of largest flows would be larger than a difference between the load or predicted load on the first output port and the target load; and assign the flows in the set of largest flows to one or more output ports other than the first output port.
Claim 6
Dependent Claim
83 words
5 . The network device according to claim 1 , wherein the first rule and the second rule are stored in a forwarding table, wherein the forwarding table stores forwarding rules that are either rules redirecting an input flow to a group table or rules associating an input flow with an output port; and wherein each rule that redirects an input flow to the group table points to a set of entries of the group table that implements traffic split over multiple paths.
Claim 7
Dependent Claim
27 words
6 . The networking device according to claim 5 , wherein the forwarding table and the group table are stored in a Ternary Content Access Memory (TCAM).
Claim 8
Dependent Claim
30 words
7 . The network device according to claim 5 , wherein assigning a flow to the second output port causes the second rule to be added to the forwarding table.
Claim 9
Dependent Claim
46 words
8 . The network device according to claim 1 , further comprising: an interface to a controller; wherein the circuitry is configured to receive, over the interface, the forwarding rules and/or a target split ratio specifying for the plurality of output ports, the respective target loads.
Claim 10
Dependent Claim
43 words
9 . The network device according to claim 8 , wherein the circuitry is further configured to transmit a request to the controller, over the interface, requesting the controller to provide the network device with one or more new or updated forwarding rules.
Claim 11
Dependent Claim
81 words
10 . The network device according to claim 9 , wherein the request includes at least one of: a notification of the load on the first output port not matching the target load for the first port; information on a Ternary Content Access Memory (TCAM) utilization and/or a number of rules added locally; information on a deviation from the target load on each port; or a list of flows that the network device associated with another port than the first port.
Claim 12
Dependent Claim
37 words
11 . The network device according to claim 1 , wherein the second rule is established such that a deviation of the load or predicted load from the target load on the first output port is minimized.
Claim 13
Dependent Claim
49 words
12 . The network device according to claim 1 , wherein in the reducing the load on the first output port, a Variable Sized Bin Packing Problem (VSBPP) algorithm is used after associating the at least one of the flows of the aggregated flow with the second output port.
Claim 14
Dependent Claim
27 words
13 . The network device according to claim 1 , wherein the target load per port is determined from the forwarding rules received from a control node.
Claim 15
Dependent Claim
119 words
14 . The network device according to claim 1 , wherein the forwarding rules include a rule for forwarding packets of sub-aggregated flows of the aggregated flow; and in a case where the load or predicted load on the first output port does not match the target load for the first port, the circuitry is further configured to exclude at least one of the sub-aggregated flows from the aggregated flow and modify the forwarding rules by establishing a third rule associating the at least one of the sub-aggregated flows of the aggregated flow with a third output port so as to improve the match between the target load and the load or predicted load on the first output port.
Claim 16
Dependent Claim
31 words
15 . The network device according to claim 1 , wherein one or more group tables define the forwarding rules based on hash results or via Weighted Cost Multi Pathing (WCMP).
Claim 17
Dependent Claim
49 words
16 . The network device according to claim 15 , wherein the hash results are computed over at least one of the header entries, wherein the at least one of the header entries includes an IP source, an IP destination, a Protocol, a source port, or a destination port.
Claim 18
Dependent Claim
82 words
17 . The network device according to claims 2 , wherein the circuitry is further configured to: predict a future load on the plurality of output ports; in a case where the future load on the first output port does not match the target load for the first port, identify the flow with a heaviest future load among the flows forwarded to the first output port according to the flow forwarding rules; and associate the identified flow to the second output port.
Claim 19
Dependent Claim
138 words
18 . The network device according to claim 2 , wherein the circuitry is further configured to: in a case where the load or predicted load on the first output port does not match the target load for the first output port, identify a set of largest flows forwarded to the first output port, wherein a number of flows in the set of largest flows is chosen such that if one more flow was added to the set of largest flows, then a total data rate of the flows of the set of largest flows would be larger than a difference between the load or predicted load on the first output port and the target load; and assign the flows in the set of largest flows to one or more output ports other than the first output port.
Claim 20
Dependent Claim
83 words
19 . The network device according to claim 2 , wherein the first rule and the second rule are stored in a forwarding table, wherein the forwarding table stores forwarding rules that are either rules redirecting an input flow to a group table or rules associating an input flow with an output port; and wherein each rule that redirects an input flow to the group table points to a set of entries of the group table that implements traffic split over multiple paths.
Claim 21
Dependent Claim
139 words
20 . A method for forwarding traffic in a network device that includes a plurality of output ports, the method comprising: storing forwarding rules including a first rule for forwarding packets of flows of an aggregated flow according to a given flow distribution to the plurality of output ports; in a case where a load on a first output port of the plurality of output ports does not match a target load for the first port, excluding at least one of the flows from the aggregated flow and modifying the forwarding rules to generate modified forwarding rules by establishing a second rule associating the at least one of the flows of the aggregated flow with a second output port so as to reduce the load on the first output port; and performing routing according to the modified forwarding rules.
Claim 22
Dependent Claim
139 words
20 . A method for forwarding traffic in a network device that includes a plurality of output ports, the method comprising: storing forwarding rules including a first rule for forwarding packets of flows of an aggregated flow according to a given flow distribution to the plurality of output ports; in a case where a load on a first output port of the plurality of output ports does not match a target load for the first port, excluding at least one of the flows from the aggregated flow and modifying the forwarding rules to generate modified forwarding rules by establishing a second rule associating the at least one of the flows of the aggregated flow with a second output port so as to reduce the load on the first output port; and performing routing according to the modified forwarding rules.
References Cited (Backward Citations)
US20090193105A1
Cited
US20170230065A1
Cited
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.