Zipline论文笔记
研究问题&动机
将开销较大的压缩和解压offload到可编程交换机（line rate），实现的压缩算法是generalized deduplication。
现有一些工作会在交换机上对数据流做on-the-fly的压缩（），但是方法是在第三层及以上，Zipline是在layer2进行压缩，可以支持更广泛的传输协议。
IoT应用一般需要处理小数据块并且因为内存限制，需要对小数据块进行压缩。标准的压缩算法对小数据块的表现不够好，而GD对小数据块的压缩表现也很好。因此对于live vedio streaming，如果deflate这种算法需要足够量的数据才能有较好的性能，但是攒这么多数据需要时间，影响实时性。这种情况下选择GD更好。
压缩算法
上图给出了压缩过程。
接收到一个网络报文，包含数据payload B，长度为n个比特
使用Hamming decoder（会映射到Tofino内置的CRC模块，计算出来的结果是相同的）计算出一个m个比特长度的syndrome
用计算出的syndrome查表，得到一个对应长度为n的mask f
用查出的f与原本的数据按位异或，得到新的长度为n的b’
取b’最右的k位形成basis m
用m查basis-ID的表，看计算出来的basis是不是已经有一个更短的ID可以替换（从而达到压缩的目的）
如果表中用basis m能得到一个更短的ID，将包变成ID+syndrome；如果表中查不到对应的basis m，将包变成basis+syndrome
（一开始不是很了解syndrome，参考了 https://www.youtube.com/watch?v=z89uW4eCRx0 这个视频。）
同样，类似给出解压过程。
接收到一个压缩后的网络报文（如果收到的包不是压缩的，即是basis+syndrome的类型，直接从步骤3开始），包含一个长度为t的ID和长度为m的syndrome
接收方也要有一个ID-basis表，与压缩方需要是一致的
查出对应的basis并且zero pad到原来的长度n比特（m+k=n）
将n比特的pad后的basis输入CRC generator，得到长度m比特的parity bits p（得到之前truncated的数据）
根据收到的syndrome查表，得到对应长度为n的mask f。
用parity和basis组成长度为n的串，与f进行按位异或
得到原始数据b
具体实现
定义了三种类型的包：
- regular但unprocessed
- processed但uncompressed
- processed且compressed
第一种可以是交换机收到的任意Ethernet包，并且将1作为输入，后续会转化成2或者3（如果计算出的basis有对应的更短ID）。
ID有限，但basis会有很多，所以使用LRU的回收机制。
syndrome look up table是一个match action table，里面的表项都是预先计算好并且不会改变的。
一种为basis选择对应ID的方法是使用cryptographic hash，但是密码散列函数在P4交换机上没有办法一轮完成。所以让控制平面来管理id的分配，当basis查表不存在时，通过digests发送到控制面，如果还有未使用的id，直接分配给该basis；如果id都使用了，通过LRU回收最近没有使用的ID。（如何保证还能正常解压？）TNA可以对表项添加ttl。需要先给目的交换机增加反过来的ID-basis表项，然后再给源交换机添加basis-ID表项。
实现的时候还需要考虑Tofino具体架构的限制，因为Tofino是为了对header自定义处理和routing而设计的，所以需要考虑到如下几个问题。
- Tofino架构中要求header必须是字节对齐的，但Hamming Code并不是字节对齐的，需要我们进行zero padding，并且会导致参数可以选择的范围减少（？）
- 论文最初的设计是将尽可能多的代码都放在数据面处理，所以考虑使用register进行存储。虽然这样能实现line rate，但是因为P4 pipeline中不支持loop，所以如果想要查看完整的register存储内容是无法实现的。因此将这些放到MATable中，通过控制平面来管理。这样的好处还有可以利用TNA提供的digests和per-table-entry TTL，能够更简单的实现LRU机制。唯一的缺点是因为涉及到了controller，更新会需要更多的时间。
- ingress实现压缩，egress实现解压（编译器可以跨stage存表，可以将egress表放到还有空间的ingress stage中）
实验结果
参数选择
实验可以设置的参数包括Hamming Code中的k、n和m，但是因为k和n的取值都是与m相关的，所以实际只有m可以自由选择。又考虑到对字节对齐的限制，m必须是8的倍数才可以避免无用的padding。m选择为8，这是m能够选择的最大值，同时满足倍数限制且符合硬件限制。
考虑缓存的basis大小，这个参数选择同样也要考虑到字节对齐的因素（？）。因为需要留一个位存储MSB，所以满足硬件限制且不需要padding的最大值是15比特，因此缓存的basis大小为2^15 = 32768。
动态学习时间
实验想要评估通过控制面管理basis-ID table对性能的影响，通过交换机接收一个未知basis到这个basis注册完能够在表中查到的时间间隔来衡量。尽可能快的发送相同数据包，然后在目的交换机上计算收到第一个类型2的包和收到第一个类型3的包之间的时间间隔。实验结果表明整个时间大概在1.77ms左右。
压缩比例
数据集包括synthetic（类似一个传感器的typical readout）和real world（大学中一天的DNS请求）。
实验有三种case：
empty table 相当于是baseline
static table 预先计算好对应的basis以及ID
dynamic learning table开始是空的，随着不断注册增加表项
Gzip 单独将数据提取到一个文件中，并用gzip进行压缩
空表的3% overhead是由padding导致的。static table是理想的情况，每个basis都事先预知id；dynamic learning是实际应用的情况。用实际常用的压缩算法gzip（在交换机上肯定无法实现！）进行比较，发现性能也挺好。
raw performance
发送Ethernet数据包，分为三种大小，64B、1500B以及9KB。
server不断给自己发送包，通过测量ttl计算延时。
总结
如果想要在P4上做压缩算法，常见的压缩算法应该不太适用（比如snappy、gzip这种），因为pipeline不支持循环，因此匹配相同的子串难以实现。所以需要找一些其他的压缩算法，比如这一篇用的GD就能正好利用Tofino的内置CRC模块，并且最终实现的效果与gzip相差并不太大。