面向骨干网流量分析的统计计数方法

摘要

本发明公开了一种面向骨干网流量分析的统计计数方法，其新颖之处在于对计数器向量进行分层，除第一层外，其他各层子计数器向量采用多级哈希表的形式进行组织，从而获得了良好的空间效率和时间效率。与现有的主动式统计计数器BRICK相比，DALCA的空间效率与其接近，但是时间效率明显优于BRICK。执行查询操作时，DALCA的访存带宽需求不到BRICK的1/8；执行更新操作时，DALCA的访存带宽需求不到BRICK的1/4。此外，DALCA的实现方式比BRICK更为灵活。

主权项

一种面向骨干网流量分析的统计计数方法，其特征在于该方法包括计数器向量的组织，计数器的更新以及计数器的查询这三个步骤；计数器向量的组织：计数器向量由多层子计数器向量构成，各层子计数器向量的长度随着层数的提高而递减，计数值的高位存放在高层的子计数器向量中，计数值的低位存放在低层的子计数器向量中；除最低层子计数器向量外，其他各层子计数器向量采用多级哈希表进行组织，除最高层子计数器向量外，其他各层子计数器向量中，每个子计数器均设置有1比特的溢出标志位；计数器的更新：对计数器进行更新时，从最低层的子计数器开始；若某个子计数器在更新之后发生溢出，则根据其溢出标志位进行判断，若溢出标志位为1，则查找其后继子计数器，并向其后继子计数器进位，若溢出标志位为0，则为其分配后继子计数器，并向后继子计数器进位；计数器的查询：对计数器进行查询时，首先从最低层的子计数器开始，若低层子计数器的溢出标志为1，则查找其后继子计数器，并且将其后继子计数器的值也累加到查询结果中，如此循环，直至查询到某个子计数器，发现其溢出标志为0，或者查询到最高层子计数器为止。