• 科研快讯

我校首次在网络领域顶尖国际学术会议SIGCOMM发表长文

2023.06.06

复旦大学计算机科学技术学院徐扬教授科研团队的研究论文《BMW Tree: Large-scale, High-throughput and Modular PIFO Implementation using Balanced Multi-Way Sorting Tree》被ACM SIGCOMM 2023接收,论文的第一作者为博士生姚如意,第二作者为博士生张志禹,指导教师为徐扬教授和刘森青年副研究员。该工作联合了复旦大学微电子学院和纽约大学共同完成。

ACM SIGCOMM是国际通信网络领域的顶尖会议,以高质量、高影响力著称,在该会议几十年的历史上,第一单位是国内大陆科研院所的论文总数很少,这也是复旦大学首次以第一完成单位在SIGCOMM会议上发表学术成果。SIGCOMM 2023将于2023年9月10-14日在美国纽约市召开。

在网络设备中,数据包调度器对网络应用的服务质量起着至关重要的作用。传统的网络设备调度策略固化,通常只支持少量常见的调度算法供用户通过配置参数选择使用。然而在当前以数据中心网络为代表的复杂网络环境中,网络模型和流量模型愈发复杂,网络应用的调度目标也变得多种多样。随着新应用的不断出现,未来还可能出现新的未知的调度目标。传统固化的数据包调度器已经难以适用于多种调度目标的网络环境,需要可编程调度器来灵活便捷地实现各种调度算法。

可编程调度器数据结构示例:2叉平衡多路排序树

近几年国际上陆续有研究团队提出不同的可编程调度器设计方案,然而现有的方案无法兼顾高吞吐量、高可扩展性和高调度准确度这三个目标。针对该问题,论文设计了一种新型数据结构:平衡多路排序树(BMW-Tree),该数据结构具有节点模块化,“插入平衡性”好(Insertion-Balanced),支持流水线操作,以及支持准确调度等优点。基于此数据结构,论文设计了两种简单高效的硬件实现方案。第一种是基于寄存器的R-BMW方案,通过流水线设计,R-BMW能够取得与树深度无关的稳定高吞吐量。第二种方案(RPU-BMW)基于论文中提出的RPU(Ranking Processing Unit)处理引擎;通过将树节点存储在SRAM中,按需动态加载到RPU中进行排序操作,可以极大地降低寄存器的使用,取得极高的可扩展性。

论文将两种方案在Xilinx Alveo U200 FPGA加速卡上进行了原型实现。评估结果表明,与原始PIFO实现相比(SIGCOMM 2016论文),R-BMW在取得相似容量的同时,吞吐量提高了4.8倍。论文在GlobalFoundries的28纳米工艺上综合实现了具有更好可扩展性的RPU-BMW方案。结果表明,一个具有8层4叉的RPU-BMW调度器仅需使用约0.5%的芯片面积和0.57MB的片外SRAM存储开销,就能实现每秒2亿次数据包调度和87,000个流的调度规模。