空间高效的计数器结构

黄清杉，张 进，肖 刚，顾晓鸣

(1.解放军理工大学 通信工程学院，南京 210007;2.中国电子设备系统工程公司研究所，北京 100039)

随着互联网链路速率和数据流数量的飞速增长，流测量对内存的大小和内存的处理速度提出了苛刻的要求，需要计数器具备高速的在线计数处理能力［1－2］。例如，在40 Gbit/s的 OC －768 链路中，每隔8 ns就会有一个新的数据包到来，相应的计数器需要在这段时间内完成更新，这就需要具有快速处理能力的SRAM计数器。但是在最坏情况下所需的SRAM计数器数量也往往是不切实际的，因此如何提升计数器空间效率，使其适应高速流测量的需求，成为当前的研究重点［3］。

文献［4－5］提出了一种被动式(passive)计数器。该计数器是基于SRAM+DRAM的混合结构，基本思想是在SRAM中存储一些低位数值(例如9位)，将对应的所有高位数值存储在DRAM中(例如64位)，当数值较小时只有这些SRAM计数器有增量。当SRAM计数器的值接近溢出时，相应的DRAM计数器将对应的SRAM计数器值记录下来，这样可以显著降低SRAM的成本，快速进行SRAM计数器写操作(延迟2～5 ns)，但DRAM计数器部分的读取访问就比较慢(延迟60～100 ns)。这种方法称之为被动式计数，即其中一般计数器值不需要经常读出(直到测量周期结束)。文献［6－7］提出了另一种被动式计数器 CB(counterbraids)，它基于数据压缩与编码技术，核心是采用类似低密度校验码的思想对计数型布鲁姆过滤器的计数器空间进行压缩，在查询阶段再采用解码算法对计数值进行还原。

文献［8］提出了一种主动式计数器SAC(simple active counter)，它基于数值压缩的思想。SAC可以将计数值存储在SRAM中，但每个计数器需要有额外的存储开销和额外的处理开销。文献［9］提出了另一种主动式计数器DISCO(DIScount Counting)，它也是基于数值压缩的思想。它将计数值进行压缩后存储，这种压缩存储存在一定的压缩误差，但比较适用于计数精度要求不是很高的情况。文献［10］提出的一种主动式计数器BRICK(bucketized rank indexed counter)，是基于分级索引(rank index)技术。BRICK采用标记索引方式将计数器位空间分级，然后按照标记索引存储，查询时再按照计数的反操作，通过标记位求出计数器的值。这样就不需要将每一个计数器的位宽设为一样，在引入少量的空间标记比特的情况下可有效提升空间效率。

文献［11］提出的SBF(spectral bloom filter)采用动态的计数器空间分配策略，在一定程度上提升了空间效率，但是动态分配策略的实现机制较为复杂，难以应用到高速计算场合。

以上这些空间高效的计数器都在一定程度上提升了计数器的空间效率，但由于被动式计数器的完整信息保存在DRAM中，相对于SRAM读取较缓慢，不能很好满足高速网络中读取线速的要求，因此本研究重点研究主动式计数器，并将这些空间高效的主动式计数器引入到数据流测量算法中，用于改善数据流测量算法的空间效率。

1 典型的主动式空间高效计数器

主动式计数器都是仅使用SRAM的空间高效计数器。SAC可以将计数值存储在SRAM中，但每个计数器需要有额外的存储开销和额外的处理开销。以下重点介绍2种典型的主动式空间高效的计数器——DISCO计数器和BRICK计数器。

1.1 DISCO

文献［9］提出了DISCO(discount counting)计数器，它是基于数值压缩的思想，将要存储的计数值进行压缩，然后再将压缩值存储到计数器中。由于压缩后数值变小，所需的SRAM计数器位相对会少些，尤其是计数值越大，空间节省越明显。DISCO的压缩方法是将流的大小规范化为另一个数作为计数器值的增量。假设c为计数器值，n为流长度，有函数

其中b＞1为常数。

当长度为l的数据包到来且计数器值为c时，计数器以概率pd(c，l)使计数器值增加δ(c，l)+1，计数器以概率1－pd(c，l)使计数器值增加δ(c，l)，其中:

式中0≤pd(c，l)≤1。显然，n=f(c)是一个凸函数，要存储的计数值越大，计数器值的增量就越小，因此所需的计数器位宽是大大减小了。如图1所示，要存储的计数值为81，经过DISCO处理后计数值的增量就压缩为59，以此类似。最后将原本需要存储的计数值2334压缩为321，有效提升了计数器的空间效率。

图1 计数值压缩存储

查询时进行函数的反运算，将计数值增量还原，但是这样的压缩还原存在一定的计数误差，计数值越大绝对误差也就越大。DISCO能够支持流量大小和流量字节计数，并提供离线和在线的测量结果。

1.2 BRICK

文献［10］提出的另一种主动式计数器BRICK(bucketized rank indexed counter)是基于分级索引(rank index)技术的。BRICK的主要思想是将计数器随机捆绑到固定大小的桶中来实现统计复用，并通过采用比特位向量作为排列索引来动态分配计数器位空间。这里的比特位向量是关键。对于每个计数器Ci，将其分割为 d个子计数器Ci，1，…，Ci，d，其中 Ci，j的地址记为 Ci，j=Aj［ai，j］。如图2 所示，C5的值分布为 A3［1］=10，A2［2］=11，A1［5］=11011，即 C5=101111011=379。

图2 BRICK计数器结构

对每个计数器设置一个比特位向量I，I分为p－1 个部分 I1，…，Ip－1，分别对应计数器的各个部分 A1，…，Ap－1，每个 Ij都有 k bit，一个比特Ij［a］对应一个 Aj［a］。Ij［a］既用于判别计数器Aj［a］之后是否还有值，又用于计算下一个子计数器Aj+1的地址。如图3所示，A1［1］和 A1［5］对应的 I1［1］和 I1［5］设置为 1，说明 A1［1］和 A1［5］在 A2还有值，且分别在 A2［1］和 A2［2］。

图3 BRICK计数器更新过程

查询计数值，按照A1到Ap－1的顺序逐个查看其标记比特位Ij［a］，然后将 Ij［a］为1的计数器位Aj［a］串起来，即得到计数值的大小。这个寻址过程需要计算Ij的和，根据Ij的和值寻址到高级计数器。这种寻址方式称之为间接寻址。

BRICK计数器可以将计数值有效地存储在SRAM中，同时支持快速更新和查找(例如40 Gbit/s的线率)，且查询时不会增加新的误差。

2 空间高效计数器的应用分析

2.1 DISCO计数器对数据流测量算法的影响

由于DISCO算法在进行数据处理的时候属于有损压缩，在还原数据时不可避免地会有一定的误差，这些误差在理论上肯定会影响到数据流测量算法。如图4可见，通过简单的模拟分析，DISCO处理前，越大的计数值其处理后的压缩值的绝对误差越大，而在计数值较小时其相对误差却会比较大。

图4 DISCO算法原始值与压缩值的比较

进一步模拟骨干网的数据流量进行应用分析。通过对骨干网流量数据的流长分布进行统计分析，发现数据流长基本符合Zipf统计分布，因此模拟这样一组数据流，其流长区间为［1，M］，流长分布服从Zipf分布，则流长取x的概率为

通常，网络流长分布的参数Z的取值为1.5～2.0。Zipf分布的互补累计分布函数CCDF如图5所示。当Z=2.0时，90%的流的流长是小于8，99%的流的流长是小于64;当Z=1.5时，90%的流的流长是小于64，99%的流的流长是小于4721。为保证分析效果，选择一个相对保守的参数Z=1.5。

图5 Zipf分布

根据式(1)，实验中设DISCO计数器参数b=1.01。数据流测量算法使用DISCO计数器的查询误差，如图6所示。和未使用DISCO计数器的查询误差相比，在使用DISCO计数器后，数据流测量算法的查询误差有明显增加，尤其是在120～180的时间周期变化最大。这主要是因为这一段时间的数据流数目较少。对照图4可知，流长越大得到的查询误差影响也越大。

图6 使用DISCO计数器时查询误差

因此，从应用效果来看，DISCO计数器可以使用在允许一定计数误差的应用中，但在精确度要求较高的环境下难以满足需求。

2.2 BRICK计数器对数据流测量算法的影响

BRICK将计数器分为多个桶，同时为每个桶中的计数器引入排列索引标记。同样采用模拟骨干网的数据流量进行仿真分析。

BRICK计数器采用3级索引标记作为分析。图7是使用BRICK计数器情况下的查询误差，得到的查询误差前后是一样的，说明使用BRICK计数器没有增加算法的查询误差。

图7 使用BRICK时的查询误差

实验表明BRICK计数器应用到数据流测量中没有误差影响，但是时间效率显然要比不使用BRICK计数器时低，因为它要对每个计数器进行标记寻址后再进行查询判断。

3 DA-BRICK

前面重点分析了DISCO计数器和BRICK计数器对数据流测量算法的影响，仿真结果表明，2种计数器在空间效率方面毫无疑问都有着显著的提升，但是引入DISCO计数器对数据流测量的查询误差有影响，而且这样的误差还比较大，在某些地方甚至比布鲁姆过滤器本身的查询误差还要大。

从应用结果来看，BRICK对流测量算法的查询误差没有影响，但由于使用了标记比特位向量，需要通过求和寻址方式计算原始的计数器值。若1级计数器中有新的计数值溢出，则相应的次级计数器都要改变，即次级计数器的更新与先后无关。如图3所示，1级计数器C1和C5溢出后顺序使用2级计数器的C1和C2，而当1级计数器C2也产生溢出后，则需要将1级计数器C5使用的2级计数器C2让出来给1级计数器C2使用，1级计数器C5再顺序使用的2级计数器C3。这样，每次变动都要进行大范围的调整，显然会增加一定的时间复杂度。因此希望改进标记比特位向量的寻址方式，即改间接寻址为直接寻址 BRICK，即 DABRICK(direct addressing BRICK)。

3.1 DA-BRICK的结构设计

DA-BRICK与BRICK唯一不同之处就是将标记比特位替换为下标计数器，这样当有计数器更新需要用到次级计数器时，用下标计数器记下溢出计数器的先后顺序。在查询时，只要计算下标计数器的值就能直接找到相对应的次级计数器了。DA-BRICK结构如图8所示。

在进行计数器更新过程中，1级计数器中先溢出的计数器按照先后顺序使用2级计数器，下标计数器记下使用次级计数器的先后顺序。当前面有新的计数器也产生溢出时，则按顺序使用2级计数器，而不是像BRICK将次级计数器顺次向下移位。如图8所示，1级计数器C1和C5溢出后顺序使用2级计数器的C1和C2，下标计数器的值则分别为1和2。而当1级计数器C2也产生溢出后，则使用2级计数器C3，下标计数器则记为3，次级计数器不需要顺次移位。

图8 DA-BRICK的结构

3.2 DA-BRICK的参数设计

DA－BRICK结构的关键是使用了直接寻址机制，所以下标计数器大小的设计很重要，它直接影响算法的时间效率。下标计数器的大小主要与1级计数器的多少、大小有关，而1级计数器的大小设计又与流长的分布相关。因为当大的数据流较多时，如1级计数器较小会使得大部分计数器需要使用2级计数器，这样1级下标计数器的比特位也需要增加，这会影响结构的空间效率。

由于经典CBF［12］在测量时需要按照最大元素频率值设置计数器的位宽，因此其位宽大小为b=。BRICK计数器采用3级索引标记，将每个计数器分割为3个子计数器。在流长服从Z=1.5的Zipf分布下:BRICK的1级计数器位宽设为=6bit，1级标记比特位设为1位;2级计数器位宽设为，2 级标记比特位设为1位;3级计数器位宽设为2 bit。DABRICK计数器仍然采用3级索引标记，依然将每个计数器分割为3个子计数器。考虑到1级计数器太小会需要使用较多的2级计数器导致1级下标计数器比特位的增加，因此DA-BRICK的1级计数器位宽的设置要比BRICK的多。从图5的流长分布情况看，DA-BRICK的1级计数器位宽设为29=512就能够满足绝大部分的数据流计数需求，只有少量数据流会有计数溢出到2级计数器。因此将2级计数器的位宽设为级计数器位宽设为2 bit。和 BRICK相比，DABRICK所需付出的额外的空间开销就在于1、2级下标计数器的位宽。DA-BRICK结构的一个实例如图9所示。

图9 DA-BRICK结构实例

4 仿真分析

本节使用真实网络流量数据进行仿真分析。仿真实验的目的是验证在真实网络流量下，计数器向量的溢出概率，并分析和BRICK相比，将DABRICK应用于数据流测量算法后计数误差的变化情况以及空间效率情况。

实验通过CAIDA得到网络的真实数据。选取2组数据:trace1是2004年06月01日19:00—20:00第5、35 min的网络流量;trace2是2002年08月14日09:00—10:00第5、35 min的网络流量。数据以互补累计分布函数CCDF(complementary cumulative distributionfunction)形式进行统计分析，如图10所示。

首先根据布鲁姆过滤器参数设计原则可以算出所需的布鲁姆过滤器空间的大小。例如要使得布鲁姆过滤器的误差为0.02135级别，且哈希函数个数为6时，则所需的布鲁姆过滤器空间为

综合考虑，数据流测量仿真时布鲁姆过滤器的空间大小设定为m=1500000。此时，可知最佳哈希函数个数

其次进行DA-BRICK计数器的参数设置。由图10所示的流长分布，99%的数据流的流长小于512。实验中DA-BRICK计数器采用3级索引标记，1级计数器位宽设为12 bit，2级计数器位宽设为5 bit，3级计数器位宽设为2 bit。2级计数器的个数设为32，此时1级下标计数器的大小为5 bit。又将3级计数器个数设为4，则2级下标计数器的大小设为2 bit。

图10 流长分布

通过仿真统计，在这样的参数设计下，计数器向量空间的溢出个数为12，溢出概率为12/150000=8 ×10－5。

图11 各级计数器使用情况

在以上的参数设计下，分析DA-BRICK空间效率。设实验中数据流测量算法使用了m个计数器，各级计数器使用情况如图11所示，则经典CBF按照最大元素频率值设置计数器的位宽使用的总空间MCBF=m×19，BRICK计数器使用的总空间

DA-BRICK计数器使用的总空间

显然，BRICK计数器空间效率比普通计数器提高了31.5%，而DA－BRICK的空间效率比普通计数器提高了10.5%。由于使用直接寻址方式，使得改进后的DA-BRICK的空间效率比BRICK低了30%，但是时间效率提高100%了，因为数据流测量算法的时间复杂度不再是 O(n)，而是O(1)了。

仿真得到的查询误差如图12所示，和使用BRICK计数器的查询误差(图13)相同，即使用改进后的DA_BRICK计数器没有增加新的查询误差。

实验表明将DA-BRICK计数器应用到数据流测量中没有增加查询误差，DA_BRICK在增加少量的下标计数器空间的情况下，时间效率显然比BRICK计数器要高一些，因为它不再需要对每个计数器进行标记寻址后查询判断，而是采用直接寻址方式。数据流测量算法的时间复杂度不再是O(n)，而是 O(1)了。

图12 使用DA-BRICK时的查询误差

图13 使用BRICK时的查询误差

5 结束语

本文通过对现有的空间高效的计数器DISCO、BRICK进行深入的研究和比较，发现DISCO计数误差大，而BRICK计算复杂度高，因而均不适用于面向高速骨干网的流测量。对BRICK进行了改进，提出了面向高速骨干网流测量的DA-BRICK计数器。仿真分析表明:DA-BRICK能够适用于高速测量的实时需要，同时不增大错误概率;其代价是和BRICK相比，在支持相同数目的计数器的前提下，DA-BRICK所需的存储空间增加了30%。

［1］Roeder M，Lin B.Maintaining exact statistics counters with a multilevel counter memory［C］//Proc.of IEEE Globecom.Dalas，USA:［s.n.］，2004.

［2］Shah D，Iyer S，Prabhakar B，et al.Analysis of a statistics counter arc hitecture［J］.IEEE Micro，2002，22(1):76 －81.

［3］Peter Lieven，Bjorn Scheuermann.High-Speed Per-Flow Traffic Measurement with Probabilistic Multiplicity Counting［C］//Proc.of IEEE Infocom.New York，USA:［s.n.］，2010.

［4］Ramabhadran S，Varghese G.Efficient implementation of a statistics counter architecture［C］//Proc.of Sigmetrics.San Diego，USA:［s.n.］，2003.

［5］Zhao Q，Xu J，Liu Z.Design of a Novel Statistics Counter Architecture with Optimal Space and Time Efficiency［C］//Proc.of ACM SIGMETRICS ’06.France:［s.n.］，2006.

［6］Yi Lu，Andrea Montanari，Balaji Prabhakar.Counter Braids:A Novel Counter Architecture for Per-Flow Measuremen［C］//Proc.of ACM Sigmetrics.USA:［s.n.］，2008.

［7］Yi Lu，Balaji Prabhakar.Robust Counting Via Counter Braids:An Error-Resilient Network Measurement Architecture［C］//Proc.of IEEE Infocom.USA:IEEE，2009.

［8］Rade Stanojevic.Small active counters［C］//in Proc.of IEEE Infocom .USA:IEEE，2007.

［9］Chengchen Hu，Bin Liu，Kai Chen.Compressing Flow Statistic Counters［C］//Proceeding of IEEE ICNP 2009(poster).New Jersey，USA:IEEE，2009.

［10］Hua N，Lin B，Xu J，et al.BRICK:A novel exact active statistics counter architecture［C］//ACM/IEEE Symposium on Architectures for Networking and Communications Systems(ANCS).USA:［s.n.］，2008.

［11］Cohen S，Matias Y.Spectral Bloom Filters［C］//Proceedings of the ACM SIGMOD.San Diego，USA:［s.n.］，2003:224－236.

［12］Fan L，Cao P，Almeida J，et al.Broder.Summary Cache:a Scalable Wide-area Web Cache Sharing Protocol［J］.IEEE/ACM Transactions on Networking，2000，8(3):281－293.