(57)【要約】【課題】経路に障害が発生したときに、運用者の手間を煩わせることなく迅速な経路の迂回措置を可能にする。【解決手段】ＨＣＮノード１は、端末Ａから直接的に宛先アドレスを含むデータを受信した場合に、その宛先アドレスの端末Ｂと直接的に通信するＨＣＮノード８のノードＩＤをテーブルから抽出し、宛先ノードＩＤとしてデータに付与することで、端末間の通信の中継に、自ノードＩＤと宛先ノードＩＤの排他的論理和演算によって転送先を決定するハイパーキューブネットワークを適用可能にする。また、各ＨＣＮノードでは、障害が発生したリンクの次元数を優先ビットとして設定しておき、データ転送時に優先ビットがある場合には、排他的論理和演算の結果が１となる桁のうち優先ビットに対応する桁が自ノードＩＤに対して反転しているノードＩＤをもつ転送装置に対してデータを転送することで、転送先を自律的に変更する。【選択図】図１
2008066843.tif 000002
【特許請求の範囲】
【請求項１】
複数の転送装置に２進数のノードＩＤを割り振り、各転送装置と当該転送装置の自ノードＩＤにおける１つのビットを反転させたノードＩＤを持つ他の転送装置との間でリンクが形成されるハイパーキューブネットワークにより端末間でのデータ通信を中継するデータ転送システムであって、
各転送装置は、
各端末のアドレスと端末が接続されている転送装置のノードＩＤを示すテーブルを記憶しておく記憶手段と、
使用を回避すべきリンクに関わる２つの転送装置のノードＩＤが反転するビットの桁数(次元数)を優先ビットとして記憶手段に記憶させておく優先ビット管理手段と、
端末から直接的に宛先アドレスを含むデータを受信した場合に、その宛先アドレスの端末と直接的に通信する転送装置のノードＩＤを前記テーブルから抽出し、宛先ノードＩＤとしてデータに付与する付与手段と、
他の転送装置から宛先ノードＩＤが付与されたデータを受信した場合に、その宛先ノードＩＤを取得して記憶手段に記憶させる取得手段と、
自ノードＩＤと前記宛先ノードＩＤとの排他的論理和を演算し、その演算結果を記憶手段に記憶させる演算手段と、
付与又は受信して得た前記宛先ノードＩＤが付与されたデータを、前記演算結果が１となる最も小さい桁が自ノードＩＤに対して反転しているノードＩＤをもつ転送装置に対して送信するか、前記優先ビットがある場合には前記演算結果が１となる桁のうち優先ビットに対応する桁が自ノードＩＤに対して反転しているノードＩＤをもつ転送装置に対して送信する送信手段と、
を有することを特徴とするデータ転送システム。
【請求項２】
複数の転送装置に２進数のノードＩＤを割り振り、各転送装置と当該転送装置の自ノードＩＤにおける１つのビットを反転させたノードＩＤを持つ他の転送装置との間でリンクが形成されるハイパーキューブネットワークにより端末間でのデータ通信を中継するデータ転送方法であって、
各端末のアドレスと端末が接続されている転送装置のノードＩＤを示すテーブル、および使用を回避すべきリンクに関わる２つの転送装置のノードＩＤが反転するビットの桁数(次元数)を示す優先ビットを記憶手段に記憶した転送装置により、
端末から直接的に宛先アドレスを含むデータを受信した場合に、その宛先アドレスの端末と直接的に通信する転送装置のノードＩＤを前記テーブルから抽出し、宛先ノードＩＤとしてデータに付与するステップと、
他の転送装置から宛先ノードＩＤが付与されたデータを受信した場合に、その宛先ノードＩＤを取得して記憶手段に記憶させるステップと、
自ノードＩＤと前記宛先ノードＩＤとの排他的論理和を演算し、その演算結果を記憶手段に記憶させるステップと、
付与又は受信して得た前記宛先ノードＩＤが付与されたデータを、前記演算結果が１となる最も小さい桁が自ノードＩＤに対して反転しているノードＩＤをもつ転送装置に対して送信するか、前記優先ビットがある場合には前記演算結果が１となる桁のうち優先ビットに対応する桁が自ノードＩＤに対して反転しているノードＩＤをもつ転送装置に対して送信するステップと、
を有することを特徴とするデータ転送方法。
【請求項３】
複数の転送装置に２進数のノードＩＤを割り振り、各転送装置と当該転送装置の自ノードＩＤにおける１つのビットを反転させたノードＩＤを持つ他の転送装置との間でリンクが形成されるハイパーキューブネットワークにより端末間でのデータ通信を中継するデータ転送システムに用いられる転送装置であって、
各端末のアドレスと端末が接続されている転送装置のノードＩＤを示すテーブルを記憶しておく記憶手段と、
使用を回避すべきリンクに関わる２つの転送装置のノードＩＤが反転するビットの桁数(次元数)を優先ビットとして記憶手段に記憶させておく優先ビット管理手段と、
端末から直接的に宛先アドレスを含むデータを受信した場合に、その宛先アドレスの端末と直接的に通信する転送装置のノードＩＤを前記テーブルから抽出し、宛先ノードＩＤとしてデータに付与する付与手段と、
他の転送装置から宛先ノードＩＤが付与されたデータを受信した場合に、その宛先ノードＩＤを取得して記憶手段に記憶させる取得手段と、
自ノードＩＤと前記宛先ノードＩＤとの排他的論理和を演算し、その演算結果を記憶手段に記憶させる演算手段と、
付与又は受信して得た前記宛先ノードＩＤが付与されたデータを、前記演算結果が１となる最も小さい桁が自ノードＩＤに対して反転しているノードＩＤをもつ転送装置に対して送信するか、前記優先ビットがある場合には前記演算結果が１となる桁のうち優先ビットに対応する桁が自ノードＩＤに対して反転しているノードＩＤをもつ転送装置に対して送信する送信手段と、
を有することを特徴とする転送装置。
【請求項４】
直接接続されているリンクにおける障害の発生を検知して当該リンクの次元数を記憶手段に記憶させる検知手段と、
他の転送装置から障害が発生したリンクの次元数を含むデータを受信し、当該リンクの次元数を記憶手段に記憶させる受信手段と、
検知又は受信して得た前記リンクの次元数を、経由したリンクの数を示すホップ数より大きい次元数のうち障害が発生したリンクの次元数およびデータを受信したリンクの次元数を除いた次元数に対応する桁が自ノードＩＤに対して反転しているノードＩＤをもつ転送装置に対して送信する送信手段と、を有し、
前記優先ビット管理手段は、受信して得た前記リンクの次元数を優先ビットとして記憶手段に記憶させることを特徴とする請求項３記載の転送装置。
【請求項５】
直接接続されているリンクにおける障害の発生を検知して当該リンクの次元数を記憶手段に記憶させる検知手段と、
検知して得た前記リンクの次元数を、１ホップ先にだけ転送する旨と併せて隣接する転送装置に対して送信する送信手段と、
他の転送装置から前記リンクの次元数および前記旨を含むデータを受信する受信手段と、
前記旨を受信した場合には、以降のデータ転送を停止する手段と、を有し、
前記優先ビット管理手段は、受信して得た前記リンクの次元数を優先ビットとして記憶手段に記憶させることを特徴とする請求項３記載の転送装置。
【請求項６】
前記検知手段は、リンクの利用率を監視し、利用率が記憶手段に予め記憶している閾値を超えたときに当該リンクの次元数を記憶手段に記憶させることを特徴とする請求項４又は５記載の転送装置。
【請求項７】
全ての次元数が優先ビットになったときに、自ノードＩＤに対して全てのビットが反転しているノードＩＤをもつ転送装置に障害が発生したと判断する判断手段と、
障害発生と判断された転送装置のノードＩＤを他の転送装置に送信する送信手段と、
障害発生と判断された転送装置のノードＩＤを他の転送装置から受信する受信手段と、
判断又は受信して得た障害発生と判断された転送装置のノードＩＤを前記テーブルに反映させて抽出対象から除外する手段と、
を有することを特徴とする請求項３記載の転送装置。
【請求項８】
端末との間での直接的な接続／接続断を検知して当該端末のアドレスを前記テーブルに反映させる検知手段と、
他の転送装置から接続／接続断を検知した転送装置のノードＩＤおよび検知された端末のアドレスを含むデータを受信して当該ノードＩＤおよび当該アドレスを前記テーブルに反映させる第２受信手段と、
検知又は受信して得た接続／接続断を検知した転送装置のノードＩＤおよび検知された端末のアドレスを、経由したリンクの数を示すホップ数より大きい次元数のうちデータを受信したリンクの次元数を除いた次元数に対応する桁が自ノードＩＤに対して反転しているノードＩＤを持つ転送装置に対して送信する第２送信手段と、
を有することを特徴とする請求項３記載の転送装置。
【請求項９】
前記テーブルは、端末が異なる転送装置に２重に接続される場合に、いずれの転送装置を優先させるかを示す種別も記録するものであって、
前記第２送信手段は、接続／接続断を検知した転送装置のノードＩＤおよび検知された端末のアドレスに加えて前記種別を送信し、
前記第２受信手段は、当該ノードＩＤおよび当該アドレスに加えて当該種別を前記テーブルに反映させ、
前記付与手段は、前記テーブルからの抽出対象となるノードＩＤのうち、優先の種別がある方のノードＩＤを宛先ノードＩＤとして採用することを特徴とする請求項８記載の転送装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、端末間でのデータ通信を中継するためのデータ転送技術に関する。
【背景技術】
【０００２】
各端末にＩＰアドレスを割り振って通信を行うＩＰ網では、各端末がネットワーク全体の経路、形態といったトポロジを表現したルーティング(経路選択)テーブルを保持し、それに基づきデータに宛先アドレス等を示すＩＰヘッダを付与してパケットとし、これを送受信する。そして端末間の送受信をルータが中継する。このようなＩＰ網においては、任意のトポロジを構成できる反面、経路の学習が必要であり、故障発生時には経路の再学習が必要となり、経路の切り替えに時間がかかるという問題があった。
【０００３】
また、近年は、ルータにおいてＩＰヘッダに代えて「ラベル」とよばれる識別情報を用いることで、より大容量化・高速化を図るＭＰＬＳ(Multi Protocol Label Switching)が知られている。ＭＰＬＳでは、通常時に利用する経路の他に、故障時に利用する予備経路を予め設定することが可能である。また、リンクの利用率が高くなるとパケットロスが発生し易くなるところ、ＭＰＬＳは、リンクの利用率からパケットロスによる障害発生を予測する機能を有しており、故障の未然防止、予防保全に役立てることが可能である。なお、本願に関する公知文献としては次のものがある。
【非特許文献１】青山友紀，”ＭＰＬＳとフォトニックＧＭＰＬＳ”，電気通信協会，２００３年１２月１５日
【非特許文献２】Y. Saad, M.H.Schultz, etc., "Topological Properties of Hypercubes", IEEE Transactions on computers, Vol.37, No.7, July, 1998
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、ＭＰＬＳでは、経路の正常性監視の間隔が大きく、経路断の検知に時間がかかるため、故障発生時には予備経路が設定されているにも関わらず復旧までに相応の時間を要することになる。そこで、ＭＰＬＳでは、レイヤ２からの警報を元に、断検知された経路を高速に迂回するＦＲＲ(First ReRoute)が実現されている。
【０００５】
ところが、ＦＲＲでは、迂回用の予備経路は、通常経路の断検知された部分の終端ノードをその終端ノードとして設定する必要があり、利用効率といった面からの最適な経路での迂回が困難である。このため、ネットワークの一部にしか適用しないか、もしくは物理的なトポロジをＦＲＲで迂回経路の設定し易い形態に限定しなければならない。
【０００６】
また、リンクの利用率からパケットロスによる障害が予測された場合には、運用者の操作によって、その障害が予測されたリンク上の起点となるノードからの迂回経路を確立する必要があり、この際に利用率の高いリンクを避けて経路を設定することも必要であり、運用上の手間がかかるという問題がある。
【０００７】
また、ＭＰＬＳでは、端末と直接的に通信するルータに故障が発生した場合、次候補の経路学習や、学習した経路をネットワーク全体に通知させてルーティングテーブルの更新を行う動作が必要となるため、迅速な迂回措置が困難である。特に、そのルータが異なる２つの端末と直接的に接続される二重帰属となっていた場合には、その学習には更に時間がかかることになる。
【０００８】
本発明は、上記に鑑みてなされたものであり、その目的とするところは、経路に障害が発生したときに、運用者の手間を煩わせることなく迅速な経路の迂回措置を可能にすることにある。
【課題を解決するための手段】
【０００９】
第１の本発明に係るデータ転送システムは、複数の転送装置に２進数のノードＩＤを割り振り、各転送装置と当該転送装置の自ノードＩＤにおける１つのビットを反転させたノードＩＤを持つ他の転送装置との間でリンクが形成されるハイパーキューブネットワークにより端末間でのデータ通信を中継するデータ転送システムであって、各転送装置は、各端末のアドレスと端末が接続されている転送装置のノードＩＤを示すテーブルを記憶しておく記憶手段と、使用を回避すべきリンクに関わる２つの転送装置のノードＩＤが反転するビットの桁数(次元数)を優先ビットとして記憶手段に記憶させておく優先ビット管理手段と、端末から直接的に宛先アドレスを含むデータを受信した場合に、その宛先アドレスの端末と直接的に通信する転送装置のノードＩＤを前記テーブルから抽出し、宛先ノードＩＤとしてデータに付与する付与手段と、他の転送装置から宛先ノードＩＤが付与されたデータを受信した場合に、その宛先ノードＩＤを取得して記憶手段に記憶させる取得手段と、自ノードＩＤと前記宛先ノードＩＤとの排他的論理和を演算し、その演算結果を記憶手段に記憶させる演算手段と、付与又は受信して得た前記宛先ノードＩＤが付与されたデータを、前記演算結果が１となる最も小さい桁が自ノードＩＤに対して反転しているノードＩＤをもつ転送装置に対して送信するか、前記優先ビットがある場合には前記演算結果が１となる桁のうち優先ビットに対応する桁が自ノードＩＤに対して反転しているノードＩＤをもつ転送装置に対して送信する送信手段と、を有することを特徴とする。
【００１０】
本発明にあっては、転送装置が端末から直接的に宛先アドレスを含むデータを受信した場合に、その宛先アドレスの端末と直接的に通信する転送装置のノードＩＤをテーブルから抽出し、宛先ノードＩＤとしてデータに付与することで、端末間の通信の中継に、自ノードＩＤと宛先ノードＩＤの排他的論理和演算によって転送先を決定するハイパーキューブネットワークを適用可能にする。
【００１１】
また、使用を回避すべきリンクの次元数を優先ビットとして設定しておき、データ転送時に優先ビットがある場合には、排他的論理和演算の結果が１となる桁のうち優先ビットに対応する桁が自ノードＩＤに対して反転しているノードＩＤをもつ転送装置に対してデータを転送することで、使用を回避すべきリンクを保持する転送装置にデータが転送される前に当該リンクの次元数にデータを送り、当該リンクを迂回した上で宛先の転送装置にデータを転送する。このように、転送先を自律的に変更することで、途中経路の設計・管理を行う必要がなく、運用者の手間を不要にすることができる。また、経路の学習が不要であり、障害のあるリンクを迅速に迂回することができる。ここで「使用を回避すべきリンク」とは、障害が発生したリンクの他、工事等を考慮して運用者が設定したリンクも含むものである。
【００１２】
第２の本発明に係るデータ転送方法は、複数の転送装置に２進数のノードＩＤを割り振り、各転送装置と当該転送装置の自ノードＩＤにおける１つのビットを反転させたノードＩＤを持つ他の転送装置との間でリンクが形成されるハイパーキューブネットワークにより端末間でのデータ通信を中継するデータ転送方法であって、各端末のアドレスと端末が接続されている転送装置のノードＩＤを示すテーブル、および使用を回避すべきリンクに関わる２つの転送装置のノードＩＤが反転するビットの桁数(次元数)を示す優先ビットを記憶手段に記憶した転送装置により、端末から直接的に宛先アドレスを含むデータを受信した場合に、その宛先アドレスの端末と直接的に通信する転送装置のノードＩＤを前記テーブルから抽出し、宛先ノードＩＤとしてデータに付与するステップと、他の転送装置から宛先ノードＩＤが付与されたデータを受信した場合に、その宛先ノードＩＤを取得して記憶手段に記憶させるステップと、自ノードＩＤと前記宛先ノードＩＤとの排他的論理和を演算し、その演算結果を記憶手段に記憶させるステップと、付与又は受信して得た前記宛先ノードＩＤが付与されたデータを、前記演算結果が１となる最も小さい桁が自ノードＩＤに対して反転しているノードＩＤをもつ転送装置に対して送信するか、前記優先ビットがある場合には前記演算結果が１となる桁のうち優先ビットに対応する桁が自ノードＩＤに対して反転しているノードＩＤをもつ転送装置に対して送信するステップと、を有することを特徴とする。
【００１３】
第３の本発明に係る転送装置は、複数の転送装置に２進数のノードＩＤを割り振り、各転送装置と当該転送装置の自ノードＩＤにおける１つのビットを反転させたノードＩＤを持つ他の転送装置との間でリンクが形成されるハイパーキューブネットワークにより端末間でのデータ通信を中継するデータ転送システムに用いられる転送装置であって、各端末のアドレスと端末が接続されている転送装置のノードＩＤを示すテーブルを記憶しておく記憶手段と、使用を回避すべきリンクに関わる２つの転送装置のノードＩＤが反転するビットの桁数(次元数)を優先ビットとして記憶手段に記憶させておく優先ビット管理手段と、端末から直接的に宛先アドレスを含むデータを受信した場合に、その宛先アドレスの端末と直接的に通信する転送装置のノードＩＤを前記テーブルから抽出し、宛先ノードＩＤとしてデータに付与する付与手段と、他の転送装置から宛先ノードＩＤが付与されたデータを受信した場合に、その宛先ノードＩＤを取得して記憶手段に記憶させる取得手段と、自ノードＩＤと前記宛先ノードＩＤとの排他的論理和を演算し、その演算結果を記憶手段に記憶させる演算手段と、付与又は受信して得た前記宛先ノードＩＤが付与されたデータを、前記演算結果が１となる最も小さい桁が自ノードＩＤに対して反転しているノードＩＤをもつ転送装置に対して送信するか、前記優先ビットがある場合には前記演算結果が１となる桁のうち優先ビットに対応する桁が自ノードＩＤに対して反転しているノードＩＤをもつ転送装置に対して送信する送信手段と、を有することを特徴とする。
【００１４】
上記転送装置は、直接接続されているリンクにおける障害の発生を検知して当該リンクの次元数を記憶手段に記憶させる検知手段と、他の転送装置から障害が発生したリンクの次元数を含むデータを受信し、当該リンクの次元数を記憶手段に記憶させる受信手段と、検知又は受信して得た前記リンクの次元数を、経由したリンクの数を示すホップ数より大きい次元数のうち障害が発生したリンクの次元数およびデータを受信したリンクの次元数を除いた次元数に対応する桁が自ノードＩＤに対して反転しているノードＩＤをもつ転送装置に対して送信する送信手段と、を有し、前記優先ビット管理手段は、受信して得た前記リンクの次元数を優先ビットとして記憶手段に記憶させることを特徴とする。
【００１５】
本発明にあっては、障害が発生したリンクの次元数を他の転送装置に送信する際に、経由したリンクの数を示すホップ数より大きい次元数のうち障害が発生したリンクの次元数およびパケットを受信したリンクの次元数を除いた次元数に対応する桁が自ノードＩＤに対して反転しているノードＩＤをもつ転送装置に対して送信することで、１つの転送装置に対して重複してデータが送信されないようにして、ネットワークの効率的な利用を図る。
【００１６】
上記転送装置は、直接接続されているリンクにおける障害の発生を検知して当該リンクの次元数を記憶手段に記憶させる検知手段と、検知して得た前記リンクの次元数を、１ホップ先にだけ転送する旨と併せて隣接する転送装置に対して送信する送信手段と、他の転送装置から前記リンクの次元数および前記旨を含むデータを受信する受信手段と、前記旨を受信した場合には、以降のデータ転送を停止する手段と、を有し、前記優先ビット管理手段は、受信して得た前記リンクの次元数を優先ビットとして記憶手段に記憶させることを特徴とする。
【００１７】
本発明にあっては、障害が発生したリンクの次元数を他の転送装置に送信する際に、障害発生を検知した転送装置から１ホップ先の転送装置にだけ送信することで、全ての転送装置に送信した場合に比べてネットワークを効率的に利用することができる。
【００１８】
上記転送装置において、前記検知手段は、リンクの利用率を監視し、利用率が記憶手段に予め記憶している閾値を超えたときに当該リンクの次元数を記憶手段に記憶させることを特徴とする。
【００１９】
本発明にあっては、リンクの利用率が多くなるとパケットロスが生じ易くなることから、リンクの利用率が閾値を超えたときに障害が発生したときと同様に処理させることで、混んでいるリンクを自律的に迂回して転送でき、パケットロスの発生を抑え、ネットワークを効率的に利用することができる。
【００２０】
上記転送装置は、全ての次元数が優先ビットになったときに、自ノードＩＤに対して全てのビットが反転しているノードＩＤをもつ転送装置に障害が発生したと判断する判断手段と、障害発生と判断された転送装置のノードＩＤを他の転送装置に送信する送信手段と、障害発生と判断された転送装置のノードＩＤを他の転送装置から受信する受信手段と、判断又は受信して得た障害発生と判断された転送装置のノードＩＤを前記テーブルに反映させて抽出対象から除外する手段と、を有することを特徴とする。
【００２１】
本発明にあっては、全ての次元が優先ビットになった転送装置においては、自ノードＩＤに対して全てのビットが反転しているノードＩＤをもつ転送装置に障害が発生したと判断する。そして、その情報を各転送装置のテーブルに反映させて宛先ノードＩＤの抽出対象から除外することで、障害のある転送装置へはデータを転送しないようにして、ネットワークの効率的な利用を図る。
【００２２】
上記転送装置は、端末との間での直接的な接続／接続断を検知して当該端末のアドレスを前記テーブルに反映させる検知手段と、他の転送装置から接続／接続断を検知した転送装置のノードＩＤおよび検知された端末のアドレスを含むデータを受信して当該ノードＩＤおよび当該アドレスを前記テーブルに反映させる第２受信手段と、検知又は受信して得た接続／接続断を検知した転送装置のノードＩＤおよび検知された端末のアドレスを、経由したリンクの数を示すホップ数より大きい次元数のうちデータを受信したリンクの次元数を除いた次元数に対応する桁が自ノードＩＤに対して反転しているノードＩＤを持つ転送装置に対して送信する第２送信手段と、を有することを特徴とする。
【００２３】
本発明にあっては、端末との接続／接続断を検知した転送装置のノードＩＤおよび検知された端末のアドレスを各転送装置が通知し合ってそれぞれのテーブルに反映させることで、接続検知の場合にはデータ転送時にそのノードＩＤを宛先ノードＩＤとして抽出可能にするとともに、接続断検知の場合には抽出対象から除外してネットワークの効率的な利用を図る。
【００２４】
上記転送装置において、前記テーブルは、端末が異なる転送装置に２重に接続される場合に、いずれの転送装置を優先させるかを示す種別も記録するものであって、前記第２送信手段は、接続／接続断を検知した転送装置のノードＩＤおよび検知された端末のアドレスに加えて前記種別を送信し、前記第２受信手段は、当該ノードＩＤおよび当該アドレスに加えて当該種別を前記テーブルに反映させ、前記付与手段は、前記テーブルからの抽出対象となるノードＩＤのうち、優先の種別がある方のノードＩＤを宛先ノードＩＤとして採用することを特徴とする。
【００２５】
本発明にあっては、端末が異なる転送装置に２重に接続される２重帰属の場合に、優先の種別を各転送装置が通知し合ってそれぞれのテーブルに反映させ、データ転送時には優先種別がある方のノードＩＤを宛先ノードＩＤとして採用することで、適切なデータ転送を可能にする。
【発明の効果】
【００２６】
本発明によれば、経路に障害が発生したときに、運用者の手間を煩わせることなく迅速に経路迂回の措置を取ることができる。
【発明を実施するための最良の形態】
【００２７】
［基本構成］
図１は、一実施の形態におけるデータ転送システムの全体的な概略構成を示す図である。同図に示すように、本システムは、端末Ａ，Ｂ，Ｃ間のデータ通信をハイパーキューブネットワーク(ＨＣＮ)で中継するものである。図２(ａ)に示すように、ＨＣＮでは、複数のＨＣＮノードに２進数のノードＩＤをそれぞれ割り振り、各ＨＣＮノードと自ノードＩＤの１つのビットを反転させたノードＩＤを持つ他のＨＣＮノードとの間でリンクが形成される。図２(ａ)では、一例としてノードＩＤ(000)-(111)がそれぞれ割り振られた８個のＨＣＮノード１−８を示す。また、図２(ｂ)に示すように、各ＨＣＮノードは３次元のリンクを持つ。各ＨＣＮノードは、ＨＣＮ用に３つのポート１１，１２，１３を備え、これらのポートに他のＨＣＮノードが接続される。図２(ａ)では、ＨＣＮノード１のノードＩＤは(000)であり、１桁目(１次元目)のビットを反転させた(001)のノードＩＤを持つＨＣＮノード２がポート１１に接続され、２桁目(２次元目)のビットを反転させた(010)のノードＩＤを持つＨＣＮノード３がポート１２に接続され、３桁目(３次元目)のビットを反転させた(100)のノードＩＤを持つＨＣＮノード４がポート１３に接続される。他のＨＣＮノードについても同様である。
【００２８】
そして、図１に示すように、ＨＣＮノード１，５，８は、端末用にポート１，２を備える。ＨＣＮノード１にはアドレスａを持つ端末Ａがポート１を通じた外部リンクによって接続され、ＨＣＮノード５にはアドレスｂを持つ端末Ｂがポート２を通じた外部リンクによって接続されると共にアドレスｃを持つ端末Ｃがポート１を通じた外部リンクによって接続され、ＨＣＮノード８にはアドレスｂを持つ端末Ｂがポート１を通じた外部リンクによって接続される。端末Ｂは、ＨＣＮノード５よりもＨＣＮノード８との通信を優先する。このように１つの端末が異なる２つのＨＣＮノードに帰属することを２重帰属と呼び、優先的に利用する外部リンクをプライマリ(Primary)、優先しない方をバックアップ(Backup)と呼ぶものとする。
【００２９】
ここで、端末とは、ＨＣＮ外のアドレス(例えばＩＰアドレス)を持つ装置のことをいい、サーバ、ルータが相当する。ＨＣＮノードは、本願の転送装置であり、ＨＣＮを構成するルータや伝送装置に相当する。ＨＣＮリンクは、ＨＣＮノード同士を接続するリンクである。外部リンクは、端末とＨＣＮノードを接続するリンクである。
【００３０】
次に、本実施形態で適用するＨＣＮにおける経路決定手順について図３を用いて説明する。各ＨＣＮノードでは、自ノードＩＤと宛先ノードＩＤとの排他的論理和を演算し、その演算結果が１となる最も小さい桁数に対応するリンクへデータを転送する。
【００３１】
ここでは、ノードＩＤ(000)のＨＣＮノード１からノードＩＤ(111)のＨＣＮノード８へデータを転送する例で説明する。まず、ＨＣＮノード１では、宛先ノードＩＤ(111)と自ノードＩＤ(000)との排他的論理和は(111)となり、演算結果が１となる最も小さい桁数は１桁目であるので、1次元目のリンクへデータを転送する。これを受けたＨＣＮノード２では、宛先ノードＩＤ(111)と自ノードＩＤ(001)の排他的論理和は(110)となり、演算結果が１となる最も小さい桁数は２桁目であるので、２次元目のリンクへデータを転送する。これを受けたＨＣＮノード５では、宛先ノードＩＤ(111)と自ノードＩＤ(011)の排他的論理和は(100)となり、演算結果が１となる最も小さい桁数は３桁目であるので、３次元目のリンクへデータを転送する。この結果、データはＨＣＮノード８に転送される。
【００３２】
本システムは、上記ＨＣＮの適用に際し、リンクの故障発生時に、それを検知したＨＣＮノードから他のＨＣＮノードに通信不能の次元を通知し、その通知を受信したＨＣＮノードがデータ転送を行う際には、障害のあるリンクを保持するＨＣＮノードにデータが転送される前に当該リンクの次元数に優先的にデータを転送することで、最短経路を担保できるようにしたものである。
【００３３】
続いて、ＨＣＮノード(転送装置)の内部構成について図４を用いて説明する。同図に示すように、ＨＣＮノードは、外部転送テーブル１、ＨＣＮ転送テーブル２、ＨＣＮリンク管理テーブル３、優先ビット４、オペレーションシステム(ＯｐＳ)ＩＦ部５、リンク状態検知部６、外部パケット受信部７、ＨＣＮ側送信部８、ＨＣＮ側受信部９、外部パケット送信部１０、ノード制御部１１、複数の受信ポート及び送信ポートを有する。外部転送テーブル１、ＨＣＮ転送テーブル２、ＨＣＮリンク管理テーブル３、優先ビット４はＨＤＤ，メモリ等の記憶装置に読み出し可能に記憶される。また、各部において処理された結果も記憶装置に読み出し可能に記憶される。各テーブルの構成及び各部の概略的な機能は次の通りである。
【００３４】
外部転送テーブル１は、ＨＣＮ外の端末が接続される自ＨＣＮノードのポート番号と、その通信状態(通信可能はUp，通信不能はDown)を記録したものである。外部転送テーブル１は、ＨＣＮノードが端末へパケットを送信する際に、どのポートへ転送するかを判断するために利用される。図５に、ＨＣＮノード１が保持する外部転送テーブルの例を示す。この外部転送テーブルでは、ポート番号、端末のアドレス、通信状態が関連付けられている。♯はコメント行を示す。
【００３５】
ＨＣＮ転送テーブル２は、各ＨＣＮノードにどの端末が属しているかを記録したものである。各ＨＣＮノードがパケットを受信した際に、宛先端末に接続されているＨＣＮノードのノードＩＤ(宛先ノードＩＤ)を検索するために利用される。図６に、ＨＣＮノード１が保持するＨＣＮ転送テーブルの例を示す。このＨＣＮ転送テーブルでは、ＨＣＮノードＩＤ、端末のアドレス、２重帰属時のPrimary/Backupの種別が関連付けられている。  
ＨＣＮリンク管理テーブル３は、自身のポートに接続されているリンクが、ＨＣＮのどの次元に対応しているかということと、その通信状態(Up/Down)を記録したものである。図７にＨＣＮノード１が保持するＨＣＮリンク管理テーブルの例を示す。このＨＣＮリンク管理テーブルでは、ポート番号、次元数、通信状態が関連付けられている。
【００３６】
優先ビット４は、いずれかのリンクに障害が発生した場合に、排他的論理和の演算結果で１となったビットのうち、どのビットを優先させるかを記録したものである。本実施形態のように３次元のＨＣＮを対象とする場合には３ビットで表される。優先ビット４は、ＨＣＮ内でいずれかのリンクに障害が発生したことが通知されたときに変更される。また、ＯｐＳ等からのコマンド入力によっても変更可能である。
【００３７】
ＯｐＳＩＦ部５は、オペレーションシステムとデータや制御コマンド等の情報のやり取りを行う。
【００３８】
リンク状態検知部６は、当該ＨＣＮノードが利用しているリンクの状態を監視し、障害の発生を検知する。ケーブルの接続／撤去、通信断、バッファ溢れによるパケットロス等を検知した場合にはＨＣＮ側送信部８へ処理を移す。また、外部端末の接続／接続断を検知した場合には外部転送テーブル１の更新を行う。通信断の判断は、常に監視用のパケット若しくは信号を隣接のＨＣＮノードと送受信しあい、送受信の状態が予め設定された判定基準を超えた場合に通信断とみなす。判定基準としては、例えば監視用パケットが連続していくつロスしたか、或いはどれだけの期間に渡って監視用信号を確認できなかったか等を用いる。これらの設定値は設定情報として記憶装置に記憶しておき、ノード制御部１１により読み書きを管理する。また、リンク利用率の閾値についても設定情報として記憶しておき、単位時間当たりのデータ転送量から算出した実際のリンク利用率と閾値とを比較し、リンク利用率が閾値を超えた場合には、そのリンクの次元数を記憶装置に記憶させる。
【００３９】
外部パケット受信部７は、ＨＣＮ経由判定部７１により、ＨＣＮ外の端末から送られてきたパケットを受信し、その受信パケットに含まれている宛先端末のアドレス(宛先アドレス)を元に、ＨＣＮ転送テーブル２を参照して、宛先端末が接続されているＨＣＮノードの宛先ノードＩＤを取得する。そして、ラベル付与部７２により、宛先ノードＩＤをＨＣＮラベルとして受信パケットに付与した上でＨＣＮ側送信部８へ処理を移す。この動作によって、端末間の既存の通信ネットワークに対してＨＣＮを適用することが可能となる。また、ＨＣＮ転送テーブル２に宛先アドレスの記録がない場合には、外部パケット送信部１０に対してエラーメッセージ送信の指示を行う。
【００４０】
ＨＣＮラベルは、図８に示すように、データ部に付与されるものであり、制御ビット、制御データ、宛先ノードＩＤから構成される。制御ビットは、通常のデータ転送、リンクに障害が発生したときにこれを１ホップ先のＨＣＮノードに通知するアラーム転送、リンクに障害が発生したときにこれを全てのノードに通知する広告といった３種の通信モードを識別するために利用される。データ部は、外部端末から受信したパケットそのものであり、送信元端末のアドレス、宛先端末のアドレス、送信元端末が送信したデータが含まれる。また、データ部には、アラーム転送時又は広告時には制御用のデータが格納される。
【００４１】
制御ビットの値の例は次の通りである。
【００４２】
(0000)：通常のデータ通信
(0001)：アラーム転送
(0010)：広告
制御データには、広告を行う際にＨＣＮの次元数、ホップ数を格納する。次元数は本実施形態では３である。ホップ数は、経由したリンクの数である。制御データのフォーマットを図９に例示する。また、アラーム転送時又は広告時のデータ部を図１０に例示する。
【００４３】
ＨＣＮ側送信部８は、他のＨＣＮノードに対してパケットを転送するものであり、広告送信部８１、アラーム転送部８２、優先ビット管理部８３、エラー送信部８４、ＸＯＲ計算部８５、送信リンク決定部８６を有する。ＸＯＲ計算部８５により、宛先ノードＩＤと自ノードＩＤとの排他的論理和(ＸＯＲ)を演算する。送信リンク決定部８６により、優先ビットのビット列を参照して優先すべき転送次元があるか否かを判定し、あった場合には該当する次元に対応するリンクをデータ転送先として決定する。優先すべき転送次元がない場合や複数の優先転送先があった場合には、排他的論理和演算の結果が１となったビットのうち最小の桁のビットに対応するリンクをデータ転送先として決定する。優先するリンクの状態がDownの場合は次候補を検索する。
【００４４】
送信リンク決定部８６の具体的な処理について次に説明する。ここでは優先ビットを次のように定める。
【００４５】
(000)：リンクに障害が発生していないときに使用されるものであり、最小ビットを優先させる。
【００４６】
(010)：２次元のリンクがいずれかのＨＣＮノードで不能となっている場合に使用されるものであり、２ビット目を優先させる。
【００４７】
(100)：３次元目のリンクがいずれかのＨＣＮノードで不能となっている場合に使用されるものであり、３ビット目を優先させる。
【００４８】
(011)：１，２次元目のリンクがいずれかのＨＣＮノードで不可能となっている場合に使用されるものであり、１ビット目、２ビット目の順で優先させる。
【００４９】
例えば、ＸＯＲ計算部８５の計算結果が(011)となった場合、１次元目と２次元目のどちらに対応するリンクを転送先としても良いところであるが、送信リンク決定部８６は次のように動作する。
【００５０】
(000)の優先ビットでは、優先的に転送する次元がないため、最小次元の１次元目のリンクを転送先に決定する。但し、ＨＣＮリンク管理テーブル３を参照して１次元目のリンク状態がDownの場合は２次元目のリンクを転送先とする。
【００５１】
(010)の優先ビットでは、２次元目のリンクを転送先に決定する。但し、ＨＣＮリンク管理テーブル３を参照して２次元目のリンク状態がDownの場合は１次元目のリンクを転送先に決定する。また、２，１次元目のリンク状態が共にDownの場合には転送が可能な３次元目のリンクを転送先に決定する。
【００５２】
(100)の優先ビットでは、３次元目を優先させるところであるが、ＸＯＲの演算結果から３次元目のリンクへの転送は不要と判断できるので、３次元目への優先的な転送は行わず、最小次元である１次元目のリンクを転送先に決定する。
【００５３】
(011)の優先ビットでは、通信状態がUpとなっている転送可能な最小次元のリンク(１次元目)を転送先に決定する。
【００５４】
広告送信部８１に処理がきた場合には、障害発生を他のＨＣＮノードに通知するために、制御ビットを(0010)に設定した上で、障害が発生したリンクの次元数を、ホップ数より大きい次元数のうち障害が発生したリンクの次元数およびパケットを受信したリンクの次元数を除いた次元数に対応する桁が自ノードＩＤに対して反転しているノードＩＤを持つ転送装置に対して送信する。ホップ数がＨＣＮ次元数に到達している場合には転送処理を終了する。
【００５５】
また、優先ビットが(111)となった場合は、自ノードＩＤのビット列が全て反転しているノードＩＤをもつＨＣＮノードに障害が発生したと判断し、ＨＣＮ転送テーブル２から該当するノードの情報を削除すると共に、障害が発生したＨＣＮノードのＩＤ等をデータに付加して広告送信を行う。
【００５６】
アラーム転送部８２に処理がきた場合には、基本的には広告送信部８１と同様の処理を行うが、制御ビットを(0001)に設定し、データ転送が１ホップ先で止まるように処理する。
【００５７】
優先ビット管理部８３に処理がきた場合には、広告時又はアラーム転送時においてデータ部に保持されている通信不可の次元を取得し、当該次元数を優先ビットに設定する。例えば、優先ビットが(000)の状態で、２次元目へのシフトが不可であるというアラームを受信した場合には、優先ビットを(010)に変更する。
【００５８】
ＨＣＮ側受信部９は、制御ビット判断部９１と宛先判定部９２を有する。ＨＣＮ側受信部９は、他のＨＣＮノードから転送されてきたパケットを受信し、制御ビット判断部９１により、制御ビットの値から通常のデータ転送、広告、アラーム転送のいずれであるかを判断し、次に行う処理を決定する。宛先判定部９２は、受信したパケットに含まれる宛先ノードＩＤから宛先となるＨＣＮノードのノードＩＤを判定する。
【００５９】
通常のデータ転送の場合は、宛先ノードＩＤが自ノードＩＤのときは外部パケット送信部１０へ処理を移す。宛先ノードＩＤが自ノードＩＤでないときはＨＣＮ側送信部８へ処理を移す。
【００６０】
広告の場合は、ＨＣＮ側送信部８の広告送信部８１へ処理を移す。そして、データ部を解析し、その情報に応じて次の動作を行う。外部リンクのUp/Downの変化を通知するものである場合には、その情報を外部転送テーブル１、ＨＣＮ転送テーブル２に反映させる。ＨＣＮ内でのリンク断の場合には、アラーム転送部８２へ処理を移す。ＨＣＮ内でのノード断の場合には、ＨＣＮ転送テーブル２から該当する断ノードの情報を削除する。
【００６１】
ＨＣＮアラーム転送の場合は、優先ビット管理部８３へ処理を移す。
【００６２】
外部パケット送信部１０は、ラベル削除部１０１により、受信したパケットからＨＣＮラベルを削除した後、送信リンク決定部１０２により、データ部から端末の宛先アドレスを取得し、外部転送テーブル１を参照して転送先ポートを決定し、宛先アドレスへ向けてＨＣＮ外へパケットを転送する。また、外部パケット受信部７からのエラーメッセージ送信の指示を受けた場合は、エラー送信部１０３により、端末に対してエラーメッセージの送信を行う。
【００６３】
ノード制御部１１は、ＯｐＳからのコマンド受付や、各種テーブルの更新、閾値やＨＣＮ内リンク断検知時に広告するか、アラーム転送するかといった設定情報等、ノードの制御に必要な情報を管理する。なお、設定情報は運用者が設定を行うこともある。
【００６４】
［通常のデータ転送時の動作］
次に、本システムにおける通常のデータ転送時の動作について説明する。ここでは一例として、端末Ａが端末Ｂにデータを送信するケースで説明する。前提として、各ＨＣＮノードは、外部転送テーブル１、ＨＣＮ転送テーブル２、ＨＣＮリンク管理テーブル３が正しく構築されているものとする。また、障害等は発生しておらず優先すべきリンクは無い、すなわち優先ビットが(000)であるものとする。
【００６５】
<Ｓｔｅｐ１>：ＨＣＮノード１(起点ノード)では以下の処理を行う。
【００６６】
(１)外部パケット受信部７により、端末Ａからパケットを受信し、ＨＣＮ経由判定部７１により、受信したパケットの宛先アドレスｂを取得し、アドレスｂを元にＨＣＮ転送テーブル２を検索してアドレスｂの端末が接続されているＨＣＮノードのノードＩＤは(111)である事を判断し、ラベル付与部７２へ処理を移す。このとき、宛先の端末が２重帰属の時は２つのノードＩＤを取得できるが、プライマリ(Primary)の種別が付いているノードＩＤを優先する。
【００６７】
(２)ラベル付与部７２では、制御ビットとして通常データ送信を示す(0000)、制御データとして全て(0)、宛先ノードＩＤとして(111)を設定したＨＣＮラベルをパケットに付加し、ＨＣＮ側送信部８に処理を移す。
【００６８】
(３)ＨＣＮ側送信部８のＸＯＲ計算部８５では、宛先ノードＩＤ(111)と自ノードＩＤ(000)のＸＯＲ演算を行い、(111)の結果を得る。
【００６９】
(４)送信リンク決定部８６では、優先ビットを参照し、優先的に転送すべき次元が無く、ＸＯＲ演算で得られた結果が１となっている最下位の桁数が１である事から転送すべき先は１次元目に対応するリンクであると判断し、ＨＣＮリンク管理テーブル３から該当次元数のリンクが接続されているポートが11番である事を取得し、そこへパケットを送出する。これにより、ＨＣＮノード２へパケットが転送される。図１１にＨＣＮ内を流れるパケットの例を示す。
【００７０】
<Ｓｔｅｐ２>：ＨＣＮノード２(経由ノード)では以下の処理を行う。
【００７１】
(５)ＨＣＮ側受信部９により、パケットを受信し、そのＨＣＮラベルを解析する。制御ビット判断部９１により、ＨＣＮラベルから制御ビットを取得し、取得結果(0000)から通常のデータ転送と判断し、宛先判定部９２により、宛先ノードＩＤ(111)を取得する。宛先ノードＩＤが自身のノードＩＤではないため、処理をＨＣＮ側送信部８に移す。
【００７２】
(６)ＨＣＮ側送信部８では、ＸＯＲ計算部８５により、宛先ノードＩＤ(111)と自身のノードＩＤ(001)のXOR演算を行い、(110)の結果を得る。
【００７３】
(７)送信リンク決定部８６では、優先ビットを参照し、優先的に転送すべき次元が無く、ＸＯＲ演算で得られた結果で１となっている最下位の桁数が２である事から次に転送すべき先は２次元目に対応するリンクであると判断し、ＨＣＮリンク管理テーブル３から該当次元数のリンクが接続されているポートが１２番である事を取得し１２番ポートにパケットを送出する。これにより、ＨＣＮノード５にパケットが転送される。
【００７４】
ＨＣＮノード５においても同様の処理を行うことで、ＨＣＮノード８にパケットが転送される。
【００７５】
<Ｓｔｅｐ３>：ＨＣＮノード８(終点ノード)では以下の処理を行う。
【００７６】
(８)ＨＣＮ側受信部９により、パケットを受信し、そのＨＣＮラベルを解析する。制御ビット判断部９１により、ＨＣＮラベルから制御ビットを取得し、取得結果(0000)から通常のデータ転送と判断し、宛先判定部９２により、宛先ノードＩＤ(111)を取得する。宛先ノードＩＤが自身のノードＩＤに一致するので外部パケット送信部１０に処理を移す。
【００７７】
(９)外部パケット送信部１０では、ラベル削除部１０１によりパケットからＨＣＮラベルを削除する。送信リンク決定部１０２により、データ部から端末Ｂの宛先アドレスｂを取得し、外部転送テーブル１からアドレスｂがポート１に接続されていることを判断し、ポート１にパケットを送出する。以上の一連の処理により、端末Ａが送信したパケットがＨＣＮを経由して端末Ｂへ転送される。
【００７８】
［ＨＣＮ内にリンク障害が発生したときの広告動作］
ＨＣＮ内にリンク障害が発生した場合は、これをＨＣＮ内の全てのＨＣＮノードに通知する広告と、隣接するノードにだけ通知するアラーム転送の２つの動作がある。ここでは広告動作について、図１２に示すようにＨＣＮノード５と８の間にリンク障害が発生した場合を例に説明する。
【００７９】
広告は、全てのＨＣＮノードにリンク障害の発生を伝えるものであるが、１つのＨＣＮノードに重複して伝えることがないように、各ＨＣＮノードでは、ホップ数より大きい次元数のうち障害が発生したリンクの次元数およびパケットを受信したリンクの次元数を除いた次元数に対応する桁が自ノードＩＤに対して反転しているノードＩＤを持つ転送装置に対してパケットを送信する。ホップ数がＨＣＮ次元数に到達した場合には転送処理を終了する。具体的には次のように動作する。
【００８０】
<Ｓｔｅｐ１>：ＨＣＮノード５，８が３次元目のリンク障害を検知し、当該リンクの次元数をデータとして他のＨＣＮノードに対して広告する。
【００８１】
(１)ＨＣＮノード８の動作
リンク状態検知部６により、ＨＣＮノード５との間のリンクに障害発生を検知したときに、そのポート番号からＨＣＮリンク管理テーブル３を参照して断リンクの次元数(3)を把握すると共に、ＨＣＮノード５への通信状態をDownに変更する。そして、設定情報から広告を行う事を判断してＨＣＮ側送信部８の広告送信部８１へ処理を移す。図１３にＨＣＮリンク管理テーブルの変更状態を示す。
【００８２】
広告送信部８１では、制御ビットとして広告を示す(0010)、制御データとしてホップ数(1)、ＨＣＮ次元数(3)、データ数、総データ長、データとしてメッセージＩＤにリンク断転送を示す(0000)、自身のノードＩＤ(111)、障害が発生したリンクの次元数(3)をセットする。そして、ＨＣＮリンク管理テーブル３で通信状態がUpとなっているポート(1,2次元目)にパケットを送出する。これにより、ＨＣＮノード６，７に広告用のパケットが送信される。図１４にパケット、図１５にデータの具体例を示す。
【００８３】
(２)ＨＣＮノード５の動作
ＨＣＮノード８と同様の動作を行う。これにより、ＨＣＮノード２，３に広告用のパケットが送信される。
【００８４】
<Ｓｔｅｐ２>：ＨＣＮノード２，３，６，７は、広告されてきたパケットを受信し、パケットに含まれている障害発生リンクの次元数に基づいて優先ビットを変更する。ＨＣＮノード３，７は広告を続け、ＨＣＮノード２,６は次の転送先が無いため処理を終了する。
【００８５】
(３)ＨＣＮノード７の動作
ＨＣＮ側受信部９によりパケットを受信し、制御ビット判断部９１によりパケットに含まれる制御ビットから広告パケットであると判断し、広告送信部８１へ処理を移す。
【００８６】
広告送信部８１では、ＨＣＮラベルの制御データから、ホップ数(1)、ＨＣＮ次元数(3)を取得し、データ部から、ＨＣＮ内リンク断転送である事と、断したリンクの次元数(3次元目)を取得する。そして、ホップ数より大きい次元数(2,3次元目)のうち、断したリンクの次元数(3次元目)および広告パケットを受信したリンクの次元数(1次元目)を除く次元数に対応するリンクに対して、ホップ数を１増加させた上でパケットを転送する。ここでは２次元目のリンクが該当するため、２次元目のリンクに対応するＨＣＮノード４に転送する。
【００８７】
優先ビット管理部８３では、取得された断リンクの次元数(3)を優先するように優先ビットを(100)に変更する。図１６に優先ビットの変更状態を示す。
【００８８】
(４)ＨＣＮノード３の動作
基本的にＨＣＮノード７と同様に動作する。但し、転送先に該当する２次元目のリンクに対応するのはＨＣＮノード１であるので、ＨＣＮノード１に対してパケットを転送する。
【００８９】
(５)ＨＣＮノード６の動作
基本的にＨＣＮノード７と同様に動作する。但し、ホップ数より大きい次元数(2,3次元目)のうち、断したリンクの次元数(3次元目)および広告パケットを受信したリンクの次元数(2次元目)を除いた次元数に対応するリンクがないため、ここで広告処理を終了する。
【００９０】
(６)ＨＣＮノード２の動作
基本的にＨＣＮノード７と同様に動作する。但し、ホップ数より大きい次元数(2,3次元目)のうち、断したリンクの次元数(3次元目)および広告パケットを受信したリンクの次元数(2次元目)を除いた次元数に対応するリンクがないため、ここで広告処理を終了する。
【００９１】
<Ｓｔｅｐ３>：ＨＣＮノード１，４は、広告されてきたパケットを受信して優先ビットを変更し、次の転送先が無いため広告処理を終了する。
【００９２】
(７)ＨＣＮノード４の動作
ＨＣＮ側受信部９によりパケットを受信し、制御ビット判断部９１によりパケットに含まれる制御ビットから広告パケットであると判断し、広告送信部８１へ処理を移す。
【００９３】
広告送信部８１では、ＨＣＮラベルの制御データから、ホップ数(2)、ＨＣＮ次元数(3)を取得し、データ部から、ＨＣＮ内リンク断転送である事と、断したリンクの次元数(3次元目)を取得する。そして、ホップ数より大きい次元数(3次元目)のうち、断したリンクの次元数(3次元目)および広告パケットを受信したリンクの次元数(2次元目)を除く次元数に対応するリンクに対してパケットを転送しようとする。但し、該当するリンクが無いため、ここで広告処理を終了する。
【００９４】
優先ビット管理部８３では、取得された断リンクの次元数(3)を優先するように優先ビットを(100)に変更する。
【００９５】
(８)ＨＣＮノード１の動作
ＨＣＮノード４と同様の動作を行う。
【００９６】
［広告後のデータ転送時の動作］
次に、広告後の通常のデータ転送時の動作について図１７を用いて説明する。
【００９７】
<Ｓｔｅｐ１>：ＨＣＮノード１が、端末Ａからデータを受信し、受信したデータに含まれている宛先アドレスｂを元にＨＣＮ転送テーブル２を検索して宛先ノードＩＤ(111)を取得し、この宛先ノードＩＤを含むＨＣＮラベルをデータに付与する。
【００９８】
<Ｓｔｅｐ２>：ＨＣＮノード１は、自身のノードＩＤ(000)と宛先ノードＩＤ(111)のＸＯＲ演算を行い、演算結果(111)を得る。
【００９９】
<Ｓｔｅｐ３>：ＨＣＮノード１は、優先ビット(100)を参照し、３次元目が優先であると判断し、３次元目のリンクに対応するＨＣＮノード４へデータを送信する。
【０１００】
<Ｓｔｅｐ４>：ＨＣＮノード４は、自身のノードＩＤ(100)と宛先ノードＩＤ(111)のＸＯＲ演算を行い、演算結果(011)を得る。
【０１０１】
<Ｓｔｅｐ５>：ＨＣＮノード４は、優先ビットを参照し、３次元目が優先だが、ＸＯＲ演算の結果から３次元目への転送は不要なため、演算結果が１となっている最小の桁に対応する１次元目のリンクを転送先に決定し、１次元目のリンクに対応するＨＣＮノード６へデータを転送する。
【０１０２】
<Ｓｔｅｐ６>：ＨＣＮノード６は、自身のノードＩＤ(101)と宛先ノードＩＤ(111)のＸＯＲ演算を行い、演算結果(010)を得る。
【０１０３】
<Ｓｔｅｐ７>：ＨＣＮノード６は、優先ビットを参照し、３次元目が優先だが、ＸＯＲの結果から３次元目への転送は不要なため、２次元目のリンクに対応するＨＣＮノード８へデータを転送する。
【０１０４】
<Ｓｔｅｐ８>：ＨＣＮノード８は、自身のノードＩＤ(111)が宛先ノードＩＤ(111)に一致するのでデータからＨＣＮラベルを削除し、外部転送テーブル１を参照して宛先アドレスｂに対応する外部リンクを決定して、データを端末Ｂへ送信する。
【０１０５】
以上の処理により、ＨＣＮノード５，８間の障害が発生したリンクを回避した最短経路を通じて端末間でデータが送受信される。
【０１０６】
［ＨＣＮ内にリンク障害が発生したときのアラーム転送動作］
次に、ＨＣＮ内にリンク障害が発生したときのアラーム転送の動作について説明する。図１８に示すように、ＨＣＮノード５，８間のリンクに障害が発生したことをＨＣＮノード５，８がそれぞれ検知すると、ＨＣＮノード５は、その旨を示すデータを隣接するＨＣＮノード２，３に転送し、ＨＣＮノード８は、隣接するＨＣＮノード６，７に転送する。それ以上のデータ転送は行わない。このように１ホップ先のＨＣＮノードにだけ転送することで、ネットワーク負荷の軽減を図る。具体的な処理は次の通りである。
【０１０７】
<Ｓｔｅｐ１>：ＨＣＮノード５，８がリンク断を検知し、該当リンクの次元数をデータとしてＨＣＮ内にアラーム転送する。
【０１０８】
(１)ＨＣＮノード８の動作
リンク状態検知部６により、ＨＣＮノード５との間のリンクに関して障害の発生を検知し、そのポート番号からＨＣＮリンク管理テーブル３を参照して断リンクの次元数(3)を把握し、通信状態をDownに変更する。そして、設定情報からアラーム転送を行う事を判断してＨＣＮ側送信部８のアラーム転送部８２へ処理を移す。
【０１０９】
アラーム転送部８２では、制御ビットとしてアラーム転送を示す(0001)、制御データとして全て(0)、データ数、総データ長、データとしてメッセージＩＤにリンク断転送を示す(0001)、自身のノードＩＤ(111)、障害が発生したリンクの次元数(3)をセットする。そして、ＨＣＮリンク管理テーブル３で状態がUpとなっているポート(1,2次元目)にパケットを送出する。これにより、ＨＣＮノード６，７にアラーム転送用のパケットが送信される。  (２)ＨＣＮノード５の動作
ＨＣＮノード８と同様の動作を行う。これにより、ＨＣＮノード２，３にアラーム転送用のパケットが送信される。
【０１１０】
<Ｓｔｅｐ２>：ＨＣＮノード２，３，６，７は転送されてきたパケットを受信し、優先ビットを変更する。ＨＣＮ内アラーム転送であるため転送はそれ以上行わない。
【０１１１】
(３)ＨＣＮノード２，６の動作
ＨＣＮ側受信部９によりパケットを受信し、制御ビット判断部９１により制御ビットからアラーム転送パケットであると判断し、アラーム転送部８２へ処理を移す。
【０１１２】
アラーム転送部８２では、データ部から、ＨＣＮ内リンク断転送である事と、断したリンクの次元数(3次元目)を取得する。そして、優先ビット管理部８３により、取得された断リンクの次元数(3)を優先するように優先ビットを(100)に変更する。ＨＣＮ内のアラーム転送であるため、これ以上の転送は行わない。
【０１１３】
(４)ＨＣＮノード３，７の動作
ＨＣＮノード２，６と同様の動作を行う。
【０１１４】
［アラーム転送後のデータ転送時の動作］
次に、アラーム転送後の通常のデータ転送時の動作について図１９を用いて説明する。
【０１１５】
<Ｓｔｅｐ１>：ＨＣＮノード１が、端末Ａからデータを受信し、受信したデータに含まれている宛先アドレスｂを元にＨＣＮ転送テーブル２を検索して宛先ノードＩＤ(111)を取得し、この宛先ノードＩＤを含むＨＣＮラベルをデータに付与する。
【０１１６】
<Ｓｔｅｐ２>：ＨＣＮノード１は、自身のノードＩＤ(000)と宛先ノードＩＤ(111)のＸＯＲ演算を行い、演算結果(111)を得る。
【０１１７】
<Ｓｔｅｐ３>：ＨＣＮノード１は、優先ビット(000)を参照し、優先させるリンクがないことから、演算結果に１が立っているビットのうち最小の桁に対応する１次元目のリンクを送信先に決定し、１次元目リンクに対応するＨＣＮノード２へデータを送信する。
【０１１８】
<Ｓｔｅｐ４>：ＨＣＮノード２は、自身のノードＩＤ(001)と宛先ノードＩＤ(111)のＸＯＲ演算を行い、演算結果(110)を得る。
【０１１９】
<Ｓｔｅｐ５>：ＨＣＮノード２は、優先ビット(100)を参照し、３次元目が優先であるため、３次元目のリンクに対応するＨＣＮノード６へデータを転送する。
【０１２０】
<Ｓｔｅｐ６>：ＨＣＮノード６は、自身のノードＩＤ(101)と宛先ノードＩＤ(111)のＸＯＲ演算を行い、演算結果(010)を得る。
【０１２１】
<Ｓｔｅｐ７>：ＨＣＮノード６は、優先ビット(100)を参照し、３次元目が優先だが、ＸＯＲの結果から３次元目への転送は不要なため、演算結果に基づいて２次元目のリンクに対応するＨＣＮノード８へデータを転送する。
【０１２２】
<Ｓｔｅｐ８>：ＨＣＮノード８は、自身のノードＩＤ(111)と宛先ノードＩＤ(111)が一致するのでデータからＨＣＮラベルを削除し、外部転送テーブル１を参照して宛先アドレスｂに対応する外部リンクを決定して、データを端末Ｂへ送信する。
【０１２３】
以上の処理により、ＨＣＮノード５，８間の障害が発生したリンクを回避した最短経路を通じて端末間でデータが送受信される。
【０１２４】
［ＨＣＮノード断が発生したときの動作］
次に、リンク障害のひとつとしてノード断、すなわちＨＣＮノード自体に障害が発生したときの動作について説明する。ここでは、各ノードについて優先ビット、ＨＣＮ転送テーブル、ＨＣＮリンク管理テーブルが、図２０に示す初期状態であるときに、図２１に示すようにＨＣＮノード８に障害が発生した場合を例に説明する。
【０１２５】
<Ｓｔｅｐ１>：ＨＣＮノード８とのリンク状態を監視するＨＣＮノード５，６，７がそれぞれリンク断を検知し、隣接するＨＣＮノードへ広告する。
【０１２６】
(１)ＨＣＮノード５は、３次元目のリンク断を検知し、ＨＣＮリンク管理テーブル３を３次元目がDownとなるように更新し、断検知の旨を示すパケットを隣接するＨＣＮノードに広告する。ＨＣＮノード２，３がこれを受信する。
【０１２７】
(２)ＨＣＮノード６は、２次元目リンク断を検知し、ＨＣＮリンク管理テーブル３を２次元目がDownとなるように更新し、断検知の旨を示すパケットを隣接するＨＣＮノードに広告する。ＨＣＮノード２，４がこれを受信する。
【０１２８】
(３)ＨＣＮノード７は、１次元目リンク断を検知し、ＨＣＮリンク管理テーブル３を１次元目がDownとなるように更新し、断検知の旨を示すパケットを隣接するＨＣＮノードに広告する。ＨＣＮノード３，４がこれを受信する。
【０１２９】
<Ｓｔｅｐ２>：ＨＣＮノード２，３，４は、優先ビットを変更する。
【０１３０】
(４)ＨＣＮノード２は、２，３次元目のリンク断が通知されるので、２，３次元目のリンクを優先するように優先ビットを変更する。
【０１３１】
(５)ＨＣＮノード３は、１，３次元目のリンク断が通知されるので、１，３次元目のリンクを優先するように優先ビットを変更する。
【０１３２】
(６)ＨＣＮノード４は、１，２次元目のリンク断が通知されるので、１，２次元目のリンクを優先するように優先ビットを変更する。
【０１３３】
<Ｓｔｅｐ３>：ＨＣＮノード３，４は広告を続け、ＨＣＮノード２は広告を終了する。
【０１３４】
(７)ＨＣＮノード３は、ＨＣＮノード５から受信したパケットについては、ホップ数より大きい次元数(2,3次元目)のうち、断したリンクの次元数(3次元目)および広告パケットを受信したリンクの次元数(1次元目)を除く次元数に対応するリンクに対してパケットを転送しようとする。ここでは２次元目のリンクが該当するので、２次元目のリンクに対応するＨＣＮノード１へ転送することで広告を続ける。
【０１３５】
また、ＨＣＮノード７から受信したパケットについても、ホップ数より大きい次元数(2,3次元目)のうち、断したリンクの次元数(1次元目)および広告パケットを受信したリンクの次元数(3次元目)を除く次元数は２次元目が該当するので、２次元目のリンクに対応するＨＣＮノード１へ転送することで広告を続ける。
【０１３６】
(８)ＨＣＮノード４は、ＨＣＮノード６から受信したパケットについては、ホップ数より大きい次元数(2,3次元目)のうち、断したリンクの次元数(2次元目)および広告パケットを受信したリンクの次元数(1次元目)を除く次元数に対応するリンクに対してパケットを転送しようとする。ここでは３次元目のリンクが該当するので、３次元目のリンクに対応するＨＣＮノード１へ転送することで広告を続ける。
【０１３７】
また、ＨＣＮノード７から受信したパケットについても、ホップ数より大きい次元数(2,3次元目)のうち、断したリンクの次元数(1次元目)および広告パケットを受信したリンクの次元数(2次元目)を除く次元数は３次元目が該当するので、３次元目のリンクに対応するＨＣＮノード１へ転送することで広告を続ける。
【０１３８】
(９)ＨＣＮノード２は、ＨＣＮノード５から受信したパケットについては、ホップ数より大きい次元数(2,3次元目)のうち、断したリンクの次元数(3次元目)および広告パケットを受信したリンクの次元数(2次元目)を除く次元数に対応するリンクに対してパケットを転送しようとする。ここでは該当するリンクがないので、転送を終了する。
【０１３９】
また、ＨＣＮノード６から受信したパケットについても、ホップ数より大きい次元数(2,3次元目)のうち、断したリンクの次元数(2次元目)および広告パケットを受信したリンクの次元数(3次元目)を除く次元数に該当するリンクがないので、転送を終了する。
【０１４０】
<Ｓｔｅｐ４>：ＨＣＮノード１は、優先ビットを変更すると共に、ＨＣＮノード８に障害が発生したことを判断し、これを広告する。
【０１４１】
(１０)ＨＣＮノード１は、１，２，３次元目のリンク断が通知されるので、１，２，３次元全てのリンクを優先するように優先ビットを変更する。このとき各ＨＣＮノードが保持する優先ビット、ＨＣＮ転送テーブル、ＨＣＮリンク管理テーブルの様子を図２２に示す。
【０１４２】
(１１)ＨＣＮノード１は、優先ビットが全て１になった事から、自ノードＩＤ(000)に対して全てのビットが反転しているノードＩＤ(111)をもつＨＣＮノード８に障害が発生したと判断する。そして、ＨＣＮノード１は、ノードＩＤ(111)のノード断を他のＨＣＮノードに広告する。広告を受信したＨＣＮノードは、ＨＣＮ転送テーブル２に断したＨＣＮノードを反映させる。このときの広告の様子を図２３に、各ＨＣＮノードが保持する優先ビット、ＨＣＮ転送テーブル、ＨＣＮリンク管理テーブルの様子を図２４に示す。
【０１４３】
［ＨＣＮノードが端末との接続／接続断を検知したときの動作］
次に、ＨＣＮノードが端末との接続(Up)又は接続断(Down)を検知したときの動作について説明する。ここでは、図２５に示すように、ＨＣＮノード８に端末Ｃ(アドレスｃ)が新たに接続された場合を例に説明する。
【０１４４】
接続を検知したＨＣＮノード８は、検知結果を外部転送テーブル１に反映させるとともに、その検知の旨を自身のノードＩＤ(111)、検知アドレスｃと併せて他のＨＣＮノードに対して広告する。広告メッセージを受け取ったＨＣＮノードは、ＨＣＮ転送テーブル２に、検知されたノードＩＤに関連付けて端末Ｃのアドレスｃを追加する。接続断を検知した場合も広告動作は同様であり、広告メッセージを受信したＨＣＮノードは、ＨＣＮ転送テーブル２から断検知されたアドレスを削除する。具体的な処理は次の通りである。
【０１４５】
<Ｓｔｅｐ１>：ＨＣＮノード８は、端末Ｃが自身に接続されたことを検知し、外部転送テーブル１を変更すると共に、他のＨＣＮノードに広告する。
【０１４６】
(１)ＨＣＮノード８の動作
リンク状態検知部６により、新たに端末Ｃがポートに接続されたことを検知する。そして、外部転送テーブル１に端末Ｃが接続されたポート番号(2)と端末Ｃのアドレス(ｃ)を追加し、ＨＣＮ側送信部８の広告送信部８１に処理を移す。
【０１４７】
広告送信部８１では、制御ビットとして広告を示す(0010)、制御データとしてホップ数(1)、ＨＣＮ次元数(3)、データ数、総データ長、データとしてメッセージＩＤに外部リンクUpを示す(0010)、自身のノードＩＤ(111)、検知したアドレス(ｃ)をセットする。そして、ＨＣＮリンク管理テーブル３で状態がUpとなっているポート(1,2,3次元目)にパケットを送出する。これにより、ＨＣＮノード５，６，７に広告用のパケットが送信される。
【０１４８】
<Ｓｔｅｐ２>：ＨＣＮノード５，６，７は、広告されてきたパケットを受信し、ＨＣＮ転送テーブル２を変更した後、広告を続ける。
【０１４９】
(２)ＨＣＮノード５の動作
ＨＣＮ側受信部９によりパケットを受信し、制御ビット判断部９１によりパケットに含まれる制御ビットから広告用のパケットであると判断し、広告送信部８１へ処理を移す。
【０１５０】
広告送信部８１では、ＨＣＮラベルの制御データからホップ数(1)、ＨＣＮ次元数(3)を取得し、データ部から外部リンクUpである事と、検知したＨＣＮノードのノードＩＤ(111)、検知されたアドレス(ｃ)を取得する。そして、ホップ数より大きい次元数(2,3次元目)のうち、広告パケットを受信したリンクの次元数(3次元目)を除く次元数に対応するリンクに対して、ホップ数を１増加させた上でパケットを転送しようとする。ここでは２次元目のリンクが該当するため、２次元目のリンクに対応するＨＣＮノード２に転送する。さらに、ＨＣＮ転送テーブル２に、ノードＩＤ(111)、アドレス(ｃ)を追加する。
【０１５１】
(３)ＨＣＮノード６の動作
基本的にＨＣＮノード５と同様に動作する。但し、ホップ数より大きい次元数(2,3次元目)のうち、広告パケットを受信したリンクの次元数(2次元目)を除く次元数に対応するリンクは３次元目が該当するので、３次元目のリンクに対応するＨＣＮノード２にパケットを転送する。
【０１５２】
(４)ＨＣＮノード７の動作
基本的にＨＣＮノード５と同様に動作する。但し、ホップ数より大きい次元数(2,3次元目)のうち、広告パケットを受信したリンクの次元数(1次元目)を除く次元数に対応するリンクは２，３次元目が該当するので、２次元目に対応するＨＣＮノード４および３次元目に対応するＨＣＮノード３に対してパケットを転送する。
【０１５３】
<Ｓｔｅｐ３>：ＨＣＮノード４は広告されてきたパケットをＨＣＮノード１へ転送し、ＨＣＮノード２，３は転送先がないので転送処理を終了する。
【０１５４】
(５)ＨＣＮノード４の動作
ＨＣＮ側受信部９によりパケットを受信し、制御ビット判断部９１によりパケットに含まれる制御ビットから広告用のパケットであると判断し、広告送信部８１へ処理を移す。
【０１５５】
広告送信部８１では、ＨＣＮラベルの制御データからホップ数(2)、ＨＣＮ次元数(3)を取得し、データ部から外部リンクUpである事と、検知したノードのノードＩＤ(111)、検知されたアドレス(ｃ)を取得する。そして、ホップ数より大きい次元数(3次元目)のうち、広告用パケットを受信したリンクの次元数(2次元目)を除く次元数に対応するリンクに対して、ホップ数を１増加させた上でパケットを転送しようとする。ここでは３次元目が該当するので、３次元目のリンクに対応するＨＣＮノード１へ転送する。さらに、ＨＣＮ転送テーブル２に、ノードＩＤ(111)、アドレス(ｃ)を追加する。
【０１５６】
(６)ＨＣＮノード２，３の動作
基本的にＨＣＮノード４と同様に動作する。但し、ＨＣＮノード２では、ホップ数より大きい次元数(3次元目)のうち、広告用パケットを受信したリンクの次元数(2,3次元目)を除く次元数に対応するリンクが無く、ＨＣＮノード３でも、ホップ数より大きい次元数(3次元目)のうち、広告用パケットを受信したリンクの次元数(1,3次元目)を除く次元数に対応するリンクが無いため転送処理は終了する。
【０１５７】
<Ｓｔｅｐ４>：ＨＣＮノード１も、基本的にＨＣＮノード４と同様に動作する。但し、広告パケットの転送先が無いため転送処理は終了する。
【０１５８】
以降、通常のデータ転送においては、端末から直接的にデータを受信したＨＣＮノードは、データの宛先がアドレスｃの場合にはＨＣＮ転送テーブル２を検索してアドレスｃの端末が接続されているのはＨＣＮノード８であることを判断し、ＨＣＮノード８のノードＩＤを宛先ノードＩＤとしたＨＣＮラベルをデータに付与した上で転送の処理を行う。
【０１５９】
［２重帰属した場合の広告動作］
次に、１つの端末が異なるＨＣＮノードに２重に帰属した場合の動作について説明する。２重帰属時には、一方のＨＣＮノードを優先(Primary)とし、他方のＨＣＮノードをバックアップ(Backup)に設定する。この際、端末が接続されているＨＣＮノードのＨＣＮ転送テーブルに対して運用者が(Primary/Backup)の種別を設定し、このＨＣＮノードが設定内容を他のＨＣＮノードに対して広告する。
【０１６０】
広告されたパケットを受信したＨＣＮノードは、受信した設定内容に基づいてＨＣＮ転送テーブル２を更新する。なお、端末とＨＣＮノードとを接続するリンクが断した場合も同様に広告を行い、広告されたパケットを受信したＨＣＮノードはＨＣＮ転送テーブル２から該当する設定情報を削除する。ここでは、図２６に示すように、ＨＣＮノード５，８に対して新たに端末Ｂが接続される場合を例に説明する。ＨＣＮノード８をPrimary、ＨＣＮノード５をBackupとする。図中、実線矢印はノード８から広告されるパケットを、点線矢印はノード５から広告されるパケットをそれぞれ示す。図２７は、各ＨＣＮノードにおける外部転送テーブル１、ＨＣＮ転送テーブル２の初期状態を示す図である。
【０１６１】
<Ｓｔｅｐ１>：ＨＣＮノード５，８は、それぞれが端末Ｂの接続を検知し、検知した端末Ｂのアドレスｂと(Primary/Backup)の種別を広告する。
【０１６２】
(１)ＨＣＮノード８の動作
リンク状態検知部６により、新たに端末Ｂが接続されたことを検知し、外部転送テーブル１に端末Ｂが接続されているポート番号(11)、端末Ｂのアドレス(ｂ)、接続状態(Up)を追加し、ＨＣＮ側送信部８の広告送信部８１へ処理を移す。
【０１６３】
広告送信部８１では、制御ビットとして広告を示す(0010)、制御データとしてホップ数(1)、ＨＣＮ次元数(3)、データ数、総データ長、データとしてメッセージＩＤに外部リンクUpを示す(0010)、自身のノードＩＤ(111)、検知した端末Ｂのアドレス(ｂ)、種別(Primary)をセットする。そして、ＨＣＮリンク管理テーブル３で状態がUpとなっているポート(1,2,3次元目)にパケットを送出する。これにより、ＨＣＮノード５，６，７に広告用のパケットが送信される。
【０１６４】
(２)ＨＣＮノード５の動作
基本的にＨＣＮノード８と同様に動作する。但し、データに格納する種別は(Backup)になる。ＨＣＮノード５からは、ＨＣＮノード２，３，８に広告用のパケットが送信される。
【０１６５】
<Ｓｔｅｐ２>：広告用パケットを受信した各ＨＣＮノードは、受信したデータに基づいてＨＣＮ転送テーブル２を更新し、広告を続ける。
【０１６６】
(３)ＨＣＮノード８の動作
ＨＣＮノード５から受信した広告用パケットのデータに基づいて、ＨＣＮ転送テーブル２にノードＩＤ(011)、アドレス(ｂ)、種別(Backup)を追加する。
【０１６７】
(４)ＨＣＮノード５の動作
ＨＣＮノード８から受信した広告用パケットのデータに基づいて、ＨＣＮ転送テーブル２にノードＩＤ(111)、アドレス(ｂ)、種別(Primary)を追加する。
【０１６８】
(５)ＨＣＮノード６の動作
ＨＣＮ側受信部９によりＨＣＮノード８から送られてきたパケットを受信し、制御ビット判断部９１によりパケットに含まれる制御ビットから広告パケットであると判断し、広告送信部８１へ処理を移す。
【０１６９】
広告送信部８１では、ＨＣＮラベルの制御データからホップ数(1)、ＨＣＮ次元数(3)を取得し、データ部から外部リンクUpである事と、検知したＨＣＮノードのノードＩＤ(111)、検知されたアドレス(ｂ)、種別(Primary)を取得する。そして、ホップ数より大きい次元数(2,3次元目)のうち、広告パケットを受信したリンクの次元数(2次元目)を除く次元数に対応するリンクに対して、ホップ数を１増加させた上でパケットを転送する。ここでは３次元目のリンクが該当するので、３次元目のリンクに対応するＨＣＮノード２に転送する。
【０１７０】
また、ＨＣＮ転送テーブル２に、ノードＩＤ(111)、アドレス(ｂ)、種別(Primary)を追加する。さらに、次に説明するようにＨＣＮノード２からも広告用パケットが送信されてくるので、そのデータに基づいてＨＣＮ転送テーブル２にノードＩＤ(011)、アドレス(ｂ)、種別(Backup)を追加する。図２８(ａ)にＨＣＮ転送テーブルが変更される様子を示す。
【０１７１】
(６)ＨＣＮノード２の動作
基本的にＨＣＮノード６と同様に動作する。但し、パケットはＨＣＮノード５から受信するので、受信したパケットからは、検知したＨＣＮノードのノードＩＤ(011)、検知されたアドレス(ｂ)、種別(Backup)を取得する。そして、ホップ数より大きい次元数(2,3次元目)のうち、広告パケットを受信したリンクの次元数(2次元目)を除く次元数に対応するのは３次元目のリンクであるので、３次元目のリンクに対応するＨＣＮノード６にパケットを転送する。
【０１７２】
また、ＨＣＮ転送テーブル２に、ノードＩＤ(011)、アドレス(ｂ)、種別(Backup)を追加する。さらに、ＨＣＮノード６からも広告用パケットが送信されてくるので、そのデータに基づいてＨＣＮ転送テーブル２にノードＩＤ(111)、アドレス(ｂ)、種別(Primary)を追加する。図２８(ｂ)にＨＣＮ転送テーブルが変更される様子を示す。
【０１７３】
(７)ＨＣＮノード３，７の動作
基本的にＨＣＮノード２，６と同様に動作する。この結果、ＨＣＮノード３は、ＨＣＮノード５から受信したパケットをＨＣＮノード１，７に転送し、ＨＣＮノード７は、ＨＣＮノード８から受信したパケットをＨＣＮノード３，４へ転送する。
【０１７４】
また、ＨＣＮノード３は、ＨＣＮノード５，７から受信したパケットのデータに基づいてＨＣＮ転送テーブルを変更し、ＨＣＮノード７は、ＨＣＮノード３，８から受信したパケットのデータに基づいてＨＣＮ転送テーブルを変更する。
【０１７５】
<Ｓｔｅｐ３>：ＨＣＮノード１，４は広告を行い、転送処理を終了する。
【０１７６】
(８)ＨＣＮノード１の動作
基本的にＨＣＮノード６と同様に動作する。すなわち、ＨＣＮノード３から受信した広告用パケットのデータに基づいてＨＣＮ転送テーブル２を変更し、ＨＣＮノード４への転送を行う。また、ＨＣＮノード４から受信した広告用パケットのデータに基づいてＨＣＮ転送テーブル２を変更し、転送先が無いことから広告処理を終了する。図２８(ｃ)にＨＣＮ転送テーブルが変更される様子を示す。
【０１７７】
(９)ＨＣＮノード４の動作
基本的にＨＣＮノード６と同様に動作する。すなわち、ＨＣＮノード７から受信した広告用パケットのデータに基づいてＨＣＮ転送テーブル２を変更し、ＨＣＮノード１への転送を行う。また、ＨＣＮノード１から受信した広告用パケットのデータに基づいてＨＣＮ転送テーブル２を変更し、転送先が無いことから広告処理を終了する。図２８(ｄ)にＨＣＮ転送テーブルが変更される様子を示す。以上の広告処理によって各ＨＣＮノードが保持することになるテーブルの最終状態を図２９に示す。
【０１７８】
［二重帰属時のデータ転送動作］
次に、二重帰属時の広告が終了した後の通常のデータ転送の動作について説明する。基本的には、先に説明した［通常のデータ転送時の動作］と同様であるが、端末Ａからデータを受信したＨＣＮノード１では、受信したパケットの宛先アドレスｂを元に対応する宛先ノードＩＤについてＨＣＮ転送テーブル２を検索する。このとき、アドレスｂの端末が接続されているＨＣＮノードのノードＩＤとしては(111)，(011)が該当するところ、プライマリ(Primary)の種別が付いている方の(111)を採用し、これを宛先ノードＩＤとする。これをＨＣＮラベルに含めてパケットに付与する、自ノードＩＤと宛先ノードＩＤのＸＯＲ演算を行う、優先ビットを参照して転送先を定める等、その後の処理は通常のデータ転送と同様に行う。
【０１７９】
以上説明したように、本実施の形態によれば、ＨＣＮノード(転送装置)１が、端末Ａから直接的に宛先アドレスを含むデータを受信した場合に、その宛先アドレスの端末Ｂと直接的に通信するＨＣＮノード８のノードＩＤをＨＣＮ転送テーブル２から抽出し、宛先ノードＩＤとしてデータに付与することで、端末間の通信の中継に、自ノードＩＤと宛先ノードＩＤの排他的論理和演算によって転送先を決定するハイパーキューブネットワークを適用することが可能になる。
【０１８０】
また、各ＨＣＮノードにおいて、障害が発生したリンクの次元数を優先ビットとして設定しておき、データ転送時に優先ビットがある場合には、排他的論理和演算の結果が１となる桁のうち優先ビットに対応する桁が自ノードＩＤに対して反転しているノードＩＤをもつＨＣＮノードに対してデータを転送することで、障害のあるリンクを保持するＨＣＮノードにデータが転送される前に当該リンクの次元数にデータを送り、障害のあるリンクを迂回した上で宛先のＨＣＮノードにデータを転送する。このように、転送先を自律的に変更することで、途中経路の設計・管理を行う必要がなく、運用者の手間を不要にすることができる。また、経路の学習が不要であり、障害のあるリンクを迅速に迂回することができる。
【０１８１】
本実施の形態によれば、障害が発生したリンクの次元数を他のＨＣＮノードに送信する際に、転送回数を示すホップ数より大きい次元数のうち障害が発生したリンクの次元数およびパケットを受信したリンクの次元数を除いた次元数に対応する桁が自ノードＩＤに対して反転しているノードＩＤを持つＨＣＮノードに対して送信することで、１つのＨＣＮノードに重複して送信されないようにして、ネットワークの効率的な利用を図ることができる。
【０１８２】
本実施の形態によれば、障害が発生したリンクの次元数を他のＨＣＮノードに送信する際に、障害発生を検知したＨＣＮノードから１ホップ先のＨＣＮノードにだけ送信することで、全てのＨＣＮノードに送信した場合に比べてネットワークを効率的に利用することができる。
【０１８３】
本実施の形態によれば、リンクの利用率が多くなるとパケットロスが生じ易くなることから、利用率が閾値を超えたときに障害が発生したときと同様に処理することで、混んでいるリンクを自律的に迂回してデータを転送でき、パケットロスの発生を抑え、ネットワークを効率的に利用することができる。
【０１８４】
本実施の形態によれば、優先ビットが(111)になったＨＣＮノード１において、自ノードＩＤに対して全てのビットが反転しているノードＩＤをもつＨＣＮノード８に障害が発生したと判断し、その情報を各ＨＣＮノードのＨＣＮ転送テーブル２に反映させて宛先ノードＩＤの抽出対象から除外することで、障害のあるＨＣＮノード８へのデータ転送処理を行わずに済むので、ネットワークを効率的に利用することができる。
【０１８５】
本実施の形態によれば、端末との接続／接続断を検知したＨＣＮノード８のノードＩＤおよび検知された端末Ｃのアドレスｃを各ＨＣＮノードが通知し合ってそれぞれのＨＣＮ転送テーブル２に反映させることで、接続検知の場合にはそのノードＩＤを転送先として抽出可能にするとともに、接続断検知の場合には抽出対象から除外してネットワークの効率的な利用を図ることができる。
【０１８６】
本実施の形態によれば、端末Ｂが異なるＨＣＮノード５，８に２重に帰属する場合に、ＨＣＮノード８を優先(Primary)とする種別を各ＨＣＮノードが通知し合ってＨＣＮ転送テーブル２に反映させ、データ転送時には優先種別があるＨＣＮノード８のノードＩＤを宛先ノードＩＤとして採用することで、適切なデータ転送を可能にできる。
【図面の簡単な説明】
【０１８７】
【図１】一実施形態におけるデータ転送システムの全体的な概略構成を示す図である。
【図２】同図(ａ)は上記システムに適用されるＨＣＮの構成を示す図であり、同図(ｂ)は各ＨＣＮノードが持つ３次元リンクを説明するための図である。
【図３】ＨＣＮにおける経路決定手順を説明するための図である。
【図４】ＨＣＮノードの内部構成を示すブロック図である。
【図５】外部転送テーブルを示す図である。
【図６】ＨＣＮ転送テーブルを示す図である。
【図７】ＨＣＮリンク管理テーブルを示す図である。
【図８】ＨＣＮラベルとデータ部からなるパケットの構成を示す図である。
【図９】同図(ａ)は制御データの構成を示す図であり、同図(ｂ)は制御データのフォーマットを示す図である。
【図１０】同図(ａ)は広告時又はアラーム転送時におけるデータ部の構成を示す図であり、同図(ｂ)はそのときのデータ部のフォーマットを示す図である。
【図１１】通常のデータ送信時に使用されるパケットの構成を示す図である。
【図１２】広告時のシステム全体の動作を説明するための図である。
【図１３】広告時にＨＣＮリンク管理テーブルが変更される様子を示す図である。
【図１４】広告時に使用されるパケットの構成を示す図である。
【図１５】広告時に使用されるデータの具体例を示す図である。
【図１６】広告時に優先ビットが変更される様子を示す図である。
【図１７】広告後のデータ転送時の動作を説明するための図である。
【図１８】アラーム転送時のシステム全体の動作を説明するための図である。
【図１９】アラーム転送後のデータ転送時の動作を説明するための図である。
【図２０】各ＨＣＮノードでの優先ビット、ＨＣＮ転送テーブル、ＨＣＮリンク管理テーブルの初期状態を示す図である。
【図２１】ＨＣＮノード断時の動作を説明するための図である。
【図２２】ＨＣＮノード断時の優先ビット、ＨＣＮ転送テーブル、ＨＣＮリンク管理テーブルの２回目の変更状態を示す図である。
【図２３】ＨＣＮノード断を検知したノードがその旨を広告するときの様子を示す図である。
【図２４】ＨＣＮノード断時の優先ビット、ＨＣＮ転送テーブル、ＨＣＮリンク管理テーブルの最終状態を示す図である。
【図２５】ＨＣＮノードが外部端末との接続／接続断を検知したときのシステム全体の動作を説明するための図である。
【図２６】端末が異なるＨＣＮノードに２重に帰属した場合のシステム全体の動作を説明するための図である。
【図２７】２重帰属時の各ＨＣＮノードにおけるＨＣＮ転送テーブル、外部転送テーブルの初期状態を示す図である。
【図２８】同図(ａ)は２重帰属の広告時にＨＣＮノード２でＨＣＮ転送テーブルが変更される様子を示す図であり、同図(ｂ)はＨＣＮノード６でＨＣＮ転送テーブルが変更される様子を示す図であり、同図(ｃ)は２重帰属の広告時にＨＣＮノード１でＨＣＮ転送テーブルが変更される様子を示す図であり、同図(ｄ)は２重帰属の広告時にＨＣＮノード４でＨＣＮ転送テーブルが変更される様子を示す図である。
【図２９】２重帰属広告後の各ＨＣＮノードが保持するテーブルを示す図である。
【符号の説明】
【０１８８】
１…外部転送テーブル
２…ＨＣＮ転送テーブル
３…ＨＣＮリンク管理テーブル
４…優先ビット
５…ＯｐＳＩＦ部
６…リンク状態検知部
７…外部パケット受信部
８…ＨＣＮ側送信部
９…ＨＣＮ側受信部
１０…外部パケット送信部
１１…ノード制御部
７１…ＨＣＮ経由判定部
７２…ラベル付与部
８１…広告送信部
８２…アラーム転送部
８３…優先ビット管理部
８４…エラー送信部
８５…ＸＯＲ計算部
８６…送信リンク決定部
９１…制御ビット判断部
９２…宛先判定部
１０１…ラベル削除部
１０２…送信リンク決定部
１０３…エラー送信部
【図１】
2008066843.tif 000003
【図２】
2008066843.tif 000004
【図３】
2008066843.tif 000005
【図４】
2008066843.tif 000006
【図５】
2008066843.tif 000007
【図６】
2008066843.tif 000008
【図７】
2008066843.tif 000009
【図８】
2008066843.tif 000010
【図９】
2008066843.tif 000011
【図１０】
2008066843.tif 000012
【図１１】
2008066843.tif 000013
【図１２】
2008066843.tif 000014
【図１３】
2008066843.tif 000015
【図１４】
2008066843.tif 000016
【図１５】
2008066843.tif 000017
【図１６】
2008066843.tif 000018
【図１７】
2008066843.tif 000019
【図１８】
2008066843.tif 000020
【図１９】
2008066843.tif 000021
【図２０】
2008066843.tif 000022
【図２１】
2008066843.tif 000023
【図２２】
2008066843.tif 000024
【図２３】
2008066843.tif 000025
【図２４】
2008066843.tif 000026
【図２５】
2008066843.tif 000027
【図２６】
2008066843.tif 000028
【図２７】
2008066843.tif 000029
【図２８】
2008066843.tif 000030
【図２９】
2008066843.tif 000031