查表轉(zhuǎn)發(fā)算法包括三部分：查表、結(jié)果判別和轉(zhuǎn)發(fā)上報(bào)。查表部分負(fù)責(zé)數(shù)據(jù)包轉(zhuǎn)發(fā)表項(xiàng)的匹配,方式是針對數(shù)據(jù)包利用TCAM中存放的轉(zhuǎn)發(fā)表進(jìn)行關(guān)鍵字匹配,輸出查表結(jié)果,如果失敗則丟棄數(shù)據(jù)包;結(jié)果判別部分包括RPF檢查、數(shù)據(jù)驅(qū)動報(bào)文判定、查表成敗判定等邏輯,根據(jù)查表結(jié)果信息進(jìn)行判定;轉(zhuǎn)發(fā)上報(bào)部分包括正常數(shù)據(jù)包的轉(zhuǎn)發(fā)和數(shù)據(jù)驅(qū)動報(bào)文封裝上報(bào)等操作。其中查表部分相對復(fù)雜,時(shí)間耗費(fèi)較多,利用FPGA程序?qū)崿F(xiàn)時(shí)需要考慮如何進(jìn)行性能優(yōu)化,否則容易導(dǎo)致數(shù)據(jù)不能及時(shí)查表轉(zhuǎn)發(fā),達(dá)不到線速轉(zhuǎn)發(fā)的要求。數(shù)據(jù)驅(qū)動報(bào)文的封裝上報(bào)等操作可以采用硬件或者軟件實(shí)現(xiàn)。在路由器中硬件對組播的支持包括兩個(gè)方面：一是完成硬件查表轉(zhuǎn)發(fā),二是在硬件上支持組播復(fù)制。在組播復(fù)制的硬件實(shí)現(xiàn)中,將組播復(fù)制功能放到調(diào)度模塊實(shí)現(xiàn)。調(diào)度模塊收到轉(zhuǎn)發(fā)送來的組播報(bào)文后,根據(jù)轉(zhuǎn)發(fā)所貼標(biāo)簽標(biāo)識的目的端口號及復(fù)制數(shù)目進(jìn)行相應(yīng)的復(fù)制,并直接送到相應(yīng)端口的FIFO。
3 線速轉(zhuǎn)發(fā)可行性分析
該分布式設(shè)計(jì)方案的目的是實(shí)現(xiàn)高速數(shù)據(jù)轉(zhuǎn)發(fā),目標(biāo)是達(dá)到10G接口的線速轉(zhuǎn)發(fā)。根據(jù)以上設(shè)計(jì)需要估算一下能否達(dá)到線速轉(zhuǎn)發(fā)能力和主要限制因素。考慮到查表過程的時(shí)間耗費(fèi)對轉(zhuǎn)發(fā)性能的影響最大,從這方面展開對線速轉(zhuǎn)發(fā)限制因素的分析。
3.1 線速轉(zhuǎn)發(fā)條件
線速轉(zhuǎn)發(fā)要求數(shù)據(jù)包的吞吐率在達(dá)到線路接口的最高值時(shí)不會丟包,即必須能及時(shí)處理所有的數(shù)據(jù)包,那么衡量的標(biāo)準(zhǔn)為查表的時(shí)間應(yīng)低于單個(gè)數(shù)據(jù)包的線速轉(zhuǎn)發(fā)時(shí)間。數(shù)據(jù)包越長,對應(yīng)的查表時(shí)間就越長。因此對短數(shù)據(jù)包的要求更為苛刻。要在數(shù)據(jù)速率高達(dá)10Gbps的條件下,實(shí)現(xiàn)常見最短組播數(shù)據(jù)包(長度為40字節(jié))的線速轉(zhuǎn)發(fā),則轉(zhuǎn)發(fā)處理一個(gè)數(shù)據(jù)包的最長時(shí)間為：
(IP報(bào)文長度)40×8bit／(端口速率)10Gbps=32ns。
表2給出了不同長度數(shù)據(jù)包的轉(zhuǎn)發(fā)最長時(shí)間。
假定商用TCAM芯片的時(shí)鐘為100MHz,每個(gè)時(shí)鐘周期長10ns,也就是說必須在4個(gè)時(shí)鐘周期內(nèi)完成查表轉(zhuǎn)發(fā),才能實(shí)現(xiàn)最短數(shù)據(jù)包的線速轉(zhuǎn)發(fā)。根據(jù)轉(zhuǎn)發(fā)表格式的設(shè)計(jì),源地址和目的地址作為查表關(guān)鍵字存放于TCAM中,針對IPv4關(guān)鍵字長64bit,IPv6關(guān)鍵字長256bit,使用的TCAM為Netlogic公司的NSE5512,其容量為512kx72bit(即：若表項(xiàng)寬度為72位,則該容量(包括掩碼)為512k×72bit,事實(shí)上表項(xiàng)為256k條)。該器件的表項(xiàng)寬度可配置為72位、144位、288位和576位,表項(xiàng)配置為144位時(shí),容量為128k條;配置為288位時(shí),容量即為64k條。根據(jù)筆者設(shè)計(jì)的轉(zhuǎn)發(fā)表格式,組播表的查表關(guān)鍵字設(shè)為288位寬。
利用TCAM實(shí)現(xiàn)查表所需的總時(shí)間T可分為兩部分。一部分為查表關(guān)鍵字的輸入時(shí)間T1,例如對數(shù)據(jù)總線為72位的TCAM而言,288位查表關(guān)鍵字的輸入時(shí)間需要4個(gè)FPGA時(shí)鐘周期;另一部分為查表關(guān)鍵字搜索TCAM內(nèi)部表項(xiàng)從而得出查表結(jié)果所需的時(shí)間,也可以稱之為查表結(jié)果等待時(shí)間T2,目前業(yè)界比較先進(jìn)的TCAM的等待時(shí)間通常為10個(gè)FPGA時(shí)鐘周期。因此,有：T=T1+T2=14。這說明,采用通常的查表方案在4個(gè)時(shí)鐘周期內(nèi)無法處理完最短包,10G接口的線速轉(zhuǎn)發(fā)無法得到。
3．2 優(yōu)化查表策略
為了實(shí)現(xiàn)10G接口的線速轉(zhuǎn)發(fā),必須設(shè)法使得轉(zhuǎn)發(fā)查表能在4個(gè)時(shí)鐘周期內(nèi)完成。而純粹的TCAM查表不能在4個(gè)時(shí)鐘周期內(nèi)完成,這就要求必須采用流水查表技術(shù)對查表實(shí)現(xiàn)方案進(jìn)行優(yōu)化。這樣,一種由TCAM和SRAM共同完成的路由查表流水線方案在此處可以得到應(yīng)用。該流水查表方案中,TCAM表項(xiàng)僅存儲查表關(guān)鍵字,查表結(jié)果則存儲在相應(yīng)地址的SRAM中。組播查表過程被分解成為三級流水級。其中,一級關(guān)鍵字是組播查表關(guān)鍵字,該關(guān)鍵宇格式應(yīng)為(S,G),一級關(guān)鍵字的查表利用TCAM實(shí)現(xiàn);二級關(guān)鍵字是TCAM中表項(xiàng)最低匹配地址,二級關(guān)鍵字的查表利用SRAM實(shí)現(xiàn);二級關(guān)鍵字查表結(jié)果為最終結(jié)果,即出接口等信息。則查表流水線如圖3所示。
流水線的功能段完成該段任務(wù)所需的時(shí)間即為功能段延遲時(shí)間,表3列出了IPv4／IPv6組播數(shù)據(jù)包查表時(shí)各功能段的時(shí)間延遲。由該表可知,該查表流水線中延遲時(shí)間最長的段為“TCAM查表關(guān)鍵字輸入”,需要4個(gè)FPGA時(shí)鐘周期。
目前,在FPGA和TCAM、SRAM器件允許的條件下,該查表流水線結(jié)構(gòu)可以支持OC-192接口40字節(jié)組播包線速查表。該流水線已經(jīng)在T比特路由器上得到應(yīng)用,其具體設(shè)計(jì)方案不是本文討論的問題,只用來說明采用TCAM+FPGA方式能夠?qū)崿F(xiàn)10G接口線速轉(zhuǎn)發(fā),這一點(diǎn)將由實(shí)際測試得到證明。
關(guān)于硬件轉(zhuǎn)發(fā)性能的測試,RFC建議以最短報(bào)文來測試路由器的吞吐量。在同樣端口速率下轉(zhuǎn)發(fā)小包是對路由器包轉(zhuǎn)發(fā)能力最大的考驗(yàn)。筆者進(jìn)行了測試,測試端口包括10G wAN／LAN和10G POS,利用Spirent通信公司的AX／4000測試儀對該路由器依照RFC2544規(guī)定進(jìn)行轉(zhuǎn)發(fā)性能測試。結(jié)果10G WAN／LAN接口40字節(jié)以上組播數(shù)據(jù)包均可達(dá)到線速轉(zhuǎn)發(fā),10G POS接口70字節(jié)以上可達(dá)到線速轉(zhuǎn)發(fā)。只要FPGA程序進(jìn)一步優(yōu)化可以實(shí)現(xiàn)任意包長的線速轉(zhuǎn)發(fā)。本次測試的丟包率為0。64字節(jié)的包延遲僅為12.35μs。證明組播數(shù)據(jù)包能夠?qū)崿F(xiàn)10G線速轉(zhuǎn)發(fā),延遲很小,適合組播應(yīng)用。
本文結(jié)合國家863項(xiàng)目“可擴(kuò)展到T比特的高性能IPv4／v6路由器基礎(chǔ)平臺及實(shí)驗(yàn)系統(tǒng)”的要求,提出了一種可應(yīng)用于T比特路由器平臺的分布式PIM-SM組播實(shí)現(xiàn)方案,采用TCAM+FPGA方式實(shí)現(xiàn)了高速數(shù)據(jù)轉(zhuǎn)發(fā),并研究設(shè)計(jì)了轉(zhuǎn)發(fā)表格式和查表轉(zhuǎn)發(fā)算法,分析了該方式下線速轉(zhuǎn)發(fā)的可行性,并最終得到實(shí)際性能的驗(yàn)證。總之,本文提出了一種實(shí)現(xiàn)相對簡單、高效可行的PIM-SM組播實(shí)現(xiàn)方案。它具有較強(qiáng)的創(chuàng)新性,該方案的設(shè)計(jì)思想不僅可以應(yīng)用于T比特路由器,同樣也適用于其他具有分布式結(jié)構(gòu)的高端路由器。
（來源：電子技術(shù)應(yīng)用）
