(57)【特許請求の範囲】
【請求項１】
通信パケットを転送するルータ装置であって、
当該ルータ装置以外の通信先に宛てた通信パケットを受信する受信部と、
当該ルータ装置に隣接する１ないし複数の隣接ルータが前記通信パケットを宛先に転送するためのコスト値を各前記隣接ルータについて計算する計算部と、
いずれの前記隣接ルータを前記通信パケットの転送先とするかを前記計算部が計算したコスト値に基づき決定する転送先決定部と、
を備え、
前記計算部は、
前記隣接ルータのノード次数と、
前記隣接ルータから宛先までの前記通信パケットのホップ数と、
前記コスト値に対する前記ノード次数と前記ホップ数の寄与度を定めた係数と、
を用いて前記コスト値を計算する
ことを特徴とするルータ装置。
【請求項２】
前記計算部は、
前記係数をαとして次式により前記コスト値（Ｈｉ）を計算する
ことを特徴とする請求項１記載のルータ装置。
【数１】
0004623139.tif 000006
【請求項３】
各前記隣接ルータからその隣接ルータのノード次数を受信する次数受信部と、
当該ルータ装置のノード次数を取得する次数取得部と、
前記次数受信部が受信したノード次数および前記次数取得部が取得したノード次数を格納する記憶部と、
を備え、
前記計算部は、
前記記憶部に格納されている前記ノード次数を参照して前記コスト値を計算する
ことを特徴とする請求項１または請求項２記載のルータ装置。
【請求項４】
通信パケットを転送するルータ装置であって、
当該ルータ装置以外の通信先に宛てた通信パケットを受信する受信部と、
当該ルータ装置に隣接する１ないし複数の隣接ルータが前記通信パケットを宛先に転送するためのコスト値を各前記隣接ルータについて計算する計算部と、
いずれの前記隣接ルータを前記通信パケットの転送先とするかを前記計算部が計算したコスト値に基づき決定する転送先決定部と、
パラメータ計算部と、
を備え、
前記計算部は、
前記隣接ルータのキュー長と、
前記隣接ルータから宛先までの前記通信パケットのホップ数と、
前記コスト値に対する前記キュー長と前記ホップ数の寄与度を定めた係数と、
を用いて前記コスト値を計算し、
前記パラメータ計算部は、
前記キュー長の標本分散を用いた演算式で前記係数を求め、
前記演算式は、
前記標本分散が小さくなるほど前記キュー長の前記寄与度が小さくなるように前記係数を算出するよう構成されている
ことを特徴とするルータ装置。
【請求項５】
各前記隣接ルータからその隣接ルータのキュー長を受信するキュー長受信部と、
当該ルータ装置のキュー長を取得するキュー長取得部と、
前記キュー長受信部が受信したキュー長および前記キュー長取得部が取得したキュー長を格納する記憶部と、
を備え、
前記計算部は、
前記記憶部に格納されている前記キュー長を参照して前記コスト値を計算する
ことを特徴とする請求項４に記載のルータ装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信パケットを転送するルータ装置に関するものである。
【背景技術】
【０００２】
ネットワーク内に流すことができるトラフィック総量は、そのネットワークの性能を測る指標ともなり重要である。トラフィック総量を増加させるために、下記非特許文献１では、ルータのパケット転送方式を提案している。
下記非特許文献１で提案されている方式は、目的アドレスまでのホップ数とキュー待ち時間を考慮に入れたものである。これにより輻輳を回避したルーティングが可能となる。ルーティングの手順は、以下の（１）〜（２）の通りである。
【０００３】
（１）パケットを転送するルータが転送先ルータを決定する時に、各隣接ルータｉについて、下記（式１）に示す重みＨｉを算出する。
【数１】
0004623139.tif 000002
【０００４】
上記（式１）は、パケットがノードｉを通過する時のコストを表す。つまり、ルータｉを通る時に、右辺第１項はそのパケットが処理されるまでの時間的コストを表し、右辺第２項はパケットが目的アドレスに到達するまでの距離的コストを表す。
【０００５】
（２）パケットを転送するルータは、上記（式１）でこの重みＨｉが最小となる隣接ルータを転送先ルータと決定し、パケットを転送する。
時間的コストを加味することで、転送したパケットが処理されるまでに時間のかかる、混雑したルータを避けたルーティングを実現することができる。
このような手順により、宛先までのホップ数のみを考えてルーティングするＲＩＰ（Ｒｏｕｔｉｎｇ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｐｒｏｔｏｃｏｌ）やＯＳＰＦ（Ｏｐｅｎ  Ｓｈｏｒｔｅｓｔ  Ｐａｔｈ  Ｆｉｒｓｔ）のようなルーティングプロトコルを用いた場合に比べ、ネットワークのトラフィック総量を増加させることができる。
【０００６】
【非特許文献１】Ｚｈｅｎ  Ｙｉ  Ｃｈｅｎ  ａｎｄ  Ｘｉａｏ  Ｆａｎ  Ｗａｎｇ，”Ｅｆｆｅｃｔｓ  ｏｆ  ｎｅｔｗｏｒｋ  ｓｔｒｕｃｔｕｒｅ  ａｎｄ  ｒｏｕｔｉｎｇ  ｓｔｒａｔｅｇｙ  ｏｎ  ｎｅｔｗｏｒｋ  ｃａｐａｃｉｔｙ”，ＰＨＹＳＩＣＡＬ  ＲＥＶＩＥＷ  Ｅ，７３，０３６１０７，２００６
【発明の開示】
【発明が解決しようとする課題】
【０００７】
上記非特許文献１に記載の転送方式では、隣接ルータにキュー待ち時間を知らせる必要がある。全ての隣接ルータにキュー待ち時間を通知するパケットを流すと、各ルータがそのパケットを処理するための負荷が増加し、ネットワークのトラフィックを圧迫する恐れがある。
【０００８】
一方、上記（式１）において、キュー待ち時間とホップ数をどれくらいの割合で重みＨｉに反映させるかを決めるパラメータαの決定が課題となる。
従来技術の文献のＦＩＧ．２〜４には、ネットワークのトポロジーが異なれば、λｃｒｉｔ（ネットワークを構成するルータが単位時間当たりに発生させられるパケット量の最大値）を最大にするαが異なることが記載されている。
これは、ネットワークのトラフィック総量を最大にするαがネットワークのトポロジーにより異なるので、最適なαを決定するためには、ネットワーク全体のトポロジーをあらかじめ知っておかなければならないことを示している。
【０００９】
しかし、上記非特許文献１では、特定のネットワークトポロジーに対してトラフィック総量が最大になるαを示してはいるものの、実在するネットワークに対してαを決定する方法については何ら言及されていない。
そのため、実際のネットワークでαを固定にしたルーティング方式を適用しようとした場合、トラフィック総量を最大にするαがネットワークのトポロジーにより異なることに鑑み、αを決定するためにネットワーク全体のトポロジーを知らなければならないが、このようなことは現実的ではない。
【００１０】
以上説明した理由から、全ての隣接ルータにキュー待ち時間を通知するパケットを流すことなく、輻輳を回避した効率の良いルーティングを行うことのできるルータ装置が望まれていた。
【課題を解決するための手段】
【００１１】
本発明に係るルータ装置は、通信パケットを転送するルータ装置であって、当該ルータ装置以外の通信先に宛てた通信パケットを受信する受信部と、当該ルータ装置に隣接する１ないし複数の隣接ルータが前記通信パケットを宛先に転送するためのコスト値を各前記隣接ルータについて計算する計算部と、いずれの前記隣接ルータを前記通信パケットの転送先とするかを前記計算部が計算したコスト値に基づき決定する転送先決定部と、を備え、前記計算部は、前記隣接ルータのノード次数と、前記隣接ルータから宛先までの前記通信パケットのホップ数と、前記コスト値に対する前記ノード次数と前記ホップ数の寄与度を定めた係数と、を用いて前記コスト値を計算するものである。
【発明の効果】
【００１２】
本発明に係るルータ装置によれば、キュー待ち時間よりも変更頻度の小さいノード次数を用いて転送コスト値を計算するので、ノード次数を通知するパケットを受信したルータ装置の負荷を軽減することができる。
また、転送先ルータを決定する際にノード次数を考慮することで、輻輳を生じやすいルータを回避することができ、これによりネットワークのトラフィック総量を増加させることができる。
【発明を実施するための最良の形態】
【００１３】
実施の形態１．
図１は、本発明の実施の形態１に係るルータ１００の機能ブロック図である。
ルータ１００は、記憶部１１１、使用頻度記憶部１１２、パケット受信部１２１、コスト計算部１２２、転送先決定部１２３、パケット送信部１２４、ホップ数受信部１３１、次数受信部１４１、次数取得部１４２、次数通知部１４３を備える。
【００１４】
記憶部１１１は、ルータ１００、およびルータ１００にネットワーク上で隣接するルータ（以下、隣接ルータと呼ぶ）全てのノード次数と、任意の隣接ルータからある宛先アドレスまでのホップ数の情報を保持する。ノード次数とは、ルータ１００の隣接ルータの数を意味する。
使用頻度記憶部１１２は、コスト計算部１２２が記憶部１１１内に格納されているホップ数情報を参照した頻度を管理する。この参照頻度の使用方法については、後述の図３で説明する。
【００１５】
パケット受信部１２１は、隣接ルータからパケットを受信する。
コスト計算部１２２は、パケット受信部１２１が受信したパケットを転送する先の隣接ルータを決定するために用いる、各隣接ルータのコスト値Ｈｉを計算する。コスト値Ｈｉとは、後述の（式２）で算出される値であり、当該隣接ルータがパケットを宛先に転送するために要するコストを表すものである。詳細は後述する。
【００１６】
転送先決定部１２３は、コスト計算部１２２が算出したコスト値が最小となる隣接ルータを求め、その隣接ルータを、パケット受信部１２１が受信したパケットの転送先ルータとして決定する。
パケット送信部１２４は、転送先決定部１２３が決定した転送先の隣接ルータに、パケット受信部１２１が受信したパケットを転送する。
【００１７】
ホップ数受信部１３１は、ＲＩＰやＯＳＰＦなどのルーティングプロトコルの広告によって、隣接ルータ毎に、当該隣接ルータがパケットを転送する宛先の候補となるアドレスと、そのアドレスまでのホップ数を取得する。
また、ホップ数受信部１３１は、コスト計算部１２２より、ある隣接ルータからあるアドレスまでのホップ数を取得すべき旨のリクエストを受け取る。次に、その隣接ルータに対し広告のリクエストを行い、要求されたアドレスまでのホップ数をルーティングプロトコルの広告により取得する。
ホップ数受信部１３１は、取得した情報を記憶部１１１に格納し、またはコスト計算部１２２に出力する。
【００１８】
なお、広告とは、ＲＩＰやＯＳＰＦなどのルーティングプロトコルで用いられる、あるアドレスとそのアドレスまでのホップ数の情報を含んだメッセージを指す。広告の送信を依頼することをリクエストと呼ぶ。
【００１９】
次数受信部１４１は、任意の隣接ルータから当該隣接ルータのノード次数の通知を受け取り、記憶部１１１にその情報を格納する。
次数取得部１４２は、ルータ１００に隣接するルータ数、即ちノード次数を取得する。
次数通知部１４３は、ルータ１００のノード次数に変更があった時に限り、隣接ルータの次数受信部１４１に更新後のルータ１００のノード次数を通知する。
【００２０】
記憶部１１１、使用頻度記憶部１１２は、ＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）のような書き込み可能な記憶装置で構成することができる。これらを一体的に構成してもよい。
パケット受信部１２１、コスト計算部１２２、転送先決定部１２３、パケット送信部１２４、ホップ数受信部１３１、次数受信部１４１、次数取得部１４２、次数通知部１４３は、これらの機能を実現する回路デバイスのようなハードウェアで構成することもできるし、マイコンやＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）のような演算装置とその動作を規定するソフトウェアで構成することもできる。
また、パケット受信部１２１、パケット送信部１２４、ホップ数受信部１３１、次数受信部１４１、次数通知部１４３は、必要なネットワークインターフェースを適宜備える。ネットワークインターフェースはこれら各機能部で共用してもよい。
【００２１】
以上、ルータ１００の構成について説明した。
次に、コスト計算部１２２が各隣接ルータのコスト値Ｈｉを算出する手順を説明する。
【００２２】
（１）ノード次数とホップ数の取得
コスト計算部１２２は、まず記憶部１１１を参照し、隣接ルータのノード次数と、当該隣接ルータからパケット受信部１２１が受信したパケットの宛先アドレスまでのホップ数を、パケット送信元ルータを除く全隣接ルータについて取得する。
パケット送信元ルータを除くのは、送信元ルータに受信パケットを送り返すことがないようにするためである。
記憶部１１１を参照しても得られないホップ数の情報がある場合、ホップ数受信部１３１に対し、不足しているホップ数の情報取得を依頼する。ホップ数受信部１３１は、不足している隣接ルータのホップ数情報を取得し、コスト計算部１２２に出力する。
【００２３】
（２）コスト値Ｈｉの計算
コスト計算部１２２は、全隣接ルータについてノード次数とホップ数の情報を取得すると、下記（式２）を用いて各隣接ルータのコスト値Ｈｉを計算する。
なお、下記（式２）中のαは固定のパラメータであり、あらかじめシミュレーション等で最適な値を定めておく。本実施の形態１における「係数」は、下記（式２）中のαがこれに相当する。
【数２】
0004623139.tif 000003
【００２４】
以上、コスト計算部１２２が各隣接ルータのコスト値Ｈｉを算出する手順を説明した。
次に、ルータ１００の詳細動作について、動作フロー図を用いて説明する。
【００２５】
図２は、ルータ１００が自ルータ１００と隣接ルータのノード次数を取得する際の動作フローである。図２（ａ）は自ルータ１００のノード次数、図２（ｂ）は隣接ルータのノード次数を取得する動作フローである。以下、図２の各ステップについて説明する。
【００２６】
（ａ）自ルータのノード次数
（Ｓ２０１）
次数取得部１４２は、自ルータ１００のノード次数を取得する。具体的には、例えば隣接ルータとの間の通信経路情報が存在するか否か、などの手法により、隣接ルータの数をカウントすることで、自ルータ１００のノード次数を取得することができる。
（Ｓ２０２）
次数取得部１４２は、ステップＳ２０１で取得した新たなノード次数が、記憶部１１１に格納されている自ルータ１００の従前のノード次数と異なるか否かを確認する。異なっていればノード次数に変更が生じたものとしてステップＳ２０３へ進み、変更が生じていなければステップＳ２０１へ戻る。
【００２７】
（Ｓ２０３）
次数取得部１４２は、記憶部１１１に格納されている自ルータ１００の従前のノード次数を、新たなノード次数で更新する。また、更新後の値を次数通知部１４３に出力する。
（Ｓ２０４）
次数通知部１４３は、次数取得部１４２より受け取った自ルータ１００のノード次数を全ての隣接ルータに通知する。
（Ｓ２０５）
ノード次数を取得する処理を継続する場合は、ステップＳ２０１へ戻る。
【００２８】
（ｂ）隣接ルータのノード次数
（Ｓ２０６）
次数受信部１４１は、隣接ルータからノード次数の通知を受信する。
（Ｓ２０７）
次数受信部１４１は、ステップＳ２０６で取得した新たなノード次数が、記憶部１１１に格納されている当該隣接ルータの従前のノード次数と異なるか否かを確認する。異なっていればノード次数に変更が生じたものとしてステップＳ２０８へ進み、変更が生じていなければステップＳ２０６へ戻る。
【００２９】
（Ｓ２０８）
次数受信部１４１は、記憶部１１１に格納されている当該隣接ルータのノード次数を更新する。
（Ｓ２０９）
ノード次数を受信する処理を継続する場合は、ステップＳ２０６へ戻る。
【００３０】
図３は、ルータ１００が隣接ルータから宛先アドレスまでのホップ数の情報を取得する際の動作フローである。以下、図３の各ステップについて説明する。
【００３１】
（Ｓ３０１）
ホップ数受信部１３１は、任意の隣接ルータからＲＩＰやＯＳＰＦなどのルーティングプロトコルによって通知される広告から、その広告に記載してある宛先アドレスと、その隣接ルータを経由した時のその宛先アドレスまでのホップ数の情報を取得する。
（Ｓ３０２）
ホップ数受信部１３１は、記憶部１１１が格納している、当該隣接ルータに関する項目エントリの中に、ステップＳ３０１で取得した宛先アドレスが登録されているか否かを確認する。
登録があればステップＳ３０３へ進み、登録がなければステップＳ３０５へ進む。
【００３２】
（Ｓ３０３）
ホップ数受信部１３１は、ステップＳ３０２で確認したアドレスまでのホップ数に基づき、記憶部１１１が格納している、当該隣接ルータに関する項目エントリ中の従前のホップ数に変更があるか否かを確認する。
変更があればステップＳ３０４へ進み、なければステップＳ３０１へ戻る。
また、ホップ数受信部１３１は、使用頻度記憶部１１２における当該隣接ルータに関する項目エントリの使用頻度を更新する。
（Ｓ３０４）
ホップ数受信部１３１は、記憶部１１１が格納している、当該隣接ルータに関する項目エントリ中の従前のホップ数を、ステップＳ３０２で確認したアドレスまでのホップ数で更新する。
【００３３】
（Ｓ３０５）
ホップ数受信部１３１は、記憶部１１１の登録領域に空きがあるか否かを確認する。空きがあればステップＳ３０７へ進み、なければステップＳ３０６へ進む。
（Ｓ３０６）
ホップ数受信部１３１は、使用頻度記憶部１１２を参照し、一定期間、コスト計算部１２１が計算に用いなかったアドレスが存在するか否かを確認する。存在すればステップＳ３０８へ進み、存在しなければステップＳ３０１へ戻る。
【００３４】
（Ｓ３０７）
ホップ数受信部１３１は、記憶部１１１中に、ステップＳ３０１で広告を受け取った隣接ルータに関する新たな項目エントリを生成し、取得したホップ数の情報を格納する。
（Ｓ３０８）
ホップ数受信部１３１は、ステップＳ３０６で参照した宛先アドレスに関する項目エントリを記憶部１１１から削除して、登録領域を確保する。次に、ステップＳ３０１で広告を受け取った隣接ルータの項目エントリを新たに生成し、取得した宛先アドレスとホップ数の情報を新たに登録する。
【００３５】
以上、ルータ１００がノード次数とホップ数の情報を取得する際の動作を説明した。
次に、具体的なネットワーク構成の下で、ルータ１００の各部動作について例を挙げて説明する。
【００３６】
図４は、本実施の形態１に係るルータＲ１〜Ｒ５で構成されるネットワークの構成図である。図４（ａ）はルータＲ５がＲ２に接続される前、図４（ｂ）はルータＲ５がＲ２に接続された後のネットワーク構成図である。
以下、ルータＲ２を中心として、新たなルータＲ５がＲ２に接続される前後に係る各部の動作を説明する。
【００３７】
図５は、ルータＲ５がＲ２に接続される前後に係る、ルータＲ２の記憶部１１１が格納する情報の状態を示す図である。図５（ａ）はルータＲ５がＲ２に接続される前、図５（ｂ）はルータＲ５がＲ２に接続された後の状態を示す。
図４（ａ）の状態では、記憶部１１１に格納されている情報は図５（ａ）のようになっている。各ルータのノード次数は「ノード次数」欄に、各ルータの宛先アドレス毎のホップ数は「ホップ数」欄に格納されている。
【００３８】
図５を参照すると、例えばルータＲ２のノード次数は３で、Ｒ５が接続されるとノード次数が４に変更されていることが分かる。同様に、Ｒ５のノード次数は、Ｒ２を含めて１０である（Ｒ２以外に９個の隣接ルータと接続されている）ことが分かる。
また、例えばルータＲ５からアドレス「１９２．１６８．０．１」までのホップ数は、３であることが分かる。
【００３９】
Ｒ２にＲ５が接続されると、以下のステップ（１）〜（７）で説明するような手順にしたがって記憶部１１１の内容が更新され、図５（ａ）の状態から図５（ｂ）の状態に更新される。
【００４０】
（１）Ｒ２にＲ５が接続されると、Ｒ２の次数取得部１４２は、自ルータＲ２のノード次数を取得する。これは、図２のステップＳ２０１に相当する。
（２）Ｒ２の次数取得部１４２は、図２のステップＳ２０２〜Ｓ２０３で説明した手順にしたがって、図５に示す「ノード次数」欄の項目「Ｒ２：３」を、「Ｒ２：４」に更新する。
（３）Ｒ２の次数通知部１４３は、図２のステップＳ２０４にしたがって、自ルータＲ２の新たなノード次数：４を、全隣接ルータＲ１、Ｒ３〜Ｒ５に通知する。
【００４１】
（４）Ｒ５の次数通知部１４３は、自ルータＲ５のノード次数が９から１０に変更されたことにともなって、自ルータＲ５の新たなノード次数：１０を、全隣接ルータＲ１〜Ｒ４に通知する。
（５）Ｒ２の次数受信部１４１は、図２のステップＳ２０６〜Ｓ２０８で説明した手順にしたがって、Ｒ５のノード次数：１０を受信する。図５に示す「ノード次数」欄には、Ｒ５に関する項目エントリがないので、Ｒ２の次数受信部１４１は、新たな項目エントリ「Ｒ５：１０」を生成して記憶部１１１に登録する。
【００４２】
（６）Ｒ２のホップ数受信部１３１は、Ｒ５よりＲＩＰ、ＯＳＰＦ等のルーティングプロトコルの広告を受信する。この広告には、アドレス「１９２．１６８．０．１」までのホップ数が３と記載されていたものとする。
（７）Ｒ２のホップ数受信部１３１は、図３で説明した手順にしたがって、図５に示す「ホップ数」欄を更新する。図５（ａ）の状態ではＲ５に関する項目エントリがなく、かつ空き領域が存在するので、新たに記憶部１１１中へＲ５に関する項目エントリを生成し、アドレス「１９２．１６８．０．１」までのホップ数：３を登録する。
【００４３】
以上、新たなルータＲ５がＲ２に接続される前後に係る各部の動作を説明した。
次に、図４〜図５で説明した構成の下、Ｒ１からアドレス「１９２．１６８．０．１」へ宛てて送信されたパケットをＲ２が受信し、アドレス「１９２．１６８．０．１」へ宛てて転送する際の各部の動作を、下記ステップ（８）〜（１１）で説明する。
なお、上記（式２）におけるパラメータαは、シミュレーションにより最適値０．５にあらかじめ設定されているものとする。
【００４４】
（８）Ｒ２のパケット受信部１２１は、Ｒ１が送信したアドレス「１９２．１６８．０．１」宛てのパケットを受信する。
（９）Ｒ２のコスト計算部１２２は、パケットの送信元であるＲ１を除き、以下の手順で各隣接ルータのコスト値Ｈｉを算出する。
【００４５】
（９．１）コスト計算部１２２は、記憶部１１１より各隣接ルータのノード次数とアドレス「１９２．１６８．０．１」までのホップ数を取得する。
（９．２）コスト計算部１２２は、上記（式２）および記憶部１１１より取得した各値を用いて、各隣接ルータのコスト値Ｈｉを算出する。ここでは、図５（ｂ）に示す各値に基づき、以下のように求められる。
（９．３）Ｒ３のコスト値Ｈ３＝０．３１
（９．４）Ｒ４のコスト値Ｈ４＝０．３５
（９．５）Ｒ５のコスト値Ｈ５＝０．３３
【００４６】
（１０）Ｒ２の転送先決定部１２３は、コスト計算部１２２が算出した各隣接ルータのコスト値に基づき、Ｒ１から受信したパケットの転送先ルータを決定する。ここでは、コスト値の最も小さいルータＲ３に決定する。
（１１）パケット送信部１２４は、Ｒ１から受信したパケットをＲ３へ転送する。
【００４７】
以上、図４〜図５で説明した構成の下、パケットの転送先を決定して転送する際の動作を説明した。
【００４８】
一般に、ノード次数の大きいルータは、任意のアドレスまでのホップ数も小さくなる。
転送先をホップ数だけで決めるルーティングプロトコルを使用した場合、ホップ数の小さいルータ、即ちノード次数の大きいルータをパケットが集中的に通過する傾向があり、そのルータで輻輳を生じやすい。
そこで従来技術では、ノード次数の大きいルータの輻輳を避けるため、隣接ルータのキュー待ち時間を考慮してルーティングを実行している。
【００４９】
一方、本実施の形態１で説明した構成と動作によれば、ルータ１００は、コスト計算部１２２が計算するコスト値を元にルーティングを実行するので、必ずしもホップ数が最短ではないルータも、次の転送先ルータとして選択され得る。
即ち、ホップ数が小さくノード次数の高いルータを回避して、パケットが集中しやすいルータを避けたルーティングを実行することが可能となる。
【００５０】
また、本実施の形態１によれば、隣接ルータのノード次数を用いることにより、輻輳を生じやすいルータを避けるという点において、従来技術と同種の効果を発揮することができる。
【００５１】
また、ルータのノード次数の変更頻度は、キューの待ち時間の変更頻度に比べれば小さいので、ルータ間でノード次数の情報を相互に交換する頻度も小さくて済む。
これにより、ルータ間でノード次数の情報を通知するパケットを処理するルータの負荷も減少し、ホップ数だけを用いて転送先を決定するルーティング手法に比べ、データを運ぶトラフィック総量を増加させることができる。
【００５２】
実施の形態２．
従来技術や実施の形態１では、各隣接ルータのコスト値Ｈｉの算出に用いるパラメータαを固定しているので、あらかじめ最適なαの値を定めておく必要がある。さらには、非特許文献１に記載のように、ネットワークのトラフィック総量を最大にするαの値を定めるに際し、ネットワーク全体のトポロジーを知らなければならない。
そこで、本発明の実施の形態２では、ネットワーク全体のトポロジーを知らなくとも、パラメータαを好適に可変することのできる構成と動作を説明する。
【００５３】
図６は、本実施の形態２に係るルータ１００の機能ブロック図である。
本実施の形態２に係るルータ１００は、記憶部１１１、使用頻度記憶部１１２、パケット受信部１２１、コスト計算部１２２、転送先決定部１２３、パケット送信部１２４、ホップ数受信部１３１、キュー長受信部１５１、キュー長取得部１５２、キュー長通知部１５３、パラメータ計算部１５４を備える。
使用頻度記憶部１１２、パケット受信部１２１、転送先決定部１２３、パケット送信部１２４、ホップ数受信部１３１の機能は、実施の形態１で説明したものと同様であるため、説明を省略する。
【００５４】
記憶部１１１は、ルータ１００、およびルータ１００の全隣接ルータのキュー長と、任意の隣接ルータからあるアドレスまでのホップ数の情報を保持する。キュー長とは、処理待ち状態でキューに保持されているパケットの数を表す。
コスト計算部１２２は、後述の（式４）を用いて各隣接ルータのコスト値Ｈｉを計算する。詳細は後述する。
【００５５】
キュー長受信部１５１は、任意の隣接ルータから当該隣接ルータのキュー長の通知を受け取り、記憶部１１１にその情報を格納する。
キュー長取得部１５２は、ルータ１００のキュー長を取得する。
キュー長通知部１５３は、ルータ１００のキュー長に変更があった時に限り、隣接ルータのキュー長受信部１５１に更新後のルータ１００のキュー長を通知する。
【００５６】
パラメータ計算部１５４は、記憶部１１１に格納されている全隣接ルータのキュー長を取得し、下記（式３）を用いてパラメータαを算出し、記憶部１１１に格納する。
算出処理は、記憶部１１１に格納するキュー長の情報が更新されるときに実行する。具体的には、キュー長受信部１５１やキュー長取得部１５２が記憶部１１１の内容を更新した後に、パラメータ計算部１５４にその旨を通知し、パラメータ計算部１５４はこれを契機に算出処理を開始する。
このαは、０≦α＜１の範囲の値をとり、隣接ルータのキュー長の分散が大きくなるとαの値も大きくなる。
【数３】
0004623139.tif 000004
【００５７】
キュー長受信部１５１、キュー長取得部１５２、キュー長通知部１５３、パラメータ計算部１５４は、これらの機能を実現する回路デバイスのようなハードウェアで構成することもできるし、マイコンやＣＰＵのような演算装置とその動作を規定するソフトウェアで構成することもできる。
また、キュー長受信部１５１、キュー長通知部１５３は、必要なネットワークインターフェースを適宜備える。ネットワークインターフェースはこれら各機能部で共用してもよい。このようなネットワークインターフェースとして、例えば、キュー長の取得を実装しているルータや、ＳＮＭＰのインターフェース等を挙げることができる。
【００５８】
以上、本実施の形態２に係るルータ１００の構成について説明した。
次に、コスト計算部１２２が各隣接ルータのコスト値Ｈｉを算出する手順を説明する。
【００５９】
（１）キュー長とホップ数の取得
コスト計算部１２２は、まず記憶部１１１を参照し、隣接ルータのキュー長と、パケット受信部１２１が受信したパケットの宛先アドレスまでのホップ数を、パケット送信元ルータを除く全隣接ルータについて取得する。
パケット送信元ルータを除くのは、実施の形態１と同様に、送信元ルータに受信パケットを送り返すことがないようにするためである。
記憶部１１１を参照しても得られないホップ数の情報がある場合、ホップ数受信部１３１に対し、不足しているホップ数の情報取得を依頼する。ホップ数受信部１３１は、不足している隣接ルータのホップ数情報を取得し、コスト計算部１２２に出力する。
【００６０】
（２）コスト値Ｈｉの計算
コスト計算部１２２は、全隣接ルータについてキュー長とホップ数の情報を取得すると、下記（式４）を用いて各隣接ルータのコスト値Ｈｉを計算する。
なお、下記（式４）中のαは、パラメータ計算部１５４が算出した値を用いる。本実施の形態２における「係数」は、下記（式４）中のαがこれに相当する。
【数４】
0004623139.tif 000005
【００６１】
以上、コスト計算部１２２が各隣接ルータのコスト値Ｈｉを算出する手順を説明した。
次に、ルータ１００の詳細動作について、動作フロー図を用いて説明する。
【００６２】
図７は、ルータ１００が自ルータ１００と隣接ルータのキュー長を取得する際の動作フローである。図７（ａ）は自ルータ１００のキュー長、図７（ｂ）は隣接ルータのキュー長を取得する動作フローである。以下、図７の各ステップについて説明する。
【００６３】
（ａ）自ルータのキュー長
（Ｓ７０１）
キュー長取得部１５２は、自ルータ１００のキュー長を取得する。
（Ｓ７０２）
キュー長取得部１５２は、ステップＳ７０１で取得した新たなキュー長が、記憶部１１１に格納されている自ルータ１００の従前のキュー長と異なるか否かを確認する。異なっていればキュー長に変更が生じたものとしてステップＳ７０３へ進み、変更が生じていなければステップＳ７０１へ戻る。
【００６４】
（Ｓ７０３）
キュー長取得部１５２は、記憶部１１１に格納されている自ルータ１００の従前のキュー長を、新たなキュー長で更新する。また、更新後の値をキュー長通知部１５３に出力する。
（Ｓ７０４）
キュー長通知部１５３は、キュー長取得部１５２より受け取った自ルータ１００のキュー長を全ての隣接ルータに通知する。
（Ｓ７０５）
キュー長を取得する処理を継続する場合は、ステップＳ７０１へ戻る。
【００６５】
（ｂ）隣接ルータのキュー長
（Ｓ７０６）
キュー長受信部１５１は、隣接ルータからキュー長の通知を受信する。
（Ｓ７０７）
キュー長受信部１５１は、記憶部１１１に格納されている当該隣接ルータの従前のキュー長を、新たなキュー長で更新する。
（Ｓ７０８）
キュー長を受信する処理を継続する場合は、ステップＳ７０６へ戻る。
【００６６】
以上、ルータ１００がキュー長とホップ数の情報を取得する際の動作を説明した。
次に、実施の形態１で説明した図４と同様のネットワーク構成の下で、本実施の形態２に係るルータ１００の各部動作について例を挙げて説明する。
【００６７】
図８は、Ｒ２がＲ４からのキュー長変更通知を受信する前後に係る、ルータＲ２の記憶部１１１が格納する情報の状態を示す図である。図８（ａ）はキュー長が変更される前、図８（ｂ）はキュー長が変更された後の状態を示す。
初期状態では、記憶部１１１に格納されている情報は図８（ａ）のようになっている。各ルータのキュー長は「キュー長」欄に、各ルータの宛先アドレス毎のホップ数は「ホップ数」欄に格納されている。また、（式３）〜（式４）のパラメータαは、「パラメータ」欄に格納されている。
【００６８】
パラメータ計算部１５４は、記憶部１１１に格納されている情報に基づき、パラメータαを以下のように計算し、記憶部１１１に格納しておく。
σ2＝６．５
α＝σ2／｛１．０＋σ2｝＝０．８７
【００６９】
次に、図８（ａ）の状態の下で、Ｒ１からアドレス「１９２．１６８．０．１」へ宛てて送信されたパケットをＲ２が受信し、アドレス「１９２．１６８．０．１」へ宛てて転送する際の各部の動作を、下記ステップ（１）〜（４）で説明する。
【００７０】
（１）Ｒ２のパケット受信部１２１は、Ｒ１が送信したアドレス「１９２．１６８．０．１」宛てのパケットを受信する。
（２）Ｒ２のコスト計算部１２２は、パケットの送信元であるＲ１を除き、以下の手順で各隣接ルータのコスト値Ｈｉを算出する。
【００７１】
（２．１）コスト計算部１２２は、記憶部１１１より各隣接ルータのキュー長とアドレス「１９２．１６８．０．１」までのホップ数を取得する。
（２．２）コスト計算部１２２は、上記（式４）および記憶部１１１より取得した各値を用いて、各隣接ルータのコスト値Ｈｉを算出する。ここでは以下のように求められる。
（２．３）Ｒ３のコスト値Ｈ３＝０．４５
（２．４）Ｒ４のコスト値Ｈ４＝０．１６
（２．５）Ｒ５のコスト値Ｈ５＝０．３８
【００７２】
（３）Ｒ２の転送先決定部１２３は、コスト計算部１２２が算出した各隣接ルータのコスト値に基づき、Ｒ１から受信したパケットの転送先ルータを決定する。ここでは、コスト値の最も小さいルータＲ４に決定する。
（４）パケット送信部１２４は、Ｒ１から受信したパケットをＲ４へ転送する。
【００７３】
以上、図８（ａ）の状態下、Ｒ２がパケットの転送先を決定して転送する際の動作を説明した。
次に、Ｒ２の隣接ルータＲ４から、キュー長が８に変更された旨の通知を受け取ったものとし、Ｒ２の各部の動作を下記ステップ（５）〜（７）で説明する。
【００７４】
（５）Ｒ２のキュー長受信部１５１は、Ｒ４からのキュー長通知を受信する。これは、図７のステップＳ７０６に相当する。
（６）Ｒ２のキュー長受信部１５１は、図７のステップＳ７０６〜Ｓ７０７で説明した手順にしたがって、図８に示す「キュー長」欄の項目「Ｒ４：２」を、「Ｒ４：８」に更新する。また、更新を行った旨を、パラメータ計算部１５４に通知する。
【００７５】
（７）パラメータ計算部１５４は、Ｒ４のキュー長が更新されたことを契機として、記憶部１１１が格納している各隣接ルータのキュー長を取得し、パラメータαを再計算する。ここでは以下のように求められる。再計算したαの値は、記憶部１１１に格納される。
σ2＝１．３
α＝σ2／｛１．０＋σ2｝＝０．５６
【００７６】
以上、Ｒ２の隣接ルータＲ４から、キュー長が８に変更された旨の通知を受け取った際の各部の動作を説明した。以上の手順により、記憶部１１１の内容は、図８（ａ）から図８（ｂ）へと更新される。
次に、図８（ｂ）の状態の下で、Ｒ１からアドレス「１９２．１６８．０．１」へ宛てて送信されたパケットをＲ２が再度受信し、アドレス「１９２．１６８．０．１」へ宛てて転送する際の各部の動作を、下記ステップ（８）〜（１１）で説明する。
【００７７】
（８）Ｒ２のパケット受信部１２１は、Ｒ１が送信したアドレス「１９２．１６８．０．１」宛てのパケットを受信する。
（９）Ｒ２のコスト計算部１２２は、パケットの送信元であるＲ１を除き、以下の手順で各隣接ルータのコスト値Ｈｉを算出する。
【００７８】
（９．１）コスト計算部１２２は、記憶部１１１より各隣接ルータのキュー長とアドレス「１９２．１６８．０．１」までのホップ数を取得する。
（９．２）コスト計算部１２２は、上記（式４）および記憶部１１１より取得した各値を用いて、各隣接ルータのコスト値Ｈｉを算出する。ここでは以下のように求められる。
（９．３）Ｒ３のコスト値Ｈ３＝０．２８
（９．４）Ｒ４のコスト値Ｈ４＝０．４１
（９．５）Ｒ５のコスト値Ｈ５＝０．３２
【００７９】
（１０）Ｒ２の転送先決定部１２３は、コスト計算部１２２が算出した各隣接ルータのコスト値に基づき、Ｒ１から受信したパケットの転送先ルータを決定する。ここでは、コスト値の最も小さいルータＲ３に決定する。
（１１）パケット送信部１２４は、Ｒ１から受信したパケットをＲ３へ転送する。
【００８０】
以上のように、Ｒ４のキュー長が２から８へと変わると、隣接ルータのキュー長の標本分散σ2が６．５から１．３へと小さくなる。
これにより、パラメータαも０．８７から０．５６へと小さくなり、コスト値Ｈｉの算出におけるキュー長の寄与が小さく、ホップ数の寄与が大きくなる。
その結果、Ｒ１から受信したパケットの転送先ルータは、アドレス「１９２．１６８．０．１」までのホップ数が１０であるＲ４から、ホップ数が３であるＲ３へと、ホップ数の小さいルータに変更されることになる。
【００８１】
以上のように、本実施の形態２によれは、パラメータαをキュー長の標本分散σ2に応じて動的に変化させることで、ルーティングにおける隣接ルータのキュー長の寄与を変化させることができる。
【００８２】
キュー長の分散が大きいときはパラメータαが大きくなり、コスト値Ｈｉの計算におけるキュー長の寄与が大きく、ホップ数の寄与が小さくなるので、キュー長の小さいルータを転送先に選びやすくなり、混雑を避けたルーティングが可能になる。
【００８３】
一方、隣接ルータのキュー長の分散が小さい時は、隣接ルータのキューの混雑具合は同程度であるから、各隣接ルータのキュー長はあまり考慮しなくともよい。
これに鑑み、本実施の形態２では、隣接ルータのキュー長の分散が小さくなると、（式４）におけるホップ数の寄与が大きくなり、ホップ数を優先したルーティングが行われるように構成されているので、受信したパケットが早く宛先に到着する効果を発揮する。
【００８４】
実施の形態３．
実施の形態１〜２で説明した構成と動作は、組み合わせて用いることもできる。
例えば、実施の形態１で説明したノード次数に加えて実施の形態２で説明したキュー長を取得ないし受信するようにルータ１００を構成し、ルータ間の情報更新頻度を抑えてルーティングを実行しつつ、パラメータαを可変にしてトラフィック総量の増加を図ることもできる。
【００８５】
この場合、コスト値Ｈｉの計算は、例えば以下のような手法を用いることができる。
（１）Ｈｉの計算は、（式２）を用いる。キュー長は、αの計算にのみ用いる。
（２）Ｈｉの計算は、（式２）と（式４）の双方で求めた値を平均化するなどして、ノード次数、キュー長、ホップ数を総合的に考慮したコスト値を求める。
【００８６】
実施の形態４．
以上の実施の形態１〜３では、ルータ１００の構成と動作を説明したが、同様の構成と動作は、ルーティング処理を行う通信装置一般に適用することができる。
例えば、Ｐｅｅｒ  Ｔｏ  Ｐｅｅｒネットワークを構成するノードに同様の構成と動作を実装し、当該ノードがパケット転送を行う際に、実施の形態１〜３で説明した手法を用いることができる。
【図面の簡単な説明】
【００８７】
【図１】実施の形態１に係るルータ１００の機能ブロック図である。
【図２】ルータ１００が自ルータ１００と隣接ルータのノード次数を取得する際の動作フローである。
【図３】ルータ１００が隣接ルータから宛先アドレスまでのホップ数の情報を取得する際の動作フローである。
【図４】実施の形態１に係るルータＲ１〜Ｒ５で構成されるネットワークの構成図である。
【図５】ルータＲ５がＲ２に接続される前後に係る、ルータＲ２の記憶部１１１が格納する情報の状態を示す図である。
【図６】実施の形態２に係るルータ１００の機能ブロック図である。
【図７】ルータ１００が自ルータ１００と隣接ルータのキュー長を取得する際の動作フローである。
【図８】Ｒ２がＲ４からのキュー長変更通知を受信する前後に係る、ルータＲ２の記憶部１１１が格納する情報の状態を示す図である。
【符号の説明】
【００８８】
１００  ルータ、１１１  記憶部、１１２  使用頻度記憶部、１２１  パケット受信部、１２２  コスト計算部、１２３  転送先決定部、１２４  パケット送信部、１３１  ホップ数受信部、１４１  次数受信部、１４２  次数取得部、１４３  次数通知部、１５１  キュー長受信部、１５２  キュー長取得部、１５３  キュー長通知部、１５４  パラメータ計算部。
【図１】
0004623139.tif 000007
【図２】
0004623139.tif 000008
【図３】
0004623139.tif 000009
【図４】
0004623139.tif 000010
【図５】
0004623139.tif 000011
【図６】
0004623139.tif 000012
【図７】
0004623139.tif 000013
【図８】
0004623139.tif 000014