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. In the longest-prefix model (LPM), Draves et al. (INFOCOM 1999) find a minimal representation of a function, and Sadeh et al. (INFOCOM 2019) find a minimal representation of a partition. In certain situations, range-functions are of special interest, that is, all the addresses with the same target, or action, are consecutive. In this paper we show that minimizing the amount of TCAM entries to represent a partition comes at the cost of fragmentation, such that for some partitions some actions must have multiple ranges. Then, we also study the case where each target must have a single segment of addresses.
翻译:在网络中,交通分解是一项必要的功能,例如,对于平衡道路或服务器的负载,或对于源的准入限制,这种分流是网络中的一种必要功能。服务器的能力(或具有特定访问限制的用户数目)决定了通信应分割的部分的大小。最近的一种做法是将交通分解在长期内容可移动的内存内存(TCAM)内,这种内存通常在开关中可用。重要的是减少为这项任务分配的内存量,因为TCAM是耗电的,而且对于诸如分类和路线等其它任务也经常需要。在最长的前缀模型(LPM)、Draves等人(INFOCOM 1999)中,服务器的能力(或具有特定访问限制的用户数目)决定了一个功能的最小代表,而Sadeh等人(INFOCOM 2019)则决定了应分割部分的最小代表。在某些情况下,范围功能是特别有意义的,即同一目标或行动的所有地址都是连续的。在本文中,我们表明尽量减少TCAM条目中代表分割的成本是分解的,因此某些分区的行动必须具有多个的地址。