一种新的数据包公平抽样算法

互联网作为20世纪发展最为迅速的技术之一,已经成为现代信息社会最重要的基础设施,成为国家进步和社会发展的重要支柱。本文针对现有数据包抽样算法小流估计误差大的缺陷,提出一种新的数据包抽样算法。该算法根据到达数据包所属流大小的估计值设置包抽样率,使得大流所含数据包抽样率低,小流所含数据包抽样率高。理论分析和实验结果均表明,与已有算法相比,该算法具有更高的准确性和良好的扩展性,更适合于工程应用。     

网络自适应公平分组抽样算法研究

针对SGS(sketch guided sampling)的缺陷,提出了一种网络自适应公平抽样算法.根据抽样分组估计出值流量大小,并依据该值调整抽样比,使之适应于流量变化,从而达到对各种流的公平抽样的效果.对算法的相关性质进行了证明与分析,基于实际互联网数据进行了实验比较,实验结果表明,该算法具有准确性、自适应性、易于工程实现等优点.     

基于自组织的鲁棒非线性维数约减算法

现有的非线性维数约减算法需要求解大尺度特征值问题．由于特征值问题至少二次的计算复杂性,这类算法在大样本集上的应用较受限制．此外,现有算法的全局优化机制对于噪声较为敏感,且需要考虑“病态矩阵”的计算精度问题．提出时间复杂性为O(NlogN)的自组织非线性维数约减算法SIE.SIE的主要计算过程是局域的,可提高算法抗噪性、回避病态矩阵的计算精度问题．仿真表明,对于无噪数据和含噪数据,SIE均可获得优化或近似优化的重构质量．     

一种基于包速率自适应的报文抽样算法*

针对NetFlow抽样概率需手动配置的缺陷,提出了一种基于包速率自适应的分组抽样算法。通过测量包速率,采用预定义测量误差的方法,根据包速率的变化自适应地调整抽样概率,从而在有限资源情况下达到控制测量误差的目的。基于实际互联网数据进行了实验比较,结果显示：与传统的NetFlow算法相比,该方法易于实现,测量误差可控,具有高效性和准确性,同时具有资源节约性。     

基于迭代方法的流数估计算法

流数估计是网络管控的重要参考尺度,对网络流量全局特征信息的深入挖掘具有重要意义.针对目前已有的多种估计算法以过度消耗测量设备存储资源和计算资源提高估计精度的缺陷,采用报文抽样技术,提出一种新的迭代收敛型估计算法.实验测试表明,该算法在估计精度和内存消耗上优于EM算法,在迭代更新上优于Iteration算法.     

基于动态计数型过滤器的网络流公平抽样机制

传统的包抽样方法对每一个数据包都以同等的比率抽取,这样就导致了大部分被抽中的是大流,而短流和一般流非常少。高速网络的流量检测需要全面的流信息。针对传统流抽样的缺陷,结合现有的SGS(Sketch Guided Sampling)抽样比与流量成反比的公平抽样思想和动态计数型过滤器,提出更加高效的公平抽样算法DCFS(Dynamic Count Fair Sampling)。DCFS算法使用动态统计过滤器DCF(Dynamic Count Filter)统计流量,相对于SGS算法该方法空间更加高效,而且估计准确性也更好。     

基于近似方法的抽样报文流数估计算法

维护每个报文的流记录需要占用大量测量资源.目前已有多种抽样技术估计网络流统计信息,然而精确地估计出流数统计信息是目前的研究难点.提出了Integral和Iteration 两种基于报文抽样样本估计网络流数的算法.Integral算法只需使用抽样流长为1的流数信息就可以近似推导出未抽样的流数.Iteration算法通过建立迭代函数估计未抽样流数,然后根据未抽样流数和已抽样的流数推断出原始流量的流数.采用CERNET(China education andresearch network)骨干网络链路数据将这两种算法与EM(expectation maximization)算法进行对比,表明Iteration算法具有较好的精度和性能.     

非线性维数约减算法在文档聚类中的应用

提出一种非线性维数约减算法——自组织等距嵌入实现高维文档数据的压缩,并在文档聚类实验中,与经典的线性维数约减算法—隐含语义索引进行了比较研究。实验结果表明,在复杂度显著低于LSI算法的同时,SIE算法取得了优于LSI算法的性能,且高于基准性能。     

基于局域主方向重构的适应性非线性维数约减

现有的主要非线性维数约减算法,如SIE和Isomap等,其邻域参数的设定是全局性的。仿真表明,对于局域流形结构差异较大的数据集,全局一致的邻域参数可能无法获得合理的嵌入结果。为此给出基于局域主方向重构的适应性邻域选择算法。算法首先为每个参考点选择一个邻域集,使各邻域集近似处于局域主线性子空间,并计算各邻域集的基向量集;再由基向量集对各邻域点的线性拟合误差判定该邻域点与主线性子空间的偏离程度,删除偏离较大的点。仿真表明,基于局域主方向重构的适应性邻域选择可有效处理局域流形结构差异较大的数据集;且相对于已有的适应性邻域选择算法,可以更好屏蔽靠近参考点的孤立噪声点及较大的空间曲率导致的虚假连通性。     

一种基于DTBF的公平队列保障机制及产业化研究

许多基于队列的机制被提出,用于对带宽进行管理控制,以解决带宽分配和流量负载均衡问题。但是,它们在实际应用中没有消除链路层流控对传输层性能的影响,对TCP性 能造成一定的下降,使带宽利用率不够高。本文首先给出基于令牌分配的流量数学模型,设计了一种基于动态分配令牌的优化算法来解决逻辑链路间的流量控制问题,然后 用已有的“公平队列”技术来解决控制带宽资源的使用问题,并给出了相关的产业化研究和讨论。     

基于DCF的资源可控流抽样

Cisco的NetFlow是流测量中广泛应用的方案,但因其采用静态抽样率,当网络流量突然上升时,消耗过多的路由器资源,甚至影响路由器的正常转发功能。提出了基于DCF的资源可控流抽样,对测量间隔内到达的报文采取固定数量的抽样,并采用DCF哈希算法维护流记录,有效控制了资源的消耗。理论和实验分析结果表明,该方法具有抽样率自适应性、简单性、资源可控性,同时不失准确性。     

一种改进的自适应流量采样方法

高速链路对实时网络流量监测提出挑战.由于流量采集分析设备性能的限制,采用精确、高效的采样方法进行流量监测分析已成为必然.最简单的固定概率采样能监测较大业务流,但往往忽略掉比例几乎超过80%的较小业务流.数据流算法可以实时高效采集高速链路数据,基于该算法的SGS(sketch guided sampling)采样技术可以实时准确估计流大小分布,但当采样速率增大到监测系统处理能力最大值时,该方法的准确性迅速降低.基于SGS方法,提出一种自适应实时网络流量的采样方法SRGS(sketch and resources guided sampling).该方法将监测系统处理能力作为采样概率调节的一个重要参数.实验结果显示,SRGS方法能够及时根据当前流大小和监测系统处理能力,调节数据包采样概率,准确性高于SGS方法.     

基于NetFlow的特征感知自适应的流采样方法

采样是网络异常检测中数据采集的主要方法。而网络流的持续时间、数据包的大小、异常流量出现的频率等都在不断变化,给准确的采样带来很多负面的影响。为此,提出了特征感知的自适应采样技术,在流量特征不断变化的情况下可以自动调整采样率,并将它和随机采样技术、选择采样技术进行比较,研究了这些采样技术在网络行为分析系统中保留网络特征的能力,实验结果表明此方法在保留网络特征和异常检测质量评估中,明显优于其他方法。     

自适应网络往返时延采样方法

在讨论周期性数据采样算法弊端的基础上,提出自适应往返时延（RTT）的采样算法。该算法以时延变化率作为动态控制采样频率的主要依据,根据网络时延变化的缓急自动调整采样时间间隔。通过实验分析证明,该算法实现简单,可有效地跟踪网络RTT变化情况,从总体上减少采样工作量,减轻因网络测量而给网络带来的额外负载。     

一种新的基于SCBF的流抽样测量算法研究

为提高流测量系统的运行效率,减少其所需存储资源,提出了一种改进的测量并维护其流信息的算法——基于拆分型计数Bloom Filters（Split Counting Bloom Filters）的流抽样。该算法采用基于报文的抽样来实现流抽样,不仅可以使用较少系统资源来维护流信息,同时可适用于不同流量的测量点,提高了测量系统的准确性和可扩展性。     

基于数据包抽样的互联网业务流精确分类*

为实时精确地分类业务流,详细分析了负载特征在业务流中各数据包间位置的分布特性,原创性地提出了一种基于载荷特征检测的互联网业务早期分类方法ERBDPI。其基本思想是仅抽取业务流特征丰富的前几个数据包进行负载特征匹配,从而在连接开始阶段即可识别出业务类型。对ERBDPI进行了详细的理论分析和骨干网真实流量检测,结果表明 ,通过选取合适的数据包抽样个数,ERBDPI可在包抽样比下降至传统抽样方法的1/5的情况下获得95%以上的分类精确度,从而适合用于在线实时检测。     

一种基于BLS签名的优化公平交换协议

公平交换协议是构造电子商务系统的最基本工具。BLS短签名是双线性密码学中应用最为广泛的密码元件之一。基于BLS短签名,提出了一种优化公平交换协议,并分析了其安全性与运行效率。     

基于随机游走的大规模图中节点对采样算法

社会网络中的节点对采样可用于大规模社会网络的好友预测和用户兴趣识别.当整个网络的拓扑结构不完全或者随机选择用户的代价很高时,传统的均匀顶点采样方法的性能迅速下降.为此,提出了一种基于随机游走的大规模图中节点对采样算法.首先对社会网络的节点对采样进行了系统分析,对不同跳数下的节点对进行了定义;然后将社会网络转换成等价的网络图.新图中的顶点是原图中的边,新图中边的两个顶点是原图中含有相同顶点的两条边.最后,在新图上应用随机游走模型对节点对进行采样.实验结果表明,提出的方法统计误差小、执行效率高,性能明显优于均匀节点采样的相关算法.