發(fā)布時間：2017-11-28 15:32

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

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

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

【參考文獻】

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

1 李振強;鄭東去;馬嚴;;TSB:一種多階段IPv6路由表查找算法[J];電子學報;2007年10期

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

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

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

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

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

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

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

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

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

本文編號：1234470