低速率流淘汰与d-Left散列相结合的大流检测算法

网络中少量较高速率和较大数据量的流生成了网络的大部分流量;利用有限的存储空间有效地识别出这些数据流,对实施流量工程、缓解网络拥塞、改善网络传输具有非常重要的意义.随着网络技术的发展,传输链路的带宽容量和数据流的传输速率越来越高.具有高速报文转发能力的网络设备对数据流检测算法的处理提出了高的性能要求.将超过一定的数据量和传输速率的数据流定义为大流,提出了将低速流淘汰与d-Left散列表存储结构相结合的大流检测算法.为了满足高速网络传输的性能需求,使用d-Left散列表存储流检测的数据结构,将d-Left散列表的存储结构与流缓存替换相结合以实现高效的大流检测.通过低速率的淘汰,提高了检测算法的准确性.基于真实网络数据的测试结果表明：所提算法在相近的存储开销下保持了高的处理性能,其准确性优于LRU派生算法S-LRU和L-LRU以及CSS和WCSS检测算法.     

数据网格环境下副本淘汰策略的研究

为了在数据网格环境中不增加副本存储空间的条件下,能够很好地进行数据副本的淘汰,提出了一种改进副本淘汰算法.该算法利用权重函数兼顾访问时间和访问频率,在考虑副本传输代价的因素上引入动态调整因子μ,根据实际情况动态的调整副本传榆代价所占的比例.仿真实验结果表明,该算法在副本尺寸差异较大的情况下,可以大大减少副本淘汰误差,提高了网格结点的作业平均执行时间和网络有效利用率.     

基于流抽样和LRU的高速网络大流检测算法

在高速主干网络中,随着网络链路速率的不断提高和网络流数量的增加,如何及时、准确地检测出网络中的大流信息,成为目前网络流测量的热点问题。根据传统LRU算法由于突发性大量小流导致淘汰大流的测量缺陷和网络重尾分布的特点,提出一种新的识别大流的算法——基于流抽样和LRU的大流检测算法。算法通过流抽样技术过滤大部分的小流,并通过LRU算法识别大流信息,将过滤和识别过程分离,减少小流错误淘汰大流的可能性,提高算法测量准确性。分析算法的复杂度和漏检率,并通过实际试验数据分析了算法参数配置对于大流测量的准确性的影响。理论分析和仿真结果表明,与标准LRU算法和LRU_BF算法相比,在使用相同的存储空间下,新算法具有更高的测量准确性和实用性。     

一种高效的网络流记录表示方法

带宽和应用不断发展,迫切需要对应用业务的精细化网络流量进行持续监测.NetFlow的表示方法存在数据组织效率低等问题,导致传输开销过大、历史数据存储空间爆炸增长;聚合NetFlow表示方法又带来大量信息丢失.寻找一种高效的网络流记录表示方法对满足网络测量有着非常重要的意义.提出了一种新的方法——基于对象和应用的流量特征统计描述(TABSI),该方法以单位时间周期内各个监测对象在不同应用下的流量统计、流数目统计及分布为流量信息的基本描述单位,周期性地导出该信息来描述链路流量特征.理论分析表明TABSI比聚合NetFlow记录包含更多的信息量,能够很好地描述网络行为;且TABSI历史数据有效性更强.现网运行测试表明该方法可使传输数据量减少、存储组织高效查询分析更快、存储空间大大减少.     

一种SVM增量学习淘汰算法

基于SVM寻优问题的KKT条件和样本之间的关系,分析了样本增加后支持向量集的变化情况,支持向量在增量学习中的活动规律,提出了一种新的支持向量机增量学习遗忘机制--计数器淘汰算法.该算法只需设定一个参数,即可对训练数据进行有效的遗忘淘汰.通过对标准数据集的实验结果表明,使用该方法进行增量学习在保证训练精度的同时,能有效地提高训练速度并降低存储空间的占用.     

一种SVM增量训练淘汰算法

基于KKT条件分析了样本增加后支持向量集的变化情况,深入研究了支持向量分布特点,提出了一种新的支持向量机增量训练淘汰机制——挖心淘汰算法。该算法只需设定一个参数,即可对训练数据进行有效的遗忘淘汰。通过对标准数据集的实验结果表明,使用该方法进行增量训练在保证训练精度的同时,能有效地提高训练速度并降低存储空间的占用。     

路由器队列调度算法仿真研究

该文指出互联网技术的发展,带来了网络大流量业务的不断增加,特别是UDP业务数据急剧增加.由于UDP协议不具有拥塞控制能力,TCP协议具有拥塞控制能力,UDP数据极易阻塞网络链路,产生了严重的不公平性,影响了其他业务的进行.该文分析了路由器队列调度算法的原理,通过Opnet仿真,模拟了不同队列调度算法的拥塞状况,分析出采...     

天地一体化智能网络流量实时分类

天地一体化智能网络规模大,环境复杂,网络中流量业务类型繁多且流量具有突发性.本文结合Spark大数据分布式平台,根据流量的特点设计了SFFS-FCBF-C4.5(简称SFC)决策树分类模型,实现了大规模网络下流量的实时分类,以保障网络中资源的合理分配和利用.SFC算法是在C4.5决策树算法的基础上结合了改进后的快速相关滤波算法(Fast Correlation-Based Filter Solution, FCBF)和连续型属性值离散化算法,可以在有效去除冗余特征和降低模型复杂度的同时,提高模型分类的速度和准确率.仿真结果表明,SFC决策树分类模型相比传统的流量分类模型具有较好的稳定性和较高的准确率,可以很好的适应复杂多变的网络环境.同时,Spark大数据分布式平台的应用大幅度提高了大规模网络下流量分类的速度,能够对海量流量进行实时分类.     

基于聚类和一致Hash的数据布局算法

如何有效地对数据进行布局是大规模网络存储系统面临的重大挑战,需要一种能够自适应存储规模变化、公平有效的数据布局算法.提出的CCHDP(clustering-based and consistent hashing-aware data placement)算法将聚类算法与一致hash方法相结合,引入少量的虚拟设备,极大地减少了存储空间.理论和实验证明,CCHDP算法可以按照设备的权重公平地分布数据,自适应存储设备的增加和删除,在存储规模发生变化时迁移最少的数据量,并且可以快速地定位数据,对存储空间的消耗较少.     

基于数据中心流量特征的端到端流量估计算法

数据中心是云计算等大型分布式计算服务的基础,有效地设计与管理数据中心需要遵循数据中心网络的端到端流量特征。然而直接地测量网络的端到端流量需要耗费巨大的软件成本和硬件成本,并且由于数据中心网络结构的特殊性,传统的计算机网络采用的流量估计方法也无法适用于现有的数据中心网络。为解决以上问题,首先依据数据中心的资源分配和链路利用率情况提取出网络的粗粒度流量特征,在此基础上提出一种基于重力模型和网络层析技术的数据中心端到端流量估计算法。与现有的流量推理算法Tomogravity和ELIA在NS3搭建的不同规模的数据中心网络中进行性能对比,实验结果表明,所提算法能有效地利用提取出的粗粒度流量特征,在保证计算效率的前提下将计算准确度大幅提升,可满足当前数据中心网络实时获取端到端流量数据的需求。     

Sequential hashing: A flexible approach for unveiling significant patterns in high speed networks

Identification of significant patterns in network traffic, such as IPs or flows that contribute large volume (heavy hitters) or those that introduce large changes of volume (heavy changers), has many applications in accounting and network anomaly detection. As network speed and the number of flows grow rapidly, identifying heavy hitters/changers by tracking per-IP or per-flow statistics becomes infeasible due to both the computational overhead and memory requirements. In this paper, we propose SeqHash, a novel sequential hashing scheme that supports fast and accurate recovery of heavy hitters/changers, while requiring memory just slightly higher than the theoretical lower bound. SeqHash monitors data traffic using a sketch data structure that can flexibly trade-off between the memory usage and the computational overhead in a large range that can be utilized by different computer architectures for optimizing the overall performance. In addition, we propose statistically efficient algorithms for estimating the values of heavy hitters/changers. Using both mathematical analysis and experimental studies of Internet traces, we demonstrate that SeqHash can achieve the same accuracy as the existing methods do but using much less memory and computational overhead.     

全网异常流量簇的检测与确定机制

在网络安全管理领域,自动确定异常流量簇可为ISP分析和定位全网流量异常提供有效手段.提出了一种基于过滤的网络流数据的全网异常流量簇检测及确定机制.给出了问题的形式化描述和定义;扩展和改进了基于多维树的大流量簇检测方法,提出了灵活的“检测阈值”及“分裂值”的计算方法以改善大流量簇的检测精度;通过剪枝算法缩减了树的规模,提高了查找大流量簇的效率;给出了基于大流量簇确定异常流量簇的方法.实验表明该方法是可行的,可应用于全网异常诊断.     

Identifying heavy hitters in high-speed network monitoring

Identifying heavy hitters in a network traffic stream is important for a variety of network applications ranging from traffic engineering to anomaly detection such as detection of denial-of-service attacks. Existing methods generally examine newly arriving items in the stream, perform a small number of operations using a small amount of memory, and still provide guarantees on the identifying accuracy. In high-speed network monitoring, the update speed per item is extremely critical. However, so far as we kn...     

A hybrid local and distributed sketching design for accurate and scalable heavy key detection in network data streams

Real-time characterization of network traffic anomalies, such as heavy hitters and heavy changers, is critical for the robustness of operational networks, but its accuracy and scalability are challenged by the ever-increasing volume and diversity of network traffic. We address this problem by leveraging parallelization. We propose LD-Sketch, a data structure designed for accurate and scalable traffic anomaly detection using distributed architectures. LD-Sketch combines the classical counter-based and sketch-based techniques, and performs detection in two phases: local detection, which guarantees zero false negatives, and distributed detection, which reduces false positives by aggregating multiple detection results. We derive the error bounds and the space and time complexity for LD-Sketch. We further analyze the impact of ordering of data items on the memory usage and accuracy of LD-Sketch. We compare LD-Sketch with state-of-the-art sketch-based techniques by conducting experiments on traffic traces from a real-life 3G cellular data network. Our results demonstrate the accuracy and scalability of LD-Sketch over prior approaches.     

网络重要流检测方法综述

网络的管理与监测是网络领域的重要话题,这一领域的相关技术通常也称为网络测量(network measurement).网络重要流检测(network heavy hitter detection)是网络测量的一项关键技术,也是研究对象.重要流指占用网络资源(如带宽或发送的数据包数量)超过某一给定标准的流,检测重要流有助于快速识别网络异常,提升网络运行效率,但链路的高速化为其实现带来了挑战.按出现时间顺序,可将重要流检测方法划分为两大类:基于传统网络框架的和基于软件定义网络(SDN)框架的.围绕网络重要流检测相关的框架与算法,系统地总结其发展过程与研究现状,并尝试给出其未来可能的发展方向.     

Fast and accurate mining of correlated heavy hitters

The problem of mining correlated heavy hitters (CHH) from a two-dimensional data stream has been introduced recently, and a deterministic algorithm based on the use of the Misra–Gries algorithm has been proposed by Lahiri et al. to solve it. In this paper we present a new counter-based algorithm for tracking CHHs, formally prove its error bounds and correctness and show, through extensive experimental results, that our algorithm outperforms the Misra–Gries based algorithm with regard to accuracy and speed whilst requiring asymptotically much less space.     

无线Mesh网络中节点分级协作缓冲机制研究

在无线Mesh中,由于每个节点缓冲的数据量不同,可能会造成某些节点的缓冲区利用率低,某些节点因为缓冲任务繁重而进行频繁的数据置换操作,从而造成节点存储空间使用不均衡,降低数据缓冲的效率。提出了一种基于节点分级管理的协作缓冲算法,该算法为网络中的每个节点在网络中构造一个分布式缓冲区域,利用该缓冲区域来替代节点本身的缓冲区,通过合理地利用每个节点的存储空间,增加单个节点的数据缓冲能力。理论分析和实验结果表明,该算法可以有效提高数据访问命中率,减少缓冲区数据的置换操作,降低节点的能量消耗。     

基于稀疏矩阵的低复杂度安全网络编码算法

针对安全网络编码复杂度较大的问题,提出一种基于稀疏矩阵的安全网络编码算法。利用稀疏矩阵占用较少的存储空间和运算速度快的优点,在信源处将信源信息与稀疏矩阵进行矩阵变换操作,使得随机网络编码能以较高的概率达到信息论安全的要求。仿真结果表明,该算法能提高编解码速率,降低复杂度,减少存储空间。     

Token-ordered LRU: an effective page replacement policy and its implementation in Linux systems

Most computer systems use a global page replacement policy based on the LRU principle to approximately select a Least Recently Used page for a replacement in the entire user memory space. During execution interactions, a memory page can be marked as LRU even when its program is conducting page faults. We define the LRU pages under such a condition as false LRU pages because these LRU pages are not produced by program memory reference delays, which is inconsistent with the LRU principle. False LRU pages can significantly increase page faults, even cause system thrashing. This poses a more serious risk in a large parallel systems with distributed memories because of the existence of coordination among processes running on individual node. In the case, the process thrashing in a single node or a small number of nodes could severely affect other nodes running coordinating processes, even crash the whole system. In this paper, we focus on how to improve the page replacement algorithm running on one node.

After a careful study on characterizing the memory usage and the thrashing behaviors in the multi-programming system using LRU replacement. we propose an LRU replacement alternative, called token-ordered LRU, to eliminate or reduce the unnecessary page faults by effectively ordering and scheduling memory space allocations. Compared with traditional thrashing protection mechanisms such as load control, our policy allows more processes to keep running to support synchronous distributed process computing. We have implemented the token-ordered LRU algorithm in a Linux kernel to show its effectiveness.     

A Fine-Grained Parallel Memory Compaction Algorithm

Memory compaction is a technique for reclaiming cells containing garbage that are scattered over the memory space. More specifically, the memory cells are rearranged, so that all usable cells appear in one compact mass at one end of the area, and the remaining space at the other end can be recycled by the program. During this process, references are updated to point to the new locations. This process happens in place; no extra memory is needed. In addition to this, a sliding compaction algorithm preserves the relative order of the useful memory calls. Morris′s algorithm is such a well known sequential algorithm. In this paper, we present a program scheme that is a generalization of Morris′s algorithm, and that allows for parallel execution. Our scheme can be fine tuned for a particular implementation, taking into account the characteristics of the memory area and the hardware. The algorithm is space efficient, and runs in a time linear to the size of the memory area (the actual parameters are determined by the properties of the data to be compacted). As the algorithm is very fine grained, it has a nearly linear speedup, except in some uncommon cases. The memory area need not be contiguous, but must be globally accessible.