[發(fā)明專利]一種基于分層pc-trie結(jié)構(gòu)的LPM規(guī)則存儲(chǔ)方法

有效

• 申請(qǐng)?zhí)枺?/td>: 202010185738.5
• 申請(qǐng)日: 2020-03-17
• 公開（公告）號(hào): CN111291058B
• 公開（公告）日: 2023-06-16
• 發(fā)明（設(shè)計(jì)）人: 王娜;盧笙;陳盈安;張鵬;沈小朋
• 申請(qǐng)（專利權(quán)）人: 芯啟源（南京）半導(dǎo)體科技有限公司
• 主分類號(hào): G06F16/22
• 分類號(hào): G06F16/22;G06F16/2455
• 代理公司: 江蘇圣典律師事務(wù)所 32237
• 代理人: 郭先彬

本發(fā)明公開了一種基于分層pc?trie結(jié)構(gòu)的LPM規(guī)則存儲(chǔ)方法，該方法利用TCAM解決Black?Sheep?Memory問(wèn)題，集中所有Hash沖突的LPM規(guī)則的對(duì)應(yīng)長(zhǎng)度前綴，對(duì)前綴長(zhǎng)度進(jìn)行分類，而后根據(jù)這些前綴來(lái)存儲(chǔ)映射的pc?trie的地址，最后根據(jù)規(guī)則余下信息，快速搜索和插入規(guī)則到所映射的pc?tire的同時(shí)充分利用硬件空間，并且降低TCAM存儲(chǔ)難度，從而達(dá)到解決Hash沖突的規(guī)則存儲(chǔ)以及時(shí)延固定的問(wèn)題。

技術(shù)領(lǐng)域

本發(fā)明屬于存儲(chǔ)技術(shù)領(lǐng)域，更具體地，涉及一種基于分層pc-trie結(jié)構(gòu)的LPM規(guī)則存儲(chǔ)方法。

背景技術(shù)

基于目前的網(wǎng)絡(luò)速度（速度超過(guò)100-Gb/s），不僅須要路由查找結(jié)構(gòu)更快鎖定其最長(zhǎng)前綴匹配規(guī)則（LPM）的位置并返回相關(guān)數(shù)據(jù)，而且對(duì)LPM規(guī)則的容量也更大要求。LPM的規(guī)則存儲(chǔ)可以在DDR中實(shí)現(xiàn)，但是即便DDR容量再大，要管理海量的LPM規(guī)則還要快速索引，如果沒(méi)有合理的管理方法和設(shè)計(jì)架構(gòu)也是利用率極低。因此合理的架構(gòu)以及解決這個(gè)架構(gòu)中的瓶頸成為研究的重中之重。

?目前業(yè)界提出了pc-tire的分層結(jié)構(gòu)。基于目前實(shí)際的LPM規(guī)則的統(tǒng)計(jì)（長(zhǎng)度范圍為0~128），由于絕大多數(shù)LPM前綴規(guī)則落入在前綴長(zhǎng)度24和48的區(qū)域，因此基于這樣的分布，論文FlashTrie:?Beyond?100-Gb/s?IP?Route?Lookup?Using?Hash-Based?Prefix-Compressed?Trie指出對(duì)前綴長(zhǎng)度短的LPM規(guī)則可利用trie結(jié)構(gòu)直接存儲(chǔ)LPM規(guī)則所涉及信息，其余的LPM規(guī)則則根據(jù)不同長(zhǎng)度的分類，去向不同Hash，以鎖定pc-trie的位置，最后存儲(chǔ)這條規(guī)則所映射的附加信息。這樣做的好處是在把龐大的trie結(jié)構(gòu)轉(zhuǎn)化為動(dòng)態(tài)pc-trie，以充分利用硬件空間。

?那么它的瓶頸也不言而喻，第一個(gè)是Hash算法的設(shè)計(jì)，第二個(gè)是對(duì)于Hash沖突的解決方案，第三個(gè)是pc-trie對(duì)應(yīng)的動(dòng)態(tài)存儲(chǔ)空間的管理。Hash算法的選擇，當(dāng)然是分布越均勻越好。但是對(duì)于一個(gè)pc-trie本身的高度有限，在未知其規(guī)則模式的前提下，從其前綴中合理取Hash?Bit是很困難的。其次是當(dāng)存在Hash沖突時(shí)，需要管理Hash沖突的pc-trie，這就是所謂的Black?Sheep?Memory，須達(dá)到同時(shí)搜索的目的。最后是若給pc-trie預(yù)留完整的空間，則可申請(qǐng)的pc-trie的個(gè)數(shù)太少，而且填充率太低，因此須合理動(dòng)態(tài)擴(kuò)充pc-trie的占用空間。

?現(xiàn)有技術(shù)中基于pc-trie的LPM規(guī)則存儲(chǔ)示意圖，如圖1所示，大三角形為其存儲(chǔ)結(jié)構(gòu)，第一層區(qū)域是完全trie結(jié)構(gòu)，長(zhǎng)度為13，因此可以直接索引到規(guī)則對(duì)應(yīng)的trie的位置；第二層到最后一層都為pc-trie構(gòu)成，每一層的長(zhǎng)度分別為9，9，9，9，9，9，9，9，9，9，9，9，9。例如長(zhǎng)度為22的LPM規(guī)則會(huì)落在第二層，長(zhǎng)度為40的LPM規(guī)則會(huì)落在第四層……而每層的pc-trie個(gè)數(shù)取決于硬件容量和對(duì)應(yīng)的LPM規(guī)則個(gè)數(shù)。圖中規(guī)則2長(zhǎng)度在第一層長(zhǎng)度區(qū)間，因此可以直接存儲(chǔ)在tire結(jié)構(gòu)中；圖中規(guī)則1的長(zhǎng)度在第三層長(zhǎng)度區(qū)間，則根據(jù)對(duì)應(yīng)的Hash2來(lái)定位它對(duì)應(yīng)的pc-trie的位置；圖中規(guī)則3的長(zhǎng)度在第二層長(zhǎng)度區(qū)間，則根據(jù)對(duì)應(yīng)的Hash1來(lái)定位它對(duì)應(yīng)pc-trie的位置。現(xiàn)有技術(shù)中基于pc-trie的路由查詢的簡(jiǎn)單示意圖，如圖2所示，當(dāng)一條路由進(jìn)入查詢時(shí)，經(jīng)過(guò)Hash模塊，通過(guò)不同的Hash，進(jìn)入到相對(duì)應(yīng)的tire結(jié)構(gòu)和pc-trie結(jié)構(gòu)中，若存在與映射的pc-trie的前綴一致，則直接查找，得到的結(jié)果送到比較器中；若出現(xiàn)不一致的情況，就去往Black?Sheep?Memory中查詢，得到相對(duì)應(yīng)的結(jié)果，送到比較器。最后經(jīng)過(guò)比較器計(jì)算，輸出最長(zhǎng)匹配的附加信息數(shù)據(jù)。