本發(fā)明涉及路由管理
技術(shù)領(lǐng)域：
，具體來(lái)講是一種路由器轉(zhuǎn)發(fā)平面的等價(jià)路由管理方法和裝置。
背景技術(shù)：
：網(wǎng)絡(luò)拓?fù)渲写嬖诙鄺l到達(dá)同一目的地址的不同路徑，通常稱為ECMP(Equal-CostMultipathRouting，等價(jià)路由)。ECMP的最大特點(diǎn)是能夠?qū)崿F(xiàn)路由多路徑負(fù)載均衡和鏈路備份，且靜態(tài)路由、OSPF(OpenShortestPathFirst，開(kāi)放式最短路徑優(yōu)先)、BGP(BorderGatewayProtocol，邊界網(wǎng)關(guān)協(xié)議)和IS-IS(IntermediateSystem-to-IntermediateSystem，中間系統(tǒng)到中間系統(tǒng))等常用的路由協(xié)議都支持ECMP，ECMP已成為路由器設(shè)備不可或缺的一項(xiàng)重要功能。從概念來(lái)看ECMP的本質(zhì)是多條路由的集合，在路由設(shè)備上表現(xiàn)的特征是：去往相同的目的地址的路由，具有多個(gè)下一跳，多個(gè)下一跳對(duì)于設(shè)備而言意味著不同的出接口，我們通常稱這種去往相同目的地址的多條路由的集合為一個(gè)ECMP組，每條路由稱為該ECMP組的成員。當(dāng)前，在路由器控制層面的多種協(xié)議對(duì)ECMP支持的前提下，轉(zhuǎn)發(fā)平面如何能夠?qū)CMP路由的高效管理和轉(zhuǎn)發(fā)處理是影響路由器性能的關(guān)鍵。目前路由器轉(zhuǎn)發(fā)平面主要有兩類平臺(tái)實(shí)現(xiàn)，一類是ASIC(ApplicationSpecificIntegratedCircuit，集成電路)架構(gòu)芯片(例如，網(wǎng)絡(luò)處理器、交換芯片)，另一類是基于CPU(CentralProcessingUnit，中央處理器)平臺(tái)(例如，多核處理器)?；贏SIC架構(gòu)芯片這類平臺(tái)中ECMP表項(xiàng)設(shè)計(jì)、表項(xiàng)增加、刪除和表項(xiàng)查找都被芯片固化成嚴(yán)格的流水線邏輯，不具有太多的靈活性，同時(shí)這類平臺(tái)將ECMP與普通路由進(jìn)行嚴(yán)格區(qū)分，兩者在表項(xiàng)設(shè)計(jì)和表項(xiàng)存儲(chǔ)都完全不相同，在進(jìn)行ECMP與普通路由角色平滑轉(zhuǎn)換的過(guò)程中存在困難。而基于處理器芯片平臺(tái)，由于其高性能的處理器在數(shù)據(jù)處理過(guò)程中能夠?qū)崿F(xiàn)并行處理，并且表項(xiàng)和流程設(shè)計(jì)靈活，硬件約束較小，因此被普遍使用。但該平臺(tái)的ECMP功能完全依靠軟件算法來(lái)實(shí)現(xiàn)，因此，最終算法的實(shí)現(xiàn)方式和管理方法是決定ECMP路由轉(zhuǎn)發(fā)性能的關(guān)鍵。ECMP組對(duì)外是一條具有多個(gè)下一跳的路由，對(duì)內(nèi)是多條相同目的地址的路由集合，其本質(zhì)是路由，在處理器平臺(tái)ECMP通常采用路由表的存儲(chǔ)和查找的方法來(lái)實(shí)現(xiàn)，并遵循路由查找中的最長(zhǎng)掩碼匹配原則，應(yīng)用最廣泛的查找方法是樹(shù)型結(jié)構(gòu)算法和分段路由算法。目前，樹(shù)型算法主要有：RadixTrie(基數(shù)樹(shù))、MultibitTrie(多分支樹(shù))等。如圖1所示，樹(shù)型路由表中，路由表表項(xiàng)分部在樹(shù)的各葉子節(jié)點(diǎn)上(黑色圓點(diǎn))，每增加一條路由表項(xiàng)，其路由前綴決定掛載哪個(gè)葉子節(jié)點(diǎn)上；具有相同的路由前綴和掩碼的路由，因其下一跳目的地址不同，而被認(rèn)為是不同的路由表項(xiàng)，在葉子節(jié)點(diǎn)上通過(guò)鏈表結(jié)構(gòu)掛載在一起，形成ECMP在的樹(shù)型路由表中的線性存儲(chǔ)方式。另外，樹(shù)的高度代表了路由表項(xiàng)的存儲(chǔ)深度和平均查找的次數(shù)，隨著路由表項(xiàng)的增加樹(shù)的高度會(huì)隨之增加，為了解決上述問(wèn)題算法引入了平衡樹(shù)，在路由總數(shù)相同的情況下，平衡樹(shù)的樹(shù)高度相對(duì)之前的算法達(dá)到最優(yōu)，查找性能也有所改善，但在路由容量較大的情況下，樹(shù)的高度增加，導(dǎo)致查找性能降低。而分段路由算法有分段路由和優(yōu)化的分段路由等，分段路由算法主要通過(guò)路由分段展開(kāi)，采用空間換時(shí)間的原理實(shí)現(xiàn)查找較高效率，其本質(zhì)是將樹(shù)型算法中的平均查找次數(shù)從多次減少為確定的三次或兩次，解除了樹(shù)型算法中平均查找的次數(shù)與路由總條目直接的線性耦合關(guān)系，但分段路由算法采用空間換時(shí)間的原理，并不適用于所有的場(chǎng)景，易造成空間的極大浪費(fèi)。綜上所述，單純采用傳統(tǒng)樹(shù)型路由算法或分段路由算法在ECMP實(shí)現(xiàn)上，由于其組織結(jié)構(gòu)設(shè)計(jì)和算法的組織方式的局限性，難以滿足處理器平臺(tái)大容量ECMP路由的快速查找，難以實(shí)現(xiàn)ECMP路由與普通路由的平滑轉(zhuǎn)換，給基于處理器平臺(tái)的網(wǎng)絡(luò)設(shè)備造成性能技術(shù)瓶頸，使得處理器的并行處理能力不能完全得以發(fā)揮，造成極大的性能和內(nèi)存資源浪費(fèi)。技術(shù)實(shí)現(xiàn)要素：本發(fā)明的目的是為了克服上述
背景技術(shù)：
的不足，提供一種路由器轉(zhuǎn)發(fā)平面的等價(jià)路由管理方法和裝置，不但能滿足處理器平臺(tái)大容量ECMP路由的快速查找要求，而且能實(shí)現(xiàn)ECMP路由與普通路由的平滑轉(zhuǎn)換，解決了網(wǎng)絡(luò)路由器設(shè)備在處理器平臺(tái)中的性能瓶頸問(wèn)題。為達(dá)到以上目的，本發(fā)明提供一種路由器轉(zhuǎn)發(fā)平面的等價(jià)路由管理方法，包括以下步驟：步驟S1、快表創(chuàng)建：在路由器轉(zhuǎn)發(fā)平面內(nèi)創(chuàng)建一個(gè)用于存儲(chǔ)普通路由查找信息和ECMP路由查找信息的快表，轉(zhuǎn)入步驟S2；步驟S2、快表查找：當(dāng)報(bào)文進(jìn)入路由器轉(zhuǎn)發(fā)平面后，提取報(bào)文中IP頭部的目的地址和VPN值，在創(chuàng)建的快表中進(jìn)行匹配查找，若未查找到相匹配的路由查找信息，表明表項(xiàng)尚未創(chuàng)建，轉(zhuǎn)入步驟S3；若查找到相匹配的路由查找信息，表明表項(xiàng)已存在，轉(zhuǎn)入步驟S4；步驟S3、快表表項(xiàng)的添加：利用報(bào)文中的目的地址和VPN值，通過(guò)在已有的樹(shù)型路由表中進(jìn)行路由表項(xiàng)查找的方式，判斷是普通路由還是ECMP路由，若是普通路由，則將目的地址解析所獲得的路由信息作為普通路由查找信息添加到快表中，返回步驟S2；若是ECMP路由，則將目的地址解析所獲得的路由信息作為ECMP路由查找信息添加到快表中，返回步驟S2；步驟S4、報(bào)文的轉(zhuǎn)發(fā)：根據(jù)查找到的相匹配的路由查找信息，判斷是普通路由還是ECMP路由，若是普通路由，則在確認(rèn)樹(shù)型路由表中葉子節(jié)點(diǎn)未發(fā)生變更的情況下，將報(bào)文按照查找到的普通路由查找信息進(jìn)行普通路由的轉(zhuǎn)發(fā)；若是ECMP路由，則在確認(rèn)樹(shù)型路由表中葉子節(jié)點(diǎn)未發(fā)生變更的情況下，將報(bào)文按照查找到的ECMP路由查找信息進(jìn)行ECMP路由的轉(zhuǎn)發(fā)。本發(fā)明同時(shí)還提供一種基于上述方法的路由器轉(zhuǎn)發(fā)平面的等價(jià)路由管理裝置，包括快表創(chuàng)建單元、快表查找單元、快表表項(xiàng)添加單元和報(bào)文轉(zhuǎn)發(fā)單元；所述快表創(chuàng)建單元用于：在路由器轉(zhuǎn)發(fā)平面內(nèi)創(chuàng)建一個(gè)用于存儲(chǔ)普通路由查找信息和ECMP路由查找信息的快表，并向快表查找單元發(fā)送查找信號(hào)；所述快表查找單元用于：收到查找信號(hào)后，當(dāng)報(bào)文進(jìn)入路由器轉(zhuǎn)發(fā)平面時(shí)，提取報(bào)文中IP頭部的目的地址和VPN值，在創(chuàng)建的快表中進(jìn)行匹配查找，若未查找到相匹配的路由查找信息，向快表表項(xiàng)添加單元發(fā)送添加信號(hào)；若查找到相匹配的路由查找信息，向報(bào)文轉(zhuǎn)發(fā)單元發(fā)送轉(zhuǎn)發(fā)信號(hào)；所述快表表項(xiàng)添加單元用于：收到添加信號(hào)后，利用報(bào)文中的目的地址和VPN值，通過(guò)在已有的樹(shù)型路由表中進(jìn)行路由表項(xiàng)查找的方式，判斷是普通路由還是ECMP路由，若是普通路由，則將目的地址解析所獲得的路由信息作為普通路由查找信息添加到快表中，并向快表查找單元發(fā)送查找信號(hào)；若是ECMP路由，則將目的地址解析所獲得的路由信息作為ECMP路由查找信息添加到快表中，并向快表查找單元發(fā)送查找信號(hào)；所述報(bào)文轉(zhuǎn)發(fā)單元用于：收到轉(zhuǎn)發(fā)信號(hào)后，根據(jù)查找到的相匹配的路由查找信息，判斷是普通路由還是ECMP路由，若是普通路由，則在確認(rèn)樹(shù)型路由表中葉子節(jié)點(diǎn)未發(fā)生變更的情況下，將報(bào)文按照查找到的普通路由查找信息進(jìn)行普通路由的轉(zhuǎn)發(fā)；若是ECMP路由，則在確認(rèn)樹(shù)型路由表中葉子節(jié)點(diǎn)未發(fā)生變更的情況下，將報(bào)文按照查找到的ECMP路由查找信息進(jìn)行ECMP路由的轉(zhuǎn)發(fā)。本發(fā)明的有益效果在于：(1)與單純的樹(shù)型路由表的查找算法相比，本發(fā)明利用創(chuàng)建的存儲(chǔ)普通路由查找信息和ECMP路由查找信息的快表，記錄了前期樹(shù)型路由查找過(guò)程中的必要的信息，并組建了數(shù)據(jù)流的快表表項(xiàng)。讓后續(xù)的數(shù)據(jù)報(bào)文從快表中直接獲取路由查找中的必要信息，直接進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)，將原本樹(shù)型結(jié)構(gòu)中的多次匹配，變化為快表中的有限幾次匹配，從而提高了處理器平臺(tái)在路由查找中的執(zhí)行效率，滿足了處理器平臺(tái)大容量ECMP路由的快速查找要求。(2)本發(fā)明中，將快表設(shè)計(jì)成能夠兼容存儲(chǔ)普通路由查找信息和ECMP路由查找信息的結(jié)構(gòu)，使得在相同的表項(xiàng)中能夠同時(shí)存儲(chǔ)普通路由和ECMP路由，不但節(jié)約了內(nèi)存開(kāi)銷，而且兼容了普通路由與ECMP路由，實(shí)現(xiàn)了普通路由與ECMP路由平滑轉(zhuǎn)換，避免了普通路由與ECMP路由分離存儲(chǔ)的問(wèn)題。(3)本發(fā)明在完成報(bào)文ECMP路由的轉(zhuǎn)發(fā)時(shí)，兼容實(shí)現(xiàn)了ECMP負(fù)載均衡的兩種模式——基于數(shù)據(jù)流的ECMP分流模式或基于報(bào)文逐包的ECMP分流模式，對(duì)于ECMP等價(jià)路由在進(jìn)行流量均衡具有更加靈活的功能。(4)本發(fā)明在進(jìn)行報(bào)文轉(zhuǎn)發(fā)的過(guò)程中，無(wú)論是普通路由還是ECMP路由，在確認(rèn)樹(shù)型路由表中葉子節(jié)點(diǎn)發(fā)生變更的情況下，均會(huì)執(zhí)行快表的更新操作，即能夠進(jìn)行快表表項(xiàng)的自清潔和新的表項(xiàng)的創(chuàng)建，滿足了實(shí)際使用需求，適用性高。附圖說(shuō)明圖1為現(xiàn)有的樹(shù)型路由表的結(jié)構(gòu)示意圖；圖2為本發(fā)明實(shí)施例中路由器轉(zhuǎn)發(fā)平面的等價(jià)路由管理方法的流程圖；圖3為本發(fā)明實(shí)施例中ECMP成員信息表數(shù)組ecmp_cache指向樹(shù)型路由表葉子節(jié)點(diǎn)的ECMP鏈表成員地址的示意圖；具體實(shí)施方式下面結(jié)合附圖及具體實(shí)施例對(duì)本發(fā)明作進(jìn)一步的詳細(xì)描述。參見(jiàn)圖2所示，本發(fā)明實(shí)施例提供一種路由器轉(zhuǎn)發(fā)平面的等價(jià)路由管理方法，包括以下步驟：步驟S1、快表創(chuàng)建：在路由器轉(zhuǎn)發(fā)平面內(nèi)創(chuàng)建一個(gè)用于存儲(chǔ)普通路由查找信息和ECMP路由查找信息的快表(Fast_Table)，轉(zhuǎn)入步驟S2；具體來(lái)說(shuō)，所述快表是一個(gè)基于目的地址和VPN(VirtualPrivateNetwork，虛擬專用網(wǎng)絡(luò))值為關(guān)鍵字的哈希表，該哈希表中具有若干個(gè)哈希桶(Bucket)，經(jīng)目的地址和VPN值計(jì)算出的哈希值對(duì)應(yīng)一個(gè)哈希桶；每個(gè)哈希桶中包括至少兩個(gè)用于存儲(chǔ)普通路由查找信息或ECMP路由查找信息的沖突域成員(Entry)，當(dāng)沖突域成員(Entry)存儲(chǔ)普通路由查找信息時(shí)，其數(shù)據(jù)結(jié)構(gòu)包括以下字段：路由通用字段+普通路由字段；當(dāng)沖突域成員(Entry)存儲(chǔ)ECMP路由查找信息時(shí)，其數(shù)據(jù)結(jié)構(gòu)包括以下字段：路由通用字段+ECMP路由字段。另外，可以理解的是，該快表建立后的初始狀態(tài)為空，即快表結(jié)構(gòu)定義完成，具體表項(xiàng)數(shù)據(jù)為空。其中，路由通用字段包括：有效位(In_use)，用于表示該表項(xiàng)是否使用，當(dāng)In_use為1，表示使用；當(dāng)In_use為0，表示未使用；狀態(tài)位(Pending)，用于表示當(dāng)前表項(xiàng)的狀態(tài)，當(dāng)Pending為1，表示當(dāng)前表項(xiàng)不可用；當(dāng)Pending為0，表示當(dāng)前表項(xiàng)可用；ECMP標(biāo)志位(Multipath)，用于表示是否存在ECMP，當(dāng)Multipath＝1時(shí)，表示存在ECMP即存儲(chǔ)的是ECMP路由查找信息；當(dāng)Multipath＝0時(shí)，表示不存在ECMP即存儲(chǔ)的是普通路由查找信息；目的地址(Addr)，用于表示目的地址；實(shí)例號(hào)(Vrf)，表示VPN實(shí)例。普通路由字段包括：普通路由地址指針(Rt)，用于指向已有的樹(shù)型路由表的葉子節(jié)點(diǎn)路由地址；普通路由接口內(nèi)層Vlan值(Subvlan)，用于存儲(chǔ)普通路由出接口的內(nèi)層Vlan值；普通路由接口值(Ifidx)，用于存儲(chǔ)普通路由的出接口值；普通路由接口外層Vlan值(Vlan)，用于存儲(chǔ)普通路由出接口的外層Vlan值；普通路由下一跳MAC地址(Edst_mac)，用于存儲(chǔ)普通路由下一跳MAC地址值。ECMP路由字段包括：ECMP成員總數(shù)值(Ecmp_total)，用于存儲(chǔ)ECMP成員個(gè)數(shù)值；ECMP成員使用值(Ecmp_index)，用于存儲(chǔ)數(shù)據(jù)流從哪個(gè)ECMP成員值出；ECMP地址指針(Ecmp_ptr)，用于指向ECMP成員信息表(ecmp_cache)的地址；保留字段(Unused)，用于預(yù)留可擴(kuò)展空間。其中，所述ECMP成員信息表用于存儲(chǔ)ECMP的成員信息，該成員信息包括：ECMP路由地址指針(Ecmp_Rt)，用于ECMP指向樹(shù)型路由表的葉子節(jié)點(diǎn)路由地址；ECMP接口內(nèi)層Vlan值(Ecmp_Subvlan)，用于存儲(chǔ)ECMP成員出接口的內(nèi)層Vlan值；ECMP接口值(Ecmp_Ifidx)，用于存儲(chǔ)ECMP路由的出接口值；ECMP接口外層Vlan值(Ecmp_vlan)，用于存儲(chǔ)ECMP成員出接口的外層Vlan值；ECMP下一跳MAC地址(Ecmp_Edst_mac)，用于存儲(chǔ)ECMP成員下一跳MAC地址值。舉例來(lái)說(shuō)，當(dāng)Multipath＝0，沖突域成員(Entry)存儲(chǔ)普通路由查找信息時(shí)，Entry的數(shù)據(jù)結(jié)構(gòu)如表1所示：表1、Multipath＝0的情況下Entry字段內(nèi)容和位寬In_usePendingMultipathAddrVrf191190189188：157156：144RtSubvlanIfidxVlanEdst_mac143：8483：7271：6059：4847：0當(dāng)Multipath＝1，沖突域成員(Entry)存儲(chǔ)ECMP路由查找信息時(shí)，Entry的數(shù)據(jù)結(jié)構(gòu)如表2所示：表2、Multipath＝1的情況下Entry字段內(nèi)容和位寬In_usePendingMultipathAddrVrf191190189188：157156：144Unused1Unused2Ecmp_totalEcmp_indexEcmp_ptr143：8483：7271：6564：6059：0另外，ECMP成員信息表(ecmp_cache)的內(nèi)容如表3所示：表2、Multipath＝1的情況下Entry字段內(nèi)容和位寬Ecmp_RtEcmp_SubvlanEcmp_IfidxEcmp_vlanEcmp_Edst_mac143：8483：7271：6059：4847：0本發(fā)明中，為了兼容普通路由與ECMP路由，并考慮到節(jié)約內(nèi)存的問(wèn)題，將快表設(shè)計(jì)成能夠兼容存儲(chǔ)普通路由查找信息和ECMP路由查找信息的結(jié)構(gòu)，且快表的沖突域成員(Entry)中具有ECMP標(biāo)志位(Multipath)，用于標(biāo)識(shí)該條信息是否是ECMP路由查找信息(即是否存在ECMP)，如果是ECMP路由查找信息，則該沖突域成員(Entry)中的ECMP地址指針(Ecmp_ptr)字段，將指向一個(gè)ECMP成員信息表(ecmp_cache)的地址，該ECMP成員信息表由數(shù)組(ecmp_cache[])組成且其成員(Ecmp_Rt)中記錄了指向樹(shù)型路由表的葉子節(jié)點(diǎn)路由地址，即樹(shù)型路由表的ECMP鏈表成員地址，如圖3所示。步驟S2、快表查找：當(dāng)報(bào)文進(jìn)入路由器轉(zhuǎn)發(fā)平面后，提取報(bào)文中IP頭部的目的地址(對(duì)應(yīng)Addr字段)和VPN值(對(duì)應(yīng)Vrf字段)，并在創(chuàng)建的快表中進(jìn)行匹配查找，若未查找到相匹配的路由查找信息，表明表項(xiàng)尚未創(chuàng)建，轉(zhuǎn)入步驟S3；若查找到相匹配的路由查找信息，表明表項(xiàng)已存在，轉(zhuǎn)入步驟S4。實(shí)際操作時(shí)，步驟S2具體包括以下操作：步驟S201：當(dāng)報(bào)文進(jìn)入路由器轉(zhuǎn)發(fā)平面后，提取報(bào)文中IP頭部的目的地址和VPN值，通過(guò)CRC運(yùn)算獲得32位的哈希值Hash_Value，轉(zhuǎn)入步驟S202。步驟S202：在創(chuàng)建的快表中，用Hash_Value取余哈希桶的最大值Bucket_Max，得到Bucket[Hash_Value％Bucket_Max]表項(xiàng)，標(biāo)記為Bucket[j]，j為正整數(shù)，轉(zhuǎn)入步驟S203；可以理解的是，經(jīng)過(guò)步驟S201和S202，則根據(jù)目的地址和VPN值找到了對(duì)應(yīng)的哈希桶Bucket[j]。步驟S203：依次遍歷Bucket[j]中的每一個(gè)沖突域成員Entry，尋找有效位In_use為1、狀態(tài)位Pending為0的沖突域成員Entry，一旦找到，則轉(zhuǎn)入步驟S204，如果Bucket[j]中一直沒(méi)有找到，則表明表項(xiàng)尚未創(chuàng)建，轉(zhuǎn)入步驟S3。步驟S204：將找到的沖突域成員Entry標(biāo)記為Entry[i]，(i為正整數(shù)且小于等于Bucket[j]中沖突域成員的個(gè)數(shù))；將報(bào)文中提取的目的地址、VPN值分別與Entry[i]中的目的地址Addr字段、實(shí)例號(hào)Vrf字段的值進(jìn)行比較，如果不匹配，則返回步驟S203繼續(xù)尋找，如果匹配，則轉(zhuǎn)入步驟S4。步驟S3、快表表項(xiàng)的添加：利用報(bào)文中的目的地址和VPN值，通過(guò)在已有的樹(shù)型路由表中進(jìn)行路由表項(xiàng)查找的方式，判斷是普通路由還是ECMP路由，若是普通路由，則將目的地址解析所獲得的路由信息作為普通路由查找信息添加到快表中，返回步驟S2；若是ECMP路由，則將目的地址解析所獲得的路由信息作為ECMP路由查找信息添加到快表中，返回步驟S2。實(shí)際操作時(shí)，步驟S3具體包括以下操作：步驟S301：依次遍歷Bucket[j]中的每一個(gè)沖突域成員Entry，找到有效位In_use為1的沖突域成員Entry，標(biāo)記為Entry[k]，(k為正整數(shù)且小于等于Bucket[j]中沖突域成員的個(gè)數(shù))，表明找到一個(gè)空閑的表項(xiàng)，轉(zhuǎn)入步驟S302；步驟S302：將Entry[k]中的目的地址Addr字段、實(shí)例號(hào)Vrf字段分別填寫(xiě)成報(bào)文中的目的地址、VPN值，并將有效位In_use置為1，狀態(tài)位Pending置為1，轉(zhuǎn)入步驟S303；步驟S303：將報(bào)文的目的地址、VPN值帶入到已有的樹(shù)型路由表中進(jìn)行路由表項(xiàng)的查找，根據(jù)路由的最長(zhǎng)掩碼匹配，查找到樹(shù)型路由表的葉子節(jié)點(diǎn)，檢測(cè)該葉子節(jié)點(diǎn)的狀態(tài)，判斷是否存在ECMP的路由，如果不存在，表示是普通路由，轉(zhuǎn)入步驟S304，如果存在，表示是ECMP路由，轉(zhuǎn)入步驟S305；步驟S304：將該葉子節(jié)點(diǎn)的地址填入到Entry[k]中的普通路由地址指針Rt字段中，將ECMP標(biāo)志位Multipath字段置為0；并解析報(bào)文的目的地址的ARP(AddressResolutionProtocol，地址解析協(xié)議)，獲取下一跳MAC地址信息、出接口值信息、內(nèi)層Vlan信息和外層Vlan信息，并將上述信息分別填入到Entry[k]中對(duì)應(yīng)的普通路由下一跳MAC地址Edst_mac字段、普通路由接口值Ifidx字段、普通路由接口內(nèi)層Vlan值Subvlan字段和普通路由接口外層Vlan值Vlan字段中，轉(zhuǎn)入步驟S307；步驟S305：申請(qǐng)內(nèi)存用于存儲(chǔ)ECMP成員信息表的數(shù)組ecmp_cache[N]，N為正整數(shù)，表示ECMP成員的個(gè)數(shù)；將Entry[k]中的ECMP標(biāo)志位Multipath字段置為1，將ECMP成員信息表的數(shù)組的地址值填入Entry[k]中的ECMP地址指針Ecmp_ptr字段中，將ECMP成員的個(gè)數(shù)填入ECMP成員總數(shù)值Ecmp_total字段中，轉(zhuǎn)入步驟S306；步驟S306：依次獲取該葉子節(jié)點(diǎn)中的每一個(gè)ECMP成員，并解析每一個(gè)ECMP成員的目的地址的ARP，獲取其下一跳MAC地址信息、出接口值信息、內(nèi)層Vlan信息和外層Vlan信息，并將上述信息依次填入到的每一個(gè)ECMP成員對(duì)應(yīng)的ECMP下一跳MAC地址Ecmp_Edst_mac字段、ECMP接口值Ecmp_Ifidx字段、ECMP接口內(nèi)層Vlan值Ecmp_Subvlan字段、ECMP接口外層Vlan值Ecmp_vlan字段中，轉(zhuǎn)入步驟S307；步驟S307：將Entry[k]中的狀態(tài)位Pending置為0，表明當(dāng)前表項(xiàng)可用；完成上述過(guò)程，報(bào)文在快表Entry[k]中完成相應(yīng)表項(xiàng)的添加。步驟S4、報(bào)文的轉(zhuǎn)發(fā)：根據(jù)查找到的相匹配的路由查找信息，判斷是普通路由還是ECMP路由，若是普通路由，則在確認(rèn)樹(shù)型路由表中葉子節(jié)點(diǎn)未發(fā)生變更的情況下，將報(bào)文按照查找到的普通路由查找信息進(jìn)行普通路由的轉(zhuǎn)發(fā)；若是ECMP路由，則在確認(rèn)樹(shù)型路由表中葉子節(jié)點(diǎn)未發(fā)生變更的情況下，將報(bào)文按照查找到的ECMP路由查找信息進(jìn)行ECMP路由的轉(zhuǎn)發(fā)。實(shí)際操作時(shí)，步驟S4具體包括以下操作：步驟S401：根據(jù)匹配到的沖突域成員Entry[i]中的ECMP標(biāo)志位Multipath字段，判斷是普通路由還是ECMP路由，若Multipath＝0表示普通路由，轉(zhuǎn)入步驟S402，若Multipath＝1表示ECMP路由，轉(zhuǎn)入步驟S403；步驟S402：獲取Entry[i]中的普通路由地址指針Rt，通過(guò)該指針獲取已有的樹(shù)型路由表的葉子節(jié)點(diǎn)，確認(rèn)該葉子節(jié)點(diǎn)未發(fā)生變更后，從Entry[i]中獲取存儲(chǔ)的普通路由下一跳MAC地址Edst_mac、普通路由接口值Ifidx、普通路由接口內(nèi)層Vlan值Subvlan和普通路由接口外層Vlan值Vlan；根據(jù)上述獲取的值，組裝報(bào)文的二層以太網(wǎng)頭部，并根據(jù)普通路由接口值Ifidx轉(zhuǎn)發(fā)到相應(yīng)的出接口上，完成報(bào)文普通路由的轉(zhuǎn)發(fā)，結(jié)束。步驟S403：根據(jù)Entry[i]中的ECMP地址指針Ecmp_ptr獲取ECMP成員信息表，并從Entry[i]中的ECMP成員總數(shù)值Ecmp_total獲取ECMP成員信息表中的成員個(gè)數(shù)，轉(zhuǎn)入步驟S404；步驟S404：遍歷ECMP成員信息表的所有成員，根據(jù)每個(gè)成員的ECMP路由地址指針Ecmp_Rt，獲取到所有成員對(duì)應(yīng)的樹(shù)型路由表的葉子節(jié)點(diǎn)，確認(rèn)所有葉子節(jié)點(diǎn)未發(fā)生變更后，轉(zhuǎn)入步驟S405；步驟S405：根據(jù)基于數(shù)據(jù)流的ECMP分流算法或基于報(bào)文逐包的ECMP分流算法，找出此次ECMP路由所對(duì)應(yīng)的ECMP成員；獲取該ECMP成員的ECMP下一跳MAC地址Ecmp_Edst_mac、ECMP接口值Ecmp_Ifidx、ECMP接口內(nèi)層Vlan值Ecmp_Subvlan和ECMP接口外層Vlan值Ecmp_vlan，轉(zhuǎn)入步驟S406；步驟S406：根據(jù)上述獲取到的值，組裝報(bào)文的二層以太網(wǎng)頭部，根據(jù)ECMP接口值Ecmp_Ifidx轉(zhuǎn)發(fā)到相應(yīng)的出接口上，完成報(bào)文ECMP路由的轉(zhuǎn)發(fā)，結(jié)束。進(jìn)一步地，步驟S405具體包括以下操作：步驟S405a：判斷逐包分流是否使能，若否，則提取報(bào)文的五元組(IP頭目的地址、源地址、TCP/UDP目的端口號(hào)、源端口號(hào)和入接口)通過(guò)CRC運(yùn)算，計(jì)算的哈希值HASH，轉(zhuǎn)入步驟S405b；若是，則轉(zhuǎn)入步驟S405c；步驟S405b：取ECMP成員信息表中的一個(gè)成員，該成員編號(hào)由HASH取余ECMP成員總數(shù)值得到，即該成員為ecmp_cache[HASH％Ecmp_total]，標(biāo)記為ecmp_cache[i]，轉(zhuǎn)入步驟S405d；步驟S405c：由Entry[i]中的ECMP成員使用值Ecmp_index，獲取ECMP成員信息表中成員編號(hào)為Ecmp_index的一個(gè)成員，即該成員為ecmp_cache[Ecmp_index]，標(biāo)記為ecmp_cache[i]；將Ecmp_index中的值加1，如果Ecmp_index大于Ecmp_total，則進(jìn)行一次取模運(yùn)算，即Ecmp_index＝Ecmp_index％Ecmp_total，完成上述操作后，轉(zhuǎn)入步驟S405d；步驟步驟S405d：根據(jù)獲得的ecmp_cache[i]，返回該成員的ECMP下一跳MAC地址Ecmp_Edst_mac、ECMP接口值Ecmp_Ifidx、ECMP接口內(nèi)層Vlan值Ecmp_Subvlan和ECMP接口外層Vlan值Ecmp_vlan。更進(jìn)一步地，步驟S4中，無(wú)論是普通路由還是ECMP路由，在確認(rèn)樹(shù)型路由表中葉子節(jié)點(diǎn)發(fā)生變更的情況下，均會(huì)執(zhí)行快表的更新操作，其具體流程為：若為普通路由，則直接對(duì)Entry[i]中的所有字段內(nèi)容進(jìn)行清除；然后，轉(zhuǎn)入步驟S3，重新對(duì)報(bào)文進(jìn)行快表表項(xiàng)的添加；若為ECMP路由，則需先對(duì)ECMP成員信息表(ecmp_cache)進(jìn)行內(nèi)存釋放；然后，對(duì)Entry[i]中的所有字段內(nèi)容進(jìn)行清除；最后，轉(zhuǎn)入步驟S3，重新對(duì)報(bào)文進(jìn)行快表表項(xiàng)的添加。另外，本發(fā)明實(shí)施例還提供一種路由器轉(zhuǎn)發(fā)平面的等價(jià)路由管理裝置，包括快表創(chuàng)建單元、快表查找單元、快表表項(xiàng)添加單元和報(bào)文轉(zhuǎn)發(fā)單元。其中，快表創(chuàng)建單元用于：在路由器轉(zhuǎn)發(fā)平面內(nèi)創(chuàng)建一個(gè)用于存儲(chǔ)普通路由查找信息和ECMP路由查找信息的快表，并向快表查找單元發(fā)送查找信號(hào)。快表查找單元用于：收到查找信號(hào)后，當(dāng)報(bào)文進(jìn)入路由器轉(zhuǎn)發(fā)平面時(shí)，提取報(bào)文中IP頭部的目的地址和VPN值，在創(chuàng)建的快表中進(jìn)行匹配查找，若未查找到相匹配的路由查找信息，向快表表項(xiàng)添加單元發(fā)送添加信號(hào)；若查找到相匹配的路由查找信息，向報(bào)文轉(zhuǎn)發(fā)單元發(fā)送轉(zhuǎn)發(fā)信號(hào)。其具體操作流程為：當(dāng)報(bào)文進(jìn)入路由器轉(zhuǎn)發(fā)平面后，提取報(bào)文中IP頭部的目的地址和VPN值，通過(guò)CRC運(yùn)算獲得32位的哈希值Hash_Value；在創(chuàng)建的快表中，用Hash_Value取余哈希桶的最大值Bucket_Max，得到Bucket[Hash_Value％Bucket_Max]表項(xiàng)，標(biāo)記為Bucket[j]，j為正整數(shù)；依次遍歷Bucket[j]中的每一個(gè)沖突域成員Entry，尋找有效位為1、狀態(tài)位為0的Entry，一旦找到，將找到的Entry標(biāo)記為Entry[i]，i為正整數(shù)且小于等于Bucket[j]中沖突域成員的個(gè)數(shù)，并將報(bào)文中提取的目的地址、VPN值分別與Entry[i]中的目的地址字段、實(shí)例號(hào)字段的值進(jìn)行比較，如果不匹配，則繼續(xù)遍歷尋找，如果匹配，則向報(bào)文轉(zhuǎn)發(fā)單元發(fā)送轉(zhuǎn)發(fā)信號(hào)；如果Bucket[j]中一直沒(méi)有找到，則表明表項(xiàng)尚未創(chuàng)建，向快表表項(xiàng)添加單元發(fā)送添加信號(hào)?？毂肀眄?xiàng)添加單元用于：收到添加信號(hào)后，利用報(bào)文中的目的地址和VPN值，通過(guò)在已有的樹(shù)型路由表中進(jìn)行路由表項(xiàng)查找的方式，判斷是普通路由還是ECMP路由，若是普通路由，則將目的地址解析所獲得的路由信息作為普通路由查找信息添加到快表中，并向快表查找單元發(fā)送查找信號(hào)；若是ECMP路由，則將目的地址解析所獲得的路由信息作為ECMP路由查找信息添加到快表中，并向快表查找單元發(fā)送查找信號(hào)。其具體操作流程為：所述快表表項(xiàng)添加單元依次遍歷Bucket[j]中的每一個(gè)沖突域成員Entry，找到有效位為1的Entry，標(biāo)記為Entry[k]，k為正整數(shù)且小于等于Bucket[j]中沖突域成員的個(gè)數(shù)；將Entry[k]中的目的地址字段、實(shí)例號(hào)字段分別填寫(xiě)成報(bào)文中的目的地址、VPN值，并將有效位置為1，狀態(tài)位置為1；將報(bào)文的目的地址、VPN值帶入到已有的樹(shù)型路由表中進(jìn)行路由表項(xiàng)的查找，根據(jù)路由的最長(zhǎng)掩碼匹配，查找到樹(shù)型路由表的葉子節(jié)點(diǎn)，檢測(cè)該葉子節(jié)點(diǎn)的狀態(tài)，判斷是否存在ECMP的路由；如果不存在，表示是普通路由，將該葉子節(jié)點(diǎn)的地址填入到Entry[k]中的普通路由地址指針字段中，將ECMP標(biāo)志位字段置為0；并解析報(bào)文的目的地址的ARP，獲取下一跳MAC地址信息、出接口值信息、內(nèi)層Vlan信息和外層Vlan信息，并將上述信息分別填入到Entry[k]中對(duì)應(yīng)的普通路由下一跳MAC地址字段、普通路由接口值字段、普通路由接口內(nèi)層Vlan值字段和普通路由接口外層Vlan值字段中，并將Entry[k]中的狀態(tài)位置為0；如果存在，表示是ECMP路由，申請(qǐng)內(nèi)存用于存儲(chǔ)ECMP成員信息表的數(shù)組；將Entry[k]中的ECMP標(biāo)志位字段置為1，將ECMP成員信息表的數(shù)組的地址值填入Entry[k]中的ECMP地址指針字段中，將ECMP成員的個(gè)數(shù)填入ECMP成員總數(shù)值字段中；依次獲取該葉子節(jié)點(diǎn)中的每一個(gè)ECMP成員，并解析每一個(gè)ECMP成員的目的地址的ARP，獲取其下一跳MAC地址信息、出接口值信息、內(nèi)層Vlan信息和外層Vlan信息，并將上述信息依次填入到的每一個(gè)ECMP成員對(duì)應(yīng)的ECMP下一跳MAC地址字段、ECMP接口值字段、ECMP接口內(nèi)層Vlan值字段、ECMP接口外層Vlan值字段中，并將Entry[k]中的狀態(tài)位置為0。報(bào)文轉(zhuǎn)發(fā)單元用于：收到轉(zhuǎn)發(fā)信號(hào)后，根據(jù)查找到的相匹配的路由查找信息，判斷是普通路由還是ECMP路由，若是普通路由，在確認(rèn)樹(shù)型路由表中葉子節(jié)點(diǎn)未發(fā)生變更的情況下，將報(bào)文按照查找到的普通路由查找信息進(jìn)行普通路由的轉(zhuǎn)發(fā)；若是ECMP路由，則在確認(rèn)樹(shù)型路由表中葉子節(jié)點(diǎn)未發(fā)生變更的情況下，將報(bào)文按照查找到的ECMP路由查找信息進(jìn)行ECMP路由的轉(zhuǎn)發(fā)。其具體操作流程為：根據(jù)匹配到的沖突域成員Entry[i]中的ECMP標(biāo)志位字段，判斷是普通路由還是ECMP路由；若是普通路由，獲取Entry[i]中的普通路由地址指針，通過(guò)該指針獲取已有的樹(shù)型路由表的葉子節(jié)點(diǎn)，確認(rèn)該葉子節(jié)點(diǎn)未發(fā)生變更后，從Entry[i]中獲取存儲(chǔ)的普通路由下一跳MAC地址、普通路由接口值、普通路由接口內(nèi)層Vlan值和普通路由接口外層Vlan值；根據(jù)上述獲取的值，組裝報(bào)文的二層以太網(wǎng)頭部，并根據(jù)普通路由接口值轉(zhuǎn)發(fā)到相應(yīng)的出接口上，完成報(bào)文普通路由的轉(zhuǎn)發(fā)；若是ECMP路由，根據(jù)Entry[i]中的ECMP地址指針獲取ECMP成員信息表，并從Entry[i]中的ECMP成員總數(shù)值獲取ECMP成員信息表中的成員個(gè)數(shù)；遍歷ECMP成員信息表的所有成員，根據(jù)每個(gè)成員的ECMP路由地址指針，獲取到所有成員對(duì)應(yīng)的樹(shù)型路由表的葉子節(jié)點(diǎn)，確認(rèn)所有葉子節(jié)點(diǎn)未發(fā)生變更后，根據(jù)基于數(shù)據(jù)流的ECMP分流算法或基于報(bào)文逐包的ECMP分流算法找出此次ECMP路由所對(duì)應(yīng)的ECMP成員；獲取該ECMP成員的ECMP下一跳MAC地址、ECMP接口值、ECMP接口內(nèi)層Vlan值和ECMP接口外層Vlan值；根據(jù)上述獲取到的值，組裝報(bào)文的二層以太網(wǎng)頭部，根據(jù)ECMP接口值轉(zhuǎn)發(fā)到相應(yīng)的出接口上，完成報(bào)文ECMP路由的轉(zhuǎn)發(fā)。更進(jìn)一步地，該裝置還包括快表表項(xiàng)更新單元，所述快表表項(xiàng)更新單元在報(bào)文轉(zhuǎn)發(fā)單元確認(rèn)樹(shù)型路由表中葉子節(jié)點(diǎn)發(fā)生變更的情況下，執(zhí)行快表表現(xiàn)的更新操作，其具體流程為：若為普通路由，則直接對(duì)Entry[i]中的所有字段內(nèi)容進(jìn)行清除；然后，向快表表項(xiàng)添加單元發(fā)送添加信號(hào)，重新對(duì)報(bào)文進(jìn)行快表表項(xiàng)的添加；若為ECMP路由，則需先對(duì)ECMP成員信息表進(jìn)行內(nèi)存釋放；然后，對(duì)Entry[i]中的所有字段內(nèi)容進(jìn)行清除；最后，向快表表項(xiàng)添加單元發(fā)送添加信號(hào)，重新對(duì)報(bào)文進(jìn)行快表表項(xiàng)的添加。需要說(shuō)明的是：上述實(shí)施例提供的系統(tǒng)在進(jìn)行操作時(shí)，僅以上述各功能模塊的劃分進(jìn)行舉例說(shuō)明，實(shí)際應(yīng)用中，可以根據(jù)需要而將上述功能分配由不同的功能模塊完成，即將系統(tǒng)的內(nèi)部結(jié)構(gòu)劃分成不同的功能模塊，以完成以上描述的全部或者部分功能。本發(fā)明不局限于上述實(shí)施方式，對(duì)于本
技術(shù)領(lǐng)域：
的普通技術(shù)人員來(lái)說(shuō)，在不脫離本發(fā)明原理的前提下，還可以做出若干改進(jìn)和潤(rùn)飾，這些改進(jìn)和潤(rùn)飾也視為本發(fā)明的保護(hù)范圍之內(nèi)。本說(shuō)明書(shū)中未作詳細(xì)描述的內(nèi)容屬于本領(lǐng)域?qū)I(yè)技術(shù)人員公知的現(xiàn)有技術(shù)。當(dāng)前第1頁(yè)1 2 3