从美国大选预测看流量计算的准确性

        1. 引言

        美国大选已进入白热化阶段,双方爆料不断,斗争之激烈堪比宫廷斗争剧, 11月5号几乎出现了阿扁一颗子弹穿肚皮的场景。很多专家利用计算机模型和数据分析在预测最终结果。据外媒报道,一个由印度企业开发的MogIA 系统从Google、Facebook、Twitter和YouTube上收集超过2000万个数据点并进行分析后,预测特朗普将会获得今年美国大选的最终胜利【1】。而Unanimous A.I系统通过实时收集选民的反馈意见加上AI模型得出希拉里将以微弱优势胜出【2】。我们华人界的自然语言处理牛人也利用他开发的NLP大数据平台针对社交媒体做了很多有意义的预测【3】。各种预测反复提到由于数据量太大,只好使用抽样技术(sampling)选取少量案例进行分析。那么抽样分析的准确性如何呢?

        大选的准确性还真不好说,里面的偶然因数太多;但技术问题如果也采用抽样技术解决,其准确度会有多高呢? 我们以网络流量计算问题展开讨论。

        2. 网络流量计算

        简单的网络流量问题是指计算单位时间内有多少比特(bits)通过了某个节点,由于因特网是分层结构的,即使这一简单问题针对不同层次的网络协议,问题也会从简单变到复杂的。

        一般来说,网络设备(交换机或路由器)某一端口的流量是一个简单的加法运算问题;通过硬件计数器(SNMP counters)对全流量而不是抽样进行计算就能非常准确地计算出来端口流量。但是网络传输层TCP的流量计算就非常复杂了。例如:在万兆(10G)压力下,从上千万个TCP流中挑出某一条流,这本身已经是一个非常有挑战性的问题了,更不要说精确地计算这条TCP的流量了!不得已实践中只好采用抽样的方法来解决。思科提出的Netflow V9是一种经常用的抽样计算方法(1:1000)【4】,这种抽样方法的计算准确性是我们讨论的重点。

        复杂的网络流量特征问题还包括: 流量中应用的识别, 即传输层流量中各种网络协议的分布。例如: 多少是HTTP网页的流量,多少是HTTPs加密的流量等等。 如果还要计算TCP流的重传率、延迟、流总数、包长分布、TopN等特征的话,那问题就变得更加复杂。

        下面来讨论抽样计算的误差有多大呢?


        3. 抽样的误差?

        流量计算使用采样方法是为了平衡准确性和高性能之间的相互制约,大流量下可以通过减少采样率来解决性能限制。如何在适当地采样率的基础上保持精度是一门艺术。下面介绍一下Netflow在路由器里是如何实现的。首先一条TCP流由协议头的五元组刻画:

(IPsrc, IPdst, Portsrc, Portdst,Protocol)


Figure 1. Netflow 实现框架和潜在问题


        在IP层的转发引擎中,一旦看到一条新的TCP流(报头里有SYN位)就把这条流插入Netflow的cache流表里(见Figure 1)。由于cache的空间有限,一般采用采样技术(1:N)来检查报文头的。当一条流结束时,这条流的记录连同它的统计信息一起输出到Netflow的收集器中。如果一条流15秒内没有任何报文来过,这条流也会被输出。可见TIMEOUT阈值的设计也非常重要。

        从Figure 1还可以看出,转发引擎是硬件实现的,检查出一条新的TCP流是很快的。但flow cache是由软件来完成的,不但空间有限,而且CPU对流表更新的执行效率也没有硬件高,实际中必须用采样的方法来弥补性能上的缺陷。Netflow采样带来的问题主要有【6】:

        • 如果流表被大量的小流量给占满了(DoS攻击时容易发生),正常流量统计会不准。

        • 一个固定的采样蘋率在某些流量下会计算不准。 例如: 流量小时应该多采点,流量大时,应该少采点。实际操作起来,运维人员很难选定采样频率。

        • 跨时间段的分析不好做。 如果一条TCP流横跨两个时间段,而只有在结束时输出其流量信息,那么在前一个时间段流量少算了,在后一时间段流量反而多算了!如何弥补这差异是个难题。

        虽然问题诸多,但矮子里拔将军,Netflow由于其简洁性在实际应用中还是被广泛使用着。 那么实际的误差有多少呢?下面通过对Timeout和采样频率的变化来研究TCP的总流数的准确率和采样频率、timeout这三者之间的关系。

Figure 2. 采样分析总流数随Timeout和采样频率的误差



        Figure 2给出了TCP总流数的准确度和timeout、采样频率的关系【5】。 值得指出的是由于最高的误差高达23%,实际中采样的频率选择至关重要。采样的方法也有多种,systematic, random, stratified and biased 【7】. 例如: 只挑TCP里有SYN的报文就是一种biased采样,它对计算总的流数特别有用。但没有那种采样是万能的,用途广的还是基于报文的1:N抽样(systematic)比较可靠。学术界有人提出了adaptive sampling【6】, 但要更新路由器的软件才行。


        4. 总结

        采用抽样的方法来计算流量特征总是有误差的,人们发现:

        • 单包能决定的特征一般对采样频率的依赖没有那么大, 例如:报文的总数;

        • 多包才能决定的特征对采样频率的依赖相比来说较大。例如:TCP活跃流的总数,这时要看TCP里SYN的报文才有可能推导出来。

        对于协议识别问题,一般要看一条流的头几个报文,即使用上了人工智能的ML方法,10%的误差率是很常见的【7】。所以实际中如果能做全流量的分析是最好的。我们利用多核并行化技术,用无锁设计来实现并行程序,一举解决了网络流量可视化的计算难题,通过全流量的大数据分析及大地提高了各种流量特征统计的精度。

        10%以上的误差在网络流量计算中勉强可用,在今年这么激烈的选举中恐怕就不适合了,个别摇摆州的差距就是1%--4%。更何况在文【1】分析中,只看谁关注了谁?没有跟踪关注了后说了哪些话,那么分析就有问题了!这种分析类似网络流量分析中抽取多包特征一样,不多看几眼无法看清楚事情的本质。所以舆情分析不做基于自然语言的语义分析(semantic analysis)是不太准的。这里【3】做的分析是首先通过抽取每人发言的语气判断是否是拥护候选人,然后再做大数据的统计分析。通过自然语言理解处理社交媒体数据,这个要比【1】在技术上领先一代。期待着舆情分析也能研制出全流量的语义分析技术,大幅度地提高预测的精度。






        Reference:

        【1】 Businessinsider.com, "An artificial intelligence system that correctly predicted the last 3 elections says Trump will win",Oct. 29, 2016
        【2】 TechRepublic.com, "Swarm AI predicts tight election, gives edge to Clinton", Nov. 1, 2016
        【3】 Liweinlp.com,"大数据跟踪美大选每日更新,希拉里成功反击,拉川普下水", Nov. 1, 2016
        【4】 Cisco Systems, " http://www.cisco.com/c/en/us/products/collateral/ios-nx-os-software/ios-netflow/prod_white_paper0900aecd80406232.html", May, 2012
        【5】 Nick Duffield, Carsten Lund, and Mikkel Thorup,"Properties and prediction of flow statistics from sampled packet streams", In SIGCOMM Measurement Workshop, November 2002.
        【6】 Cristian Estan, Ken Keys, David Moore, George Varghese, "Build a Better NetFlow", in Proc. of SIGCOMM, Aug., 2004
        【7】 Valentín Carela-Español,"Analysis of the impact of sampling on NetFlow traffic classification", Computer Network, Vol 55, Issue 5, Pages 1083–1099, Apr., 2011.


© 2013-2019 IDO-NET All rights reserved.