一種多線程邊界網關協議並行處理方法
2023-10-10 06:08:19
專利名稱：一種多線程邊界網關協議並行處理方法
技術領域：
本發明屬於路由協議系統結構領域，尤其涉及高性能路由器邊界網關協議 BGP(Border Gateway Protocol)的線程級並行處理方法。
背景技術：
自上世紀90年代以來，Internet經歷了飛速發展的過程，已經從一個簡單的實驗性網絡演變成為一個巨大的商業網絡。路由器作為構建整個hternet核心網絡的重要設施，其體系結構經歷了從集中式路由器、分布式路由器到集群路由器的發展過程，然而路由器軟體技術的發展則相對比較滯後，協議性能提升受限使其難以滿足下一代^ternet發展的需求。特別是，隨著化切！！！討規模的快速增長以及各種網絡應用的大量湧現，運行BGP 的路由器需要處理的路由更新報文數量迅猛增長，對路由器的協議處理速度提出了更高要求。多核處理器的應用為提高BGP協議處理速度提供了重要手段。一方面，相對於單核處理器，多核處理器擁有豐富的計算資源，具有更高的工作頻率、低功耗和易擴展等特點，克服了單核處理器的計算瓶頸，並且可以支持線程級並行來幫助改善應用程式性能。另一方面，相對於集群結構，它具有分布式計算資源與共享存儲結構優勢，提供了更快的同步操作與更高的核間通信帶寬，能夠有效降低路由節點之間的通信同步開銷。因此，設計一種基於多核處理器的BGP多線程並行處理方法，通過有效利用多核多線程計算資源來提高BGP處理海量路由更新報文的計算速度，從而降低路由更新報文處理延遲及提高網絡收斂時間， 具有重要實踐意義。現有專利(公開號為CN101741705A)公開了一種BGP多線程結構來實現並行處理路由更新報文的方法，它採用分層處理方式，通過劃分多線程，使BGP軟體在多核環境下多線程並行處理路由更新報文，其典型過程(如圖1)主要包含以下步驟1、類別項預計算BGP按照路由地址前綴分布將全部路由信息分類計算為ρ個類別項，P為可變的自然數，將不同前綴範圍的路由信息放進不同的類別項，類別項可以為散列表的表項、樹結構中的子樹等數據結構，不同類別項內部的地址前綴之間沒有交叉，且所有類別項的地址前綴集合為所有目標地址總和。2、構建BGP多線程結構它由一個鄰居管理和前處理前綴分類線程與多個選路線程組成。其中，鄰居管理與前處理前綴分類線程由多個鄰居管理單元與一個前處理前綴分類單元組成。鄰居管理與前處理前綴分類線程將BGP鄰居劃分為多個子集，這些子集分別稱為「鄰居束1」、「鄰居束2」、…、「鄰居束ρ」。選路線程根據類別項劃分為η個，η為可變自然數，它需要根據處理器核的數量與P進行調整，以達到軟體最優性能。例如，假設核的數量為4，ρ、η可以調成4，如果處理的報文較多，也可以將ρ、η調成8。3、解析報文鄰居管理單元i (i為自然數且KiSp)用於處理與鄰居束i的會話關係，處理過程中僅使用本鄰居束中的鄰居信息、路由信息及出口策略信息。鄰居管理單元i從鄰居束i的一個鄰居接收到路由更新報文以後，解析出路由更新報文中的目的地址和路由屬性，並封裝成消息發送給前處理前綴分類單元。
4、查找類別項前處理前綴分類單元獲得解析出的目的地址和路由屬性組成的消息，根據目的地址查找類別項，按照查找到的類別項，向與該類別項對應的選路線程j(j為自然數且KjSn)發送攜帶目的地址和路由屬性的消息。5、選路計算選路線程j根據消息中網絡地址和路由屬性在類別項中選擇最優路徑，計算最優路徑需要根據預定標準進行衡量，例如路徑長度、可靠性、延遲、帶寬、負載、 通信代價等權值，繼而將最優路徑發送給鄰居管理與前處理前綴分類線程中所有P個鄰居
管理單元。6、路由更新播報所有ρ個鄰居管理單元接收到選路線程j發送的最優路徑後，每個鄰居管理單元都會對本單元負責的鄰居束中的每個鄰居，對發送來的最優路徑進行該鄰居的出口策略過濾，將經過過濾的路由打包發送給該鄰居。7、當有新的路由更新報文達到，轉步驟3。上述方法實現了 BGP在多核處理器上多個線程並行處理路由更新報文，提高了工作效率，但該方法仍存在一些不足(1)由於該方法將對單個路由更新報文的解析與封裝、選路計算過程分布在兩個線程上並行執行，導致線程之間需要進行頻繁通信，降低了工作效率；(2)該方法將全局路由信息預先劃分為固定的類別項，無法反映選路線程訪問類別項的真實情況，極易出現多個選路線程同時訪問同一類別項而產生大量訪存競爭，使得選路線程之間無法真正並行工作，限制了 BGP處理路由更新報文處理速度的繼續提升。
發明內容
本發明要解決的技術問題在於提供一種多線程BGP並行處理方法，在降低線程間通信開銷、減少線程之間訪存競爭的前提下，充分利用多核處理器多線程並行執行優勢， 加快BGP處理路由更新報文速度。本發明技術方案如下步驟1、構建BGP多線程結構。它採用主從處理方式，由一個主控線程和L個協議執行線程組成，L為可變自然數，L根據公式L = CXD-I來確定，其中C為多核處理器的核數，D為多核處理器每個核可支持的最大線程數。主控線程是執行BGP鄰居分配、全局路由信息動態組織的軟體線程，由鄰居分配模塊與路由表重構模塊組成。鄰居分配模塊是用於計算鄰居與協議執行線程對應關係的軟體代碼，路由表重構模塊是用於動態更新全局路由表結構的軟體代碼。協議執行線程是完成與鄰居束的具體會話關係的軟體線程，由鄰居管理模塊、選路模塊與路由廣播模塊組成。鄰居管理模塊是用於完成與鄰居束中各鄰居的會話建立與通信的軟體代碼，選路模塊是執行最優路徑選擇的軟體代碼，路由廣播模塊是用於向其他協議執行線程發布本地最優路徑的軟體代碼。步驟2、路由表重構模塊設置路由表重構定時器，對全局路由信息進行周期性動態重構，方法是2. 1啟動路由表重構定時器。路由表重構定時器為一個計時程序，計時時間設定為路由通告最大時間間隔。若路由表重構定時器未超時，由鄰居分配模塊執行步驟3 ；若路由表重構定時器超時，路由表重構模塊執行2. 2 ；2. 2重構路由表結構。當路由表重構定時器超時時，首先設置超時標識，便於協議執行線程查詢，然後路由表重構模塊將傳統路由表邏輯劃分成若干個子樹集合，並構建快速索引樹，具體方法是2. 2. 1路由表重構模塊對路由表進行後序遍歷(見《數據結構與算法分析》中第四章，(美)維斯著，馮舜璽譯，機械工業出版社，2004年第一版)，統計路由表在定時器計時周期內各路由節點被訪問總次數T，T為自然數。路由表以二叉樹結構組織，每訪問一個路由節點時累計路由表重構定時器計時期間該節點及它的左右子樹被訪問的次數(左右子樹是以左右子節點為根的二叉樹)；2. 2. 2對路由表執行層次遍歷(見《數據結構與算法分析》中第四章，(美)維斯著，馮舜璽譯，機械工業出版社，2004年第一版)，將路由表邏輯地劃分為若干個路由表子樹(簡稱子樹)，且子樹數量上限為U，U為自然數，U根據公式U= μ XM確定，其中μ為子樹數量參考係數，為大於等於4且小於等於64的偶數，M為劃分子樹集合數量，M為可變自然數，M根據公式M = 2XL來確定。具體方法是2. 2. 2. 1如果當前路由節點的左右子節點與左右子樹訪問次數均大於TXr1JU 路由表重構模塊對該節點的左右子樹執行剪枝操作(見《數據結構與算法分析》中第四章， (美)維斯著，馮舜璽譯，機械工業出版社，2004年第一版)，將左右子樹邏輯地劃分為獨立的子樹，執行2. 2. 2. 2 ；否則，直接執行2. 2. 2. 2 ；2. 2. 2. 2如果當前路由節點所在的路由表二叉樹分層中還有其他未遍歷的節點，則路由表重構模塊繼續按由左至右的順序遍歷下一個節點，轉2. 2. 2. 1 ；否則執行 2 · 2 · 2 · 3 ；2. 2. 2. 3如果已遍歷路由表二叉樹中所有分層及節點，則轉2. 2. 3 ；否則，路由表重構模塊跳至路由表二叉樹的下一個分層中繼續遍歷，轉2. 2. 2. 1。2. 2. 3路由表重構模塊將步驟2. 2. 2中劃分的子樹歸類為M個子樹集合 Q1,......，％。具體方法是2. 2. 3. 1路由表重構模塊將劃分後的子樹按照訪問次數進行降序排列後得到路由表子樹序列 ，3-2， · · ·，；2. 2. 3. 2累加子樹集合仏(1 < i彡M)中所有子樹的訪問次數，計算出仏訪問總次數，再將所有子樹集合按照訪問總次數降序排列，獲得訪問總次數最小和最大的子樹集合Qa和Qe，Qa (α為子樹集合的下標，a ^M)表示訪問次數最小的子樹集合，Q0 (β 為子樹集合的下標，1 ^ β ^ Μ)表示訪問次數最大的子樹集合；2. 2. 3. 3從子樹序列a1; a2，-,au中取出頭子樹 (1彡s彡U)，s初始值為1，放入子樹集合隊(1 < t < M)中，放置子樹的規則為當前訪問次數最大的子樹放置到訪問總次數最小的集合Qa中。方法為判斷條件^^/^PM)是否滿足，即子樹集合…去除頂部子樹re[pe]之後的訪問次數是否仍大於F(Qa)，其中函數WQa)表示子樹集合Qa 的訪問次數，表示子樹巧[ 0]的訪問次數，rB表示Q0中子樹，ρ0表示子樹巧在… 中的位置，Kpe彡U，re[pe]是當前Q0中最晚放入的子樹。如果滿足上述條件，則進行 Qa與Qe的子樹置換操作，即將巧[pe]放入Qa中，而把子樹 放入到Q0中；如果條件不
滿足，則路由表重構模塊將子樹 放入Qa中。該子樹放置方法可以使F(Qk)(表示執行完此次子樹放置操作之後各子樹集合訪問總次數的最大值)增長最小，最終獲得訪問均衡的M個子樹集合。2. 2. 3. 4如果s小於U，即子樹序列中還有子樹未放置到任何子樹集合中，則s增加1，轉2. 2. 3. 2 ；否則執行2. 2. 4 ；2. 2. 4路由表重構模塊按照構建二叉樹的方法(見《數據結構與算法分析》中第四章，(美)維斯著，馮舜璽譯，機械工業出版社，2004年第一版)將所有劃分子樹的根節點組織成索引樹，每一項索引由該節點的前綴地址、前綴長度(見《TCP/IP協議詳解卷I》中第三章，範建華譯，機械工業出版社，2000年第一版)及子樹所屬集合進行標識，實現對子樹中某個路由節點的快速查找與訪問。繼而，轉步驟2. 1。步驟3、鄰居分配模塊採取RoimdRobin方式計算出與路由器連接的每個鄰居進行會話通信的協議執行線程，根據協議執行線程數量L將BGP鄰居劃分為L個鄰居束，並將與鄰居進行通信的埠地址(進行TCP/IP通信的地址，見《TCP/IP協議詳解卷I》中第三章， 範建華譯，機械工業出版社，2000年第一版)傳遞給對應的協議執行線程。具體方法為如果路由表重構定時器超時，轉2. 2 ；如果路由表重構定時器未超時，當有新的鄰居會話請求到達，鄰居分配模塊根據鄰居的前綴地址為該鄰居會話分配協議執行線程k(k為自然數且
L)，並將鄰居會話通信埠地址以消息方式發送給協議執行線程k，繼而執行步驟 4 ；如果路由表重構定時器未超時且沒有新鄰居會話請求到達，則繼續執行步驟3，等待新的鄰居會話請求到達。步驟4、鄰居會話交互。該步驟實現路由更新報文在單個協議執行線程上完整處理，可以顯著降低背景技術中方法的路由更新報文處理過程中的頻繁通信開銷，提高BGP 運行速度。具體方法為4. 1建立會話關係。協議執行線程k接收到鄰居分配模塊發送的攜帶鄰居通信埠地址的消息，鄰居管理模塊根據通信埠地址與該鄰居建立會話關係。4. 2解析報文。當鄰居管理模塊接收到路由更新報文，鄰居管理模塊解析出路由更新報文中的路由項。其中，每個路由項都由目的地址和多個路由屬性組成。4. 3鄰居管理模塊查詢路由表重構定時器超時標識，如果超時標識被置位表明路由表重構定時器已超時，轉2. 2 ；否則執行4. 4。4. 4選路模塊根據4. 2解析出的目的地址和路由屬性在全局路由信息中選擇最優路徑，方法為選路模塊首先在路由表的索引樹中查找前綴最長匹配的節點，繼而在索引到的子樹中查找與目的地址完全匹配的節點，如果查找到則計算最優路徑，計算過程採用背景技術中第5步的選路計算方法；如果未查找到匹配節點，則在該子樹中添加該目的節點及相應路由信息，並將新路由作為最優路徑。4. 5路由更新廣播。與背景技術中方法第6步類似，最主要的區別在於路由更新廣播的通信實體不同。
背景技術：
將鄰居管理功能與最優路徑選擇功能分開在不同的線程上執行，路由更新廣播操作就是各選路線程將選擇的最優路徑發送給鄰居管理單元所在的鄰居管理和前處理前綴分類線程，因此，路由更新廣播的通信實體為鄰居管理和前處理前綴分類線程與選路線程。而本發明中將鄰居管理功能與最優路徑選擇功能集中在一個協議執行線程上完成，路由更新廣播的通信實體為不同的協議執行線程。具體方法是路由廣播模塊將選路模塊選擇的最優路徑發送給除該路由廣播模塊所屬協議執行線程之外的所有協議執行線程，並接收來自其他協議執行線程選擇的最優路徑。當路由更新廣播操作完成，執行4. 6。4.6最優路徑播報。鄰居管理模塊根據鄰居束b(b為自然數且KbSL)中每個鄰居的出口過濾策略(見《BGP設計與實現》中第四章，黃博、葛建立譯，人民郵電出版社， 2008年第二版)對步驟4. 5獲得的全部最優路徑進行過濾，將已過濾的最優路徑封裝成路由更新報文，向各鄰居發送。4. 7如果BGP進程結束，則轉步驟5 ；否則，當有新的路由更新報文到達，轉4. 2 ；步驟5、主控線程與所有協議執行線程運行終止。採用本發明可以達到以下技術效果1、通過將BGP軟體設計成多線程結構，使執行路由更新報文處理任務的多個線程並行運行在多核處理器的多個核上，降低了背景技術中方法的路由更新報文處理時頻繁的線程間通信開銷，進一步提高了 BGP運行速度；2、本發明第2. 2步動態重構路由表，可以反映實際路由表訪問行為，降低線程間同時訪問路由表時引發的競爭，從而提高BGP多線程並行執行效率。
圖1為背景技術一種BGP多線程結構來實現並行處理路由更新報文的方法的流程
圖2為本發明總體流程圖3為傳統路由表結構圖4為本發明可重構路由表構造過程示例圖。具體實施方案
圖1是背景技術一種BGP多線程結構來實現並行處理路由更新報文的方法的流程圖，主要包括以下步驟
1、類別項預計算。
2、構建BGP多線程結構。
3、解析報文。
4、查找類別項。
5、選路計算。
6、路由更新播報。
7、當有新的路由更新報文達到，轉步驟3。
圖2是本發明的總體流程圖，主要包括以下步驟
1、構建BGP多線程結構。
2、設置路由表重構定時器。
2. 1啟動路由表重構定時器。
2. 2重構路由表。
2. 2. 1後序遍歷路由表，統計路由表訪問總次數。
2. 2. 2層次遍歷路由表，劃分路由表子樹。
2. 2. 2. 1如果當前路由節點的左右子節點與左右子樹訪問次數大於TXU—1，將左
8右子樹邏輯劃分為獨立子樹，然後轉2. 2. 2. 2 ；否則直接轉2. 2. 2. 2。2. 2. 2. 2如果當前分層還有其他節點未遍歷，則由左至右遍歷下一個節點，轉 2. 2. 2. 1 ；否則，轉 2. 2. 2. 3。2. 2. 2. 3如果已遍歷所有分層及節點，則轉2. 2. 3 ；否則，跳至下一分層繼續遍歷， 車專 2 ■ 2 ■ 2 ■ 1 ο2. 2. 3將劃分子樹歸類為子樹集合。2. 2. 3. 1劃分子樹按訪問次數降序排列。2. 2. 3. 2計算訪問次數最大與最小集合。2. 2. 3. 3 子樹放置。2. 2. 3. 4如果放置完所有子樹，轉2. 2. 4 ；否則，轉2. 2. 3. 2。2. 2. 4組織索引樹，轉2. 1。3、鄰居劃分與分配。如果路由表重構定時器超時，轉2. 2;如果路由表重構定時器未超時，當有新的鄰居請求到達，轉4;如果路由表重構定時器未超時且沒有新鄰居請求到達，轉3。4、鄰居會話交互。4.1建立鄰居會話關係。4. 2解析報文。4. 3查詢路由表重構定時器超時標識。如果超時，則轉2. 2 ；否則，轉4. 4。4. 4選擇最優路徑。4. 5路由更新廣播。4. 6最優路徑播報。4. 7如果BGP結束，轉5 ；否則，當有新的更新報文達到，轉4. 2。5、所有線程運行終止。圖3為傳統路由表結構圖。傳統路由表採用二叉樹結構組織，每個節點由前綴地址和前綴長度兩個屬性進行標識。每個節點都指向一個路由信息表，路由信息表由到達該節點的所有路由項及每個路由項所包含的路由屬性組成。圖4為本發明第2. 2步中可重構路由表構造過程示例圖。主要過程為[初始時].初始構建路由表時按照傳統路由表二叉樹結構構造，統計路由表中每個節點被訪問的次數，如圖4(a)所示中每個節點旁標註的數字。[2.2.1].當路由表重構定時器超時後，開始重構路由表。在圖4(b)中，路由表重構模塊後序遍歷路由表，統計得到路由表訪問總次數T為1696，並統計了每個節點的左右子樹的訪問次數，圖中每個節點旁標註了由(節點訪問次數，左子樹訪問次數，右子樹訪問次數)構成的三元組。[2.2.2].層次遍歷路由表，劃分路由表子樹，如圖4(c)所示。設定M為8、U為32， 如果節點的左右子節點與左右子樹訪問次數都大於53 (ΤΧΓ1)，則將左右子樹從路由表中進行剪枝，在維持傳統路由表邏輯關係不變的前提下劃分出18個子樹。子樹由傳統路由表中一部分節點組成，也是一棵二叉樹，不同子樹內的節點互不相同，且所有子樹包含的節點為傳統路由表節點總和。圖中表格裡記錄了每個子樹的節點組成，並通過累加子樹中各節點訪問次數計算出每個子樹訪問次數。
[2.2.3].將劃分好的子樹歸類為M個子樹集合，過程如圖4(d)所示。首先，將18 個子樹按照訪問次數降序排列，得到子樹序列al，a2，…，al8，然後依次將al_al8放入8個子樹集合中。在子樹放置初始時，各子樹集合為空，則將子樹al-a8依次放入集合1到集合 8中，子樹集合訪問次數也相應發生變化，例如集合1在放入al後訪問次數由0變成131。 繼而，子樹a9_al8按照子樹放置規則依次放入子樹集合中，並更新子樹集合訪問次數。以放置子樹al7為例，在放置前訪問次數最大、最小集合分別為集合5與集合1，由於集合5在去除最晚放入的子樹(al2)後的訪問次數(121)小於集合1的訪問次數(189)，則將al7放入集合1中。最終得到各子樹集合的子樹組成。[2.2.4].組織索引樹，如圖4(e)所示。將劃分子樹的根節點按照二叉樹構造方式組織成索引樹，索引樹中每個節點由前綴地址、前綴長度及所屬集合三個關鍵屬性進行標識；同時索引樹中每個節點都指向一個子樹，以節點2為例，它指向子樹a2，a2由節點2、5、 6組成，與傳統路由表結構相同，它們分別指向一個路由信息表，記錄到達該節點的所有路由項及每個路由項所包含的路由屬性。
權利要求
1.一種多線程邊界網關協議並行處理方法，其特徵在於包括以下步驟步驟1、構建BGP多線程結構，BGP多線程結構採用主從處理方式，由一個主控線程和L 個協議執行線程組成，L為可變自然數，L根據公式L = CXD-I來確定，其中C為多核處理器的核數，D為多核處理器每個核可支持的最大線程數；主控線程是執行BGP鄰居分配、全局路由信息動態組織的軟體線程，由鄰居分配模塊與路由表重構模塊組成，鄰居分配模塊是用於計算鄰居與協議執行線程對應關係的軟體代碼，路由表重構模塊是用於動態更新全局路由表結構的軟體代碼；協議執行線程是完成與鄰居束的具體會話關係的軟體線程，由鄰居管理模塊、選路模塊與路由廣播模塊組成，鄰居管理模塊是用於完成與鄰居束中各鄰居的會話建立與通信的軟體代碼，選路模塊是執行最優路徑選擇的軟體代碼，路由廣播模塊是用於向其他協議執行線程發布本地最優路徑的軟體代碼；步驟2、路由表重構模塊設置路由表重構定時器，對全局路由信息進行周期性動態重構，方法是·2.1啟動路由表重構定時器，若路由表重構定時器未超時，由鄰居分配模塊執行步驟 3 ；若路由表重構定時器超時，路由表重構模塊執行2. 2 ；·2. 2重構路由表結構當路由表重構定時器超時時，首先設置超時標識，然後路由表重構模塊將傳統路由表邏輯劃分成若干個子樹集合，並構建快速索引樹，具體方法是·2. 2. 1路由表重構模塊對路由表進行後序遍歷，統計路由表在定時器計時周期內各路由節點被訪問總次數T，T為自然數；路由表以二叉樹結構組織，每訪問一個路由節點時累計路由表重構定時器計時期間該節點及它的左右子樹被訪問的次數，左右子樹是以左右子節點為根的二叉樹；·2. 2. 2對路由表執行層次遍歷，將路由表邏輯地劃分為若干個路由表子樹，且子樹數量上限為U，U為自然數，U根據公式U= μ XM確定，其中μ為子樹數量參考係數，為大於等於4且小於等於64的偶數，M為劃分子樹集合數量，M為可變自然數，M根據公式M = 2 X L 來確定，具體方法是·2. 2. 2. 1如果當前路由節點的左右子節點與左右子樹訪問次數均大於TXU—1，則路由表重構模塊對該節點的左右子樹執行剪枝操作，將左右子樹邏輯地劃分為獨立的子樹，轉 2. 2. 2. 2 ；否則，直接執行2. 2. 2. 2 ；·2. 2. 2. 2如果當前路由節點所在的路由表二叉樹分層中還有其他未遍歷的節點，則路由表重構模塊繼續按由左至右的順序遍歷下一個節點，轉2. 2. 2. 1 ；否則執行2. 2. 2. 3 ；·2. 2. 2. 3如果已遍歷路由表二叉樹中所有分層及節點，則執行2. 2. 3 ；否則，路由表重構模塊跳至路由表二叉樹的下一個分層中繼續遍歷，轉2. 2.2.1；·2. 2. 3路由表重構模塊將子樹歸類為M個子樹集合Q1,......,Qm,方法是·2. 2. 3. 1路由表重構模塊將劃分後子樹按照訪問次數進行降序排列後得到子樹序列，3-2， · · ·，；2. 2. 3. 2累加子樹集合&中所有子樹的訪問次數，1 ^ i ^ M,計算出&訪問總次數， 再將所有子樹集合按照子樹集合訪問總次數降序排列，獲得訪問總次數最小和最大的子樹集合Qa和Qe，Qa表示訪問次數最小的子樹集合，Qe表示訪問次數最大的子樹集合，α為子樹集合的下標，a ^M, β為子樹集合的下標，1 ^ β ^M5·2. 2. 3. 3從子樹序列B1, a2, ...，au中取出頭子樹as, 1 ^ s ^ U，s初始值為1，放入子樹集合Qt中，1 < t <M，方法為判斷條件M^Hj^y^^)是否滿足，即子樹集合…去除頂部子樹巧[ 0]之後的訪問次數是否仍大於F(Qa),如果滿足，則進行Qa與…的子樹置換操作，即將re[pe]放入Qa中，而把子樹 放入到Q0中；如果不滿足，則路由表重構模塊將子樹 放入Qa中，其中函數WQa)表示子樹集合Qa的訪問次數，表示子樹巧[ 0] 的訪問次數，r0表示Q0中子樹，ρ0表示子樹巧在…中的位置，1 Sp0 ^U, Γ0[ρ0]是當前Qe中最晚放入的子樹；.2. 2. 3. 4如果s小於U，則s增加1，轉2. 2. 3. 2 ；否則執行2. 2. 4 ； 2. 2. 4路由表重構模塊按照構建二叉樹的方法將所有劃分子樹的根節點組織成索引樹，每一項索引由該節點的前綴地址、前綴長度及子樹所屬集合進行標識；繼而，轉步驟 2. 1 ；步驟3、鄰居分配模塊採取RoimdRobin方式計算出與路由器連接的每個鄰居進行會話通信的協議執行線程，根據協議執行線程數量L將BGP鄰居劃分為L個鄰居束，並將與鄰居進行通信的埠地址傳遞給對應的協議執行線程，具體方法為如果路由表重構定時器超時，轉2. 2 ；如果路由表重構定時器未超時，當有新的鄰居會話請求到達，鄰居分配模塊根據鄰居的前綴地址為該鄰居會話分配協議執行線程k，並將鄰居會話通信埠地址以消息方式發送給協議執行線程k，繼而執行步驟4，k為自然數且KkSL ；如果路由表重構定時器未超時且沒有新鄰居會話請求到達，則繼續執行步驟3，等待新的鄰居會話請求到達； 步驟4、鄰居會話交互，方法為.4. 1建立會話關係協議執行線程k接收到鄰居分配模塊發送的攜帶鄰居通信埠地址的消息，鄰居管理模塊根據通信埠地址與該鄰居建立會話關係；.4. 2解析報文當鄰居管理模塊接收到路由更新報文，鄰居管理模塊解析出路由更新報文中的路由項，每個路由項都由目的地址和多個路由屬性組成；.4. 3鄰居管理模塊查詢路由表重構定時器超時標識，如果超時標識被置位表明路由表重構定時器已超時，轉2. 2 ；否則執行4. 4 ；.4. 4選路模塊根據4. 2解析出的目的地址和路由屬性在全局路由信息中選擇最優路徑，方法為選路模塊首先在路由表的索引樹中查找前綴最長匹配的節點，繼而在索引到的子樹中查找與目的地址完全匹配的節點，如果查找到則採用選路計算方法計算最優路徑； 如果未查找到匹配節點，則在該子樹中添加該目的節點及相應路由信息，並將新路由作為最優路徑；.4. 5路由更新廣播路由廣播模塊將選路模塊選擇的最優路徑發送給除該路由廣播模塊所屬協議執行線程之外的所有協議執行線程，並接收來自其他協議執行線程選擇的最優路徑，當路由更新廣播操作完成，執行4. 6 ；.4. 6最優路徑播報鄰居管理模塊根據鄰居束b中每個鄰居的出口過濾策略對步驟4. 5 獲得的全部最優路徑進行過濾，將已過濾的最優路徑封裝成路由更新報文，向各鄰居發送， b為自然數且1彡b彡L;.4. 7如果BGP進程結束，則轉步驟5 ；否則，當有新的路由更新報文到達，轉4. 2 ； 步驟5、主控線程與所有協議執行線程運行終止。
2.如權利要求1所述的多線程邊界網關協議並行處理方法，其特徵在於所述路由表重構定時器為一個計時程序，計時時間設定為路由通告最大時間間隔。
全文摘要
本發明公開了一種多線程邊界網關協議並行處理方法，目的是加快BGP處理路由更新報文速度。技術方案是構建由一個主控線程和L個協議執行線程組成的BGP多線程結構，主控線程由鄰居分配模塊與路由表重構模塊組成，協議執行線程由鄰居管理模塊、選路模塊與路由廣播模塊組成；路由表重構模塊對全局路由信息進行動態重構；鄰居分配模塊計算出每個鄰居對應的協議執行線程，將BGP鄰居劃分為L個鄰居束，並將與鄰居進行通信的埠地址傳遞給對應的協議執行線程；由鄰居管理模塊、選路模塊與路由廣播模塊相互配合進行鄰居會話交互。採用本發明能降低線程間通信開銷，降低線程間同時訪問路由表時引發的競爭，提高BGP運行速度。
文檔編號H04L12/56GK102394809SQ201110310369
公開日2012年3月28日 申請日期2011年10月13日 優先權日2011年10月13日
發明者任珊珊, 王志英, 肖儂, 賴明澈, 陸洪毅, 馬勝, 高蕾 申請人:中國人民解放軍國防科學技術大學