ノード装置、ネットワークシステム、故障通知方法、およびコンピュータプログラム
【課題】 多数のノード装置が同時に故障した場合であってもネットワーク内での制御負荷集中を回避することを可能とする。
【解決手段】 ノード装置は、自ノード装置と同一のネットワークシステムに含まれるノード装置のうちの少なくとも２つのノード装置の故障を検出した際、他のノード装置に対して、故障中の前記各ノード装置についての故障通知を異なるタイミングで送信する送信タイミング調整部を備える。
【解決手段】 ノード装置は、自ノード装置と同一のネットワークシステムに含まれるノード装置のうちの少なくとも２つのノード装置の故障を検出した際、他のノード装置に対して、故障中の前記各ノード装置についての故障通知を異なるタイミングで送信する送信タイミング調整部を備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ノード装置、ネットワークシステム、故障通知方法、およびコンピュータプログラムに関する。
【背景技術】
【０００２】
ネットワークにおいて、あるノード（例えば、ルータ）に故障が発生した場合、それを検知したノードは、故障ノードについての故障通知を他のノードに送信する。故障通知を受け取った他のノードは、故障ノードを迂回する新しい経路を再計算する。他のノードは、最新経路情報に基づいて、通信を継続させることができる。
【０００３】
しかしながら、例えば、ワーム攻撃、設定ミス、バグなどの原因により、多数のノードに同時に故障が発生した場合、ネットワーク内に大量の故障通知が一斉に発生することとなる。すなわち、各ノードに大量の故障通知が同時に通知されることとなる。これにより、各ノードの制御負荷（迂回経路の計算負荷）が増大することが予想される。制御負荷が増すと、ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）の過負荷やメモリ容量の不足等の危険性が高まり、さらなるノードの故障（例えば、ルータのクラッシュやセッションのリセット）が誘発される虞がある。事実、近年、このような障害が頻繁に発生していることが報告されている。
【０００４】
制御負荷の集中を軽減するための技術の一例として、Ｒｏｕｔｅ Ｆｌａｐ Ｄａｍｐｉｎｇ（非特許文献１）という技術を挙げることができる。この技術は、経路変更や、故障と復旧を頻繁に繰り返すノードに対して、一定時間が経過するまではその経路もしくはノードについての故障通知を転送させないというペナルティを与える技術である。
【０００５】
また、特許文献１は、通信装置に対して実行された措置の記録を参照して措置を決定することで、同一装置に対する同一措置を回避し、システムの処理性能低下を抑える技術について記載する。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００４−２６０７２９号公報
【非特許文献】
【０００７】
【非特許文献１】Ｃ． Ｖｉｌｌａｍｉｚａｒ、Ｒ． Ｃｈａｎｄｒａ、 Ｇｏｖｉｎｄａｎ、「ＢＧＰ Ｒｏｕｔｅ Ｆｌａｐ Ｄａｍｐｉｎｇ」、１９９８年１１月、ＲＦＣ
【発明の概要】
【発明が解決しようとする課題】
【０００８】
非特許文献１記載の技術は、ある一つのノードにおける頻繁な故障と復旧による制御負荷集中に対しては有効であるかもしれないが、上述したような多数のノードの一斉故障により発生する制御負荷集中の軽減に対してはあまり効果がないと考えられる。
【０００９】
また、特許文献１の技術は、同一装置に対する重複措置の実行については効果があるかもしれない。しかしながら、上述した、ノードの一斉故障に伴う故障通知の大量発生は、あくまで同一装置に対する同一措置ではないので、特許文献１の技術では、この問題を解決することは困難である。
【００１０】
本発明は、多数のノード装置が同時に故障した場合であってもネットワーク内での制御負荷集中を回避することが可能な、ノード装置、ネットワークシステム、故障通知方法、およびコンピュータプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１１】
本発明のノード装置は、自ノード装置と同一のネットワークシステムに含まれるノード装置のうちの少なくとも２つのノード装置の故障を検出した際、他のノード装置に対して、故障中の前記各ノード装置についての故障通知を異なるタイミングで送信する送信タイミング調整部を備える。
【００１２】
本発明のネットワークシステムは、複数のノード装置を含むネットワークシステムであって、前記ネットワークシステムに含まれるノード装置のうちの少なくとも２つのノード装置の故障が検出された際、前記所定のノード装置から他のノード装置に対して、故障中の前記各ノード装置についての故障通知を異なるタイミングで送信する。
【００１３】
本発明の故障通知方法は、複数のノード装置を含むネットワークシステムにおける故障通知方法であって、前記ネットワークシステムに含まれるノード装置のうちの少なくとも２つのノード装置の故障が検出された際、前記所定のノード装置から他のノード装置に対して、故障中の前記各ノード装置についての故障通知を異なるタイミングで送信する。
【００１４】
本発明のコンピュータプログラムは、複数のノード装置を含むネットワークシステムにおける所定のノード装置のコンピュータに、前記ネットワークシステムに含まれるノード装置のうちの少なくとも２つのノード装置の故障が検出された際、前記所定のノード装置から他のノード装置に対して、故障中の前記各ノード装置についての故障通知を異なるタイミングで送信する処理を、実行させる。
【発明の効果】
【００１５】
本発明によれば、多数のノード装置が同時に故障した場合であってもネットワーク内での制御負荷集中を回避することが可能となる。
【図面の簡単な説明】
【００１６】
【図１】本発明の第１の実施形態に係るノード装置の構成例を説明するためのブロック図である。
【図２】本発明の第２の実施形態に係るノード装置の構成例を説明するためのブロック図である。
【図３】図２に示すノード装置の動作例（パケット受信時の動作）を説明するためのフローチャートである。
【図４】図３に示すフローチャートの説明を補足するための補足図であり、（ａ）は、本説明で用いるネットワークの構成図（ノード接続図）であり、（ｂ）は、そのネットワークにおけるノード毎の通信量の変化例を示す表である。
【図５】図２に示すノード装置の動作例（パケット送信時の動作）を説明するためのフローチャートである。
【図６】図５に示すフローチャートの説明を補足するための補足図であり、（ａ）は、本説明で用いるネットワークの構成図（ノード接続図）であり、（ｂ）は、そのネットワークにおけるノード毎の通信量の変化例を示す表である。
【図７】図２に示すノード装置の動作例（故障発生時の動作）を説明するためのフローチャートである。
【図８】図７を用いて説明した故障発生時の動作に関してのより具体的な説明で使用されるネットワークの構成図（ノード接続図）である。
【図９】第２の実施形態に関し、図８におけるノードｎ１の隣接ノードの重要度の一例を示す表である。
【図１０】図８に示すネットワークにおいて故障が発生した場合の図である。
【図１１】中心度の考慮がされない場合における迂回通信トラフィックの例を示す図である。
【図１２】本発明の第３の実施形態に係るノード装置の構成例を説明するためのブロック図である。
【図１３】図１２に示すノード装置の動作例（次数の算出動作）を示すフローチャートである。
【図１４】図１２に示すノード装置の動作例（故障発生時の動作）を示すフローチャートである。
【図１５】第３の実施形態に関し、図８におけるノードｎ１の隣接ノードの重要度の一例を示す表である。
【図１６】第３の実施形態における故障通知の送信順序の決定条件例である。
【図１７】第３の実施形態による効果を説明するための図である。
【図１８】本発明の第４の実施形態に係るノード装置の構成例を説明するためのブロック図である。
【図１９】図１８に示すノード装置の動作例（Ｃｌｏｓｅｎｅｓｓ中心度の算出動作）を示すフローチャートである。
【図２０】第４の実施形態に関し、Ｃｌｏｓｅｎｅｓｓ中心度の計算の説明に用いるためのネットワークの構成例である。
【図２１】本発明の第５の実施形態に係るノード装置の構成例を説明するためのブロック図である。
【図２２】図２１に示すノード装置の動作例（Ｂｅｔｗｅｅｎｎｅｓｓ中心度の算出動作）を示すフローチャートである。
【発明を実施するための形態】
【００１７】
［第１の実施形態］
図１は、本発明の第１の実施形態に係るノード装置１０の構成例を説明するためのブロック図である。ノード装置１０は、ネットワークシステム（図１においては不図示）内に存在する所定のノード装置である。このネットワークシステムには、ノード装置１０以外に少なくとも２つ以上のノード装置が含まれる。ノード装置１０は、送信タイミング調整部１２を備える。送信タイミング調整部１２は、上記ネットワークシステムに含まれるノード装置のうちの少なくとも２つのノード装置の故障を検出した際、他のノード装置（故障中のノード装置以外のノード装置）に対して、故障中の各ノード装置についての故障通知を異なるタイミングで送信する。尚、上記において、故障ノードは、ノード装置１０に隣接しているノードであってもよく、隣接していないノード（例えば、２ホップ以上のノード）であってもよく、場合によっては、両者が混在していてもよい。
【００１８】
以上説明した第１の実施形態によれば、各故障ノード装置の故障通知は、時間方向に分散されて通知されるので、ワーム攻撃等により多数のノード装置に同時に故障が発生した場合であっても、所定のノード装置に対して大量の故障通知が同時に到達する事態を回避することができる。すなわち、ネットワーク内での制御負荷集中を回避することが可能となるため、さらなるノード装置の故障を阻止し、適切な経路制御を実行することが可能となる。
【００１９】
［第２の実施形態］
図２は、本発明の第２の実施形態に係るノード装置２０の構成例を説明するためのブロック図である。ノード装置２０は、経路制御部２２と、パケット転送部２４と、ネットワークインタフェース２６−１〜２６−ｎと、を少なくとも備える。
【００２０】
経路制御部２２は、故障検知部１００と、故障数判定部１０２と、リアルタイムクロック１０４と、故障通知遅延決定部１０６と、隣接ノード重要度表１０８と、通信量測定部１１０と、故障通知部１１２と、を少なくとも備える。
【００２１】
故障検知部１００は、ＯＳＰＦ（Ｏｐｅｎ Ｓｈｏｒｔｅｓｔ Ｐａｔｈ Ｆｉｒｓｔ）やＢＧＰ（Ｂｏｒｄｅｒ Ｇａｔｅｗａｙ Ｐｒｏｔｏｃｏｌ）などの経路制御プロトコルを使用して、ネットワークインタフェース２６−１〜２６−ｎに繋がっている、各リンク及び隣接ノードの故障を検知する。故障検知部１００は、例えば、隣接ノードから一定時間内に制御メッセージを受信しない場合、あるいは下位レイヤからの切断通知により、隣接ノードが故障していると判断する。尚、制御メッセージは、例えば、ＢＧＰの場合はＫｅｅｐ Ａｌｉｖｅメッセージであり、ＯＳＰＦの場合はＨｅｌｌｏメッセージである。故障を検知した場合、故障検知部１００は、故障が発生している隣接ノードについての情報である「故障ノード情報」を、故障数判定部１０２へ出力する。
【００２２】
故障数判定部１０２は、「故障ノード情報」に基づいて、隣接ノードの故障数を把握する。そして、故障数判定部１０２は、故障数に基づいて、各故障通知を異なるタイミングで送信するか、一斉に送信（通常の故障通知）するかを判断し、各々に、場合に応じた処理を実行する。具体的には、故障数が所定の閾値と等しいかあるいは超えている場合、故障数判定部１０２は、リアルタイムクロック１０４から「故障検知時刻情報」を取得する。そして、故障数判定部１０２は、「故障ノード情報」および「故障検知時刻情報」を、故障通知遅延決定部１０６へ出力する。一方、故障数が所定の閾値を下回る場合、故障数判定部１０２は、「故障ノード情報」を、故障通知部１１２へ出力する。
【００２３】
リアルタイムクロック１０４は、故障数判定部１０２のリクエストに応じて時刻情報を提供する。
【００２４】
故障通知遅延決定部１０６は、故障数判定部１０２から取得した「故障ノード情報」に基づいて、どの隣接ノードが故障しているかを把握し、それぞれの故障ノードの通信量を、隣接ノード重要度表１０８から取得する。そして、故障通知遅延決定部１０６は、得られた各故障ノードの通信量に基づいて各故障ノードの故障通知遅延時間を決定する。故障通知遅延決定部１０６は、少なくとも、「故障通知遅延時間情報」および「故障検知時刻情報」を、故障通知部１１２へ出力する。
【００２５】
隣接ノード重要度表１０８には、ネットワークに参加している各ノードについての重要度が記憶されている。第２の実施形態において、重要度は、各ノードとそれらに接続する各隣接ノードとの間の各通信量であるものとする。通信量の測定方法については、後述する。
【００２６】
通信量測定部１１０は、隣接ノードとの間の通信を監視し、その監視結果に基づいて、隣接ノード重要度表１０８の内容を更新する。具体的には、通信量測定部１１０は、ネットワークインタフェース２６−１〜２６−ｎに入ってくるパケット、もしくは、ネットワークインタフェース２６−１〜２６−ｎから出ていくパケットを観測し、隣接ノード重要度表１０８における各隣接ノードとの通信量をインクリメントする。また、通信量測定部１１０は、例えば、内部にタイマ（図２において不図示）を保持することができる。そして、通信量測定部１１０は、タイマ値が一定値以上となった場合、隣接ノード重要度表１０８における、所定の隣接ノードについての通信量を０にリセットすることもできる。
【００２７】
故障通知部１１２は、故障数判定部１０２からの「故障ノード情報」に基づいて、通常の故障通知（一斉通知）を行う。また、故障通知部１１２は、故障通知遅延決定部１０６からの「故障通知遅延時間情報」および「故障検知時刻情報」に基づいて、各故障通知を異なるタイミングで送信する処理を実行する。具体的には、故障通知部１１２は、上記各情報に基づいて、各故障ノードの故障通知送信時刻を決定する。故障通知部１１２は、各送信時刻となる度に、その都度、対応する故障通知を送信する。
【００２８】
パケット転送部２４は、経路表１２０を備える。経路表１２０には、ネットワーク内の各宛先ノードへパケットを送信するとき、最初に送信するノードについての情報が記載されている。
【００２９】
以下、第２の実施形態のノード装置２０の動作について説明する。パケット受信時の動作、パケット送信時の動作、および故障発生時の動作について、以下、順番に説明する。
【００３０】
図３は、図２に示すノード装置２０の動作例（パケット受信時の動作）を説明するためのフローチャートである。
【００３１】
まず、通信量測定部１１０は、ネットワークインタフェース２６−１〜２６−ｎのいずれかを介してパケット転送部２４がパケットを受信したか否かを判定する（ステップＳ１）。パケットが受信された場合（ステップＳ１においてＹｅｓ判定）、通信量測定部１１０は、受信したパケットのヘッダ情報を参照し、そのパケットを自分に転送したノードがどのノードであるかを特定する（ステップＳ２）。そして、通信量測定部１１０は、隣接ノード重要度表１０８において、特定したノードの通信量をインクリメントする（ステップＳ３）。ここで、インクリメントする値はどのような値であってもよい。本実施形態では、＋１する場合を例に挙げる。
【００３２】
通信量測定部１１０は、特定したノード（転送元のノード）の通信量をインクリメントした後、一定の時間が経過したか否かを判定する（ステップＳ４）。一定時間が経過しない場合（ステップＳ４においてＮｏ判定）、通信量測定部１１０は、新たなパケットの受信（ステップＳ１）あるいはパケット送信の有無（図３では不図示）を判定する。一方、一定時間が経過した場合（ステップＳ４においてＹｅｓ判定）、通信量測定部１１０は、そのノードの通信量に変化が有るか否かを判定する（ステップＳ５）。通信量に変化がある場合（ステップＳ５においてＹｅｓ判定）、図３に示す処理を終了する（再びステップＳ１の処理あるいはパケット送信の有無判定を行っても良い）。一方、通信量に変化が無い場合（ステップＳ５においてＮｏ判定）、通信量測定部１１０は、隣接ノード重要度表１０８において、そのノードの通信量を０にリセットする（ステップＳ６）。
【００３３】
図４は、図３に示すフローチャートの説明を補足するための補足図であり、具体的には、パケット受信時における通信量の測定について説明するための図である。図４（ａ）は、本説明で用いるネットワークの構成図（ノード接続図）であり、図４（ｂ）は、そのネットワークにおけるノード毎の通信量の変化例を示す表である。図４（ａ）を参照し、自己のノードＡには、隣接ノードＢ、Ｃが接続される。この場合、ノードＡは、ノードＢからパケットを受信するものとする。ここで、パケットの受信とは、ノードＡが最終宛先の場合と、ノードＡを中継する場合と、を含む。自己のノードＡがノードＢからパケットを受信した際、ノードＡの通信量測定部１１０は、隣接ノード重要度表１０８において、ノードＢの通信量を１つインクリメントする。具体的には、図４（ｂ）に示すように、ノードＢの通信量は、０（パケット受信前）から１（パケット受信後）へと変化する。
【００３４】
図５は、図２に示すノード装置２０の動作例（パケット送信時の動作）を説明するためのフローチャートである。
【００３５】
まず、通信量測定部１１０は、パケット転送部２４がネットワークインタフェース２６−１〜２６−ｎのいずれかにパケットを送信したか否かを判定する（ステップＳ１０）。パケットを送信した場合（ステップＳ１０においてＹｅｓ判定）、通信量測定部１１０は、経路表１２０を参照し、パケットの転送先ノードを特定する（ステップＳ１１）。そして、通信量測定部１１０は、隣接ノード重要度表１０８において、特定した転送先ノードの通信量をインクリメントする（ステップＳ１２）。ここで、パケット受信時と同様に、インクリメントする値はどのような値であってもよい。本実施形態では、＋１する場合を例に挙げる。
【００３６】
通信量測定部１１０は、所定のノード（転送先のノード）の通信量をインクリメントした後、一定の時間が経過したか否かを判定する（ステップＳ１３）。一定時間が経過しない場合（ステップＳ１３においてＮｏ判定）、通信量測定部１１０は、新たなパケットの送信（ステップＳ１０）あるいはパケット受信の有無（図５では不図示）を判定する。一方、一定時間が経過した場合（ステップＳ１３においてＹｅｓ判定）、通信量測定部１１０は、そのノードの通信量に変化が有るか否かを判定する（ステップＳ１４）。通信量に変化がある場合（ステップＳ１４においてＹｅｓ判定）、図５に示す処理を終了する（再びステップＳ１の処理あるいはパケット受信の有無判定を行っても良い）。一方、通信量に変化が無い場合（ステップＳ１４においてＮｏ判定）、通信量測定部１１０は、隣接ノード重要度表１０８において、そのノードの通信量を０にリセットする（ステップＳ１５）。
【００３７】
図６は、図５に示すフローチャートの説明を補足するための補足図であり、具体的には、パケット送信時における通信量の測定について説明するための図である。図６（ａ）は、本説明で用いるネットワークの構成図（ノード接続図）であり、図６（ｂ）は、そのネットワークにおけるノード毎の通信量の変化例を示す表である。図６（ａ）を参照し、自己のノードＡには、隣接ノードＢ、Ｃが接続される。この場合、ノードＡは、ノードＣにパケットを送信するものとする。ここで、パケットの送信とは、ノードＣが最終宛先の場合と、ノードＣを中継する場合と、を含む。自己のノードＡがノードＣにパケットを送信した際、ノードＡの通信量測定部１１０は、隣接ノード重要度表１０８において、ノードＣの通信量を１つインクリメントする。具体的には、図６（ｂ）に示すように、ノードＣの通信量は、０（パケット送信前）から１（パケット送信後）へと変化する。
【００３８】
図７は、図２に示すノード装置２０の動作例（故障発生時の動作）を説明するためのフローチャートである。
【００３９】
故障検知部１００は、隣接ノードの故障を検知する（ステップＳ２０）。この場合、故障検知部１００は、例えば、隣接ノードから一定時間内に制御メッセージを受信しない場合に隣接ノードが故障していると判断する。故障を検知した場合、故障検知部１００は、故障が発生している隣接ノードについての情報である「故障ノード情報」を、故障数判定部１０２へ出力する。
【００４０】
故障数判定部１０２は、「故障ノード情報」に基づいて隣接ノードの故障数を把握し、故障数が所定の閾値Ｋ以上か否かを判定する（ステップＳ２１）。故障数が閾値Ｋ未満の場合（ステップＳ２１においてＮｏ判定）、通常の故障通知（一斉通知）処理が実行される（ステップＳ２２）。具体的には、故障数判定部１０２は、「故障ノード情報」を、故障通知部１１２へ出力する。故障通知部１１２は、「故障ノード情報」における全ての故障ノードに対して、故障通知を一斉に送信する。
【００４１】
一方、故障数が閾値Ｋ以上の場合（ステップＳ２１においてＹｅｓ判定）、各故障通知を異なるタイミングで送信する処理が実行される。具体的には、故障数判定部１０２は、リアルタイムクロック１０４から「故障検知時刻情報」を取得する。そして、故障数判定部１０２は、「故障ノード情報」および「故障検知時刻情報」を、故障通知遅延決定部１０６へ出力する（ステップＳ２３）。
【００４２】
故障通知遅延決定部１０６は、各故障ノードの故障通知遅延時間を決定する（ステップＳ２４）。具体的には、故障通知遅延決定部１０６は、隣接ノード重要度表１０８から各故障ノードの通信量Ｘｉを取得し、これらの通信量Ｘｉに応じて、それぞれの故障ノードの故障通知遅延時間Ｄｉを決定する。そして、故障通知遅延決定部１０６は、故障通知遅延時間Ｄｉおよび故障検知時刻ｔを、故障通知部１１２へ出力する（ステップＳ２５）。
【００４３】
故障通知部１１２は、各故障ノードについて、故障通知の送信時刻を決定する（ステップＳ２６）。具体的には、故障通知部１１２は、各故障検知時刻ｔに各通知遅延Ｄｉを足した時刻を、各故障通知の送信時刻とする。故障通知部１１２は、各送信時刻となる度に、その都度、対応する故障通知を送信する（ステップＳ２７）。
【００４４】
以下、図７を用いて説明した故障発生時の動作に関し、より具体的な例を挙げて説明する。
【００４５】
図８は、本説明で用いるネットワークの構成図（ノード接続図）である。図８に示すように、対象ネットワークは、ネットワーク１と、ノードｎｉ（ｉ＝１〜９）から構成される。図８において、太い矢印は通信トラフィックのフローとその方向を示している。もちろん、本実施形態が適用されるネットワークは、図８に記載されたネットワークに限定されることはない。
【００４６】
ここで、ノードｎ１にとって、ノードｎ２、ノードｎ４、ノードｎ５の通信量が０であり、ノードｎ３とノードｎ８の通信量が９であると仮定する。従って、この場合、隣接ノード重要度表１０８において、自ノードｎ１の隣接ノードについての重要度は、図９のようになる。
【００４７】
図７のステップＳ２１において、閾値Ｋ＝２とする場合を例に挙げる。もちろん、この値は単なる一例であって、ネットワーク状況や規模に応じて、閾値Ｋは、どの値に設定してもよい。また、ステップＳ２４において、故障通知遅延時間をＤｉ＝１００／（Ｘｉ＋１）［ｍｓ］に設定する場合を例に挙げる。ここで、Ｘｉは、故障ノードｎｉ（この場合、ｉ＝１〜９）の各通信量を示し、Ｄｉは、各故障ノードの各故障通知遅延時間を示す。尚、上記計算式はあくまで一例であって、故障通知遅延時間を算出するための計算式は上記に限定されることはない。
【００４８】
図１０は、図８に示すネットワークにおいて故障が発生した場合の図である。図１０では、ノードｎ２、ノードｎ３、ノードｎ４が故障し、ノードｎ１が、これらの故障を時刻ｔにおいて検知した場合を例に挙げる。ここで、これらの故障通知を通常の方法にて送信する場合（すなわち、一斉送信する場合）、ノードｎ１は、ノードｎ２、ノードｎ３、ノードｎ４の故障通知を、ネットワーク内に同時に送信する。従って、ノードｎ８、ノードｎ９、およびネットワーク１にある全ノードに、経路再計算のための制御負荷が集中してしまう。しかしながら、第２の実施形態の通知方法（図７に示すフローチャートで示す方法）を適用した場合の動作は次のようになる。
【００４９】
以下、図８〜図１０に示す具体的な状況を、図７に示すフローチャートに当てはめて説明する。ノードｎ１の故障検知部１００は、ノードｎ２、ｎ３、ｎ４の故障を検知する（ステップＳ２０）。ノードｎ１の故障数判定部１０２は、故障数が所定の閾値Ｋ＝２以上か否かを判定する（ステップＳ２１）。この場合、故障ノード数は３であり閾値Ｋ＝２よりも大きい（ステップＳ２１においてＹｅｓ判定）。従って、ノードｎ１の故障数判定部１０２は、故障ノード情報（ノードｎ２、ｎ３、ｎ４のリスト）および故障検知時刻情報（リアルタイムクロック１０４から取得した時刻ｔ）を、故障通知遅延決定部１０６へ出力する（ステップＳ２３）。
【００５０】
故障通知遅延決定部１０６は、隣接ノード重要度表１０８から、自ノードに接続する隣接ノードのうち各故障ノードｎ２、ｎ３、ｎ４についての各通信量Ｘｉを取得し、これらの通信量Ｘｉに応じて、それぞれの故障ノードの故障通知遅延時間Ｄｉを決定する（ステップＳ２４）。ここで、ノードｎ２、ｎ３、ｎ４の各通信量は、０、９、０である（図９参照）。一方、上述した通り、故障通知遅延時間Ｄｉは、計算式Ｄｉ＝１００／（Ｘｉ＋１）［ｍｓ］によって計算される。従って、上記各通信量Ｘｉを該計算式に代入することにより、それぞれの故障ノードｎ２、ｎ３、ｎ４の各故障通知遅延時間Ｄｉは、１００ｍｓ、 １０ｍｓ、１００ｍｓとなる（ステップＳ２５）。
【００５１】
ノードｎ１は、ノードｎ３の故障通知時刻をｔ＋１０ｍｓと決定し、ノードｎ２、ｎ４の故障通知時刻をｔ＋１００ｍｓと決定する（ステップＳ２６）。ノードｎ１は、各故障通知を各時刻が到達する度に送信する（ステップＳ２７）。
【００５２】
以上説明した第２の実施形態によれば、各故障ノードの故障通知は、時間方向に分散されて通知されるので、ワーム攻撃等により多数のノードに同時に故障が発生した場合であっても、所定のノードに対して大量の故障通知が同時に到達する事態を回避することができる。すなわち、ネットワーク内での制御負荷集中を回避することが可能となるため、さらなるノード故障を阻止し、適切な経路制御を実行することが可能となる。
【００５３】
さらに、第２の実施形態の場合、各故障通知の送信タイミングは、ノードの重要度、例えば、通信量に基づいて決定される。従って、例えば、図９に示すノードｎ３のように、通信量が多いノードの故障通知を真っ先に伝搬させることが可能となる。これにより、重要度が高い経路（換言すれば、通信量の多い経路、あるいは頻繁に使用される経路）の復旧（すなわち、迂回路の再計算）を他の経路に先んじて優先的に実施することが可能となる。
【００５４】
さらに、以上説明した第２の実施形態では、故障ノードの数に基づいて、故障通知を異なるタイミングで送信するか、通常の故障通知（すなわち、一斉送信）を行うかを決定している。例えば、システムの規模を鑑みてある程度の数であれば故障通知を同時に送信しても問題ないと判断できる場合（換言すれば、処理負荷上、特に問題が発生しない場合）、故障通知を敢えて遅らせるよりも、できるだけ早く送ったほうがよい場合もあるからである。
【００５５】
尚、以上説明した第２の実施形態において、通信量と故障通知遅延時間とは必ずしも反比例（あるいは、通信量や計算式自体の設定によっては比例の場合もある）の関係にあるとは限らない。例えば、故障通知遅延決定部１０６は、故障ノードの通信量同士を比較し、該比較結果に応じて各故障通知の送信順序のみを決定し、故障通知遅延時間自体は定数（例えば、１００ｍｓ）とすることも可能である。例えば、故障通知送信の基準時刻をｔとした場合、各故障通知を、各時刻ｔ、ｔ＋１００ｍｓ、ｔ＋２００ｍｓ・・・に順次送信すればよい。このような方法でも、制御負荷集中の回避と重要度が高い経路の早期復旧を実現することが可能となる。
【００５６】
また、以上説明した図７のステップＳ２１における、故障数と閾値Ｋとの比較条件は、「以上」に限定されることはない。例えば、故障数と閾値Ｋとが等しい場合を除外する「より大きい」であってもよい。
【００５７】
［第３の実施形態］
第２実施形態において、ノードの重要度は、ノードの通信量のみに基づいている。もちろん、これにより、基本的には、制御負荷集中の回避と重要度が高い経路の早期復旧を実現することが可能となる。しかしながら、故障したノードの通信量自体は少ないが、他の故障ノードの迂回経路の通過点として選択される可能性が非常に高い（中心度が非常に高い）場合を想定すると、通信量のみの考慮では不十分な場合がある。
【００５８】
第２の実施形態の場合、例えば、図１０において、他ノード（ノードｎ８、ノードｎ９、あるいはネットワーク１内のノード）に対して、通信量の少ないノードｎ４の故障通知は、通信量の多いノードｎ３の故障通知よりも遅れて到着する。この場合、他ノードは、図１１に示すように、故障したノードｎ３を迂回する新しい経路として、故障したノードｎ４を経由した経路（すなわち、有効ではない経路）を選択してしまう虞がある。この場合、他ノードは、ノードｎ３を迂回する更なる別の経路を再計算しなければならないため、効率が低下する可能性がある。
【００５９】
そこで、第３の実施形態は、ノードの通信量だけでなくノードの中心度も考慮して、各故障通知の送信を制御する点を特徴とする。第３の実施形態では、中心度を、「自ノードに接続する隣接ノードに接続するノード数（次数）」とする場合を例に挙げる。
【００６０】
図１２は、本発明の第３の実施形態に係るノード装置５０の構成例を説明するためのブロック図である。ノード装置５０は、第２の実施形態のノード装置２０（図２参照）を基本としており、パケット転送部２４とネットワークインタフェース２６−１〜２６−ｎは、ノード装置２０と同一である。従って、これらについては図１２において図２と同一の参照符号を付し、ここでの説明を省略する。
【００６１】
また、経路制御部５２を構成する要素のうち、故障検知部１００と、故障数判定部１０２と、リアルタイムクロック１０４と、通信量測定部１１０と、故障通知部１１２とは、ノード装置２０の経路制御部２２におけるそれらと同一である。従って、これらについては図１２において図２と同一の参照符号を付し、ここでの説明を省略する。
【００６２】
従って、以下、経路制御部５２を構成する要素のうち、経路制御部２２と機能が異なる構成要素あるいは新規な構成要素、すなわち、隣接ノード重要度表１３０と、故障通知遅延決定部１３２と、トポロジ情報交換部１３４と、中心度計算部１３６とについてのみ説明する。
【００６３】
隣接ノード重要度表１３０には、ネットワークに参加している各ノードについての重要度が記憶されている。第３の実施形態において、重要度は、「通信量」と「中心度（次数）」を含む。ここで、通信量は、第２の実施形態と同様に、各ノードとそれらに接続する各隣接ノードとの間の各通信量（例えば、受信パケット数および／または送信パケット数）である。一方、中心度は、各隣接ノードに接続するノードの数（以下、これを次数と呼ぶ）である。この場合、次数には、自ノードも含まれる。尚、通信量は、第２の実施形態と同様に、通信量測定部１１０によって計算（更新）され、次数は、中心度計算部１３６によって計算（更新）される。
【００６４】
故障通知遅延決定部１３２は、通信量だけでなく、中心度（第３の実施形態の場合は、次数）も考慮して、故障ノードの故障通知の遅延を決定する。遅延決定処理の詳細については、後述する。
【００６５】
トポロジ情報交換部１３４は、隣接ノードからトポロジ情報を受信する。ここで、トポロジ情報とは、例えば、ネットワークの接続形態についての情報である。トポロジ情報交換部１３４は、新しいトポロジ情報が設定された場合、あるいはネットワークトポロジに変化があった場合、中心度計算部１３６に対して、トポロジ情報を渡す。
【００６６】
中心度計算部１３６は、トポロジ情報交換部１３４から得られたトポロジ情報を元に、各隣接ノードの次数を計算し、その結果を隣接ノード重要度表１３０に登録する。
【００６７】
以下、第３の実施形態のノード装置５０の動作について説明する。尚、第３の実施形態における、パケット受信時の動作およびパケット送信時の動作は、第２の実施形態の各動作（図３および図５を各々に参照）と同一であるため、省略する。従って、以下、次数の算出動作と故障発生時の動作について、以下、順番に説明する。
【００６８】
図１３は、図１２に示すノード装置の動作例（次数の算出動作）を示すフローチャートである。
【００６９】
中心度計算部１３６は、トポロジ情報交換部１１８からトポロジ情報を取得する（ステップＳ３０）。中心度計算部１３６は、各隣接ノードの次数を算出する（ステップＳ３１）。具体的には、中心度計算部１３６は、得られたトポロジ情報に基づいて、自ノードの各隣接ノードに接続する隣接ノード数を算出し、その値を次数とする。中心度計算部１３６は、算出された各隣接ノードの次数を隣接ノード重要度表１３０に登録する（ステップＳ３２）。
【００７０】
図１４は、図１２に示すノード装置の動作例（故障発生時の動作）を示すフローチャートである。尚、図１４に示すフローチャートにおける各処理ステップにおいて、図７に示す第２の実施形態のフローチャートと同一の処理ステップには図７と同一のステップ番号を付し、それらの説明については簡略化して説明する。
【００７１】
故障検知部１００は、隣接ノードの故障を検知する（ステップＳ２０）。故障を検知した場合、故障検知部１００は、「故障ノード情報」を、故障数判定部１０２へ出力する。故障数判定部１０２は、故障数が所定の閾値Ｋ以上か否かを判定する（ステップＳ２１）。故障数が閾値Ｋ未満の場合（ステップＳ２１においてＮｏ判定）、通常の故障通知（一斉通知）処理が実行される（ステップＳ２２）。
【００７２】
一方、故障数が閾値Ｋ以上の場合（ステップＳ２１においてＹｅｓ判定）、故障数判定部１０２は、リアルタイムクロック１０４から「故障検知時刻情報」を取得する。そして、故障数判定部１０２は、「故障ノード情報」および「故障検知時刻情報」を、故障通知遅延決定部１３２へ出力する（ステップＳ４３）。
【００７３】
故障通知遅延決定部１３２は、隣接ノード重要度表１３０から、各故障ノードの通信量および中心度（次数）を取得する（ステップＳ４４）。故障通知遅延決定部１３２は、、各故障ノードの通信量および中心度（次数）に基づいて、各故障ノードの故障通知を送信する順番を決定する（ステップＳ４５）。故障通知部１１２は、決定された送信順序に従って、各故障ノードの故障通知を送信する（ステップＳ４６）。
【００７４】
以上説明した故障発生時の動作に関し、以下、具体的な例を挙げて説明する。例えば、図８に示すネットワークを例に挙げて説明する。もちろん、本実施形態が適用されるネットワークは、図８に記載されたネットワークに限定されることはない。図９に示すように、自ノードｎ１にとって、ノードｎ２、ノードｎ４、ノードｎ５の通信量は０であり、ノードｎ３とノードｎ８の通信量は９である。ここで、自ノードｎ１の隣接ノードであるノードｎ２に接続する隣接ノード数は１つである（すなわち、自ノードｎ１のみ）。従って、ノードｎ２の次数は、１となる。また、図８において、自ノードｎ１に接続する他の隣接ノードｎ３、ノードｎ４、ノードｎ５、ノードｎ８のそれぞれに接続する隣接ノードの数は各２つであるため、それぞれのノードの次数は、２になる。すなわち、図８に示すネットワーク構成の場合、隣接ノード重要度表１３０において、自ノードｎ１に接続する隣接ノードの重要度は、図１５のようになる。
【００７５】
また、第２実施形態と同様、図１４のステップＳ４１において、閾値Ｋ＝２とする場合を例に挙げる。もちろん、この値は単なる一例であって、ネットワーク状況や規模に応じて、閾値Ｋは、どの値に設定してもよい。尚、以下の説明において、複数ノードが故障した際、制御負荷の分散のために、故障ノードの故障通知を複数回（具体的には２回）に分割して、送信する場合を想定する。また、以下の説明において、第２の実施形態と同様に、図１０に示す如く、ノードｎ２、ノードｎ３、ノードｎ４が故障し、ノードｎ１がこれらのノードについての故障通知の送信を制御する場合を例に挙げる。
【００７６】
図１４のステップＳ４５における故障ノード（ノードｎ２、ｎ３、ｎ４）の故障通知送信順序の条件の一例として、図１６に示す条件（条件１）を挙げる。尚、条件１はあくまで一例であって、送信順序の条件は、この条件１に限定されることはない。
【００７７】
すると、故障発生時、ノードｎ２に関しては、Ｘ２（ノードｎ２の通信量）＝０、Ｙ２（ノードｎ２の中心度（次数））＝１である（以上、図１５参照）。従って、条件１の式において、Ｘ２＋１０＊Ｙ２＝１０＜１５となるため、故障ノードｎ２の故障通知を後で送信すると判断する。
【００７８】
一方、ノードｎ３に関しては、Ｘ３（ノードｎ３の通信量）＝９、Ｙ３（ノードｎ３の中心度（次数））＝２である（以上、図１５参照）。従って、条件１の式において、Ｘ３＋１０＊Ｙ３＝２９＞１５となる。さらに、ノードｎ４に関しては、Ｘ４（ノードｎ４の通信量）＝０、Ｙ４（ノードｎ４の中心度（次数））＝２である（以上、図１５参照）。従って、条件１の式において、Ｘ４＋１０＊Ｙ４＝２０＞１５となる。以上から、故障ノードｎ３および故障ノードｎ４の故障通知を先に送信すると判断する。
【００７９】
図１７は、第３の実施形態による効果を説明するための図である。図１７に示すように、通信量および中心度（次数）の高い、ノードｎ３およびノードｎ４の故障通知を、他のノード（ノードｎ８、ノードｎ９、およびネットワーク１にいるノード）に対して、早くかつ同時に到着させることが可能となる。従って、これらの他のノードは、ノードｎ３とノードｎ４が同時に故障していることがわかるため、ノードｎ３を迂回する新しい通信経路を計算する際に、ノードｎ４を含むことなく他の適切な通信経路（例えば、ノードｎ５を通過する経路）を選択することが可能となる。
【００８０】
以上説明した第３の実施形態の場合、第２の実施形態と同様に、各故障ノードの故障通知は、時間方向に分散されて通知される。従って、ネットワーク内での制御負荷集中を回避することが可能となり、さらなるノード故障を阻止し、適切な経路制御を実行することが可能となる。
【００８１】
さらに、第３の実施形態の場合、各故障通知の送信タイミングは、ノードの重要度に基づいて決定される。従って、通信量が多いノードの故障通知を真っ先に伝搬させることが可能となる。
【００８２】
しかも、第３の実施形態の場合、通信量と中心度（次数）の両方を考慮して重要度を判断する。従って、例えば、重要度が一定以上の故障ノード（例えば、ノードｎ３とノードｎ４）の故障通知を、重要度が一定以下の故障ノード（例えば、ノードｎ２）の故障通知に先んじて、且つ、重要度が一定以上のもの同士を、同時に送信することが可能となる。従って、これらの故障通知を受信した他のノードは、故障ノードｎ３の有効な迂回経路を素早く計算することができるばかりでなく、故障ノードｎ４を避けることができるので、経路計算を１回で済ますことができる。すなわち、第３の実施形態によれば、通信効率の向上と経路計算効率の向上とを同時に達成することが可能となる。
【００８３】
［第４の実施形態］
第４の実施形態は、ノードの通信量だけでなくノードの中心度も考慮して重要度を判断する点は、第３の実施形態と同様である。第４の実施形態の、第３の実施形態に対する差異は、中心度として、「次数」の代わりに「Ｃｌｏｓｅｎｅｓｓ中心度」を用いる点にある。Ｃｌｏｓｅｎｅｓｓ中心度とは、あるノードからネットワークに存在する他ノードまでの最短距離（例えば、最小ホップ数）の合計値または各最短距離の平均値に、反比例する値のことである。
【００８４】
図１８は、第４の実施形態に係るノード装置６０の構成例を説明するためのブロック図である。ノード装置６０は、第３の実施形態のノード装置５０（図１２参照）を基本としており、パケット転送部２４とネットワークインタフェース２６−１〜２６−ｎは、ノード装置５０と同一である。従って、これらについては図１８において図１２と同一の参照符号を付し、ここでの説明を省略する。
【００８５】
また、経路制御部６２を構成する要素のうち、故障検知部１００と、故障数判定部１０２と、リアルタイムクロック１０４と、通信量測定部１１０と、故障通知部１１２と、トポロジ情報交換部１３４とは、ノード装置５０の経路制御部５２におけるそれらと同一である。従って、これらについては図１８において図１２と同一の参照符号を付し、ここでの説明を省略する。
【００８６】
従って、以下、経路制御部６２を構成する要素のうち、経路制御部５２と機能が異なる構成要素あるいは新規な構成要素、すなわち、隣接ノード重要度表１４０と、故障通知遅延決定部１４２と、Ｃｌｏｓｅｎｅｓｓ中心度計算部１４４とについてのみ説明する。
【００８７】
故障通知遅延決定部１４２は、通信量だけでなく、中心度（第４の実施形態の場合、Ｃｌｏｓｅｎｅｓｓ中心度）も考慮して、故障ノードの故障通知の遅延を決定する。尚、故障通知遅延決定部１４２における遅延決定処理は、参照する情報が、次数とＣｌｏｓｅｎｅｓｓ中心度の違いはあれど、基本的には、第３の実施形態の故障通知遅延決定部１３２と同じである。
【００８８】
隣接ノード重要度表１４０には、ネットワークに参加している各ノードについての重要度が記憶されている。第４の実施形態において、重要度は、「通信量」と「中心度（Ｃｌｏｓｅｎｅｓｓ中心度）」を含む。尚、通信量は、第２の実施形態と同様に、通信量測定部１１０によって計算（更新）され、Ｃｌｏｓｅｎｅｓｓ中心度は、Ｃｌｏｓｅｎｅｓｓ中心度計算部１４４によって計算（更新）される。
【００８９】
Ｃｌｏｓｅｎｅｓｓ中心度計算部１４４は、各ノードのＣｌｏｓｅｎｅｓｓ中心度を計算し、その結果を隣接ノード重要度表１４０に登録する。
【００９０】
以下、第４の実施形態のノード装置６０の動作について説明する。尚、第４の実施形態における、パケット受信時の動作およびパケット送信時の動作は、第２の実施形態の各動作（図３および図５を各々に参照）と同一であるため、省略する。また、第４の実施形態における故障発生時の動作（すなわち、通信量と中心度とを考慮して、各故障通知の送信を制御する動作）については、第３の実施形態（図１４参照）と同一であるため、省略する。従って、以下、Ｃｌｏｓｅｎｅｓｓ中心度の算出動作についてのみ説明する。
【００９１】
図１９は、図１８に示すノード装置の動作例（Ｃｌｏｓｅｎｅｓｓ中心度の算出動作）を示すフローチャートである。
【００９２】
Ｃｌｏｓｅｎｅｓｓ中心度計算部１４４は、トポロジ情報交換部１３４からトポロジ情報を取得する（ステップＳ５０）。Ｃｌｏｓｅｎｅｓｓ中心度計算部１４４は、以下の（式１）により、Ｃｌｏｓｅｎｅｓｓ中心度を計算する（ステップＳ５１）。
【００９３】
（式１）
（式１）において、Ｃｌｏｓｅｎｅｓｓ（ｉ）はノードｉのＣｌｏｓｅｎｅｓｓ中心度を示し、Ｎはネットワーク内に存在するノード数を示し、Ｇはネットワーク内のノード集合を示し、ｄｉｊはノードｉからノードｊまでの最短距離（例えば、最小ホップ数）を示す。
【００９４】
Ｃｌｏｓｅｎｅｓｓ中心度計算部１４４は、トポロジ情報に基づいて、ノードｊをネットワーク中の全ノード集合Ｇに属する変数とするとともに、ネットワーク内における全ノード数Ｎを求める。Ｃｌｏｓｅｎｅｓｓ中心度計算部１４４は、ノードｉをルートとする最短経路（例えば、最小ホップ数）パスツリーを計算する。Ｃｌｏｓｅｎｅｓｓ中心度計算部１４４は、全てのノードｊに対して、ノードｉからノードｊまでの最短距離（例えば、最小ホップ数）ｄｉｊを計算する。Ｃｌｏｓｅｎｅｓｓ中心度計算部１４４は、全てのノードｊに対してＣｌｏｓｅｎｅｓｓ（ｉ）を計算し、これらを隣接ノード重要度表１４０に登録する（ステップＳ５２）。
【００９５】
以上説明したＣｌｏｓｅｎｅｓｓ中心度の算出動作に関し、以下、具体的な例を挙げて説明する。例えば、図２０に示すネットワークを例に挙げて説明する。もちろん、本実施形態が適用されるネットワークは、図２０に記載されたネットワークに限定されることはない。
【００９６】
図２０において、ネットワーク内に存在するノード数Ｎ＝６であり、ネットワーク内のノード集合Ｇ＝［Ａ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ］である。ここで、ノードＣから各ノード（Ａ、Ｂ、Ｆ、Ｄ、Ｅ）までの最短距離（この場合、最小ホップ数）は、それぞれ、２、１、１、１、２となる。従って、ノードＣのＣｌｏｓｅｎｅｓｓ（Ｃ）は、（式１）により、（６−１）／（２＋１＋１＋１＋２）＝５／７となる。
【００９７】
また、ノードＡのＣｌｏｓｅｎｅｓｓ（Ａ）を計算する場合、ノードＡから各ノード（Ｂ、Ｃ、Ｄ、Ｅ、Ｆ）までの最短距離（この場合、最小ホップ数）は、それぞれ、１、２、３、４、３であるため、Ｃｌｏｓｅｎｅｓｓ（Ａ）は、（式１）により、（６−１）／（１＋２＋３＋４＋３）＝５／１３となる。
【００９８】
尚、Ｃｌｏｓｅｎｅｓｓ中心度の計算に用いる最短距離（例えば、最小ホップ数）は、経路表１２０の情報から直接求めるか、もしくは、トポロジ情報やグラフ情報を元に、Ｄｉｊｋｓｔｒａ法などのアルゴリズムを用いることで計算することができる。
【００９９】
また、第４の実施形態において、最短距離の例として最小ホップ数を挙げたが、最短距離はこれに限定されず、例えば、通信遅延（時間として表される距離情報）を用いてもよい。
【０１００】
［第５の実施形態］
第５の実施形態は、ノードの通信量だけでなくノードの中心度も考慮して重要度を判断する点は、第３および第４の実施形態と同様である。第５の実施形態の、第４の実施形態に対する差異は、中心度として、「Ｃｌｏｓｅｎｅｓｓ中心度」の代わりに「Ｂｅｔｗｅｅｎｎｅｓｓ中心度」を用いる点にある。Ｂｅｔｗｅｅｎｎｅｓｓ中心度とは、あるノードを通過する最短路の数、またはその数に比例する値のことである。
【０１０１】
図２１は、第５の実施形態に係るノード装置７０の構成例を説明するためのブロック図である。ノード装置７０は、第４の実施形態のノード装置６０（図１８参照）を基本としており、パケット転送部２４とネットワークインタフェース２６−１〜２６−ｎは、ノード装置６０と同一である。従って、これらについては図２１において図１８と同一の参照符号を付し、ここでの説明を省略する。
【０１０２】
また、経路制御部７２を構成する要素のうち、故障検知部１００と、故障数判定部１０２と、リアルタイムクロック１０４と、通信量測定部１１０と、故障通知部１１２と、トポロジ情報交換部１３４とは、ノード装置６０の経路制御部６２におけるそれらと同一である。従って、これらについては図２１において図１８と同一の参照符号を付し、ここでの説明を省略する。
【０１０３】
従って、以下、経路制御部７２を構成する要素のうち、経路制御部６２と機能が異なる構成要素あるいは新規な構成要素、すなわち、隣接ノード重要度表１５０と、故障通知遅延決定部１５２と、Ｂｅｔｗｅｅｎｎｅｓｓ中心度計算部１５４とについてのみ説明する。
【０１０４】
故障通知遅延決定部１５２は、通信量だけでなく、中心度（第５の実施形態の場合、Ｂｅｔｗｅｅｎｎｅｓｓ中心度）も考慮して、故障ノードの故障通知の遅延を決定する。尚、故障通知遅延決定部１５２における遅延決定処理は、参照する情報が、次数とＢｅｔｗｅｅｎｎｅｓｓ中心度の違いはあれど、基本的には、第３の実施形態の故障通知遅延決定部１３２と同じである。
【０１０５】
隣接ノード重要度表１５０には、ネットワークに参加している各ノードについての重要度が記憶されている。第５の実施形態において、重要度は、「通信量」と「中心度（Ｂｅｔｗｅｅｎｎｅｓｓ中心度）」を含む。尚、通信量は、第２の実施形態と同様に、通信量測定部１１０によって計算（更新）され、Ｂｅｔｗｅｅｎｎｅｓｓ中心度は、Ｂｅｔｗｅｅｎｎｅｓｓ中心度計算部１５４によって計算（更新）される。
【０１０６】
Ｂｅｔｗｅｅｎｎｅｓｓ中心度計算部１５４は、各ノードのＢｅｔｗｅｅｎｎｅｓｓ中心度を計算し、その結果を隣接ノード重要度表１５０に登録する。
【０１０７】
以下、第５の実施形態のノード装置７０の動作について説明する。尚、第５の実施形態における、パケット受信時の動作およびパケット送信時の動作は、第２の実施形態の各動作（図３および図５を各々に参照）と同一であるため、省略する。また、第５の実施形態における故障発生時の動作（すなわち、通信量と中心度とを考慮して、各故障通知の送信を制御する動作）については、第３の実施形態（図１４参照）と同一であるため、省略する。従って、以下、Ｂｅｔｗｅｅｎｎｅｓｓ中心度の算出動作についてのみ説明する。
【０１０８】
図２２は、図２１に示すノード装置７０の動作例（Ｂｅｔｗｅｅｎｎｅｓｓ中心度の算出動作）を示すフローチャートである。
【０１０９】
Ｂｅｔｗｅｅｎｎｅｓｓ中心度計算部１５４は、トポロジ情報交換部１３４からトポロジ情報を取得する（ステップＳ６０）。Ｂｅｔｗｅｅｎｎｅｓｓ中心度計算部１５４は、以下の（式２）により、Ｂｅｔｗｅｅｎｎｅｓｓ中心度を計算する（ステップＳ６１）。
【０１１０】
（式２）
（式２）において、Ｂｅｔｗｅｅｎｎｅｓｓ（ｉ）はノードｉのＢｅｔｗｅｅｎｎｅｓｓ中心度を示し、Ｎはネットワーク内に存在するノード数を示し、Ｇはネットワーク内のノード集合を示し、ｎｊｋはノードｊとノードｋの間を繋ぐ最短路の数を示す。また、（式２）において、ｎｊｋ（ｉ）は、ノードｊを通過点とする、ノードｊとノードｋの間を繋ぐ最短路の数を示す。
【０１１１】
Ｂｅｔｗｅｅｎｎｅｓｓ中心度計算部１５４は、トポロジ情報に基づいて、ネットワーク内における全ノード数Ｎを計算する。また、Ｂｅｔｗｅｅｎｎｅｓｓ中心度計算部１５４は、ｊを自ノードの隣接ノード集合に属する変数とするとともに、ｋをネットワーク中の全ノード集合に属する変数とする。Ｂｅｔｗｅｅｎｎｅｓｓ中心度計算部１５４は、全てのｊ（ｊ≠ｉ）と全てのｋ（ｋ≠ｊ、ｋ≠ｉ）に対して、ｊをルートとする最短経路ツリーを求める。Ｂｅｔｗｅｅｎｎｅｓｓ中心度計算部１５４は、ｊからｋまでの総経路数をカウントし、その値をΣｎｊｋとする。Ｂｅｔｗｅｅｎｎｅｓｓ中心度計算部１５４は、上記のｊとｋ間の全経路のうち、ノードｉを含む経路の数をカウントし、その値をΣｎｊｋ（ｉ）とする。Ｂｅｔｗｅｅｎｎｅｓｓ中心度計算部１５４は、上記で求めた各値を（式２）に代入することにより、Ｂｅｔｗｅｅｎｎｅｓｓ（ｉ）を計算し、隣接ノード重要度表１５０に登録する（ステップＳ６２）。
【０１１２】
以上説明したＢｅｔｗｅｅｎｎｅｓｓ中心度の算出動作に関し、以下、具体的な例を挙げて説明する。例えば、図２０に示すネットワークを例に挙げて説明する。もちろん、本実施形態が適用されるネットワークは、図２０に記載されたネットワークに限定されることはない。
【０１１３】
図２０において、ネットワーク内に存在するノード数Ｎ＝６であり、各ノードｊ（ｊ≠Ｃ）とノードｋ間（ｋ≠ｊ、ｋ≠Ｃ）の総最短経路数ｎｊｋは、ＡＢ、ＡＤ、ＡＥ、ＡＦ、ＢＦ、ＢＤ、ＢＥ、ＤＦ、ＤＥの９経路である、そのうちノードＣを通過する経路数ｎｊｋ（Ｃ）は、ＡＤ、ＡＦ、ＡＥ、ＢＦ、ＢＤ、ＢＥの６経路である。従って、ノードＣのＢｅｔｗｅｅｎｅｓｓ中心度は、（式２）により、（６／９）／（（６−１）×（６−２））＝１／３０となる。
【０１１４】
尚、第５の実施形態における最短路の数の計算は、トポロジ情報やグラフ情報を元に、Ｄｉｊｋｓｔｒａ法などのアルゴリズムを用いることで計算することができる。
【０１１５】
尚、以上説明した第２〜第５の実施形態において、故障ノードは、自ノード（故障通知を異なるタイミングで送信するノード）に「隣接」するノード（すなわち、自ノード自らが故障を検出したノード）である場合を例に挙げたが、これはあくまで一例であって、故障ノードはこれに限定されない。例えば、故障ノードは、自ノードに隣接しないノード（例えば、２ホップ以上のノードであって、故障通知にて故障を知り得たノード）であってもよい。さらに、故障ノードは、隣接するノードと隣接しないノードとが混在していてもよい。
【０１１６】
また、以上説明した第１〜第５の実施形態は、制御プログラムに基づいて図示しないコンピュータ回路（例えば、ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ））によって制御され、動作するようにすることができる。その場合、これらの制御プログラムは、例えば、装置またはシステム内部の記憶媒体（例えば、ＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）やハードディスク等）、あるいは、外部の記憶媒体（例えば、リムーバブルメディアやリムーバブルディスク等）に記憶され、上記コンピュータ回路によって読み出され実行される。
【符号の説明】
【０１１７】
１０ ノード装置
１２ 送信タイミング調整部
２０、５０、６０、７０ ノード装置
２２、５２、６２、７２ 経路制御部
２４ パケット転送部
２６−１〜２６−ｎ ネットワークインタフェース
１００ 故障検知部
１０２ 故障数判定部
１０４ リアルタイムクロック
１０６、１３２、１４２、１５２ 故障通知遅延決定部
１０８、１３０、１４０、１５０ 隣接ノード重要度表
１１０ 通信量測定部
１１２ 故障通知部
１２０ 経路表
１３４ トポロジ情報交換部
１３６ 中心度計算部
１４４ Ｃｌｏｓｅｎｅｓｓ中心度計算部
１５４ Ｂｅｔｗｅｅｎｎｅｓｓ中心度計算部
【技術分野】
【０００１】
本発明は、ノード装置、ネットワークシステム、故障通知方法、およびコンピュータプログラムに関する。
【背景技術】
【０００２】
ネットワークにおいて、あるノード（例えば、ルータ）に故障が発生した場合、それを検知したノードは、故障ノードについての故障通知を他のノードに送信する。故障通知を受け取った他のノードは、故障ノードを迂回する新しい経路を再計算する。他のノードは、最新経路情報に基づいて、通信を継続させることができる。
【０００３】
しかしながら、例えば、ワーム攻撃、設定ミス、バグなどの原因により、多数のノードに同時に故障が発生した場合、ネットワーク内に大量の故障通知が一斉に発生することとなる。すなわち、各ノードに大量の故障通知が同時に通知されることとなる。これにより、各ノードの制御負荷（迂回経路の計算負荷）が増大することが予想される。制御負荷が増すと、ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）の過負荷やメモリ容量の不足等の危険性が高まり、さらなるノードの故障（例えば、ルータのクラッシュやセッションのリセット）が誘発される虞がある。事実、近年、このような障害が頻繁に発生していることが報告されている。
【０００４】
制御負荷の集中を軽減するための技術の一例として、Ｒｏｕｔｅ Ｆｌａｐ Ｄａｍｐｉｎｇ（非特許文献１）という技術を挙げることができる。この技術は、経路変更や、故障と復旧を頻繁に繰り返すノードに対して、一定時間が経過するまではその経路もしくはノードについての故障通知を転送させないというペナルティを与える技術である。
【０００５】
また、特許文献１は、通信装置に対して実行された措置の記録を参照して措置を決定することで、同一装置に対する同一措置を回避し、システムの処理性能低下を抑える技術について記載する。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００４−２６０７２９号公報
【非特許文献】
【０００７】
【非特許文献１】Ｃ． Ｖｉｌｌａｍｉｚａｒ、Ｒ． Ｃｈａｎｄｒａ、 Ｇｏｖｉｎｄａｎ、「ＢＧＰ Ｒｏｕｔｅ Ｆｌａｐ Ｄａｍｐｉｎｇ」、１９９８年１１月、ＲＦＣ
【発明の概要】
【発明が解決しようとする課題】
【０００８】
非特許文献１記載の技術は、ある一つのノードにおける頻繁な故障と復旧による制御負荷集中に対しては有効であるかもしれないが、上述したような多数のノードの一斉故障により発生する制御負荷集中の軽減に対してはあまり効果がないと考えられる。
【０００９】
また、特許文献１の技術は、同一装置に対する重複措置の実行については効果があるかもしれない。しかしながら、上述した、ノードの一斉故障に伴う故障通知の大量発生は、あくまで同一装置に対する同一措置ではないので、特許文献１の技術では、この問題を解決することは困難である。
【００１０】
本発明は、多数のノード装置が同時に故障した場合であってもネットワーク内での制御負荷集中を回避することが可能な、ノード装置、ネットワークシステム、故障通知方法、およびコンピュータプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１１】
本発明のノード装置は、自ノード装置と同一のネットワークシステムに含まれるノード装置のうちの少なくとも２つのノード装置の故障を検出した際、他のノード装置に対して、故障中の前記各ノード装置についての故障通知を異なるタイミングで送信する送信タイミング調整部を備える。
【００１２】
本発明のネットワークシステムは、複数のノード装置を含むネットワークシステムであって、前記ネットワークシステムに含まれるノード装置のうちの少なくとも２つのノード装置の故障が検出された際、前記所定のノード装置から他のノード装置に対して、故障中の前記各ノード装置についての故障通知を異なるタイミングで送信する。
【００１３】
本発明の故障通知方法は、複数のノード装置を含むネットワークシステムにおける故障通知方法であって、前記ネットワークシステムに含まれるノード装置のうちの少なくとも２つのノード装置の故障が検出された際、前記所定のノード装置から他のノード装置に対して、故障中の前記各ノード装置についての故障通知を異なるタイミングで送信する。
【００１４】
本発明のコンピュータプログラムは、複数のノード装置を含むネットワークシステムにおける所定のノード装置のコンピュータに、前記ネットワークシステムに含まれるノード装置のうちの少なくとも２つのノード装置の故障が検出された際、前記所定のノード装置から他のノード装置に対して、故障中の前記各ノード装置についての故障通知を異なるタイミングで送信する処理を、実行させる。
【発明の効果】
【００１５】
本発明によれば、多数のノード装置が同時に故障した場合であってもネットワーク内での制御負荷集中を回避することが可能となる。
【図面の簡単な説明】
【００１６】
【図１】本発明の第１の実施形態に係るノード装置の構成例を説明するためのブロック図である。
【図２】本発明の第２の実施形態に係るノード装置の構成例を説明するためのブロック図である。
【図３】図２に示すノード装置の動作例（パケット受信時の動作）を説明するためのフローチャートである。
【図４】図３に示すフローチャートの説明を補足するための補足図であり、（ａ）は、本説明で用いるネットワークの構成図（ノード接続図）であり、（ｂ）は、そのネットワークにおけるノード毎の通信量の変化例を示す表である。
【図５】図２に示すノード装置の動作例（パケット送信時の動作）を説明するためのフローチャートである。
【図６】図５に示すフローチャートの説明を補足するための補足図であり、（ａ）は、本説明で用いるネットワークの構成図（ノード接続図）であり、（ｂ）は、そのネットワークにおけるノード毎の通信量の変化例を示す表である。
【図７】図２に示すノード装置の動作例（故障発生時の動作）を説明するためのフローチャートである。
【図８】図７を用いて説明した故障発生時の動作に関してのより具体的な説明で使用されるネットワークの構成図（ノード接続図）である。
【図９】第２の実施形態に関し、図８におけるノードｎ１の隣接ノードの重要度の一例を示す表である。
【図１０】図８に示すネットワークにおいて故障が発生した場合の図である。
【図１１】中心度の考慮がされない場合における迂回通信トラフィックの例を示す図である。
【図１２】本発明の第３の実施形態に係るノード装置の構成例を説明するためのブロック図である。
【図１３】図１２に示すノード装置の動作例（次数の算出動作）を示すフローチャートである。
【図１４】図１２に示すノード装置の動作例（故障発生時の動作）を示すフローチャートである。
【図１５】第３の実施形態に関し、図８におけるノードｎ１の隣接ノードの重要度の一例を示す表である。
【図１６】第３の実施形態における故障通知の送信順序の決定条件例である。
【図１７】第３の実施形態による効果を説明するための図である。
【図１８】本発明の第４の実施形態に係るノード装置の構成例を説明するためのブロック図である。
【図１９】図１８に示すノード装置の動作例（Ｃｌｏｓｅｎｅｓｓ中心度の算出動作）を示すフローチャートである。
【図２０】第４の実施形態に関し、Ｃｌｏｓｅｎｅｓｓ中心度の計算の説明に用いるためのネットワークの構成例である。
【図２１】本発明の第５の実施形態に係るノード装置の構成例を説明するためのブロック図である。
【図２２】図２１に示すノード装置の動作例（Ｂｅｔｗｅｅｎｎｅｓｓ中心度の算出動作）を示すフローチャートである。
【発明を実施するための形態】
【００１７】
［第１の実施形態］
図１は、本発明の第１の実施形態に係るノード装置１０の構成例を説明するためのブロック図である。ノード装置１０は、ネットワークシステム（図１においては不図示）内に存在する所定のノード装置である。このネットワークシステムには、ノード装置１０以外に少なくとも２つ以上のノード装置が含まれる。ノード装置１０は、送信タイミング調整部１２を備える。送信タイミング調整部１２は、上記ネットワークシステムに含まれるノード装置のうちの少なくとも２つのノード装置の故障を検出した際、他のノード装置（故障中のノード装置以外のノード装置）に対して、故障中の各ノード装置についての故障通知を異なるタイミングで送信する。尚、上記において、故障ノードは、ノード装置１０に隣接しているノードであってもよく、隣接していないノード（例えば、２ホップ以上のノード）であってもよく、場合によっては、両者が混在していてもよい。
【００１８】
以上説明した第１の実施形態によれば、各故障ノード装置の故障通知は、時間方向に分散されて通知されるので、ワーム攻撃等により多数のノード装置に同時に故障が発生した場合であっても、所定のノード装置に対して大量の故障通知が同時に到達する事態を回避することができる。すなわち、ネットワーク内での制御負荷集中を回避することが可能となるため、さらなるノード装置の故障を阻止し、適切な経路制御を実行することが可能となる。
【００１９】
［第２の実施形態］
図２は、本発明の第２の実施形態に係るノード装置２０の構成例を説明するためのブロック図である。ノード装置２０は、経路制御部２２と、パケット転送部２４と、ネットワークインタフェース２６−１〜２６−ｎと、を少なくとも備える。
【００２０】
経路制御部２２は、故障検知部１００と、故障数判定部１０２と、リアルタイムクロック１０４と、故障通知遅延決定部１０６と、隣接ノード重要度表１０８と、通信量測定部１１０と、故障通知部１１２と、を少なくとも備える。
【００２１】
故障検知部１００は、ＯＳＰＦ（Ｏｐｅｎ Ｓｈｏｒｔｅｓｔ Ｐａｔｈ Ｆｉｒｓｔ）やＢＧＰ（Ｂｏｒｄｅｒ Ｇａｔｅｗａｙ Ｐｒｏｔｏｃｏｌ）などの経路制御プロトコルを使用して、ネットワークインタフェース２６−１〜２６−ｎに繋がっている、各リンク及び隣接ノードの故障を検知する。故障検知部１００は、例えば、隣接ノードから一定時間内に制御メッセージを受信しない場合、あるいは下位レイヤからの切断通知により、隣接ノードが故障していると判断する。尚、制御メッセージは、例えば、ＢＧＰの場合はＫｅｅｐ Ａｌｉｖｅメッセージであり、ＯＳＰＦの場合はＨｅｌｌｏメッセージである。故障を検知した場合、故障検知部１００は、故障が発生している隣接ノードについての情報である「故障ノード情報」を、故障数判定部１０２へ出力する。
【００２２】
故障数判定部１０２は、「故障ノード情報」に基づいて、隣接ノードの故障数を把握する。そして、故障数判定部１０２は、故障数に基づいて、各故障通知を異なるタイミングで送信するか、一斉に送信（通常の故障通知）するかを判断し、各々に、場合に応じた処理を実行する。具体的には、故障数が所定の閾値と等しいかあるいは超えている場合、故障数判定部１０２は、リアルタイムクロック１０４から「故障検知時刻情報」を取得する。そして、故障数判定部１０２は、「故障ノード情報」および「故障検知時刻情報」を、故障通知遅延決定部１０６へ出力する。一方、故障数が所定の閾値を下回る場合、故障数判定部１０２は、「故障ノード情報」を、故障通知部１１２へ出力する。
【００２３】
リアルタイムクロック１０４は、故障数判定部１０２のリクエストに応じて時刻情報を提供する。
【００２４】
故障通知遅延決定部１０６は、故障数判定部１０２から取得した「故障ノード情報」に基づいて、どの隣接ノードが故障しているかを把握し、それぞれの故障ノードの通信量を、隣接ノード重要度表１０８から取得する。そして、故障通知遅延決定部１０６は、得られた各故障ノードの通信量に基づいて各故障ノードの故障通知遅延時間を決定する。故障通知遅延決定部１０６は、少なくとも、「故障通知遅延時間情報」および「故障検知時刻情報」を、故障通知部１１２へ出力する。
【００２５】
隣接ノード重要度表１０８には、ネットワークに参加している各ノードについての重要度が記憶されている。第２の実施形態において、重要度は、各ノードとそれらに接続する各隣接ノードとの間の各通信量であるものとする。通信量の測定方法については、後述する。
【００２６】
通信量測定部１１０は、隣接ノードとの間の通信を監視し、その監視結果に基づいて、隣接ノード重要度表１０８の内容を更新する。具体的には、通信量測定部１１０は、ネットワークインタフェース２６−１〜２６−ｎに入ってくるパケット、もしくは、ネットワークインタフェース２６−１〜２６−ｎから出ていくパケットを観測し、隣接ノード重要度表１０８における各隣接ノードとの通信量をインクリメントする。また、通信量測定部１１０は、例えば、内部にタイマ（図２において不図示）を保持することができる。そして、通信量測定部１１０は、タイマ値が一定値以上となった場合、隣接ノード重要度表１０８における、所定の隣接ノードについての通信量を０にリセットすることもできる。
【００２７】
故障通知部１１２は、故障数判定部１０２からの「故障ノード情報」に基づいて、通常の故障通知（一斉通知）を行う。また、故障通知部１１２は、故障通知遅延決定部１０６からの「故障通知遅延時間情報」および「故障検知時刻情報」に基づいて、各故障通知を異なるタイミングで送信する処理を実行する。具体的には、故障通知部１１２は、上記各情報に基づいて、各故障ノードの故障通知送信時刻を決定する。故障通知部１１２は、各送信時刻となる度に、その都度、対応する故障通知を送信する。
【００２８】
パケット転送部２４は、経路表１２０を備える。経路表１２０には、ネットワーク内の各宛先ノードへパケットを送信するとき、最初に送信するノードについての情報が記載されている。
【００２９】
以下、第２の実施形態のノード装置２０の動作について説明する。パケット受信時の動作、パケット送信時の動作、および故障発生時の動作について、以下、順番に説明する。
【００３０】
図３は、図２に示すノード装置２０の動作例（パケット受信時の動作）を説明するためのフローチャートである。
【００３１】
まず、通信量測定部１１０は、ネットワークインタフェース２６−１〜２６−ｎのいずれかを介してパケット転送部２４がパケットを受信したか否かを判定する（ステップＳ１）。パケットが受信された場合（ステップＳ１においてＹｅｓ判定）、通信量測定部１１０は、受信したパケットのヘッダ情報を参照し、そのパケットを自分に転送したノードがどのノードであるかを特定する（ステップＳ２）。そして、通信量測定部１１０は、隣接ノード重要度表１０８において、特定したノードの通信量をインクリメントする（ステップＳ３）。ここで、インクリメントする値はどのような値であってもよい。本実施形態では、＋１する場合を例に挙げる。
【００３２】
通信量測定部１１０は、特定したノード（転送元のノード）の通信量をインクリメントした後、一定の時間が経過したか否かを判定する（ステップＳ４）。一定時間が経過しない場合（ステップＳ４においてＮｏ判定）、通信量測定部１１０は、新たなパケットの受信（ステップＳ１）あるいはパケット送信の有無（図３では不図示）を判定する。一方、一定時間が経過した場合（ステップＳ４においてＹｅｓ判定）、通信量測定部１１０は、そのノードの通信量に変化が有るか否かを判定する（ステップＳ５）。通信量に変化がある場合（ステップＳ５においてＹｅｓ判定）、図３に示す処理を終了する（再びステップＳ１の処理あるいはパケット送信の有無判定を行っても良い）。一方、通信量に変化が無い場合（ステップＳ５においてＮｏ判定）、通信量測定部１１０は、隣接ノード重要度表１０８において、そのノードの通信量を０にリセットする（ステップＳ６）。
【００３３】
図４は、図３に示すフローチャートの説明を補足するための補足図であり、具体的には、パケット受信時における通信量の測定について説明するための図である。図４（ａ）は、本説明で用いるネットワークの構成図（ノード接続図）であり、図４（ｂ）は、そのネットワークにおけるノード毎の通信量の変化例を示す表である。図４（ａ）を参照し、自己のノードＡには、隣接ノードＢ、Ｃが接続される。この場合、ノードＡは、ノードＢからパケットを受信するものとする。ここで、パケットの受信とは、ノードＡが最終宛先の場合と、ノードＡを中継する場合と、を含む。自己のノードＡがノードＢからパケットを受信した際、ノードＡの通信量測定部１１０は、隣接ノード重要度表１０８において、ノードＢの通信量を１つインクリメントする。具体的には、図４（ｂ）に示すように、ノードＢの通信量は、０（パケット受信前）から１（パケット受信後）へと変化する。
【００３４】
図５は、図２に示すノード装置２０の動作例（パケット送信時の動作）を説明するためのフローチャートである。
【００３５】
まず、通信量測定部１１０は、パケット転送部２４がネットワークインタフェース２６−１〜２６−ｎのいずれかにパケットを送信したか否かを判定する（ステップＳ１０）。パケットを送信した場合（ステップＳ１０においてＹｅｓ判定）、通信量測定部１１０は、経路表１２０を参照し、パケットの転送先ノードを特定する（ステップＳ１１）。そして、通信量測定部１１０は、隣接ノード重要度表１０８において、特定した転送先ノードの通信量をインクリメントする（ステップＳ１２）。ここで、パケット受信時と同様に、インクリメントする値はどのような値であってもよい。本実施形態では、＋１する場合を例に挙げる。
【００３６】
通信量測定部１１０は、所定のノード（転送先のノード）の通信量をインクリメントした後、一定の時間が経過したか否かを判定する（ステップＳ１３）。一定時間が経過しない場合（ステップＳ１３においてＮｏ判定）、通信量測定部１１０は、新たなパケットの送信（ステップＳ１０）あるいはパケット受信の有無（図５では不図示）を判定する。一方、一定時間が経過した場合（ステップＳ１３においてＹｅｓ判定）、通信量測定部１１０は、そのノードの通信量に変化が有るか否かを判定する（ステップＳ１４）。通信量に変化がある場合（ステップＳ１４においてＹｅｓ判定）、図５に示す処理を終了する（再びステップＳ１の処理あるいはパケット受信の有無判定を行っても良い）。一方、通信量に変化が無い場合（ステップＳ１４においてＮｏ判定）、通信量測定部１１０は、隣接ノード重要度表１０８において、そのノードの通信量を０にリセットする（ステップＳ１５）。
【００３７】
図６は、図５に示すフローチャートの説明を補足するための補足図であり、具体的には、パケット送信時における通信量の測定について説明するための図である。図６（ａ）は、本説明で用いるネットワークの構成図（ノード接続図）であり、図６（ｂ）は、そのネットワークにおけるノード毎の通信量の変化例を示す表である。図６（ａ）を参照し、自己のノードＡには、隣接ノードＢ、Ｃが接続される。この場合、ノードＡは、ノードＣにパケットを送信するものとする。ここで、パケットの送信とは、ノードＣが最終宛先の場合と、ノードＣを中継する場合と、を含む。自己のノードＡがノードＣにパケットを送信した際、ノードＡの通信量測定部１１０は、隣接ノード重要度表１０８において、ノードＣの通信量を１つインクリメントする。具体的には、図６（ｂ）に示すように、ノードＣの通信量は、０（パケット送信前）から１（パケット送信後）へと変化する。
【００３８】
図７は、図２に示すノード装置２０の動作例（故障発生時の動作）を説明するためのフローチャートである。
【００３９】
故障検知部１００は、隣接ノードの故障を検知する（ステップＳ２０）。この場合、故障検知部１００は、例えば、隣接ノードから一定時間内に制御メッセージを受信しない場合に隣接ノードが故障していると判断する。故障を検知した場合、故障検知部１００は、故障が発生している隣接ノードについての情報である「故障ノード情報」を、故障数判定部１０２へ出力する。
【００４０】
故障数判定部１０２は、「故障ノード情報」に基づいて隣接ノードの故障数を把握し、故障数が所定の閾値Ｋ以上か否かを判定する（ステップＳ２１）。故障数が閾値Ｋ未満の場合（ステップＳ２１においてＮｏ判定）、通常の故障通知（一斉通知）処理が実行される（ステップＳ２２）。具体的には、故障数判定部１０２は、「故障ノード情報」を、故障通知部１１２へ出力する。故障通知部１１２は、「故障ノード情報」における全ての故障ノードに対して、故障通知を一斉に送信する。
【００４１】
一方、故障数が閾値Ｋ以上の場合（ステップＳ２１においてＹｅｓ判定）、各故障通知を異なるタイミングで送信する処理が実行される。具体的には、故障数判定部１０２は、リアルタイムクロック１０４から「故障検知時刻情報」を取得する。そして、故障数判定部１０２は、「故障ノード情報」および「故障検知時刻情報」を、故障通知遅延決定部１０６へ出力する（ステップＳ２３）。
【００４２】
故障通知遅延決定部１０６は、各故障ノードの故障通知遅延時間を決定する（ステップＳ２４）。具体的には、故障通知遅延決定部１０６は、隣接ノード重要度表１０８から各故障ノードの通信量Ｘｉを取得し、これらの通信量Ｘｉに応じて、それぞれの故障ノードの故障通知遅延時間Ｄｉを決定する。そして、故障通知遅延決定部１０６は、故障通知遅延時間Ｄｉおよび故障検知時刻ｔを、故障通知部１１２へ出力する（ステップＳ２５）。
【００４３】
故障通知部１１２は、各故障ノードについて、故障通知の送信時刻を決定する（ステップＳ２６）。具体的には、故障通知部１１２は、各故障検知時刻ｔに各通知遅延Ｄｉを足した時刻を、各故障通知の送信時刻とする。故障通知部１１２は、各送信時刻となる度に、その都度、対応する故障通知を送信する（ステップＳ２７）。
【００４４】
以下、図７を用いて説明した故障発生時の動作に関し、より具体的な例を挙げて説明する。
【００４５】
図８は、本説明で用いるネットワークの構成図（ノード接続図）である。図８に示すように、対象ネットワークは、ネットワーク１と、ノードｎｉ（ｉ＝１〜９）から構成される。図８において、太い矢印は通信トラフィックのフローとその方向を示している。もちろん、本実施形態が適用されるネットワークは、図８に記載されたネットワークに限定されることはない。
【００４６】
ここで、ノードｎ１にとって、ノードｎ２、ノードｎ４、ノードｎ５の通信量が０であり、ノードｎ３とノードｎ８の通信量が９であると仮定する。従って、この場合、隣接ノード重要度表１０８において、自ノードｎ１の隣接ノードについての重要度は、図９のようになる。
【００４７】
図７のステップＳ２１において、閾値Ｋ＝２とする場合を例に挙げる。もちろん、この値は単なる一例であって、ネットワーク状況や規模に応じて、閾値Ｋは、どの値に設定してもよい。また、ステップＳ２４において、故障通知遅延時間をＤｉ＝１００／（Ｘｉ＋１）［ｍｓ］に設定する場合を例に挙げる。ここで、Ｘｉは、故障ノードｎｉ（この場合、ｉ＝１〜９）の各通信量を示し、Ｄｉは、各故障ノードの各故障通知遅延時間を示す。尚、上記計算式はあくまで一例であって、故障通知遅延時間を算出するための計算式は上記に限定されることはない。
【００４８】
図１０は、図８に示すネットワークにおいて故障が発生した場合の図である。図１０では、ノードｎ２、ノードｎ３、ノードｎ４が故障し、ノードｎ１が、これらの故障を時刻ｔにおいて検知した場合を例に挙げる。ここで、これらの故障通知を通常の方法にて送信する場合（すなわち、一斉送信する場合）、ノードｎ１は、ノードｎ２、ノードｎ３、ノードｎ４の故障通知を、ネットワーク内に同時に送信する。従って、ノードｎ８、ノードｎ９、およびネットワーク１にある全ノードに、経路再計算のための制御負荷が集中してしまう。しかしながら、第２の実施形態の通知方法（図７に示すフローチャートで示す方法）を適用した場合の動作は次のようになる。
【００４９】
以下、図８〜図１０に示す具体的な状況を、図７に示すフローチャートに当てはめて説明する。ノードｎ１の故障検知部１００は、ノードｎ２、ｎ３、ｎ４の故障を検知する（ステップＳ２０）。ノードｎ１の故障数判定部１０２は、故障数が所定の閾値Ｋ＝２以上か否かを判定する（ステップＳ２１）。この場合、故障ノード数は３であり閾値Ｋ＝２よりも大きい（ステップＳ２１においてＹｅｓ判定）。従って、ノードｎ１の故障数判定部１０２は、故障ノード情報（ノードｎ２、ｎ３、ｎ４のリスト）および故障検知時刻情報（リアルタイムクロック１０４から取得した時刻ｔ）を、故障通知遅延決定部１０６へ出力する（ステップＳ２３）。
【００５０】
故障通知遅延決定部１０６は、隣接ノード重要度表１０８から、自ノードに接続する隣接ノードのうち各故障ノードｎ２、ｎ３、ｎ４についての各通信量Ｘｉを取得し、これらの通信量Ｘｉに応じて、それぞれの故障ノードの故障通知遅延時間Ｄｉを決定する（ステップＳ２４）。ここで、ノードｎ２、ｎ３、ｎ４の各通信量は、０、９、０である（図９参照）。一方、上述した通り、故障通知遅延時間Ｄｉは、計算式Ｄｉ＝１００／（Ｘｉ＋１）［ｍｓ］によって計算される。従って、上記各通信量Ｘｉを該計算式に代入することにより、それぞれの故障ノードｎ２、ｎ３、ｎ４の各故障通知遅延時間Ｄｉは、１００ｍｓ、 １０ｍｓ、１００ｍｓとなる（ステップＳ２５）。
【００５１】
ノードｎ１は、ノードｎ３の故障通知時刻をｔ＋１０ｍｓと決定し、ノードｎ２、ｎ４の故障通知時刻をｔ＋１００ｍｓと決定する（ステップＳ２６）。ノードｎ１は、各故障通知を各時刻が到達する度に送信する（ステップＳ２７）。
【００５２】
以上説明した第２の実施形態によれば、各故障ノードの故障通知は、時間方向に分散されて通知されるので、ワーム攻撃等により多数のノードに同時に故障が発生した場合であっても、所定のノードに対して大量の故障通知が同時に到達する事態を回避することができる。すなわち、ネットワーク内での制御負荷集中を回避することが可能となるため、さらなるノード故障を阻止し、適切な経路制御を実行することが可能となる。
【００５３】
さらに、第２の実施形態の場合、各故障通知の送信タイミングは、ノードの重要度、例えば、通信量に基づいて決定される。従って、例えば、図９に示すノードｎ３のように、通信量が多いノードの故障通知を真っ先に伝搬させることが可能となる。これにより、重要度が高い経路（換言すれば、通信量の多い経路、あるいは頻繁に使用される経路）の復旧（すなわち、迂回路の再計算）を他の経路に先んじて優先的に実施することが可能となる。
【００５４】
さらに、以上説明した第２の実施形態では、故障ノードの数に基づいて、故障通知を異なるタイミングで送信するか、通常の故障通知（すなわち、一斉送信）を行うかを決定している。例えば、システムの規模を鑑みてある程度の数であれば故障通知を同時に送信しても問題ないと判断できる場合（換言すれば、処理負荷上、特に問題が発生しない場合）、故障通知を敢えて遅らせるよりも、できるだけ早く送ったほうがよい場合もあるからである。
【００５５】
尚、以上説明した第２の実施形態において、通信量と故障通知遅延時間とは必ずしも反比例（あるいは、通信量や計算式自体の設定によっては比例の場合もある）の関係にあるとは限らない。例えば、故障通知遅延決定部１０６は、故障ノードの通信量同士を比較し、該比較結果に応じて各故障通知の送信順序のみを決定し、故障通知遅延時間自体は定数（例えば、１００ｍｓ）とすることも可能である。例えば、故障通知送信の基準時刻をｔとした場合、各故障通知を、各時刻ｔ、ｔ＋１００ｍｓ、ｔ＋２００ｍｓ・・・に順次送信すればよい。このような方法でも、制御負荷集中の回避と重要度が高い経路の早期復旧を実現することが可能となる。
【００５６】
また、以上説明した図７のステップＳ２１における、故障数と閾値Ｋとの比較条件は、「以上」に限定されることはない。例えば、故障数と閾値Ｋとが等しい場合を除外する「より大きい」であってもよい。
【００５７】
［第３の実施形態］
第２実施形態において、ノードの重要度は、ノードの通信量のみに基づいている。もちろん、これにより、基本的には、制御負荷集中の回避と重要度が高い経路の早期復旧を実現することが可能となる。しかしながら、故障したノードの通信量自体は少ないが、他の故障ノードの迂回経路の通過点として選択される可能性が非常に高い（中心度が非常に高い）場合を想定すると、通信量のみの考慮では不十分な場合がある。
【００５８】
第２の実施形態の場合、例えば、図１０において、他ノード（ノードｎ８、ノードｎ９、あるいはネットワーク１内のノード）に対して、通信量の少ないノードｎ４の故障通知は、通信量の多いノードｎ３の故障通知よりも遅れて到着する。この場合、他ノードは、図１１に示すように、故障したノードｎ３を迂回する新しい経路として、故障したノードｎ４を経由した経路（すなわち、有効ではない経路）を選択してしまう虞がある。この場合、他ノードは、ノードｎ３を迂回する更なる別の経路を再計算しなければならないため、効率が低下する可能性がある。
【００５９】
そこで、第３の実施形態は、ノードの通信量だけでなくノードの中心度も考慮して、各故障通知の送信を制御する点を特徴とする。第３の実施形態では、中心度を、「自ノードに接続する隣接ノードに接続するノード数（次数）」とする場合を例に挙げる。
【００６０】
図１２は、本発明の第３の実施形態に係るノード装置５０の構成例を説明するためのブロック図である。ノード装置５０は、第２の実施形態のノード装置２０（図２参照）を基本としており、パケット転送部２４とネットワークインタフェース２６−１〜２６−ｎは、ノード装置２０と同一である。従って、これらについては図１２において図２と同一の参照符号を付し、ここでの説明を省略する。
【００６１】
また、経路制御部５２を構成する要素のうち、故障検知部１００と、故障数判定部１０２と、リアルタイムクロック１０４と、通信量測定部１１０と、故障通知部１１２とは、ノード装置２０の経路制御部２２におけるそれらと同一である。従って、これらについては図１２において図２と同一の参照符号を付し、ここでの説明を省略する。
【００６２】
従って、以下、経路制御部５２を構成する要素のうち、経路制御部２２と機能が異なる構成要素あるいは新規な構成要素、すなわち、隣接ノード重要度表１３０と、故障通知遅延決定部１３２と、トポロジ情報交換部１３４と、中心度計算部１３６とについてのみ説明する。
【００６３】
隣接ノード重要度表１３０には、ネットワークに参加している各ノードについての重要度が記憶されている。第３の実施形態において、重要度は、「通信量」と「中心度（次数）」を含む。ここで、通信量は、第２の実施形態と同様に、各ノードとそれらに接続する各隣接ノードとの間の各通信量（例えば、受信パケット数および／または送信パケット数）である。一方、中心度は、各隣接ノードに接続するノードの数（以下、これを次数と呼ぶ）である。この場合、次数には、自ノードも含まれる。尚、通信量は、第２の実施形態と同様に、通信量測定部１１０によって計算（更新）され、次数は、中心度計算部１３６によって計算（更新）される。
【００６４】
故障通知遅延決定部１３２は、通信量だけでなく、中心度（第３の実施形態の場合は、次数）も考慮して、故障ノードの故障通知の遅延を決定する。遅延決定処理の詳細については、後述する。
【００６５】
トポロジ情報交換部１３４は、隣接ノードからトポロジ情報を受信する。ここで、トポロジ情報とは、例えば、ネットワークの接続形態についての情報である。トポロジ情報交換部１３４は、新しいトポロジ情報が設定された場合、あるいはネットワークトポロジに変化があった場合、中心度計算部１３６に対して、トポロジ情報を渡す。
【００６６】
中心度計算部１３６は、トポロジ情報交換部１３４から得られたトポロジ情報を元に、各隣接ノードの次数を計算し、その結果を隣接ノード重要度表１３０に登録する。
【００６７】
以下、第３の実施形態のノード装置５０の動作について説明する。尚、第３の実施形態における、パケット受信時の動作およびパケット送信時の動作は、第２の実施形態の各動作（図３および図５を各々に参照）と同一であるため、省略する。従って、以下、次数の算出動作と故障発生時の動作について、以下、順番に説明する。
【００６８】
図１３は、図１２に示すノード装置の動作例（次数の算出動作）を示すフローチャートである。
【００６９】
中心度計算部１３６は、トポロジ情報交換部１１８からトポロジ情報を取得する（ステップＳ３０）。中心度計算部１３６は、各隣接ノードの次数を算出する（ステップＳ３１）。具体的には、中心度計算部１３６は、得られたトポロジ情報に基づいて、自ノードの各隣接ノードに接続する隣接ノード数を算出し、その値を次数とする。中心度計算部１３６は、算出された各隣接ノードの次数を隣接ノード重要度表１３０に登録する（ステップＳ３２）。
【００７０】
図１４は、図１２に示すノード装置の動作例（故障発生時の動作）を示すフローチャートである。尚、図１４に示すフローチャートにおける各処理ステップにおいて、図７に示す第２の実施形態のフローチャートと同一の処理ステップには図７と同一のステップ番号を付し、それらの説明については簡略化して説明する。
【００７１】
故障検知部１００は、隣接ノードの故障を検知する（ステップＳ２０）。故障を検知した場合、故障検知部１００は、「故障ノード情報」を、故障数判定部１０２へ出力する。故障数判定部１０２は、故障数が所定の閾値Ｋ以上か否かを判定する（ステップＳ２１）。故障数が閾値Ｋ未満の場合（ステップＳ２１においてＮｏ判定）、通常の故障通知（一斉通知）処理が実行される（ステップＳ２２）。
【００７２】
一方、故障数が閾値Ｋ以上の場合（ステップＳ２１においてＹｅｓ判定）、故障数判定部１０２は、リアルタイムクロック１０４から「故障検知時刻情報」を取得する。そして、故障数判定部１０２は、「故障ノード情報」および「故障検知時刻情報」を、故障通知遅延決定部１３２へ出力する（ステップＳ４３）。
【００７３】
故障通知遅延決定部１３２は、隣接ノード重要度表１３０から、各故障ノードの通信量および中心度（次数）を取得する（ステップＳ４４）。故障通知遅延決定部１３２は、、各故障ノードの通信量および中心度（次数）に基づいて、各故障ノードの故障通知を送信する順番を決定する（ステップＳ４５）。故障通知部１１２は、決定された送信順序に従って、各故障ノードの故障通知を送信する（ステップＳ４６）。
【００７４】
以上説明した故障発生時の動作に関し、以下、具体的な例を挙げて説明する。例えば、図８に示すネットワークを例に挙げて説明する。もちろん、本実施形態が適用されるネットワークは、図８に記載されたネットワークに限定されることはない。図９に示すように、自ノードｎ１にとって、ノードｎ２、ノードｎ４、ノードｎ５の通信量は０であり、ノードｎ３とノードｎ８の通信量は９である。ここで、自ノードｎ１の隣接ノードであるノードｎ２に接続する隣接ノード数は１つである（すなわち、自ノードｎ１のみ）。従って、ノードｎ２の次数は、１となる。また、図８において、自ノードｎ１に接続する他の隣接ノードｎ３、ノードｎ４、ノードｎ５、ノードｎ８のそれぞれに接続する隣接ノードの数は各２つであるため、それぞれのノードの次数は、２になる。すなわち、図８に示すネットワーク構成の場合、隣接ノード重要度表１３０において、自ノードｎ１に接続する隣接ノードの重要度は、図１５のようになる。
【００７５】
また、第２実施形態と同様、図１４のステップＳ４１において、閾値Ｋ＝２とする場合を例に挙げる。もちろん、この値は単なる一例であって、ネットワーク状況や規模に応じて、閾値Ｋは、どの値に設定してもよい。尚、以下の説明において、複数ノードが故障した際、制御負荷の分散のために、故障ノードの故障通知を複数回（具体的には２回）に分割して、送信する場合を想定する。また、以下の説明において、第２の実施形態と同様に、図１０に示す如く、ノードｎ２、ノードｎ３、ノードｎ４が故障し、ノードｎ１がこれらのノードについての故障通知の送信を制御する場合を例に挙げる。
【００７６】
図１４のステップＳ４５における故障ノード（ノードｎ２、ｎ３、ｎ４）の故障通知送信順序の条件の一例として、図１６に示す条件（条件１）を挙げる。尚、条件１はあくまで一例であって、送信順序の条件は、この条件１に限定されることはない。
【００７７】
すると、故障発生時、ノードｎ２に関しては、Ｘ２（ノードｎ２の通信量）＝０、Ｙ２（ノードｎ２の中心度（次数））＝１である（以上、図１５参照）。従って、条件１の式において、Ｘ２＋１０＊Ｙ２＝１０＜１５となるため、故障ノードｎ２の故障通知を後で送信すると判断する。
【００７８】
一方、ノードｎ３に関しては、Ｘ３（ノードｎ３の通信量）＝９、Ｙ３（ノードｎ３の中心度（次数））＝２である（以上、図１５参照）。従って、条件１の式において、Ｘ３＋１０＊Ｙ３＝２９＞１５となる。さらに、ノードｎ４に関しては、Ｘ４（ノードｎ４の通信量）＝０、Ｙ４（ノードｎ４の中心度（次数））＝２である（以上、図１５参照）。従って、条件１の式において、Ｘ４＋１０＊Ｙ４＝２０＞１５となる。以上から、故障ノードｎ３および故障ノードｎ４の故障通知を先に送信すると判断する。
【００７９】
図１７は、第３の実施形態による効果を説明するための図である。図１７に示すように、通信量および中心度（次数）の高い、ノードｎ３およびノードｎ４の故障通知を、他のノード（ノードｎ８、ノードｎ９、およびネットワーク１にいるノード）に対して、早くかつ同時に到着させることが可能となる。従って、これらの他のノードは、ノードｎ３とノードｎ４が同時に故障していることがわかるため、ノードｎ３を迂回する新しい通信経路を計算する際に、ノードｎ４を含むことなく他の適切な通信経路（例えば、ノードｎ５を通過する経路）を選択することが可能となる。
【００８０】
以上説明した第３の実施形態の場合、第２の実施形態と同様に、各故障ノードの故障通知は、時間方向に分散されて通知される。従って、ネットワーク内での制御負荷集中を回避することが可能となり、さらなるノード故障を阻止し、適切な経路制御を実行することが可能となる。
【００８１】
さらに、第３の実施形態の場合、各故障通知の送信タイミングは、ノードの重要度に基づいて決定される。従って、通信量が多いノードの故障通知を真っ先に伝搬させることが可能となる。
【００８２】
しかも、第３の実施形態の場合、通信量と中心度（次数）の両方を考慮して重要度を判断する。従って、例えば、重要度が一定以上の故障ノード（例えば、ノードｎ３とノードｎ４）の故障通知を、重要度が一定以下の故障ノード（例えば、ノードｎ２）の故障通知に先んじて、且つ、重要度が一定以上のもの同士を、同時に送信することが可能となる。従って、これらの故障通知を受信した他のノードは、故障ノードｎ３の有効な迂回経路を素早く計算することができるばかりでなく、故障ノードｎ４を避けることができるので、経路計算を１回で済ますことができる。すなわち、第３の実施形態によれば、通信効率の向上と経路計算効率の向上とを同時に達成することが可能となる。
【００８３】
［第４の実施形態］
第４の実施形態は、ノードの通信量だけでなくノードの中心度も考慮して重要度を判断する点は、第３の実施形態と同様である。第４の実施形態の、第３の実施形態に対する差異は、中心度として、「次数」の代わりに「Ｃｌｏｓｅｎｅｓｓ中心度」を用いる点にある。Ｃｌｏｓｅｎｅｓｓ中心度とは、あるノードからネットワークに存在する他ノードまでの最短距離（例えば、最小ホップ数）の合計値または各最短距離の平均値に、反比例する値のことである。
【００８４】
図１８は、第４の実施形態に係るノード装置６０の構成例を説明するためのブロック図である。ノード装置６０は、第３の実施形態のノード装置５０（図１２参照）を基本としており、パケット転送部２４とネットワークインタフェース２６−１〜２６−ｎは、ノード装置５０と同一である。従って、これらについては図１８において図１２と同一の参照符号を付し、ここでの説明を省略する。
【００８５】
また、経路制御部６２を構成する要素のうち、故障検知部１００と、故障数判定部１０２と、リアルタイムクロック１０４と、通信量測定部１１０と、故障通知部１１２と、トポロジ情報交換部１３４とは、ノード装置５０の経路制御部５２におけるそれらと同一である。従って、これらについては図１８において図１２と同一の参照符号を付し、ここでの説明を省略する。
【００８６】
従って、以下、経路制御部６２を構成する要素のうち、経路制御部５２と機能が異なる構成要素あるいは新規な構成要素、すなわち、隣接ノード重要度表１４０と、故障通知遅延決定部１４２と、Ｃｌｏｓｅｎｅｓｓ中心度計算部１４４とについてのみ説明する。
【００８７】
故障通知遅延決定部１４２は、通信量だけでなく、中心度（第４の実施形態の場合、Ｃｌｏｓｅｎｅｓｓ中心度）も考慮して、故障ノードの故障通知の遅延を決定する。尚、故障通知遅延決定部１４２における遅延決定処理は、参照する情報が、次数とＣｌｏｓｅｎｅｓｓ中心度の違いはあれど、基本的には、第３の実施形態の故障通知遅延決定部１３２と同じである。
【００８８】
隣接ノード重要度表１４０には、ネットワークに参加している各ノードについての重要度が記憶されている。第４の実施形態において、重要度は、「通信量」と「中心度（Ｃｌｏｓｅｎｅｓｓ中心度）」を含む。尚、通信量は、第２の実施形態と同様に、通信量測定部１１０によって計算（更新）され、Ｃｌｏｓｅｎｅｓｓ中心度は、Ｃｌｏｓｅｎｅｓｓ中心度計算部１４４によって計算（更新）される。
【００８９】
Ｃｌｏｓｅｎｅｓｓ中心度計算部１４４は、各ノードのＣｌｏｓｅｎｅｓｓ中心度を計算し、その結果を隣接ノード重要度表１４０に登録する。
【００９０】
以下、第４の実施形態のノード装置６０の動作について説明する。尚、第４の実施形態における、パケット受信時の動作およびパケット送信時の動作は、第２の実施形態の各動作（図３および図５を各々に参照）と同一であるため、省略する。また、第４の実施形態における故障発生時の動作（すなわち、通信量と中心度とを考慮して、各故障通知の送信を制御する動作）については、第３の実施形態（図１４参照）と同一であるため、省略する。従って、以下、Ｃｌｏｓｅｎｅｓｓ中心度の算出動作についてのみ説明する。
【００９１】
図１９は、図１８に示すノード装置の動作例（Ｃｌｏｓｅｎｅｓｓ中心度の算出動作）を示すフローチャートである。
【００９２】
Ｃｌｏｓｅｎｅｓｓ中心度計算部１４４は、トポロジ情報交換部１３４からトポロジ情報を取得する（ステップＳ５０）。Ｃｌｏｓｅｎｅｓｓ中心度計算部１４４は、以下の（式１）により、Ｃｌｏｓｅｎｅｓｓ中心度を計算する（ステップＳ５１）。
【００９３】
（式１）
（式１）において、Ｃｌｏｓｅｎｅｓｓ（ｉ）はノードｉのＣｌｏｓｅｎｅｓｓ中心度を示し、Ｎはネットワーク内に存在するノード数を示し、Ｇはネットワーク内のノード集合を示し、ｄｉｊはノードｉからノードｊまでの最短距離（例えば、最小ホップ数）を示す。
【００９４】
Ｃｌｏｓｅｎｅｓｓ中心度計算部１４４は、トポロジ情報に基づいて、ノードｊをネットワーク中の全ノード集合Ｇに属する変数とするとともに、ネットワーク内における全ノード数Ｎを求める。Ｃｌｏｓｅｎｅｓｓ中心度計算部１４４は、ノードｉをルートとする最短経路（例えば、最小ホップ数）パスツリーを計算する。Ｃｌｏｓｅｎｅｓｓ中心度計算部１４４は、全てのノードｊに対して、ノードｉからノードｊまでの最短距離（例えば、最小ホップ数）ｄｉｊを計算する。Ｃｌｏｓｅｎｅｓｓ中心度計算部１４４は、全てのノードｊに対してＣｌｏｓｅｎｅｓｓ（ｉ）を計算し、これらを隣接ノード重要度表１４０に登録する（ステップＳ５２）。
【００９５】
以上説明したＣｌｏｓｅｎｅｓｓ中心度の算出動作に関し、以下、具体的な例を挙げて説明する。例えば、図２０に示すネットワークを例に挙げて説明する。もちろん、本実施形態が適用されるネットワークは、図２０に記載されたネットワークに限定されることはない。
【００９６】
図２０において、ネットワーク内に存在するノード数Ｎ＝６であり、ネットワーク内のノード集合Ｇ＝［Ａ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ］である。ここで、ノードＣから各ノード（Ａ、Ｂ、Ｆ、Ｄ、Ｅ）までの最短距離（この場合、最小ホップ数）は、それぞれ、２、１、１、１、２となる。従って、ノードＣのＣｌｏｓｅｎｅｓｓ（Ｃ）は、（式１）により、（６−１）／（２＋１＋１＋１＋２）＝５／７となる。
【００９７】
また、ノードＡのＣｌｏｓｅｎｅｓｓ（Ａ）を計算する場合、ノードＡから各ノード（Ｂ、Ｃ、Ｄ、Ｅ、Ｆ）までの最短距離（この場合、最小ホップ数）は、それぞれ、１、２、３、４、３であるため、Ｃｌｏｓｅｎｅｓｓ（Ａ）は、（式１）により、（６−１）／（１＋２＋３＋４＋３）＝５／１３となる。
【００９８】
尚、Ｃｌｏｓｅｎｅｓｓ中心度の計算に用いる最短距離（例えば、最小ホップ数）は、経路表１２０の情報から直接求めるか、もしくは、トポロジ情報やグラフ情報を元に、Ｄｉｊｋｓｔｒａ法などのアルゴリズムを用いることで計算することができる。
【００９９】
また、第４の実施形態において、最短距離の例として最小ホップ数を挙げたが、最短距離はこれに限定されず、例えば、通信遅延（時間として表される距離情報）を用いてもよい。
【０１００】
［第５の実施形態］
第５の実施形態は、ノードの通信量だけでなくノードの中心度も考慮して重要度を判断する点は、第３および第４の実施形態と同様である。第５の実施形態の、第４の実施形態に対する差異は、中心度として、「Ｃｌｏｓｅｎｅｓｓ中心度」の代わりに「Ｂｅｔｗｅｅｎｎｅｓｓ中心度」を用いる点にある。Ｂｅｔｗｅｅｎｎｅｓｓ中心度とは、あるノードを通過する最短路の数、またはその数に比例する値のことである。
【０１０１】
図２１は、第５の実施形態に係るノード装置７０の構成例を説明するためのブロック図である。ノード装置７０は、第４の実施形態のノード装置６０（図１８参照）を基本としており、パケット転送部２４とネットワークインタフェース２６−１〜２６−ｎは、ノード装置６０と同一である。従って、これらについては図２１において図１８と同一の参照符号を付し、ここでの説明を省略する。
【０１０２】
また、経路制御部７２を構成する要素のうち、故障検知部１００と、故障数判定部１０２と、リアルタイムクロック１０４と、通信量測定部１１０と、故障通知部１１２と、トポロジ情報交換部１３４とは、ノード装置６０の経路制御部６２におけるそれらと同一である。従って、これらについては図２１において図１８と同一の参照符号を付し、ここでの説明を省略する。
【０１０３】
従って、以下、経路制御部７２を構成する要素のうち、経路制御部６２と機能が異なる構成要素あるいは新規な構成要素、すなわち、隣接ノード重要度表１５０と、故障通知遅延決定部１５２と、Ｂｅｔｗｅｅｎｎｅｓｓ中心度計算部１５４とについてのみ説明する。
【０１０４】
故障通知遅延決定部１５２は、通信量だけでなく、中心度（第５の実施形態の場合、Ｂｅｔｗｅｅｎｎｅｓｓ中心度）も考慮して、故障ノードの故障通知の遅延を決定する。尚、故障通知遅延決定部１５２における遅延決定処理は、参照する情報が、次数とＢｅｔｗｅｅｎｎｅｓｓ中心度の違いはあれど、基本的には、第３の実施形態の故障通知遅延決定部１３２と同じである。
【０１０５】
隣接ノード重要度表１５０には、ネットワークに参加している各ノードについての重要度が記憶されている。第５の実施形態において、重要度は、「通信量」と「中心度（Ｂｅｔｗｅｅｎｎｅｓｓ中心度）」を含む。尚、通信量は、第２の実施形態と同様に、通信量測定部１１０によって計算（更新）され、Ｂｅｔｗｅｅｎｎｅｓｓ中心度は、Ｂｅｔｗｅｅｎｎｅｓｓ中心度計算部１５４によって計算（更新）される。
【０１０６】
Ｂｅｔｗｅｅｎｎｅｓｓ中心度計算部１５４は、各ノードのＢｅｔｗｅｅｎｎｅｓｓ中心度を計算し、その結果を隣接ノード重要度表１５０に登録する。
【０１０７】
以下、第５の実施形態のノード装置７０の動作について説明する。尚、第５の実施形態における、パケット受信時の動作およびパケット送信時の動作は、第２の実施形態の各動作（図３および図５を各々に参照）と同一であるため、省略する。また、第５の実施形態における故障発生時の動作（すなわち、通信量と中心度とを考慮して、各故障通知の送信を制御する動作）については、第３の実施形態（図１４参照）と同一であるため、省略する。従って、以下、Ｂｅｔｗｅｅｎｎｅｓｓ中心度の算出動作についてのみ説明する。
【０１０８】
図２２は、図２１に示すノード装置７０の動作例（Ｂｅｔｗｅｅｎｎｅｓｓ中心度の算出動作）を示すフローチャートである。
【０１０９】
Ｂｅｔｗｅｅｎｎｅｓｓ中心度計算部１５４は、トポロジ情報交換部１３４からトポロジ情報を取得する（ステップＳ６０）。Ｂｅｔｗｅｅｎｎｅｓｓ中心度計算部１５４は、以下の（式２）により、Ｂｅｔｗｅｅｎｎｅｓｓ中心度を計算する（ステップＳ６１）。
【０１１０】
（式２）
（式２）において、Ｂｅｔｗｅｅｎｎｅｓｓ（ｉ）はノードｉのＢｅｔｗｅｅｎｎｅｓｓ中心度を示し、Ｎはネットワーク内に存在するノード数を示し、Ｇはネットワーク内のノード集合を示し、ｎｊｋはノードｊとノードｋの間を繋ぐ最短路の数を示す。また、（式２）において、ｎｊｋ（ｉ）は、ノードｊを通過点とする、ノードｊとノードｋの間を繋ぐ最短路の数を示す。
【０１１１】
Ｂｅｔｗｅｅｎｎｅｓｓ中心度計算部１５４は、トポロジ情報に基づいて、ネットワーク内における全ノード数Ｎを計算する。また、Ｂｅｔｗｅｅｎｎｅｓｓ中心度計算部１５４は、ｊを自ノードの隣接ノード集合に属する変数とするとともに、ｋをネットワーク中の全ノード集合に属する変数とする。Ｂｅｔｗｅｅｎｎｅｓｓ中心度計算部１５４は、全てのｊ（ｊ≠ｉ）と全てのｋ（ｋ≠ｊ、ｋ≠ｉ）に対して、ｊをルートとする最短経路ツリーを求める。Ｂｅｔｗｅｅｎｎｅｓｓ中心度計算部１５４は、ｊからｋまでの総経路数をカウントし、その値をΣｎｊｋとする。Ｂｅｔｗｅｅｎｎｅｓｓ中心度計算部１５４は、上記のｊとｋ間の全経路のうち、ノードｉを含む経路の数をカウントし、その値をΣｎｊｋ（ｉ）とする。Ｂｅｔｗｅｅｎｎｅｓｓ中心度計算部１５４は、上記で求めた各値を（式２）に代入することにより、Ｂｅｔｗｅｅｎｎｅｓｓ（ｉ）を計算し、隣接ノード重要度表１５０に登録する（ステップＳ６２）。
【０１１２】
以上説明したＢｅｔｗｅｅｎｎｅｓｓ中心度の算出動作に関し、以下、具体的な例を挙げて説明する。例えば、図２０に示すネットワークを例に挙げて説明する。もちろん、本実施形態が適用されるネットワークは、図２０に記載されたネットワークに限定されることはない。
【０１１３】
図２０において、ネットワーク内に存在するノード数Ｎ＝６であり、各ノードｊ（ｊ≠Ｃ）とノードｋ間（ｋ≠ｊ、ｋ≠Ｃ）の総最短経路数ｎｊｋは、ＡＢ、ＡＤ、ＡＥ、ＡＦ、ＢＦ、ＢＤ、ＢＥ、ＤＦ、ＤＥの９経路である、そのうちノードＣを通過する経路数ｎｊｋ（Ｃ）は、ＡＤ、ＡＦ、ＡＥ、ＢＦ、ＢＤ、ＢＥの６経路である。従って、ノードＣのＢｅｔｗｅｅｎｅｓｓ中心度は、（式２）により、（６／９）／（（６−１）×（６−２））＝１／３０となる。
【０１１４】
尚、第５の実施形態における最短路の数の計算は、トポロジ情報やグラフ情報を元に、Ｄｉｊｋｓｔｒａ法などのアルゴリズムを用いることで計算することができる。
【０１１５】
尚、以上説明した第２〜第５の実施形態において、故障ノードは、自ノード（故障通知を異なるタイミングで送信するノード）に「隣接」するノード（すなわち、自ノード自らが故障を検出したノード）である場合を例に挙げたが、これはあくまで一例であって、故障ノードはこれに限定されない。例えば、故障ノードは、自ノードに隣接しないノード（例えば、２ホップ以上のノードであって、故障通知にて故障を知り得たノード）であってもよい。さらに、故障ノードは、隣接するノードと隣接しないノードとが混在していてもよい。
【０１１６】
また、以上説明した第１〜第５の実施形態は、制御プログラムに基づいて図示しないコンピュータ回路（例えば、ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ））によって制御され、動作するようにすることができる。その場合、これらの制御プログラムは、例えば、装置またはシステム内部の記憶媒体（例えば、ＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）やハードディスク等）、あるいは、外部の記憶媒体（例えば、リムーバブルメディアやリムーバブルディスク等）に記憶され、上記コンピュータ回路によって読み出され実行される。
【符号の説明】
【０１１７】
１０ ノード装置
１２ 送信タイミング調整部
２０、５０、６０、７０ ノード装置
２２、５２、６２、７２ 経路制御部
２４ パケット転送部
２６−１〜２６−ｎ ネットワークインタフェース
１００ 故障検知部
１０２ 故障数判定部
１０４ リアルタイムクロック
１０６、１３２、１４２、１５２ 故障通知遅延決定部
１０８、１３０、１４０、１５０ 隣接ノード重要度表
１１０ 通信量測定部
１１２ 故障通知部
１２０ 経路表
１３４ トポロジ情報交換部
１３６ 中心度計算部
１４４ Ｃｌｏｓｅｎｅｓｓ中心度計算部
１５４ Ｂｅｔｗｅｅｎｎｅｓｓ中心度計算部
【特許請求の範囲】
【請求項１】
自ノード装置と同一のネットワークシステムに含まれるノード装置のうちの少なくとも２つのノード装置の故障を検出した際、他のノード装置に対して、故障中の前記各ノード装置についての故障通知を異なるタイミングで送信する送信タイミング調整部を備えることを特徴とするノード装置。
【請求項２】
前記送信タイミング調整部は、前記各故障ノード装置の重要度に基づいて、前記各故障通知の送信タイミングを決定することを特徴とする請求項１記載のノード装置。
【請求項３】
前記重要度は、少なくとも、前記各故障ノード装置の通信量を考慮して決定されることを特徴とする請求項２記載のノード装置。
【請求項４】
前記重要度は、少なくとも、前記各故障ノード装置に隣接するノード装置の数を考慮して決定されることを特徴とする請求項２または３記載のノード装置。
【請求項５】
前記重要度は、少なくとも、所定のノード装置からネットワーク内に存在する他のノード装置までの距離を考慮して決定されることを特徴とする請求項２〜４のいずれか１項に記載のノード装置。
【請求項６】
前記重要度は、少なくとも、ネットワーク内に存在するノード装置のうちで所定のノード装置を除くノード装置間の総最短経路数のうちで前記所定のノード装置を通過する最短経路数を考慮して決定されることを特徴とする請求項２〜５のいずれか１項に記載のノード装置。
【請求項７】
前記送信タイミング調整部は、故障中のノード装置の重要度同士を比較し、該比較結果に応じて、各故障通知の送信順序を決定することを特徴とする請求項２〜８のいずれか１項に記載のノード装置。
【請求項８】
複数のノード装置を含むネットワークシステムであって、
前記ネットワークシステムに含まれるノード装置のうちの少なくとも２つのノード装置の故障が検出された際、前記所定のノード装置から他のノード装置に対して、故障中の前記各ノード装置についての故障通知を異なるタイミングで送信することを特徴とするネットワークシステム。
【請求項９】
複数のノード装置を含むネットワークシステムにおける故障通知方法であって、
前記ネットワークシステムに含まれるノード装置のうちの少なくとも２つのノード装置の故障が検出された際、前記所定のノード装置から他のノード装置に対して、故障中の前記各ノード装置についての故障通知を異なるタイミングで送信することを特徴とする故障通知方法。
【請求項１０】
複数のノード装置を含むネットワークシステムにおける所定のノード装置のコンピュータに、
前記ネットワークシステムに含まれるノード装置のうちの少なくとも２つのノード装置の故障が検出された際、前記所定のノード装置から他のノード装置に対して、故障中の前記各ノード装置についての故障通知を異なるタイミングで送信する処理を、
実行させることを特徴とするコンピュータプログラム。
【請求項１】
自ノード装置と同一のネットワークシステムに含まれるノード装置のうちの少なくとも２つのノード装置の故障を検出した際、他のノード装置に対して、故障中の前記各ノード装置についての故障通知を異なるタイミングで送信する送信タイミング調整部を備えることを特徴とするノード装置。
【請求項２】
前記送信タイミング調整部は、前記各故障ノード装置の重要度に基づいて、前記各故障通知の送信タイミングを決定することを特徴とする請求項１記載のノード装置。
【請求項３】
前記重要度は、少なくとも、前記各故障ノード装置の通信量を考慮して決定されることを特徴とする請求項２記載のノード装置。
【請求項４】
前記重要度は、少なくとも、前記各故障ノード装置に隣接するノード装置の数を考慮して決定されることを特徴とする請求項２または３記載のノード装置。
【請求項５】
前記重要度は、少なくとも、所定のノード装置からネットワーク内に存在する他のノード装置までの距離を考慮して決定されることを特徴とする請求項２〜４のいずれか１項に記載のノード装置。
【請求項６】
前記重要度は、少なくとも、ネットワーク内に存在するノード装置のうちで所定のノード装置を除くノード装置間の総最短経路数のうちで前記所定のノード装置を通過する最短経路数を考慮して決定されることを特徴とする請求項２〜５のいずれか１項に記載のノード装置。
【請求項７】
前記送信タイミング調整部は、故障中のノード装置の重要度同士を比較し、該比較結果に応じて、各故障通知の送信順序を決定することを特徴とする請求項２〜８のいずれか１項に記載のノード装置。
【請求項８】
複数のノード装置を含むネットワークシステムであって、
前記ネットワークシステムに含まれるノード装置のうちの少なくとも２つのノード装置の故障が検出された際、前記所定のノード装置から他のノード装置に対して、故障中の前記各ノード装置についての故障通知を異なるタイミングで送信することを特徴とするネットワークシステム。
【請求項９】
複数のノード装置を含むネットワークシステムにおける故障通知方法であって、
前記ネットワークシステムに含まれるノード装置のうちの少なくとも２つのノード装置の故障が検出された際、前記所定のノード装置から他のノード装置に対して、故障中の前記各ノード装置についての故障通知を異なるタイミングで送信することを特徴とする故障通知方法。
【請求項１０】
複数のノード装置を含むネットワークシステムにおける所定のノード装置のコンピュータに、
前記ネットワークシステムに含まれるノード装置のうちの少なくとも２つのノード装置の故障が検出された際、前記所定のノード装置から他のノード装置に対して、故障中の前記各ノード装置についての故障通知を異なるタイミングで送信する処理を、
実行させることを特徴とするコンピュータプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【公開番号】特開２０１２−１００９２（Ｐ２０１２−１００９２Ａ）
【公開日】平成２４年１月１２日（２０１２．１．１２）
【国際特許分類】
【出願番号】特願２０１０−１４４０２７（Ｐ２０１０−１４４０２７）
【出願日】平成２２年６月２４日（２０１０．６．２４）
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【Ｆターム（参考）】
【公開日】平成２４年１月１２日（２０１２．１．１２）
【国際特許分類】
【出願日】平成２２年６月２４日（２０１０．６．２４）
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【Ｆターム（参考）】
[ Back to top ]