{'fraction_non_alphanumeric': 0.04415990687861482, 'fraction_numerical': 0.020224800843912552, 'mean_word_length': 4.062051187626588, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Throughput-Optimal Load Balancing for Intra Datacenter Networks

Traffic load-balancing in datacenters alleviates hot spots and improves network utilization. In this paper, a stable in-network load-balancing algorithm is developed in the setting of software-defined networking. A control plane configures a data plane over successive intervals of time. While the MaxWeight algorithm can be applied in this setting and offers certain throughput optimality properties, its bang-bang control structure rewards single flows on each interval and prohibits link-capacity sharing. This paper develops a new algorithm that is throughput-optimal and allows link-capacity sharing, leading to low queue occupancy. The algorithm deliberately imitates weighted fair queueing, which provides fairness and graceful interaction with TCP traffic. Inspired by insights from the analysis, a heuristic improvement is also developed to operate with practical switches and TCP flows. Simulations from a network simulator shows that the algorithm outperforms the widely-used equal-cost multipath (ECMP) technique.


I. INTRODUCTION
Datacenter networks serve as infrastructure for search engines, social networks, cloud computing, etc. Due to potentially high traffic loads, load-balancing becomes an important solution to improve network utilization and alleviate hot spots [1]- [4]. A widely-used technique is equal-cost multipath (ECMP), where traffic flows are split equally according to the number of available equal-cost next-hops. However, ECMP does not take into account actual traffic and is susceptible to asymmetric topology [5]- [7]. Further, the deployment of ECMP is limited due to its equal-cost constraint [8].
Traffic load-balancing can be implemented using softwaredefined networking (SDN). An SDN switch, a network device supporting layer-2 and layer-3 operations in OSI architecture, consists of a data plane and control plane [9]. 1 The data plane forwards packets according to given rules and operates at a fast timescale, e.g., 1ns. The control plane sets those rules and operates at a much slower timescale, e.g., 1ms. Several traffic load-balancing algorithms can be implemented through the control plane reconfiguration.
Existing traffic load-balancing methods for datacenter networks distribute traffic according to network capacity and measured traffic. Weighted-cost multipath [7] distributes traffic according to path capacity. Centralized algorithms, such as Hedera [10] and Niagara [5], take advantage of global traffic information to split traffic at a coarse timescale. Loadbalancing with a finer timescale has been implemented in DeTail [11] and CONGA [6] using the in-network technique, where decisions are made at switches inside a network without any central controller. Conceptually, these approaches attempt to distribute traffic over available network resources. However, the path-based approach in CONGA limits scalability, and the packet-by-packet dispersion in DeTail needs TCP with out-oforder resilience. Further, these algorithms do not come with analytical optimality proofs, and it is not clear if they are throughput optimal.
An algorithm is throughput optimal if it stably supports any feasible traffic load, so that average backlog is bounded [12]. Specifically, a throughput-optimal algorithm utilizes the entire network capacity and can distribute traffic to any portion of the network to maintain network stability. MaxWeight [12] is a well-known throughput-optimal algorithm and has been studied for packet radio [12], switching [13], and interdatacenter networking [14]. It has been generalized to optimize power allocation [15], throughput [16], etc. Practical aspects of MaxWeight such as finite buffer capacity and fairness with TCP connections have been studied in [17]- [19]. However, MaxWeight is not suitable for in-network load-balancing because it prohibits the sharing of link capacity at the data plane's timescale and thus causes high queue occupancy. This queue size has a finite average, but the size of the longer timescale makes that average unacceptably large.
The MaxWeight algorithm is illustrated by the example in Fig. 1. Two traffic commodities share three links passing through switches 1, 2 and 3. Time is slotted. The slot size equals the length of the decision update interval (the control plane's timescale). The capacity of each link is 3 packets per slot. Every switch has a dedicated queue for each commodity. In every time slot, MaxWeight calculates, for each link and commodity, a weight equal to the differential backlog between a queue and its next-hop queue. For that slot, the entire capacity of the link is allocated to the commodity with the maximum non-negative weight, while a commodity with negative weight is ignored. For example, commodity 2 is served on the link between switches 1 and 2 in Fig. 1, and commodity 1 is served 1 2 3   1 2 3  1 2 3  1 2 3  1 2 3  1 2 3  1 2 3  1 2 3  1 2 3  1 2 3  1 2 3  1 2 3  1 2 3  1 2 3  1 2 3   1 2 3  1 2 3  1 2 3  1 2 3  1 2 3  1 2 3  1 2 3  1 2 3  1 2 3  1 2 3  1 2 3  1 2 3  1 2 3  1 2 3  1 2 3   Commodity-1   Commodity-2   t=0  t=1  t=2  t=3  t=4  t=5  t=6  t=7  t=8  t=9  t=10  t=11  t=12  t=13  t=14   t=0  t=1  t=2  t=3  t=4  t=5  t=6  t=7  t=8  t=9  t=10  t=11  t=12  t=13  t=14 Fig. 2. Timeline of queue occupancy under MaxWeight: a small box represents a packet in a queue. Switch i is represented by the number i ∈ {1, 2, 3} under the long line. The short line under the number indicates that the commodity at the numbered switch is served in that particular time slot. The occupancy pattern repeats after t = 14, which is similar to the pattern at t = 11. Let the arrival rates to switch 1 of commodities 1 and 2 be respectively 1 and 2 packets per slot. The timeline of queue evolution is shown in Fig. 2. MaxWeight is effective and always transmits three packets per slot after t = 11. This effectiveness requires a sufficient amount of queue backlog. For example, commodity 2 backlog at switch 1 is always at least 5 for times t ≥ 11. This occupancy might be acceptable. However, if the control plane is reconfigured at a slow timescale relative to the link capacity, the queue occupancy can be very high. For example, with a 1ms update interval, 10Gbps link speed, and 1kB packet size, each link can serve 1250 packets per slot (rather than just 3). This multiplies queue backlog in the timeline of Fig. 2 by a factor 1250/3, so the minimum queue backlog of commodity 2 at switch 1 is 5×(1250/3) ≈ 2083 for t ≥ 11. Another undesirable property of MaxWeight is that queue occupancy scales linearly with the number hops, as shown in [20], [21]. In fact, Fig. 2 is inspired by an example in [20].
In practice, the MaxWeight mechanism with a long update interval leads to i) large buffer memory, ii) packet drops, iii) high latency, and iv) burstiness (no capacity sharing during an update interval). Issues (i)-(iii) can be alleviated partially by the techniques in [21]- [24]. However, issue (iv) resides in the decision making mechanism of MaxWeight and still persists under those techniques. The situation is worse when issues (ii) and (iv) interact with TCP congestion control, causing slow flow rate and under utilization. To put it into theoretical perspective, even though MaxWeight solves a network stability problem with O(1) average queue size, the constant factor is too large for a practical system with a long update interval. Note that an ideal algorithm for the example in Fig. 1 always serves 1 and 2 packets of commodities 1 and 2 by sharing the link capacity as shown in Fig. 3.
In this paper, a new throughput-optimal algorithm is developed. The algorithm shares link capacity among commodities during an update interval, resulting in low queue occupancy and low latency. The key challenge is to design a model and an algorithm that are analyzable, provably optimal, and practically implementable at the same time. The algorithm imitates the weighted fair queueing (WFQ) [25], [26] available in practical switches to provide fairness and low latency among TCP flows in practice. A general intra data center network may have an exponential number of paths, and our algorithm comes with an optimality proof considering all possible paths using per-commodity queueing which grows linearly with the number of commodities. This is also a key distinct aspect from the path-based algorithm in [27].
Section III develops the throughput-optimal algorithm. Inspired by this algorithm, Section IV presents an enhanced algorithm that includes heuristics to cope with practical aspects, including queue information dissemination, queue approximation, and packet reordering issues in TCP. This heuristic algorithm uses local queue information and local measured traffic to hash TCP flows to next-hop switches and set weights of the weighted fair queueing. The hash-based mechanism is chosen to reduce packet reordering, which is not possible for DeTail [11]. Simulation results in Section V show that both proposed algorithms outperform MaxWeight and ECMP algorithms in ideal simulation and in more realistic simulation with OMNeT++ [28].

II. SYSTEM MODEL AND DESIGN
The fast timescale of the data plane operates over slotted time t ∈ Z + , where Z + = {0, 1, 2, . . .}. The control plane configures the data plane every T slots, where T is a positive integer. Thus, reconfigurations occur at times in the set T = {0, T, 2T, . . .}.

A. Topology and Routing
An intra datacenter network is the interconnection of switches and destinations (such as servers), as shown in Fig.  4. Traffic designated for a particular destination d is called commodity d traffic. Let S be the set of all switches and D be the set of all destinations (commodities). A link between switches i and j is bi-directional with capacity c ij from i to j, and capacity c ji in the reverse direction. Define c ij = 0 if link (i, j) does not exist or if i = j.
Each switch must decide where to send its packets next. Define H d i ⊆ S as the set of next-hop switches available to commodity d packets in switch i, for all i ∈ S and d ∈ D. In practice, these sets can be obtained from manual configuration or from other routing mechanisms. Define the set of all nexthop switches from switch i as from switch i to switch j for i, j ∈ S. Note that this model allows arbitrary path lengths, and can be applied to existing topologies in [1]- [4], [8].

B. Traffic
Switch i receives a d i (t) commodity-d packets from external sources at time t (for i ∈ S, d ∈ D). The external source represents a group of servers or a link connecting to the outside of the network. For each i ∈ S, d ∈ D, the arrival process ) across time slots. The i.i.d. assumption is useful for a simple and insightful analysis. The resulting algorithm developed under this assumption inspires a heuristic algorithm in Section IV that does not require i.i.d. arrivals and works gracefully with TCP traffic.
Recall that c ij is the capacity of the link between switch i and switch j, for i, j ∈ S. Let b d i be the capacity of the link between switch i ∈ S and destination d ∈ D. Set b d i = 0 if switch i does not have a direct link to destination d. Assume arrivals and link capacities are always bounded by a constant

C. Decision Variables
Decision variables are defined for every link connecting switch i to its next-hop switch j, for i ∈ S, j ∈ H i . Recall that D ij is a set of commodities using the link. At configuration time t ∈ T , the control plane in switch i chooses a control plane decision variable x d ij (t, T ) for d ∈ D ij , which represents a constant transmission rate allocated to commodity d (in units of packets) for the entire T -slot interval. Define x d ij (t, T ) = 0 for d ∈ D\D ij . The control plane decisions for link (i, j) are chosen to satisfy the link capacity constraint: Once x d ij (t, T ) is determined, no more than x d ij (t, T ) commodity-d packets can be transmitted by the data plane during an interval {t, . . . , t + T − 1}. For example, the data plane can impose a token bucket mechanism. Let x d ij (t) be data plane decision variable that represents the transmission rate assigned by the data plane to commodity d on link (i, j) for slot t. These are chosen to satisfy

D. Queues
Packets are queued at each switch according to their commodity. Let Q d i (t) be the number of commodity-d packets queued at switch i on slot t. The value Q d i (t) is also called the commodity-d backlog and satisfies:  (3) is an inequality rather than an equality because the actual amount of new endogenous arrivals on slot t may be less than j∈P d i x d ji (t) if previous switches j do not have enough commodity d backlog to fill the assigned transmission rate x d ji (t). It can be shown that the backlog at time t ∈ T satisfies for every i ∈ S, d ∈ D: Note that, while a common queue for each commodity is not available in practical switches, it can be heuristically implemented by queues in an SDN switch in Section IV.

E. Stability and Assumption
Definition 1 (Queue Stability [22]). A queue with backlog Definition 2 (Network Stability [22]). A network is strongly stable when every queue in the network is strongly stable.
The arrival and departure rates are assumed to satisfy a standard Slater condition: Assumption 1 (Slater Condition). There exists an > 0 and a randomized policy and the randomized policy satisfies the constraint (2).
Note that Assumption 1 is stated in terms of only the data plane decision variables x d * ij (t) and the constraint (2). While the control plane decisions are used in the algorithm and the additional constraint (1) is satisfied by the algorithm, those are not used in the Slater condition.

III. THROUGHPUT-OPTIMAL ALGORITHM A. The Algorithm
The novel throughput-optimal algorithm runs distributively at every switch. Let K be a positive real number, and At every reconfiguration time t ∈ T , switch i executes Algorithm 1 for each link connecting to a next-hop switch j for rounds the real-valued z to its closest integer.

B. Intuitions
Algorithm 1 solves problem (5) with the value of k ij (t) that depends on local queue information and previous decisions. This k ij (t) is deliberately introduced, just as a solution of Fig. 6. Packet-filling Algorithm 2 iteratively fulfills the requests. An iteration number is indicated in a gray box. In this example, T c ij = 9 and the first iteration (the plot on the left) allocates rate to commodity 4. The algorithm allocates 2, 0, 3, 4 rates to commodities 1, 2, 3, 4.
In Algorithm 1, y d ij (t) represents a request for transmission rate of commodity d. It also indicates how well the previous rates were allocated. Under allocation of x d ij (t − T, T ) increases queue backlog Q d i (t), which tends to increase the request y d ij (t). It is easy to see that, if the queue backlogs Q d i (t) and Q d j (t) are about the same, then the request is about the same as its previous value. This behavior is smoother than MaxWeight.
The requests are fulfilled in two situations. i) When the total requests are roughly within KT c ij , i.e., d∈Dij round y d ij (t) + /k ij (t) ≤ T c ij , the requests are fulfilled in WFQ fashion, which can be seen by considering k ij (t) = 1 T cij d∈Dij y d ij (t) + and ii) The other is an extreme situation for stability analysis, which occurs when a network operates near its capacity, which may not be the case in practice due to TCP congestion control. This case is solved by Algorithm 2 2 , as illustrated by Fig. 6. It is easy to see the fairness introduced by k ij (t). Without k ij (t), i.e., k ij (t) is always 1, the allocation in Fig. 6 will be 0, 0, 2, 7 for commodities 1 to 4, which may cause a fairness issue with TCP flows [19].

C. Correctness of Algorithm 1
This subsection shows that Algorithm 1 returns an optimal solution of problem (5). To simplify notation in this section, the time index of variables and constants in problem (5) are omitted. Let z d ij denote x d ij (t − T, T ). When commodity d is allocated an integer service value v d ij , define its contribution to the cost function of problem (5) as The cost difference of getting another service allocation is Since the cost function in problem (5) is minimized, commodity d only accepts a transmission allocation if g d The cost difference in (7) is monototically increasing in v d ij . Therefore, commodity d receives transmission allocation at most: leads to a feasible solution of problem (5). Note that the objective function of problem (5) is separable, minimizes the problem with respect to commodity d.
Lemma 1 implies that Algorithm 1 solves problem (5) when the first (if-)condition is met. The other case of Algorithm 1 can be shown by the following property. When commodity d is allocated v d ij transmission rate, define the unfulfilled level of commodity-d's request as Lemma 2. When k ij > 0, for any commodities d, e ∈ D ij whose allocated rates are respectively v d ij and v e ij , the following holds: (v e ij + 1). Proof. It holds from equations (7) and (10) that In )+g e ij (v e ij ) = 0, which proves (i). Case (ii) can be proven similarly by substituting −l d ij (v d ij )+l e ij (v e ij ) < 0 into equation (11) and rearranging terms. Lemma 2 implies that allocating rate to the commodity with the highest unfulfilled level reduces the total objective the most. Specifically, let v d ij be the current rate allocation of commodity d.
The above property ensures that the iterative allocation in Algorithm 2 greedily optimizes problem (5) when event d∈Dij round y d ij (t) + /k ij (t) > T c ij occurs. It can be proven by contradiction that commodity d gets at most x d(max) ij rate for all d ∈ D ij . Then, the algorithm always allocates the entire transmission rate, as an implication of the event. Therefore, Algorithm 2 returns an optimal solution of problem (5). Theorem 1. Given K > 0, Algorithm 1 solves problem 5 with k ij (t) ∈ [1, K], where k ij (t) is defined in the algorithm.
Proof. The theorem is the consequence of Lemmas 1 and 2 and the fact that k ij (t) ∈ [1, K].
Proof. Squaring both sides of (4), rearranging, and bounding terms (see [22] for example) leads to . Define a T -slot quadratic Lyapunov drift of queue backlogs [22] as where z is the l 2 -norm of vector z, i.e., The second line of the above equation can be rewritten as using the fact that x d ij (t, T ) = 0 for every d ∈ D\D ij . Instead of minimizing the above expression, which leads to the MaxWeight algorithm, an state-dependent proximal term [1, min[K, z]]. This proximal term is non-negative and is upper bounded by KT 2 δ 2 , so it holds from (12) and (13) that 3 The x d ij (t − T, T ) in the proximal term can be replaced by z d ij (t)/α for any 0 ≤ z d ij (t) < ∞ and 0 < α < ∞ to allow more control flexibility.
Minimizing the right-hand-side of (14) with respect to x d ij (t, T ) d∈Dij leads to problem (5). Applying the result from Algorithm 1, which solves the minimization at reconfiguration time t ∈ T , yields the bound for any other x d ij (t, T ) d∈Dij satisfying constraints in problem (5): Since the proximal term is bounded and policy constructed from the randomized policy in Assumption 1, is one of those x d ij (t, T ) d∈Dij , it follows that Applying identity (13), taking expectation, and using the independent property of the randomized policy gives where G 1 is defined in the theorem.

IV. SYSTEM REALIZATION
The previous section provides an ideal allocation of decision variables. This section develops a heuristic improvement that is easier to implement for practical switches.

A. Approximation of Common Queues
An SDN switch has output queues at each of its ports [11], [29], [30]. Those queues can be assigned to each commodity. Let Q d ij (t) denote the backlog of a queue for commodity d at the port of switch i connecting to switch j at time t. The queue backlog Q d i (t) in Section II-D can be approximated bỹ It can be shown that this approximation becomes exact when the port's queues have never been emptied. Note that OpenFlow [30] allows 2 32 unique queues per port, but availability of those queues may depend on a switch. This work encourages next generation switches to have a high number of available queues.

B. Additional Packet Headers
Three fields are appended into the IP header as IP options: CommodityId, QueueInfo, and HashField. The CommodityId identifies the commodity of QueueInfo which stores the rounded value of exponential moving average of approximated queue backlog,Q d j (t). A packet from switch j to switch i carries queue information of a commodity, which is circularly selected from commodities in D ij 4 . The HashField is used for traffic splitting and is explained in Section IV-D.
Once a packet with the additional headers from switch j arrives to switch i, the contained queue information is extracted and stored in a local memory, which is denoted by M d ij (t). This is the most recent queue information for commodity d on link (i, j) up to time t, where d is the value in CommodityId. The header processing can be implemented by P4 [32], NetFPGA [33], or a custom ASIC.

C. Weighted Fair Queueing
Each port of switch i connecting to switch j ∈ H i is configured with weighted fair queueing. Let r d ij (t, T ) denote the measured number of commodity-d packets transmitted from switch i to switch j during the interval [t, t + T ). At every configuration time t ∈ T , the weight w d ij (t) for the interval [t, t + T ) is and w d ij (t) = 0 for d ∈ D\D ij . Parameter α > 0 is added to scale the magnitude of actual traffic to match a finite queue capacity. From these weights, w d ij (t)/ e∈D w e ij (t) fraction of link capacity is given to commodity d, which corresponds to the intuition in equation (6). Note that actual traffic r d ij (t − T, T ) is used instead of x d ij (t − T, T ), because it is a better approximation under TCP traffic.

D. Traffic Splitting by Hashing
A sending rate of a TCP connection is reduced when out-oforder packets are received at a destination. Hashing a packet to a next-hop switch based on HashField is implemented to reduce packet reordering. The HashField is generated once for the entire packet life. Packets from the same TCP connection have the same HashField, so they are hashed to the same path. Reordering does not occur if a hash rule at each switch is the same for the entire TCP connection. The hash rule is calculated as follows. For each commodity d ∈ D, Subject to This problem can be solved in polynomial time. Let s d ij (t) = 0 for all j ∈ H d i . Iteratively, s d ij (t) is increased for a group of in- until the equality constraint is met 5 . This process keeps increasing the min j∈H d The intuition of problem (16) is that it attempts to equalize the backlog levels at all ports at end of the interval [t, t + T ) by using r d ij (t − T, T ) as an estimate of actual transmission r d ij (t, T ). The attempt tries to make the approximation in Section IV-A exact. The splitting ratio of the port connecting to switch j is V. SIMULATIONS

A. Ideal Simulation
Algorithm 1 is simulated according to the system model in Section II. A switch uses a token bucket mechanism to ensure that transmission rate per interval satisfy constraint (1) after Fig. 7 is simulated with the interval length T = 100 and the constant K = 10. The network is simulated for 10 5 slots. The average backlogs shown in Table  TABLE I  I are calculated after Algorithm 1 and MaxWeight converge. The link-capacity sharing of Algorithm 1 leads to small queue backlogs. For scaling comparison, when T = 1000, the average backlogs of commodity 1 at switch 1 are respectively 23.94 and 16005.63 under Algorithm 1 and MaxWeight. In this simulation, the maximum value of k ij (t) for all i ∈ S, j ∈ H i , t ∈ 0, . . . , 10 5 is 1.732 < K.
A network in Fig. 8 is simulated with T = 100 and K = 10. After 10 5 slots, the average backlogs per queue (from all 124 queues) are 34.23 and 555.95 under Algorithm 1 and MaxWeight. An event k ij (t) = K occurs 93.41% of the times due to that the network operates near its capacity boundary. Reducing the arrivals by 12% (24%) yields 20.68% (5.49%) of the times that k ij (t) = K. This suggests that Algorithm 2 is rarely invoked, i.e., k ij (t) < K, when a network does not operate near its capacity boundary. In practice, TCP flows with congestion control are different from the i.i.d. arrivals, so Algorithm 2 is not included in the heuristic algorithm.

B. Network Simulator
The heuristic in-network load-balancing algorithm in Section IV is simulated by OMNeT++ [28]. All simulations share the following setting. Capacity of each commodity queue at a switch port is 200 packets. For ECMP setting, a shared queue at a switch port has buffer capacity of 200 × |D| packets, where D is a set of commodities in a considered network. Configuration interval is T = 1ms, and the scaling parameter is α = 5. The NewReno TCP from INET Framework [34] is adjusted for 10Gbps and 40Gbps link speeds. Every TCP flow is randomly established during [0s, 0.5s] and starts during [1s, 1.01s]. Each flow transmits 1MB of data. Flow completion time (FCT) is measured as the performance metrics, which are also used in [6], [11]. FCT is the duration of time to complete a flow, i.e., the time to send 1MB of data. A network without commodity 9 in Fig. 8 is simulated. The speeds of level-1 links and level-2 links are respectively 10Gbps and 40Gbps. 64 flows are generated from a commodity to one another, and the total number of flows in the network is 3584. The FCTs under the heuristic algorithm and ECMP are shown in Fig. 9, and their variances are 5.8 × 10 −4 and 19.5 × 10 −4 . Unsurprisingly, they are comparable, since the topology is optimized for ECMP. The FCTs under the heuristic algorithm has less variation, as the distribution of flows are more balance. Note that the tail of FCTs is critical for interactive services [11].
A follow-up scenario is simulated when the link between switches 12 and 14 in Fig. 8 fails. The FCTs of all flows are shown Fig. 10. The heuristic algorithm balances the flows better than ECMP. Switches 9 and 10 hash more flows to switch 13 than switch 14, while ECMP hashes flows equally.
A network in Fig. 11 illustrates the adaptiveness of the heuristic algorithm when some link capacity is taken away by priority flows. The FCTs of all flows are shown in Fig.  12. The FCTs under the heuristic algorithm is more balance compared to the FCTs under ECMP, as switches 1 and 2 hash more flows to switch 4 instead of equally hashing in ECMP case. Note that if the priority flows begin shortly after 1.01s, the same result is observed.
A similar trend can be observed from scenarios with short

VI. CONCLUSION
This paper showed that practical load-balancing in datacenter networks can be tackled by the concept of throughput optimality. Our first algorithm is a novel variation of the MaxWeight concept that treats control plane and data plane timescales (useful for software defined networking), allows link capacity sharing during a control plane interval, incorporates weighted fair queueing aspects, and comes with a proof of throughput optimality. Next, this algorithm was modified to include heuristic improvements that allow easy operation with practical switch capabilities and works gracefully with TCP flows. Ideal and OMNeT++ simulations show promising potential against existing MaxWeight and ECMP.