Accurate traffic splitting on commodity switches

Traffic splitting is essential for load balancing over multiple servers, middleboxes, and paths. Often the target traffic distribution is not uniform (e.g., due to heterogeneous servers or path capacities). A natural approach is to implement traffic split in existing rule matching tables in commodity switches. In this paper we suggest an analytical study of such an approach. To do that, we relate the description of distributions in switches to signed representations of positive integers. We suggest an optimal algorithm that minimizes the number of rules needed to represent a weighted traffic distribution. Since switches often have limited rule-table space, the target distribution cannot always be exactly achieved. Accordingly, we also develop a solution that, given a restricted number of rules, finds a distribution that can be implemented within the limited space. To select among different solutions, we describe metrics for quantifying the accuracy of an approximation. We demonstrate the efficiency of the solutions through extensive experiments.