(57)【要約】【課題】マルチパスルーティングをサポートしたネットワークで、各ノードが宛先ノードへメッセージを送信する際に、複数のリンクについて送信を試行する順序を、ネットワークの各構成要素の稼働率を考慮してより適切に決定する技術を提供する。【解決手段】本発明に係る方法では、ネットワークのトポロジ情報に基づいて、各ノードに接続された各リンクを用いた場合にメッセージが各ノードから宛先ノードに到達する条件を表す、各リンクに対応する論理式を生成する。また、各ノードに接続された複数のリンクから成る集合の部分集合ごとに、当該部分集合のいずれかのリンクを用いた場合にメッセージが宛先ノードに到達する条件を表す、各部分集合に対応する論理式を生成する。更に、生成された各部分集合に対応する論理式と、ネットワーク内の各構成要素の稼働率とに基づいて、各ノードについての送信試行順序を決定する。【選択図】図１
2015029223.tif 000002
【特許請求の範囲】
【請求項１】
ノード及びリンクを構成要素として含むネットワークにおいて、ノードに接続された複数のリンクのそれぞれを用いて当該ノードが宛先ノードへのメッセージの送信を順に試行するための送信試行順序を決定する方法であって、
宛先ノードまでのパスに存在する各構成要素が稼働しているか否かを示す論理変数を用いて記述され、かつ、各ノードに接続された複数のリンクのそれぞれを用いて当該ノードがメッセージを送信した場合に当該メッセージが前記宛先ノードに到達する条件を表す、各リンクに対応する論理式を、前記ネットワーク内の構成要素の接続関係を示すトポロジ情報に基づいて生成する第１の生成ステップと、
各ノードに接続された複数のリンクから成る集合の各部分集合に含まれるいずれかのリンクを用いた場合にメッセージが前記宛先ノードに到達する条件を表す、各部分集合に対応する論理式を、前記第１の生成ステップで生成された各リンクに対応する論理式に基づいて生成する第２の生成ステップと、
前記送信試行順序の決定対象となる対象ノードについて前記第２の生成ステップで生成された各部分集合に対応する論理式に、前記ネットワーク内の各構成要素についての予め定められた稼働率を適用することで、各部分集合を用いた場合にメッセージが前記対象ノードから前記宛先ノードに到達する確率を表す到達率を算出し、算出した前記到達率に応じて、前記対象ノードについての前記送信試行順序を決定する決定ステップと
を含むことを特徴とする方法。
【請求項２】
前記決定ステップでは、前記第２の生成ステップで生成された論理式が真になる確率を、前記到達率として算出することを特徴とする請求項１に記載の方法。
【請求項３】
前記決定ステップでは、前記第２の生成ステップで生成された論理式に含まれる各論理変数に、当該論理変数に対応するノードまたはリンクについての稼働率を適用することで、当該論理式が真になる確率を算出することを特徴とする請求項２に記載の方法。
【請求項４】
前記決定ステップで決定された前記送信試行順序を示す情報を前記対象ノードに送信する送信ステップを更に含むことを特徴とする請求項１から３のいずれか１項に記載の方法。
【請求項５】
前記決定ステップでは、前記対象ノードに接続された複数のリンクについての前記送信試行順序を、送信を先に試行すべきリンクから順に１つずつ決定することを特徴とすることを特徴とする請求項１から４のいずれか１項に記載の方法。
【請求項６】
前記決定ステップでは、
前記送信試行順序の決定を開始する際には空集合であり、かつ、１つ以上のリンクについて順序が既に決定されている場合には当該１つ以上のリンクを含む第１の部分集合に対して、順序が決定されていないリンクをそれぞれ新たなリンクとして加えて得られる１つ以上の第２の部分集合のそれぞれについて、当該第２の部分集合に対応する、前記第２の生成ステップで生成された論理式に基づいて、前記到達率を算出する処理と、
前記１つ以上の第２の部分集合のうち、算出した前記到達率が最大となる第２の部分集合に含まれる前記新たなリンクを、前記第１の部分集合に含まれる１つ以上のリンクの次に送信を試行すべきリンクとして決定する処理と
を繰り返すことによって、前記対象ノードに接続された複数のリンクについての前記送信試行順序を決定する
ことを特徴とする請求項５に記載の方法。
【請求項７】
前記第１の生成ステップは、
各ノードについて、当該ノードに接続された複数のリンクのそれぞれに対応する論理式が生成されると、生成された論理式の論理和を、各ノードがメッセージを送信した場合に当該メッセージが前記宛先ノードに到達する条件を表す、各ノードに対応する論理式として生成するステップを含み、
前記第１の生成ステップでは、前記宛先ノードに近いノードから順に、各ノードについて、隣接するノードに対応する論理式を用いて、当該ノードに接続された各リンクに対応する論理式を生成する
ことを特徴とする請求項１から６のいずれか１項に記載の方法。
【請求項８】
前記第１の生成ステップでは、前記宛先ノードに近いノードから順に、各ノードに接続された複数のリンクのそれぞれについて、当該ノードに対応する前記論理変数と、当該リンクに対応する前記論理変数と、当該リンクを介して当該ノードに隣接するノードに対応する論理式との論理積を、当該リンクに対応する論理式として生成する
ことを特徴とする請求項７に記載の方法。
【請求項９】
前記第１の生成ステップでは、前記ネットワーク内の各ノードに接続された各リンクに対応する論理式の生成を所定の回数だけ繰り返すことで、各リンクに対応する論理式を繰り返し更新する
ことを特徴とする請求項７または８に記載の方法。
【請求項１０】
前記所定の回数は、前記ネットワーク内のパス長の上限から１減算した数に等しいことを特徴とする請求項９に記載の方法。
【請求項１１】
前記第２の生成ステップでは、各部分集合に含まれる各リンクについて前記第１の生成ステップで生成された論理式の論理和を、当該部分集合に対応する論理式として生成することを特徴とする請求項１から１０のいずれか１項に記載の方法。
【請求項１２】
ノード及びリンクを構成要素として含むネットワークにおいて、ノードに接続された複数のリンクのそれぞれを用いて当該ノードが宛先ノードへのメッセージの送信を順に試行するための送信試行順序を決定する方法であって、
宛先ノードまでのパスに存在する各構成要素が稼働しているか否かを示す論理変数を用いて記述され、かつ、各ノードに接続された複数のリンクのそれぞれを用いて当該ノードがメッセージを送信した場合に当該メッセージが前記宛先ノードに到達する条件を表す、各リンクに対応する論理式であって、前記ネットワーク内の構成要素の接続関係を示すトポロジ情報に基づいて生成された論理式を取得する取得ステップと、
自ノードに接続された複数のリンクから成る集合の各部分集合に含まれるいずれかのリンクを用いた場合にメッセージが前記宛先ノードに到達する条件を表す、各部分集合に対応する論理式を、前記取得ステップで取得された各リンクに対応する論理式に基づいて生成する生成ステップと、
前記生成ステップで生成された各部分集合に対応する論理式に、前記ネットワーク内の各構成要素についての予め定められた稼働率を適用することで、各部分集合を用いた場合にメッセージが前記自ノードから前記宛先ノードに到達する確率を表す到達率を算出し、算出した前記到達率に応じて、前記自ノードについての前記送信試行順序を決定する決定ステップと
を含むことを特徴とする方法。
【請求項１３】
前記取得ステップでは、各リンクに対応する論理式を、前記ネットワーク内の別のノードから、または前記自ノードが備える記憶手段から取得することを特徴とする請求項１２に記載の方法。
【請求項１４】
ノード及びリンクを構成要素として含むネットワークにおいて、ノードに接続された複数のリンクのそれぞれを用いて当該ノードが宛先ノードへのメッセージの送信を順に試行するための送信試行順序を決定する方法であって、
宛先ノードまでのパスに存在する各構成要素が稼働しているか否かを示す論理変数を用いて記述され、かつ、自ノードに接続された複数のリンクから成る集合の各部分集合に含まれるいずれかのリンクを用いた場合にメッセージが前記宛先ノードに到達する条件を表す、各部分集合に対応する論理式を取得する取得ステップと、
前記取得ステップで取得された各部分集合に対応する論理式に、前記ネットワーク内の各構成要素についての予め定められた稼働率を適用することで、各部分集合を用いた場合にメッセージが前記自ノードから前記宛先ノードに到達する確率を表す到達率を算出し、算出した前記到達率に応じて、前記自ノードについての前記送信試行順序を決定する決定ステップと
を含むことを特徴とする方法。
【請求項１５】
前記取得ステップでは、各部分集合に対応する論理式を、前記ネットワーク内の別のノードから、または前記自ノードが備える記憶手段から取得することを特徴とする請求項１４に記載の方法。
【請求項１６】
請求項１から１５のいずれか１項に記載の方法の各ステップをコンピュータに実行させるためのプログラム。
【請求項１７】
ノード及びリンクを構成要素として含むネットワークにおいて、ノードに接続された複数のリンクのそれぞれを用いて当該ノードが宛先ノードへのメッセージの送信を順に試行するための送信試行順序を決定する装置であって、
宛先ノードまでのパスに存在する各構成要素が稼働しているか否かを示す論理変数を用いて記述され、かつ、各ノードに接続された複数のリンクのそれぞれを用いて当該ノードがメッセージを送信した場合に当該メッセージが前記宛先ノードに到達する条件を表す、各リンクに対応する論理式を、前記ネットワーク内の構成要素の接続関係を示すトポロジ情報に基づいて生成する第１の生成手段と、
各ノードに接続された複数のリンクから成る集合の各部分集合に含まれるいずれかのリンクを用いた場合にメッセージが前記宛先ノードに到達する条件を表す、各部分集合に対応する論理式を、前記第１の生成手段によって生成された各リンクに対応する論理式に基づいて生成する第２の生成手段と、
前記送信試行順序の決定対象となる対象ノードについて前記第２の生成手段によって生成された各部分集合に対応する論理式に、前記ネットワーク内の各構成要素についての予め定められた稼働率を適用することで、各部分集合を用いた場合にメッセージが前記対象ノードから前記宛先ノードに到達する確率を表す到達率を算出し、算出した前記到達率に応じて、前記対象ノードについての前記送信試行順序を決定する決定手段と
を備えることを特徴とする装置。
【請求項１８】
前記決定手段によって決定された前記送信試行順序を示す情報を前記対象ノードに送信する送信手段を更に備えることを特徴とする請求項１７に記載の装置。
【請求項１９】
ノード及びリンクを構成要素として含むネットワークにおいて、ノードに接続された複数のリンクのそれぞれを用いて当該ノードが宛先ノードへのメッセージの送信を順に試行するための送信試行順序を決定する装置であって、
宛先ノードまでのパスに存在する各構成要素が稼働しているか否かを示す論理変数を用いて記述され、かつ、各ノードに接続された複数のリンクのそれぞれを用いて当該ノードがメッセージを送信した場合に当該メッセージが前記宛先ノードに到達する条件を表す、各リンクに対応する論理式であって、前記ネットワーク内の構成要素の接続関係を示すトポロジ情報に基づいて生成された論理式を取得する取得手段と、
自ノードに接続された複数のリンクから成る集合の各部分集合に含まれるいずれかのリンクを用いた場合にメッセージが前記宛先ノードに到達する条件を表す、各部分集合に対応する論理式を、前記取得手段によって取得された各リンクに対応する論理式に基づいて生成する生成手段と、
前記生成手段によって生成された各部分集合に対応する論理式に、前記ネットワーク内の各構成要素についての予め定められた稼働率を適用することで、各部分集合を用いた場合にメッセージが前記自ノードから前記宛先ノードに到達する確率を表す到達率を算出し、算出した前記到達率に応じて、前記自ノードについての前記送信試行順序を決定する決定手段と
を備えることを特徴とする装置。
【請求項２０】
前記取得手段は、各リンクに対応する論理式を、前記ネットワーク内の別のノードから、または前記自ノードが備える記憶手段から取得することを特徴とする請求項１９に記載のノード。
【請求項２１】
ノード及びリンクを構成要素として含むネットワークにおいて、ノードに接続された複数のリンクのそれぞれを用いて当該ノードが宛先ノードへのメッセージの送信を順に試行するための送信試行順序を決定する装置であって、
宛先ノードまでのパスに存在する各構成要素が稼働しているか否かを示す論理変数を用いて記述され、かつ、自ノードに接続された複数のリンクから成る集合の各部分集合に含まれるいずれかのリンクを用いた場合にメッセージが前記宛先ノードに到達する条件を表す、各部分集合に対応する論理式を取得する取得手段と、
前記取得手段によって取得された各部分集合に対応する論理式に、前記ネットワーク内の各構成要素についての予め定められた稼働率を適用することで、各部分集合を用いた場合にメッセージが前記自ノードから前記宛先ノードに到達する確率を表す到達率を算出し、算出した前記到達率に応じて、前記自ノードについての前記送信試行順序を決定する決定手段と
を備えることを特徴とする装置。
【請求項２２】
前記取得手段は、各部分集合に対応する論理式を、前記ネットワーク内の別のノードから、または前記自ノードが備える記憶手段から取得することを特徴とする請求項２０に記載のノード。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信ネットワーク内の各ノードが宛先ノードへメッセージを送信する際に、接続された複数のリンクについて送信を試行する順序を決定する技術に関する。
【背景技術】
【０００２】
通信ネットワークにおいては、あるノードから宛先ノードにメッセージを送信する際に、宛先ノードにメッセージが到達するまでの遅延、及び使用するネットワーク資源を最小化する一方、宛先ノードにメッセージが到達する確率を最大化することが必要である。これを達成するために、従来の通信ネットワークでは、例えば最短パスルーティング（非特許文献１及び２）が用いられている。
【０００３】
図１は、通信ネットワークの一例を示しており、ここでは一例としてノードｖ1がノードｖ8を宛先としてメッセージを送信する場合を想定する。この場合、ｖ1からｖ8に至るパスとして、以下の３つのパスが存在する。
パス１：ｖ1→ｅ1→ｖ2→ｅ2→ｖ3→ｅ3→ｖ8
パス２：ｖ1→ｅ4→ｖ4→ｅ5→ｖ2→ｅ2→ｖ3→ｅ3→ｖ8
パス３：ｖ1→ｅ6→ｖ5→ｅ7→ｖ6→ｅ8→ｖ7→ｅ9→ｖ3→ｅ3→ｖ8
図１に示す通信ネットワークでは、ｖ1は、最短パスルーティングによってｖ8へメッセージを送信する場合、最短のパス１に沿ったリンクｅ1へメッセージを送信する。これにより、遅延及び使用するネットワーク資源が最小となる。
【０００４】
また、ｖ1及びｖ8を除くネットワークの各構成要素（ノードまたはリンク）の稼働率を０．９と仮定する。パス１を使用する場合、ｖ1からｖ8へ送信されたメッセージは、５個の構成要素（３本のリンク及び２台のノード）を経由する。この場合、ｖ8にメッセージが到達する確率を表す到達率は０．９5≒０．５９となる。この到達率は、パス２を使用する場合の到達率０．９7≒０．４９、及びパス３を使用する場合の到達率０．９9≒０．３９よりも大きい。したがって、パス１の選択は、到達率の観点でも最適な選択となる。この例は、送信元ノードがメッセージを送信するために単一のパスを選択するシングルパスルーティングに相当し、到達率の限界は、パス１を選択した場合の０．５９である。
【０００５】
一方、近年では、複数のパスを活用するマルチパスルーティングを用いることで、宛先ノードへのメッセージの到達率を高める方法が検討されている（非特許文献３）。マルチパスルーティングでは、宛先ノードにメッセージが到達するまで、複数のパスのそれぞれについて送信を順に試行する。上記の例の場合、例えば、ｖ1は、まずパス１での送信を試し、宛先ノードにメッセージが到達しない場合には、次にパス２での送信を試す。それでも宛先ノードにメッセージが到達しない場合、ｖ1は、パス３での送信を試す。このように複数のパスを活用した場合、宛先ノードへのメッセージの到達率は、０．７２まで向上する。
【０００６】
しかし、このようなマルチパスルーティングでは、宛先ノードにメッセージが到達するまで、複数のパスのそれぞれについて送信を順に試行するため、メッセージが宛先ノードに到達するまでの遅延が増大する。遅延の増大をできる限り抑えるためには、送信元のノードが複数のパスについて送信を試行する順序を適切に決定することが重要である。上記の例の場合、送信を試行する最適な順序は、パス１、２、３の順ではなく、パス１、３、２の順となる。これは、パス１を構成する５個の構成要素のうちの４個の構成要素はパス２と共有されており、パス１でメッセージが宛先ノードに到達しなかった場合、パス２でも到達しない可能性が高いためである。この場合、パス１と共有している構成要素が少ないパス３を先に試す方が、宛先ノードにメッセージが到達するまでの遅延が少なくなる。
【０００７】
非特許文献３には、複数のパスについて送信を試行する最適な順序を得る方法については記載されていない。また、上述の最短パスルーティングのように、宛先ノードまでのパスの長さを指標として用いる場合、構成要素の重複が考慮されず、送信を試行する最適な順序を得ることはできない。
【０００８】
一方、非特許文献４には、最短パスを第１のパスとして用い、最短パスと構成要素を共有しない別のパス（disjoint path）を第２のパスとして用いる方法が記載されている。しかし、上述の例のように、最短パスと構成要素を共有しないパスが存在しない場合には、この方法を使用することができない。また、非特許文献５には、最短パスと部分的に構成要素が重複しない別のパス（partially disjoint path）を用いる方法が記載されている。しかし、この方法では、宛先ノードへのメッセージの到達率を厳密には考慮していないため、送信を試行する最適な順序が必ずしも得られるとは限らない。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】RFC 2453, RIP Version 2, http://tools.ietf.org/html/rfc2453
【非特許文献２】RFC 2328, OSPF Version 2, http://tools.ietf.org/html/rfc2328
【非特許文献３】Cheng Yi, Alexander Afanasyev, Lan Wang, Beichuan Zhang, and Lixia Zhang. 2012. Adaptive forwarding in named data networking. SIGCOMM Comput. Commun. Rev. 42, 3 (June 2012), 62-67. DOI=10.1145/2317307.2317319 http://doi.acm.org/10.1145/2317307.2317319
【非特許文献４】Bhandari, R.,“Optimal diverse routing in telecommunication fiber networks,”INFOCOM '94. Networking for Global Communications., 13th Proceedings IEEE , vol., no., pp.1498,1508 vol.3, 12-16 Jun 1994.
【非特許文献５】Deepak Ganesan, Ramesh Govindan, Scott Shenker, and Deborah Estrin. 2001. Highly-resilient, energy-efficient multipath routing in wireless sensor networks. SIGMOBILE Mob. Comput. Commun. Rev. 5, 4 (October 2001), 11-25.
【非特許文献６】Donald E. Knuth, The Art of Computer Programming Volume 4, Fascicle 1 Bitwise Tricks & Techniques; Binary Decision Diagarms, Addison-Wesley Professional, March 27, 2009.
【発明の概要】
【発明が解決しようとする課題】
【００１０】
このように、マルチパスルーティングをサポートした通信ネットワークでは、メッセージが宛先ノードに到達するまでの遅延を少なくするために、各ノードに接続された複数のリンクについてメッセージの送信を試行する順序をより適切に決定することが必要である。
【００１１】
本発明は、上述の課題に鑑みてなされたものである。本発明は、マルチパスルーティングをサポートしたネットワークで、各ノードが宛先ノードへメッセージを送信する際に、複数のリンクについて送信を試行する順序を、ネットワークの各構成要素の稼働率を考慮してより適切に決定する技術を提供することを目的としている。
【課題を解決するための手段】
【００１２】
本発明の一態様の係る方法は、ノード及びリンクを構成要素として含むネットワークにおいて、ノードに接続された複数のリンクのそれぞれを用いて当該ノードが宛先ノードへのメッセージの送信を順に試行するための送信試行順序を決定する方法であって、宛先ノードまでのパスに存在する各構成要素が稼働しているか否かを示す論理変数を用いて記述され、かつ、各ノードに接続された複数のリンクのそれぞれを用いて当該ノードがメッセージを送信した場合に当該メッセージが前記宛先ノードに到達する条件を表す、各リンクに対応する論理式を、前記ネットワーク内の構成要素の接続関係を示すトポロジ情報に基づいて生成する第１の生成ステップと、各ノードに接続された複数のリンクから成る集合の各部分集合に含まれるいずれかのリンクを用いた場合にメッセージが前記宛先ノードに到達する条件を表す、各部分集合に対応する論理式を、前記第１の生成ステップで生成された各リンクに対応する論理式に基づいて生成する第２の生成ステップと、前記送信試行順序の決定対象となる対象ノードについて前記第２の生成ステップで生成された各部分集合に対応する論理式に、前記ネットワーク内の各構成要素についての予め定められた稼働率を適用することで、各部分集合を用いた場合にメッセージが前記対象ノードから前記宛先ノードに到達する確率を表す到達率を算出し、算出した前記到達率に応じて、前記対象ノードについての前記送信試行順序を決定する決定ステップとを含むことを特徴とする。
【００１３】
本発明の他の一態様の係る方法は、ノード及びリンクを構成要素として含むネットワークにおいて、ノードに接続された複数のリンクのそれぞれを用いて当該ノードが宛先ノードへのメッセージの送信を順に試行するための送信試行順序を決定する方法であって、宛先ノードまでのパスに存在する各構成要素が稼働しているか否かを示す論理変数を用いて記述され、かつ、各ノードに接続された複数のリンクのそれぞれを用いて当該ノードがメッセージを送信した場合に当該メッセージが前記宛先ノードに到達する条件を表す、各リンクに対応する論理式であって、前記ネットワーク内の構成要素の接続関係を示すトポロジ情報に基づいて生成された論理式を取得する取得ステップと、自ノードに接続された複数のリンクから成る集合の各部分集合に含まれるいずれかのリンクを用いた場合にメッセージが前記宛先ノードに到達する条件を表す、各部分集合に対応する論理式を、前記取得ステップで取得された各リンクに対応する論理式に基づいて生成する生成ステップと、前記生成ステップで生成された各部分集合に対応する論理式に、前記ネットワーク内の各構成要素についての予め定められた稼働率を適用することで、各部分集合を用いた場合にメッセージが前記自ノードから前記宛先ノードに到達する確率を表す到達率を算出し、算出した前記到達率に応じて、前記自ノードについての前記送信試行順序を決定する決定ステップとを含むことを特徴とする。
【００１４】
本発明の更に他の一態様の係る方法は、ノード及びリンクを構成要素として含むネットワークにおいて、ノードに接続された複数のリンクのそれぞれを用いて当該ノードが宛先ノードへのメッセージの送信を順に試行するための送信試行順序を決定する方法であって、宛先ノードまでのパスに存在する各構成要素が稼働しているか否かを示す論理変数を用いて記述され、かつ、自ノードに接続された複数のリンクから成る集合の各部分集合に含まれるいずれかのリンクを用いた場合にメッセージが前記宛先ノードに到達する条件を表す、各部分集合に対応する論理式を取得する取得ステップと、前記取得ステップで取得された各部分集合に対応する論理式に、前記ネットワーク内の各構成要素についての予め定められた稼働率を適用することで、各部分集合を用いた場合にメッセージが前記自ノードから前記宛先ノードに到達する確率を表す到達率を算出し、算出した前記到達率に応じて、前記自ノードについての前記送信試行順序を決定する決定ステップとを含むことを特徴とする。
【発明の効果】
【００１５】
本発明によれば、マルチパスルーティングをサポートした通信ネットワークで、各ノードが宛先ノードへメッセージを送信する際に、複数のリンクについて送信を試行する順序を、ネットワークの各構成要素の稼働率を考慮してより適切に決定できる。
【図面の簡単な説明】
【００１６】
【図１】通信ネットワークの一例を示す図。
【図２】通信ネットワークについて手順１を実行する場合の、開始前の初期状態における各論理式の具体例を示す図。
【図３】通信ネットワークについて手順１を実行する場合の、１回目のループ終了時における各論理式の具体例を示す図。
【図４】通信ネットワークについて手順１を実行する場合の、２回目のループ終了時における各論理式の具体例を示す図。
【図５】通信ネットワークについて手順１を実行する場合の、３回目のループ終了時における各論理式の具体例を示す図。
【図６】通信ネットワークについて手順１を実行する場合の、４回目のループ終了時における各論理式の具体例を示す図。
【図７】通信ネットワークについて手順１を実行する場合の、５回目のループ終了時における各論理式の具体例を示す図。
【図８】論理式が真になる確率を計算する際に使用される真理値表の一例を示す図。
【発明を実施するための形態】
【００１７】
以下、本発明の例示的な実施形態について図面を参照して説明する。なお、以下の各図において、実施形態の説明に必要ではない構成要素については図から省略する。
【００１８】
＜概要＞
本実施形態では、Ｎ台のノードｖ1，...，ｖNとＭ本のリンクｅ1，...，ｅMとにより構成される、図１に示すような通信ネットワークに本発明を適用した場合について説明する。図１は、Ｎ＝８、Ｍ＝９とした場合の、通信ネットワークの一例を示す図である。説明の便宜上、ノードｖNを宛先ノードとする。本実施形態では、以下の３つの手順により、各ノードｖi（ｉ＝１，...，Ｎ）について、各ノードに接続されたリンクのそれぞれを用いて宛先ノードｖNへのメッセージの送信を順に試行するための送信試行順序を決定する。この送信試行順序は、各ノードが宛先ノードｖNへメッセージを送信する際に送信を試行すべきリンクの順序を示す。
【００１９】
また、本実施形態では、以下の３つの手順を、１台の経路計算ノードで実行する場合について説明する。経路計算ノードは、Ｎ台のノードｖ1，...，ｖNのいずれかのノードであってもよいし、あるいは、Ｎ台のノードとは別に設けられた専用のノードであってもよい。
【００２０】
（手順１）
手順１において経路計算ノードは、通信ネットワークのトポロジ情報に基づいて、各ノードｖiに接続された各リンクｅjを用いて当該ノードｖiがメッセージを送信した場合に当該メッセージが宛先ノードｖNに到達する条件を表す、各リンクに対応する論理式ｂi,jを生成する。トポロジ情報は、ネットワーク内の構成要素（ノード及びリンク）の接続関係を示す。また、論理式ｂi,jは、各ノードから宛先ノードまでのパスに存在する構成要素が稼働しているか否か（即ち、稼働状況）を示す論理変数を用いて記述される。経路計算ノードは、ネットワーク内の各ノードｖi（ｉ＝１，...，Ｎ）について、当該ノードに接続された全てのリンクに対して論理式ｂi,jを生成する。
【００２１】
（手順２）
手順２において経路計算ノードは、各ノードｖiに接続された複数のリンクｅjから成る集合の部分集合ごとに、当該ノードｖiが当該部分集合のいずれかのリンクを用いた場合にメッセージが宛先ノードｖNに到達する条件を表す、各部分集合に対応する論理式Ｂi,Jを生成する。論理式Ｂi,Jは、手順１で生成された論理式に基づいて生成される。ただし、Ｊは、部分集合に含まれるリンクのリンク番号の集合を示す。経路計算ノードは、ネットワーク内の各ノードｖi（ｉ＝１，...，Ｎ）について、当該ノードに接続された全てのリンクから成る集合のあらゆる部分集合に対して論理式Ｂi,Jを生成する。
【００２２】
（手順３）
手順３において経路計算ノードは、ネットワーク内の各ノードｖiをそれぞれ、送信試行順序の決定対象となる対象ノードとして、手順２で生成された論理式Ｂi,Jと、ネットワーク内の各構成要素の稼働率とに基づいて、対象ノードについての送信試行順序を決定する。具体的には、経路計算ノードは、対象ノードｖiについて手順２で生成された論理式Ｂi,Jに、ネットワーク内の各構成要素の稼働率を適用することで、各部分集合を用いた場合にメッセージが対象ノードから宛先ノードｖNに到達する確率を表す到達率を算出する。次に、経路計算ノードは、算出した到達率に応じて、対象ノードについての送信試行順序を決定する。なお、各構成要素の稼働率には、予め定められた値が用いられてもよい（例えば、ネットワークの管理者が予め経路計算ノードに与えてもよい）。あるいは、例えばネットワーク内の各構成要素の動作状態を経路計算ノードが監視することで得られた値が用いられてもよい。
【００２３】
＜手順１＞
次に、手順１の詳細について説明する。手順１では、対象とするネットワークのトポロジ情報を必要とする。トポロジ情報は、ネットワークの管理者が予め経路計算ノードに与えてもよいし、あるいは、経路計算ノードとＮ台のノードｖi（ｉ＝１，...，Ｎ）との間に別途設けられた通信路を介して、経路計算ノードがＮ台のノードから収集してもよい。手順１で生成（構築）される論理式は、ネットワーク内の各構成要素、即ち、ノードｖi，リンクｅjの稼働状況を示す論理変数Ｖi，Ｅjを用いて記述される。これらの論理変数は、以下の値を有する。
‐Ｖi：ノードｖiが稼働している場合は１（真）、それ以外の場合は０（偽）
‐Ｅj：リンクｅjが稼働している場合は１（真）、それ以外の場合は０（偽）
【００２４】
手順１において経路計算ノードは、上記の論理変数Ｖi，Ｅjを用いて、各ノードｖiについて、以下の論理式を生成する。なお、ｂi,jは、各リンクに対応する論理式の一例であり、Ｂiは、各ノードに対応する論理式の一例である。
‐ｂi,j：ノードｖiがリンクｅjを用いてメッセージを送信した場合に、当該メッセージが宛先ノードｖNに到達する条件を表す論理式（ただし、ｅjは、ノードｖiに接続されたいずれかのリンクとする）
‐Ｂi：ノードｖiがメッセージを送信した場合に、当該メッセージが宛先ノードｖNに到達する条件を表す論理式
【００２５】
ここで、ノードｖiに接続された全てのリンク（番号）の集合をＪiとすると、論理式Ｂiは、次式のように、ノードｖiに接続された全てのリンクに対応する論理式ｂi,j（ｉ＝１，...，Ｎ；ｊ∈Ｊi）の論理和によって求められる。
Ｂi＝∨ｊ∈Ｊi ｂi,j
また、論理式ｂi,jは、リンクｅjを介してノードｖiに隣接（対向）するノードｖkに対応する論理式Ｂkに基づいて求められる。具体的には、論理式ｂi,jは、次式のように、Ｖiと、Ｅjと、関数invert(Ｂk, Ｖi) との論理積によって求められる。
ｂi,j＝Ｖi ∧ Ｅj ∧ invert(Ｂk, Ｖi)
ここで、関数invert(Ｂk, Ｖi)は、論理式Ｂkの中に現れる論理変数Ｖiを、その否定である¬Ｖiに置き換えて得られる論理式を表す。
【００２６】
このように、上記の論理式ｂi,j，Ｂiは、隣接ノード間で依存関係が循環している。このため、論理式ｂi,jをより適切に求めるためには、自明な初期値から開始して、収束するまでの間、論理式ｂi,j，Ｂiの計算を繰り返し行う必要がある。
【００２７】
具体的には、以下の手順により、そのような繰り返し処理を実行できる。まず、経路計算ノードは、Ｎ台のノードｖiに対応する論理式Ｂi（ｉ＝１，...，Ｎ）を初期化する。ここで、経路計算ノードは、宛先ノード以外のノードｖi（ｉ＝１，...，Ｎ−１）については、
Ｂi＝０
に初期化し、宛先ノードｖNについては、
ＢN＝ＶN
に初期化する。
【００２８】
次に、経路計算ノードは、以下の処理（１）及び（２）を、全てのノードｖi（ｉ＝１，...，Ｎ）について実行する。
【００２９】
（１）ｂi,jの生成（更新）
経路計算ノードは、ノードｖiに接続された各リンクｅj（ｊ∈Ｊi）について、論理式ｂi,jを次式によって生成（更新）する。
ｂi,j＝Ｖi ∧ Ｅj ∧ invert(Ｂk, Ｖi)
なお、Ｊiは、ノードｖiに接続された全てのリンク（番号）の集合を表す。
【００３０】
（２）Ｂiの更新
次に、経路計算ノードは、ノードｖiに対応する論理式Ｂiを、論理式ｂi,jに基づいて更新する。論理式Ｂiは、次式のように、処理（１）で生成（更新）された、ノードｖiに接続された全てのリンクに対応する論理式ｂi,j（ｊ∈Ｊi）の論理和によって求められる。
Ｂi＝∨ｊ∈Ｊi ｂi,j
【００３１】
処理（１）及び（２）により、各ノードｖi（ｉ＝１，...，Ｎ）について、接続された各リンクｅjに対応する論理式ｂi,j（ｉ＝１，...，Ｎ；ｊ∈Ｊi）が生成（更新）される。経路計算ノードは、全てのノードについての処理（１）及び（２）の実行を１回のループとして、これを所定の回数だけ繰り返すことで、論理式ｂi,j（ｉ＝１，...，Ｎ；ｊ∈Ｊi）を繰り返し更新する。なお、本実施形態では、所定の回数は、（ネットワーク内のパス長の上限）−１とする。なお、所定の回数の繰り返し処理が完了する前に、論理式ｂi,j（ｉ＝１，...，Ｎ；ｊ∈Ｊi）が収束した時点で、繰り返し処理を終了してもよい。
【００３２】
このような処理によって、宛先ノードｖNを起点として、当該宛先ノードに近い順に、各ノードについて、接続された各リンクｅjに対応する論理式ｂi,jが生成（更新）される。即ち、上述の１回のループの処理を実行するごとに、宛先ノードｖNに近いノードから遠いノードに向かって、隣接ノードに対応する論理式が順次伝搬していくことになる。
【００３３】
（手順１の具体例）
図２乃至図７を参照して、手順１の具体例として、図１に示す通信ネットワークについて手順１を実行した場合について説明する。図２は、手順１における開始前の初期状態における各論理式の例を示す図である。図３乃至図７はそれぞれ、手順１における上述の繰り返し処理のうち、１〜５回目のループが終了した時点における各論理式の例を示す図である。ただし、図１と同様、Ｎ＝８、Ｍ＝９である。
【００３４】
‐初期状態（図２）
まず、経路計算ノードは、論理式Ｂi＝０（ｉ＝１，...，７）、Ｂ8＝Ｖ8に初期化する。
【００３５】
‐１回目のループ終了時（図３）
経路計算ノードは、ノードｖ3について、隣接ノードｖ8に対応する論理式Ｂ8に基づいて、リンクｅ3に対応する論理式
ｂ3,3＝Ｖ3 ∧ Ｅ3 ∧ Ｂ8
を生成する。更に、経路計算ノードは、論理式Ｂ3を、
Ｂ3＝ｂ3,2 ∨ ｂ3,3 ∨ ｂ3,9
に更新する。なお、ノードｖ3及びｖ3以外のノードｖiについては、隣接ノードに対応する論理式Ｂk＝０であるため、ｂi,jは生成されず、Ｂiは更新されない。
【００３６】
‐２回目のループ終了時（図４）
１回目のループでは、ノードｖ3に対応する論理式Ｂ3が０以外に更新されている。このため、２回目のループでは、ノードｖ3の隣接ノードｖ2及びｖ7についての論理式ｂ2,2，Ｂ3，ｂ7,9，Ｂ7が、図４に示すように求められる。
【００３７】
‐３回目のループ終了時（図５）
２回目のループでは、ノードｖ2及びｖ7に対応する論理式Ｂ2及びＢ7が０以外に更新されている。このため、３回目のループでは、ノードｖ2及びｖ7の隣接ノードｖ1、ｖ4及びｖ6についての論理式ｂ1,1，Ｂ1，ｂ4,5，Ｂ4，ｂ6,8，Ｂ6が、図５に示すように求められる。ただし、３回目のループを開始する時点では、ノードｖ1の隣接ノードｖ4及びｖ5に対応する論理式Ｂ4及びＢ5は０であるため、それらのノードへのリンクに対応する論理式ｂ1,4及びｂ1,6は求められていない。このため、ノードｖ1に対応する論理式は、
Ｂ1＝ｂ1,1
に更新される。
【００３８】
‐４回目のループ終了時（図６）
３回目のループで、ノードｖ6に対応する論理式Ｂ6が０以外に更新されたため、４回目のループでは、ノードｖ5についての論理式ｂ5,7，Ｂ5が、図６に示すように求められる。また、３回目のループで、ノードｖ4に対応する論理式Ｂ4が０以外に更新されたため、ノードｖ1からノードｖ4へのリンクｅ4に対応する論理式ｂ1,4が新たに求められ、ノードｖ1に対応する論理式が、
Ｂ1＝ｂ1,1 ∨ ｂ1,4
に更新される。
【００３９】
‐５回目のループ終了時（図７）
４回目のループで、ノードｖ5に対応する論理式Ｂ5が０以外に更新されたため、ノードｖ1からノードｖ5へのリンクｅ6に対応する論理式ｂ1,6が新たに求められ、ノードｖ1に対応する論理式が、
Ｂ1＝ｂ1,1 ∨ ｂ1,4∨ ｂ1,6
に更新される。
【００４０】
＜手順２＞
次に、手順２の詳細について説明する。手順２では、経路計算ノードは、手順１によって生成された、各ノードに接続された各リンクに対応する論理式ｂi,j（ｉ＝１，...，Ｎ；ｊ∈Ｊi）に基づいて、各ノードについて新たな論理式を生成する。具体的には、経路計算ノードは、各ノードｖiについて、接続された全リンクの番号から成る集合Ｊiに対するあらゆる部分集合Ｊ⊆Ｊiについて、以下の論理式を生成する。
Ｂi,J：ノードｖiが、接続された全リンクに対する部分集合｛ｅj|ｊ∈Ｊ｝のいずれかのリンクを用いてメッセージを送信した場合に当該メッセージが宛先ノードｖNに到達する条件を表す論理式
【００４１】
具体的には、論理式Ｂi,Jは、各部分集合に含まれる各リンクについて手順１で生成された論理式ｂi,jの論理和として、次式のように求められる。
Ｂi,J＝∨j∈J ｂi,j
【００４２】
（手順２の具体例）
ここでは、手順２の具体例として、上述の手順１の具体例によって得られた結果（図７）に基づいて手順２を実行した場合について説明する。ただし、ノードｖ1の場合についてのみ説明する。
【００４３】
経路計算ノードは、ノードｖ1について、各部分集合に対応する論理式を、次式により生成する。
Ｂ1,J＝∨j∈J ｂ1,j
ここで、ノードｖ1に接続されたリンクの番号から成る集合は、
Ｊ1＝{１，４，６}
であるため、その部分集合Ｊとして、{１}、{４}、{６}、{１，４}、{１，６}、{４，６}、{１，４，６} が存在する。このため、経路計算ノードは、ノードｖ1について、各部分集合に対応する論理式として、
Ｂ1,{1}＝ｂ1,1
Ｂ1,{4}＝ｂ1,4
Ｂ1,{6}＝ｂ1,6
Ｂ1,{1,4}＝ｂ1,1 ∨ ｂ1,4
Ｂ1,{1,6}＝ｂ1,1 ∨ ｂ1,6
Ｂ1,{4,6}＝ｂ1,4 ∨ ｂ1,6
Ｂ1,{1,4,6}＝ｂ1,1 ∨ ｂ1,4 ∨ ｂ1,6
を生成する。
【００４４】
＜手順３＞
次に、手順３の詳細について説明する。手順３では、経路計算ノードは、ネットワーク内の各ノードｖiをそれぞれ、送信試行順序の決定対象となる対象ノードとして、以下の計算を行う。
【００４５】
経路計算ノードは、対象ノードｖiがｎ番目に使用するリンクを、ｎ＝１から順に（即ち、送信を先に試行すべきリンクから順に）、以下の処理を繰り返すことによって、１つずつ決定する。なお、本実施形態では、Ｊ’は第１の部分集合に対応するリンク番号の部分集合の一例であり、Ｊは第２の部分集合に対応するリンク番号の部分集合の一例である。
【００４６】
まず、経路計算ノードは、１番目から（ｎ−１）番目までに使用するリンクの番号の集合をＪ’とする。ただし、送信試行順序の決定を開始する際（ｎ＝１の場合）、Ｊ’は空集合とする。
【００４７】
次に、経路計算ノードは、対象ノードｖiに接続されたリンクのうち、Ｊ’にリンク番号が含まれていない各リンクｅjについて、ｎ番目のリンクとして使用した場合の到達率を、以下の手順により計算する。
・既に順序が決定されている１つ以上のリンク（番号）を含む部分集合Ｊ’に対して、順序が決定されていないリンク（番号）を新たなリンク（番号）として加えて、次式のように第２の部分集合Ｊを生成する。
Ｊ＝Ｊ' ∪ {ｊ}
・次に、部分集合Ｊについて、手順２で生成された論理式Ｂi,Jに基づいて、到達率Ｐｒ(Ｂi,J＝１) を算出する。
【００４８】
ここで、Ｐｒ(Ｂi,J＝１) は、論理式Ｂi,Jが真になる確率を表す。到達率Ｐｒ(Ｂi,J＝１) は、ネットワーク内の各構成要素（ノード及びリンク）についての予め定められた稼働率Ｐｒ(Ｖi＝１|ｉ＝１，...，Ｎ)及びＰｒ(Ｅi＝１|ｉ＝１，...，Ｍ) を適用することによって算出できる。具体的には、Ｂi,Jに含まれる各論理変数Ｖi，Ｅiに、当該論理変数に対応する構成要素についての稼働率を適用することで、Ｂi,Jが真になる確率を算出できる。
【００４９】
次に、経路計算ノードは、Ｊ’にリンク番号が含まれていない各リンクｅjに基づく１つ以上の部分集合Ｊについて算出された到達率Ｐｒ(Ｂi,J＝１) のうち、算出した到達率が最大となるリンクｅjを特定する。経路計算ノードは、特定したリンクｅjを、対象ノードｖiがｎ番目に使用するリンク（即ち、既に決定されている１つ以上のリンクの次に送信を試行すべきリンク）として決定する。
【００５０】
経路計算ノードは、上述の処理を繰り返すことによって、対象ノードｖiに接続された全リンクについての送信試行順序を決定する。なお、経路計算ノードは、対象ノードｖiについて決定した送信試行順序を示す情報を、対象ノードｖiに送信しうる。
【００５１】
（手順３の具体例）
ここでは、手順３の具体例として、上述の手順２の具体例によって得られた結果に基づいて手順３を実行した場合について説明する。ただし、送信試行順序を決定する対象となる対象ノードをノードｖ1とした場合についてのみ説明する。ノードｖ1には、リンクｅ1，ｅ4，ｅ6が接続されている。このため、経路計算ノードは、これら３つのリンクについての送信試行順序を決定する。
【００５２】
‐１番目のリンク（ｎ＝１）の決定
経路計算ノードは、送信試行順序の決定を開始する際には空集合である、リンク（番号）の部分集合Ｊ’に、１つのリンクを加えて得られる、リンク（番号）の部分集合Ｊについて、到達率Ｐｒ(Ｂi,J＝１) を算出する。ここでは、
Ｐｒ(Ｂ1,{1}＝１)＝０．５９
Ｐｒ(Ｂ1,{4}＝１)＝０．４８
Ｐｒ(Ｂ1,{6}＝１)＝０．３９
が算出されたものとする。これは、リンクｅ1を介して宛先ノードｖ8に至るパスは最短のパスであるため、到達率が最も高くなることを示している。その結果、経路計算ノードは、算出した２つの到達率のうち、最も到達率が高くなるリンクｅ1を、１番目に送信を試行すべきリンクに決定する。
【００５３】
ここで、Ｐｒ() の計算方法について説明する。例えば、
・論理式ｂ3,3＝Ｖ3 ∧ Ｅ3 ∧ Ｖ8
・論理変数Ｖ3が真となる確率＝０．９
・論理変数Ｅ3が真となる確率＝０．９
・論理変数Ｖ8が真となる確率＝１
として、Ｐｒ(ｂ3,3＝１) を計算する場合を想定する。なお、Ｐｒ(ｂ3,3＝１) は、論理式ｂ3,3が真となる確率を表す。この場合、まず、図８に示すような真理値表（左から第１〜５列とする。）を作成する。更に、真理値表の各行について、各論理変数の値から、論理式ｂ3,3の値（第４列）を求めるとともに、その確率を求める（第５列）。最後に、論理式ｂ3,3の値が１となる行の確率の和（＝０．８１）を、Ｐｒ(ｂ3,3＝１) として求める。
【００５４】
‐２番目のリンク（ｎ＝２）の決定
順序が決定されているリンク（番号）を含む部分集合Ｊ’＝{１} に、１つのリンクを加えて得られる、リンク（番号）の部分集合Ｊについて、到達率Ｐｒ(Ｂi,J＝１) を算出する。ここでは、
Ｐｒ(Ｂ1,{1,4}＝１)＝０．６４
Ｐｒ(Ｂ1,{1,6}＝１)＝０．７０
が算出されたものとする。これは、リンクｅ6を介して宛先ノードｖ8に至るパスは、リンクｅ1を介して宛先ノードｖ8に至るパス（最短パス）と共有する部分が少ないため、２番目に使用することで、到達率の増加量が大きくなることを示している。その結果、経路計算ノードは、算出した２つの到達率のうち、最も到達率が高くなるリンクｅ6を、２番目に送信を試行すべきリンクに決定する。
【００５５】
‐３番目のリンク（ｎ＝３）の決定
経路計算ノードは、最終的に残ったリンクｅ4を、３番目に送信を試行すべきリンクに決定する。
【００５６】
以上説明したように、本実施形態によれば、マルチパスルーティングをサポートした通信ネットワークで、各ノードが宛先ノードへメッセージを送信する際に、複数のリンクについて送信を試行する順序を、ネットワークの各構成要素の稼働率を考慮して決定できる。これにより、宛先ノードへのメッセージの到達率を最大化しつつ、送信を試行するリンクの数を可能な限り少なくすることができる。その結果、メッセージが宛先ノードに到達するまでの遅延と、使用するネットワーク資源とを、可能な限り少なくすることができ、より効率的な通信を実現できる。
【００５７】
［その他の実施形態］
上述の実施形態は、以下で説明するように、様々な形態に変更して実施することが可能である。
【００５８】
例えば、ある程度規模の大きいネットワークに対して上述の実施形態を適用する場合、手順１及び２で生成される各論理式のサイズが非常に大きくなる。この場合、経路計算ノードにおいて、各論理式を格納するため、及び論理演算及び確率計算を実行するために必要となるメモリ量または計算時間が膨大になりうる。このような場合、上述の各手順において各論理式をメモリ上に格納する際のデータ構造として、ＢＤＤ（Binary Decision Diagram）（非特許文献６）を用いてもよい。これにより、上述の各手順において必要となるメモリ量及び計算時間を低減することが可能である。
【００５９】
また、上述の手順２及び３を同一のノードで実行する場合、手順２によって予めあらゆる部分集合に対応する論理式を生成しなくてもよい。この場合、まず手順３の実行を開始して、到達率の計算に必要となった部分集合についてのみ、手順２に従って論理式を生成してもよい。これにより、送信試行順序の決定に不要な論理式を生成する手間を軽減することが可能である。
【００６０】
また、上述の実施形態では、経路計算ノードが手順１〜３の全てを実行しているが、例えば、手順２及び３については、ネットワーク内の各ノードで実行することも可能である。この場合、各ノードは、手順１において生成される、各リンクに対応する論理式を、ネットワーク内の別のノード（例えば、経路計算ノード）から、または自ノードが備えるメモリ等から取得すればよい。これにより、経路計算ノードの負荷が低減される。
【００６１】
また、手順２及び３だけでなく、手順１についても、ネットワーク内の各ノードで実行することも可能である。これにより、各ノードの負荷は増えるものの、経路計算ノードと各ノードとの間の通信が必要なくなる。ただし、この場合、各ノードは、手順１及び３で使用するトポロジ情報及び各構成要素の稼働率情報を何らかの方法で取得する必要がある。例えばＯＳＰＦ（非特許文献２）で行われているように、ノード間で情報をフラッディングすることで、各ノードがこのような情報を取得できる。なお、各ノードは、手順２及び３については、自ノードについてのみ計算を行えばよい。
【００６２】
また、上述の実施形態では、手順１及び２を経路計算ノード等の別のノードで実行し、手順３のみをネットワーク内の各ノードで実行するようにしてもよい。この場合、各ノードは、手順２において生成される、各部分集合に対応する論理式を、ネットワーク内の別のノード（例えば、経路計算ノード）から、または自ノードが備えるメモリ等から取得すればよい。これにより、経路計算ノードの負荷が低減される。
【００６３】
また、上述の実施形態は、分散アルゴリズムとして実施することも可能である。この場合、各ノードｖiは、手順１の計算のうち、自ノードに関する論理式である、Ｂi，ｂi,jの生成に関連する部分のみを実行する。更に、各ノードｖiは、計算したＢiを、ＲＩＰ（非特許文献１）における距離ベクトルの広告と同様に隣接ノードに送信し、逆に、各隣接ノードｖkからＢkを受信する。各ノードｖiは、受信したＢkに基づき、Ｂi，ｂi,jを更新する。以上のような手順を繰り返すことで、上述の実施形態を分散アルゴリズムとして実施することが可能である。
【００６４】
また、上述の実施形態において、各ノードについての送信試行順序を決定するために、リンクの稼働率とノードの稼働率とのいずれか一方のみを考慮すれば十分である場合には、それらの両方ではなく一方のみを使用してもよい。これにより、上述の各手順において必要となるメモリ量、計算時間及び通信量を低減することが可能である。
【００６５】
なお、本発明によるノードは、コンピュータを上記ノードとして動作させるプログラムにより実現することができる。これらコンピュータプログラムは、コンピュータが読み取り可能な記憶媒体に記憶されて、又は、ネットワーク経由で配布が可能なものである。
【図１】
2015029223.tif 000003
【図２】
2015029223.tif 000004
【図３】
2015029223.tif 000005
【図４】
2015029223.tif 000006
【図５】
2015029223.tif 000007
【図６】
2015029223.tif 000008
【図７】
2015029223.tif 000009
【図８】
2015029223.tif 000010