基于Bloomier Filter的IPv6路由算法.pdf_第1頁
已閱讀1頁,還剩78頁未讀 繼續(xù)免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權,請進行舉報或認領

文檔簡介

1、Internet骨干鏈路速度的不斷提高,要求Internet核心路由器必須以OC-768(40Gbps)甚至更高的鏈路速度處理IP最長前綴匹配(LongestPrefixMatch,LPM),這一問題已成為Internet核心路由器的主要性能瓶頸之一。IPv6地址的出現(xiàn)要求最長前綴匹配的查找長度從IPv4的32比特增加到128比特,更大的前綴寬度給LPM帶來了巨大的挑戰(zhàn)。而路由器的轉發(fā)速率通常受限于路由選擇的速度,因此,路由查找和更新的

2、方法是路由器進行包轉發(fā)的基礎和提高其性能的關鍵性技術,在路由器設計中至關重要。 傳統(tǒng)的LPM機制并不能很好地滿足IPv6的查找要求,基于TCAM的算法能耗高,花費大;基于Trie的算法占用內(nèi)存多,延時大?;趆ash的算法由于其低能耗,高效的存儲以及O(1)的時間復雜度,是IPv6下LPM的一個很好的選擇。 本文在詳細分析多種現(xiàn)有LPM算法的基礎上,對基于hash的LPM查找機制Chisel進行改進。Chisel利用了B

3、loomierFilter這一數(shù)據(jù)結構,實現(xiàn)無沖突的hash機制;并通過前綴縮減,把比特向量引進hash機制,大大節(jié)省了存儲空間。然而,Chisel的高速路由查找,是以復雜的路由更新為代價的,最壞情況下,一個前綴的更新,將影響到2l個前綴項。本文在Chisel的基礎上,通過對IPv6地址分布現(xiàn)狀和分配政策的研究,充分利用Amdahl定律,提出了1-Chisel機制,以每個前綴增加一個比特的很小的存儲代價,使更新復雜度有了極大的提高。同時

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經(jīng)權益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論