Optimal Representations of a Traffic Distribution in Switch Memories

Traffic splitting is a required functionality in networks, for example for load balancing over multiple paths or among different servers. The capacity of each server or path implies the distribution by which traffic should be split. A recent approach implements traffic splitting within the ternary content addressable memory (TCAM), which is often available in switches. It is important to reduce the amount of memory allocated for this task since TCAMs are power hungry and are often also required for other tasks such as classification and routing. For splitting a universe of 2^W addresses into k pieces of particular sizes, we give a simple algorithm that computes an optimal representation in Õ(Wk) time. Furthermore, we prove that a recently published load balancer, called Niagara, which also runs in Õ(W k) time is in fact optimal. That is, both our algorithm and Niagara produce the smallest possible TCAM that splits the traffic exactly to the required pieces, where the only previously known algorithm for computing optimal exact representation has running time exponential in k. Finally, we rely on our optimal Õ(Wk) runtime algorithm to investigate through extensive experiments the amount of TCAM memory required to represent traffic splitting in typical scenarios.

I. Introduction

In many networking applications, the support of traffic split into multiple possible outputs is required. For example, this is required to partition traffic among multiple paths to a destination or when sending traffic to one of multiple servers. The split has to be deterministic such that all packets of the same flow are mapped to a single output, e.g., to avoid packet reordering within a flow. It is increasingly common to rely on the switches in the network to perform the split [1], [2], and traditional schemes use relatively simple hashing techniques for this task. Equal cost multipath routing (ECMP) [3] implements a split into k options by associating a hash value with each option and mapping a flow according to the hash value of its flow id. While ECMP distributes traffic uniformly among outputs, in many applications non-uniform distributions are required, e.g., when the outputs differ in their available resources. WCMP (Weighted ECMP) [4] is a generalization of ECMP supporting non-uniform output distributions. The possible output values are written to memory entries with repetitions. Then, a flow is randomly hashed into one of the entries, generating a distribution according to the number of appearances of each possible output.