面向缓存的数据名查找加速机制研究

发布时间：2020-08-08 14:46

【摘要】：近几年,随着网络技术的飞速发展,互联网应用已经渗透到人们工作生活的方方面面。人们越来越关注网络中传输的数据内容;而现有的TCP/IP架构却是以地址为核心,在可扩展性、动态性和安全性等方面已难以满足应用的需求。鉴于此,命名数据网络(Named Data Networking,NDN)提出将网络关注的焦点从地址转移到数据内容,颠覆了传统TCP/IP网络的通信模型。在NDN的数据平面,数据名查找是一项关键技术,直接决定了数据平面转发数据包的性能以及资源开销。相比于IP地址,NDN数据名结构复杂、不定长且无理论上限,这给数据名查找带来了更大的挑战。基于前缀树的数据名查找方案在不考虑专用硬件加速的情况下查找速度难以满足性能需求;哈希表和布鲁姆过滤器虽然操作简单、平均查找速度快,但不能直接应用于前缀查找,且需小心处理哈希冲突和假阳性问题。前缀布鲁姆过滤器(Prefix Bloom Filter,PBF)根据前缀长度分布,结合哈希表和布鲁姆过滤器来实现查找加速,同时降低假阳性率。然而,其存储利用率较低,浪费了大部分存储空间。鉴于此,本文基于前缀布鲁姆过滤器,设计了一种更紧凑的结构及相应的查找算法,在保障查找速度、假阳性率和准确率的前提下压缩存储开销。实验表明,该方案能节省近54%的存储空间,而且查找速度也有提升。在数据集为全匹配模式和全不匹配模式的情况下,平均查找延时分别下降了 11.5%和7.5%。可见,该方案既能压缩存储空间,又能提升查找性能。另一方面,常规NDN的包转发过程中需要查多张表;而在一些特定场景下,比如流媒体传输,短时间内需要处理大量数据名相同或相近的包。因此,本文在对NDN转发流水线进行深入分析后,设计了一种包缓存(Packet Cache,PC),以数据包类型及数据名(去除段号)为联合关键字,直接索引所需操作,以减少不必要的查表,分别使用兴趣包和数据包作为数据集与常规查找方案做对比进行测试,结果表明在数据名重复率为30%以上时,使用包缓存效果较好;在重复率为100%时,例如传输一部电影,使用本文设计的包缓存可减少60%左右的查表开销。
【学位授予单位】：湖南大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TP393.0
【图文】：

模型图,沙漏,前缀,模型

图１．１邋ＴＣＰ／ＩＰ网络与ＮＤＮ网络沙漏模型逦逦１逡逑图１．２邋ＮＤＮ结构中两种类型的包逦２逡逑图１．３邋ＮＤＮ节点中的转发过程逦逦３逡逑图２．１前缀布鲁姆过滤器逦１０逡逑图２．２前缀

数据名,名字,兴趣,数据包

逑１．１．２邋ＮＤＮ路由转发模型与数据名查找逡逑如图１．２ｍ所示，在ＮＤＮ中有两种类型的传输包：兴趣包（Ｉｎｔｅｒｅｓｔ邋Ｐａｃｋｅｔ）和逡逑数据包（ＤａｔａＰａｃｋｅｔ）邋［８］。兴趣包表达了用户对数据的请求，其数据名标识了它所逡逑请求的数据；数据包则承载着数据资源，其数据名即为其所承载数据的唯一标识。逡逑此外，兴趣包还可以携带一些额外信息来定制数据选择策略，而数据包则必须包含逡逑数据生产者签名用以验证其合法性和完整性。这些包都是独立存在的，不依赖连接逡逑控制，也不需要状态信息，与其从哪里来以及将要被转发到哪里去都没有任何的关逡逑系。我们用包的名字来替代现在的地址，包路由时只依据自身携带的内容而无需逡逑依赖类似ＩＰ的位置信息。每个包的名字由多个可变长的组件构成，例如，名字／ｘ／ｙ／ｚ逡逑由３个组件构成

节点,数据名,兴趣,引擎

逑而到ＦＩＢ表中进行查找。若ＦＩＢ表中有对应项，则表明该引擎知道该兴趣包的转发逡逑规则；若没有，则表明该引擎无法处理该兴趣包，此时直接将其丢弃，如图１．３所逡逑Ｉ查询ＣＳ逦查询ＷＴ邋｜（＝＞｜查询ＦＩＢ邋｜逡逑＼＼逦栔名查找逦Ｚ，’逡逑兴趣包请求兴趣包请求逡逑ＬＡ＾．ｌ逡逑返？教据包逦返回数握包逡逑图１．３邋ＮＤＮ节点中的转发过程逡逑可见，ＮＤＮ的转发过程涉及两种包在三张表上以数据名为关键字进行的匹配，逡逑既包括精确匹配，也包括最长前缀匹配。因此，ＮＤＮ转发的核心操作即为数据名逡逑查找。相比于ＴＣＰ／ＩＰ中的ＩＰ地址查找，ＮＤＮ数据名查找面临更严峻的的挑战［１０］。逡逑首先，ＮＤＮ数据名的长度不定且无理论上限［＂］，这就对查找算法的性能提出了更逡逑高的要求。其次，ＮＤＮＦＩＢ可能比ＩＰＦｆｆｉ大好几个数量级［１２］，这就需要设计更紧逡逑凑的数据结构。最后，ＰＩＴ需要处理的更新远比单纯的路由更新要频繁。逡逑１．２国内外研究现状逡逑文献［１３］分析了传统的基于ＩＰ转发与基于数据名转发的根本区别：ＩＰ地址是固逡逑定的、有限的

【参考文献】