本文關(guān)鍵詞：基于多核處理器的并行路由查找算法研究與實(shí)現(xiàn)

  更多相關(guān)文章： 路由查找算法 Trie樹(shù) 并行 多核處理器 流表

【摘要】：多核處理器憑借處理速度快、延遲小、吞吐量大和并行處理等特點(diǎn)，被迅速應(yīng)用于高端路由器。而在基于多核處理器平臺(tái)的路由查找算法，則成為了路由器數(shù)據(jù)查找轉(zhuǎn)發(fā)的瓶頸。傳統(tǒng)基于Hash、Trie樹(shù)和分段地址的查找算法多應(yīng)用于串行數(shù)據(jù)處理的單核處理器中，這些算法應(yīng)用于多核處理器，由于多核處理器并行處理的特點(diǎn)，容易形成資源競(jìng)爭(zhēng)，造成數(shù)據(jù)瓶頸。因此，本文針對(duì)多核處理器的特點(diǎn)，，提出了一種基于分割多分支Trie的并行路由查找算法，并利用處理器的Cache和流表思想，對(duì)算法做了進(jìn)一步研究和改進(jìn)，解決了在多核處理器平臺(tái)下，路由查找速度慢的問(wèn)題。 首先，針對(duì)多核處理器任務(wù)調(diào)度和并行處理的特點(diǎn)，在研究傳統(tǒng)多分支Trie樹(shù)的基礎(chǔ)上，提出了一種基于SDRAM的并行路由查找算法，即分割多分支Trie樹(shù)算法。該算法將一棵多分支Trie樹(shù)根據(jù)處理器的核數(shù)分割成若干子樹(shù)，每棵子樹(shù)又構(gòu)成一棵單獨(dú)的多分支Trie樹(shù)，子樹(shù)中取消了前綴查找，采取組成一個(gè)大中間節(jié)點(diǎn)的方式。在中間節(jié)點(diǎn)之間采用固定步長(zhǎng)查詢，中間節(jié)點(diǎn)內(nèi)部采用二進(jìn)制Trie樹(shù)來(lái)表示。由于每個(gè)核只在其對(duì)應(yīng)的子樹(shù)中查找，從而有效避免多個(gè)核因資源共享而產(chǎn)生競(jìng)爭(zhēng)和互斥的問(wèn)題，同時(shí)還保持了較低的時(shí)間復(fù)雜度和空間復(fù)雜度。 其次，為進(jìn)一步提升算法的查找效率，在分割多分支Trie樹(shù)的基礎(chǔ)上，引入了流表的思想。在處理器Cache中建立一張流表，把整個(gè)路由查找分為兩層，首先到Cache的流表中查找，如果命中，則根據(jù)路由表的轉(zhuǎn)發(fā)信息將數(shù)據(jù)包轉(zhuǎn)發(fā)，如果未命中，則到SDRAM總表中按照分割多分支Trie的算法查找，查找成功后將該路由信息調(diào)入Cache中的流表，方便同一路由再次被查找。其中Cache中的流表采用哈希表結(jié)構(gòu)，用鏈地址方法防止哈希沖突。當(dāng)哈希表滿時(shí)，則采用直接覆蓋的方法進(jìn)行路由淘汰。另外，為了防止Cache流表中因多個(gè)核對(duì)同一個(gè)路由表項(xiàng)操作而產(chǎn)生的競(jìng)爭(zhēng)問(wèn)題，設(shè)計(jì)了一種無(wú)鎖流表，即將路由表項(xiàng)的刪除過(guò)程分為兩個(gè)階段，第一個(gè)階段為失效，第二個(gè)階段為刪除。 最后，在高端路由器上對(duì)本文提出的算法進(jìn)行了實(shí)驗(yàn)，證明了本算法的實(shí)用性。
【學(xué)位授予單位】：武漢郵電科學(xué)研究院
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類號(hào)】：TP332

【參考文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫(kù) 前10條

1 李振強(qiáng);鄭東去;馬嚴(yán);;TSB:一種多階段IPv6路由表查找算法[J];電子學(xué)報(bào);2007年10期

2 陳蹊;趙躍龍;;多分枝trie樹(shù)路由查找算法研究[J];電子設(shè)計(jì)工程;2010年03期

3 楊玉梅;黎仁國(guó);;基于二分查找和Trie的IPv6路由查找算法[J];蘭州理工大學(xué)學(xué)報(bào);2012年04期

4 劉中金;李勇;楊懋;蘇厲;金德鵬;曾烈光;;基于可編程硬件的虛擬路由器數(shù)據(jù)平面設(shè)計(jì)與實(shí)現(xiàn)[J];電子學(xué)報(bào);2013年07期

5 鄭緯民,楊博,林偉堅(jiān),李志光;SMP機(jī)群系統(tǒng)上優(yōu)化通信的并行任務(wù)調(diào)度[J];中國(guó)科學(xué)E輯:技術(shù)科學(xué);2001年05期

6 李冬梅;施�；�;;負(fù)載平衡調(diào)度問(wèn)題的一般模型研究[J];計(jì)算機(jī)工程與應(yīng)用;2007年08期

7 李冬梅;施海虎;顧毓清;;基于規(guī)則的分層負(fù)載平衡調(diào)度模型[J];計(jì)算機(jī)科學(xué);2003年10期

8 王亞剛;杜慧敏;楊康平;;使用Hash表和樹(shù)位圖的兩級(jí)IPv6地址查找算法[J];計(jì)算機(jī)科學(xué);2010年09期

9 張明杰,盧錫城;基于二分法搜索hash表的快速IP路由查找算法[J];計(jì)算機(jī)工程與科學(xué);2000年05期

10 蘭舟;孫世新;;基于動(dòng)態(tài)關(guān)鍵任務(wù)的多處理器任務(wù)分配算法[J];計(jì)算機(jī)學(xué)報(bào);2007年03期

本文編號(hào)：1234470