记录一下自己涉及的一些的科研方向
高性能网包处理
网包分类(Packet Classification)
这是网络设备的最最基本的要求! 狭义理解可以把一般性的网络转发:最长前缀匹配(LPM), 看作其子类。
- 输入: 输入5元组(ip,port,protocol)规则集, 或者是OpenFlow这种自定义协议
- 输出: 匹配的规则(可以是最高优先级、也可以是匹配的所有规则)
- 目标: 低时延、高吞吐(可能通过牺牲时延得到提升, 如batch)、更新响应快
- 理论: 计算几何和数据库查询
- 实验室背景: 实验室的老方向,进行了10年左右的research。
- 方案: TSS、HyperSplit、HiCuts等算法，为了高性能、一般使用树、哈希作为典型数据结构，利用分组、启发式进行决策树分割等方法进行优化。在硬件方向，一般会使用FPGA、TCAM进行硬件优化。
- 前沿: 优化或者使用混合方法。优化的典型是NeuroCuts，使用RL来优化决策树的构造; 混合方法的典型是CutSplit、TSS和树混合等。
正则匹配(Regular Expression)
在网络检测中基本的功能
- 输入: 正则表达式规则集、字符串(流式)
- 输出: 命中的规则
- 目标: 低时延、高吞吐、更新(更新一般是个次要因素)
- 理论: 自动机理论、BDD优化等
- 实验室背景: 实验室之前的博士生研究了7年左右的方向。
- 方案: DFA和NFA是最基本的两种方法, 基于这两种方法衍生出来了Hybrid-FA、XFA(增加跳转优化)等, 核心解决DFA的内存爆炸和NFA的匹配过慢的问题, 其中还涉及到分组算法以及利用字符串匹配来做预过滤的工程优化。
- 前沿: Intel的Hyperscan库
网包调度(Packet Scheduling)
- 输入: 各种流量、人为定义的性能要求
- 输出: 按照一定顺序调度流量
- 理论: 微分方程(离散网包控制进行连续化–使用窗口)和各种调度理论(未来有可能使用ML优化，但其高性能的要求使得未必工作OK–需要考虑应用背景)。
- 实验室背景: 自己从大四开始陆陆续续做了大约1年的方向
- 方案: 典型的令牌桶(Token Bucket)、虚拟时钟(Virutal Clock)，加上层级架构和典型的服务调度算法，从而诞生的HTB、WFQ等算法。在硬件方向，使用FPGA做优化(已经有2篇网络顶会Sigcomm/NSDI的文章了)。
- 前沿: PIFO引发的统一性的算法设计，这里存在问题的是TB能应对抖动保持高性能，但PIFO(或者说背后的Virtual Clock)应对burst存疑。
网络管理功能
网络功能验证(Network Verification)
- 实验室背景: 跟随同事参与了解一些东西。
涵盖的内容有：数据平面的验证(针对网络拓扑和netflow)、控制平面的验证(针对网络功能,例如NFV和Protocol)。典型的算法有：HSA、Batfish等。现在最新的文章聚焦在使用SAT等形式化验证的PL常见内容来进行
网络建模(Network Modelling)可以认为是网络验证的第一步
