(57)【特許請求の範囲】
【請求項１】
ネットワーク内の各ノード間におけるリンクの有無に基づいて、ネットワーク内の各ノードにパケットを略均一に分散させる確率である転送確率を算出する転送確率算出手段と、
トポロジ情報に基づいてパケットの宛先ノードまでの最短経路を決定する最短経路決定手段と、
前記転送確率に応じて選択されるノードと前記最短経路におけるノードを、確率的に選択して転送先ノードと決定する転送先決定手段とを備えた
ことを特徴とするパケット中継システム。
【請求項２】
転送確率算出手段は、ネットワーク内の各ノードにパケットを略均一に分散させる転送確率を算出する
請求項１記載のパケット中継システム。
【請求項３】
ネットワーク内における各ノードのパケット転送容量を示す転送容量情報を記憶する転送容量情報記憶手段を備え、
転送確率算出手段は、トポロジ情報および前記転送容量情報に基づいて、ネットワーク内の各ノードに、当該ノードの転送容量に比例した量のパケットを分散させる転送確率を算出する
請求項１記載のパケット中継システム。
【請求項４】
転送確率算出手段は、ネットワーク上の各ノードにパケットが存在する確率を固有ベクトルの各成分とする固有値が１である転送確率行列を算出し、算出した転送確率行列における各要素を転送確率とする
請求項１から請求項３のうちのいずれか１項に記載のパケット中継システム。
【請求項５】
転送先決定手段は、宛先ノードが隣接するノードの場合、当該ノードを転送ノードと決定する
請求項１から請求項４のうちのいずれか１項に記載のパケット中継システム。
【請求項６】
ネットワーク内の各ノード間におけるリンクの有無に基づいて、ネットワーク内の各ノードにパケットを略均一に分散させる確率である転送確率を算出し、
トポロジ情報に基づいてパケットの宛先ノードまでの最短経路を決定し、
前記転送確率に応じて選択されるノードと前記最短経路におけるノードを、確率的に選択して転送先ノードと決定する
ことを特徴とするパケット中継方法。
【請求項７】
ネットワーク内の各ノードにパケットを略均一に分散させる転送確率を算出する
請求項６記載のパケット中継方法。
【請求項８】
ネットワーク内における各ノードのパケット転送容量およびトポロジ情報に基づいて、ネットワーク内の各ノードに、当該ノードのパケット転送容量に比例した量のパケットを分散させる転送確率を算出する
請求項６記載のパケット中継方法。
【請求項９】
コンピュータに、
ネットワーク内の各ノード間におけるリンクの有無に基づいて、ネットワーク内の各ノードにパケットを略均一に分散させる確率である転送確率を算出する転送確率算出処理、
トポロジ情報に基づいてパケットの宛先ノードまでの最短経路を決定する最短経路決定処理、および、
前記転送確率に応じて選択されるノードと前記最短経路におけるノードを、確率的に選択して転送先ノードと決定する転送先決定処理
を実行させるためのパケット中継用プログラム。
【請求項１０】
コンピュータに、
転送確率算出処理で、ネットワーク内の各ノードにパケットを略均一に分散させる転送確率を算出させる
請求項９記載のパケット中継用プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パケットを中継する際の転送負荷を分散させるパケット中継システム、パケット中継方法およびパケット中継用プログラムに関する。
【背景技術】
【０００２】
近年、インターネットをはじめとする多くのネットワークがスケールフリー性を有することが知られている。スケールフリー性とは、各ノードに接続されたリンクの数（以下、次数と記すこともある。）が冪分布をなす特徴のことを指す。スケールフリー性を有するネットワークにおいては、次数の大きなノードが少数のみ存在している。このノードは、ハブノードと呼ばれている。
【０００３】
また、ネットワークの任意の２点間を結ぶ最短経路において、パケットがハブノードを経由することが多いことも知られている。このため、パケットが宛先ノードまでの最短経路を必ず通るよう転送された場合、ハブノードへのパケットが集中し、輻輳を招いてしまう。
【０００４】
通信ネットワークにおいて、通信トラヒックの輻輳を回避しパケットの損失を最小限に抑えることは最も重要な課題の一つである。最も単純な輻輳回避手段の１つは、ネットワーク全体の通信トラヒックをリアルタイムに監視し、輻輳が生じる前にパケットを迂回させることである。しかし、ネットワークのサイズが大きくなると、ネットワーク全体の通信を監視することが困難であり、有効な迂回路を設定することができない。
【０００５】
ハブノードへパケットが集中することを回避するパケット中継方式として、特許文献１に記載されたパケット経路制御方法が知られている。特許文献１に記載されたパケット経路制御方法では、最短経路方向の隣接ノードを転送先とする最短経路制御と、隣接ノードのうちから１つを一様ランダムに選択して転送先とするランダムウォーク制御とを組み合わせてパケット転送先を決定する。
【０００６】
具体的には、特許文献１に記載されたパケット経路制御方法では、宛先ノードがノードｋであるパケットを、ノードｉが隣接ノードｊに転送する確率は、以下の式１で表される。
【０００７】
【数１】
0005732995.tif 000002
【０００８】
ここで、ｐ（Ｓ）ｋｉｊは、最短経路制御により宛先ノードがｋであるパケットを、ノードｉがノードｊに転送する確率である。また、ｐ（Ｒ）ｋｉｊは、ランダムウォーク制御により宛先ノードがｋであるパケットを、ノードｉがノードｊに転送する確率である。
【０００９】
この式１は、最短経路制御によるパケット転送処理とランダムウォーク制御によるパケット転送処理が、それぞれ確率δおよび１−δでランダムに選択されることを意味している。このように、特許文献１に記載されたパケット経路制御方法では、最短経路以外へパケットをの経路を分散させることにより、パケットが集中しているノードへのパケットの配送を軽減している。
【００１０】
また、特許文献１には、隣接ノードへパケットを転送する確率の算出方法が記載されている。特許文献１に記載された算出方法では、ネットワークの負荷状況として各隣接ノードｌのキュー長ｑｌを監視しておく。そして、式１により算出される確率を隣接ノードのキュー長によって重み付けした値をパケット転送確率とする。この場合のパケット転送確率は、以下の式２で表される。
【００１１】
【数２】
0005732995.tif 000003
【００１２】
ここで、ｆ（ｑ）は、ｑ（すなわち、キュー長）に関する任意の減少関数である。特許文献１に記載されたパケット経路制御方法では、このパケット転送確率を用いて、より負荷の少ない隣接ノードにパケットを転送することによって、負荷を分散させている。
【００１３】
なお、非特許文献１には、ホップバイホップ方式でパケットが転送されるとき、そのパケットが通る軌跡がランダムになるパケット転送確率の算出方法が記載されている。
【先行技術文献】
【特許文献】
【００１４】
【特許文献１】特開２０１０−１７８０６２号公報
【非特許文献】
【００１５】
【非特許文献１】Ｚ．Ｂｕｒｄａ、Ｊ．Ｄｕｄａ、Ｊ．Ｍ．Ｌｕｃｋ、ａｎｄ  Ｂ．Ｗａｃｌａｗ、「Ｌｏｃａｌｉｚａｔｉｏｎ  ｏｆ  ｍａｘｉｍａｌ  ｅｎｔｒｏｐｙ  ｒａｎｄｏｍ  ｗａｌｋ」、Ｐｈｙｓ．Ｒｅｖ．Ｌｅｔｔ．１０２、１６０６０２、２００８
【発明の概要】
【発明が解決しようとする課題】
【００１６】
特許文献１に記載されたパケット経路制御方法を用いることで、ネットワーク全体の通信を監視することなく、ハブノードへパケットが集中することを回避することはある程度可能である。しかし、特許文献１に記載されたパケット経路制御方法を用いても、パケット転送負荷分散の効果が薄いという問題がある。特許文献１に記載されたパケット経路制御方法では、パケット転送負荷を分散させるため、隣接ノードのうちの１つに一様ランダムに転送を行うランダムウォーク制御を用いているが、このランダムウォーク制御では、ハブノードへパケットが集中してしまうからである。以下、この理由について説明する。
【００１７】
今、ランダムウォーク制御によって、あるパケットがネットワーク内で転送されていくモデルを考える。すなわち、パケットが存在するノードの隣接ノードの１つにそのパケットが毎時刻ごとにランダムに移動していくものとする。ノードｊがパケットを受信したとき、これをノードｉに転送する確率Ｔｉｊは、以下の式３で表される。
【００１８】
【数３】
0005732995.tif 000004
【００１９】
ここで、Ａｉｊは、ノードｉとノードｊの間にリンクが張られているときの値が１になり、リンクが張られていないときの値が０になる変数である。また、ｋｊは、ノードｊの隣接ノードの数である。また、時刻ｔにおいて、パケットがノードｉに存在する確率ｐｉ（ｔ）は、以下の式４で表される。
【００２０】
【数４】
0005732995.tif 000005
【００２１】
さらに、ｉ行ｊ列成分をＴｉｊとする転送確率行列Ｔと、ｉ番目成分をｐｉとする列ベクトルｐ（ｔ）を用いると、上記式４は、以下の式５で表すことができる。なお、Ｔは、ｎ行ｎ列の行列で、ｎはネットワーク内のノードの数である。
【００２２】
【数５】
0005732995.tif 000006
【００２３】
十分時間が経過し、ｐ（ｔ）が定常状態ｐ＊に収束したとすると、上記式５は、以下の式６で表すことができる。
【００２４】
【数６】
0005732995.tif 000007
【００２５】
すなわち、ランダムウォーク制御において、転送確率行列の固有値１に対応する固有ベクトルは、定常状態でパケットが各ノードに存在している確率と等しい。このときのｐ＊における各成分は、ノードの中心性と呼ばれ、ランダムウォーク制御を行った場合におけるパケットの到達のしやすさを表す。
【００２６】
スケールフリーネットワークでは、一般に、ハブノードの中心性が高くなりやすいことが知られている。このため、ランダムウォーク制御によるパケット転送は、ハブノードへパケットを集中させやすい性質をもつといえる。よって、特許文献１に記載されたランダムウォーク制御によりパケットを転送するパケット経路制御方法では、パケット転送負荷分散の効果が薄いと考えられる。
【００２７】
そこで、本発明は、パケットを中継する際の転送負荷をより効果的に分散できるパケット中継システム、パケット中継方法およびパケット中継用プログラムを提供することを目的とする。
【課題を解決するための手段】
【００２８】
本発明によるパケット中継システムは、ネットワーク内の各ノード間におけるリンクの有無に基づいて、ネットワーク内の各ノードにパケットを略均一に分散させる確率である転送確率を算出する転送確率算出手段と、トポロジ情報に基づいてパケットの宛先ノードまでの最短経路を決定する最短経路決定手段と、転送確率に応じて選択されるノードと最短経路におけるノードを、確率的に選択して転送先ノードと決定する転送先決定手段とを備えたことを特徴とする。
【００２９】
本発明によるパケット中継方法は、ネットワーク内の各ノード間におけるリンクの有無に基づいて、ネットワーク内の各ノードにパケットを略均一に分散させる確率である転送確率を算出し、トポロジ情報に基づいてパケットの宛先ノードまでの最短経路を決定し、転送確率に応じて選択されるノードと最短経路におけるノードを、確率的に選択して転送先ノードと決定することを特徴とする。
【００３０】
本発明によるパケット中継用プログラムは、コンピュータに、ネットワーク内の各ノード間におけるリンクの有無に基づいて、ネットワーク内の各ノードにパケットを略均一に分散させる確率である転送確率を算出する転送確率算出処理、トポロジ情報に基づいてパケットの宛先ノードまでの最短経路を決定する最短経路決定処理、および、転送確率に応じて選択されるノードと最短経路におけるノードを、確率的に選択して転送先ノードと決定する転送先決定処理を実行させることを特徴とする。
【発明の効果】
【００３１】
本発明によれば、パケットを中継する際の転送負荷をより効果的に分散できる。
【図面の簡単な説明】
【００３２】
【図１】本発明によるパケット中継システムの第１の実施形態の構成例を示すブロック図である。
【図２】第１の実施形態のパケット中継システムの動作例を示すフローチャートである。
【図３】本発明によるパケット中継システムの第２の実施形態の構成例を示すブロック図である。
【図４】第２の実施形態のパケット中継システムの動作例を示すフローチャートである。
【図５】本発明によるパケット中継システムの最小構成例を示すブロック図である。
【発明を実施するための形態】
【００３３】
以下、本発明の実施形態を図面を参照して説明する。
【００３４】
実施形態１．
図１は、本発明によるパケット中継システムの第１の実施形態の構成例を示すブロック図である。以下の説明では、本発明によるパケット中継システムを、ネットワークノード１００、または、単にノードと記す。本実施形態におけるネットワークノード１００は、転送先決定部１１０と、パケット分散制御部１２０と、最短経路制御部１３０と、通信部１４０と、トポロジ情報管理部１５０とを備えている。
【００３５】
ネットワークノード１００は、通信ネットワーク上に少なくとも１つ以上存在し、各ネットワークノード１００は、同様に動作する。ここでは、ノードｊの動作について説明する。
【００３６】
通信部１４０は、隣接ノードと通信を行い、パケットの授受を行う。通信部１４０は、パケットを受信すると、転送先決定部１１０にパケットの転送先を問い合わせ、転送先決定部１１０の指示する転送先に、受信したパケットを転送する。通信部１４０は、通信のプロトコルとして任意のプロトコルを用いてよい。
【００３７】
トポロジ情報管理部１５０は、ネットワークのトポロジ情報を収集し、収集したトポロジ情報を保持する。また、トポロジ情報管理部１５０は、パケット分散制御部１２０または最短経路制御部１３０からの要求に応じて、ネットワークのトポロジ情報の提供を行う。ここで、トポロジ情報には、ネットワーク内の各ノード間におけるリンクの有無を示す情報が含まれる。ただし、トポロジ情報は、ノード間のリンクの有無を示す情報以外の情報を含んでいてもよい。
【００３８】
転送先決定部１１０は、通信部１４０が受信したパケットの次の転送先を決定する。転送先決定部１１０は、パケットの宛先を読み出し、宛先が自身の隣接ノードであれば宛先ノードを転送先ノードと決定する。一方、パケットの宛先ノードが、自身の隣接ノードでない場合、転送先決定部１１０は、後述する最短経路制御部１３０が決定した転送先と、パケット分散制御部１２０が算出した確率に従って決定される転送先とを確率的に選択することでパケットの転送先を決定する。
【００３９】
ここで、転送先を確率的に選択するとは、具体的には、例えば、管理者等により予め定められる確率δ（０≦δ≦１）に基づいて、パケット分散制御部１２０が算出した転送確率に応じて選択されるノードを確率δで選択し、最短経路制御部１３０が決定した転送先を確率１−δで選択する、としてもよい。言い換えると、パケット分散制御部１２０が算出した各隣接ノードへ転送する確率と、最短経路制御部１３０が決定した隣接ノードへの転送確率（ここでは、１００％）に、確率δを用いて重み付けした転送確率にしたがって隣接ノードを選択するということもできる。
【００４０】
あるいは、転送先決定部１１０は、予め隣接ノードのキュー長など、各ノードの負荷状況を監視しておいてもよい。そして、転送先決定部１１０は、確率δを用いて重み付けされた転送確率に対して、負荷状況に応じた重み付けをさらに行った確率を用いて、パケット転送先を選択してもよい。具体的には、転送先決定部１１０は、隣接するノードの転送確率に対して、負荷が小さいほど重み付けを重く設定してもよい。
【００４１】
以下では、説明のため、パケット分散制御部１２０が算出した転送確率に応じて選択されるノードを確率δで選択し、最短経路制御部１３０が決定した転送先を確率１−δで選択する場合について述べる。
【００４２】
パケット分散制御部１２０は、転送先決定部１１０からの要求に対して、トポロジ情報管理部１５０が保持するトポロジ情報を参照して、ネットワーク内の各ノードになるべく均一にパケットを分散させる、各隣接ノードへの転送確率を算出する。すなわち、パケット分散制御部１２０は、各ノードにパケットを均一に分散させる転送確率を算出する。
【００４３】
まず、パケット分散制御部１２０は、パケットがネットワーク内の各ノードに等確率で存在するような、転送確率行列を算出する。そして、パケット分散制御部１２０は、算出した転送確率行列におけるｊ列目の各要素を各隣接ノードへの転送確率とする。以下、転送確率の算出方法について、具体的に説明する。
【００４４】
パケット分散制御部１２０は、以下の式７に示すように、固有値１に対応する固有ベクトルがｑである転送確率行列Ｔ’をトポロジ情報を元に作成する。ここで、ネットワーク内のノード数をｎとしたとき、Ｔ’はｎ行ｎ列の行列であり、また、ベクトルｑは、全ての成分が１／ｎであるｎ次元の列ベクトルである。
【００４５】
【数７】
0005732995.tif 000008
【００４６】
ここで、式７の表す意味について説明する。パケットの宛先や最短経路を無視して「各ノードが、ある転送確率行列で規定される転送確率のみに従って、あるパケットを転送していく（すなわち、パケットがネットワーク内を動き回る）」場合を考える。この場合、十分に時間が経った後、あるパケットがノードｉに存在する確率は、転送確率行列の固有値１に対応する固有ベクトルのｉ番目成分に等しくなるという性質が知られている。よって、十分時間が経った後に、パケットがノードｉに確率１／ｎで存在する（すなわち、各ノードにパケットが存在する確率が均等である）ための転送確率は、固有値１に対応する固有ベクトルのｉ番目成分が１／ｎである転送確率行列を算出することで算出することができる。すなわち、式７は、この性質を近似的に用いた式であり、式７におけるＴ’は、パケットを各ノードに均一に分散させる転送確率行列を表している。
【００４７】
さらに、転送確率行列Ｔ’は、以下に示す式８、式９および式１０を満たす必要がある。ここで、転送確率行列Ｔ’の要素Ｔ’ ｉｊは、ノードｊがパケットを受信したとき、このパケットをノードｉに転送する確率を表す。
【００４８】
【数８】
0005732995.tif 000009
【００４９】
【数９】
0005732995.tif 000010
【００５０】
【数１０】
0005732995.tif 000011
【００５１】
式８は、パケットを受信したノードｊがノードｉに転送する確率が０以上１以下であることを意味する。式９は、各列（すなわち、各ノードｊ）が、隣接ノードｉに転送する確率の合計が１になることを意味する。また、式１０は、ノードｉとノードｊとの間にリンクが存在しない場合に、転送確率の値が０になることを意味する。ここで、Ａｉｊは、ノードｉとノードｊの間にリンクが張られているときの値が１になり、リンクが張られていないときの値が０になる変数である。ノード間のリンクの有無は、トポロジ情報から判断される。すなわち、式１０は、ノード間のリンクの有無によって定められる転送確率行列Ｔ’の制約条件を表す。
【００５２】
一般に、式８〜式１０の制約を満たしつつ、式７が成り立つＴ’が存在しない場合がある。この場合、パケット分散制御部１２０は、式８〜式１０の制約を満たしつつ、固有値１に対応する固有ベクトルｒがなるべくｑに近くなるＴ’を求める。そして、パケット分散制御部１２０は、Ｔ’のｊ列目の要素を各隣接ノードへの転送確率として、転送先決定部１１０に通知する。パケット分散制御部１２０は、例えば、以下の式１１に示す関数を最小化するＴ’を求めてもよい。
【００５３】
【数１１】
0005732995.tif 000012
【００５４】
パケット分散制御部１２０は、例えば、山登り法や遺伝的アルゴリズムなど、最適化の分野で知られている種々の手法を用いて、式１１に例示する関数を最小化するＴ’を求めればよい。
【００５５】
最短経路制御部１３０は、転送先決定部１１０からの要求に対して、パケットの宛先ノードまでの最短経路をトポロジ情報管理部１５０を参照して探索する。そして、最短経路制御部１３０は、パケットが最短で宛先ノードに到達するための転送先情報を転送先決定部１１０に返信する。なお、この転送先情報には、通信部１４０がパケットを転送する隣接ノードを示す情報も含まれる。最短経路制御部１３０は、例えば、ダイクストラ法など、任意の手法を用いて最短経路を探索する。
【００５６】
転送先決定部１１０と、パケット分散制御部１２０と、最短経路制御部１３０とは、プログラム（パケット中継用プログラム）に従って動作するコンピュータのＣＰＵによって実現される。例えば、プログラムは、ネットワークノード１００の記憶部（図示せず）に記憶され、ＣＰＵは、そのプログラムを読み込み、プログラムに従って、転送先決定部１１０、パケット分散制御部１２０および最短経路制御部１３０として動作してもよい。また、転送先決定部１１０と、パケット分散制御部１２０と、最短経路制御部１３０とは、それぞれが専用のハードウェアで実現されていてもよい。
【００５７】
次に、本実施形態におけるネットワークノード１００の動作を説明する。まず、通信部１４０は、パケットを受信すると（ステップＳ２０１）、転送先決定部１１０にパケットの転送先を問い合わせる。転送先決定部１１０は、パケットの宛先ノードを読み出す（ステップＳ２０２）。パケットの宛先が自身の隣接ノードであれば（ステップＳ２０３におけるＹｅｓ）、転送先決定部１１０は、パケットの転送先を宛先ノードとして通信部１４０からの問い合わせに返答する（ステップＳ２０７）。
【００５８】
一方、パケットの宛先が自身の隣接ノードでない場合（ステップＳ２０３におけるＮｏ）、転送先決定部１１０は、パケットがネットワーク内に均一に分散するための転送確率をパケット分散制御部１２０に問い合わせる。さらに、転送先決定部１１０は、パケットが最短経路を通って宛先ノードに到達するための転送先を最短経路制御部１３０に問い合わせる。パケット分散制御部１２０は、トポロジ情報をもとに転送確率を算出し（ステップＳ２０４）、算出結果を転送先決定部１１０に通知する。また、最短経路制御部１３０は、トポロジ情報をもとに最短経路に基づく転送先を決定し（ステップＳ２０５）、決定した転送先を転送先決定部１１０に通知する。
【００５９】
次に、転送先決定部１１０は、パケット分散制御部１２０が提供する転送確率に従った転送先と、最短経路制御部１３０が決定した転送先とを確率的に選択する（ステップＳ２０６）。転送先決定部１１０は、例えば、確率δでパケット分散制御部１２０が提供する転送確率に従った転送先を選択し、確率１−δで最短経路制御部１３０が決定した転送先を選択する。最後に、通信部１４０は、転送先決定部１１０が指示する転送先に、パケットを転送する（ステップＳ２０８）。
【００６０】
以上のように、本実施形態によれば、パケット分散制御部１２０が、トポロジ情報に基づいて、ネットワーク内の各ノードにパケットを分散させる確率（転送確率）を算出し、最短経路制御部１３０が、トポロジ情報に基づいてパケットの宛先ノードまでの最短経路を決定する。そして、転送先決定部１１０が、転送確率に応じて選択されるノードと最短経路におけるノードを、確率的に選択して転送先ノードと決定する。よって、パケットを中継する際の転送負荷をより効果的に分散できる。
【００６１】
すなわち、本実施形態では、パケットは、常に最短経路に転送されるのではなく、確率δでネットワーク内のノードに均一に分散するよう転送される。その結果、パケットがハブノードに集中することを防止でき、ネットワークの輻輳を回避できる。
【００６２】
また、宛先ノードが隣接するノードの場合、転送先決定部１１０が、その隣接するノードを転送ノードと決定している。このように、転送先が明らかな場合には、無駄な転送処理を抑制することで、転送負荷を効果的に抑制できている。
【００６３】
実施形態２．
図３は、本発明によるパケット中継システムの第２の実施形態の構成例を示すブロック図である。なお、第１の実施形態と同様の構成については、図１と同一の符号を付し、説明を省略する。本実施形態におけるネットワークノード３００は、転送先決定部１１０と、パケット分散制御部３２０と、最短経路制御部１３０と、通信部１４０と、トポロジ情報管理部１５０と、転送容量情報管理部３６０とを備えている。
【００６４】
すなわち、本実施形態のネットワークノード３００は、転送容量情報管理部３６０を備えており、パケット分散制御部３２０の動作がパケット分散制御部１２０の動作と異なる点において、第１の実施形態におけるネットワークノード１００と異なる。
【００６５】
転送容量情報管理部３６０は、ネットワーク内における各ノードのパケット転送容量を示す情報（以下、転送容量情報と記す。）を収集し、収集した転送容量情報を保持する。また、転送容量情報管理部３６０は、パケット分散制御部３２０からの要求に応じて、各ノードの転送容量情報を提供する。
【００６６】
パケット分散制御部３２０は、トポロジ情報管理部１５０が保持するトポロジ情報と、転送容量情報管理部３６０が保持する転送容量情報とを参照し、各ノードの転送容量に比例した量にパケットを分散させる転送確率を算出する。すなわち、パケット分散制御部３２０は、各ノードの転送容量に応じてパケットを分散させる転送確率を算出する。
【００６７】
具体的には、ベクトルｑ’の各成分ｑ’ ｊを、以下の式１２のように定義する。ここで、ベクトルｑ’は、第１の実施形態における固有ベクトルｑに対応するｎ次元の列ベクトルである。また、ｕｊは、各ノードｊの転送容量を表す。すなわち、転送容量が多いノードに対応するｑ’ ｊには、より大きな値が設定される。
【００６８】
【数１２】
0005732995.tif 000013
【００６９】
そして、パケット分散制御部３２０は、以下の式１３に示すように、固有値１に対応する固有ベクトルがベクトルｑ’になる転送確率行列Ｔ’を求める。パケット分散制御部３２０は、Ｔ’のｊ列目の要素を各隣接ノードへの転送確率として、転送先決定部１１０に通知する。
【００７０】
【数１３】
0005732995.tif 000014
【００７１】
ただし、このＴ’についても上記の式８〜式１０を満たす必要がある。しかし、式１３を満たすＴ’が存在しない場合がある。この場合、パケット分散制御部３２０は、式８〜式１０の制約を満たしつつ、固有値１に対応する固有ベクトルｒがなるべくｑ’に近くなるＴ’を求める。そして、パケット分散制御部３２０は、Ｔ’のｊ列目の要素を各隣接ノードへの転送確率として、転送先決定部１１０に通知する。パケット分散制御部３２０は、例えば、以下の式１４に示す関数を最小化するＴ’を求めてもよい。
【００７２】
【数１４】
0005732995.tif 000015
【００７３】
パケット分散制御部３２０は、例えば、山登り法や遺伝的アルゴリズムなど、最適化の分野で知られている種々の手法を用いて、式１４に例示する関数を最小化するＴ’を求めればよい。
【００７４】
転送先決定部１１０と、パケット分散制御部３２０と、最短経路制御部１３０とは、プログラム（パケット中継用プログラム）に従って動作するコンピュータのＣＰＵによって実現される。また、転送先決定部１１０と、パケット分散制御部３２０と、最短経路制御部１３０とは、それぞれが専用のハードウェアで実現されていてもよい。
【００７５】
次に、本実施形態におけるネットワークノード３００の動作を説明する。まず、通信部１４０は、パケットを受信すると（ステップＳ４０１）、転送先決定部１１０にパケットの転送先を問い合わせる。転送先決定部１１０は、パケットの宛先ノードを読み出す（ステップＳ４０２）。パケットの宛先が自身の隣接ノードであれば（ステップＳ４０３におけるＹｅｓ）、転送先決定部１１０は、パケットの転送先を宛先ノードとして通信部１４０からの問い合わせに返答する（ステップＳ４０７）。
【００７６】
一方、パケットの宛先が自身の隣接ノードでない場合（ステップＳ４０３におけるＮｏ）、転送先決定部１１０は、ネットワーク内において各ノードの転送容量に比例した量にパケットを分散させる転送確率をパケット分散制御部３２０に問い合わせる。さらに、転送先決定部１１０は、パケットが最短経路を通って宛先ノードに到達するための転送先を最短経路制御部１３０に問い合わせる。パケット分散制御部３２０は、トポロジ情報および転送容量情報をもとに転送確率を算出し（ステップＳ４０４）、算出結果を転送先決定部１１０に通知する。また、最短経路制御部１３０は、トポロジ情報をもとに最短経路に基づく転送先を決定し（ステップＳ４０５）、決定した転送先を転送先決定部１１０に通知する。
【００７７】
次に、転送先決定部１１０は、パケット分散制御部３２０が提供する転送確率に従った転送先と、最短経路制御部１３０が決定した転送先とを確率的に選択する（ステップＳ４０６）。転送先決定部１１０は、例えば、確率δでパケット分散制御部１２０が提供する転送確率に従った転送先を選択し、確率１−δで最短経路制御部１３０が決定した転送先を選択する。最後に、通信部１４０は、転送先決定部１１０が指示する転送先に、パケットを転送する（ステップＳ４０８）。
【００７８】
以上のように、本実施形態によれば、パケット分散制御部３２０が、トポロジ情報および転送容量情報に基づいて、ネットワーク内の各ノードに、そのノードの転送容量に比例した量のパケットを分散させる転送確率を算出する。すなわち、本実施形態では、パケットは、常に最短経路に転送されるのではなく、確率δでネットワーク内のノードの転送容量に比例した量に分散するよう転送される。その結果、パケットがハブノードに集中することを防止できるとともに、転送容量の乏しいノードの転送負荷が軽減されるため、ネットワークの輻輳を回避できる。
【００７９】
例えば、特許文献１に記載されたパケット経路制御方法では、ネットワーク内における各ノードの転送容量が考慮されていない。すなわち、転送容量の乏しいノードと、転送容量の大きなノードが同列に扱われている。このため、特許文献１に記載されたパケット経路制御方法では、転送容量の乏しいノードがボトルネックになり、輻輳を引き起こす恐れがある。しかし、本実施形態によれば、ノードの転送容量が大きいほど、選択される確率が高くなるため、パケットの転送負荷をより効率的に分散できる。
【００８０】
次に、本発明の最小構成例を説明する。図５は、本発明によるパケット中継システムの最小構成例を示すブロック図である。本発明によるパケット中継システムは、トポロジ情報に基づいて、ネットワーク内の各ノードにパケットを分散させる確率である転送確率（例えば、転送確率行列Ｔ’）を算出する転送確率算出手段８１（例えば、パケット分散制御部１２０）と、トポロジ情報に基づいてパケットの宛先ノードまでの最短経路を決定する最短経路決定手段８２（例えば、最短経路制御部１３０）と、転送確率に応じて選択されるノードと最短経路におけるノードを、確率的に選択して転送先ノードと決定する転送先決定手段８３（例えば、転送先決定部１１０）とを備えている。
【００８１】
そのような構成により、パケットを中継する際の転送負荷をより効果的に分散できる。
【００８２】
上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
【００８３】
（付記１）トポロジ情報に基づいて、ネットワーク内の各ノードにパケットを分散させる確率である転送確率を算出する転送確率算出手段と、トポロジ情報に基づいてパケットの宛先ノードまでの最短経路を決定する最短経路決定手段と、前記転送確率に応じて選択されるノードと前記最短経路におけるノードを、確率的に選択して転送先ノードと決定する転送先決定手段とを備えたことを特徴とするパケット中継システム。
【００８４】
（付記２）転送確率算出手段は、ネットワーク内の各ノードにパケットを略均一に分散させる転送確率を算出する付記１記載のパケット中継システム。
【００８５】
（付記３）ネットワーク内における各ノードのパケット転送容量を示す転送容量情報を記憶する転送容量情報記憶手段を備え、転送確率算出手段は、トポロジ情報および前記転送容量情報に基づいて、ネットワーク内の各ノードに、当該ノードの転送容量に比例した量のパケットを分散させる転送確率を算出する付記１記載のパケット中継システム。
【００８６】
（付記４）転送確率算出手段は、ネットワーク上の各ノードにパケットが存在する確率を固有ベクトルの各成分とする固有値が１である転送確率行列を算出し、算出した転送確率行列における各要素を転送確率とする付記１から付記３のうちのいずれか１つに記載のパケット中継システム。
【００８７】
（付記５）転送先決定手段は、宛先ノードが隣接するノードの場合、当該ノードを転送ノードと決定する付記１から付記４のうちのいずれか１つに記載のパケット中継システム。
【００８８】
（付記６）トポロジ情報に基づいて、ネットワーク内の各ノードにパケットを分散させる確率である転送確率を算出し、トポロジ情報に基づいてパケットの宛先ノードまでの最短経路を決定し、前記転送確率に応じて選択されるノードと前記最短経路におけるノードを、確率的に選択して転送先ノードと決定することを特徴とするパケット中継方法。
【００８９】
（付記７）ネットワーク内の各ノードにパケットを略均一に分散させる転送確率を算出する付記６記載のパケット中継方法。
【００９０】
（付記８）ネットワーク内における各ノードのパケット転送容量およびトポロジ情報に基づいて、ネットワーク内の各ノードに、当該ノードのパケット転送容量に比例した量のパケットを分散させる転送確率を算出する付記６記載のパケット中継方法。
【００９１】
（付記９）コンピュータに、トポロジ情報に基づいて、ネットワーク内の各ノードにパケットを分散させる確率である転送確率を算出する転送確率算出処理、トポロジ情報に基づいてパケットの宛先ノードまでの最短経路を決定する最短経路決定処理、および、前記転送確率に応じて選択されるノードと前記最短経路におけるノードを、確率的に選択して転送先ノードと決定する転送先決定処理を実行させるためのパケット中継用プログラム。
【００９２】
（付記１０）コンピュータに、転送確率算出処理で、ネットワーク内の各ノードにパケットを略均一に分散させる転送確率を算出させる付記９記載のパケット中継用プログラム。
【００９３】
（付記１１）コンピュータに、転送確率算出処理で、ネットワーク内における各ノードのパケット転送容量およびトポロジ情報に基づいて、ネットワーク内の各ノードに、当該ノードのパケット転送容量に比例した量のパケットを分散させる転送確率を算出させる付記９記載のパケット中継システム。
【産業上の利用可能性】
【００９４】
本発明は、パケットの転送負荷分散を実現するパケット中継システムに好適に適用される。例えば、本発明によるパケット中継システムを用いて通信ネットワークを構築することができる。本発明は、例えば、パケット中継用プログラムに従って動作するコンピュータのＣＰＵによって実現することができる。
【符号の説明】
【００９５】
１００，３００  ネットワークノード
１１０  転送先決定部
１２０，３２０  パケット分散制御部
１３０  最短経路制御部
１４０  通信部
１５０  トポロジ情報管理部
３６０  転送容量情報管理部
【図１】
0005732995.tif 000016
【図２】
0005732995.tif 000017
【図３】
0005732995.tif 000018
【図４】
0005732995.tif 000019
【図５】
0005732995.tif 000020