(57)【要約】【課題】ネットワークにおいて、パケットが集中しているノードへのパケットの配送を軽減し、輻輳に対する耐性を向上させる。【解決手段】ネットワークを構成するノード１０はそれぞれ、受信したパケットの配送先ノードを決定するとき、最小コスト経路制御による配送確率と、ランダムウォーク経路制御による配送確率とを所定の割合で混合した配送確率を計算する。そして、その配送確率を、ノード１０の隣接ノードそれぞれのキュー長を考慮して補正し、キュー長の長い（つまり、混雑している）隣接ノードを選択する確率を下げるようにする。そして、このようにして補正した配送確率をもとに、パケットの配送先ノードを決定する。【選択図】図１
2010178062.tif 000002
【特許請求の範囲】
【請求項１】
ネットワーク内のパケットの経路制御を行うノードにおいて、このノードの隣接ノードの中から、前記パケットの次の配送先となる隣接ノードを決定するパケット経路制御装置であって、
記憶部に記憶された前記ネットワークのネットワークトポロジおよび前記ネットワークの各ノード間を接続するリンクのリンクコストを参照して、パケットの宛先ノードｋへの最小コスト経路を計算し、前記最小コスト経路へ接続する隣接ノードを、前記パケットの次の配送先として選択することにより、最小コスト経路制御を行う最小コスト経路制御部と、
前記パケットの次の配送先として、前記自身のノードに隣接する隣接ノードそれぞれを同じ確率で選択することにより、ランダム経路制御を行うランダムウォーク経路制御部とを備え、
前記記憶部に記憶された隣接ノードそれぞれのバッファにおけるキュー長を参照して、自身のノードのバッファから取り出した宛先ノードｋへのパケットの次の配送先として、前記自身のノードの隣接ノードのうち、隣接ノードｊを選択する確率ｐ＾ｋｉｊを、以下の式（１）および式（２）により計算し、この計算した確率ｐ＾ｋｉｊに従い、乱数を発生させ前記宛先ノードｋへのパケットの次の配送先となる隣接ノードを決定するパケット経路制御部とを備えることを特徴とするパケット経路制御装置。
【数７】
2010178062.tif 000010
δ：ｐｋｉｊにおけるｐ（Ｓ）ｋｉｊの混合比率
ｑｊ：隣接ノードｊにおけるキュー長
ｆ（ｑ）：キュー長ｑに関する減少関数
ｐ（Ｓ）ｋｉｊ：前記最小コスト経路制御部による最小コスト経路制御により、宛先ノードｋへのパケットの次の配送先として、自身のノードの隣接ノードのうち、隣接ノードｊを選択する確率
ｐ（Ｒ）ｋｉｊ：前記ランダムウォーク経路制御部によるランダムウォーク経路制御により、宛先ノードｋへのパケットの次の配送先として、自身のノードの隣接ノードのうち、隣接ノードｊを選択する確率
【請求項２】
前記隣接ノードそれぞれのバッファにおけるキュー長の問い合わせを行い、前記記憶部に記憶された隣接ノードそれぞれのバッファにおけるキュー長を最新の情報に書き換えるキュー長取得部を備えることを特徴とする請求項１に記載のパケット経路制御装置。
【請求項３】
前記パケット経路制御部は、前記ｐ＾ｋｉｊを、前記自身のノードの隣接ノードごと、宛先ノードごとに計算しておき、前記計算したｐ＾ｋｉｊの計算結果を配送確率情報として、前記記憶部に記憶し、前記記憶部に記憶された配送確率情報を参照して、乱数を発生させ、前記宛先ノードｋへのパケットの次の配送先となる隣接ノードを決定することを特徴とする請求項１または請求項２に記載のパケット経路制御装置。
【請求項４】
前記式（２）における、減少関数ｆ（ｑ）として、ｆ（ｑ）＝（ｑ＋１）−２を用いたとき、前記式（１）における、δ＝０．９２〜０．９９とすることを特徴とする請求項１から請求項３のいずれか１項に記載のパケット経路制御装置。
【請求項５】
請求項１から請求項４のいずれか１項に記載のパケット経路制御装置を備え、前記パケット経路制御装置により決定された前記パケットの次の配送先となる隣接ノードへパケットを配送するノード。
【請求項６】
前記自身のノードは、宛先ノードとの間にコネクションを確立して通信を行うオーバーレイネットワーク上のノードであり、
前記隣接ノードは、前記コネクションを確立して通信を行う前記宛先ノードであることを特徴とする請求項５に記載のノード。
【請求項７】
ネットワーク内のパケットの経路制御を行うノードにおいて、このノードの隣接ノードの中から、前記パケットの次の配送先となる隣接ノードを決定するパケット経路制御装置のパケット経路制御方法であって、
記憶部に記憶された前記ネットワークのネットワークトポロジおよび前記ネットワークの各ノード間を接続するリンクのリンクコストを参照して、パケットの宛先ノードｋへの最小コスト経路を計算し、前記最小コスト経路へ接続する隣接ノードを、前記パケットの次の配送先として選択することにより、最小コスト経路制御を行う最小コスト経路制御部と、前記パケットの次の配送先として、前記自身のノードに隣接する隣接ノードそれぞれを同じ確率で選択することにより、ランダム経路制御を行うランダムウォーク経路制御部とを備える前記パケット経路制御装置が、
前記記憶部に記憶された隣接ノードそれぞれのバッファにおけるキュー長を参照して、自身のノードのバッファから取り出した宛先ノードｋへのパケットの次の配送先として、前記自身のノードの隣接ノードのうち、隣接ノードｊを選択する確率ｐ＾ｋｉｊを、以下の式（１）および式（２）により計算し、この計算した確率ｐ＾ｋｉｊに従い、乱数を発生させ、前記宛先ノードｋへの次のパケットの配送先となる隣接ノードを決定することを特徴とするパケット経路制御方法。
【数８】
2010178062.tif 000011
δ：ｐｋｉｊにおけるｐ（Ｓ）ｋｉｊの混合比率
ｑｊ：隣接ノードｊにおけるキュー長
ｆ（ｑ）：キュー長ｑに関する減少関数
ｐ（Ｓ）ｋｉｊ：前記最小コスト経路制御部による最小コスト経路制御により、宛先ノードｋへのパケットの次の配送先として、自身のノードの隣接ノードのうち、隣接ノードｊを選択する確率
ｐ（Ｒ）ｋｉｊ：前記ランダムウォーク経路制御部によるランダムウォーク経路制御により、宛先ノードｋへの次のパケットの配送先として、自身のノードの隣接ノードのうち、隣接ノードｊを選択する確率
【請求項８】
コンピュータを、請求項１から請求項４のいずれか１項に記載のパケット経路制御装置として機能させるためのパケット経路制御プログラム。
【請求項９】
請求項８に記載のパケット経路制御プログラムを記録したコンピュータに読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークにおける経路制御技術に関する。
【背景技術】
【０００２】
従来から、通信ネットワーク上を配送されるパケットは、そのパケットが生成された時点で、宛先ノードが決まっている。このパケットを生成したノードがネットワークトポロジの情報を持っていれば、このパケットを生成した時点で、目的とするノードまでの経路を計画することができる。しかし、インターネットでは多くの場合、途中のノードが次のノードまでの経路を決定するホップバイホップルーティングにより経路制御が行われる。各ノードでは、宛先ノードとそれに対応する経路が書き込まれた経路表を備え、受信したパケットの宛先ノードに基づき、次にパケットを配送（転送）すべき隣接ノードを決定する。各ノードはネットワーク状況に関する情報を交換しあって、必要に応じて経路表を更新する。この経路表を作成する方法としては、ＯＳＰＦ（Open Shortest Path First）が一般的である。このＯＳＰＦにおいて、各ノードは、ネットワークトポロジや、各ノード間を接続するリンクのリンクコスト（リンクでの遅延時間等）等の情報を交換する。そして、受信した情報からリンクコストを最小にする経路（最小コスト経路）を計算する。このような最小コスト経路の計算方法としてダイクストラ法が知られている（非特許文献１参照）。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】D. Bertsekas 、R.Gallager、「Data Networks(2nd Edition)」、Prentice Hall、1992
【発明の概要】
【発明が解決しようとする課題】
【０００４】
このダイクストラ法では、最小コスト経路を計算し、その最小コスト経路によりパケットを配送するようにする。しかし、その最小コスト経路上のノードに輻輳が発生した場合、その輻輳が発生したノードを避けた経路を再計算し、その再計算した経路によりパケットを配送するようにしなければならない。よって、輻輳に対してリアルタイムに対応することが困難であった。
【０００５】
本発明は、前記した問題を解決し、ネットワーク内の輻輳に対してリアルタイムに対応し、輻輳発生に対する耐性を向上させることを目的とする。
【課題を解決するための手段】
【０００６】
前記した課題を解決するため、請求項１に記載の発明は、ネットワーク内のパケットの経路制御を行うノードにおいて、このノードの隣接ノードの中から、パケットの次の配送先となる隣接ノードを決定するパケット経路制御装置であって、記憶部に記憶されたネットワークのネットワークトポロジおよびネットワークの各ノード間を接続するリンクのリンクコストを参照して、パケットの宛先ノードｋへの最小コスト経路を計算し、最小コスト経路へ接続する隣接ノードを、パケットの次の配送先として選択することにより、最小コスト経路制御を行う最小コスト経路制御部と、パケットの次の配送先として、自身のノードに隣接する隣接ノードそれぞれを同じ確率で選択することにより、ランダム経路制御を行うランダムウォーク経路制御部とを備え、記憶部に記憶された隣接ノードそれぞれのバッファにおけるキュー長を参照して、自身のノードのバッファから取り出した宛先ノードｋへのパケットの次の配送先として、自身のノードの隣接ノードのうち、隣接ノードｊを選択する確率ｐ＾ｋｉｊを、以下の式（１）および式（２）により計算し、この計算した確率ｐ＾ｋｉｊに従い、乱数を発生させ宛先ノードｋへのパケットの次の配送先となる隣接ノードを決定するパケット経路制御部とを備えることを特徴とする。
【数１】
2010178062.tif 000003
δ：ｐｋｉｊにおけるｐ（Ｓ）ｋｉｊの混合比率
ｑｊ：隣接ノードｊにおけるキュー長
ｆ（ｑ）：キュー長ｑに関する減少関数
ｐ（Ｓ）ｋｉｊ：最小コスト経路制御部による最小コスト経路制御により、宛先ノードｋへのパケットの次の配送先として、自身のノードの隣接ノードのうち、隣接ノードｊを選択する確率
ｐ（Ｒ）ｋｉｊ：ランダムウォーク経路制御部によるランダムウォーク経路制御により、宛先ノードｋへのパケットの次の配送先として、自身のノードの隣接ノードのうち、隣接ノードｊを選択する確率
【０００７】
請求項７に記載の発明は、ネットワーク内のパケットの経路制御を行うノードにおいて、このノードの隣接ノードの中から、パケットの次の配送先となる隣接ノードを決定するパケット経路制御装置のパケット経路制御方法であって、パケット経路制御装置が、記憶部に記憶されたネットワークのネットワークトポロジおよびネットワークの各ノード間を接続するリンクのリンクコストを参照して、パケットの宛先ノードｋへの最小コスト経路を計算し、最小コスト経路へ接続する隣接ノードを、パケットの次の配送先として選択することにより、最小コスト経路制御を行う最小コスト経路制御部と、パケットの次の配送先として、自身のノードに隣接する隣接ノードそれぞれを同じ確率で選択することにより、ランダム経路制御を行うランダムウォーク経路制御部とを備え、記憶部に記憶された隣接ノードそれぞれのバッファにおけるキュー長を参照して、自身のノードのバッファから取り出した宛先ノードｋへのパケットの次の配送先として、自身のノードの隣接ノードのうち、隣接ノードｊを選択する確率ｐ＾ｋｉｊを、以下の式（１）および式（２）により計算し、この計算した確率ｐ＾ｋｉｊに従い、乱数を発生させ、宛先ノードｋへの次のパケットの配送先となる隣接ノードを決定することを特徴とする。
【数２】
2010178062.tif 000004
δ：ｐｋｉｊにおけるｐ（Ｓ）ｋｉｊの混合比率
ｑｊ：隣接ノードｊにおけるキュー長
ｆ（ｑ）：キュー長ｑに関する減少関数
ｐ（Ｓ）ｋｉｊ：最小コスト経路制御部による最小コスト経路制御により、宛先ノードｋへのパケットの次の配送先として、自身のノードの隣接ノードのうち、隣接ノードｊを選択する確率
ｐ（Ｒ）ｋｉｊ：ランダムウォーク経路制御部によるランダムウォーク経路制御により、宛先ノードｋへの次のパケットの配送先として、自身のノードの隣接ノードのうち、隣接ノードｊを選択する確率
【０００８】
このようなパケット経路制御装置は、宛先ノードｋへのパケットの次の配送先として隣接ノードｊを選択する確率ｐ＾ｋｉｊを、最小コスト経路制御よる確率ｐ（ｓ）ｋｉｊと、ランダムウォーク経路制御による確率ｐ（Ｒ）ｋｉｊとを混合した確率として計算する。つまり、パケット経路制御装置は、パケットの次の配送先となる隣接ノードを決定するとき、最小コスト経路の隣接ノードのみならず、ランダムに選択した隣接ノードも選択範囲に含めて決定することになる。また、パケット経路制御装置は、隣接ノードのうち、キュー長の長い隣接ノードを次の配送先として選択する配送確率を低くする。よって、このようなパケット経路制御装置を備えるノードにより構成されるネットワークは、混雑している可能性の高い隣接ノードへのパケットの配送を軽減し、輻輳に対する耐性を向上させることができる。なお、各請求項における隣接ノードｊとは、自身のノードの隣接ノード群におけるｊという隣接ノードという意味であり、宛先ノードｋとは、パケットの宛先ノード群のうち、ｋというノードという意味である。
【０００９】
請求項２に記載の発明は、請求項１のパケット経路制御装置が、隣接ノードそれぞれのバッファにおけるキュー長の問い合わせを行い、記憶部に記憶された隣接ノードそれぞれのバッファにおけるキュー長を最新の情報に書き換えるキュー長取得部を備えることを特徴とする。
【００１０】
このようにすることで、このパケット経路制御装置は、隣接ノードそれぞれのバッファにおける最新のキュー長を考慮して確率ｐ＾ｋｉｊを計算できる。よって、このようなパケット経路制御装置を備えるノードにより構成されるネットワークは、混雑している可能性の高い隣接ノードへのパケットの配送を軽減し、輻輳に対する耐性を向上させることができる。
【００１１】
請求項３に記載の発明は、請求項１または請求項２に記載のパケット経路制御装置のパケット経路制御部が、ｐ＾ｋｉｊを、自身のノードの隣接ノードごと、パケットの宛先ノードごとに計算しておき、計算したｐ＾ｋｉｊの計算結果を配送確率情報として、記憶部に記憶し、記憶部に記憶された配送確率情報を参照して、乱数を発生させ、宛先ノードｋへのパケットの次の配送先となる隣接ノードを決定することを特徴とする。
【００１２】
このようにすることで、パケット経路制御装置は、予め作成しておいた配送確率情報を参照して、宛先ノードへのパケットの次の配送先である隣接ノードを決定するので、パケットを受信するたびに配送確率を計算する必要がなくなる。
【００１３】
請求項４に記載の発明は、請求項１から請求項３のいずれか１項に記載のパケット経路制御装置が、式（２）における、減少関数ｆ（ｑ）として、ｆ（ｑ）＝（ｑ＋１）−２を用いたとき、式（１）における、δ＝０．９２〜０．９９とすることを特徴とする。
【００１４】
このようにすることで、このパケット経路制御装置を備えるノードからなるネットワークにおいて、混雑状態（ネットワーク内のパケット総数が時間に比例して増加する状態）になりにくくすることができる。よって、このようなパケット経路制御装置を備えるノードにより構成されるネットワークにおいて、混雑している可能性の高い隣接ノードへのパケットの配送を軽減し、輻輳に対する耐性を向上させることができる。
【００１５】
請求項５に記載の発明は、請求項１から請求項４のいずれか１項に記載のパケット経路制御装置を備え、パケット経路制御装置により決定されたパケットの次の配送先となる隣接ノードへパケットを配送するノードとした。
【００１６】
このようなノードにより構成されるネットワークにおいて、混雑している可能性の高い隣接ノードへのパケットの配送を軽減し、輻輳に対する耐性を向上させることができる。
【００１７】
請求項６に記載の発明は、請求項５に記載のノードが、宛先ノードとの間にコネクションを確立して通信を行うオーバーレイネットワーク上のノードであり、隣接ノードは、コネクションを確立して通信を行う宛先ノードであることを特徴とする。
【００１８】
このようにすることで、このようなパケット経路制御装置を備えるノードを備えるオーバーレイネットワークの輻輳に対する耐性を向上させることができる。
【００１９】
請求項８に記載の発明は、コンピュータを、請求項１から請求項４のいずれか１項に記載のパケット経路制御装置として機能させるためのパケット経路制御プログラムとした。
【００２０】
このようなプログラムによれば、請求項１から請求項４のいずれか１項に記載のパケット経路制御装置の機能を一般的なコンピュータにより実現できる。
【００２１】
請求項９に記載の発明は、請求項８に記載のパケット経路制御プログラムを記録したコンピュータに読み取り可能な記録媒体とした。
【００２２】
このような記録媒体により、請求項８に記載のパケット経路制御プログラムをコンピュータにインストールすることで、このコンピュータに、請求項１から請求項４のいずれか１項に記載のパケット経路制御装置の機能を実現させることができる。
【発明の効果】
【００２３】
本発明によれば、ネットワークにおいて、パケットが集中している隣接ノードへのパケットの配送を軽減し、ネットワーク全体としての輻輳に対する耐性を向上させることができる。このようにネットワーク全体の混雑を緩和することによって、混雑を起こさずに配送できるパケット数（データ量）を増やすことができる。
【図面の簡単な説明】
【００２４】
【図１】本実施の形態であるパケット経路制御装置（パケット経路制御部）を備えるノードの動作概要を説明した図である。
【図２】パケット経路制御装置（パケット経路制御部）を備えるノードのブロック図である。
【図３】図２のノードの処理手順を示したフローチャートである。
【図４】本実施の形態における最小コスト経路制御による配送確率の計算手順を示したフローチャートである。
【図５】ネットワークの構成を例示した図である。
【図６】本実施の形態におけるランダムウォーク経路制御による配送確率の計算手順を示したフローチャートである。
【発明を実施するための形態】
【００２５】
＜概要＞
以下、本発明を実施するための形態について説明する。まず、図１を参照して、本実施の形態であるパケット経路制御装置（パケット経路制御部）を備えるノード１０のネットワークにおける動作概要を説明する。
【００２６】
ここで、ノード１０は、ネットワークにおいてパケットの経路制御を行うルータ等である。ノード２０は、ユーザ端末やＰＲＯＸＹサーバ等である。このネットワークは、ノード１０（１０Ａ，１０Ｂ，１０Ｃ，１０Ｄ，１０Ｅ，１０Ｆ，１０Ｇ，１０Ｈ）を含んで構成され、ノード１０は、例えば、ノード２０Ａから送信されたパケットの経路制御を行い、このパケットを、宛先ノードであるノード２０Ｂへ到達させる。ここで、現在着目しているノード１０をノードｉ（例えば、ノード１０Ｅ）とすると、このノードｉは、バッファから取り出した宛先ノードｋ（例えば、ノード２０Ｂ）へのパケットを次に隣接ノードｊへ配送する配送確率ｐｋｉｊを、隣接ノードｊとなるノード１０（ノード１０Ａ〜１０Ｄ，１０Ｆ，１０Ｇ）ごとに計算する。そして、その計算した配送確率ｐｋｉｊに基づき、パケットの次の配送先ノードを決定する。つまり、ネットワークのノード１０は、パケットの次の配送先ノードを確率論に基づき選択するので、必ずしも最小コスト経路上のノードを次の配送先ノードとして選択するわけではない。
【００２７】
ここで、ノード１０は、前記した配送確率ｐｋｉｊを、（１）ＯＳＰＦによる最小コスト経路制御（宛先ノードへの最小コスト経路を選択する経路制御）に基づき、宛先ノードｋのパケットを隣接ノードｊへ配送する配送確率ｐ（Ｓ）ｋｉｊと、ランダムウォーク経路制御（隣接ノードそれぞれに同じ確率で配送する経路制御）に基づき、宛先ノードｋのパケットを隣接ノードｊへ配送する配送確率ｐ（Ｒ）ｋｉｊとを所定の割合で混合して計算する。また、ノード１０は、隣接ノードそれぞれから、その隣接ノードにおけるキュー長の情報を取得する。つまり、ノード１０は、隣接ノードそれぞれのパケットの混雑状況を把握する。例えば、ノード１０Ｅは、隣接ノード（ノード１０Ａ〜１０Ｄ，１０Ｆ，１０Ｇ）のキュー長の情報を取得する。
【００２８】
（２）次に、ノード１０は、取得した隣接ノードそれぞれのキュー長をもとに、混雑しているノード１０を避けるような（つまり、混雑しているノード１０を配送先ノードとして選択する確率を低くした）、新たな配送確率ｐ＾ｋｉｊを計算する。（３）そして、ノード１０は、擬似乱数を発生させ、この計算した配送確率ｐ＾ｋｉｊに基づき、次の配送先ノードを決定する。そして、この決定した配送先ノードへパケットを配送する。このようにすることで、例えば、ノード１０Ｅは、最小コスト経路制御によれば、ノード１０Ｄを次の配送先ノードとするところ、配送確率ｐ＾ｋｉｊに基づきノード１０Ｃを次の配送先ノードとして決定する。
【００２９】
以上のような方法で、ネットワークの各ノード１０がパケットの配送先ノードを確率論に基づきに決定することで、各ノード１０は必ずしも最小コスト経路を選択しないことになる。また、各ノード１０は、隣接ノードの混雑状況を把握し、混雑しているノード１０を次の配送先ノードとして選択する確率を低くする。よって、ネットワーク内においてパケットが集中しているノードへのパケットの配送を軽減し、輻輳に対する耐性を向上させることができる。
【００３０】
＜構成＞
次に、このようなノード１０の構成を説明する。図２に示すように、ノード１０の機能は、大きく、入出力部１１、処理部１２および記憶部１３に分けられる。このうち入出力部１１は、隣接ノードからパケットの入力を受け付けたり、隣接ノードへパケットを出力（配送）したりする。処理部１２は、パケットの経路制御を司り、ここでは主に、パケットの次の配送先として隣接ノードｊを選択する確率を計算し、この計算した確率に基づきパケットの次の配送先の隣接ノードを決定する。そして、この決定した隣接ノードへパケットを配送する。記憶部１３は、処理部１２が経路制御のために用いる各種情報を記憶する。
【００３１】
入出力部１１は、入出力インタフェースや通信インタフェースから構成される。また、処理部１２は、このノード１０が備えるＣＰＵ（Central Processing Unit）によるプログラム実行処理や、専用回路等により実現される。さらに、記憶部１３は、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）、ＨＤＤ（Hard Disk Drive）、フラッシュメモリ等の記憶媒体から構成される。なお、ノード１０の処理部１２の機能をプログラム実行処理により実現する場合、記憶部１３には、このノード１０の処理部１２の機能を実現するためのプログラムが格納される。なお、そのプログラムをコンピュータによる読み取り可能な記録媒体（ＣＤ−ＲＯＭ等）に記憶して提供することも可能である。
【００３２】
次に、処理部１２の構成を詳細に説明する。処理部１２は、パケット経路制御部１２１と、パケット配送部１２２と、キュー長取得部１２３とを備える。このうち、パケット経路制御部１２１は、配送確率行列１３５（配送確率情報、詳細は後記）を作成する。そして、その作成した配送確率行列１３５を参照して、宛先ノードｋのパケットの次の配送先となる隣接ノード（以下、配送先ノードと略す）を決定する。このようなパケット経路制御部１２１は、配送確率行列１３５を作成するパケット配送確率計算部１２４と、乱数発生部１２５１により乱数を発生させ、この配送確率行列１３５に示される配送確率に基づきパケットの配送先ノードを決定する配送先決定部１２５とを備える。また、パケット配送部１２２は、パケット経路制御部１２１により決定された配送先ノードへ、入出力部１１経由でパケットを配送する。さらに、キュー長取得部１２３は、隣接ノードそれぞれから、その隣接ノードのバッファのキュー長の情報を取得し、その情報を、記憶部１３のキュー長情報１３３として記録する。また、このキュー長取得部１２３は、他のノード１０（またはノード２０）から、自身のバッファ１３１のキュー長の問い合わせを受けたとき、この問い合わせ元のノード１０へ、自身のバッファ１３１のキュー長の情報を返信する。
【００３３】
パケット配送確率計算部１２４は、（１）最小コスト経路制御部１２４１による最小コスト経路制御に基づき、宛先ノードｋのパケットを隣接ノードｊへ配送する配送確率ｐ（Ｓ）ｋｉｊと、（２）ランダムウォーク経路制御部１２４２によるランダムウォーク経路制御（隣接ノードそれぞれに同じ確率で配送する経路制御）に基づき、宛先ノードｋのパケットを隣接ノードｊへ配送する配送確率ｐ（Ｒ）ｋｉｊとを所定の割合で混合して、宛先ノードｋのパケットを隣接ノードｊへ配送する配送確率ｐｋｉｊを計算する。このパケット配送確率計算部１２４は、隣接ノードそれぞれのキュー長（キュー長情報１３３）をもとに、このｐｋｉｊを修正して配送確率ｐ＾ｋｉｊを得る。つまり、キュー長が長い（つまり、混雑している可能性が高い）隣接ノードを次の配送先ノードとして選択する確率を低くした配送確率ｐ＾ｋｉｊを得る。パケット配送確率計算部１２４は、このようなｐ^ｋｉｊの計算を、自身のノード１０の隣接ノードそれぞれ、宛先ノードそれぞれについて実行する。そして、このときの実行結果をもとに、配送確率行列１３５を作成する。
【００３４】
この最小コスト経路制御部１２４１は、ネットワークトポロジ情報１３２およびリンクコスト情報１３４を参照して、最小コスト経路制御による配送確率ｐ（Ｓ）ｋｉｊを計算する。この配送確率ｐ（Ｓ）ｋｉｊの計算の詳細は、具体例を用いて後記する。また、ランダムウォーク経路制御部１２４２は、ランダムウォーク経路制御による配送確率ｐ（Ｒ）ｋｉｊを計算する。
【００３５】
つまり、パケット配送確率計算部１２４は、以下の式（１）により、配送確率ｐ（Ｓ）ｋｉｊと、配送確率ｐ（Ｒ）ｋｉとを所定の割合で混合して配送確率ｐｋｉｊを計算する。
【数３】
2010178062.tif 000005
δ：ｐｋｉｊにおけるｐ（Ｓ）ｋｉｊの混合比率
【００３６】
このようにパケット配送確率計算部１２４は、最小コスト経路制御の配送確率のみならず、所定割合でランダムウォーク経路制御の配送確率を混合して、配送確率ｐｋｉｊを計算する。そして、ネットワークのノード１０それぞれが、このようにして計算した配送確率ｐｋｉｊに基づき、パケットの次の配送先ノードを決定することで、ネットワークにおけるパケットの配送経路が適度に分散するようになる。つまり、ネットワーク内に輻輳が発生しにくくなる。
【００３７】
また、パケット配送確率計算部１２４は、記憶部１３に記憶されたキュー長情報１３３（隣接ノードそれぞれのキュー長）をもとに、以下の式（２）に基づき、配送確率ｐｋｉｊを修正する。
【数４】
2010178062.tif 000006
ｑｊ：隣接ノードｊにおけるキュー長
ｆ（ｑ）：キュー長ｑに関する減少関数
【００３８】
つまり、パケット配送確率計算部１２４は、配送確率ｐｋｉｊに対し、その隣接ノードｊのキュー長と、自身のノード１０の隣接ノード（隣接ノードl）それぞれのキュー長および宛先ノードｋへのパケットを、次にその隣接ノードｌへ配送する配送確率ｐｋｉｌを乗算した値とを用いて重み付けを行い、配送確率ｐ^ｋｉｊを得る。ここで、ｆ（ｑ）は、キュー長ｑに関する減少関数であり、キュー長ｑが長い程、ｆ（ｑ）の値は小さいものとなる。また、ここで用いるｆ（ｑ）として、べき型、指数型等の関数を用いることができる。例えば、ｆ（ｑ）＝（ｑ＋１）−αや、ｆ（ｑ）＝ｅｘｐ（−１０−βｑ）等を用いることができる。ｆ（ｑ）＝（ｑ＋１）−２を用いた場合、前記した式（１）におけるδの値は、例えば、δ＝０．９２〜０．９９とする。このときの実験結果については、後記する。
【００３９】
また、記憶部１３は、バッファ１３１を所定領域に備え、ネットワークトポロジ情報１３２と、キュー長情報１３３と、リンクコスト情報１３４と、配送確率行列１３５とを記憶する。
【００４０】
バッファ１３１は、パケットを一時的に蓄積する。ここで蓄積されたパケットは、他のノード１０，２０から受信したもののほか、自身のノード１０で新たに生成されたパケットを含んでいてもよい。この新たに生成されたパケットや、他のノード１０，２０から受信したパケットは、このバッファ１３１において既に蓄積されているパケットの最後尾に蓄積される。なお、バッファ１３１で配送を待っているパケットのバイト長をキュー長と呼ぶ。
【００４１】
ネットワークトポロジ情報１３２は、ネットワーク全体のトポロジを示した情報である。すなわち、このネットワークトポロジ情報１３２は、ネットワークにおいて、どのノード１０，２０と、どのノード１０，２０とが接続されているかを示した情報である。
【００４２】
キュー長情報１３３は、隣接ノードそれぞれのバッファにおけるキュー長を示した情報である。このキュー長情報１３３は、キュー長取得部１２３により取得される最新のキュー長情報により更新される。
【００４３】
リンクコスト情報１３４は、ネットワークトポロジ情報１３２に示される各ノード間を接続するリンクのリンクコストを示した情報である。
【００４４】
配送確率行列１３５は、宛先ノードｋごと、隣接ノードごとの配送確率ｐ＾ｋｉｊを示した情報である。この配送確率ｐ＾ｋｉｊは、配送先決定部１２５がパケットの配送先ノードを決定するときに参照される。
【００４５】
このようなノード１０によりネットワークを構成することで、ネットワーク内において混雑している可能性の高いノードへのパケットの配送を軽減し、輻輳に対する耐性を向上させることができる。
【００４６】
＜処理手順＞
次に、図２を参照しつつ、図３を用いて、ノード１０の処理手順を説明する。なお、ここでは事前に、ノード１０が配送確率行列１３５を作成して、記憶部１３に記憶しておくものとする。
【００４７】
まず、図２のノード１０のパケット配送部１２２は、新規パケットをバッファ１３１から取り出し（Ｓ１０１）、このパケットの宛先ノード（宛先ノードの識別情報）を読み出す（Ｓ１０２）。ここで、この宛先ノードが隣接ノードであれば（Ｓ１０３のＹｅｓ）、パケット配送部１２２は、この宛先ノード（つまり、隣接ノード）へパケットを配送して（Ｓ１０４）、Ｓ１０１へ戻る。一方、Ｓ１０３において、宛先ノードが隣接ノードではなかったとき（Ｓ１０３のＮｏ）、キュー長取得部１２３は、キュー長情報１３３に最新のキュー長情報があるか否かを判断する（Ｓ１０５）。ここで、最新のキュー長情報がなかったとき（Ｓ１０５のＮｏ）、例えば、キュー長情報が、前回の取得から既に所定時間以上の経過したものであるとき、キュー長取得部１２３は、隣接ノードへキュー長の問い合わせを行い（Ｓ１０６）、この問い合わせの結果得られた隣接ノードのキュー長の情報を、キュー長情報１３３として記憶部１３に記録する。そして、パケット配送確率計算部１２４は、この最新のキュー長情報を用いて配送確率行列１３５を更新する。そして、Ｓ１０７へ進む。一方、最新のキュー長情報があったとき（Ｓ１０５のＹｅｓ）、Ｓ１０６をスキップして、Ｓ１０７へ進む。
【００４８】
Ｓ１０５またはＳ１０６の後、パケット配送確率計算部１２４は、パケットの宛先ノードと、配送確率行列１３５とを参照して、このパケットの配送確率を計算する（Ｓ１０７）。つまり、配送確率行列１３５から、このパケットの配送確率を読み出す。そして、この配送確率を配送先決定部１２５へ出力する。
【００４９】
Ｓ１０７の後、配送先決定部１２５は、乱数により、このパケットの配送先を決定する（Ｓ１０８）。つまり、配送先決定部１２５は、乱数発生部１２５１により乱数を発生させ、パケット配送確率計算部１２４から出力された配送確率に基づき、このパケットの配送先を決定する。
【００５０】
そして、パケット経路制御部１２２は、この配送先決定部１２５により決定された配送先ノードへパケットを配信する（Ｓ１０９）。
【００５１】
このような処理をノード１０はバッファ１３１から新規パケットを取り出すたびに実行する。ここで、ノード１０が、パケットの配送確率の計算に用いる配送確率行列１３５は、前記したとおり、最小コスト経路制御による配送確率ｐ（Ｓ）ｋｉｊと、ランダムウォーク経路制御による配送確率ｐ（Ｒ）ｋｉｊとを所定の割合で混合して計算した配送確率であり、また、この配送確率行列１３５に示される配送確率も、隣接ノードの混雑状況を考慮したものである。よって、ネットワークにおけるパケットの配送経路が適度に分散するようになり、その結果、ネットワークに輻輳が発生しにくくなる。
【００５２】
＜最小コスト経路制御の配送確率＞
ここで、前記した最小コスト経路制御部１２４１が最小コスト経路制御により配送確率ｐ（Ｓ）ｋｉｊを計算するためのアルゴリズムを、図４を用いて、詳細に説明する。この最小コスト経路制御とは、パケットの発生した発生ノードから宛先ノードまでの経路で経由するリンクのリンクコストの和が最小になるようなノード系列の経路による経路制御のことである。なお、各リンクのリンクコストが同じであるとすると、最小コスト経路制御は、最短経路制御に一致する。また、宛先ノードまでの経路が複数ある場合、その経路は、同じ確率でランダムに選択するものとする。つまり、ここでのｐｋｉｊは、隣接ノードｊを通る最小コスト経路の数を、宛先ノードｋへの最小コスト経路の総数で割った値となる。
【００５３】
ここで、アルゴリズム中に登場する変数は以下の通りである。
Ｖ：すべてのノード集合
Ｐ：最小コスト（またはホップ数）が確定したノード集合
Ｅｊ：ノードｊから配送されるべきノード集合
Ｎｊ：ノードｊから、ノードｋまでの最小コスト経路の数
ｄｊ：ノードｊから、ノードｋまでのコスト（またはホップ数）
ｃｉｊ：ノードｉ（自身のノード１０）から、ノードｊへのリンクコスト
【００５４】
まず、図２のノード１０の最小コスト経路制御部１２４１は、前処理として、トポロジ（ネットワークトポロジ情報１３２）とリンクコスト情報１３４とを収集し（Ｓ２０１）、記憶部１３に記憶する。
【００５５】
そして、最小コスト経路制御部１２４１は、各変数の初期化を行う（Ｓ２０２）。つまり、最小コスト経路制御部１２４１は、各変数に以下のような値を設定する。なお、「＼」は、ある集合からある集合を取り除いた集合を示す。例えば、Ｖ＼｛Ｓ｝であれば、ＶからＳを除いた集合を示す。
ｄＳ＝０、ｄｊ＝∞  for ｊ∈Ｖ＼｛Ｓ｝
Ｐ＝φ
Ｎｓ＝１、Ｎｊ＝０  for   j≠Ｓ
Ｅｊ＝φ  for ｊ∈Ｖ
ｐｉｊ＝０  for ｉ，ｊ∈Ｖ
【００５６】
次に、最小コスト経路制御部１２４１は、最小コスト確定ノードを抽出し、そのノードの配送確率を計算する（Ｓ２０３）。つまり、最小コスト経路制御部１２４１は、
Ｑ＝argminｊ∈Ｖ＼Ｐ｛ｄｊ｝
ｐｉｌ＝Ｎｌ／Ｎｊ  for ｊ∈Ｑ，ｌ∈Ｅｊ
Ｐ＝Ｐ∪Ｑ
とする。
【００５７】
次に、最小コスト経路制御部１２４１は、未確定ノードの最小コスト（仮最小コスト）を更新する。そして、それを実現する配送先（配送先ノード）を抽出する。また、そのときの最小コスト経路数を計算する（Ｓ２０４）。つまり、最小コスト経路制御部１２４１は、
Ｅｊ＝argminｊ∈Ｖ＼Ｐ｛ｄｊ＋ｃｊｉ｝  for ｉ∈Ｖ＼Ｐ
ｄｊ＝minｊ∈Ｖ＼Ｐ｛ｄｊ＋ｃｊｉ｝  for ｉ∈Ｖ＼Ｐ
Ｎｊ＝Σｌ∈ＥｌＮｌ
とする。
【００５８】
そして、最小コスト経路制御部１２４１は、最小コストがすべて確定したとき（Ｓ２０５のＹｅｓ）、処理を終了する。一方、まだ最小コストが確定していないとき（Ｓ２０５のＮｏ）、Ｓ２０３へ戻る。
【００５９】
以上の処理を、具体例を用いて説明する。ここでは、ネットワークが図５に示す構成であった場合を例に説明する。ネットワークは、ノードＡ〜Ｉにより構成されているものとする。また、ノードＡを宛先ノードとする。ここでは説明を簡単にするために、ホップ数のみに着目するのでｃｉｊ＝１とする。
【００６０】
最小コスト経路制御部１２４１は、Ｓ２０２において各変数の初期化の手順に従い、各変数に初期値を代入する。つまり、最小コスト経路制御部１２４１は、
ｄＡ＝０、ｄＢ＝ｄＣ＝…＝ｄＩ＝∞
ＥＡ＝ＥＢ＝…＝ＥＩ＝０
ＮＡ＝１，ＮＢ＝ＮＣ＝…＝ＮＩ＝０
Ｐ＝φ，ｐｉｊ＝０
とする。
【００６１】
次に、最小コスト経路制御部１２４１は、Ｓ２０３において、最小のｄｊを見つけるが、今のところ宛先ノードであるノードＡだけである。ホップ数ももちろん０である。つまり、最小コスト経路制御部１２４１は、
Ｐ＝Ｑ＝｛Ａ｝，ｄＡ＝０
を得る。
【００６２】
そして、最小コスト経路制御部１２４１は、Ｓ２０４において、ｃＡｊ＝１となるノードｊ、つまり隣接ノードに関する変数を更新する。すなわち、最小コスト経路制御部１２４１は、
ｄＢ＝ｄＣ＝１，ＥＢ＝ＥＣ＝｛Ａ｝，ＮＢ＝ＮＣ＝１
とする。
【００６３】
ここでは、まだすべての最小コストは確定していないので（Ｓ２０５のＮｏ）、Ｓ２０３へ戻るが、最小ホップ数のノード１０は、ノードＢ，Ｃである。よって、最小コスト経路制御部１２４１は、
Ｑ＝｛Ｂ，Ｃ｝、Ｐ＝｛Ａ，Ｂ，Ｃ｝
ｐＢＡ＝ＮＡ／ＮＢ＝１，ｐＣＡ＝ＮＡ／ＮＣ＝１
を得る。
【００６４】
この後、最小コスト経路制御部１２４１は、Ｓ２０４へ進み、ノードＤ，Ｅ，Ｆ，Ｇの値を更新する。つまり、最小コスト経路制御部１２４１は、
ｄＤ＝ｄＥ＝ｄＦ＝ｄＧ＝２
ＥＤ＝ＥＥ＝｛Ｂ｝，ＥＦ＝｛Ｂ，Ｃ｝，ＥＧ｛Ｃ｝
ＮＤ＝ＥＥ＝ＮＧ＝１，ＮＦ＝２
とする。
【００６５】
さらに、最小コスト経路制御部１２４１は、Ｓ２０３へ戻り、
Ｑ＝｛Ｄ，Ｅ，Ｆ，Ｇ｝、Ｐ＝｛Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，Ｇ｝
ｐＤＢ＝ｐＥＢ＝ｐＧＣ＝１，ｐＦＢ＝ＮB／ＮＦ＝＝１／２，ｐＦＣ＝ＮＣ／ＮＦ＝＝１／２
を得る。また、Ｓ２０４へ進み、
ｄＨ＝ｄＩ＝３
ＥＨ＝｛Ｄ，Ｆ｝，Ｅｌ＝｛Ｅ，Ｆ，Ｇ｝
ＮＨ＝ＮＤ＋ＮＦ＝３，Ｎｉ＝ＮＥ＋ＮＦ＋ＮＧ＝４
を得る。
【００６６】
そして、最終的に最小コスト経路制御部１２４１は、
Ｑ＝｛Ｈ，Ｉ｝、Ｐ＝｛Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，Ｇ，Ｈ，Ｉ｝
ｐＨＤ＝ＮＤ／ＮＨ＝＝１／３，ｐＨＦ＝ＮＦ／ＮＨ＝＝２／３，ｐＩＥ＝ＮＥ／ＮＩ＝＝１／４，
ｐＩＦ＝ＮＦ／ＮＩ＝＝２／４＝１／２，ｐＩＧ＝ＮＧ／ＮＩ＝１／４
を得る。
【００６７】
＜ランダムウォーク経路制御の配送確率＞
次に、図６を用いて、前記したランダムウォーク経路制御部１２４２がランダムウォーク経路制御により配送確率ｐ（Ｒ）ｋｉｊを計算するためのアルゴリズムを説明する。ここでは、現在着目しているノード１０をノードｉ、このノードｉ以外のノード１０をノードｊとする。
【００６８】
まず、ランダムウォーク経路制御部１２４２は、パケットの宛先ノードｋが、ノードｉ（自身のノード１０）でなく（Ｓ３０１のＮｏ）、かつ、この宛先ノードｋが、ノードｊでなく（Ｓ３０３のＮｏ）、ノードｊがノードｉの隣接ノードであったとき（Ｓ３０５のＹｅｓ）、ノードｉのｄｅｇｒｅｅ（ｉ）（ノードｉの次数。つまり、ノードｉの隣接ノードの数）の逆数を用いることで、ｐ（Ｒ）ｋｉｊを計算する（Ｓ３０６）。一方、宛先ノードｋが、ノードｉ（自身のノード１０）であるとき（Ｓ３０１のＹｅｓ）、ｐ（Ｒ）ｋｉｊ＝０とする（Ｓ３０２）。また、宛先ノードｋがノードｊであるとき（Ｓ３０３のＹｅｓ）、ｐ（Ｒ）ｋｉｊ＝１とする（Ｓ３０４）。なお、ノードｊがノードｉの隣接ノードでなかったとき（Ｓ３０５のＮｏ）、ｐ（Ｒ）ｋｉｊ＝０とする（Ｓ３０７）。
【００６９】
このようにすることで、ランダムウォーク経路制御部１２４２は、自身のノードｉにリンク接続される各隣接ノードとも同じ確率のｐ（Ｒ）ｋｉｊを計算する。また、パケットの宛先ノードｋが隣接ノードであれば、ｐ（Ｒ）ｋｉｊ＝１とするので、そのパケットを確実にその隣接ノードへ配送するようにできる。
【００７０】
なお、図１で説明したノード２０は、宛先ノードｆであるノード２０との間にコネクションを確立して通信を行うオーバーレイネットワーク上のノードであってもよい。この場合、コネクションを確立して通信を行う経路上のいずれかのノード２０を隣接ノードとして考えればよい。このようにすることで、オーバーレイネットワークの輻輳に対する耐性を向上させることができる。
【００７１】
＜実験結果＞
次に、前記したノード１０を用いたシミュレーション実験の結果を説明する。ここで構築したネットワークはBarabasi−Albert（Albert-Laszlo Barabasi, Reka Albert“Emergence of Scaling in Random Networks”，Science 286, p509-512,1999参照）に従い、指数が−３の、べき次数分布になるものである。
【００７２】
ここで、ネットワーク内で時刻ｔ＝０からパケットが発生し始め、現在時刻ｔだとする。この場合、これまでに発生したパケット総数をＧ（ｔ）とすると、ここで用いたモデルでは、＜Ｇ（ｔ）＞=ρＮｔとなる。＜＞は期待値を示す。また、ρはパケットの発生率である。また、Ｎはネットワークのノード数である。現在ネットワーク中に滞在しているパケット数をＭ（ｔ）とする。過渡期の影響を無視できる充分大きなｔで考えると、Ｍ（ｔ）は、以下の式（３）により表される。
【数５】
2010178062.tif 000007
【００７３】
ただし、ｂρおよびｃρはρの関数である。ρが、閾値ρＣよりも小さければ、ネットワーク中のパケット総数Ｍ（ｔ）は、時刻ｔに関係なく所定の値ｃρのままとなる。Ｌｉｔｔｌｅの法則によれば、パケットのネットワーク内の平均滞在時間は、ネットワーク内の滞留パケット数に比例するので、パケットは有限時間内で宛先ノードへと到着することになる。このときのネットワークの状態を非混雑状態という。一方、ρが閾値ρＣよりも大きければ、ネットワーク中のパケット総数は、時刻ｔに比例して増加する。このときパケットの到着時間はいくらでも大きくなり、この状態を混雑状態という。ここで混雑状態の指標として、以下の式（４）により計算されるηを考える。
【数６】
2010178062.tif 000008
【００７４】
式（４）において、非混雑状態では、η＝０となり、混雑状態ではη＝ｂρ／（ρＮ）＞０となるので、ηの値をみていれば混雑状態か否かを判別することができる。ここで、非混雑状態から、混雑状態に変化するρＣを、臨界パケット発生率ということにする。
【００７５】
ここで、ネットワークを、ノード１０を用いて構成し、そのネットワークは、１０００個のノード１０を備えることとした。ここで、前記した式（２）におけるキュー長ｑの減少関数としてｆ（ｑ）＝（ｑ＋１）−２を用いた。η＝０．００１を基準として、この基準値を超えるρをρＣとして求めた。ここで、式（１）におけるδの値を変えたときの臨界パケット発生率ρＣを以下の表１に示す。
【００７６】
【表１】
2010178062.tif 000009
【００７７】
表１に示すように、各ノード１０において配送先ノードを決定するとき、前記した式（１）の配送確率ｐｋｉｊを、最小コスト経路制御による配送確率ｐ（ｓ）ｋｉｊのみを用いて計算した場合（δ＝１.０）に比べ、この配送確率ｐ（ｓ）ｋｉｊにランダムウォーク経路制御により配送確率ｐ（Ｒ）ｋｉｊと混合した場合の方が、臨界パケット発生率ρＣの値が約３倍向上することが分かる。特にδ＝０．９２〜０．９９とすることで、ρＣ＝０．０３４となり、臨界パケット発生率ρＣの値が極めて向上していることが分かる。以上のことから、ネットワークを構成するノードとして、パケット経路制御部１２１を備えるノード１０を用いることで、ネットワーク内の輻輳に対する耐性を向上させることが確認できた。
【符号の説明】
【００７８】
１０（１０Ａ〜１０Ｈ），２０（２０Ａ〜２０Ｃ）  ノード
１１    入出力部
１２    処理部
１３    記憶部
１２１  パケット経路制御部（パケット経路制御装置）
１２２  パケット配送部
１２３  キュー長取得部
１２４  パケット配送確率計算部
１２５  配送先決定部
１３１  バッファ
１３２  ネットワークトポロジ情報
１３３  キュー長情報
１３４  リンクコスト情報
１３５  配送確率行列（配送確率情報）
１２４１  最小コスト経路制御部
１２４２  ランダムウォーク経路制御部
１２５１  乱数発生部
【図１】
2010178062.tif 000012
【図２】
2010178062.tif 000013
【図３】
2010178062.tif 000014
【図４】
2010178062.tif 000015
【図５】
2010178062.tif 000016
【図６】
2010178062.tif 000017