構造路由表及用其查找路由項的方法
2023-04-27 03:21:16
專利名稱：構造路由表及用其查找路由項的方法
技術領域：
本發明屬於數據通訊技術領域，特別涉及網際網路中進行路由選擇技術。
背景技術：
在網際網路中進行路由選擇要使用路由器，路由器根據所收到的IP數據報文上的目的IP位址決定將報文向何處發送。所謂IP位址就是給每一個連接在Internet上的埠分配的一個唯一的32位地址。IP位址由兩部分組成第一部分為網絡號，第二部分為主機號。但是由於網絡發展的需要，現在已進一步將主機號再分成一個子網號和一個主機號。子網掩碼就是用來確定IP位址中多少位用於子網號，多少位用於主機號的。為了指導路由器轉發報文的工作，每一臺路由器都有一個路由表，路由表中存放路由項。每一個路由項都包含如下信息1、目的IP位址它既可以是一個完整的主機地址，也可以是一個網絡地址，主機地址有一個非0的主機號，以指定某一特定的主機，而網絡地址中的主機號為0，以指定某一網絡中的所有主機。2、子網掩碼通過子網掩碼可以進一步知道目的IP位址的子網號。3、輸出埠說明IP數據報文應從路由器哪個埠發送出去。4、下一跳IP位址說明IP數據報文要到達的下一個設備的IP位址。路由器收到IP數據報文後，根據報文中的目的IP位址在路由表中查找到匹配的路由項，然後從路由項中指明的輸出埠將報文轉發出去。
在路由表中可能出現路由覆蓋的現象，即對於某個特定的目的IP位址，有多個子網掩碼不同的路由項對應。目的IP位址相同的情況下，子網掩碼長的路由項是子網掩碼短的路由項的子路由項，子網掩碼短的路由項是子網掩碼長的路由項的父路由項。查找路由表的目標就是為了找到一個最能匹配給定目的IP位址的特定路由項。所謂最能匹配的路由項，也就是說，一個網絡號、子網號、主機號都能夠匹配的路由項要優於一個網絡號、子網號能匹配的路由項；而一個網絡號、子網號能匹配的路由項要優於一個網絡號匹配的路由項。
路由器每轉發一次IP數據報文就要通過路由表查找一遍路由項，因此路由表的查找速率是影響路由器轉發效率的關鍵因素。同時，路由項可以通過用戶手工配置得到，也可以通過運行動態路由協議自動得到。動態路由協議可能在短時間內學習到成千上萬條路由項，所以，在路由表中快速添加刪除路由項的能力也很重要。
現有的常見的構建路由表的方法是利用二叉樹來構建路由表，如圖1所示，根據目的IP位址從高位到低位，每一位是0或1來確定是在二叉樹的左分支還是右分支。用這種結構的路由表存放路由項的方法，比較直觀，有層次，但是添加刪除過程複雜，查找效率低。由圖1可見，如果要查找一條子網掩碼長度為4的路由項，要查找4次，而如果要查找一條子網掩碼長度為32位的主機路由項，則需要查找32次。
用二叉樹形式的路由表來存放路由項，在查找時幾乎每一個路由項都要經過數次或數十次的查找才能找到，極大影響了路由器的轉發效率。此外該方法的擴充性不好，例如對於128位的IPv6地址，找一個路由項的查找次數可能達到上百次，這幾乎是不能忍受的。
發明內容
本發明的目的是為克服已有技術的不足之處，提供一種構造路由表及用其查找路由項的方法，本發明具有維護方便，查找路由項高效快速，且可自動擴充的特點。
本發明提出的一種構造路由表的方法，包括a、生成一級或多級索引表；b、將路由項按照所述各級索引表長度分段存儲在所述的索引表中。
所述第i級索引表的長度可為Ni，其中Ni為自然數。
所述第i級索引表中可包括2Ni個索引結點。
所述索引結點可順序排列。
所述多級索引表中第一級索引表固定生成，其它各級索引表可在添加新路由項的過程中動態產生。
除所述第一級以外的其它各級索引表的表項還可包括表頭域，該表頭域中包含一個計數器。
所述索引結點指向內容可包括指向某一路由項、指向下一級索引表、指向空。
所述生成索引表可包括以下步驟1)路由器啟動時即創建一級索引表，有2N1個索引結點，索引結點都指向空；2)在添加新路由項的過程中，如果有路由項的子網掩碼長度大於N1，小於等於N1+N2，會創建二級索引表，如果有路由項的子網掩碼長度大於N1+N2，小於等於N1+N2+N3，會創建二級和三級索引表，以此類推；3)如果不再有子網掩碼長度大於N1+N2+...+Np-1，小於等於N1+N2+...+Np-1+Np的路由項，會刪除第p級索引表，p為當前索引表的最高級數。
所述添加新路由項，具體可包括以下步驟1)如果路由項的子網掩碼長度L小於等於N1位，在一級索引表中找到索引號和目的IP位址的前N1位值相同的索引結點，從這個結點開始，索引號依次遞增的2(N1-L)個索引結點都指向此路由項；2)如果路由項的子網掩碼長度L大於N1位，小於等於N1+N2位，在一級索引表中找到索引號和目標IP位址的前N1位值相同的索引結點，判斷此索引結點的內容21)如果此索引結點沒有指向一個二級索引表，先建立一個設有表頭域的二級索引表，這個表有2N2個索引結點，索引結點的索引號依次為0到2N2，表頭域中計數器值為0，找到索引號和路由項的目的IP位址的第N1+1至N1+1+N2位值相同的索引結點，從此結點開始，往後的2(N2-(L-N1))個索引結點都指向該路由項，其它索引結點指向空；
22)如果此索引結點指向一個二級索引表，直接在這個二級索引表中找到索引號和路由項的目的IP位址的第N1+1至N1+1+N2位值相同的索引結點，從此結點開始，往後的2(N2-(L-N1))個索引結點都指向該路由項；3)如果路由項的子網掩碼長度L大於N1+N2，小於等於N1+N2+N3，則要在三級索引表中添加路由項，則具體步驟和在二級索引表中添加路由項類似，以此類推；4)如果要指向新路由項的索引結點原來並不指向空，而指向一個已有的路由項，則需要判斷兩個路由項的子網掩碼長度；41)如果新路由項的子網掩碼長度小於已有的路由項的，則新路由項為父路由項，直接將已有的路由項指向新路由項，索引結點內容不變；42)如果新路由項的子網掩碼長度大於已有的路由項的，則已有路由項為父路由項，將新路由項指向已有的路由項，索引結點指向新路由項；5)如果要指向新路由項的索引結點原來是指向下一級索引表表頭域的，則直接將表頭域指向新路由項；如果表頭域原來也指向了一個已有的路由項，則比較已有的路由項和新路由項的子網掩碼的長度，最終由表頭域指向子路由項，子路由項指向父路由項；6)如果索引結點需要指向新建立的下一級索引表，而該索引結點原來已指向一已有路由項，只需要將該索引結點指向下一級索引表表頭域，將表頭域指向已有路由項。
所述刪除路由項，具體可包括以下步驟1)如果要刪除的路由項不指向其它路由項，則直接將指向要刪除的路由項的索引結點或子路由項指向空，將存放要刪除的路由項的內存釋放；2)如果要刪除的路由項指向父路由項，則將指向要刪除的路由項的索引結點或子路由項直接指向父路由項，將存放要刪除的路由項的內存釋放；3)如果刪除路由項後，使動態生成的索引表中表頭裡的計數器值為0，即索引表中沒有索引結點指向路由項了，要將此索引表刪除；
4)如果待刪索引表表頭域指向空，則指向它的上一級索引表中的索引結點也指向空；5)如果待刪索引表表頭域指向一父路由項，則將指向表頭域的索引結點指向父路由項；將存放動態索引表的內存釋放。
本發明提出的一種查找路由項的方法，其特徵在於，採用分級索引表構造路由表，查找路由項包括以下步驟1)對IP數據報文中目的IP位址取前N1位，在一級索引表中找到索引號與之相等的索引結點；2)如果此索引結點指向路由項，則表明路由項找到；3)如果索引結點指向空，表明路由項沒有找到；4)如果索引結點指向下一級索引表，則在二級索引表中找到索引號和目的IP位址第N1+1位至第N1+1+N2位的值相等的索引結點，如果該索引結點指向路由項，表明路由項找到；5)如果該索引結點指向空，則看本級索引表的表頭域，如果表頭域指向某一路由項，表明路由項找到，如果表頭域指向空，表明路由項沒有找到；6)如果索引結點指向下一級索引表，則根據目的IP址的第N1+N2+1位至第N1+N2+1+N3位的值在三級索引表中繼續查找，查找方法和在二級索引表中查找的方法一樣，以此類推查找到目的IP位址的最後位。
本發明帶來的有益效果利用本發明的技術方案構造路由表，根據任何目的IP位址查找路由項，最多只需要查找M次(M值為索引表的級數)，而且很大部分的路由項可以一次查到，大大提高了路由表的查找效率。其次，這種方法也很好的解決了路由表的維護問題，無論添加刪除路由項，操作步驟都較少，維護效率高。同時，由於低級索引表是動態產生，動態刪除的，可以節省內存資源。
本發明的擴展性也很好，索引表的級數可根據情況調整，每一級索引結點的數目也可以根據具體情況設定。例如，可以將索引表設為三級，該三級索引表的一級索引表有216個索引結點，每個二級索引表有28個索引結點，每個三級索引表也有28個索引結點。在三級分級索引表中查找路由項，簡單快速，最多查找3次即能找到需要的路由項。
也可以將索引表設為四級，第一級有220個索引結點，第二級、第三級、第四級都有24個索引結點，這樣雖然一級索引表佔用的內存大一些，但是可以確保有62.5％的目的IP位址可以一次查到路由，提高總體轉發速率。在IPv6協議裡，IPv6地址長度達到128位，採用本方法可以建立更多級的索引表來適應，而且只要控制好索引表的級數，路由查找的效率仍然是非常高的。
圖1為現有的利用二叉樹來存放路由路由的方法示意圖。
圖2為本發明構造的多級索引表形式的路由表中各級索引表、索引結點、路由項關係圖。
圖3為本發明採用三級索引表形式的路由表查找路由項的方法流程圖。
具體實施例方式
本發明提出的構造的路由表及用其查找路由項的方法，下面結合實施例及附圖進行詳細說明。
一、本發明採用多級索引表構造的路由表，如圖2所示，詳細說明如下查找路由項的主要線索是路由項中的目的IP位址，所以本發明以索引表的形式構建路由表，索引表中每一表項的索引號和路由項中的目的IP位址建立某種聯繫，達到快速查找的目的。同時，利用路由項有子網掩碼的特點，本發明將索引表分級，子網掩碼短的路由項放在高級索引表中，子網掩碼長的路由項放在低級索引表中。最高級的索引表，即一級索引表固定生成，其它低級索引表動態產生，這種分級的索引表在確保查找效率的同時，又大大節省了內存。
本發明稱索引表中的每一個表項為一個索引結點，每個索引結點有一個索引號，索引號按照索引結點的排列從0依次遞增，如第一個索引結點的索引號為0，第二個索引結點的索引號為1，以此類推。索引結點可能指向三種內容1、指向某一路由項；2、指向下一級索引表；3、指向空。當然，最後一級索引表的索引結點不能指向下一級索引表，只能指向路由項或空。除了一級索引表，其它各級索引表還設有表頭域，表頭域內可包含一個計數器，記錄本索引表中有多少個索引結點不指向空，以便在本索引表中所有索引結點都指向空時刪除此表。
索引表具體分為幾級，每一級有多少個結點，沒有特定值，但必須滿足以下要求假設索引表分為m級，每一級的結點數必須是2的Ni次冪(Ni為自然數)，對於32位地址，需要滿足以下公式N1+N2+......+Nm＝32；對於128位的IPv6地址，則N1+N2+......+Nm＝128。
本發明以一個三級索引表為實施例，詳細介紹分級索引表的建立、添加、刪除路由項和查找路由項方法。
在本實施例中，一級索引表由索引結點構成，二、三級索引表由表頭域和索引結點構成，其中，三級索引表中的一級索引表有216個索引結點，每個二級索引表有28個索引結點，每個三級索引表也有28個索引結點。
本實施例的構造路由表的方法為路由器啟動時即創建一級索引表，有216個索引結點，索引結點都指向空。當有新路由項產生時，根據路由項中的目的IP位址和子網掩碼將合適的索引結點指向此路由項，具體構造步驟如下1、如果路由項的子網掩碼長度L小於等於16位，找到索引號和目的IP位址的前16位值相同的索引結點，從這個結點開始，索引號依次遞增的2(16-L)個索引結點都指向此路由項。
2、如果路由項的子網掩碼長度L大於16位，小於等於24位，在一級索引表中找到索引號和目標IP位址的前16位值相同的索引結點，判斷此索引結點的內容21、如果此索引結點沒有指向一個二級索引表，先建立一個設有表頭域的二級索引表，這個表有28個索引結點，索引結點的索引號依次為0到28，表頭域中計數器值為0，找到索引號和路由項的目的IP位址的第17至24位值相同的索引結點，從此結點開始，往後的2(8-(L-16))個索引結點都指向該路由項，其它索引結點指向空；22、如果此索引結點指向一個二級索引表，直接在這個二級索引表中找到索引號和路由項的目的IP位址的第17至24位值相同的索引結點，從此結點開始，往後的2(8-(L-16))個索引結點都指向該路由項；3、如果路由項的子網掩碼長度L大於24，小於等於32，則要在二級索引表的基礎上繼續創建三級索引表。具體步驟和創建二級索引表類似，這裡就不贅述了。
4、如果要指向新路由項R2的索引結點原來並不指向空，而指向一個已有的路由項R1，則需要判斷兩個路由項的子網掩碼長度；41、如果R2的子網掩碼長度小於R1的，說明R2是R1的父路由項，只用直接將R1指向R2就行了，索引結點內容不變；42、如果R2的子網掩碼長度大於R1的，說明R1是R2的父路由項，將R2指向R1，索引結點指向R2；5、如果要指向新路由項R2的索引結點原來是指向下一級索引表表頭域的，則直接將表頭域指向R2；6、如果表頭域原來也指向了一個已有的路由項R1，也要比較一下R1和R2的子網掩碼的長度，最終表頭域指向子路由項，子路由項指向父路由項；7、如果指向新路由項R2的索引結點需要指向新建立的下一級索引表，而該索引結點原來已指向一已有路由項R1，只需要將索引結點指向下一級索引表表頭域，將表頭域指向R1就行了。
本實施例在路由表中內容的刪除的方法，具體步驟如下1、如果要刪除的路由項R2不指向其它路由項，則直接將指向R2的索引結點或子路由項指向空，將存放路由項R2的內存釋放；2、如果要刪除的路由項R2指向了父路由項R1，則將指向R2的索引結點或子路由項直接指向R1，將存放路由項R2的內存釋放；3、如果刪除路由項後，動態生成的索引表中表頭裡的計數器值為0，即索引表中沒有索引結點指向路由項了，要將此索引表刪除4、如果待刪索引表表頭域指向空，則指向它的上一級索引表中的索引結點也指向空；5、如果待刪索引表表頭域指向一路由項R1，則將指向表頭域的索引結點指向R1。將存放動態索引表的內存釋放。
由上面描述可見，除了一級索引表是固定產生的外，其它各級索引表都是動態產生，動態刪除的，可以節省大量內存。而表頭域的存在除了可以方便的判斷刪除動態索引表的時機外，還帶來了一個很直接的好處，這就是在一個索引表中增加或刪除路由結點時，不會影響到它所有的下級索引表，至多會修改某些下級索引表中表頭域的一個指針。通過這種特殊的結構，極大提高了路由表的維護效率，即使有路由覆蓋的情況，維護路由表的操作也較簡單。
二、本發明採用上述路由表查找路由項的方法實施例，如圖3所示，詳細說明如下路由器轉發IP數據報文時要查找路由表中的路由項；查找的依據是IP數據報文中所帶的目的IP位址，即路由項中的內容。本實施例的路由表為三級索引表，具體查找方法的步驟如下1、取IP數據報文中目的IP位址的前16位；2、在一級索引表中找到索引號與之相等的索引結點，3、判斷索引結點內容4、如果此索引結點指向路由項，則表明路由項找到，返回；5、如果索引結點指向空，表明路由項沒有找到，返回；
6、如果索引結點指向下一級索引表，則在二級索引表中找到索引號和目的IP位址第17位至第24位的值相等的索引結點；7、判斷索引結點內容8、如果該索引結點指向路由項，表明路由項找到，返回；9、如果該索引結點指向空，則看本級索引表的表頭域，如果表頭域指向某一路由項，表明路由項找到，返回；10、如果表頭域指向空，表明路由項沒有找到，返回；11、如果索引結點指向下一級索引表，則根據目的IP位址的第25位至32位的值在三級索引表中繼續查找，查找方法和在二級索引表中查找的方法一樣，如步驟7、8、9、10所述。
在三級分級索引表中查找路由項，簡單快速，最多查找3次即能找到需要的路由項。
本發明的索引表不限於用三級，可根據情況調整為更多或更少級，每一級索引結點的數目也可以根據具體情況設定。例如，可以將索引表設為四級，第一級有220個索引結點，第二級、第三級、第四級都有24個索引結點，這樣雖然一級索引表佔用的內存大一些，但是可以確保有62.5％的目的IP位址可以一次查到路由，提高總體轉發速率。
權利要求
1.一種構造路由表的方法，其特徵在於a、生成一級或多級索引表；b、將路由項按照所述各級索引表長度分段存儲在所述的索引表中。
2.如權利要求1所述語構造路由表的方法，其特徵在於，所述第i級索引表的長度為Ni，其中Ni為自然數。
3.如權利要求2所述語構造路由表的方法，其特徵在於，所述第i級索引表中包括2Ni個索引結點。
4.如權利要求3所述語構造路由表的方法，其特徵在於，所述索引結點順序排列。
5.如權利要求1所述的構造路由表的方法，其特徵在於，所述多級索引表中第一級索引表固定生成，其它各級索引表在添加新路由項的過程中動態產生。
6.如權利要求1所述的構造路由表的方法，其特徵在於，除所述第一級以外的其它各級索引表的表項還包括表頭域，該表頭域中包含一個計數器。
7.如權利要求3所述的構造路由表的方法，其特徵在於，所述索引結點指向內容包括指向某一路由項、指向下一級索引表、指向空。
8.如權利要求3所述的構造路由表的方法，其特徵在於，所述生成索引表包括以下步驟1)路由器啟動時即創建一級索引表，有2N1個索引結點，索引結點都指向空；2)在添加新路由項的過程中，如果有路由項的子網掩碼長度大於N1，小於等於N1+N2，會創建二級索引表，如果有路由項的子網掩碼長度大於N1+N2，小於等於N1+N2+N3，會創建二級和三級索引表，以此類推；3)如果不再有子網掩碼長度大於N1+N2+...+Np-1，小於等於N1+N2+...+Np-1+Np的路由項，會刪除第p級索引表，p為當前索引表的最高級數。
9.如權利要求5或8所述的構造路由表的方法，其特徵在於，所述添加新路由項，具體包括以下步驟1)如果路由項的子網掩碼長度L小於等於N1位，在一級索引表中找到索引號和目的IP位址的前N1位值相同的索引結點，從這個結點開始，索引號依次遞增的2(N1-L)個索引結點都指向此路由項；2)如果路由項的子網掩碼長度L大於N1位，小於等於N1+N2位，在一級索引表中找到索引號和目標IP位址的前N1位值相同的索引結點，判斷此索引結點的內容21)如果此索引結點沒有指向一個二級索引表，先建立一個設有表頭域的二級索引表，這個表有2N2個索引結點，索引結點的索引號依次為0到2N2，表頭域中計數器值為0，找到索引號和路由項的目的IP位址的第N1+1至N1+1+N2位值相同的索引結點，從此結點開始，往後的2(N2-(L-N1))個索引結點都指向該路由項，其它索引結點指向空；22)如果此索引結點指向一個二級索引表，直接在這個二級索引表中找到索引號和路由項的目的IP位址的第N1+1至N1+1+N2位值相同的索引結點，從此結點開始，往後的2(N2-(L-N1))個索引結點都指向該路由項；3)如果路由項的子網掩碼長度L大於N1+N2，小於等於N1+N2+N3，則要在三級索引表中添加路由項，則具體步驟和在二級索引表中添加路由項類似，以此類推；4)如果要指向新路由項的索引結點原來並不指向空，而指向一個已有的路由項，則需要判斷兩個路由項的子網掩碼長度；41)如果新路由項的子網掩碼長度小於已有的路由項的，則新路由項為父路由項，直接將已有的路由項指向新路由項，索引結點內容不變；42)如果新路由項的子網掩碼長度大於已有的路由項的，則已有路由項為父路由項，將新路由項指向已有的路由項，索引結點指向新路由項；5)如果要指向新路由項的索引結點原來是指向下一級索引表表頭域的，則直接將表頭域指向新路由項；如果表頭域原來也指向了一個已有的路由項，則比較已有的路由項和新路由項的子網掩碼的長度，最終由表頭域指向子路由項，子路由項指向父路由項；6)如果索引結點需要指向新建立的下一級索引表，而該索引結點原來已指向一已有路由項，只需要將該索引結點指向下一級索引表表頭域，將表頭域指向已有路由項。
10.如權利要求8所述的構造路由表的方法，其特徵在於，所述刪除路由項，具體包括以下步驟1)如果要刪除的路由項不指向其它路由項，則直接將指向要刪除的路由項的索引結點或子路由項指向空，將存放要刪除的路由項的內存釋放；2)如果要刪除的路由項指向父路由項，則將指向要刪除的路由項的索引結點或子路由項直接指向父路由項，將存放要刪除的路由項的內存釋放；3)如果刪除路由項後，使動態生成的索引表中表頭裡的計數器值為0，即索引表中沒有索引結點指向路由項了，要將此索引表刪除；4)如果待刪索引表表頭域指向空，則指向它的上一級索引表中的索引結點也指向空；5)如果待刪索引表表頭域指向一父路由項，則將指向表頭域的索引結點指向父路由項；將存放動態索引表的內存釋放。
11.一種查找路由項的方法，其特徵在於，採用多級索引表構造路由表，查找路由項包括以下步驟1)對IP數據報文中目的IP位址取前N1位，在一級索引表中找到索引號與之相等的索引結點；2)如果此索引結點指向路由項，則表明路由項找到；3)如果索引結點指向空，表明路由項沒有找到；4)如果索引結點指向下一級索引表，則在二級索引表中找到索引號和目的IP位址第N1+1位至第N1+1+N2位的值相等的索引結點，如果該索引結點指向路由項，表明路由項找到；5)如果該索引結點指向空，則看本級索引表的表頭域，如果表頭域指向某一路由項，表明路由項找到，如果表頭域指向空，表明路由項沒有找到；6)如果索引結點指向下一級索引表，則根據目的IP址的第N1+N2+1位至第N1+N2+1+N3位的值在三級索引表中繼續查找，查找方法和在二級索引表中查找的方法一樣，以此類推查找到目的IP位址的最後位。
全文摘要
本發明屬於數據通訊技術領域，涉及構造路由表及用其查找路由項的方法。本方法包括路生成一級或多級索引表；將路由項按照所述各級索引表長度分段存儲在所述的索引表中。本發明具有維護方便，查找路由項高效快速，且可自動擴充的特點。
文檔編號H04L12/28GK1553655SQ03140559
公開日2004年12月8日 申請日期2003年5月29日 優先權日2003年5月29日
發明者朱英明, 郭寧 申請人:華為技術有限公司