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

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

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

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