Traffic splitting is a required functionality in networks, for example for load balancing over paths or servers, or by the source's access restrictions. The capacities of the servers (or the number of users with particular access restrictions) determine the sizes of the parts into 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 consuming and are often also required for other tasks such as classification and routing. Recent works suggested algorithms to compute a smallest implementation of a given partition in the longest prefix match (LPM) model. In this paper we analyze properties of such minimal representations and prove lower and upper bounds on their size. The upper bounds hold for general TCAMs, and we also prove an additional lower-bound for general TCAMs. We also analyze the expected size of a representation, for uniformly random ordered partitions. We show that the expected representation size of a random partition is at least half the size for the worst-case partition, and is linear in the number of parts and in the logarithm of the size of the address space.
翻译:在网络中,交通分解是一项必要的功能,例如用于平衡路径或服务器的负载,或由源的进入限制来进行。服务器的能力(或有特定访问限制的用户数目)决定了交通应分割的部件的大小。最近的一种做法是将交通分解在开关中经常提供的可移植内容存储存储器(TCAM)内。重要的是减少为这项任务分配的内存量,因为TCAM是耗电的,而且对于诸如分类和定线等其他任务也经常需要。最近的工作建议了计算在最长的前缀匹配(LPM)模式中最小实施特定分区的算法。在本文件中,我们分析这种最小表达方式的属性,并证明其大小的大小较低和上界。对于一般的TCAM而言,我们证明还有额外的较低限制。我们还分析了一个代表的预期大小,对于统一订购的分区,我们还分析了一个随机分区的预期代表大小。我们发现,随机分区的预期代表大小至少是最坏的分区面积的一半,并且是空间分区的日数和行距数中的直线。