JPH10501935A - ローカルに構成されたルーチング・テーブルを使用したパケット通信網においてパケットをルーチングする方法およびシステム - Google Patents

Abstract

(57)【要約】 ノードに絶対座標ベースのアドレスが割り当てられ、ディレクトリ・ベースのルーチングを使用せずに各ノードてルーチングの決定が下される（Ｓ２、Ｓ７）パケット通信システムにおいて、最終的な宛先を有する特定のパケットに対して下されたルーチングの決定は、そのノードによって同じ最終的な宛先へ次に送信されるパケットが、その宛先に関して前に下されたルーチングの決定に従って転送できるように、各ノードごとに記憶される。ルーチングの決定は各ノードごとにローカル・ルーチング・テーブルに記憶される（Ｓ６、Ｓ１２）。一実施形態では、ノードは、最初の送信元に対する返信パケットが受信されたときに、中継ノードがすでにルーチング上の決定を下さなくても済むように、パケットの送信元ノードに関するルーチング情報も記憶する。

Description

【発明の詳細な説明】 ローカルに構成されたルーチング・テーブルを使用した パケット通信網においてパケットをルーチングする方法およびシステム 発明の背景 本発明は、パケット通信網内でデータ・パケットをルーチングする方法に関し 、詳細には、各ノードで生成されるルーチング・テーブルにノード間の最良の経 路が記憶されているネットワーク内でデータ・パケットをルーチングする方法に 関する。 パケット通信は、データのセグメントまたはパケットがエラー検査および受信 の確認と共にルーチングされるデータ通信の形態である。パケットは送信元ノー ドと宛先ノードとの間で直接送信することも、あるいはいくつかの中継ノードを 介して中継することもできる。いくつかのデータ・パケット・ルーチング方法が 知られている。 １つの方法は、ディレクトリ・ベースのルーチングとして知られている。この 方法によれば、パケットのヘッダ中のアドレスが、送信元ノードに記憶されてい るパケット・ルーチング・リストのディレクトリのインデックスとして使用され る。パケット・ルーチング・リストは、送信元ノードから宛先ノードへの完全な 送信経路を表すパケット・ノード識別子または呼出し符号の順序付きリストから なる。パケットが送信元ノードから送信された後、ネットワーク内のパケットの 経路は、送信元ノードに記憶されていたパケット・ルーチング・リストによって 決定される。パケット・ルーチング・リストは、ネットワーク中の各ノードの接 続性に関する知識を用いて作成しなければならず、通常のディレクトリ・ベース ・ルーチング方式では、各ノードは、それがパケットを送信するネットワーク中 の他のあらゆるノードに関する完全なルーチング・リストを維持しなければなら ない。ディレクトリ・ベースのルーチング方式は、ディレクトリで使用されるネ ットワーク相互接続情報の継続的な維持および通信を必要とする。これらの機能 はそれぞれ、ネットワーク資源をかなり使用し、このため、大規模なネットワー クの性能が著しく低下することがある。しかし、ディレクトリ・ベースのルーチ ング技法は、データ遅延、スループット、信頼性、優先順位などを含め、様々な ネットワーク・パラメータに関してルーチングを最適化できるようにするという 利点を有する。 他の基本的なルーチング技法は、非ディレクトリ・ベースのルーチング技法で ある。非ディレクトリ・ベースのルーチングでは、ディレクトリ・ベースのルー チングに伴う複雑さが回避される。ネットワーク中の各送信側ノードごとの接続 性情報を記憶する必要はなく、したがって、ネットワークの接続を保存するため にネットワークによって行わなければならないオーバヘッド処理の量が低減され る。しかし、非ディレクトリ・ベースのルーチング技法では一般に、ネットワー ク・パラメータを最適化することはできない。 Ｂａｒａｎその他に発行され、出願人に譲渡された米国特許第４，９３９，７ ２６号では、ネットワーク・パラメータを最適化できるようにする非ディレクト リ・ベースのルーチング方法およびシステムが開示されている。この特許に記載 された方法によれば、ネットワーク中の各ノードは、絶対地理座標、または外部 座標ベースの基準系（ノード座標）中の絶対位置を示す符号によって固有に識別 され、そのような絶対地理座標または等価物は、各パケットごとのパケット識別 子の一部として使用される。パケットをルーチングするための各ノードごとの手 段は、パケット宛先座標およびその近傍のノードのノード座標を使用してデータ ・パケットの所望の伝送経路を決定する。受信されるパケットが、ノードがすで にパケットを受信している宛先へ送られる場合でも、ルーチングの決定は、受信 される各パケットごとに下される。ルーチングは、好ましくは最適な転送、すな わち、最少量の電力しか使用せず、かつシステムの特性を考慮に入れた最大の転 送を行うように、事前に選択された基準に従って優先順位付けすることができる 。 したがって、Ｂａｒａｎパケット・ルーチング方法は、ルーチング・ディレク トリもルーチング・テーブルも使用せずにデータ・ルーチングを実行する。ネッ トワークの各ノードは、それ自体と、そのノードの通信範囲内の近傍のノードと の間の通信の質に関する情報を収集し、あるいはその他の方法で各ノードにその ような情報が与えられる。ノードでデータ・パケットが受信されると、データ・ パケットは、ローカル・ノードとその近傍のノードとの間の通信の履歴から導か れた基準に基づいてさらにネットワーク内でルーチングされる。この基準には、 距離、電力要件、再試行履歴（信頼性）、スループット履歴、転送速度（正味デ ータ転送速度）、ネットワーク遅延、データ優先順位が含まれる。通常、宛先象 限内の近傍の緯度および経度を判定するために実行される初期設定手順があり、 基準が、事前に選択された優先順位に従って重み付けされ、各ノードごとに、各 ノードに対してローカルな可能な各宛先ごとのリンク品質（ＬＱ）係数が確立さ れる。Ｂａｒａｎシステムでは、受信されており転送する必要がある各パケット ごとに、ノードは、可能な中継ノードのリストを作成し、そのリストを順序付け 、次いで近傍のノードをポールし、どのノードが使用できるかを調べる。 Ｂａｒａｎで開示されたシステムは、うまく実行され、ディレクトリ・ベース のルーチング・システムに勝る利点を有するものとして知られているが、ネット ワーク中の各ノードが、受信する各パケットに関するルーチングの決定を下す必 要があるので、Ｂａｒａｎネットワークはコストがかかり、遅延をもたらす。Ｂ ａｒａｎ座標ベースのアドレス方式の利点を維持するが、各パケットに関するル ーチングの決定を下すうえでＢａｒａｎシステムで必要とされるあらゆるパケッ トのオーバヘッドおよび処理を必要としないネットワークおよびルーチング方法 が必要である。 発明の概要 本発明によれば、ノードに絶対座標ベースのアドレスが割り当てられ、ディレ クトリ・ベースのルーチングを使用せずに各ノードごとにルーチングの決定が下 されるパケット通信システムにおいて、ある最終的な宛先を有する特定のパケッ トに対して下されたルーチングの決定は、そのノードによって同じ最終的な宛先 へ次に送信されるパケットが、その宛先に対して下されたルーチングの第１の決 定に従って転送できるように、各ノードごとに記憶される。ルーチングの決定は 各ノードごとにローカル・ルーチング・テーブルに記憶される。一実施態様では 、ノードは、最初の送信元に対する返信パケットが受信されたときに、中継ノー ドがすでにルーチングの適当な決定を算出しているように、パケットの送信元ノ ー ドに関するルーチング情報も記憶する。 ネットワークの動作中に、各ノードは、パケットをその最終的宛先に向かって 次のノードへ送るうえで有用なルーチング・テーブルを作成し維持する。本発明 による方法によれば、最終的な宛先へのパケットに対してルーチングの決定を下 さなければならないのは、その宛先へのパケットとその宛先からのパケットのど ちらかが初めて受信されたときだけである。宛先ノードに対するパケットを受信 した中継ノードは、宛先ノードの絶対座標ベースのアドレスに基づいてそのパケ ットの次の中継ノードを判定する。中継ノードが最終的な宛先に対する次の中継 ノードを判定した後、その情報はルーチング・テーブルに記憶され、その後その 中継ノードで受信されるその最終的な宛先へのパケットはただちに、ルーチング ・テーブルにリストされている次の中継ノードへルーチングされる。本発明の一 実施態様では、中継ノードは、その中継ノードへパケットを送信した中継ノード が、送信元ノードに返信されるパケットに関する最良の次の中継ノードであると 仮定することによって、受信したパケットの送信元ノードに対する次の中継ノー ドも記憶する。このように、中継ノードは、送信元に返信される宛先からの返信 パケットを受信したときには、そのパケットに関するルーチングの決定を下す必 要はなく、その代わり、そのパケットが送信されてきた経路に沿ってそのパケッ トを送り返す。 本発明によって構築されたネットワーク・システムは、パケットに関するルー チングの決定がローカルに各ノードごとに下されるという点でディレクトリ・ベ ースのルーチング・システムとは異なる。送信元ノードは、宛先ノードに達する 完全な経路を指定するわけではなく、最終的なノードの方向の近傍のノードへパ ケットを送信するだけであり、その近傍のノードは、最終的なノードへの経路中 の次の中継ノードを判定する。本発明によって構築されたシステムは、ルーチン グに関するローカルな決定がローカルに記憶され、次いで他のパケットをルーチ ングする際に使用できるという点で、Ｂａｒａｎのシステムとは異なる。Ｂａｒ ａｎとは異なり、パケットが受信されるたびにノードがルーチングの決定を下す 必要はなく、これによって、ネットワークの速度および効率が大幅に向上する。 本発明は、添付の図面に関連して下記の詳細な説咀を参照することによってよ りよく理解されよう。 図面の簡単な説明 第１図は、本発明による一般的なデータ・ネットワーク・トポロジを示すブロ ック図である。 第２図は、宛先ノードにアドレスされたパケットを受信したときの中継ノード の動作を説明するフローチャートである。 特定の実施形態の詳細な説明 第１図は、本発明によるデータ・ネットワークを示す。このネットワークは、 ノード間の許容される通信リンクを表す経路１２によって相互接続されたＯ〜Ｚ と呼ばれるノードからなる。ルーチングの決定が下された宛先へのパケットの送 信を高速化するために、矢印１６で表されたルーチング・テーブル項目がある種 のノード間に存在する。 送信元ノードと宛先ノードとの間のデータ送信は下記のように行われる。ノー ドＷは、ノードＯへ情報パケットを送信したい場合、ノードＷを送信元として識 別し、ノードＯを宛先として識別し、ノードＷ自体およびノードＯの絶対座標ベ ースのアドレスを与えるヘッダと共に、データ・パケットを準備する。ノードＷ は次いで、そのルーチング・テーブルを検査して、ノードＯに関する項目がある かどうか調べる。ノードＯに関する項目がない場合Ｂａｒａｎシステムと同様に ルーチングの決定を下す。すなわち、ノードＷは、それが通信できるすべてのノ ード（この場合はＺおよびＹであり、ノードＷの近傍のノードとも呼ばれる）を 調べ、ノードＯの方向へ送信するうえでどれが最も有利かに応じてこれらのノー ドを順序付けし、最も有利なノードへポーリング・パケットを送信し、そのノー ドがデータ・パケットを受信できるかどうかを判定することによってルーチング を決める。ノードＷは、ある近傍のノードがノードＯへパケットを中継できると 判定した後、そのパケットの送信元および宛先を識別し、ノードＷ自体を送信機 として識別するヘッダと共に、そのデータ・パケットを、選択されたノード（こ の場合はノードＹ）へ送信する。本発明によれば、ノードＷは、最終的な宛先Ｏ へパケットを到達させるうえで送信を行うべき中継ノードがノードＹであると判 定した後、その情報をルーチング・テーブルに記憶する。ノードＷは、次にノー ドＯへパケットを送信したいときは、ルーチング・テーブルを検査し、Ｏに関す る項目を見つけ、上記とは異なりルーチングの決定を下すプロセスを実行せずに ただちにそのパケットをノードＹへ送信する。 ノードＹは、パケットを受信すると、やはりノードＹ自体のルーチング・テー ブルを検査して、宛先ノードＯに関する項目があるかどうか調べる。項目がある 場合、パケットは即座にルーチング・テーブル中の次のノードとしてリストされ ているノードに中継される。項目がない場合、ノードＹは、前述のルーチングの 決定を下すプロセスを実行し、次いで次のノード（この場合はＶ）をノードＯに 関する項目としてルーチング・テーブルに記憶し、次いで次のノードへこのパケ ットを転送する。 ノードＶは、パケットを受信すると、そのルーチング・テーブル内でノードＯ を探し、項目を見つけた場合は、その項目にリストされているノードへパケット を送信する。Ｏに関する項目がない場合、ノードＶは、前述のようにルーチング の決定を下し、次いでＯに関するルーチング・テーブル項目を作成する。同時に 、ノードＶは、そのルーチング・テーブルと近傍ノード・リストを検査して、ノ ードＷ、すなわちそのパケットの最初の送信元ノードに関する項目があるかどう か調べる。ノードＷに関する項目がない場合、ノードＶは、ノードＷに関するル ーチング・テーブル項目を作成し、ノードＶにＷからのパケットを送信したノー ド（この場合はノードＹ）を、Ｗに戻るパケットの次の中継ノードとして使用す る。このように、ノードＶは、ＯからＷへの応答パケットを受信した場合、その パケットに関するルーチングの新たな決定を下す必要なしにそのパケットをただ ちにノードＹへ転送する。下記の表は、ノードＷからの、ノードＯに対するパケ ットを、受信し、送信した後のノードＶのキャッシュ・ルーチング・テーブルを 表すものである。 本発明によるノードは、ルーチング・テーブルが、各項目が最後に使用された のはいつかを追跡するように設計される。ルーチング・テーブルが満杯になると 、パケットに関するルーチングの新たな決定が下されるたびに、最初に使用され た項目が破棄され、新しい項目が作成される。 第２図は、本発明の一実施形態による中継ノードの動作を示すフローチャート を示す。このプロセスのステップは特定の順序で示されているが、当業者には、 このプロセスに含まれるいくつかのサブプロセスの順序を変更することができ、 このプロセスのいくつかのステップを並行して処理できることが自明であろう。 このプロセスではまず、中継ノードがルーチングに関するパケットを受信する（ ステップＳ１）。前述のように、パケットは、送信元ノードおよび宛先ノードの 絶対アドレスと、パケットを送信してきた近傍のノードのアドレスを含む。中継 ノードはまず、パケットの送信元ノード識別子を調べて、その送信元ノードが、 中継ノードが直接送信できる近傍のノードであるかどうかを判定する（ステップ Ｓ２）。そうでない場合、中継ノードはそのルーチング・テーブルを調べて、そ の送信元ノードに関する項目があるかどうか調べる（ステップＳ３）。項目がな い場合、送信元ノードは、ルーチング・テーブルが満杯かどうか調べて（ステッ プＳ４）、そうである場合は最も古い時期に使用された項目を削除する（ステッ プＳ５）。中継ノードは次いで、送信元ノードに関するルーチング・テーブル項 目を作成する（ステップＳ６）。 送信元ノード識別子の処理が完了した後、中継ノードは、パケットの宛先ノー ド識別子を調べる。宛先ノードが、中継ノードが直接送信できる近傍のノードで ある場合（ステップＳ７）、中継ノードはパケットを送信する（ステップＳ８） 。そうでない場合、中継ノードはそのルーチング・テーブルを調べて、すでに宛 先 ノードに関する項目があるかどうかを判定する（ステップＳ９）。パケットの宛 先ノードに関するルーチング・テーブル項目がない場合、中継ノードは、ルーチ ング・テーブルに新しい項目用の空間があるかどうか調べる（ステップＳ１０） 。ルーチング・テーブルに新しい項目用の空間がない場合、中継ノードは、最も 古く使用された項目を削除し、新しい項目用の空間を設ける（ステップＳ１１） 。中継ノードは次いで、宛先ノードに関する新しいルーチング・テーブル項目を 作成する（ステップＳ１２）。宛先項目は、上記で説明しＢａｒａｎ特許に記載 されたルーチングの決定を下すプロセスによって作成される。宛先ノードに関す るルーチング・テーブル項目が作成された後、中継ノードはその項目を使用して （ステップＳ１３）、パケットをその宛先へ転送する（ステップＳ８）。 当業者には、この手順に対するいくつかの修正例が自明であろう。たとえば、 送信元ノード識別子を処理し送信元ノード項目を作成するステップは、パケット の送信後に実行することも、あるいはパケットの送信中に実行することもできる 。他の例は、送信元ノードに関する古い項目が存在するときでも、送信元ノード ・ルーチング・テーブル項目を常に更新することである。 本発明を特定の実施形態に関して説明した。当業者には他の実施形態が明らか であろう。したがって、本発明は、添付の請求の範囲で示したものを除いて本発 明を制限するものではない。

Claims (1)

1. 【特許請求の範囲】 １．ネットワーク・ディレクトリなしでデータ・パケットをルーチングする方 法であって、 座標位置を示し絶対座標値を含む識別子をネットワーク中の各ノードに割り当 てるステップと、 ネットワークがパケットを任意の中間経路を介して最終的な宛先ノードへ自由 にルーチングできる最終的な宛先ノードへの完全な中間経路を指定することなし に、前記最終的な宛先ノードをその最終的な宛先ノードの前記絶対値によっての みパケット・ヘッダに指定することにより、前記最終的な宛先ノードにパケット をアドレスするステップと、 中継ローカル・ノードにおいて、事前に選択された基準に従って、前記パケッ ト・ヘッダと前記ローカル・ノードに特有のその他の情報を使用することによっ て１つの近傍のノードを選択するステップと、 前記中継ノードにおいて、前記選択された近傍のノードの識別子を、前記最終 的な宛先ノード用のラベルと共にルーチング・テーブルに記憶するステップと、 前記パケットを、前記最終的な宛先ノードへ最終的に転送できるように、前記 選択された近傍のノードへ転送するステップと、 前記最終的な宛先に対するその後のパケットが前記中継ノードで受信されたと きに、前記選択された近傍のノードの前記ルーチング・テーブルから前記識別子 を検索し、その後のパケットをその識別子によって前記ノードへ転送するステッ プと を含むことを特徴とする方法。 ２．前記選択するステップが、前記パケット・ヘッダを使用して、前記最終的 な宛先ノードに対する前記近傍のノードの距離を求めることを含むことを特徴と する請求項１に記載の方法。 ３．前記選択するステップが、前記ローカル・ノードと前記近隣のノードとの 間の通信履歴を維持するローカル・テーブルを作成することを含むことを特徴と する請求項１に記載の方法。 ４．さらに、前記中継ノードにおいて、直接送信可能な近傍のノードの識別子 を、前記送信元ノード用のラベルと共にルーチング・テーブルに記憶するステッ プと、 前記送信元ノードへ送られる返信パケットが前記中継ノードで受信されたとき に、前記ルーチング・テーブルから前記直接送信可能な近傍のノードの前記識別 子を検索するステップと、 前記その後のパケットを前記識別子によって前記ノードへ転送するステップと を含むことを特徴とする請求項１、２、または３に記載の方法。 ５．「待ち時間」予想計算で使用されるリンク品質係数を使用して、好ましい 通信経路が定義されることを特徴とする請求項３に記載の方法。 ６．ネットワーク・ディレクトリのないパケット・データ通信網においてデー タ・パケットをルーチングするシステムであって、 それぞれ、座標位置を示し地上格子に対する座標値を含む識別子を含むネット ワーク中の複数のノードと、 ネットワークがパケットを任意の中間経路を介して最終的な宛先ノードへ自由 にルーチングできるように最終的な宛先ノードへの完全な中間経路を指定するこ となしに、前記最終的な宛先ノードをその最終的な宛先ノードの前記座標値によ ってのみパケット・ヘッダに指定することにより、前記最終的な宛先ノードにパ ケットをアドレスする手段と、 ルーチング・テーブル項目が、パケットの最終的な宛先ノードの識別子によっ て選択することができ、近傍のノードを前記最終的な宛先に対する転送ノードと して識別する情報を含むとき、前記複数のノードのそれぞれにおいて前記最終的 な宛先に関する前記ルーチング・テーブル項目を記憶する手段と を備えることを特徴とするシステム。 ７．ネットワーク・ディレクトリのないパケット・データ通信網においてデー タ・パケットをルーチングするシステムであって、 それぞれ、地理的位置を示し地上格子に対する座標値を含む識別子を含むネッ トワーク中の複数のノードと、 ネットワークがパケットを任意の中間経路を介して最終的な宛先ノードへ自由 にルーチングできるように最終的な宛先ノードへの完全な中間経路を指定するこ となしに、前記最終的な宛先ノードをその最終的な宛先ノードの前記座標値によ ってのみパケット・ヘッダに指定することにより、前記最終的な宛先ノードにパ ケットをアドレスする手段と、 中継ローカル・ノードにおいて、事前に選択された基準に従って、前記パケッ ト・ヘッダと前記ローカル・ノードに特有のその他の情報を使用することによっ て少なくとも１つの近傍のノードを選択する手段と、 最終的に前記最終的な宛先ノードへ転送できるように、前記パケットを前記選 択された近傍のノードへ転送する手段と、 ルーチング・テーブル項目が、パケットの最終的な宛先ノードの識別子によっ て選択することができ、近傍のノードを前記最終的な宛先に対する転送ノードと して識別する情報を含むとき、前記複数のノードのそれぞれにおいて、前記最終 的な宛先に関する前記ルーチング・テーブル項目を記憶する手段と を備えることを特徴とするシステム。 ８．前記選択する手段が、前記パケットを転送するうえで最少量の電力しか必 要としない１つの近傍のノードを選択する手段を備えることを特徴とする請求項 ７に記載のシステム。 ９．前記選択手段が、前記パケット・ヘッダを使用して、前記最終的な宛先ノ ードに対する近傍のノードの距離を求める手段を備えることを特徴とする請求項 ７に記載のシステム。 １０．前記選択する手段が、前記ローカル・ノードと前記近隣のノードとの間 の通信履歴を維持するリンク・リストを作成する手段を備えることを特徴とする 請求項７に記載のシステム。 １１．前記リンク・リストが、距離、通信を確立するのに必要な出力電力、再 試行履歴（信頼性）、スループット履歴、転送速度（正味データ転送速度）、ネ ットワーク遅延、データ優先順位、リンク使用度、所望の宛先への近さ、所望の 方位への近さ、無作為さ、ローカル方位への近さの各基準のうちの少なくとも１ つに関する前記近傍のノードに関する情報を維持することを特徴とする請求項１ ０に記載のシステム。 １２．リンク品質係数を使用して、好ましい通信経路が定義されることを特徴 とする請求項１０に記載のシステム。