摘要：
在软件定义的网络（SDN）中，统计信息对于不同的应用至关重要，例如流量工程，流重新路由和攻击检测。
由于某些资源通常受限于SDN交换机，因此基于流表或采样的流量测量变得不可行sketch，通过监视具有固定大小的内存的每个数据包提供了一个有前途的构建基块，用于填补这一空白。尽管已经设计了许多有效的sketch，但我们的分析表明，现有的基于sketch的测量解决方案可能会在交换机上承受大量的计算开销，尤其是在高流量负载下，这会严重干扰交换机的基本功能。
提出了CountMax，这是一种用于流量测量的轻量级协作sketch，可以实现低摊销的处理开销和严格的估计范围，以跟踪SDN中的大流量。本文将讨论如何应用CountMax来支持各种应用程序，目前也已经在开放式交换机上实现了建议的算法，测试床实验和广泛的仿真结果表明，与相同内存大小下的现有解决方案相比，CountMax仅消耗1/3-1/2的计算开销，并且将平均估计误差降低了20％–30％。
问题/背景：
SDN交换机上有限的资源给流量测量带来了额外的困难，具体来说，三种类型的资源是主要关注的问题：
- 三进制内容可寻址内存（TCAM）资源
- SRAM资源
- 计算资源
SDN交换机具有用于数据包转发的特殊硬件，另外，按照OpenFlow标准的规定，每个具有OpenFlow功能的交换机都有一个软件实现的OpenFlow代理（OFA），用于计算除数据包转发以外的其他功能，该转发通常在具有有限处理能力的低端CPU上运行，这些资源限制无疑限制了如何在网络中测量单个流量。
流量测量的第一种方法是使用SDN中基于TCAM的流表：根据Openflow的规定，每个流条目都可以为匹配的流统计流量统计信息，但是流表的条目数是有限的。当流量太多无法容纳在流量表中时，虽然可以使用聚合路径以服务所有流量，但是由于许多流与一个流条目匹配，汇总这些流的流量后，难以通过基于TCAM的流表获得每个单独流的流量大小。
第二种方法基于流量采样：例如，当今的SDN交换机支持的NetFlow和sFlow，然而数据包采样固有地具有低的测量精度，并且仅实现粗粒度的测量，尽管可以通过提高采样率甚至记录所有流量来提高测量精度，但是内存/计算资源的使用将急剧增加，并在高速网络中引起可扩展性问题。
流量测量的第三种方法是使用sketch，它可以对单个流量进行细粒度的测量，sketch是紧凑的数据结构，该结构使用特殊的算法来汇总所有数据包的流量统计信息，而这些数据包使用的内存较小，并且存在一定的错误。在不同的场景下，有许多不同的基于sketch的解决方案可以解决测量精度与资源使用之间的不同折衷。
最大k（或top-k）流的统计信息对于许多应用程序来说很重要，因此应该设计有效的sketch以获得top-k统计信息，并且我们期望基于sketch的度量应引起较低的计算开销，以便可以有效地应用于SDN（甚至在高速应用场景中）。
我们注意到，由于每个交换机上的CPU负责流规则设置，端口统计信息收集和流量测量等，因此流量测量的高计算开销或高CPU利用率将对其他重要操作产生负面影响，从而减少网络性能。有两个重要的sketch，CountSketch和FSS，用于top-k流量测量，虽然这些sketch可以区分大象流并获得其流量统计信息，但这两种解决方案都有一个关键的缺点——交换机上的计算开销更高。
即使在高流量负载下，我们也应该设计一种具有精确流量估算和内存/计算资源效率的测量解决方案。
解决方案：
提出了一种轻量级的协作流量测量工具，称为CountMax，用于数据包处理。
与SketchVisor ，CountSketch和FSS相比，CountMax除了具有存储效率外，还具有以下显着优势：当接收到一个数据包时，CountMax将仅对其中的每一行执行一次哈希操作和一项加法操作。由于CountMax sketch支持在不同的交换机上进行协作的测量任务，因此每个交换机仅处理部分流量以进行有效的流量测量，结果它在保持测量精度的同时显着减少了计算开销。
本文提出了一个新的top-k sketch，该sketch可以实现较低的摊销处理开销和严格的估计范围，以跟踪这些大流量，除此之外还讨论如何应用算法来支持针对不同类型的流量统计信息的各种测量任务。
实现细节：
记录流量类似于Count-Min，维护一个具有w列和d行以及一系列d个不同哈希函数{h1，...，hd}的位图，每个哈希函数hj将任何输入（例如，五元组流ID）映射到0到w − 1之间的随机整数：hj：{...}→{0，...，w − 1}位图有两个字段：密钥和计数器，位图和哈希函数集形成sketch S。
流程查询对于流程fi：
对所有行重复上述查询操作，然后选择最大的一个（表示为aˆi）作为估计：
countMax的脆弱性分析：
论文描述功能实现的就只有这一小段算法而已，只能反复看，最后按自己的笔记研究它结构的结论来说，如果攻击使用的流哈希值一样，或者说以一种波动的形式攻击，一个流很大一个流很小，流size的差值其实就很接近两个流size的合，这样可能能做到让它查询到一个错误的max。
看结构看了半天才弄懂原理，晚上还得赶软工，有想到其他攻击的方法再说吧，暂时没有特别的想法。
网友评论