基于TCAM的高效率路由更新算法.pdf

1、三重內(nèi)容可尋址存儲(chǔ)器(TCAM)技術(shù)是近年來出現(xiàn)的一種硬件查找技術(shù),它可以實(shí)現(xiàn)高速路由查找,滿足Internet的發(fā)展需求。但是TCAM的高功耗一直限制著它的發(fā)展。分塊TCAM和路由壓縮是兩種解決TCAM高功耗的策略,但是它們都有更新速度慢和更新能耗高的弊端。因此,本文結(jié)合因特網(wǎng)報(bào)文數(shù)急速增長(zhǎng)和路由規(guī)則迅速擴(kuò)大的現(xiàn)狀,著重研究了基于TCAM的低功耗路由更新和路由查找等問題,主要工作如下;
　　(1)基于動(dòng)態(tài)更新存儲(chǔ)空間策略,提出了

2、一種TCAM分塊溢出解決算法。分塊TCAM是指把TCAM存儲(chǔ)空間劃分為若干個(gè)小塊,每次路由查找只到其中一個(gè)分塊進(jìn)行匹配查詢,以降低查找能耗。由于路由更新具有隨機(jī)性和突發(fā)性的特點(diǎn),更新操作有可能集中發(fā)生在某些分塊從而造成分塊溢出,迫使重劃分塊。這會(huì)極大地影響路由查找速度。本文通過動(dòng)態(tài)調(diào)整溢出分塊的TCAM存儲(chǔ)空間,提出了一種分塊溢出解決算法,可以很好地避免因分塊溢出而造成的重劃分塊。
　　(2)基于前綴按序排列的特征,提出了一種分塊

3、TCAM空閑資源分配算法。存儲(chǔ)在TCAM的前綴也是按照長(zhǎng)度降序排列的,以滿足最長(zhǎng)前綴查詢。因此,路由更新帶來的插入和刪除操作,會(huì)造成大量的前綴移動(dòng)。在分塊TCAM策略中,每個(gè)分塊都有相應(yīng)的空閑存儲(chǔ)空間。本文依據(jù)前綴按序排列的特征,優(yōu)化了各分塊空閑存儲(chǔ)空間的分配,可以極大地減少更新時(shí)不相關(guān)前綴的位置移動(dòng),從而提高更新速度,降低更新能耗。
　　(3)針對(duì)現(xiàn)有規(guī)則集冗余度較大的特點(diǎn),提出了一種路由規(guī)則壓縮算法。一般路由器的接口比較少,而