基于拆分模型的高性能哈希機(jī)制研究與實(shí)現(xiàn).pdf

1、IP地址查找（簡(jiǎn)稱IP查找）是TCP/IP網(wǎng)絡(luò)中路由器、交換機(jī)等設(shè)備轉(zhuǎn)發(fā)數(shù)據(jù)包過(guò)程中的一項(xiàng)核心技術(shù)。隨著互聯(lián)網(wǎng)的日益普及，網(wǎng)絡(luò)規(guī)模持續(xù)增大，轉(zhuǎn)發(fā)信息表需維護(hù)的表項(xiàng)也越來(lái)越多，這就加劇了IP查找方案的存儲(chǔ)壓力。大多數(shù)存儲(chǔ)壓縮方案都會(huì)犧牲一點(diǎn)查找性能或更新效率為代價(jià)，而拆分模型則在壓縮存儲(chǔ)的同時(shí)還能實(shí)現(xiàn)非常好的綜合性能。但其片外存儲(chǔ)開銷大，且增長(zhǎng)快，制約了其在實(shí)際系統(tǒng)中的部署應(yīng)用。鑒于此，本文重點(diǎn)研究基于拆分模型的哈希機(jī)制，旨在保障片上存儲(chǔ)

2、效率和綜合性能優(yōu)勢(shì)的前提下大幅提升片外存儲(chǔ)效率，跨越拆分模型從理論到實(shí)踐的最后一道鴻溝。
　　首先，本文對(duì)拆分模型進(jìn)行了深入研究和分析，針對(duì)拆分模型片下查找的鍵值取值范圍固定且可預(yù)知而哈希條目易于分組的特點(diǎn)，提出了一種基于鍵值映射的分組哈希(Key-Mapping based Group Hashing，KMGH)機(jī)制。首先對(duì)哈希條目進(jìn)行分組，然后在片上存儲(chǔ)中維護(hù)一個(gè)固定大小的鍵值映射數(shù)組，將待檢索的鍵值映射到一個(gè)更小的值域，以減

3、小構(gòu)建哈希表的開銷。同時(shí)，為每一個(gè)哈希表維護(hù)一個(gè)高效的空位列表以提升哈希表的存儲(chǔ)利用率。這樣，在保持一次查找一次片外訪存的前提下，大幅減少了片外存儲(chǔ)開銷。實(shí)驗(yàn)結(jié)果表明，拆分模型原有的實(shí)現(xiàn)相比，KMGH僅消耗額外的256K片上存儲(chǔ)資源就能使片外存儲(chǔ)效率提升超70％。而在整體上與現(xiàn)有的優(yōu)秀算法相比，拆分模型配合KMGH在片上和片外的存儲(chǔ)效率提升分別超過(guò)了80％和90％。
　　此外，本文還進(jìn)一步研究了KMGH機(jī)制在葉推、多步長(zhǎng)前綴樹場(chǎng)景