1.本发明涉及数据中心测量和管理领域，具体为一种利用towersketch(塔型摘要)和可驱逐流表在数据中心可编程交换机中进行全流量统计的方法和系统。
背景技术：2.随着数据中心规模的不断扩张，高速以太网技术的不断发展，目前大型数据中心中使用的核心交换机带宽已经达到3.2tbps(100gbps*32)或者6.4tbps(100gbps*64)，部分交换机厂商已经开始研发25.6tbps(400gbps*64)甚至更高带宽的下一代数据中心交换机。为了实现对数据中心网络的状态监管，以及对数据中心用户的带宽计费，对通过交换机的高速网络流量进行统计是具有必要性的。
3.通过交换机的流量由连续的网络数据包构成，每个数据包具有一定字节数量，并由二元组(源ip地址、目的ip地址)或者五元组(源ip地址、源端口号、目的ip地址、目的端口号、协议号)标记属于某个网络流，流量统计旨在统计每个网络流包含多少字节数量。由于数据中心交换机的缓存容量和控制面计算性能的提升速度远低于交换带宽的提升速度，在有限的计算和存储资源下对流量进行尽可能精确的统计具有极大挑战性，也是目前各个云服务提供商的核心技术。
4.目前常见的流量统计方案包括基于采样的统计方案和基于sketch(摘要)的统计方案。基于采样的方案使用预设的采样比(如1/1000采样比)对通过交换机的网络数据包进行采样并上送控制面，并且在控制面使用被采样的数据包对网络流量进行恢复；基于摘要的方案在交换机数据面部署并维护sketch数据结构，并且在数据面读取sketch数据结构以查询每个网络流包含的字节数量。上述两种统计方案分别受限于较低的控制面接受数据包的性能(常见为2百万数据包每秒)或者较小的数据面的缓存容量(常见为48m比特)，在高速流量场景(如1.6tbps)中流量统计精度很低，且无法提供流量估计性质保证。
技术实现要素：5.为了满足在idc(互联网数据中心)场景下流量统计的需求，本发明提供一种使用了紧凑数据结构，一级流表，以及环形缓存的数据中心流量统计方法，该方法可以被部署在可编程交换机上，在保证不高估的条件下高效地统计二元组《源ip，目的ip》的流量。
6.本发明的目的通过如下的技术方案来实现：
7.一种基于塔型摘要和可驱逐流表的数据中心流量统计方法，包括三个阶段/步骤：
8.第一阶段中，将每一个数据包经过一个基于塔型摘要的过滤器，该过滤器判断该数据包是否属于大流；
9.第二阶段中，将被认为属于大流的数据包插入流表，如果与原先的流表表项冲突，则驱逐原先的流表表项，并将该数据包插入流表；
10.第三阶段中，将驱逐的流表表项依次存入一个环形缓存，每当环形缓存中的流表表项到达一个阈值，就将环形缓存中的流表表项生成一个数据包，从环形缓存中取出该数
据包，即取出一组连续的流表表项，并上送控制面进行流量统计。
11.其中，上送控制面即上送cpu，是为了将这些流表表项插入到无错的数据结构中，例如哈希表，从而实现流量统计。
12.上述方法的关键思想是用一个支持滑动窗口的过滤器来过滤小流，以减小缓存的冲突次数。
13.进一步地，第一阶段中，过滤器由一个扩展的塔型摘要即towersketch组成。towersketch由多个内存开销相同的数组组成。每个数组由不同大小的计数器组成，用于统计包的字节数。称这些计数器为字节计数器。为了支持滑动窗口，扩展的towersketch中，为每个字节计数器分配一个用于记录时间戳的计数器，称为时间戳计数器。字节计数器与其对应的时间戳计数器共同组成一个桶。
14.进一步地，第一阶段中，当一个数据包进入交换机时，它先从交换机获取当前时间戳t，以及其包长l。随后，将该数据包插入过滤器中，插入操作如下：为towersketch的第i行数组，以该数据包的二元组《源ip，目的ip》为输入，用哈希函数hi计算一个哈希值ki。如果第ki个桶中时间戳计数器的值与t不同，将该桶中的时间戳计数器的值更新为t，将该桶中的字节计数器更新为min(上界，l)；如果第ki个桶中时间戳计数器的值与t相同，将该桶中的字节计数器的值更新为min(上界，原计数器值+l)。“上界”指该字节计数器的上界，比如一个8bit计数器的上界为255。随后，输出查询值，其值为更新后的字节计数器值。将等于上界的查询值视为无穷大。得到过滤器每行数组的查询值后，将其与一个可以动态配置的阈值thresh比较，如果均大于该阈值，认为这是一个大流，并进入第二阶段。
15.进一步地，第二阶段中，利用一个流表统计流量数据。流表由一个桶数组组成，每个桶中包含三个计数器，分别记录源ip，目的ip，以及经过的包的总字节数，分别称为源ip计数器，目的ip计数器，以及字节计数器。
16.进一步地，第二阶段中，当一个数据包被认为属于大流，并进入第二阶段后，将其插入流表，插入操作如下：以该数据包的二元组《源ip，目的ip》为输入，用哈希函数h计算一个哈希值k。如果第k个桶中的源ip计数器的值与目的ip计数器的值均与该数据包的源ip，目的ip值相同，将字节计数器的值更新为其当前值加插入的数据包包长；否则，驱逐原先桶中的数据，将源ip计数器的值与目的ip计数器的值更新为当前数据包的对应值，将字节计数器更新为当前包的包长。
17.进一步地，第三阶段中，利用一个环形缓存结构缓存流表表项，目的在于减少上送cpu的包数，用一个大包携带尽可能多的流表表项。环形缓存由一个长度为w的桶数组组成，每个桶中包含三个计数器，分别记录源ip，目的ip，以及经过的包的总字节数，分别称为源ip计数器，目的ip计数器，以及字节计数器。环形缓存结构维护两个索引，分别为称为生产者索引p_index与消费者索引c_index。生产者索引指向最新插入的流表表项在环形缓存中的位置，消费者索引指向最后被大包携带上送的流表表项在环形缓存中的位置，初始两个索引都设为0。设置一个上送频率f。
18.进一步地，第三阶段中，每次有流表表项被驱逐时，如果环形缓存没有满，即(p_index+1)mod w不等于c_index，即将流表表项插入第(p_index+1)个桶中，并将p_index更新为(p_index+1)mod w；否则，如果环形缓存已满，则选择不插入环形缓存，直接将被驱逐流表表项上送cpu。其中，w表示环形缓存中桶的数量。
19.进一步地，第三阶段中，每当p_index更新后，如果p_index modf＝0，则生成一个数据包，连续携带从第(p_index-f+1)个桶，到第p_index个桶的所有缓存桶，然后上送cpu。随后，将c_index更新为p_index。
20.一种采用上述方法的基于塔型摘要和可驱逐流表的数据中心流量统计系统，其包括：
21.过滤模块，用于将每一个数据包经过一个基于塔型摘要的过滤器，该过滤器判断该数据包是否属于大流；
22.流表插入模块，用于将被认为属于大流的数据包插入流表，如果与原先的流表表项冲突，则驱逐原先的流表表项，并将该数据包插入流表；
23.环形缓存模块，用于将驱逐的流表表项依次存入一个环形缓存，当环形缓存中的流表表项到达一个阈值时，将环形缓存中的流表表项生成一个数据包，从环形缓存中取出该数据包，并上送控制面进行流量统计。
24.本发明的有益效果是：
25.本发明可以被部署在可编程交换机上，在保证不高估的条件下高效地统计二元组《源ip，目的ip》的流量。
附图说明
26.图1是一个将数据包信息插入towersketch并判断是否为大流的示例。
27.图2是一个将数据包信息插入流表并驱逐原表项的示例。
28.图3是一个将被驱逐的表项插入环形缓存区并触发上送控制面的过程。
29.图4是本发明的基于towersketch和可驱逐流表的数据中心流量统计方法的整体流程。
具体实施方式
30.为了使得本发明的目的，技术方案以及优点更加清楚明白，以下结合附图当中的实例对本发明进行更进一步详细说明。应当理解，此处所描述的具体实例仅仅用以解释本发明，并不用于限定本发明。
31.图1是过滤器工作的过程。如图1所示，建立一个拥有两个数组的扩展的towersketch，其字节计数器的大小分别为8bit和16bit，时间戳计数器的大小均为8bit。时间戳的取值范围为0-255。一个数据包的包长为64字节，从交换机中得到的时间戳为14，过滤器的阈值thresh为300。首先将该数据包插入第一个数组的第四个桶中。在这一步中，发现第四个桶中的时间戳计数器的值也是14，字节计数器的值为200，因此，将字节计数器的值更新为min(上界，200+64)＝255。然后，将该数据包插入第二个数组的第六个桶中。在这一步中，发现第六个桶中的时间戳计数器的值也是13，字节计数器的值为53323，因此，将时间戳计数器的值更新为14，字节计数器的值更新为min(上界，64)＝64。两个查询值255与64分别被认为是正无穷与64，发现有一个查询值小于300，因此这个包被认为属于小流。
32.图2是流表工作的过程。如图2所示，建立一个拥有一个数组的流表，其中源ip计数器，目的ip计数器，与字节计数器的大小均为32bit。一个数据包的包长为64字节，源ip为12，目的ip为14。将该数据包插入数组的第五个桶中，在这一步中，发现第五个桶中的源ip
计数器的值为13，目的ip计数器的值为15，字节计数器的值是1000，因此，将源ip计数器的值更新为12，目的ip计数器的值更新为13，字节计数器的值更新为64。
33.图3是环形缓存工作的过程。如图3所示，建立一个拥有一个数组的缓存，其中源ip计数器，目的ip计数器，与字节计数器的大小均为32bit。上送频率f被设置为256。环形缓存的p_index为255，c_index为0，一个数据包的包长为64字节，源ip为13，目的ip为15。将该数据包插入数组的第(p_index+1)＝256个桶中，更新其源ip计数器的值为13，目的ip计数器的值为15，字节计数器的值为64，更新p_index为256，发现p_index modf＝0，生成一个数据包，连续携带从第(p_index-f+1)＝1个桶，到第p_index＝256个桶的所有缓存桶，然后上送cpu，cpu将上送的流表表项插入无错数据结构，例如哈希表中，从而统计二元组《源ip，目的ip》的流量，实现流量统计。随后，将c_index更新为256。
34.图4是本实施例的基于towersketch和可驱逐流表的数据中心流量统计方法的整体流程，包括以下步骤：
35.1)数据包《源ip，目的ip，字节数》进入交换机；
36.2)查找过滤器的towersketch，估计数据流包《源ip，目的ip》的总字节数，判断该数据包是否属于大流；
37.3)如果属于大流，则将属于大流的数据包插入流表，使用数据流标志《源ip，目的ip》查找流表，判断表项是否冲突；如果与原先的流表表项冲突，则驱逐原先的流表表项《原源ip，原目的ip》，并将该数据包插入流表；将驱逐的流表表项依次存入环形缓存(环形缓冲区)；如果与原先的流表表项不冲突，则使用数据包字节数更新流表的字节计数器；
38.4)判断是否触发上送，每当环形缓存中的流表表项到达一个阈值，则触发上送，将环形缓存中的流表表项生成一个数据包，并上送交换机的cpu；如果环形缓存中的流表表项未到达阈值，则不触发上送。
39.5)交换机根据规则转发/丢弃数据包。其中规则不仅包括通过查找路由表确定下一跳交换机/路由器，也包括通过查找访问控制列表(acl)确定是否要直接将包丢弃。
40.基于同一发明构思，本发明的另一实施例提供一种采用本发明方法的基于塔型摘要和可驱逐流表的数据中心流量统计系统，其包括：
41.过滤模块，用于将每一个数据包经过一个基于塔型摘要的过滤器，该过滤器判断该数据包是否属于大流；
42.流表插入模块，用于将被认为属于大流的数据包插入流表，如果与原先的流表表项冲突，则驱逐原先的流表表项，并将该数据包插入流表；
43.环形缓存模块，用于将驱逐的流表表项依次存入一个环形缓存，当环形缓存中的流表表项到达一个阈值时，将环形缓存中的流表表项生成一个数据包，从环形缓存中取出该数据包，并上送控制面进行流量统计。
44.基于同一发明构思，本发明的另一实施例提供一种电子装置(计算机、服务器、智能手机等)，其包括存储器和处理器，所述存储器存储计算机程序，所述计算机程序被配置为由所述处理器执行，所述计算机程序包括用于执行本发明方法中各步骤的指令。
45.基于同一发明构思，本发明的另一实施例提供一种计算机可读存储介质(如rom/ram、磁盘、光盘)，所述计算机可读存储介质存储计算机程序，所述计算机程序被计算机执行时，实现本发明方法的各个步骤。
46.以上公开的本发明的具体实施例，其目的在于帮助理解本发明的内容并据以实施，本领域的普通技术人员可以理解，在不脱离本发明的精神和范围内，各种替换、变化和修改都是可能的。本发明不应局限于本说明书的实施例所公开的内容，本发明的保护范围以权利要求书界定的范围为准。
技术特征：1.一种基于塔型摘要和可驱逐流表的数据中心流量统计方法，其特征在于，包括以下步骤：将每一个数据包经过一个基于塔型摘要的过滤器，该过滤器判断该数据包是否属于大流；将被认为属于大流的数据包插入流表，如果与原先的流表表项冲突，则驱逐原先的流表表项，并将该数据包插入流表；将驱逐的流表表项依次存入一个环形缓存，当环形缓存中的流表表项到达一个阈值时，将环形缓存中的流表表项生成一个数据包，从环形缓存中取出该数据包，并上送控制面进行流量统计。2.根据权利要求1所述的方法，其特征在于，所述过滤器由一个扩展的塔型摘要即towersketch组成，towersketch由多个内存开销相同的数组组成，每个数组由不同大小的字节计数器组成，用于统计包的字节数；为支持滑动窗口，为每个字节计数器分配一个时间戳计数器，字节计数器与其对应的时间戳计数器共同组成一个桶。3.根据权利要求2所述的方法，其特征在于，所述过滤器采用以下步骤判断数据包是否属于大流：当一个数据包进入交换机时，先从交换机获取当前时间戳t，以及其包长l；随后将该数据包插入过滤器中，插入操作为：为towersketch的第i行数组，以该数据包的二元组<源ip，目的ip>为输入，用哈希函数h
i
计算一个哈希值k
i
；如果第k
i
个桶中时间戳计数器的值与t不同，将该桶中的时间戳计数器的值更新为t，将该桶中的字节计数器更新为min(上界，l)；如果第k
i
个桶中时间戳计数器的值与t相同，将该桶中的字节计数器的值更新为min(上界，原计数器值+l)；随后输出查询值，其值为更新后的字节计数器值，将等于上界的查询值视为无穷大；得到过滤器每行数组的查询值后，将其与一个动态配置的阈值thresh比较，如果均大于该阈值，则认为该数据包是一个大流。4.根据权利要求1所述的方法，其特征在于，所述流表由一个桶数组组成，每个桶中包含三个计数器，分别记录源ip、目的ip以及经过的包的总字节数，分别称为源ip计数器、目的ip计数器以及字节计数器。5.根据权利要求4所述的方法，其特征在于，所述将被认为属于大流的数据包插入流表，包括：以被认为属于大流的数据包的二元组<源ip，目的ip>为输入，用哈希函数h计算一个哈希值k；如果第k个桶中的源ip计数器的值与目的ip计数器的值均与该数据包的源ip、目的ip值相同，将字节计数器的值更新为其当前值加插入的数据包包长；否则，驱逐原先桶中的数据，将源ip计数器的值与目的ip计数器的值更新为当前数据包的对应值，将字节计数器更新为当前包的包长。6.根据权利要求1所述的方法，其特征在于，所述环形缓存由一个长度为w的桶数组组成，每个桶中包含三个计数器，分别记录源ip、目的ip以及经过的包的总字节数，分别称为源ip计数器、目的ip计数器以及字节计数器；所述环形缓存维护两个索引，分别为称为生产者索引p_index与消费者索引c_index。生产者索引指向最新插入的流表表项在环形缓存中的位置，消费者索引指向最后被大包携带上送的流表表项在环形缓存中的位置，初始两个索引都设为0，设置一个上送频率f。
7.根据权利要求6所述的方法，其特征在于，每次有流表表项被驱逐时，如果所述环形缓存没有满，即(p_index+1)mod w不等于c_index，即将流表表项插入第(p_index+1)个桶中，并将p_index更新为(p_index+1)mod w；如果所述环形缓存已满，则选择不插入环形缓存，直接将被驱逐流表表项上送控制面；每当p_index更新后，如果p_index mod f＝0，则生成一个数据包，连续携带从第(p_index-f+1)个桶，到第p_index个桶的所有缓存桶，然后上送控制面；随后，将c_index更新为p_index。8.一种采用权利要求1～7中任一权利要求所述方法的基于塔型摘要和可驱逐流表的数据中心流量统计系统，其特征在于，包括：过滤模块，用于将每一个数据包经过一个基于塔型摘要的过滤器，该过滤器判断该数据包是否属于大流；流表插入模块，用于将被认为属于大流的数据包插入流表，如果与原先的流表表项冲突，则驱逐原先的流表表项，并将该数据包插入流表；环形缓存模块，用于将驱逐的流表表项依次存入一个环形缓存，当环形缓存中的流表表项到达一个阈值时，将环形缓存中的流表表项生成一个数据包，从环形缓存中取出该数据包，并上送控制面进行流量统计。9.一种电子装置，其特征在于，包括存储器和处理器，所述存储器存储计算机程序，所述计算机程序被配置为由所述处理器执行，所述计算机程序包括用于执行权利要求1～7中任一权利要求所述方法的指令。10.一种计算机可读存储介质，其特征在于，所述计算机可读存储介质存储计算机程序，所述计算机程序被计算机执行时，实现权利要求1～7中任一权利要求所述的方法。
技术总结本发明涉及一种基于塔型摘要和可驱逐流表的数据中心流量统计方法和系统。该方法的步骤包括：将每一个数据包经过一个基于塔型摘要的过滤器，该过滤器判断该数据包是否属于大流；将被认为属于大流的数据包插入流表，如果与原先的流表表项冲突，则驱逐原先的流表表项，并将该数据包插入流表；将驱逐的流表表项依次存入一个环形缓存，当环形缓存中的流表表项到达一个阈值时，将环形缓存中的流表表项生成一个数据包，从环形缓存中取出该数据包，并上送控制面进行流量统计。本发明可以被部署在可编程交换机上，在保证不高估的条件下高效地统计二元组<源IP，目的IP>的流量。目的IP>的流量。目的IP>的流量。
技术研发人员：杨仝 赵义凯 杨凯程
受保护的技术使用者：北京大学
技术研发日：2022.03.18
技术公布日：2022/7/5
