(57)【特許請求の範囲】
【請求項１】
端末および他のパケット転送中継装置とネットワークを介して接続され、相互間でパケット転送を行なうパケット転送中継装置において、
パケット転送中継装置の相互の接続状況を元に、各パケット転送中継装置を多次元座標空間上の点に対応させ、各点の座標を取得する手段と、
転送先候補となる他のパケット転送中継装置と送信元のパケット転送中継装置との間の多次元座標空間上の距離を算出する手段と、
算出した結果の距離が最小となるパケット転送中継装置を転送先として選択する手段と、
転送すべきパケットに、送信先のパケット転送中継装置の多次元座標空間上の座標の情報を付加する手段とを備えたことを特徴とするパケット転送中継装置。
【請求項２】
請求項１に記載のパケット転送中継装置において、
前記各パケット転送中継装置の多次元座標空間上の座標を記憶する手段を備えたことを特徴とするパケット転送中継装置。
【請求項３】
ネットワーク内のパケット転送中継装置の相互の接続状況を元に、各パケット転送中継装置を多次元座標空間上の点に対応させ、
任意のパケット転送中継装置からパケットを発信する場合には、送信先のパケット転送中継装置に対応する多次元座標空間上の座標に関する情報を該パケットに付加し、
該パケットを隣接のパケット転送中継装置に送出する場合には、隣接する一つ以上のパケット転送中継装置の各座標および送信元のパケット転送中継装置の座標を元に送信先のパケット転送中継装置の多次元座標空間上の距離が最小となるパケット転送中継装置の一つに送出し、
上記ネットワーク内の各パケット転送中継装置の多次元座標空間上の点への対応付けは、動的経路制御プロトコルを利用し、あるいはトポロジーマッピング部により設定情報により得られた各パケット転送中継装置の接続情報に基づいて各パケット転送中継装置を多次元座標空間上の点に対応させ、上記対応関係をマップ記憶部に記憶し、
また、上記ネットワーク内のパケット転送中継装置のアドレスを含む問い合わせに対して、上記マップ記憶部を検索して、上記対応関係により得られた該ノードの座標を答えるアドレス・マップ装置により行なうことを特徴とするパケット転送制御方法。
【請求項４】
ネットワーク内のパケット転送中継装置の相互の接続状況を元に、各パケット転送中継装置を多次元座標空間上の点に対応させ、
任意のパケット転送中継装置からパケットを発信する場合には、送信先のパケット転送中継装置に対応する多次元座標空間上の座標に関する情報を該パケットに付加し、
該パケットを隣接のパケット転送中継装置に送出する場合には、隣接する一つ以上のパケット転送中継装置の各座標および送信元のパケット転送中継装置の座標を元に送信先のパケット転送中継装置の多次元座標空間上の距離が最小となるパケット転送中継装置の一つに送出し、
上記ネットワーク内の各パケット転送中継装置は、上記アドレス・マップ装置に対して問い合わせを行ない、上記ネットワーク内のパケット転送中継装置に関して対応する座標を示す対応表を保持し、
パケットの転送に当っては、該パケットの転送元装置あるいは転送元装置を直接収容するパケット転送中継装置が、上記対応表を参照して宛先アドレスに対応する転送先装置あるいは転送先装置を収容するパケット転送中継装置の座標に関する情報が、上記対応表に存在する場合はそれを、存在しない場合は上記アドレス・マップ装置に問い合わせを行なって、得られた情報を用いて上記宛先装置の座標に関するラベル情報をパケットに付加することを特徴とするパケット転送制御方法。
【請求項５】
ネットワーク内のパケット転送中継装置の相互の接続状況を元に、各パケット転送中継装置を多次元座標空間上の点に対応させ、
任意のパケット転送中継装置からパケットを発信する場合には、送信先のパケット転送中継装置に対応する多次元座標空間上の座標に関する情報を該パケットに付加し、
該パケットを隣接のパケット転送中継装置に送出する場合には、隣接する一つ以上のパケット転送中継装置の各座標および送信元のパケット転送中継装置の座標を元に送信先のパケット転送中継装置の多次元座標空間上の距離が最小となるパケット転送中継装置の一つに送出し、
上記パケット転送中継装置は、隣接するパケット転送中継装置あるいはリンクに関しての障害状況をモニタし、障害発生時あるいは回復時に、上記多次元座標空間上で座標が近接しているパケット転送中継装置に障害通知を行ない、
通知を受けたパケット転送中継装置は、上記ラベル情報に基づく次転送先決定の際に、該障害情報を利用して障害箇所を迂回することを特徴とするパケット転送制御方法。
【請求項６】
ネットワーク内のパケット転送中継装置の相互の接続状況を元に、各パケット転送中継装置を多次元座標空間上の点に対応させ、
任意のパケット転送中継装置からパケットを発信する場合には、送信先のパケット転送中継装置に対応する多次元座標空間上の座標に関する情報を該パケットに付加し、
該パケットを隣接のパケット転送中継装置に送出する場合には、隣接する一つ以上のパケット転送中継装置の各座標および送信元のパケット転送中継装置の座標を元に送信先のパケット転送中継装置の多次元座標空間上の距離が最小となるパケット転送中継装置の一つに送出し、
上記ネットワーク内の障害の数や停止期間など障害程度が閾値を越えた場合には、動的経路制御プロトコルを利用して、あるいは障害近傍のパケット転送中継装置からの通知により、該状況を上記アドレス・マップ装置が認識し、該アドレス・マップ装置がその時点での各パケット転送中継装置を接続する接続線の物理的な接続情報に基づく各パケット転送中継装置の多次元座標空間上の点への再対応付けを行なうことを特徴とするパケット転送制御方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、パケット転送の転送先を決定する際に、検索する座標検索テーブルのエントリー数をネットワークの規模にかかわらず少数にすることができ、高速な検索処理が可能なパケット転送中継装置および転送制御方法に関する。
【０００２】
【従来の技術】
従来より、ルータ等のパケット転送中継装置を相互に接続したパケット転送ネットワークが知られており、特にインターネット・プロトコル（ＩＰ）を用いたパケット転送ネットワークが広く用いられている。ＩＰを用いるネットワークにおいては、ネットワーク内のルータやホスト等の装置にアドレスが付与されている。パケット転送元の装置は宛先装置のアドレスをパケットのヘッダに記載して、ネットワーク内に投入する。パケット転送中継装置では、パケット中に記された宛先アドレスについてパケット転送中継装置内に記憶した経路表等を検索して、次転送先のパケット転送中継装置あるいは送出する接続線を決定し、転送処理を行う。
【０００３】
従来のパケット転送中継装置では、図２に示すように、パケットが入力ポート１１に入力されると、振分部１２で経路制御プロトコルパケットとそれ以外に分別され、経路制御プロトコルパケットは経路制御プロトコル処理部１３で処理される。経路制御プロトコル処理部１３は、ＯＳＰＦ（Ｏｐｅｎ  Ｓｈｏｒｔｅｓｔ  Ｐａｔｈ  Ｆｉｒｓｔ）あるいはＲＩＰ（Ｒｏｕｔｉｎｇ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｐｒｏｔｏｃｏｌ）等の動的経路制御プロトコルの処理を行ない、ダイクストラ・アルゴリズムやベルマン・フォード・アルゴリズムなどに基づいて、パケット転送に用いる経路表１５を作成する。
経路制御プロトコルパケット以外のパケットは、通常転送処理部１４に送られる。通常転送処理部１４では、そのパケットに含まれる宛先アドレスに関して経路表１５を検索し、次転送先を選択して転送を行なう。
【０００４】
図３は、従来のパケット転送中継装置の経路表を示す図である。
図１に示すパケット転送ネットワークにおいて、従来のルータを利用して転送中継を行う場合に、ノードＤに設置されたルータの経路表を示している。
図３では、宛先ＡからＳに関して集約（アグリゲーション）をしておらず、実際には、宛先ＡからＳはアドレスのプレフィックスであり、アグリゲーションによって経路表１５のエントリー数はより少ない可能性がある。
一般に、従来のルータ等を利用する場合の各パケット転送中継装置の経路表１５のエントリー数は、ネットワークの規模に応じて増大する。経路表１５は、全てのパケットの転送の際に参照され、その検索時間は大凡エントリー数の対数に比例する。
【０００５】
【発明が解決しようとする課題】
このように、従来、インターネットなどのパケット転送ネットワークにおいて、通常、装置のアドレスはネットワークのトポロジー構成とは無関係に割り当てられている。パケット転送中継装置では、装置内の経路表に宛先のプレフィックス毎にエントリーを作成するため、ネットワーク規模の増大に伴って経路表も増大し、経路表の検索処理に時間がかかることになる。経路表のエントリー数が大きくなるに応じて経路表検索に必要な処理の量も大きくなるため、装置の処理能力を大きくする必要があった。
【０００６】
特に、実現しつつある、あるいは将来実現が期待されている無線中継局を多数配置したパケット転送ネットワーク、例えばＩＥＥＥ８０２．１１を利用した無線ＬＡＮネットワークや次々世代携帯電話ネットワーク、Ｂｌｕｅｔｏｏｔｈを用いたアドホック・ネットワークにおいては、従来よりネットワークの規模が大きく、かつ／または、ネットワーク中のパケット転送中継装置間の接続線数が大きくなることが予想される。このようなネットワークにおいては、従来の手法では経路表検索処理量の増大が予想される。
【０００７】
そこで、本発明の目的は、これら従来の課題を解決し、大規模なネットワークにおいても検索する経路表のエントリー数を増加させずに、高速に処理可能なパケット転送中継装置および転送制御方法を提供することにある。
【０００８】
【課題を解決するための手段】
上記目的を達成するため、本発明のパケット転送中継装置は、(1)端末および他のパケット転送中継装置とネットワークを介して接続され、相互間でパケット転送を行なうパケット転送中継装置において、パケット転送中継装置の相互の接続状況を元に、各パケット転送中継装置を多次元座標空間上の点に対応させ、各点の座標を取得する手段と、転送先候補となる他のパケット転送中継装置と送信元のパケット転送中継装置との間の多次元座標空間上の距離を算出する手段と、算出した結果の距離が最小となるパケット転送中継装置を転送先として選択する手段と、転送すべきパケットに、送信先のパケット転送中継装置の多次元座標空間上の座標の情報を付加する手段とを備えたことを特徴としている。
【０００９】
また、(2)上記（1)に記載のパケット転送中継装置において、前記各パケット転送中継装置の多次元座標空間上の座標を記憶する手段を備えたことも特徴としている。
【００１０】
また、本発明のパケット転送制御方法は、(3)ネットワーク内のパケット転送中継装置の相互の接続状況を元に、各パケット転送中継装置を多次元座標空間上の点に対応させ、任意のパケット転送中継装置からパケットを発信する場合には、送信先のパケット転送中継装置に対応する多次元座標空間上の座標に関する情報を該パケットに付加し、該パケットを隣接のパケット転送中継装置に送出する場合には、隣接する一つ以上のパケット転送中継装置の各座標および送信元のパケット転送中継装置の座標を元に送信先のパケット転送中継装置の多次元座標空間上の距離が最小となるパケット転送中継装置の一つに送出し、上記ネットワーク内の各パケット転送中継装置の多次元座標空間上の点への対応付けは、動的経路制御プロトコルを利用し、あるいはトポロジーマッピング部により設定情報により得られた各パケット転送中継装置の接続情報に基づいて各パケット転送中継装置を多次元座標空間上の点に対応させ、上記対応関係をマップ記憶部に記憶し、また、上記ネットワーク内のパケット転送中継装置のアドレスを含む問い合わせに対して、上記マップ記憶部を検索して、上記対応関係により得られた該ノードの座標を答えるアドレス・マップ装置により行なうことを特徴としている。
【００１１】
また、(4)ネットワーク内のパケット転送中継装置の相互の接続状況を元に、各パケット転送中継装置を多次元座標空間上の点に対応させ、任意のパケット転送中継装置からパケットを発信する場合には、送信先のパケット転送中継装置に対応する多次元座標空間上の座標に関する情報を該パケットに付加し、該パケットを隣接のパケット転送中継装置に送出する場合には、隣接する一つ以上のパケット転送中継装置の各座標および送信元のパケット転送中継装置の座標を元に送信先のパケット転送中継装置の多次元座標空間上の距離が最小となるパケット転送中継装置の一つに送出し、上記ネットワーク内の各パケット転送中継装置は、上記アドレス・マップ装置に対して問い合わせを行ない、上記ネットワーク内のパケット転送中継装置に関して対応する座標を示す対応表を保持し、パケットの転送に当っては、該パケットの転送元装置あるいは転送元装置を直接収容するパケット転送中継装置が、上記対応表を参照して宛先アドレスに対応する転送先装置あるいは転送先装置を収容するパケット転送中継装置の座標に関する情報が、上記対応表に存在する場合はそれを、存在しない場合は上記アドレス・マップ装置に問い合わせを行なって、得られた情報を用いて上記宛先装置の座標に関するラベル情報をパケットに付加することを特徴としている。
【００１２】
また、(5)ネットワーク内のパケット転送中継装置の相互の接続状況を元に、各パケット転送中継装置を多次元座標空間上の点に対応させ、任意のパケット転送中継装置からパケットを発信する場合には、送信先のパケット転送中継装置に対応する多次元座標空間上の座標に関する情報を該パケットに付加し、該パケットを隣接のパケット転送中継装置に送出する場合には、隣接する一つ以上のパケット転送中継装置の各座標および送信元のパケット転送中継装置の座標を元に送信先のパケット転送中継装置の多次元座標空間上の距離が最小となるパケット転送中継装置の一つに送出し、上記パケット転送中継装置は、隣接するパケット転送中継装置あるいはリンクに関しての障害状況をモニタし、障害発生時あるいは回復時に、上記多次元座標空間上で座標が近接しているパケット転送中継装置に障害通知を行ない、通知を受けたパケット転送中継装置は、上記ラベル情報に基づく次転送先決定の際に、該障害情報を利用して障害箇所を迂回することも特徴としている。
【００１３】
また、(6)ネットワーク内のパケット転送中継装置の相互の接続状況を元に、各パケット転送中継装置を多次元座標空間上の点に対応させ、任意のパケット転送中継装置からパケットを発信する場合には、送信先のパケット転送中継装置に対応する多次元座標空間上の座標に関する情報を該パケットに付加し、該パケットを隣接のパケット転送中継装置に送出する場合には、隣接する一つ以上のパケット転送中継装置の各座標および送信元のパケット転送中継装置の座標を元に送信先のパケット転送中継装置の多次元座標空間上の距離が最小となるパケット転送中継装置の一つに送出し、上記ネットワーク内の障害の数や停止期間など障害程度が閾値を越えた場合には、動的経路制御プロトコルを利用して、あるいは障害近傍のパケット転送中継装置からの通知により、該状況を上記アドレス・マップ装置が認識し、該アドレス・マップ装置がその時点での各パケット転送中継装置を接続する接続線の物理的な接続情報に基づく各パケット転送中継装置の多次元座標空間上の点への再対応付けを行なうことも特徴としている。
【００１４】
【発明の実施の形態】
以下、本発明の実施例を、図面により詳細に説明する。
図４は、本発明におけるアドレス・マップ装置の概念を示すブロック図である。
本発明におけるアドレス・マップ装置は、ネットワーク内の各パケット転送中継装置の多次元座標空間上の点への対応付けを行なう装置であって、図４に示すように、経路制御プロトコル処理部１３とトポロジー・マッピング部２２とマップ記憶部２３と問い合わせ処理部２１とから構成される。アドレス・マップ装置は、物理的にはパケット転送中継装置の一つに、図４に示す各処理部を付加したものであってもよい。従って、アドレス・マップ装置は、各パケット転送中継装置内にそれぞれ含ませることができるのは勿論であるが、複数のパケット転送中継装置毎に１箇所ずつ独立したアドレス・マップ装置を設置することもでき、あるいは複数のパケット転送中継装置のうちの１つのパケット転送中継装置内に含ませることで、その他のパケット転送中継装置の要求に対応することも可能である。
経路制御プロトコル処理部１３は、ＩＰ通信で利用されるＯＳＰＦ、ＡＴＭネットワークで利用されるＰＮＮＩ（Ｐｒｉｖａｔｅ  Ｎｅｔｗｏｒｋ−Ｎｅｔｗｏｒｋ  Ｉｎｔｅｒｆａｃｅ）等のリンク・ステート型動的経路制御プロトコルの処理を行ない、例えば、図１に示すようなネットワークの物理的トポロジーを再現・保持する機能を有している。
【００１５】
図１において、白丸はパケット転送中継装置を、白丸中のＡからＳまでのアルファベットはパケット転送中継装置のアドレスを、白丸間を結ぶ直線はパケット転送中継装置間の接続線をそれぞれ表わしている。
トポロジーマッピング部２２は、上記経路制御プロトコル処理部１３が再現・保持するネットワークの物理的トポロジーに基づいて、各パケット転送中継装置を多次元座標空間上の点に対応させる機能を有する。
【００１６】
任意のグラフ（リニアグラフ）について、その平面性を判定するアルゴリズムが知られている（例えば、Ｋ．Ｓ．Ｂｏｏｔｈ  ａｎｄ  Ｇ．Ｓ．Ｌｕｅｋｅｒ，“Ｔｅｓｔｉｎｇ  ｆｏｒ  ｔｈｅ  ｃｏｎｓｅｃｕｔｉｖｅ  ｏｎｅｓ  ｐｒｏｐｅｒｔｙ，  ｉｎｔｅｒｖａｌ  ｇｒａｐｈｓ，ａｎｄ  ｇｒａｐｈ  ｐｌａｎａｒｉｔｙ  ｕｓｉｎｇ  ＰＱ−ｔｒｅｅ  Ａｌｇｏｒｉｔｈｍ，”Ｊｏｕｎａｌ  ｏｆ  Ｃｏｍｐｕｔｅｒ  ａｎｄ  Ｓｙｓｔｅｍ  Ｓｃｉｅｎｃｅｓ，１３：３３５−３７９，１９７６）。また、これらのアルゴリズムを繰り返し用いて、非平面グラフのサブグラフで、クラトゥスキー・グラフＫ５あるいはＫ３．３と同相なものを識別することができ、このサブグラフに含まれる任意の一つのエッジ（辺）を元のグラフより除去する操作を繰り返し行なえば、元の非平面グラフのサブグラフである平面グラフを得ることができる。さらに、平面グラフを実際に座標平面上に埋め込むアルゴリズムとして、Ｎ．Ｎｉｓｈｉｚａｋｉ  ａｎｄ  Ｎ．Ｃｈｉｂａ．“Ｐｌａｎａｒ  Ｇｒａｐｈｓ：Ｔｈｅｒｙ  ａｎｄ  Ａｌｇｏｒｉｔｈｍｓ．”Ａｎｎａｌｓ  ｏｆ  Ｄｉｓｃｒｅｔｅ  Ｍａｔｈｅｍａｔｉｃｓ（３２），Ｎｏｒｔｈ−Ｈｏｌｌａｎｄ  Ｍａｔｈｅｍａｔｉｃｓ  Ｓｔｕｄｉｅｓ，１９８８などが知られている。以上述べたアルゴリズムの計算量は、いずれもグラフの大きさ（ノード数およびエッジ数）に比例することが知られている。これらのアルゴリズムをトポロジー・マッピング部２２で用いることで、ネットワークの物理的トポロジーを多次元座標空間上に対応付けることが可能である。
【００１７】
図５は、図１におけるネットワークの座標空間への対応付け例を示す図である。
例えば、図１で示すネットワークのトポロジー・マッピング部２２による多次元座標空間への対応付けは複数あり得るが、そのうちの二次元格子状座標空間への対応付けの一例を示したのが図５である。
図５の対応付けでは、パケット転送中継装置間の各接続線を多次元座標空間における各次元成分の大きさが１か０であるようなベクトルに対応させている。
図５において、ＡからＳを付けた白丸は図１の各パケット転送中継装置に対応し、（０，１）などは、対応付けにおいての各パケット転送中継装置の座標である。白丸間の太い直線はパケット転送中継装置間の接続線に対応する。
【００１８】
トポロジーマッピング部２２により作成された多次元座標空間への対応付けは、マップ記憶部２３に格納される。
問い合わせ処理部２１は、ネットワーク内のパケット転送中継装置等の他装置から送られる問い合わせパケットを受け付け、問い合わせパケット中に含まれるネットワーク内のパケット転送中継装置のアドレスに関して、マップ記憶部２３に格納されたネットワークのトポロジーの多次元座標空間への対応付けを参照して、ノードの座標を含む問い合わせ回答パケットを作成し、問い合わせパケットの発信元である上記装置に送付する。
【００１９】
図６は、本発明の一実施例を示すパケット転送中継装置のブロック構成図である。
本発明のパケット転送中継装置は、経路制御プロトコル処理部１３と経路表１５と通常転送処理部１４とからなる通常のルータを構成する機能に加えて、座標ラベル作成部２０とローカルトポロジー処理部１７と座標転送テーブル１８と座標転送処理部１９とをその構成に含んでいる。
図６のパケット転送中継装置に到着したパケットは、先ず振分部１２において、座標ラベルが付加されていないパケットと座標ラベルが付加されているものに分別される。座標ラベルが付加されていないパケットのうち、経路制御プロトコルパケットは経路制御プロトコル処理部１３で処理される。座標ラベルが付加されていないパケットであり、かつ経路制御プロトコルパケットでないものは、座標ラベル作成部２０で処理される。また、座標ラベルが付加されているパケットであり、かつ後述するローカルトポロジーパケットでないものは、座標転送処理部１９で処理される。さらに、座標ラベルが付加されているパケットで、かつローカルトポロジーパケットであるものは、ローカルトポロジー処理部１７で処理される。
【００２０】
座標ラベル作成部２０は、座標ラベルが付加されていないパケット（以下、データパケット）を受け取ると、該データパケットの宛先アドレスに関して、前記アドレス・マップ装置への問い合わせパケットを作成して送付する。アドレス・マップ装置からの問い合わせ回答パケットを待つ間、該データパケットはバッファされる。アドレス・マップ装置からの問い合わせ回答パケットが規定時間内に到着した場合、座標ラベル作成部２０は問い合わせ回答パケットから座標を取り出し、該データパケットに座標ラベルとして付加し、座標転送処理部１９に送る。アドレス・マップ装置からの問い合わせ回答が規定時間内に到着しない場合、通常のルータの場合と同様に、該データパケットの宛先アドレスについて経路表１５を検索して、次転送装置を決定し転送を行なう。
座標転送処理部１９は、座標ラベル付きのパケットについて、該座標ラベルの示す宛先装置の座標と自らの座標を比較し、次転送先を決定して転送を行なう。
【００２１】
図７は、本発明における座標による転送の概念図である。
座標に基づく転送の一般的なイメージを示すと、図７のようになる。ここで、Ａは自装置であり、Ａ周辺の白丸はＡに直接接続するパケット転送中継装置であり、Ａから宛先装置への方向により次転送先となるパケット転送中継装置が定まる。Ｂが宛先装置である場合には、次転送先はＣとなる。
【００２２】
図８は、本発明におけるパケット転送中継装置での座標による転送処理の一実施例（１）の図である。
図５で示される座標空間への対応のもとで、パケット転送中継装置Ｄの座標転送処理部の動作を説明する。座標転送テーブルには、隣接するパケット転送中継装置に関して、その方向と中継装置のアドレスが記載されている。データパケットの宛先装置がＯである場合には、座標転送処理部１９は、先ず宛先装置の座標（５，３）から自座標（１，２）をベクトルとして引き算し、宛先の方角を示すベクトル（４，１）を得る。宛先の方角を示すベクトルと、座標転送テーブルの各エントリーの方向との間で、各座標成分の差を合計した拡張ハミング距離を計算し、拡張ハミング距離が最小となるパケット転送中継装置Ｆを次転送先として選択する。
【００２３】
図９は、本発明におけるパケット転送中継装置での座標による転送処理の一実施例（２）の図である。
図５で示される座標空間への対応のもとで、パケット転送中継装置Ｄの座標転送処理の動作を説明する。座標転送テーブルには、二次元座標空間における周囲８方向について次転送先の中継装置のアドレスが記載されている。本実施例（２）では、８方向のうち直接接続するパケット転送中継装置がない方向については該方向に最も近い方向で直接接続するパケット転送中継装置（複数ある場合には、図中で半時計周りに近いもの）を次転送先として座標転送テーブルを構成する。
いま、データパケットの宛先装置がＯである場合、座標転送処理部１９は、先ず宛先装置の座標（５，３）から自座標（１，２）をベクトルとして引き算し、宛先の方角を示すベクトル（４，１）を得る。次に、宛先の方角を示すベクトルの各座標成分のうち絶対値が最大のもの（４）で該ベクトルを割って規格化し（１，０．２５）、さらに各成分を切り上げして得られた（１，１）に一致する座標転送テーブルのエントリーを参照し、次転送先としてＦを選択する。
【００２４】
図８および図９の座標転送テーブルの構成に見られるように、本発明においては、座標転送テーブルのエントリー数はネットワークの規模、つまりネットワークに含まれるパケット転送中継装置や接続線、宛先装置の数とは無関係であるため、ネットワークの大規模化に対応することができる。座標転送テーブルのエントリー数は、図８および図９に示す座標転送テーブルと従来の図３に示すパケット転送中継装置の経路表１５とを比べると明らかなように、図８および図９の方が図３よりも小さいため、高速な検索が可能である。従来方式における経路表１５、および本発明方式における座標転送テーブルの各検索は、全てのデータパケットに関して行なわれる処理であるため、検索処理が高速に行われると、パケット転送処理全体の高速化につながることになる。
【００２５】
各パケット転送中継装置は、自装置の座標とそれぞれが隣接する他の転送中継装置の座標、隣接する他のパケット転送中継装置および／あるいは接続線での障害の有無に関する情報を、周辺の転送装置との間で交換することができる。この交換に用いるパケットをローカルトポロジーパケットと呼ぶ。ローカルトポロジーパケットには、具体的には、例えば自装置の座標と、自装置に隣接し現在通信可能な装置の座標の列（あるいは直前にローカルトポロジーパケットを発した時点以降で、新たに通信可能または不可能となった装置の座標の列と通信状態）が記載される。あるいは、ローカルトポロジーパケットには、自装置の座標と、自装置に隣接し現在通信可能な装置の座標と自装置座標をベクトルとして引き算して得たベクトルの列を記載してもよい。パケット転送中継装置に他のパケット転送中継装置から到着したローカルトポロジーパケットは、前述の振分部１２による振り分けによりローカルトポロジー処理部１７に送られる。ローカルトポロジー処理部１７は、該ローカルトポロジーパケットに記載された情報に基づき座標転送テーブルの内容を更新する。
座標転送テーブルは、自装置からの方向別のテーブルであり、ネットワーク全体のトポロジーを表現するものではないため、ローカルトポロジーパケットは多次元座標空間において自装置の近隣にのみ届けばよい。
【００２６】
図１０は、本発明におけるローカルトポロジー情報の情報配布範囲の例（１）を示す図である。
図１０においては、黒丸で示す座標（ｐ，ｑ）の転送装置の障害に関するローカルトポロジーパケットの配布範囲の制限の一例を示している。丸が転送中継装置を、丸を結ぶ直線がパケット転送中継装置間の接続線を示す。障害装置の周囲の装置が、それぞれが隣接する転送装置にのみローカルトポロジーパケットを送付することにより、配布範囲は障害装置から２ホップ以内の灰色丸のパケット転送中継装置に限定される。
【００２７】
図１１は、本発明におけるローカルトポロジー情報の情報配布範囲の例（２）を示す図である。
図１１においては、黒丸で示す座標（ｐ，ｑ）の転送装置の障害に関するローカルトポロジーパケットの配布範囲の制限の一例を示している。丸がパケット転送中継装置を、丸を結ぶ直線がパケット転送中継装置間の接続線を示す。障害装置の周囲の装置からｘおよびｙの座標軸に平行な方向にのみ障害情報を通知することで、配布範囲が灰色丸のパケット転送中継装置に限定される。
【００２８】
図１２は、図５におけるローカルトポロジー情報の配布範囲の例を示す図である。
図１２では、図５に示した座標空間への一対応において、ローカルトポロジーパケットの送付を１ホップに限定した場合の送付範囲を示している。すなわち、Ｇからのローカルトポロジーパケットは、Ｆ，Ｈ，Ｒ，Ｑに、Ｎからのローカルトポロジーパケットは、Ｌ，Ｍ，Ｓ，Ｏに、それぞれ配布される。
【００２９】
図１３は、図５における接続線障害の例を示す図、図１４は図１３におけるパケット転送中継装置でのパケット転送中継処理の例（１）を示す図である。
図１４では、座標転送処理部１９が図８で示した動作を行う場合に、図１３に示すようにパケット転送処理ＤとＦとの間の接続線に障害が発生した場合について、宛先Ｏへのパケットに関するパケット転送中継装置Ｄでの座標転送処理部１９の動作を示している。すなわち、障害の発生により、Ｄの座標転送テーブルからは、方向（１，１）のエントリーが削除される。宛先方角のベクトルを計算し、拡張ハミング距離の計算の結果、残ったエントリーのうち、拡張ハミング距離が最小であるＥが次転送先として選択される。
【００３０】
図１５は、図１３におけるパケット転送中継装置Ｄでのパケット転送中継処理の例（２）を示す図である。
図１５では、座標転送処理部１９が図９で示した動作を行う場合に、図１３に示すように座標転送中継装置ＤとＦとの間の接続線に障害が発生した場合について、宛先Ｏへのパケットに関するパケット転送中継装置Ｄでの座標転送処理部１９の動作を示している。すなわち、障害の発生により、Ｄの座標転送テーブルでは、Ｆを次転送先とするエントリーが図９に関して説明した規則に従って変更される。宛先方角のベクトルを計算し、規格化と切り上げを行なった結果、次転送先としてＥが選択される。
【００３１】
図１６は、図１での接続線障害の例を示す図、図１７は、図１６のネットワークの格子状座標空間への再対応付けの例を示す図である。
パケット転送中継装置あるいは接続線の障害が長時間に及ぶ場合、あるいは障害の発生や障害からの回復が多地点で発生した場合、トポロジーマップ装置は、当該時点で有効な物理的な接続トポロジーと以前になされた多次元座標空間への対応付けが乖離していることを動的経路制御プロトコルにより、あるいは網内装置からの通知により検知し、多次元座標空間への再対応付けを行なう。
図１６では、図１のトポロジーにおいて、図１６に示すパケット転送中継装置ＧとＱの間の接続線の長期にわたる途絶を検知したトポロジーマップ装置が行なった再対応付けを示している。
【００３２】
【発明の効果】
以上説明したように、本発明によれば、パケット転送中継装置がパケット転送を行なう場合に、検索する座標検索テーブルのエントリー数はネットワークの規模に関係なく少数とすることができるので、大規模なネットワークにおいても高速な検索処理が可能になる、という顕著な効果がある。
【図面の簡単な説明】
【図１】本発明に適用されるパケット転送ネットワークの例を示す図である。
【図２】従来のパケット転送中継装置のブロック図である。
【図３】従来のパケット転送中継装置の経路表の概念図である。
【図４】本発明の一実施例を示すアドレス・マップ装置のブロック図である。
【図５】図１のネットワークの格子状座標空間への対応付けの例を示す図である。
【図６】本発明の一実施例を示すパケット転送中継装置のブロック図である。
【図７】本発明における座標による転送の概念を示す図である。
【図８】本発明の一実施例（１）を示すパケット転送中継装置での座標による転送処理の説明図である。
【図９】本発明の一実施例（２）を示すパケット転送中継装置での座標による転送処理の説明図である。
【図１０】本発明におけるローカルトポロジー情報の情報配布範囲の例（１）を示す図である。
【図１１】本発明におけるローカルトポロジー情報の情報配布範囲の例（２）を示す図である。
【図１２】図５でのローカルトポロジー情報の配布範囲の例を示す図である。
【図１３】図５における接続線障害の例を示す図である。
【図１４】図１３におけるパケット転送中継装置Ｄでのパケット転送中継処理の例（１）を示す図である。
【図１５】図１３におけるパケット転送中継装置Ｄでのパケット転送中継処理の例（２）を示す図である。
【図１６】図１での接続線障害の例を示す図である。
【図１７】図１６のネットワークの格子状座標空間への再対応付け例を示す図である。
【符号の説明】
１１…入力ポート、１２…振分部、１３…経路制御プロトコル処理部、
１４…通常転送処理部、１５…経路表、１６…出力ポート、
２１…問い合わせ処理部、２２…トポロジーマッピング部、
２３…マップ記憶部、１７…ローカルトポロジー処理部、
１８…座標転送テーブル、１９…座標転送処理部、２０…座標ラベル作成部。
【図１】
0003622672.tif 000002
【図２】
0003622672.tif 000003
【図３】
0003622672.tif 000004
【図４】
0003622672.tif 000005
【図５】
0003622672.tif 000006
【図６】
0003622672.tif 000007
【図７】
0003622672.tif 000008
【図８】
0003622672.tif 000009
【図９】
0003622672.tif 000010
【図１０】
0003622672.tif 000011
【図１１】
0003622672.tif 000012
【図１２】
0003622672.tif 000013
【図１３】
0003622672.tif 000014
【図１４】
0003622672.tif 000015
【図１５】
0003622672.tif 000016
【図１６】
0003622672.tif 000017
【図１７】
0003622672.tif 000018