信息学院李晓明-杨仝课题组在网络大数据流核默算法研究中取得紧张进展

近日，北京大学信息科学技术学院李晓明教授、杨仝助理研究员课题组在计算机网络领域顶级期刊《计算机协会数据通讯专业爱好组计算机通讯评论》（ACM SIGCOMM CCR）和《电气电子工程师学会网络汇刊》（IEEE Transactions on Networking）上各发表一篇论文。其中，题为《加速软件环境的网络测量》（Accelerating network measurement in software）的论文为在该期刊所发表的北京大学第一作者单位的首篇论文；第一作者为信息学院本科生周洋，通信作者为杨仝。

针对多种软件流量测量平台速度慢，难以应对高速网络流量测量需求的近况，课题组提出一种通用的测量加速框架，基本思想是：先通过一个极小的数据结构进行高速流量聚合，然后根据需求将聚合后的数据记录到测量结构中。将该加速框架应用到七种测量平台及算法后，在正确率不变的情况下，处理速度平均进步了5.7倍。

ACM SIGCOMM CCR是计算机网络领域排名第一的会议（ACM SIGCOMM）所对应的在线刊物，在业界享有极高的声誉。中国大陆第一作者单位论文迄今不超过10篇。

另一项工作研究的是路由查找这一计算机网络的核心题目。互联网的核心是主干网，主干网由路由器连接而成，而路由器的性能瓶颈在于路由表查找速度。因此，路由表查找算法的性能决定了互联网性能。随着路由表的规模呈指数级增加，对其查找速度和扩展性提出了伟大的挑衅。课题组创新性地提出二维分割和关键层叶推、继续算法，不仅将IPv4（互联网协议第四版）路由表查找速度进步一个数量级，而且实现了对大规模IPv6（互联网协议第六版）路由表的高速查找和更新。理论和实验效果表现，较现有最新的IPv4和IPv6路由表查找算法而言，该算法具有明显的速度和内存占用上风，并可同时支撑多种软硬件平台。

编辑：知远