Recyclable Counter With Confinement （RCC）浅析

近来一直实验被卡在如何有效的构建一个实时的可扩展的SDN 测量和监控上。 其实关于SDN的测量，这几年有大量的工作，比如Open sketch, UnivMon 等，这些工作后面有空我再分享。 这里谈一谈一个比较有意思的工作， RFlow+, 今年Infocom的一个工作。 它本质上是将测量与监控任务分成长期和短期。 长期任务有控制器周期性收集数据，来定制和完成相应的规则。短期任务则是在数据平面实时测量，并通过预先制定的一些规则来实现诸如热门流检测，恶意流隔离之类的工作。 本质上来说，这个工作的创意放到2017年这个SDN已经渐渐脱离炒概念的年份，有些平凡无奇，但是让我比较感兴趣的是作者在文章用于做实时流统计的计数器 RCC。

直接切入主题，RCC 究竟是什么？

RCC由两个hash 表构成，即图中所示的Counter A 和 Counter B 构成。 Counter A 本质上采用的是随机计数器，类似于CSE。 简单说起来，就是所有的流的统计，都放在这一块内存上，只不过通过哈希函数，映射到不同的bit 上。 这里做的一个改进是，对于一个流，它映射的s 位不会 散布在整个内存上，而是集中在一个 c-bit的小块上。这也就是所谓的受限（with confinement）。 具体结构，可以参考下图。

这里可以看出RCC能完成的其实是每流包统计。 这个统计是这么做的呢？ 当每一个流来是时候，通过 H(f)把他映射成 （w,a_1,a_2….a_s）. w 表示那个内存小块的索引，a_i表示小块上的位置。以 c=32bit 为例，这里， w 为 mA/32 个bit, a_i 均是5个bit。 寄存器一次读取 索引为w的小块，这时候（a_1,a_2…a_s）构成一个虚拟向量。这个流的每一个包，都会随机生成一个1-s 的数，然后把向量的对应这个数的位置为1. Z来统计，这个向量中0的个数。这样每次包近来，映射到相应的位置，如果这一位原来是0，Z就减1. 置1的操作则是总是进行的。
为什么这样可以统计？ 这来自一篇更早一点的论文《A Linear Time Probabilistic Counting Algorithm for Database Applications》。 这里描述了一个利用hash表来进行统计的原理，这里不用特别大的空间，允许冲突，损失一定的精度，但能统计互不相同的项的个数。

这个例子可以看出，把包含1个重复项的12个元素映射到一个空间仅仅为8的哈希表，统计表中0的个数，即Vn=2.
这里给出统计值的预估公式：
e_n = -m ln(Vn)
代入可得 e_n = 11.1 非常接近正确值 11.
RCC 的counter A 就是基于这个原理，具体的正确性证明以及误差分析，可以参考前面给出的论文 《A Linear Time Probabilistic Counting Algorithm for Database Applications》，以及CSE的论文 《Fit a Compact Spread Estimator in Small High-Speed Memory》。这些数学证明还是比较有意思，这里得到的结论是这种统计，当0的个数在30%以上即装载率在70%一下，这个机制都工作的很好。具体过程这里暂且略过，以后有经历，也许我会整理一下。
回到RCC上来， counter A 利用这种方式进行统计，当某个小块装载率 达到70%，就会将其统计到Counter B中。 Counter B就是我们正常用的哈希表，对于冲突采用的二次探测 的方法。 统计值 est_i 是不断累加的。 对于 Counter A过载提交之后，就会清空，但这里注意，由于存在多流共享一些bit的存在，所以不是全变成0，而是随机翻转一些位， 如前面那个counterA示意图的（c）所示。具体翻转多少位，其实就是让这个向量达到全部内存的平均噪声水平，即 0占的比例和整个A 所在的内存块一致。公式是S *Z/MA - Zf。 后面我给出一个符号列表，以及具体的统计的编解码过程，这里要考虑共享内存带来的误差和噪音。但基本原理就是上面我所描述的这些。

总结性思考： 为什么要用RCC而不是简单的累加 呢 ？ 这是因为，网路中存在大量的流，而每流的数据包大小分布各不相同，我们如何分配内存呢？ 如果要是固定大小互补干扰的分配，我们只能按照最大的来，这样浪费大量的内存用来统计小流。 而不幸的是，网络实际中充斥着大量的小流，而大流的数据包数目又相当的多。再没有预先大小流识别的机制下，设计一个好的计数器都是一个很难的工作，简单的想法，下场就是内存空间大量浪费却又很容易过载，还要频繁进行内存访问。 从这个角度看，RCC牺牲一定的精准度，很好的面向实时流的包统计。
当然这只是一种包统计而不是流量统计，而且这种概率统计的机制，更适合做类别统计，而不是计数，我觉得，因为面对大流很容易过载，所以还是有很大的局限性。 但不可否认，这是一个有意思的工作，也是数据平面counter的一个很好的补充。