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

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

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

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

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