DEVICE AND METHOD FOR IMPROVED LOAD BALANCING WITH LIMITED FORWARDING RULES IN SOFTWARE DEFINED NETWORKS

[0001] This application is a continuation of International Application No. PCT/EP2019/066821, filed on Jun. 25, 2019, which is incorporated herein by reference in its entirety.

[0002] The present disclosure relates to a method and device for forwarding data ports in a network.

[0003] Software-defined networking (SDN) technology is an approach to network management that enables dynamic, programmatically efficient network configuration in order to improve network performance and monitoring. SDN is meant to address the fact that the static architecture of traditional networks is decentralized and complex while current networks require more flexibility and easy troubleshooting. SDN attempts to centralize network intelligence in one network component by disassociating the forwarding process of network packets (data plane) from the routing process (control plane) while the control plane consists of one or more controllers.

[0004] Load balancing plays a crucial role in improving network utilization. The main idea is to split traffic over multiple paths in order to make a better use of network capacity. Traffic in such networks is commonly organized in flows, which can be defined as a host-to-host communication path, or a socket-to-socket communication identified by a unique combination of source and destination addresses (for instance, Internet Protocol (IP) or media access control (MAC) addresses) and port numbers, together with transport protocols (for example, User Datagram Protocol (UDP) or Transmission Control Protocol (TCP)) or any other identifiers. Commonly, flows are grouped into macroflows (also called traffic aggregates or flow aggregates) and microflows. Macroflows may be defined by their source and destination and can be subdivided into microflows which are defined by finer granulate identifiers, such as particular service or quality of service and/or priority. For example, microflows can be the finest granulate flows possible (i.e., unitary TCP flows) and can not be split further as they would introduce packet reordering issues. Macroflows are composites of microflows and can be split in several subflows that can be routed over different paths. In general any kind of flow or flow aggregate can be called flow.

[0005] Nowadays, network controllers like, for instance, Software-Defined Networking (SDN) controllers or Path Computation Elements (PCE) integrate traffic engineering methods to continuously optimize routing and load balancing. These centralized control plane entities leverage on a global view of the network to decide whether it is necessary to split flows and the most efficient way to do it, given the statistic on network load and traffic flows.

[0006] Embodiments of the present disclosure provide apparatuses and methods for effectively forwarding data in networks like Software-Defined Networks (SDNs). The forwarding network devices can detect load imbalance issues and adapt load balancing to real traffic conditions. Adaptation is made locally in priority and by the network controller when needed. Furthermore, the adaption focuses on problematic flows (the ones at the root of the imbalance issue) so that a limited amount of additional forwarding rules is used.

[0007] The foregoing and other objects are achieved by the subject matter of the independent claims. Further implementation forms are apparent from the dependent claims, the description and the figures.

[0008] According to a first aspect, a network device (100) for forwarding traffic with a plurality of output ports (120-1 to 120-N) is provided, comprising a storage system (101) storing forwarding rules including a first rule for forwarding packets of flows of an aggregated flow according to a given flow distribution to the output ports and a circuitry (110) configured to, in a case where the load on a first output port (120-N) does not match a target load for the first port, exclude at least one of the flows from the aggregated flow and modify said stored forwarding rules by establishing a second rule associating the at least one of the flows of the aggregated flow with a second output port (120-1) so as to improve the match between the target load and the load on the first output port, and perform routing according to the stored forwarding rules. A network device according to this aspect can change the routing of flows locally without need for a global reconfiguration of the network. This may, for instance, allow a faster reaction to load imbalance issues.

[0009] According to a second aspect, the network device (500) according to the first aspect is provided, wherein the circuitry (510) is configured to observe the load on the output ports (520-1 to 520-N), and in a case where the load on the first output port (520-N) does not match the target load for the first port (520-N), identify the flow (550-1) with the heaviest load among the flows (550-1 to 550-N) forwarded to the first output port (520-N) according to the flow forwarding rules and associate said identified flow (550-1) to the second output port (520-1). A network device according to this aspect can detect load imbalance issues on the output ports and resolve the load imbalance issues locally without need for a global reconfiguration of the network. This may, for instance, allow a faster load balancing.

[0010] According to a third aspect, the network device (500) according to the first or second aspect is provided, wherein the circuitry is configured to predict the future load on the output ports (520-1 to 520-N), and in a case where the future load on the first output port (520-N) does not match the target load for the first port (520-N), identify the flow (550-1) with the heaviest future load among the flows (550-1 to 550-N) forwarded to the first output port (520-N) according to the flow forwarding rules, and associate said identified flow (550-1) to the second output port (520-1). A network device according to this aspect may allow local load balancing anticipating the expected future load. In case a flow is expected to be very large in future, it may be forwarded such that no load balancing issue arises on the corresponding output port.

[0011] According to a fourth aspect, the network device (500) according to any of the first to third aspect is provided wherein the circuitry (510) is further configured to, in a case where the load or predicted load (701) on the first output port (750) does not match the target load (702) for the first port, identify a set (720) of the largest flows forwarded to the first output port, wherein the number of flows in the set (720) is chosen such that if one more flow was added to the set (720) of flows, the total data rate of the flows of the set of flows would be larger than the difference between the load or predicted load (701) and the target load (702), and assign said identified flows to one or more output ports other than the first output port (750). A network device according to this aspect may allow to effectively resolve load balancing issues locally. As only the largest flows are considered to be forwarded to different output ports, this may make it possible to reconfigure the network locally with a small number of new rules (which may make efficient use of the local storage for forwarding rules) and with a small local computational demand.

[0012] According to a fifth aspect, the network device (100) according to any of the first to fourth aspect is provided, wherein the first rule and the second rule are stored in a forwarding table (801), wherein the forwarding table (801) stores forwarding rules which are either rules redirecting an input flow to the group table (821) or rules (822) associating an input flow with an output port, and each redirecting forwarding rule (821) is defined by a group table pointed to by the entry of the redirecting forwarding rule (821) in the forwarding table. A network device according to this aspect may allow to effectively resolve load balancing issues locally. For traffic that does not cause load balance issues on the output ports, group tables may be used, which may provide an efficient way of forwarding large amounts of data (and potentially well distributed over the output ports) with only a limited use of rules. For large and/or problematic flows, rules associating the flows with output ports may be used. This may allow to provide an effective forwarding while fast and locally resolving load imbalance issues.

[0013] According to a sixth aspect, a networking device (100) according to the fifth aspect is provided, wherein the forwarding table (801) and the group table are stored in a Ternary Content Access Memory (TCAM). A network device according to this aspect may provide a fast and effective forwarding potentially making a fast execution of the described functionalities possible.

[0014] According to a seventh aspect, a network device (100) according to the fifth or sixth aspect is provided, wherein in the assigning of a flow to the second output port, the second forwarding rule is added to the forwarding table (801). A network device according to this aspect may efficiently resolve load balance issues by using tailored rules associating a flow with an output port.

[0015] According to an eighth aspect, a network device (100) according to any of the first to seventh aspect is provided comprising an interface (150) to a controller wherein the circuitry (110) is configured to receive, over said interface, a target split ratio specifying for the output ports, the respective target loads; and/or said forwarding rules. A network device according to this aspect may allow to effectively forward traffic in accordance with a central controller while potentially being able to efficiently resolve imbalance issues locally.

[0016] According to a ninth aspect, a network device (100) according to the eighth aspect is provided wherein the circuitry (110) is configured to transmit a request to the controller over said interface, and request the controller to provide the network device with one or more new or updated forwarding rules. A network device according to this aspect may make it possible to resolve load balance issues in cases where the issue cannot be solved locally. The controller might reconfigure the network globally in such a case. The network device might only send such a request to the network controller if the load balance issue cannot be solved locally. A local solution may be faster and more efficient, while the global solution night be able to solve more severe load imbalance issues.

[0017] According to a tenth aspect, a network device (100) according to the ninth aspect is provided, wherein the request contains 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 the TCAM utilization and/or the number of rules added locally, information on the deviation from the target load on each port, a list of flows the network device associated with another port than the first port. A network device according to this aspect may contribute to the network controller more efficiently finding a potentially more efficient solution to a load imbalance issue.

[0018] According to an eleventh aspect, a network device (100) according to any of the first to tenth aspect is provided wherein the modification of the forwarding rules (820) is chosen such that the deviation of the load or predicted load from the target load on the output port is minimized.

[0019] According to a twelfth aspect, a network device according to any of the first to eleventh aspect is provided wherein in the improving of the match between the load or predicted load and the target load on the output ports a Variable Sized Bin Packing Problem, VSBPP, algorithm is used after removing the flow(s) identified as having the highest load. A network device according to this aspect may more efficiently find a solution for a load imbalance issue.

[0020] According to a thirteenth aspect, a network device (100) according to any of the first to twelfth aspect is provided wherein the target load per port (120-1 to 120-N) is determined from the forwarding rules (820) received from a control node. A network device according to this aspect may find the target load for the output ports without additional communication.

[0021] According to a fourteenth aspect, a network device (100) according to any of the first to thirteenth aspect is provided wherein the stored forwarding rules (820) include a rule for forwarding packets of sub-aggregated flows of an aggregated flow, and in a case where the load or predicted load on a first output port (120-N) does not match a target load for the first port (120-N), exclude at least one of the sub-aggregated flows from the aggregated flow and modify said stored forwarding rules (820) by establishing a second rule associating the at least one of the sub-aggregated flows of the aggregated flow with a second output port (120-1) so as to improve the match between the target load and the load or predicted load on the first output port (120-N). A network device according to this aspect can efficiently change the splitting of aggregated flows in case of a load imbalance issue.

[0022] According to a fifteenth aspect, a network device (100) according to any of the fifth to fourteenth aspect is provided wherein the one or more group tables define forwarding based on hash results or via Weighted Cost Multi Pathing, WCMP. A network device according to this aspect can efficiently distribute incoming traffic to its output ports according to the target load on the respective output port.

[0023] According to a sixteenth aspect, a network device (100) according to the fifteenth aspect is provided wherein the hash is computed over at least one of the header (900) entries IP source (911), IP destination (912), Protocol (913), source port (914), destination port (915) and/or the forwarding rules (822) associating an input flow with an output port identify the input flow by at least one of said header (900) entries. A network device according to this aspect can efficiently distribute traffic to its output ports. Packets pertaining to the same microflow can be guaranteed to be forwarded to the same output port as long as the routing is not reconfigured. Aggregates of flows may be identified by only a few header entries and forwarded as a whole or sub-aggregates or microflows belonging to aggregate flows may be identified based on more header entries which may lead to a split of the initial aggregate flow.

[0024] According to a seventeenth aspect, a method is provided (1200) for forwarding traffic in a network device with a plurality of output ports, 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 output ports, in a case where the load on a first output port does not match a target load for the first port, excluding at least one of the flows from the aggregated flow and modifying said stored 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 improve the match between the target load and the load on the first output port, and performing routing according to the stored forwarding rules.

[0025] The method may further comprise observing the load on the output ports, and in a case where the load on the first output port does not match the target load for the first port, identifying the flow with the heaviest load among the flows forwarded to the first output port according to the flow forwarding rules, and associating said identified flow to the second output port.

[0026] According to an embodiment, the method may further comprise predicting the future load on the output ports, and in a case where the future load on the first output port does not match the target load for the first port, identifying the flow with the heaviest future load among the flows forwarded to the first output port according to the flow forwarding rules, and associating said identified flow to the second output port.

[0027] In an exemplary implementation, the method may further be configured to, in a case where the load or predicted load (701) on the first output port (750) does not match the target load (702) for the first port, identify a set (720) of the largest flows forwarded to the first output port, wherein the number of flows in the set (720) is chosen such that if one more flow was added to the set (720) of flows, the total data rate of the flows of the set of flows would be larger than the difference between the load or predicted load (701) and the target load (702), assign said identified flows to one or more output ports other than the first output port (750).

[0028] Moreover, the method may include storing the first rule and the second rule in a forwarding table (801), wherein the forwarding table (801) stores forwarding rules which are either rules redirecting an input flow to the group table (821) or rules (822) associating an input flow with an output port, and each redirecting forwarding rule (821) is defined by a group table pointed to by the entry of the redirecting forwarding rule (821) in the forwarding table.

[0029] According to an aspect, the forwarding table (801) and the group table are stored in a Ternary Content Access Memory (TCAM).

[0030] According to an embodiment of the method, the assigning of a flow to the second output port, the second forwarding rule is added to the forwarding table (801).

[0031] In an exemplary implementation, the method may further be configured to use an interface to a controller wherein the method is configured to receive, over said interface, a target split ratio specifying for the output ports, the respective target loads; and/or said forwarding rules.

[0032] In some embodiments, the method may further include transmitting a request to the controller, over said interface, requesting the controller to provide the network device with one or more new or updated forwarding rules.

[0033] Moreover, the request may contain 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 the TCAM utilization and/or the number of rules added locally, information on the deviation from the target load on each port, and a list of flows the network device associated with another port than the first port.

[0034] According to an aspect, a method as described above is provided wherein the modification of the forwarding rules (820) is chosen such that the deviation of the load or predicted load from the target load on the output port is minimized.

[0035] The method may further comprise using a Variable Sized Bin Packing Problem, VSBPP, algorithm in the improving of the match between the load or predicted load and the target load on the output ports after removing the flow(s) identified as having the highest load.

[0036] According to an embodiment, the method may further determine the target load per port (120-1 to 120-N) is from the forwarding rules (820) received from a control node.

[0037] According to an embodiment of the method, the stored forwarding rules (820) include a rule for forwarding packets of sub-aggregated flows of an aggregated flow, and in a case where the load or predicted load on a first output port (120-N) does not match a target load for the first port (120-N), at least one of the sub-aggregated flows is excluded from the aggregated flow and said stored forwarding rules (820) are modified by establishing a second rule associating the at least one of the sub-aggregated flows of the aggregated flow with a second output port (120-1) so as to improve the match between the target load and the load or predicted load on the first output port (120-N).

[0038] In an exemplary implementation, the one or more group tables define forwarding based on hash results or via Weighted Cost Multi Pathing, WCMP.

[0039] According to an embodiment of the method the hash is computed over at least one of the header (900) entries IP source (911), IP destination (912), Protocol (913), source port (914), destination port (915) and/or the forwarding rules (822) associating an input flow with an output port identify the input flow by at least one of said header (900) entries.

[0040] The methods mentioned above may be implemented as a software code including the code instructions, which implement the above-mentioned method steps. The software may be stored in a computer readable medium. The medium may be a processor memory, any storage medium or the like. The software may be used in devices such as control device or switch referred to above.

[0041] Details of one or more embodiments are set forth in the accompanying drawings and the description below. Other features, objects, and advantages will be apparent from the description, drawings, and claims.

[0057] In the following description, reference is made to the accompanying figures, which form part of the disclosure, and which show, by way of illustration, specific aspects of embodiments of the disclosure or specific aspects in which embodiments of the present disclosure may be used. It is understood that embodiments of the disclosure may be used in other aspects and comprise structural or logical changes not depicted in the figures. The following detailed description, therefore, is not to be taken in a limiting sense, and the scope of the present disclosure is defined by the appended claims.

[0058] For instance, it is understood that a disclosure in connection with a described method may also hold true for a corresponding device or system configured to perform the method and vice versa. For example, if one or a plurality of specific method steps are described, a corresponding device may include one or a plurality of units, e.g. functional units, to perform the described one or plurality of method steps (e.g., one unit performing the one or plurality of steps, or a plurality of units each performing one or more of the plurality of steps), even if such one or more units are not explicitly described or illustrated in the figures. On the other hand, for example, if a specific apparatus is described based on one or a plurality of units, e.g. functional units, a corresponding method may include one step to perform the functionality of the one or plurality of units (e.g., one step performing the functionality of the one or plurality of units, or a plurality of steps each performing the functionality of one or more of the plurality of units), even if such one or plurality of steps are not explicitly described or illustrated in the figures. Further, it is understood that the features of the various exemplary embodiments and/or aspects described herein may be combined with each other, unless specifically noted otherwise.

[0059] Typically, load balancing (or flow splitting) is implemented inside network devices such as switches and routers using two techniques. Examples for load balancing are shown in FIGS. 1 to 3.

[0060] FIG. 1 shows an SDN/PCE Controller capable of controlling a switch, for instance, by configuring a forwarding table and/or a group table used (and possibly also stored) by the switch. In particular, the switch receives a packet with a certain destination address and decodes based on the forwarding table and the group table to which next hop the packet is to be forwarded. The forwarding table here includes two columns, the column labeled as “Match” and including IP address (in general a possible destination address) and the column labeled “Action” and defining the forwarding rule/policy. For example, packets with destination address 56.78.91.2 are always forwarded to the next hop with the address 56.78.91.2. On the other hand, the packets with the destination address 56.78.91.8 are further split over several output ports towards different next-hop addresses shown in the group table (columns “Next-Hop”). The split ratio may be also specified by the SDN / PCE controller or another controlling entity or unit. The splitting is preformed based on a hash function calculated over some parts of the packet (header). The name “group table” refers to the fact that different tables may be used for different destination addresses.

[0061] In particular, hash-based splitting where a hash is calculated over significant fields of packet headers (like source and/or destination address and/or port and/or transport protocol) and used to select the outgoing paths and Weighted Cost Multi Pathing (WCMP) where load balancing weights (for instance corresponding to, “split ratios” in FIG. 1 and FIG. 3 and “target ratio” in FIG. 2) are used to make sure that the number of flows on the outgoing paths meets a certain ratio. In both cases, once a decision is taken for a flow, all packets from a flow must follow the same decision (i.e., they follow the same path). However, in practice, the size of flows cannot be known in advance and the distribution of flow sizes is not uniform. Here, flow size can be understood as the load a flow imposes on the network (for instance on an input or output port of a forwarding device in a network).

[0062] FIG. 2 shows an example for the actual ratio of the load on three output ports in a forwarding network device and the target ratio. The network devices in this example are 3GPP network nodes Cell Site Gateway (CSG), RNC Site Gateway (RSG) and two Aggregation Site Gateways (ASG). As the number of flows per port is distributed according to the target ratio, the actual load can differ significantly if, for instance, one or more flows are significantly larger (have a larger (heavier) load than most other flows). These two observations are at the source of problematic imbalance issues that load balancers have to solve.

[0063] According to the type of traffic repartition over multiple outgoing ports, it is possible to distinguish between even or uneven flow splitting. The first type is the most popular one and also known as Equal Cost Multi-Paths (ECMP). The second type allows a better utilization of network resources but is hard to implement. It is also known as Unequal Cost Multi-Paths (UCMP). In both cases, the implementation inside forwarding network devices leverages on a Ternary Content Access Memory (TCAM) for efficient packet processing. The TCAM memory inside the switches is further divided in two tables: the forwarding and the group table, as shown in FIG. 1 and FIG. 3. FIG. 3 shows more generally than FIG. 1 that not only IP addresses, but in general any demand such as D1 and D2 may be matched in the forwarding table. The demand may correspond to identification of destination in any form such as destination name or address, or a flow number or identification, or the like.

[0064] For each incoming packet, the switch looks for the corresponding match in the forwarding table (for instance, by comparing any or all of the header entries to the corresponding entries in the forwarding table), which specifies if the packet can be directly forwarded or if a specific split must be applied. In this latter case, the switch looks for the corresponding entry of the group table where, according to the output of the value of a hash computed over significant fields of packets (i.e., fields of the packet header), the next hop is determined. The configuration of entries, also called buckets, in the group table defines the split ratio, i.e., the load balancing, used for a specific flow aggregate. Given the global view of the network, the PCE controller can instruct each switch with the best TCAM configuration. This is illustrated in FIG. 3 which shows that not only node 0 has a forwarding table, but also e.g. node 4 which is on the way between the source an destination of D1. At each node, the aggregated flow D1 or its parts may be split or aggregated again (e.g., by forwarding two sub-flows of the aggregated flow to the same next hop).

[0065] As traffic evolves during time, the flow distribution observed locally within a node may differ from the target one computed by the controller. For this reason, corrective actions are needed to accurately track the ongoing traffic distribution and adjust load balancing to better handle problematic flows.

[0066] In the state of the art two classes of solutions have been proposed to the problem: 1) elephant flow scheduling and 2) utilization-aware load balancing. In elephant scheduling, a default routing policy is used for all the flows (ECMP for instance). On top of this, the network controller keeps track of a list of the largest flows, also called elephant flows, top-N flows or heavy hitters, with the help of a monitoring system that uses classical IPFIX packet or flow sampling techniques. Once the list of the largest flows is established in the centralized monitoring system, the controller can decide to take specific routing decisions for some of them in case of imbalance issues. As the identification of heavy hitters (problem source) and the routing decisions (corrective actions) are taken in the controller, this solution is quite slow to react to short term traffic variations. In utilization-aware load balancing, the main idea is to use a routing policy for every single flow and adjust these routing policies to the actual flow size. Techniques are used to migrate flows from one path to another without packet losses and re-ordering issues. For instance, CONGA, tracks the congestion of outgoing paths and selects the uplink port that minimizes in-network congestion. Decisions are taken at flowlet level (64K max per device) wherein flows are split into flowlets whenever there is a long-enough gap in the sequence of packets in a given flow. LocalFlow tracks the rate of flows and periodically solves a bin packing problem to split them. As both methods take custom decisions for every flow, many forwarding rules need to be managed by the devices.

[0067] Embodiments of the present disclosure can provide the right trade-off between the two approaches by relying on a default routing policies computed centrally and real-time adaptations locally in case of imbalance issues.

[0068] In the following, embodiments of a network device 100 according to the present disclosure that is capable of improving load balancing are described based on FIGS. 4 to 10.

[0069] FIGS. 4A and 4B show a network device 100. The network device 100 stores one or more forwarding rules in a storage 101. In particular, the network device may be a network switch or router or gateway. Incoming data are forwarded to the various output ports 120-1 to 120-N according to the one or more forwarding rules. The incoming data 151 may be packets pertaining to flows, and the flows may be bundled to flow aggregates.

[0070] The flows may be distributed by distribution unit 130 to the output ports such that data (packets) pertaining to the same microflow are forwarded to the same output port. Data pertaining to the same aggregate flow may be forwarded to the same or distributed to different output ports. The number of flows or flow aggregates forwarded to each output port may be defined by the forwarding rules. The flow distribution to two ports 120-1 and 120-N is illustrated exemplarily in FIG. 4A, wherein the load 152 is larger than the load 153. The network device 100 may further be configured to measure the load on each output port (including loads 152 and 153) by means of a load monitoring unit 140. In an embodiment, this may be achieved by measuring the bandwidth utilization on the corresponding one or more output ports 120-1 to 120-N.

[0071] In this example, if the measured load on an output port 120-N does not match the desired load on that output port a new rule may be established by the network device. As shown in FIG. 4A, flow 152 is heavier than flow 153. Accordingly, the load monitoring unit 140 detects this mismatch and determines the new forwarding rule, which improves the load balance. The result of the load balancing is illustrates schematically in FIG. 4B. The input data 151 is split into two new flows 152n and 153n which are more balanced. It is noted that in this example, the target balancing was equal distribution of the input data 151 to ports 120-1 and 120-N. However, in general, the desired load balancing ratio is not limited to uniform distribution and a split ratio may be configured for each flow, and/or for each port.

[0072] The new rule may be stored in the storage 101. According to the new rule, one or more of the flows that were previously forwarded to port 120-N is or are now redistributed to another output port, here 120-1 or possibly also other ports between the ports 120-1 and 120-N. This may result in a distribution of the load on the output ports that is closer to the corresponding target loads. The target loads may be the same for all output ports or they may be different and defined for each output port individually.

[0073] In other words, the network device100 for forwarding traffic with a plurality of output ports 120-1 to 120-N generally comprises a storage system 101 storing forwarding rules including a first rule for forwarding packets of flows of an aggregated flow 151 according to a given flow distribution to the output ports 120-1 to 120-N. The network device further comprises a circuitry (including flow distribution circuitry 130 and load monitoring circuitry 140) configured to, in a case where the load (which might be measured, for instance in terms of bandwidth utilization) on a first output port 120-N does not match a target load for the first output port, exclude at least one of the flows from the aggregated flow and modify said stored 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 improve the match between the target load and the load on the first output port; and perform routing according to the stored forwarding rules.

[0074] In an implementation according to the present disclosure, in the case of a significant imbalance between the measured load and target load, the “bucket monitoring” module (load monitoring) 140 in the switch 100 can decide to install probes to analyze the outgoing traffic in more detail. To identify the most problematic flows, also called heavy hitters or elephant flows, the forwarding network device can use techniques such as packet or flow sampling, or advanced techniques such as the sketches. The significance of imbalance may be determined, for instance, by the deviation or difference or other disparity measure between the desired and current load.

[0075] Once the potential elephant flows have been identified, the switch tries to locally adjust routing (bucket configuration may be changed in case of hash-based splitting) for them in order to solve the imbalance issue. This may be done by associating the flow (for instance, 550-M) with the largest load, which is associated with the output port (for instance, 520-N) in which the measured load is significantly larger than the target load, to a different output port, as illustrated in FIGS. 5A and 5B.

[0076] FIGS. 5A and 5B differ in particular from FIGS. 4A and 4B respectively in that they illustrate the input aggregated flow as including a plurality of flows or flow aggregates 550-1 to 550-M which are distributed by the network device to the output ports 520-1 to 520-N. FIG. 5A shows an example in which the two heaviest incoming flows (550-1 and 550-2) are forwarded to the same output port 520-N. In this example, the input flows are ordered from the lightest flow 550-M to the heaviest flow 550-1 from top to bottom. It is noted that not all flows are shown in this figure and that each incoming flow can be forwarded to any output port. It is further noted that more flows can be forwarded to ports 520-N and 520-1. In this example, it is shown that at least two heavy flows are forwarded to port 520-N. In this example, the target load may be the same for each port or, without restriction, the target load for port 520-N may be much smaller than the actual load caused by the heavy flows 550-1 and 550-2. For port 520-1 on the other hand, the actual load may be smaller than the target load. When the network device has detected the discrepancy between the actual and the target load on an output port (in this example, port 520-N), it analyzes the load on the corresponding port and identifies the heaviest flow. In general, the network device may identify not only the heaviest flow, but a set of the heaviest flows. In this example, the network device identifies 550-1 as the flow with the heaviest load and adds a rule to the storage 530 that causes flow 550-1 to be forwarded to a different port (520-1 in this example). It is noted that, in the example shown in FIGS. 5A-5B, the loads on output ports 520-N and 520-1 are assimilated by the newly added rule. However, the target loads on the output ports can be different. In both cases, the new rule is chosen such that the actual loads on the output ports are assimilated to the target loads.

[0077] In other words, in a network device according to this implementation, the circuitry is configured to observe the load on the output ports 520-1 to 520-N and, in a case where the load on the first output port 520-N does not match the target load for the first port 520-N, identify the flow 550-1 with the heaviest load among the flows forwarded to the first output port according to the flow forwarding rules; and associate said identified flow 550-1 to the second output port 520-1.

[0078] In another Implementation according to the present disclosure, the identification of the most problematic flows may use predictive models to forecast the size of flows. Correspondingly, the network device may predict the future size of the flows and compare the future predicted load with the target load. Further, the network device may associate the flow with the largest future load on an output port where the present or future load deviates significantly from the target load with a different output port.

[0079] The prediction may be performed in any manner. For example, extrapolation of the load measured in the past (over one or more time instances) may be applied. However, in some implementations, the prediction may also be performed using the load measured currently and/or previously at the neighboring routers/switches (network nodes) or generally any routers/switches in the network.

[0080] In other words, a network device according to this implementation may be configured to predict the future load on the output ports and, 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 the heaviest future load among the flows forwarded to the first output port according to the flow forwarding rules and associate said identified flow to the second output port.

[0081] However, the present disclosure is not limited to changing the forwarding of one flow. In cases where several heavy flows are forwarded to the same output port while the load on other ports is smaller than the target load, it might be necessary to redistribute several heavy flows. These flows may be associated with one other output port or several other output ports.

[0082] FIG. 7 shows an example of a set of flows 710 initially forwarded to one output port 750 with the load or predicted load 701. In this example, the target load 702 is significantly smaller than the actual load 701. In an implementation according to the present disclosure, a set of the flows 720 with the largest loads on the output port 750 on which the load 701 is significantly larger than the target load 702 (also called target throughput in the following) may be identified. The set of flows with the largest flows may be chosen in the following way: Knowing the real throughput T_r^p (701 in this example) on outgoing paths p (here, 750) and the expected target throughput T_e^p (here 702), the path is determined where the deviation T_r^p−T_e^p is the highest. If T_r^p−T_e^p>Δ on this path, find the subset of problematic flows out of Top-N flows (here 720) F₁> . . . >F_NFind i such that arg max Σ₁^j=iF_j<T_r^p−T_e^p.

[0083] In other words, the i largest flows are chosen as the subset 720 of the largest (problematic) flows wherein i is chosen such that if the remaining largest flow (from the set 730 of flows that were not added to the set of i problematic flows) would have been added to the subset of i problematic flows, the load on the corresponding output port would be smaller than the target load. Then, the subset of the i problematic flows may be distributed to other output ports.

[0084] Each of the flows of the subset of problematic flows may be forwarded to different output ports or all flows of the set of problematic flows may be sent to the same output port.

[0085] In other words, the network device may be configured to, in a case where the measured or predicted load on the first output port does not match the target load for the first port, identify a set of the largest flows forwarded to the first output port, wherein the number of flows in the set is chosen such that if one more flow was added to the set of flows, the total data rate of the flows of the set of flows would be larger than the difference between the measured or predicted load and the target load and to assign said identified flows to one or more output ports other than the first output port.

[0086] In another implementation, the flows may be redistributed such that the deviation of the load or predicted future load on all output ports is minimized by analyzing the size of a set of flows including more than the problematic heaviest flows and, for instance, solving a bin packing problem with more flows. However, this approach may need more computational power.

[0087] In an implementation according to the present disclosure, the forwarding rules are stored in a forwarding table 801. An example for such a table is shown in FIG. 8. According to this implementation, a rule (for instance 822) can either directly associate a flow with an output port or define (for instance 821) a group table for one or more flows or flow aggregates, which defines the forwarding for the corresponding flows and/or flow aggregates or sub-aggregates. The decision which packets to forward to which output port (and thus, which flow) may be based on the result of a hash function, applied to significant fields of the packet headers. In other embodiments, the decision may be based on any rule that associates packets belonging to the same flow to the same output port.

[0088] A forwarding table can contain one or more rules of one of the types described above or rules of both types. In the example shown in FIG. 8, the group table points to all shown output ports, however a group table according to the present disclosure may also define forwarding to any subset of the available output ports.

[0089] An exemplary packet header is shown in FIG. 9. Significant fields here may include, for instance any or all of IP source 911, IP destination 912, protocol 913, source port 914 and/or destination port 915. However, the forwarding can be applied to any other kinds of protocols with different packet headers and thus different fields.

[0090] In the network device according to the implementation described above, the first rule and the second rule are stored in a forwarding table 801, wherein the forwarding table 801 stores forwarding rules which are either redirecting an input flow to a group table or rules 822 associating an input flow with an output port, and each hash-based rule is defined by a group table pointed to by the entry of the forwarding rule 821 in the forwarding table.

[0091] In one embodiment, the group table may define to which port to forward the packets based on the result of a hash function. This hash function may calculate a hash from a predefined portion of the packet header. The predefined portion may be any fraction of or the whole packet header.

[0092] In another embodiment the group table may define to which port to forward the packets via Weighted Cost Multi Pathing (WCMP). The implementation of the WCMP may but does not need to employ hash calculation. In general, the group table may define which packet to forward to which output port depending on a predefined portion of the packet header.

[0093] According to an embodiment, the forwarding rules are stored in a Ternary Content Access Memory. In other words, in an implementation according to this embodiment, the forwarding table and the group table are stored in a Ternary Content Access Memory (TCAM) which may permit a fast execution of the forwarding according to the stored forwarding rules.

[0094] A network device according to the present disclosure can improve the efficiency of using the TCAM. Group tables can be used where rules that quasi statistically distribute flows over the output ports are sufficient, and problematic flows can be identified and individually forwarded for example if their load deviates significantly from the average load of all flows.

[0095] This can for instance be important if flows are distributed to the output ports by assigning the number of flows quasi statistically to each output port according to the ratio of the target loads on the output ports. If all flows had the same size, or if the number of flows assigned to each output port was large enough to suppress statistical fluctuations in the size of the flows, the actual load on each output port would match the target flow. However, in reality the load of some flows is significantly larger than the average flow load.

[0096] In such a case, a network device according to the present disclosure can extract problematic flows and forward them separately. In doing so, it can resolve congestions without having to wait for instructions from another network entity and without having to establish an individual rule for every flow.

[0097] In an implementation according to the present disclosure, when a new rule is established locally, the forwarding network device adds an individual rule to the forwarding table. This individual rule specifies directly to which output port to forward the corresponding flow. In other words, in in the assigning of a flow to the second output port, the second forwarding rule is added to the forwarding table. On the other hand, a forwarding network device could also add or change group tables.

[0098] In an implementation according to the present disclosure, the network device comprises an interface 150 to a network controller. The network controller may be a central controller like an SDN controller or PCE that can gather information on the network and communicate with all or some of the network devices forwarding the network traffic.

[0099] Over the interface 150, the network device can, for instance, receive forwarding rules from the network controller. These can be individual rules for single flows (rules associating a flow directly with an output port) or rules based on group tables or both. Furthermore, the network device can receive target split ratios for the incoming flows between the output ports or the corresponding target loads. In addition, the network device could calculate the target load on each output port from the target split ratios or vice versa.

[0100] For instance, if the central controller is aware of flows with a heavy load, it can set individual forwarding rules for these heavy flows in the forwarding network devices in order to avoid congestions. Additionally the central controller can provide an initial set of rules comprising target split ratios and update the rules if the network is modified. The forwarding network device might modify the forwarding rules (for instance, the rules defining an individual output port for a flow) locally if there is a significant deviation from the target split ratios.

[0101] In other words, a networking device according to the implementation described above, comprises an interface 150 to a controller (e.g. SDN controller or PCE) and its circuitry is configured to receive, over said interface, a target split ratio, specifying for the output ports the respective target loads, and/or said forwarding rules.

[0102] The interface can also be used, for instance, to exchange further information like information on sizes of flows or future sizes of flows, which can be used by a network device to find new optimal forwarding rules locally or for the central controller to forward to other network devices.

[0103] According to an embodiment, the network device may send a request to the controller via the interface 150. This can be useful, for instance, in a case where the network device cannot resolve a significant deviation from the target load on the output ports by adding rules to or changing the rules in its own forwarding table. In particular, in case the deviation cannot be solved locally, the network device can ask the controller for a global reconfiguration of load balancing.

[0104] FIG. 6 shows the architecture of a switch (may be any forwarding network device) and how the different components interact in order to solve the problem of accurate load balancing. The load balancing can be logically divided in two parts: the former is implemented locally inside the switch, while the latter requires the interaction between the switch and the centralized controller for the sake of a global re-optimization of the network.

[0105] Initially, the network device may receive a set of rules from the central controller. Alternatively, the network device might choose target splitting ratios itself (for instance equal weights on all output ports).

[0106] At first, the switch node (forwarding network device) monitors traffic on outgoing ports in order to detect if some flow aggregates are deviating from the original target rate assigned by the centralized controller. In the case of significant imbalance, the “bucket monitoring” module in the switch can decide to install probes to analyze the outgoing traffic more in detail. To identify the most problematic flows, also called heavy hitters, the switch can use standard techniques such as packet or flow sampling, or advanced techniques such as the sketches in the “heavy hitter detection module”.

[0107] Note that the identification of the most problematic flows may use predictive models to forecast the size of flows. Once the potential elephant flows have been identified, the switch tries to locally adjust routing (for instance bucket configuration in case of hash-based splitting) for them in order to solve the imbalance issue. If the problem cannot be fixed by the switch, it can ask the controller for help. Once the controller has decided a new routing configuration, the switch receives new target split ratios (or new forwarding rules) from the controller and locally updates load balancing.

[0108] Compared to other existing centralized approaches, the proposed idea can allow to quickly react to traffic changes, significantly reducing the time required to adapt to varying traffic conditions.

[0109] Compared to distributed approaches, the proposed idea can leverage on the assistance of the centralized controller, in order to compensate significant traffic unbalance that could not be fixed by acting locally only.

[0110] The main benefits provided are that the adjustment can be performed locally in most cases while keeping the memory usage (a Ternary Content Access Memory (TCAM) may be used) very low: a few specific rules are used for problematic flows.

[0111] In other words, a forwarding network device according to the embodiment described above is configured to transmit a request to the controller, over said interface, requesting the controller to provide the network device with one or more new or updated forwarding rules.

[0112] In an implementation according to the present disclosure, the help message triggered by the network device to ask for support by the centralized controller may be composed of two parts: a first mandatory part to notify the controller on the current imbalance and on the resource status and a second optional part which contains more information about the issue that caused the request from the switch to the controller. The mandatory part may include a notification of the imbalance issue and the Current TCAM utilization in the switch.

[0113] The optional part may comprise any of the deviation from the target load on each output port, the deviation from the target on each port (in some embodiments this may correspond to the target load on each tunnel (which may be an MPLS (Multiprotocol Label Switching) tunnel)) and a list of problematic heavy-hitters (flow-level information).

[0114] This information can be useful for the central network controller for finding better solutions for network settings. For instance, knowing the TCAM utilization of the network device can be used to avoid adding too many individual rules to the corresponding network device.

[0115] In an embodiment, the modification of the forwarding rules is chosen such that the deviation of the measured or predicted load from the target load on the output ports is minimized.

[0116] An example of the computation of a new splitting distribution through the centralized algorithm shown in FIG. 11.

[0117] In a first step (1101) link capacities are scaled down by a factor α. This prevents a 100% link utilization and reserves space for rounding. Different values of α can be tested in parallel.

[0118] In a second step (1102) the relaxed multi-commodity flow is relaxed (i.e., using column generation). Bucket constraints are removed, integer variables are relaxed and the LP (Linear Programming) is solved.

[0119] In a third step (1103) a proportional and fair amount of bucket budget is allocated to each demand (according to the size) at each source node.

[0120] In a fourth step (1104) the fractional solution is round up randomly to find a feasible bucket configuration which minimizes the error.

[0121] In a fifth step (1105), if demands can still be allocated, the above steps are iterated.

[0122] In other words, in a network device according to the implementation described above the request contains at least one of a notification of the measured or predicted load on the first output port not matching the target load for the first port, information on the TCAM utilization and/or the number of rules added locally, information on the deviation from the target load on each port, and a list of flows the network device associated with another port than the first port.

[0123] In an implementation according to the present disclosure, the modification of the forwarding rules is chosen such that the deviation of the measured or predicted load from the target load on the output port is minimized. This may mean that the forwarding network device redistributes flows such that the deviation of the load from the target load in minimized. In one embodiment the load deviation is minimized within the scope of only redistributing the largest flows. However, more flows may be redistributed in other embodiments. Furthermore, the central controller changes the forwarding rules in one or more network devices such that load deviations that cannot be resolved locally are minimized. Note that the central controller may also amend the forwarding rules different network devices than the ones where the load deviations occur.

[0124] In an embodiment according to the present disclosure, when amending the forwarding table to resolve a significant deviation of the measured or predicted load from the target load, the network device uses a Variable Sized Bin Packing Problem (VSBPP) algorithm after removing the one or more flows identified as having the highest load.

[0125] In particular, when the network device knows what capacity is left on each outgoing port (once problematic flows have been virtually removed), a VSBPP can be solved to minimize the deviation to the expected target throughputs T_e^p. This problem is NP-Hard, but several approximation algorithms are available. In other words, in a network device according to this embodiment, for the improving of the match between the measured or predicted load and the target load on the output ports a Variable Sized Bin Packing Problem (VSBPP) algorithm is used after removing the flow(s) identified as having the highest load.

[0126] The bin packing algorithm may try to find an optimal solution for the set of flows that were identified as having the highest load. Alternatively, the algorithm may include more flows as variables for the bin packing problem. This may lead to a smaller deviation of the load from the target load but may also need more computational power.

[0127] In an embodiment according to the disclosure, the network device can determine the desired target load per port from the forwarding rules it received from a network control node. If the forwarding rules quasi-statistically distribute the flows to the output ports, possibly with different weights, these weights can be used to determine the target loads on the respective output ports. In other words, if, for instance, forwarding rules are provided to the network device by a network controller, the network device can calculate the target loads on its output ports without additionally having to receive the target loads. Conversely, the network device might only receive the target loads for its output ports and determine forwarding rules from the target loads.

[0128] In an implementation according to the present disclosure, flows can be aggregated to sub-aggregated flows and the flows and sub-aggregated flows can further be aggregated to aggregated flows that may comprise flows and/or sub-aggregated flows. When new rules are added to the set of rules in a forwarding network device (the rules may be changed by the network device itself or by a central controller), they can change the forwarding of aggregated flows as well as sub-aggregated flows and flows. It is further noted that aggregated flows can be split (into sub-aggregated flows of flows) and distributed over several outgoing paths. Likewise, flows and sub-aggregated flows can be merged. This can be caused by the initial as well as the amended forwarding rules. When rules are changed, the splitting and merging of flows and aggregated flows may be changed consequently.

[0129] In other words, a network device according to the implementation described above stores forwarding rules including a rule for forwarding packets of sub-aggregated flows of an aggregated flow, and in a case where the measured or predicted load on a first output port does not match a target load for the first port, excludes at least one of the sub-aggregated flows from the aggregated flow and modifies said stored forwarding rules by establishing a second rule associating the at least one of the sub-aggregated flows (e.g., a flow which according to the hash rule (or generally the first rule) was assigned to the first port) of the aggregated flow with a second output port so as to improve the match between the target load and the load on the first output port.

[0130] In an implementation according to an embodiment, the network device forwards the packets depending on the result of a computation of a hash over at least one of the header entries IP source, IP destination, Protocol, source port, destination port and/or the forwarding rules associating an input flow with an output port and/or the forwarding rules associating an input flow with an output port identify the input flow by at least one of said header entries.

[0131] Header entries can be entries TCP/IP or UDP/IP headers or entries of any other kind of headers.

[0132] Aggregated flows may be forwarded depending on only one or two of the header entries and sub-aggregated flows may be forwarded depending on more header entries than are used for the aggregated flows and flows may be forwarded depending on more entries than are used for sub-aggregated flows. The same mechanism can be used for flows and aggregated flows by the network device in any kind of forwarding, for instance, when a specific forwarding rule for a flow or aggregated flow is defined, wherein the specific forwarding rule forwards the flow or aggregated flow to a specific output port directly.

[0133] FIG. 10 shows an exemplary network in which a network device according to the present disclosure can be used. Host A and Host B are part of a local area network. In this example, the local area network comprising Host A and Host B is part of Enterprise site A comprising also Router A. Enterprise site A is connected via a Wide Area Network with Router B which is part of Enterprise Site B comprising, again, a local area network. In this example. MPLS tunnels are used to transport a flow from site A to site B (wherein this flow may also be called aggregated flow). The flow or aggregated flow from site A to site B may be composed of any number of sub-flows. Network devices that are part of the Wide Area Network in this example can perform load balancing as described in the present disclosure.

[0134] FIG. 12 shows an example for a method to optimize load distribution according to the present disclosure. In an implementation of a method for forwarding traffic in a network device with a plurality of output ports according to the present disclosure, forwarding rules are stored, that include a first rule for forwarding packets of flows of an aggregated flow according to a given flow distribution to the output ports and, in a case where the load on a first output port does not match a target load for the first port, at least one of the flows from the aggregated flow is excluded and said stored forwarding rules are modified 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 improve the match between the target load and the load on the first output port, and routing is performed according to the stored forwarding rules.

[0135] In particular, to detect if the load on a first output port does not match a target load for the first port, the outgoing port utilization may be monitored (S1 in FIG. 12). This may be done by measuring the real throughput T_r^p on each outgoing paths p and comparing it with the expected throughput T_e^p (decided by the controller). To decide which new rule to establish, the traffic may be analyzed inside problematic outgoing ports (see S2 in FIG. 12). If T_r^p−T_e^p>Δ, probes may be installed on related ports to identify heavy hitters. Standard techniques like packet or flow sampling or advanced techniques like sketches may be used. As shown in S3 in FIG. 12, to identify problematic heavy hitters (large flows) the top N_S or largest flows are analyzed to identify which flow must be load balanced separately. Further, traffic prediction may used to select flows based on their expected future size. More generally, the subset of problematic flows is identified. S4 shows adjusting of forwarding for problematic flows. The next hop for problematic flows may be calculated locally and a bin packing algorithm may be used for this calculation. If needed, the controller may be asked for help (S5 in FIG. 12). In particular, the controller may be asked to globally configure the network (trigger for a global adjustment) if the imbalance problem cannot be solved locally. In general the method may include going back to the first step S1 and repeat the steps.

[0136] The device and method according to the present disclosure proposes a solution for imbalance issues by adapting load balancing to real traffic conditions. The main property of the solution may be that adaptation 1) is made locally in priority and up to the controller when needed, and 2) focuses on problematic flows (the one at the root of the imbalance issue) so that a limited set of additional rules are used in forwarding tables.

[0137] In this disclosure a method and an apparatus for accurate load balancing are provided that may locally identify the sources of imbalance issues, such as elephant flows whose distribution deviates from the original planned target, locally adjust the forwarding of problematic flows by adjusting the split of flows and reassigning forwarding rules and ask the centralized controller for help in case the target distribution cannot be met.

[0138] In other words, this disclosure provides a method to locally identify the source of imbalance issues in that the switches (forwarding network devices) continuously observe the traffic on outgoing ports to detect deviation issues. In case of a deviation, they can perform traffic analysis on ports to identify problematic flows (typically the largest ones, called Top-N or heavy hitters). Then, the switches locally adjust forwarding for problematic flows. To do so, they can extract problematic flows and forward them separately. Then a small bin packing problem may be solved locally. In case the deviation cannot be solved locally, the switches can ask the controller for a global (potentially network-wide) reconfiguration of load balancing.

[0139] Summarizing, 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.