一種基於動態聚合樹模型的路由方法

2023-10-04 21:21:44 5

專利名稱：一種基於動態聚合樹模型的路由方法
技術領域：
本發明屬於網絡通信技術領域，涉及一種點對點的動態網絡通信技術，特別涉及基於網絡動態拓撲結構及鏈路權值隨時間變化的分布式路由方法。
背景技術：
隨著Internet規模的不斷擴大，多樣化的組網設備層出不窮。這些設備構成了通信網絡中的一個個自治系統，為了使這些自治系統內部和自治系統之間形成高效低成本的通信，就需要進行數據路由。系統中所有設備，共同遵守同一套的路由規則，使用相同的路由信息表述和存儲方法。
在現有的技術中，路由協議是解決數據路由的主要技術手段。路由協議基於抽象的網絡模型來計算網絡中節點對之間的最優路徑。按照最優路徑的計算方式，路由協議可以分為兩大類鏈路狀態路由和距離矢量路由。在鏈路狀態協議的運行過程中，網絡中的每臺負責交換路由信息的設備(路由器、交換機等)都維護著整個網絡的路由結構信息，並根據這些信息使用相應的路由算法計算最優路徑並生成路由表。距離矢量路由協議在使用過程中則不需要維護整個網絡路由信息，分布式路由的信息僅在鄰居節點之間傳遞，並在每個節點的使用分布式路由算法獲得路由表。目前在Internet上使用最普遍的兩種路由協議是RIP(Routing Information Protocol，路由信息協議)和OSPF(Open Shortest Path First，開放式最短路徑優先協議)。其中，RIP協議是距離矢量路由協議，使用分布式Ford-Bellman算法。它具有簡單、可擴展性高的特點，但收斂速度較慢。OSPF協議是典型的鏈路狀態路由協議，使用Dijkstra算法。它有效的提高了路由信息匯聚的速度和準確性，因而減小了網絡阻塞的機率，提高了網絡的整體效率。但OSPF協議過於龐大，對路由設備有相當高的要求。
目前，隨著電信業務的引入，IP網的服務質量(IP QoS)成為下一代Internet的重要研究課題。QoS路由的目標也是一個通過當前路由器路由表尋找從源節點到目的節點的最優路徑的問題。為了解決QoS路由算法隨網絡規模的增大所需的執行時間和存儲需求提高的問題，拓撲結構分層聚合的思想被廣泛的應用在大規模的網絡中。拓撲聚合的過程是將網絡中每個域會聚成具有該域信息的一個簡單的拓撲。這一思想雖然大大地簡化了路由表的大小，但是網絡的在動態改變後產生了路由信息的不精確性。而在這一思想上延伸的各種動態最短路徑樹問題得到了很高的成效。但是現存的最短路徑樹路由模型研究在網絡動態改變後，仍然需要冗餘的計算和具有不準確的信息，因而基於這些協議的網絡路由過程必然不能獲得符合實際的精確優化結果和很高的路由效率。因此建立符合實際的高精確性高路由效率並切合實際流量情況的路由方案、研究適合於大規模網絡動態改變的路由協議成為一個迫切需要解決的問題。

發明內容
本發明的目的是提供一種能夠有效為目前的網際網路骨幹網自治域提供準確切合實際流量情況的高精確性高路由效率，並且可以動態自製更新的路由方法。
本發明的技術解決方案是，在至少存在兩個具有路由承載功能的通信設備組成的數據通信網絡中，分別使用如下所述的本發明運行方案。數據通信網的拓撲可以是分布式網絡或環形網絡。網絡傳輸媒介可以使用包括光纖、數字微波、普通同軸電纜、雙絞線等多種。通信網絡的物理層和數據鏈路層可以使用多種接口，以支持用戶的不同接入方式。本發明的技術方案工作在網絡層。由於本發明所使用的模型及路由算法對網內設備的處理器、內存資源的佔用比較小，低檔路由器甚至軟路由設備均可以使用。
本發明是一種適合於網際網路骨幹網自治域使用的路由方法。該方法使用現有的硬體路由設備為基礎，適用於路由器和具有軟路由功能的設備。
本發明的技術方案包括以下步驟1.路由設備根據預留磁碟空間記錄歷史流量數據和操作記錄，以文件形式存儲在外部存儲器上，如硬碟等。
2.路由設備通過外部接口接受用戶設定，確定需要路由的起始時間以及路由量度變化的單位時段並由路由協議程序統一管理。
3.由路由設備運行路由協議程序，根據本發明設計的動態聚合樹網絡模型，在路由設備的內部高速存儲器內存中構建新型的路由表。該路由表由兩個子表組成，分別存儲有本路由節點到其它路由節點的路徑量度(Metric)和下一條信息。
對於每臺路由設備，其具體需要維護的信息如下數組D，每個元素Dj是從當前節點到目的地址j最短路徑的權值。
數組P，每個元素Pj是從當前節點到目的地址j最短路徑的下一跳。
4.由路由設備運行路由協議程序，根據本發明設計的動態聚合樹網絡模型，針對通信網內路由設備的不同類型，按照路由器間的鏈路參數將各鏈路分屬聚合樹的不同層次域中。在路由設備的內部存儲器(如內存)中構建路由子表。從聚合樹網絡模型的角度，目前的網絡通信設備可以根據其是否是關聯節點(聯繫不同層次域的節點)分為兩類，對於非關聯節點，它的路由表僅包括從該節點到該節點所在域的每個節點的信息；對於關聯節點，它的路由表不但包括從該節點到該節點所在域的每個節點的信息，還包括從該節點到其它關聯節點的信息。具體需要維護的信息如下集合V，路由信息，每個元素Vj，Dj是從當前節點到目的地址j最短路徑的最近一次計算的權值。
5.由路由設備運行路由協議程序，根據本發明設計的動態聚合樹網絡模型，在路由設備的高速存儲器，如高速緩存等，構建高速路由緩存表。對於每臺路由設備，必須在高速存儲器，如內存，flashmemory等，上存儲該表，高速存儲器為內存、flash memory等。其具體需要維護的信息如下表T，二維緩存表，每個元素Tkj是從當前節點路經鄰居節點k到達目的地址j最短路徑的權值。
6.路由設備從外部接口接受用戶輸入，確定每條物理網絡接口的物理標識和接口標識，用以唯一確定數據發送單元，即鄰居，並在路由設備的內部存儲器上，運行路由協議程序構建鄰居信息列表。
7.每個數據發送單元有路由協議程序控制，根據確定的時間間隔向鄰居發送探測數據包，用以確定鏈路的的狀態。
8.當路由設備在收到由鄰居發送的新的路由表信息時，從網絡設備(如網卡)的緩衝區中取得新的路由信息，送路由設備的內部存儲器，並由處理器運行路由協議程序，根據本發明設計路由表信息更新算法來更新相應的高速緩存表項。並判斷是否需要觸發路由表計算。
9.如需要進行路由表的計算，則由路由協議程序根據本發明設計的路由表更新算法進行路由表的更新。在更新的過程中，將更新的表項記錄在路由設備的內部存儲器中，並根據本發明設計的路由狀態信息格式，組織被更新的路由表項，形成路由數據包，由路由設備的網絡接口發送給鄰居。
10.路由設備根據當前時間段的變化運行路由協議程序自動更新當前路由表。
11.路由設備每隔一段時間通過物理網絡接口向鄰居發送下N個時段的路由信息，N因具體的網絡環境而異，本發明設計預設值為4。
由上述技術路線可知，本發明是一種基於動態聚合樹網絡模型的路由方案。在保持原有路由設備硬體架構的基礎上，設計了全新的網絡路由模型及增量算法，並根據此模型形成了一套完整新穎的路由技術。
本發明所達到的有益效果和益處是，設計的動態聚合樹網絡模型能夠準確的描述網絡的實際運行狀態，有效的描述了網絡中鏈路狀態隨時間的變化。在這一模型的基礎上，本發明設計了適合該模型的分布式距離矢量類的路由協議。該協議的優勢在於高精確性高路由效率、收斂性能好、運行效率高、對路由設備的資源佔用小、可以有效的降低路由設備的成本，減少研發和維護費用，符合QoS路由的目標。本發明的路由方案適用於大規模網絡鏈路的拓撲結構隨時間變化及鏈路權值隨時間變化的情況，其中基於動態聚合樹模型所設計的路由信息更新算法，有效的解決了傳統路由方法不能解決的大規模網絡中鏈路狀態及拓撲結構隨時間變化的問題，更加合理的分配了網絡流量，提高了網絡的實際吞吐量。


下面結合附圖和具體實施方式
對本發明作進一步的說明。
圖1為本發明使用的網絡類型示意圖。
圖2為本發明路由方案基本流程圖。
圖3為本發明路由信息數據包格式圖。
圖4為本發明路由數據探測包格式圖。
圖5為本發明動態聚合樹生成流程圖。
圖6為本發明路由信息更新算法流程圖。
具體實施例方式
本發明所述的路由方案，以現有的路由設備為應用對象，適合於目前的網際網路骨幹網自治域使用。該方案主要由動態聚合樹的網絡模型和基於該模型的增量算法以及一整套路由技術組成。這套路由技術主要由一種路由狀態預測方法和一個使用動態聚合樹模型的路由協議組成。
本發明所述的動態聚合樹網絡模型具體描述如下任何一個網絡均可劃分成若干個稱之為域的不規則區域，這個域是原網絡的子網絡並構成聚合樹的一個節點。聚合樹是n(n＞0)個域的有限集合，在非空的聚合樹中(1)有且僅有一個特定的域為聚合樹的根；(2)當n＞1時，其餘域可分為m(m＞0)個有限集合T1，T2，…，Tm，並且i≠k，1≤i，k≤m，Ti∩Tk∈V，其中每一個集合本身又是一棵聚合樹，並且稱為根的子樹。原網絡中的鏈路根據其參數的取值賦予不同級別，而聚合樹的層次正是通過這一級別來劃分的。各域通過關聯節點聯繫。當網絡的鏈路狀態發生改變時，相關的路由器調用增量算法更新網絡的狀態及受到影響的路由器的路由表。當網絡中某個路由器收到的數據包表明它所連接的鏈路參數發生改變時，觸發該算法識別受到影響的所有路由器及鏈路，然後對這些受到影響的路由器的路有表中各信息進行更新。
本發明的路由協議執行過程具體步驟描述如下1.路由設備初始化路由表。路由表分為三個子表，分別是量度路由子表D，一個一維數組，由目標地址索引，每個元素Dj是從當前節點到目的地址j最短路徑的權值。
下一跳路由子表P，一個一維數組，由目標地址索引，每個元素Pj是從當前節點到目的地址j最短路徑的下一跳。
發送路由子表V，一個路由信息的集合，每個元素Vj，Dj是從當前節點到目的地址j最短路徑的最近一次計算的權值。
2.設置本路由設備各個物理網絡接口的物理標識和接口標識，並以此唯一確定鄰居路由設備，同時插入鄰居信息隊列。
3.根據初始化的路由表，生成高速路由二維緩存表T。該表由鄰居節點、目標地址索引表項，每個元素Tkj是從當前節點路經鄰居節點k到達目的地址j最短路徑的權值。
4.將路由表表項內容打包為路由信息數據包，包中包含的欄位有協議標號、包大小(byte)、路由表更新項數、路由表項更新內容。其中，路由表項更新內容為目的地、路徑量度組成的一個二元組(j，Dj)。具體數據包格式見附圖3。
5.啟動時間路由信息時段定時器timer1，有效時間根據具體網絡環境確定，本發明建議預設值為40秒。
6.向各個鄰居發送路由探測數據包。路由探測數據包分為主動探測和答覆探測兩類，由包中的類型欄位標識，具體格式見附圖4。
7.啟動鄰居探測發送定時器timer2，有效時間根據具體網絡環境確定，本發明建議預設值為10秒。
8.路由設備接到路由數據包後，首先執行網絡分割算法，形成聚合樹模型。運行完這一算法，每個節點都掌握了其子域節點的信息。節點地址由關聯節點從根域開始遞歸分配。具體的流程見附圖59.然後執行聚合樹路由算法，分三個過程9. 1初始化。每個路由器n在接到鄰居節點i的路由數據包後，進行分類處理如果i為節點地址信息，那麼初始化n的節點類路由表信息；如果i為域地址信息，那麼初始化n的域類路由表信息。然後形成發送路由信息發送給鄰居節點。
9. 2緩存表和路由表更新算法，當緩存表中的路由或是權值有改變，形成發送路由信息發送給鄰居節點更新路由表信息。路由設備將接到的路由數據包進行分類處理如果是路由探測數據包轉步驟9.2.1。
如果是路由信息數據包轉步驟9.2.2。
9. 2.1如果是路由探測數據包，判斷該包的類型並執行相應動作如果是主動探測包，則向包的發送接口回復答覆探測包，內容中包括本路由單元的物理和接口標識。
如果是答覆探測包，取出其中的鄰居信息，檢測鄰居信息隊列相應內容，判斷是否需要更新。
9. 2.2如果是路由信息包，進行高速路由緩存表的更新，具體分以下幾步(1)按順序取下一個路由信息包中的更新路由表項。對於更新路由表項中V的每一個元素j，cost，如果高速路由緩存表中不存在Tij，那麼將Vij賦值為j，cost+Di加入集合V中。
(2)如果Tij＞cost+Di，那麼將Tij更新為cost+Di，並設置標號flag為true(3)如果flag為true，那麼對每一個目標地址j作如下操作如果Dj≠≠minTij並且Pj≠≠i，那麼Dj←Tij，Pj←i，V←j，Dj；(4)結束9. 3路由信息的會聚，各路由器將收到的路由信息收集，進行路由表的重新計算。
(1)當收到的路由信息為域類地址信息如果鄰居節點是當前節點的子域，那麼除了這一子域的信息外，其餘信息都發送。其它情況下，發送所有信息。
(2)當收到的路由信息為節點類地址信息發送所有信息給同域、父域的鄰居節點。對於鄰居節點在子域的情況，除了子域信息外的其它信息都發送。
具體流程見附圖610.當某個路由器收到的數據包表明與它相連的鏈路狀態發生改變時，則觸發增量算法更新網絡的狀態及受到影響的路由器的路由表。識別受到影響的所有路由器及鏈路，然後對這些受到影響的路由器的路有表中各信息進行更新。
11.如果timer1到時，則向鄰居廣播下N時段的本地路由表。N的值根據具體網絡環境確定，本發明建議預設值為4。
12.如果timer2到時，向每個物理接口發送路由探測數據包。同時啟動探測包計時timer3，如果在timer3到時後，還沒有收到回復類型的路由探測數據包，確定該路徑為斷路，更新該鄰居的路由緩存表項為無窮大，轉步驟6。
權利要求
1.一種基於動態聚合樹模型的路由方法，其特徵在於，在由硬路由設備構成的網絡中，路由步驟如下1)路由設備預留外部存儲器空間進行歷史流量信息和操作信息的記錄；2)設定路由設備的路由的起始時間以及路由量度變化的單位時段，根據本發明設計的聚合樹網絡模型，引入了增量算法協議適應於動態拓撲結構及鏈路權值網絡隨時間的動態改變。並且在路由設備的內部高速存儲器中構建新型的路由表；3)針對通信網內路由設備的不同類型，在路由設備的內部存儲器中構建發送路由子表，根據本發明設計的動態聚合樹網絡模型，在路由設備的高速存儲器構建高速路由緩存表；4)確定路由設備的每條物理網絡接口的物理標識和接口標識，用以唯一確定數據發送單元，即鄰居，並構建鄰居信息列表；5)根據確定的時間間隔向鄰居發送探測數據包，用以確定鏈路的狀態；6)當路由設備在收到由鄰居發送的新的路由表信息時，根據本發明設計路由表信息更新算法來更新相應的高速緩存表項，並判斷是否需要觸發路由表計算；7)如需要進行路由表的計算，根據本發明設計的路由表更新算法進行路由表的更新，根據本發明設計的路由狀態信息格式，組織被更新的路由表項，形成路由數據包，由路由設備的網絡接口發送給鄰居；8)根據當前時間段的變化運行路由協議程序自動更新當前路由表；9)每隔一段時間通過物理網絡接口向鄰居發送下N個時段的路由信息，N因具體的網絡環境而異，本發明設計預設值為4。
2.根據權利要求1所述的一種基於動態聚合樹模型的路由方法，其特徵在於，聚合樹網絡模型是網絡N＝(V，A，W)，其中V是有限節點集，AV×V是有限鏈路集；W＝{w(a)|a∈A}，W是A→R+的鏈路權值映射函數。聚合樹模型為N_Tree＝(T，H)，其中T是N的域集合；若T只含一個域，則H＝Φ，否則H是定義在T上的二元關係；在T中存在唯一的稱為根的域root，它在關係H下無定義；若T-{root}≠Φ，則存在T-{root}的一個劃分T1，T2，…，Tn(n＞0)，j≠k，l≤j，k≤n，有Tj∩Tk∈V，且對任意的Tj∩Tk∈V存在唯一域mi∈Ti，有root，mi∈H；對應於T-{root}的劃分，H-{root，m1，…，root，mn}有唯一的一個劃分H1，H2，…，Hn，j≠k，l≤j，k≤n，有Hj∩Hk＝Φ，且i，1≤i≤n，Hi是Ti上的二元關係，(Ti，Hi)是一棵符合本定義的聚合樹，稱為根域root的子聚合樹。
3.根據權利要求1所述的一種基於動態聚合樹模型的路由方法，其特徵在於，增量算法路由協議，當網絡的鏈路狀態發生改變時，相關的路由器調用增量算法更新網絡的狀態及受到影響的路由器的路由表；增量算法具體包括三個部分，其中鏈路刪除協議和鏈路增加協議對應大規模網絡中網絡的拓撲結構隨時間變化的情況，鏈路改變協議對應大規模網絡中網絡的鏈路狀態隨時間變化的情況；當網絡中某個路由器收到的數據包表明它所連接的鏈路參數發生改變時，觸發該算法識別受到影響的所有路由器及鏈路，然後對這些受到影響的路由器的路有表中各信息進行更新。
4.根據權利要求1所述的一種基於動態聚合樹模型的路由方法，其特徵在於，路由表的構建方法是該表包含量度路由子表D，由目標地址(由域類地址和節點類地址兩部分組成)索引表項，目標地址由域類地址和節點類地址兩部分組成，每個元素Dj是從當前節點到目的地址j最短路徑的權值；下一跳路由子表P，由目標地址索引表項，每個元素Pj是從當前節點到目的地址j最短路徑的下一跳；發送路由子表V，一個路由信息的集合，每個元素Vj，Dj是從當前節點到目的地址j最短路徑的最近一次計算的權值。
5.根據權利要求1所述的一種基於動態聚合樹模型的路由方法，其特徵在於，高速路由緩存表構建方法是該表由鄰居節點、目標地址索引表項，二維緩存表T，每個元素Tkj是從當前節點路經鄰居節點k到達目的地址j最短路徑的權值。
6.根據權利要求1所述的一種基於動態聚合樹模型的路由方法，其特徵在於，路由設備接到路由數據包後，首先執行網絡分割算法，形成聚合樹模型；運行完這一算法，每個節點都掌握了其子域節點的信息；節點地址由關聯節點從根域開始遞歸分配。
7.根據權利要求1所述的一種基於動態聚合樹模型的路由方法，其特徵在於，路由信息更新過程是進行高速路由緩存表的更新，具體步驟為(1)初始化，每個路由器n在接到鄰居節點i的路由數據包後，進行分類處理如果i為節點地址信息，那麼初始化n的節點類路由表信息；如果i為域地址信息，那麼初始化n的域類路由表信息，然後形成發送路由信息發送給鄰居節點；(2)緩存表和路由表更新，當緩存表中的路由或是權值有改變，形成發送路由信息發送給鄰居節點更新路由表信息，路由設備將接到的路由數據包進行分類處理對於更新路由表項中V的每一個元素j，cost，如果高速路由緩存表中不存在Tij，那麼將Vij賦值為j，cost+Di加入集合V中；如果Tij＞cost+Di，那麼將Tij更新為cost+Di，並設置標號flag為true；如果flag為true，那麼對每一個目標地址j作如下操作如果Dj≠minTij並且Pj≠i，那麼Dj←Tij，Pj←i，V←j，Dj；(3)路由信息的會聚，各路由器將收到的路由信息收集，進行路由表的重新計算；當收到的路由信息為域類地址信息如果鄰居節點是當前節點的子域，那麼除了這一子域的信息外，其餘信息都發送，其它情況下，發送所有信息；當收到的路由信息為節點類地址信息發送所有信息給同域、父域的鄰居節點，對於鄰居節點在子域的情況，除了子域信息外的其它信息都發送；(4)結束。
全文摘要
一種基於動態聚合樹模型的路由方法屬於網絡通信技術領域。本發明使用現有的路由設備作為通訊網絡的路由節點，以大規模網絡聚合樹模型作為路由模型，引入了增量算法適應於網絡隨時間動態改變的情況，並設計了分布式路由協議完成路由功能。路由步驟包括建立聚合樹模型；分配物理和接口標識；建立及更新路由表、高速路由緩存表；接受路由信息；發送路由表的更新信息；發送路由探測包，確定鏈路狀況。本發明有效的解決了網絡動態拓撲結構及鏈路權值隨時間變化的動態路由問題，獲得了符合實際的精確優化結果和很高的路由效率。其協議符合QoS路由的目標，併兼容多種路由模式。適合於網際網路骨幹網自治域的使用。
文檔編號H04L29/06GK1655556SQ20051020015
公開日2005年8月17日 申請日期2005年3月18日 優先權日2005年3月18日
發明者譚國真, 韓寧寧, 劉屹, 李棟 申請人:大連理工大學