学院概况

网络所杨仝课题组数据流测量取得重要进展

发布时间:2021-03-09

信息来源:北京大学星力捕鱼|星力正版捕鱼|星力手机捕鱼_

日前,北京大学捕鱼平台_星力捕鱼平台_正规捕鱼游戏平台_网络与信息系统研究所杨仝副教授课题组在计算机协会数据管理专业组年会(Annual Conference of the ACM Special Interest Group on Management of Data, SIGMOD2021)上发表两篇论文《利用Clock-Sketch挖掘数据流中Item Batch信息》(Out of Many We are One: Measuring Item Batch with Clock-Sktetch)与《突发检测Sketch:高效检测数据流中流量突发的手段》(BurstSketch: Finding Bursts in Data Streams),在计算机网络设计与实现研讨会(USENIX Symposium on Networked System Design and Implementation,NSDI 2021)上发表论文《LightGuardian:利用Sketchlet测量网络数据流信息》(LightGuardian: A Full-Visibility, Lightweight, In-band Telemetry System Using Sketchlet)。

这三篇文章的第一作者分别为北京大学四年级本科生陈沛庆,二年级本科生钟正与一年级博士生赵义凯。

作为数据库与数据管理领域的顶级会议与风向标,ACM SIGMOD收录的论文对学术界和工业界均具有领导性的影响,每年录用的论文一般不超过90篇。

在《利用Clock-Sketch挖掘数据流中Item Batch信息》一文SIGMOD 21中,杨仝等人研究了多种数据流应用场景,并总结出其中Item Batch特征。Item Batch指数据流中相同ID的元素呈现密集分布的特征(图1)。文章指出,Item Batch测量在优化缓存算法,Burst检测,网络流APT检测,商品点击流分析等多种场景能够起到促进作用。他们还设计了Clock-Sketch数据结构,巧妙地将缓存Clock算法与Sketch算法类结合,对Item Batch进行全方位测量。在高速数据流场景下,Clock-Sketch在Item Batch检测准确性,吞吐率,检测任务通用性上都优于现有算法。

(图1)

突发检测Sketch:高效检测数据流中流量突发的手段》一文(SIGMOD 21)中,杨仝等人研究了数据流中的常见模式——突发。突发像一个脉冲,指一个频繁元素的速度发生了突增并且紧跟着一个突减。突发在许多领域都有应用,如数据挖掘,网络流量管理,数据流管理,金融风险管理等等。为了能高速而实时地检测突发,文章设计了突发检测Sketch,一种能高效而准确地检测突发的概率算法。该算法是第一个结合sketch以检测突发的算法(图2),具有准确、紧凑、高速、通用、易实现等优点。

(图2)

USENIX NSDI是USENIX旗下的旗舰会议,也是计算机网络系统领域的顶级会议。之前北京大学尚未顶级会议上发表论文。

LightGuardian:利用Sketchlet测量网络数据流信息》一文(NSDI 21)中,杨仝等人总结了理想的网络测量系统应该满足的三个原则:完全可见性、轻量性和鲁棒性,并首次提出了同时满足这些原则的测量系统LightGuardian(图3)。他们设计了一种能够被编码在数据包头中的轻量级数据结构sketchlet,并提出了一种能够测量大多数常见的网络流级别信息的sketch数据结构SuMax sketch。SuMax sketch能够被拆分成sketchlet在带内进行传输。LightGuardian借助sketchlet实现了理想测量系统的全部设计原则,是首个能够使用可忽略开销实现全流量测量的系统。

(图3)

杨仝课题组近年取得了多项代表性研究成果,例如:2017年在计算机网络领域排名第一的国际期刊《电气电子工程师学会网络汇刊》(IEEE Transaction on Networking)上发表北京大学首篇第一作者单位论文(第一作者为杨仝)2018年网络排名第一的国际会议SIGCOMM发表北京大学首篇第一单位论文。最近还有大四学生吴钰晗CCF A类期刊Transactions on Computers发表弹性Bloom filter论文,研二学生康照东CCF A类期刊TKDE发表四色过滤器论文。至今,杨仝在美国计算机协会专业委员会(ACM SIG)级论文中以第一作者和通讯作者身份斩获9篇论文。课题组以高年级本科生为主要力量,他们在研究工作中接受扎实的训练,得到海外名校认可,拿到了众多国际一流学校PHD offer,如CMU、伯克利、哈佛、密西根UW、UIUI佐治亚理工等。