基于TCAM的多下一跳路由并行查找的方法.pdf

1、Internet的規(guī)模迅速擴大，業(yè)務(wù)種類越來越多，對網(wǎng)絡(luò)帶寬的需求不斷上升，但路由及數(shù)據(jù)分組轉(zhuǎn)發(fā)技術(shù)卻滯后于Internet的發(fā)展。路由器已經(jīng)成為制約Internet高速發(fā)展的主要因素。路由表作為路由器的一個核心部件，其查詢速度對路由器的性能有至關(guān)重要的影響。目前，路由查表速度已經(jīng)難以適應(yīng)不斷增長的鏈路速度和路由表的增長速度。為了實現(xiàn)負(fù)載平衡以及策略路由，路由表中保存了相當(dāng)數(shù)量的具有多個下一跳的路由表項。多下一跳路由的存在是Intern

2、et路由表的重要特征之一，它增加了路由查找方案設(shè)計的復(fù)雜度。研究人員已經(jīng)提出了很多路由查找算法，但普遍都是針對單一下一跳路由的方法。本文主要是圍繞如何快速查找具有多個下一跳的路由展開的。 論文分析了當(dāng)前路由器的應(yīng)用以及發(fā)展趨勢，進(jìn)而對影響路由器性能的幾個方面進(jìn)行了歸納，總結(jié)了路由查找面臨的問題及難點，介紹了現(xiàn)有的高速路由表查詢算法，并對它們進(jìn)行了詳細(xì)的研究和比較。在此基礎(chǔ)上提出了基于TCAM的多下一跳路由的并行查找方法。該方法采

3、用前綴擴展技術(shù)，減少了前綴長度種類；使用多個TCAM芯片并行查找，提高了查找速度；調(diào)整表項數(shù)據(jù)結(jié)構(gòu)，使得表項陣列免排序；循環(huán)往復(fù)查找，充分利用了TCAM資源。為多下一跳路由查找提供了一種新的解決思路。 按照方法的設(shè)計思想，通過VHDL+FPGA在Modelsim平臺實現(xiàn)了功能仿真，完整再現(xiàn)了方法的路由更新和匹配查找過程。在更新過程中，對前綴需要擴展、前綴無需擴展和多下一跳路由的更新進(jìn)行了模擬。查找過程中，對單一下一跳及多下一跳路

4、由的查找都進(jìn)行了仿真。測試結(jié)果表明：該方法各模塊的設(shè)計在速度和資源利用方面均達(dá)到了要求，在功能上也滿足了對路由更新、查找的需要。 在總體設(shè)計與仿真實現(xiàn)的基礎(chǔ)上，對其匹配結(jié)果的正確性進(jìn)行了證明。并且對前綴擴展實施中的步長選取問題進(jìn)行了研究，給出了擴展前綴情況下最優(yōu)步長的選擇公式，通過程序計算選定擴展步長及采用TCAM芯片的個數(shù)。針對路由更新問題，與傳統(tǒng)路由查找算法進(jìn)行了性能比較分析。 論文最后對本研究進(jìn)行了總結(jié)，并指出繼續(xù)