基於內容與關係分離的大數據集任務的節點遷移方法
2023-09-19 01:52:00 1
專利名稱：基於內容與關係分離的大數據集任務的節點遷移方法
技術領域：
基於內容與關係分離的大數據集任務的節點遷移方法屬於網際網路IP路由器數據以及內存管理算法研究領域。
背景技術：
在現代的計算機網絡系統中，路由器是最核心的連接設備。網際網路的飛速發展帶來了路由器體系結構的革新。下一代網際網路對下一代IP路由器體系結構提出了新的需求。對單節點進行優化，提高其處理能力已經不再是系統改進的最根本方式，因為這種方式受限於物理器件的發展速度影響。基於單節點的傳統IP路由器體系結構已經無法適應網絡的飛速發展。可擴展的體系結構是下一代IP路由器的主要發展方向。
在可擴展路由器軟體體系結構中，任務的遷移是基本的結構支持。可擴展軟體體系結構的計算模型只解決了系統的靜態抽象問題，它回答了系統該如何組織和分配任務的基本問題。但是，對於一個真正可擴展的系統來說，系統結構的動態擴充是至關重要的。由於查找效率的原因，路由表的存儲並不是以無關聯的「表」型結構進行存儲的，通常是基於Trie樹結構或其他有組織的結構進行存儲。重建不止意味著數據的拷貝，這些關聯關係也要得到恢復，而對於大數據集來說，在短時間內恢復數據集的關係是比較困難的。概括的說，數據關係完全重建的複雜度在大規模數據集的時間開銷過大以及數據關聯關係的不可複製性制約了這些任務在路由器控制平面節點之間的遷移。因此，要達到真正的可擴展軟體體系結構，就一定要解決大數據集任務的遷移問題。
發明內容
本發明的目的在於提供一種基於內容與關係分離的大數據集任務的節點遷移方法。
本發明的特徵在於，它依次含有以下步驟步驟(1.)建立內容數據存儲池，記錄各內存池的首地址，並存儲包含目標子網、下一跳、出接口以及優先級在內的路由器內部的路由信息；步驟(2.)建立結構數據內存池，記錄該內存池的首地址並存儲路由器內部路由信息之間的關聯，其中包含指向內容數據內存池的指針以及兩個用於快速檢索的指針；步驟(3.)初始化內容數據內存池和結構數據內存池；步驟(4.)建立所述內容數據內存池和結構數據內存池之間在存儲地址上的一一對應的映射關係；同時，建立各內存地址和空閒內存鍊表，該鍊表是一個用於存儲空閒內存地址的指針鍊表，以便對由於路由條目的撤消而形成的內存地址空洞進行管理；其中，所述映射關係具體表現在內容數據內存池與結構數據內存池在內存中首地址之差與所述內存池之間對應條目在內存地址上的偏移量是相同的；步驟(5.)在執行完路由條目的刪除操作後，由步驟(4.)中的空閒內存鍊表對由刪除帶來的內存地址空洞的詳細信息做記錄，該詳細信息包括空閒內存鍊表的首地址指針以及下一個空閒空間內存區域的地址；步驟(6)在執行路由條目增加操作時，首先判斷所述空閒內存鍊表的首地址是否為空，若該地址非空，則把需要添加的新路由條目優先存儲在由空閒內存鍊表維護的地址空洞中，並修改空閒內存鍊表的首地址指針，若該地址為空，則說明存儲路由條目的內存地址中不存在地址空洞，需要向系統申請新的內存地址，存放新增的路由條目；步驟(7.)當需要把路由表移動到另一塊獨立的內存區域時，依次按以下步驟進行步驟(7.1)根據需要移動的內容數據內存池的大小，在新的內存區域中申請相應的內存存儲空間，並記錄該空間的首地址；步驟(7.2)根據需要移動的結構數據內存池的大小，在新的內存區域中申請相應的存儲空間，並記錄該存儲空間的首地址；步驟(7.3)建立步驟(7.1)、步驟(7.2)中所述的新內存池對之間的映射關係，記錄新的內容數據內存池與結構數據內存池首地址間的偏移量；步驟(7.4)掃描步驟(7.2)所述的新的結構數據內存池，並根據步驟(7.3)所述的新偏移量修改新的結構數據內存池中對應的指針地址；步驟(7.5)在新的內存區域中建立空閒內存鍊表，對可能存在的空閒內存地址進行管理。
按照上述實施方式我們對該協議在路由表規模從100K到1M條的情況下對上述方法進行了仿真，並將上述方法與傳統的完全重建路由表的方式進行了比較。其中圖6是使用該方法重建路由表所花費時間的模擬仿真結果，可以發現該過程符合線性計算複雜度。圖7是採用真實路由表進行實驗情況下，上述方法與傳統的完全重建方式在路由表移動情況下花費時間的對比，從圖中可以發現基於內容與關係分離的大數據集任務的節點遷移方法與傳統方式相比在路由表移動時間上有很大的優勢，並且隨路由條目的增加其增長率也遠遠小於傳統的完全重建方式。圖8顯示了該方式與傳統方式的加速比，圖中離散的圓圈標記代表相應路由條數條件下，測得的傳統方式與基於內容與關係分離的大數據集任務的節點遷移方法的重建時間之比。加速比分布在23.47到58.90之間，雖然這些離散的加速比數據沒有很平滑的數據趨勢關係。但是，仍然能夠大體看出隨路由條數的增加，加速比有增加的趨勢。
圖1.路由表結構描述圖；圖2.內存池以及映射關係3.空閒內存鍊表結構圖；
圖4.路由表複製示意圖；圖5.本發明的總體處理流程圖；圖6.仿真數據曲線圖；圖7.路由表重建時間實驗曲線圖；圖8.加速比曲線圖；圖9.本發明的應用示例圖。
具體實施例方式
傳統的大數據集任務節點遷移與重建方式的效率底下，嚴重影響了擴展軟體體系結構的發展。設計一種更加高效率的移動以及存儲方法並滿足可擴展路由器中路由計算和路由的管理這兩個核心功能，是本發明的主要貢獻。
在本發明的描述中，基於內容與結構分離的思想，路由表通過內容數據內存池、結構數據內存池以及該兩個內存池對的映射關係進行描述，其中內容數據內存池中存儲了路由條目的基本信息，其中包括目標子網、下一跳，出接口以及優先級。結構數據內存池則用來存儲路由條目之間的基本關係，為了方便查找，由於路由表一般使用Trie樹的結構進行存儲，結構數據內存池就是針對Trie樹的一種特殊描述。其中的內存池對的映射關係可以表示為y＝f(d(x))＝x，其中x為結構數據的邏輯地址，y為內容數據的邏輯地址。
路由表結構描述圖見圖1內存池以及映射關係描述見圖2在維護內容數據內存池、結構數據內存池的過程中，如果出現路由條目的釋放，需要及時的記錄該內存塊的地址並將該地址記錄在空閒內存鍊表中，當該鍊表的首地址指針不為空的時候，為了節約內存空間，需要將新加入的路由條目優先的存儲在空閒內存鍊表所記錄的地址空洞中。
空閒內存鍊表結構見圖3當需要進行路由表遷移的時候，首先在遷移的目的內存區域中按照源內容數據內存池以及結構數據內存池大小重建相應結構，再將對應的數據內容以及關係描述進行複製。複製完畢以後，記錄新的內容數據內存池以及結構數據內存池的首地址，並建立新的映射關係，最後，通過對結構數據內存池進行掃描，根據新的首地址映射關係修改結構數據內存池中的指針地址完成路由表的遷移與重建。
路由表在內存塊中的複製過程見圖4本發明的總體處理流程圖見圖5可擴展路由器的框架結構圖即本發明應用示例圖見圖9
本發明可以通過對路由信息的內容與相互關係的分離來減少大規模路由表重建過程中的計算記憶處理開銷，並且，通過空閒內存鍊表對內存空洞的管理優先的使用由內存釋放帶來的內存空洞從而減少了內存空間上的浪費，並且，通過實驗數據表明，該方法與傳統的完全重建方法相比具有計算複雜度底，穩定性好等特點。作為可擴展路由器軟體體系結構中的重要組成部分解決了對大數據集任務遷移的支持問題。
權利要求
1.基於內容與關係分離的大數據集任務的遷移方法，其特徵在於該方法是通過在網際網路IP路由器或終端主機的軟體體系結構中增加一個動態任務遷移模塊來實現的，依次含有以下步驟步驟(1.)建立內容數據存儲池，記錄各內存池的首地址，並存儲包含目標子網、下一跳、出接口以及優先級在內的路由器內部的路由信息；步驟(2.)建立結構數據內存池，記錄該內存池的首地址並存儲路由器內部路由信息之間的關聯，其中包含指向內容數據內存池的指針以及兩個用於快速檢索的指針；步驟(3.)初始化內容數據內存池和結構數據內存池；步驟(4.)建立所述內容數據內存池和結構數據內存池之間在存儲地址上的一一對應的映射關係；同時，建立各內存地址和空閒內存鍊表，該鍊表是一個用於存儲空閒內存地址的指針鍊表，以便對由於路由條目的撤消而形成的內存地址空洞進行管理；其中，所述映射關係具體表現在內容數據內存池與結構數據內存池在內存中首地址之差與所述內存池之間對應條目在內存地址上的偏移量是相同的；步驟(5.)在執行完路由條目的刪除操作後，由步驟(4.)中的空閒內存鍊表對由刪除帶來的內存地址空洞的詳細信息做記錄，該詳細信息包括空閒內存鍊表的首地址指針以及下一個空閒空間內存區域的地址；步驟(6)在執行路由條目增加操作時，首先判斷所述空閒內存鍊表的首地址是否為空，若該地址非空，則把需要添加的新路由條目優先存儲在由空閒內存鍊表維護的地址空洞中，並修改空閒內存鍊表的首地址指針，若該地址為空，則說明存儲路由條目的內存地址中不存在地址空洞，需要向系統申請新的內存地址，存放新增的路由條目；步驟(7.)當需要把路由表移動到另一塊獨立的內存區域時，依次按以下步驟進行步驟(7.1)根據需要移動的內容數據內存池的大小，在新的內存區域中申請相應的內存存儲空間，並記錄該空間的首地址；步驟(7.2)根據需要移動的結構數據內存池的大小，在新的內存區域中申請相應的存儲空間，並記錄該存儲空間的首地址；步驟(7.3)建立步驟(7.1)、步驟(7.2)中所述的新內存池對之間的映射關係，記錄新的內容數據內存池與結構數據內存池首地址間的偏移量；步驟(7.4)掃描步驟(7.2)所述的新的結構數據內存池，並根據步驟(7.3)所述的新偏移量修改新的結構數據內存池中對應的指針地址；步驟(7.5)在新的內存區域中建立空閒內存鍊表，對可能存在的空閒內存地址進行管理。
全文摘要
本發明屬於網際網路IP路由器數據以及內存管理方法技術領域，其具體特徵在於依次含有以下步驟依次建立包含路由信息的內容數據內存池和包含路由條目之間關係的結構數據內存池；依據上述兩個內存地址池首地址之差得出並建立該內存池對在存儲地址上的映射關係；分別建立上述內存池各自的空閒內存鍊表；當要把路由表移到一個獨立的內存區域時要分別根據各自內存池的大小在新內存區域內分別建立內容數據內存池和結構數據內存池，並重新建立新內存空間內的映射關係與空閒內存鍊表，用來管理在路由維護中可能出現的地址空洞。本發明實現了IP路由器軟體體系結構中大數據集的動態維護。
文檔編號H04L29/02GK1897570SQ20061001226
公開日2007年1月17日 申請日期2006年6月15日 優先權日2006年6月15日
發明者徐恪, 吳鯤, 王海洋 申請人:清華大學