论文部分内容阅读
本文的目标是设计一个用于多集合成员快速查询的紧凑型数据结构。多集合成员查询是计算机系统和网络应用的基本操作。例如,二层交换机会把MAC地址映射到某个端口,能够根据MAC地址快速定位到相关联的端口对二层交换机进行帧转发至关重要。在这里,每个端口相当于一个集合,MAC地址相当于集合的成员。目前大部分多集合成员查询机制都是基于布隆过滤器的,但这些机制不是存储空间太大就是查询速度较低。一方面,一些现有技术把整个存储空间划分成多个均匀的单元,然后用一个或多个单元来存储成员的集合标识。这种粗粒度存储集合标识的方法导致存储空间利用率较为低下。另一方面,其他现有技术内存访问开销较高,成员查询速度较慢。这一类技术相关的机制大部分都使用多个布隆过滤器,使用布隆过滤器的个数根据不同机制的性质确定。因为这些机制的内存读取开销是标准布隆过滤器的好几倍(取决于使用布隆过滤器的数量),所以成员查询的效率不高。为了解决这个问题,本文设计了噪声编码布隆过滤器(Noisy Coding Bloom Filter,NBF)和纠错噪声编码布隆过滤器(Error Corrected Noisy Coding Bloom Filter,NBF-E)来实现多集合成员查询。本文在理论上优化了 NBF和NBF-E的分类失败率和假阳性比率并给出了选择NBF和NBF-E的标准。NBF和NBF-E的关键创新点在于把集合标识信息用一种紧凑的方法来进行存储,从而可以使用较少的存储空间完成多集合成员的快速查询。由于存储集合标识信息时会引入噪声,本文在进行成员查询的时候会对结果进行去噪处理。此外,NBF-E在NBF的基础上使用了非对称纠错编码的技术,可以利用查询结果的非对称错误特性来提高查询结果对噪声的容错性。本文使用真实的网络流量来进行NBF/NBF-E和现有多集合成员查询机制的比较实验,实验结果显示NBF和NBF-E要优于现有的多集合成员查询机制。此外,本文揭露的布隆过滤器的非对称出错性质和使用非对称纠错编码的提议不但可以用于NBF-E的后续研究,还可以应用到其他基于布隆过滤器的机制。