[發(fā)明專利]路由表快速比對(duì)方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201611024154.X
• 申請(qǐng)日: 2016-11-17
• 公開(kāi)（公告）號(hào): CN106603414B
• 公開(kāi)（公告）日: 2020-04-10
• 發(fā)明（設(shè)計(jì)）人: 申涓;于婧;伊鵬;陳博;崔世建;陸志威
• 申請(qǐng)（專利權(quán)）人: 珠海高凌信息科技股份有限公司;國(guó)家數(shù)字交換系統(tǒng)工程技術(shù)研究中心
• 主分類號(hào): H04L12/741
• 分類號(hào): H04L12/741;H04L12/755
• 代理公司: 鄭州大通專利商標(biāo)代理有限公司 41111
• 代理人: 陳大通

技術(shù)領(lǐng)域

該發(fā)明涉及一種計(jì)算機(jī)網(wǎng)絡(luò)的處理方法，特別是涉及一種路由表快速比對(duì)方法。

背景技術(shù)

路由表比對(duì)用于判別兩個(gè)路由表的一致性，其基本思想是過(guò)濾路由表中內(nèi)容一致的表項(xiàng)，標(biāo)識(shí)出兩個(gè)路由表不一致的表項(xiàng)。路由表由多條表項(xiàng)組成，路由表比對(duì)過(guò)程就是路由表項(xiàng)的逐個(gè)比較過(guò)程。假設(shè)路由表R1和R2，表項(xiàng)個(gè)數(shù)分別為m1和m2，全遍歷情況下完成R1和R2比對(duì)至少要進(jìn)行m1*m2次表項(xiàng)比較。考慮到路由表的容量通常以百萬(wàn)級(jí)為單位，假定R1和R2的表項(xiàng)規(guī)模為500萬(wàn)條，即m1＝m2＝5000000，全遍歷情況下完成R1和R2比對(duì)最多將觸發(fā)2.5*10¹³次表項(xiàng)比較。因此，如何提高表項(xiàng)比較效率，實(shí)現(xiàn)路由表快速比對(duì)，是路由表比對(duì)尤其是大規(guī)模路由表比對(duì)要解決的重要問(wèn)題。

發(fā)明內(nèi)容

本發(fā)明克服了現(xiàn)有技術(shù)中，實(shí)現(xiàn)路由表快速比的效率有待提高的問(wèn)題，提供一種路由表快速比對(duì)方法。

本發(fā)明的技術(shù)解決方案是，提供一種具有以下步驟的路由表快速比對(duì)方法：其包括：

步驟一、將路由表按照前綴長(zhǎng)度拆分成多個(gè)路由子集，同一個(gè)路由子集中的路由表項(xiàng)具有相同的路由前綴；對(duì)每個(gè)路由子集，建立對(duì)應(yīng)的Bloom過(guò)濾器；

步驟二、整個(gè)路由表比對(duì)由多次路由比對(duì)過(guò)程實(shí)現(xiàn)，路由比對(duì)過(guò)程包括路由子集預(yù)判過(guò)程和路由表項(xiàng)精確比對(duì)過(guò)程；

步驟三、路由子集預(yù)判過(guò)程首先根據(jù)待比對(duì)表項(xiàng)的前綴長(zhǎng)度定位其對(duì)應(yīng)的路由子集，通過(guò)該路由子集的bloom過(guò)濾器進(jìn)行預(yù)判，即判斷對(duì)應(yīng)的路由子集中是否存在與該前綴匹配的路由表項(xiàng)，不存在則標(biāo)識(shí)待比對(duì)表項(xiàng)為“不一致”，存在則針對(duì)該路由子集進(jìn)一步執(zhí)行路由表項(xiàng)的精確比對(duì)；

步驟四、路由表項(xiàng)精確比對(duì)過(guò)程首先在路由子集中查找到與待比對(duì)表項(xiàng)路由前綴一致的路由表項(xiàng)，然后，按照預(yù)先定義好的判定兩條具有相同前綴的表項(xiàng)是否一致的判決條件，比較兩條表項(xiàng)相關(guān)屬性內(nèi)容，如下一跳IP地址、輸出端口等，根據(jù)判決結(jié)果為兩條表項(xiàng)打上相應(yīng)的“一致”或“不一致”標(biāo)識(shí)；

步驟五、整個(gè)路由表比對(duì)過(guò)程完成后，參加比對(duì)的兩個(gè)路由表的表項(xiàng)根據(jù)比對(duì)結(jié)果都打上了“一致”或“不一致”標(biāo)識(shí)。

所述步驟一中將路由表按照前綴長(zhǎng)度9～32拆分成24個(gè)路由子集，同一個(gè)路由子集中的路由表項(xiàng)具有相同的路由前綴；對(duì)每個(gè)路由子集，建立對(duì)應(yīng)的Bloom過(guò)濾器，一共用到24個(gè)Bloom過(guò)濾器。

所述步驟三中bloom過(guò)濾器預(yù)判的過(guò)程如下：首先用bloom過(guò)濾器進(jìn)行路由子集預(yù)判，根據(jù)待比對(duì)表項(xiàng)的前綴長(zhǎng)度定位其對(duì)應(yīng)的路由子集，再通過(guò)該路由子集的bloom過(guò)濾器進(jìn)行預(yù)判，即判斷對(duì)應(yīng)的路由子集中是否存在與該前綴匹配的路由表項(xiàng)；Bloom過(guò)濾器在判決某元素是否屬于某集合時(shí)，判決結(jié)果為“屬于”時(shí)，該元素實(shí)際上有可能不屬于該集合；判決結(jié)果為“不屬于”時(shí)，該元素實(shí)際上必定不屬于該集合。

所述步驟四中路由表項(xiàng)精確比對(duì)過(guò)程中，需要以待比對(duì)表項(xiàng)的路由前綴為索引，在路由子集中進(jìn)行查找，為了加速查找過(guò)程，建立路由子集的快速查找索引，如采用hash索引。

與現(xiàn)有技術(shù)相比，本發(fā)明路由表快速比對(duì)方法具有以下優(yōu)點(diǎn)：本發(fā)明結(jié)合路由比對(duì)的特點(diǎn)，通過(guò)劃分路由子集、引入Bloom過(guò)濾器進(jìn)行預(yù)判，以子集為單位減少路由比對(duì)次數(shù)，有效提高了路由表項(xiàng)的比較效率，實(shí)現(xiàn)路由表快速比對(duì)，尤其適用于大規(guī)模路由表的快速比對(duì)。

附圖說(shuō)明

圖1是本發(fā)明路由表快速比對(duì)方法的示意圖；

圖2是本發(fā)明路由表快速比對(duì)方法的詳細(xì)流程示意圖。

具體實(shí)施方式

下面結(jié)合附圖和具體實(shí)施方式對(duì)本發(fā)明路由表快速比對(duì)方法作進(jìn)一步說(shuō)明：如圖所示，本實(shí)施例提供一種大規(guī)模路由表快速比對(duì)方法。所述方法包括：將路由表按照前綴長(zhǎng)度拆分成多個(gè)路由子集，同一個(gè)路由子集中的路由表項(xiàng)具有相同的路由前綴；對(duì)每個(gè)路由子集，建立對(duì)應(yīng)的Bloom過(guò)濾器。

整個(gè)路由表比對(duì)由多次路由比對(duì)過(guò)程實(shí)現(xiàn)，路由比對(duì)過(guò)程包括路由子集預(yù)判過(guò)程和路由表項(xiàng)精確比對(duì)過(guò)程。

路由子集預(yù)判過(guò)程首先根據(jù)待比對(duì)表項(xiàng)的前綴長(zhǎng)度定位其對(duì)應(yīng)的路由子集，通過(guò)該路由子集的bloom過(guò)濾器進(jìn)行預(yù)判，即判斷對(duì)應(yīng)的路由子集中是否存在與該前綴匹配的路由表項(xiàng)，不存在則標(biāo)識(shí)待比對(duì)表項(xiàng)為“不一致”，存在則針對(duì)該路由子集進(jìn)一步執(zhí)行路由表項(xiàng)的精確比對(duì)。