在国家自然科学基金项目(项目批准号:61202489,61672061)等资助下,北京大学网络与信息系统研究所李晓明、杨仝团队多年来一直围绕网络测量开展深入研究取得重要进展。研究成果以“Elastic Sketch: Adaptive and Fast Network-wide Measurements. (弹性Sketch:快速自适应网络范围测量)”,“HeavyGuardian: Separate and Guard Hot Items in Data Streams.(重甲卫士:分离并保护数据流中的热元素)”,“Cold Filter: A Meta-Framework for Faster and More Accurate Stream Processing.(冷元素过滤器:一种面向更快更准确流处理的元框架)”为题,分别在计算机顶级国际会议SIGCOMM 2018、SIGKDD 2018、SIGMOD 2018上发表。
互联网规模飞速扩展,新型网络及其协议不断涌现,以至于人类越来越难以全面、准确地理解和认识互联网。网络测量作为认识和理解网络的一个重要手段,是当前研究的热点问题之一。
针对传统基于采样样本的网络测量方法导致较大的误差和信息遗漏,杨仝等人创新性地提出附加式框架、通用数据结构和频数估计专用数据结构等记录单个数据包信息,从而实现网络流量信息的精确记录。更进一步提出弹性网络测量方法,设计了弹性sketch概率数据结构,该数据结构对网络带宽、CPU利用率和网络流量特征的变化具有很好的适应性。与传统算法不同,提出的算法基于一种数据结构可同时支持六种网络测量任务,具有很好的通用性,相比现有专用算法,测量精度提高2到273倍、速度提高40倍,显著提高了网络测量的速度和精度。目前该团队已在六种软硬件平台上实现该弹性sketch。该成果引起国内外学术界和工业界的广泛关注,为国家网络安全防护提供了技术支撑。
图1. 弹性测量网络架构
图2. 弹性sketch数据结构