高速网络测量的普适在线压缩统计理论与方法

网络测量为网络和各种应用的管理、优化和控制提供有效支撑，是下一代互联网发展的必备要求。随着网络线速和业务流数目的增加，物理存储器件在容量和速度方面的限制成为网络测量的巨大挑战，本课题研究网络测量当前迫切需要解决的基础性科学问题，探索高速网络测量数据的普适在线压缩统计理论与方法，通过数学模型抽象和实验验证的手段，采用理论求证、软件仿真和实验床搭建等方法，力图从三个方面寻求对现有网络测量技术的突破和创新：1)在保证测量精度的前提下在线压缩测量信息，满足至少20 Gbps链路的测量数据的实时更新和查询；2)从理论上提供一种相对普遍适用于各种网络测量统计量特点的在线压缩方法，满足不同统计量的测量要求；3)通过自适应调整测量时间间隔进一步降低测量信息传输的带宽占用。本项目研究的高速网络测量的普适在线压缩统计理论与方法对下一代互联网的发展，尤其是对高速网络测量的实现具有重要的理论意义和应用前景。

互联网经过不断地进化，已经发展成为承载各种业务的全球通信基础设施，其形式也由于移动、异构、高带宽以及新型业务的发展而变得日益复杂。无论是将网络测量用于新业务特性的认知，还是对新网络和新业务的管理控制，网络测量都将是未来互联网最基础的功能组件，为网络及其各种应用的管理、优化与控制提供有效的支撑。本课题发表论文32篇，其中SCI检索10篇，计算机学会推荐A类国际会议3篇，IEEE期刊4篇。主要研究成果包括：1) 研究自适应的非线性采样中的参数调整的问题，提出了一种参数自调整的算法，当计数器溢出时，该算法能够将参数放大到一个均衡点并进行归一化。实验结果表明，在内存开销相同的条件下，带有参数自调整算法的非线性采样方法对于实际流量，帕累托分布和指数分布的流量的统计精确度分别提高了近89倍，70倍和370倍。2) 研究利用SRAM开展高速业务量统计的机制，提出了DIScount Counting（DISCO）方法。在相同的存储开销下，该方法和相关的工作相比，具有更好的精确度。同时，存储开销随着流量大小的增长次线性地增长，使得计数器具有很好的可扩展性。使用网络处理器IXP2850的1个微处理引擎和96Kb的存储代价可以达到11.1Gbps的吞吐率，吞吐率随着微处理引擎数目的增大（不超过4个时）以接近线性的方式增长。3) 研究BGP测量探针的有效部署问题，以此来减小BGP测量系统的开销。证明了VP选择问题是NP完全问题，并提出了相应的近似算法来求解该问题。通过实验验证，只要110个VP足够观察到原来需要438个VP才能观察到的信息。另外，利用不同时期的数据运用VP选择算法，发现性能是稳定的。4) 通过网络测量手段研究了两种潜在的域间路由的多样性，即邻居AS间关系松弛转变和与同在一个IXP的其他AS建立BGP会话两种方式下的潜在路由，这两种潜在路由多样性可以被用来恢复路径失效之后路由。利用迄今为止见诸文献中最完整的AS网络拓扑来进行这两种潜在路由多样性的评价，在不同的互联网失效模型下，大约40％至80％的失效源/目的AS之间的路径可以得到恢复。5) 提出的SACK2算法有效地解决了SYN洪泛检测面临的多项挑战，包括：消除因攻击者伪造各种控制包而导致的漏判、区分端口扫描、快速报告攻击的开始和结束、以及报告遭受攻击的IP和端口对等。