[發明專利]為數據分組選擇路由的方法和系統

無效

• 申請號: 95192561.X
• 申請日: 1995-04-11
• 公開（公告）號: CN1152383A
• 公開（公告）日: 1997-06-18
• 發明（設計）人: 喬治H·福雷麥三世
• 申請（專利權）人: 麥垂考姆公司
• 主分類號: H04J3/24
• 分類號: H04J3/24;H04J1/16;H04J3/14;H04L12/56;H04L12/46;H04L12/66;H04Q11/04
• 代理公司: 中原信達知識產權代理有限責任公司
• 代理人: 余朦

一般地說，本發明涉及一種通過分組通信網為數據分組選擇路由的方法，更確切地說，涉及一種在其中各節點之間的最佳路徑被存儲在在每個節點生成的路由選擇表中的網絡中為數據分組選擇路由的方法。

分組通信是一種數據通信形式，利用這種通信形式通過誤差檢驗和接收確認為數據段或分組選擇路由。數據分組可直接在一個源節點和一個目標節點之間傳送，或經多個中繼節點中繼。已知有幾種數據分組路由選擇方法。

公知的方法之一是基于號碼簿的路由選擇方法。按照該方法，分組信標中的地址被用作存儲在一個源節點中的分組路由選擇表的號碼簿的索引。分組路由選擇表由一個順序排列的分組節點標識符或呼號的列表構成，所述的呼號代表從源節點到目標節點的完整傳輸路徑。一旦該數據分組從源節點被送出，其通過網絡的路徑就由存儲在源節點中的分組路由選擇表確定。分組路由選擇表必須利用關于網絡中每個節點的連通性的知識來準備，并且在一個典型的基于號碼簿的路由選擇方案中，每個節點必須為該網絡中其發送數據分組到達的每個其他節點保持一個完整的路由選擇表。基于號碼簿的路由選擇方案需要不斷的維護和在號碼簿中使用的網絡互聯信息的通信。這些功能的每一種都要消耗網絡資源，并會大大地降低大網絡中的性能。然而，基于號碼簿的路由選擇技術具有相對于包括數據延遲，通過率，穩定性，優先權等的各種網絡參數使路由選擇最佳化的優點。

路由選擇技術的另一基本方案是非基于號碼簿的路由選擇技術。在非基于號碼簿的路由選擇中，避免了與基于號碼簿的路由選擇技術相關的復雜性。在網絡中不必為每個發送節點存儲連通性信息，從而降低了為保持網絡連接必須由網絡執行的處理開銷量。然而，非基于號碼簿的路由選擇技術一般不允許網絡參數最佳化。

在授權給Baran等人并已轉讓給本發明受讓人的美國專利4,939,726中，公開了一種允許網絡參數最佳化的非基于號碼簿的路由選擇方法和系統。根據其中描述的方法，網絡中的每個節點由在一外部的基于坐標的參考系統中的絕對地理坐標或由一個指示絕對位置的碼(節點坐標)唯一地確定，并且所述絕對地理坐標或等效物被作為每個分組的分組標識符的一部分使用。為每個數據分組做出路由選擇決定，即使該分組被指向該節點已為其接收了一個分組的目標。按照預定的準則，路由選擇可被優先化，最好實現最佳前向過程，即-使用最少量的功率并考慮系統的特征的最大前向過程。

?因此，Baran等人的分組路由選擇方法不使用路由選擇號碼簿或表執行數據路由選擇。網絡的每個節點收集或反之被提供有關該節點的通信區域內其自身和相鄰節點間的通信質量的信息。當在一節點處一個數據分組已被接收到時，根據從該本地節點與其相鄰節點間通信的記錄中獲得的準則通過網絡進一步為該分組進行路由選擇。該準則包括距離，功率要求，重試記錄(可靠性)，通過量記錄，轉發速度(純數據速率)，網絡延遲，和數據優先權。典型地，具有一個初始化程序，執行該程序以確定在一目標象限內各相鄰節點的緯度和經度，且根據預選的優先權對該準則加權，以在每個從屬節點為每個可能的屬于該從屬節點的目標地點建立一鏈路質量因數(LQ)。對于被接收和需要被前向發送的每個分組，Baran系統中的節點生成一個可能的中繼節點表，為該表排序，然后對相鄰節點進行查詢，看看哪個節點是可用的。

雖然Baran中描述的系統表明執行的很好，且具有高于非基于號碼簿的路由選擇方案的優點，但由于網絡中的每個節點對其接收的每個分組必須做出路由選擇確定，所以在Baran網絡中存在著費用和延遲問題。所需要的是這樣一種網絡和路由選擇方法，其保留了Baran的基于坐標的選址方案的優點，但不要求開銷和在Baran系統中為做出關于每個分組的路由選擇決定所需的每個分組的處理。

按照本發明，在其中各節點被指定了一個獨立的基于坐標的地址，且在每個節點處做出路由選擇決定，而無需使用基于號碼簿的路由選擇的分組通信系統中，利用最終目標為一特定分組做出的路由選擇決定被存儲在每個節點處，以便由該節點發送到該同一最終目標的下一分組能根據該最初為該目標做出的路由選擇決定被前向發送。路由選擇決定被存儲在每個節點處的一個本地路由選擇表中。在一個實施例中，各節點還為分組存儲有關源節點的路由選擇信息，以便當原始的源接收到一返回分組時，中繼節點已計算出了合適的路由選擇決定。