(57)【要約】【課題】パケットの到着順序が送信順序と入れ替わることを低減するように経路を選択することが可能な通信経路制御装置を提供する。【解決手段】通信経路制御装置１００は、隣接装置から受信された第１のパケットの総受信パケット数に対する上記隣接装置の受信割合を上記第１のパケットの宛先と送信元との組合せ毎に計算する受信割合計算部３００と、上記第１のパケットの宛先を送信元とし上記第１のパケットの送信元を宛先とする第２のパケットを上記隣接装置に送信する割合である送信割合を上記第１のパケットの上記受信割合に基づいて計算する送信割合計算部４００と、上記送信割合に基づいて上記第２のパケットの送信先である隣接装置を選択する経路選択部５００と、を有する。【選択図】図４
2011109471.tif 000002
【特許請求の範囲】
【請求項１】
隣接装置から受信された第１のパケットの総受信パケット数に対する前記隣接装置の受信割合を前記第１のパケットの宛先と送信元との組合せ毎に計算する受信割合計算部と、
前記第１のパケットの宛先を送信元とし前記第１のパケットの送信元を宛先とする第２のパケットを前記隣接装置に送信する割合である送信割合を前記第１のパケットの前記受信割合に基づいて計算する送信割合計算部と、
前記送信割合に基づいて前記第２のパケットの送信先である隣接装置を選択する経路選択部と、
を備えることを特徴とする、通信経路制御装置。
【請求項２】
前記経路選択部が選択した前記第２のパケットの送信先である隣接装置の情報に基づいて、前記隣接装置毎の前記第２のパケットのパケット送信量を計算する送信量記憶部をさらに備え、
前記経路選択部は、前記パケット送信量が前記送信割合に近づくように前記第２のパケットの送信先である隣接装置を選択することを特徴とする、請求項１に記載の通信経路制御装置。
【請求項３】
前記経路選択部は、前記第１のパケットの送信先の候補となる前記隣接装置の数に応じて隣接装置が受信するパケット数が均等となるように前記第１のパケットの送信先の隣接装置を選択することを特徴とする、請求項１又は２のいずれかに記載の通信経路制御装置。
【請求項４】
前記送信割合計算部は、前記送信割合が前記受信割合よりも大きい場合には前記送信割合を減少させ、前記送信割合が前記受信割合よりも小さい場合には前記送信割合を増加させることを特徴とする、請求項１〜３のいずれか１項に記載の通信経路制御装置。
【請求項５】
前記送信割合計算部は、前記送信割合を前記受信割合と同じ値とすることを特徴とする、請求項１〜３のいずれか１項に記載の通信経路制御装置。
【請求項６】
前記第１のパケットは、ＴＣＰに従った通信におけるＡＣＫパケットであり、前記第２のパケットは、ＴＣＰに従った通信におけるデータパケットであることを特徴とする、請求項１〜５のいずれか１項に記載の通信経路制御装置。
【請求項７】
前記第１のパケットは、ＲＴＣＰパケットであり、前記第２のパケットはＲＴＰパケットであることを特徴とする、請求項１〜５のいずれか１項に記載の通信経路制御装置。
【請求項８】
隣接装置から受信したパケットの送信先を制御する通信経路制御装置において、
受信割合計算部が、前記隣接装置から受信された第１のパケットの総受信パケット数に対する前記隣接装置の受信割合を前記第１のパケットの宛先と送信元との組合せ毎に計算する受信割合計算ステップと、
送信割合計算部が、前記第１のパケットの宛先を送信元とし前記第１のパケットの送信元を宛先とする第２のパケットを前記隣接装置に送信する割合である送信割合を前記第１のパケットの前記受信割合に基づいて計算する送信割合計算ステップと、
経路選択部が、前記送信割合に基づいて前記第２のパケットの送信先である隣接装置を選択する経路選択ステップと、
を含むことを特徴とする、通信経路制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信経路制御装置及び通信経路制御方法に関し、特に、パケットの到着順序が送信順序と入れ替わることを低減するように経路を選択する通信経路制御装置及び通信経路制御方法に関する。
【背景技術】
【０００２】
データを小分けされたパケットに変換して伝送するパケット通信においては、通常マルチパス伝送方式が採用されている。マルチパス環境下においては、ネットワーク上のある装置に処理が集中し、負荷がかかると、その装置を経由するパケットの宛先装置への到着がその装置を経由しない他の経路を伝送されたパケットと比較して遅延してしまうという問題があった。
【０００３】
そこで、ネットワークを構成するルータは、受信したパケットを送信する先の隣接装置が複数ある場合には、各装置の負荷が分散されるようにパケットの送信先を選択している。例えば、最も単純な方法としては、ルータがパケットを送信する先の隣接装置の数に応じて送信するパケット数を等分に振分ける方法がある。また、例えば、特許文献１には、ネットワーク上の最初の分岐点において送信順序を制御することにより、各経路における負荷が分散するよう制御している。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】“Ｄｙｎａｍｉｃ  Ｌｏａｄ  Ｂａｌａｎｃｉｎｇ  Ｗｉｔｈｏｕｔ  Ｐａｃｋｅｔ  Ｒｅｏｒｄｅｒｉｎｇ”，ＡＣＭ  ＳＩＧＣＯＭＭ  Ｃｏｍｐｕｔｅｒ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ  Ｒｅｖｉｅｗ，Ｊｕｎｅ  ２００７
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかし、ネットワーク上において一度分岐させた経路が再び合流することがある。この場合に、例えばルータがパケット数を等分配していると合流点となるルータはパケットが集中するため、やはりパケットの遅延が引き起こされる場合があり、パケットが送信された順序で宛先ホストに到着しないという問題があった。
【０００６】
例えば、図１５を用いてホストＨ１からホストＨ２にデータを伝送する場合を例に説明する。図１５に示すネットワークはルータＲ１〜Ｒ７を含んで構成され、それぞれのルータは受信したパケットを送信先の隣接装置の数に応じて等分に分配する。このとき、例えばホストＨ１から６０のパケットがホストＨ２に向けて送信された場合に、ルータＲ１は受信した６０のパケットをＲ２及びＲ３にそれぞれ３０ずつ分配する。次に、ルータＲ２は受信した３０のパケットをルータＲ４及びルータＲ５にそれぞれ１５ずつ分配する。一方ルータＲ３も受信した３０のパケットをルータＲ５及びルータＲ６にそれぞれ１５ずつ分配する。ここで、ルータＲ５はルータＲ１及びルータＲ２を経由した経路とルータＲ１及びルータＲ３を経由した経路の合流点となる。即ち、ルータＲ４はルータＲ２から１５のパケットを受信し、ルータＲ６はルータＲ３から１５のパケットを受信するのに対し、ルータＲ５はルータＲ２及びルータＲ３からそれぞれ１５のパケットを受信する。
【０００７】
このように、ルータＲ５を経由する経路（例えば、Ｒ１−Ｒ２−Ｒ５−Ｒ７、及び、Ｒ１−Ｒ３−Ｒ５−Ｒ７）を伝送されたパケットは、ルータＲ５を経由しない経路（例えば、Ｒ１−Ｒ２−Ｒ４−Ｒ７、及び、Ｒ１−Ｒ３−Ｒ６−Ｒ７）と比較してルータＲ５においてパケット処理が集中するため処理遅延が発生し、宛先ホストへの到着が遅延する可能性が高い。そのため、パケットが送信された順序で宛先ホストに到着せずパケットの並び替え処理が必要となる。
【０００８】
そこで、本発明は、上記問題に鑑みてなされたものであり、本発明の目的とするところは、パケットの到着順序が送信順序と入れ替わることを低減するように経路を選択することが可能な、新規かつ改良された通信経路制御装置及び通信経路制御方法を提供することにある。
【課題を解決するための手段】
【０００９】
上記課題を解決するために、本発明のある観点によれば、隣接装置から受信された第１のパケットの総受信パケット数に対する上記隣接装置の受信割合を上記第１のパケットの宛先と送信元との組合せ毎に計算する受信割合計算部と、上記第１のパケットの宛先を送信元とし上記第１のパケットの送信元を宛先とする第２のパケットを上記隣接装置に送信する割合である送信割合を上記第１のパケットの上記受信割合に基づいて計算する送信割合計算部と、上記送信割合に基づいて上記第２のパケットの送信先である隣接装置を選択する経路選択部と、を有することを特徴とする、通信経路制御装置が提供される。
【００１０】
かかる構成によれば、第２のパケット（例えばデータパケット）の送信先は、第１のパケット（例えばＡＣＫパケット）の受信割合に基づいて選択される。このため、パケットの経路の合流点においても、送信元装置から同じホップ数である他の装置と処理量が同じになる可能性が非常に高まる。このため、経路選択部は、パケットの到着順序が送信順序と入れ替わることを低減するように経路を選択することが可能となり、パケットが送信された順番で宛先装置に到着する可能性が高まる。
【００１１】
また、上記経路選択部が選択した上記第２のパケットの送信先である隣接装置の情報に基づいて、上記隣接装置毎の上記第２のパケットのパケット送信量を計算する送信量記憶部をさらに有し、上記経路選択部は、上記パケット送信量が上記送信割合に近づくように上記第２のパケットの送信先である隣接装置を選択してもよい。
【００１２】
上記経路選択部は、上記第１のパケットの送信先の候補となる上記隣接装置の数に応じて隣接装置が受信するパケット数が均等となるように上記第１のパケットの送信先の隣接装置を選択してもよい。
【００１３】
また、上記送信割合計算部は、上記送信割合が上記受信割合よりも大きい場合には上記送信割合を減少させ、上記送信割合が上記受信割合よりも小さい場合には上記送信割合を増加させてもよい。
【００１４】
また、上記送信割合計算部は、上記送信割合を上記受信割合と同じ値としてもよい。
【００１５】
また、上記第１のパケットは、ＴＣＰに従った通信におけるＡＣＫパケットであり、上記第２のパケットは、ＴＣＰに従った通信におけるデータパケットであってもよい。
【００１６】
また、上記第１のパケットは、ＲＴＣＰパケットであり、上記第２のパケットはＲＴＰパケットであってもよい。
【００１７】
また、上記課題を解決するために、本発明の別の観点によれば、隣接装置から受信したパケットの送信先を制御する通信経路制御装置において、受信割合計算部が、上記隣接装置から受信された第１のパケットの総受信パケット数に対する上記隣接装置の受信割合を上記第１のパケットの宛先と送信元との組合せ毎に計算する受信割合計算ステップと、送信割合計算部が、上記第１のパケットの宛先を送信元とし上記第１のパケットの送信元を宛先とする第２のパケットを上記隣接装置に送信する割合である送信割合を上記第１のパケットの上記受信割合に基づいて計算する送信割合計算ステップと、経路選択部が、上記送信割合に基づいて上記第２のパケットの送信先である隣接装置を選択する経路選択ステップと、を含むことを特徴とする、通信経路制御方法が提供される。
【発明の効果】
【００１８】
以上説明したように本発明によれば、パケットの到着順序が送信順序と入れ替わることを低減するようにパケット送信経路を選択することが出来る。
【図面の簡単な説明】
【００１９】
【図１】本発明の一実施形態に係る通信経路制御装置を用いたネットワークの初期状態におけるデータパケットの伝送状態の一例を示す説明図である。
【図２】同実施形態に係る通信経路制御装置を用いたネットワークのＡＣＫパケットの伝送状態の一例を示す説明図である。
【図３】同実施形態に係る通信経路制御装置を用いたネットワークのデータパケットの伝送状態の一例を示す説明図である。
【図４】同実施形態に係る通信経路制御装置の機能ブロック図である。
【図５】同実施形態に係る通信経路制御装置のルーティングテーブルの一例を示す説明図である。
【図６】同実施形態に係る通信経路制御装置の受信割合情報の一例を示す説明図である。
【図７】同実施形態に係る通信経路制御装置の送信割合情報の一例を示す説明図である。
【図８】同実施形態に係る通信経路制御装置の送信パケット量情報の一例を示す説明図である。
【図９】同実施形態に係る通信経路制御装置のパケット処理の全体の流れを示すフローチャートである。
【図１０】同実施形態に係る通信経路制御装置の受信割合計算部の処理の流れを示すフローチャートである。
【図１１】同実施形態に係る通信経路制御装置の送信割合計算部の処理の流れを示すフローチャートである。
【図１２】同実施形態に係る通信経路制御装置の経路選択部のＡＣＫパケットに対する処理の流れを示すフローチャートである。
【図１３】同実施形態に係る通信経路制御装置の経路選択部のデータパケットに対する処理の流れを示すフローチャートである。
【図１４】同実施形態に係る通信経路制御装置の送信量計算部の処理の流れを示すフローチャートである。
【図１５】従来の通信経路制御装置を用いたネットワークの問題点を説明するための説明図である。
【発明を実施するための形態】
【００２０】
以下に添付図面を参照しながら、本発明の好適な実施の形態について詳細に説明する。なお、本明細書及び図面において、実質的に同一の機能構成を有する構成要素については、同一の符号を付することにより重複説明を省略する。
【００２１】
＜概要＞
まず、本発明の一実施形態に係る通信経路制御装置１００が実行する制御の理解を容易にするために、通信経路制御装置１００を用いたネットワークにおけるパケット伝送の概要について図１〜図３を用いて説明をする。図１は、本発明の一実施形態に係る通信経路制御装置を用いたネットワークの初期状態におけるデータパケットの伝送状態の一例を示す説明図である。また、図２は、同ネットワークのＡＣＫパケットの伝送状態の一例を示す説明図である。そして、図３は、同ネットワークのデータパケットの伝送状態の一例を示す説明図である。
【００２２】
以下、本実施形態においては、第１のパケットとしてのＡＣＫパケットと第２のパケットとしてのデータパケットを用いてＴＣＰに従った通信を例に説明をする。しかし、本実施形態に係る通信経路制御装置を用いて構成されたネットワークにおいて伝送されるパケットはこれに限らない。例えば、ストリーミング通信における第１のパケットとしてのＲＴＣＰパケットと第２のパケットとしてのＲＴＰパケットであってもよい。ここで、第１のパケットは、第２のパケットの宛先を送信元とし第２のパケットの送信元を宛先とするパケットである。
【００２３】
例えば、図１は、ホストＨ１からホストＨ２に対してデータパケットを送信した場合のデータパケットの伝送状態の一例を示している。ここで、ルータＲ１〜Ｒ７は通信経路制御装置１００が用いられる。初期状態において通信経路制御装置１００は、受信したパケットを送信先となる隣接装置に均等に配分する。従って、ルータＲ１は６０のパケットを受信すると受信したパケットをＲ２及びＲ３にそれぞれ３０ずつ配分する。次に、ルータＲ２は受信した３０のパケットをルータＲ４及びルータＲ５にそれぞれ１５ずつ分配する。一方ルータＲ３も受信した３０のパケットをルータＲ５及びルータＲ６にそれぞれ１５ずつ分配する。ここで、ルータＲ５はルータＲ１及びルータＲ２を経由した経路とルータＲ１及びルータＲ３を経由した経路の合流点となる。即ち、ルータＲ４はルータＲ２から１５のパケットを受信し、ルータＲ６はルータＲ３から１５のパケットを受信するのに対し、ルータＲ５はルータＲ２及びルータＲ３からそれぞれ１５のパケットを受信する。
【００２４】
ここでは、上記の従来例と同じようにルータＲ５において処理が集中するため、ルータＲ５を経由するパケットの遅延が生じる可能性が高い。そこで、通信経路制御装置１００は、ＡＣＫパケットの伝送状態に基づいてデータパケットの伝送における経路選択を制御する。次に、図２に示すようにホストＨ２からホストＨ１に向けてデータパケットに対するＡＣＫパケットが送信される。このとき、各通信経路制御装置１００は各送信先となる隣接装置に均等に配分する。具体的には、図２に示すようにＡＣＫパケットは配分されて伝送され、Ｈ１に到達する。
【００２５】
そこで、このＡＣＫパケットの伝送状態に基づいてデータパケットの配分を制御した一例が図３に示される。図１と比較してみると分かるように、図３においては例えばルータＲ２は受信した３０のパケットのうちルータＲ４に対して２０のパケットを配分し、ルータＲ５に対しては１０のパケットを配分する。また、ルータＲ３は受信した３０のパケットのうちルータＲ５に対して１０のパケットを配分し、ルータＲ６に対しては２０のパケットを配分する。この場合、ルータＲ５が受信するパケットは合わせて２０であり、ルータＲ４及びルータＲ６が受信するパケットも同じく２０である。かかるパケット配分方法によれば、例えばルータＲ５のような経路の合流点における受信パケット数が他の経路上の装置における受信パケット数と等しくなるため、処理遅延を低減することが出来る。
【００２６】
以上、本実施形態に係る通信経路制御装置１００を用いたネットワークにおけるパケット伝送状態の概要について説明した。次に、このようなパケット伝送を実現するための通信経路制御装置１００の構成について説明する。
【００２７】
＜通信経路制御装置の機能構成＞
通信経路制御装置１００の機能構成について、図４を用いて説明する。本発明の一実施形態に係る通信経路制御装置１００は、通信経路を制御するための装置であり、例えばルータである。通信経路制御装置１００は、受信部２００、受信割合計算部３００、送信割合計算部４００、経路選択部５００、送信量計算部６００、送信部７００、及び、記憶部８００を主に有する。
【００２８】
受信部２００は、ネットワークと接続可能であり、ネットワークを介してルータなどの隣接装置からパケットを受信する機能を有する。上述の通り、本実施形態においては、受信部２００において受信するパケットは、第１のパケットとしてのＡＣＫパケット及び第２のパケットとしてのデータパケットとする。ＡＣＫパケット及びデータパケットは、宛先情報及び送信元情報を含む。宛先情報及び送信元情報は、例えば、ＩＰアドレス、ノードＩＤ、ＩＰアドレスのプレフィックス、ＡＳ（Ａｕｔｏｎｏｏｕｓ  Ｓｙｓｔｅｍ）番号などである。宛先情報及び送信元情報は、宛先又は送信元を識別するための情報であって、宛先又は送信元を識別することが出来れば、宛先情報と送信元情報とが同種のもの同士でなくてもよい。例えば、宛先情報はＩＰアドレスで示され、送信元情報はノードＩＤで示されてもよい。受信部２００は、この宛先情報及び送信元情報、並びに、パケットを受け渡した隣接装置を識別するためのルータ情報を取得する。そして、受信部２００は、受信したパケットがＡＣＫパケットであるかデータパケットであるかを判別し、受信したパケットがＡＣＫパケットである場合には、ルータ情報、宛先情報、及び、送信元情報を受信割合計算部３００に入力する。一方、受信したパケットがデータパケットである場合には、受信部２００は、宛先情報、及び、送信元情報を経路選択部５００に入力する。
【００２９】
受信割合計算部３００は、ＡＣＫパケットの受信した割合を計算する機能を有する。受信割合計算部３００は、受信部２００から入力されたルータ情報、宛先情報、及び、送信元情報、並びに、記憶部８００の受信割合情報８０４に基づいて、受信割合を計算する。ここで受信割合とは、ある一定期間に受信したＡＣＫパケットのうち、どの隣接装置から受信したＡＣＫパケットが何割かという割合をいう。ここである一定期間としたが、受信部２００が受信した全てのＡＣＫパケットとしてもよい。受信割合計算部３００は、受信割合を計算し、記憶部８００の受信割合情報８０４に計算した受信割合を記憶する。また、受信割合は、送信元と宛先との組合せ毎に計算する。
【００３０】
送信割合計算部４００は、受信したデータパケットをどの隣接装置に何割送信するかの配分を示す送信割合を計算する機能を有する。送信割合計算部４００は、受信割合と同様に送信元と宛先との組合せ毎に送信割合を計算する。ここで送信割合計算部４００は、受信したデータパケットの宛先を送信元とし、当該データパケットの送信元を宛先とするＡＣＫパケットについての受信割合に基づいて送信割合を計算する。例えば、図１の例では、Ｈ２からＨ１に対して送信されたＡＣＫパケットについての受信割合に基づいて、Ｈ１からＨ２に対して送信されるデータパケットの送信割合が計算される。また、未だ受信割合に基づいて送信割合が計算されていない場合には、所定の初期値に従って送信されてもよい。例えば、隣接ルータの数で等分するように初期設定されていてもよい。
【００３１】
ここで、送信割合計算部４００の送信割合の更新方法について具体例を挙げる。ルータ１が隣接ルータ２から受信した送信元Ｐと宛先Ｑとの組合せについての受信割合をα１，２とする。そして、ルータ１が隣接ルータ２へ送信する受信割合α１，２に対応する組合せ、即ち送信元Ｑ、宛先Ｐとなる組合せの送信割合をβ１，２とする。送信割合計算部４００は、隣接ルータ２からの受信割合α１，２と比較して隣接ルータ２への送信割合β１，２が大きい場合には、隣接ルータ２への送信割合β１，２を減少させる。そして、送信割合計算部４００は、隣接ルータ２からの受信割合α１，２と比較して隣接ルータ２の送信割合β１，２が小さい場合には、隣接ルータ２への送信割合β１，２を増加させる。
【００３２】
送信割合計算部４００の送信割合の更新方法は、例えば、次の式で表すことが出来る。
β１，２（ｔ＋１）＝α１，２（ｔ）・・・（数式１）
或いは、次の式で表されるようにしてもよい。
【００３３】
【数１】
2011109471.tif 000003
【００３４】
ここで、ｉはルータ１の隣接ルータを表す。
【００３５】
経路選択部５００は、受信されたパケットの種類に応じてパケットをどの隣接ルータに送信するかを決定する機能を有する。経路選択部５００は、受信されたパケットがＡＣＫパケットである場合には、記憶部８００のルーティングテーブル８０２を参照して、ルーティングテーブルに従って送信先の隣接ルータを決定する。一方、受信されたパケットがデータパケットである場合には、経路選択部５００は、受信部２００から入力された宛先情報及び送信元情報、記憶部８００のパケット送信量情報８０８、並びに、送信割合に基づいて、送信先の隣接ルータを決定する。具体的には、経路選択部５００は、受信部２００から入力された宛先情報及び送信元情報に該当する組合せについてのパケット送信量を記憶部８００から参照する。そして、同じく受信部２００から入力された宛先情報及び送信元情報からその組合せについての送信割合を送信割合情報８０６を参照して取得する。経路選択部５００は、パケット送信量が送信割合に近づくように送信先の隣接ルータを決定する。
【００３６】
送信量計算部６００は、経路選択部５００により決定された隣接ルータの識別情報、受信部から入力された宛先情報及び送信元情報に基づいて、隣接ルータ毎、及び、宛先情報と送信元情報との組合せ毎のデータパケットの送信量を計算し、記憶部８００のパケット送信量情報８０８を更新する機能を有する。
【００３７】
送信部７００は、経路選択部５００において決定された送信先の隣接ルータに受信されたパケットを送信する機能を有する。
【００３８】
記憶部８００は、ルーティングテーブル８０２、受信割合情報８０４、送信割合情報８０６、及び、パケット送信量情報８０８を主に有する。以下、図１のネットワーク構成におけるルータＲ２を例にとって、記憶部８００に記憶される各情報の一例について、図５〜図８を用いて説明する。
【００３９】
図５は、図１におけるルータＲ２のルーティングテーブル８０２の一例を示す説明図である。ルーティングテーブル８０２は、宛先８０２２、メトリック８０２４、及びネクストホップノード８０２６の情報を主に含む。ここで、メトリック８０２４は、その送信先を選択した場合の宛先ノードまでの最短ホップ数である。
【００４０】
図６は、図１におけるルータＲ２の受信割合情報８０４の一例を示す説明図である。受信割合情報８０４は、送信元８０４２、宛先８０４４、ルータ８０４６、及び受信割合８０４８の情報を主に含む。受信割合情報８０４を参照すると、送信元８０４２及び宛先８０４４の組合せに対する受信したパケットのうち、ルータ８０４６の欄に記載されている隣接ルータからどの受信割合で受信したかを示す受信割合８０４８を知ることが出来る。すなわち、Ｈ２からＨ１に向けて送信されたＡＣＫパケットは、ルータＲ２において、ルータＲ４からそのパケット数の全体量の２／３、ルータＲ５からそのパケット数の全体量の１／３を受信している。
【００４１】
図７は、図１におけるルータＲ２の送信割合情報８０６の一例を示す説明図である。送信割合情報８０４は、送信元８０６２、宛先８０６４、ルータ８０６６、及び送信割合８０６８を主に含む。送信割合情報８０６は、データパケットの宛先が送信元であり、データパケットの送信元が宛先であるＡＣＫパケットの受信割合情報８０４に基づいて計算された送信割合に関する情報である。
【００４２】
図８は、図１におけるルータＲ２のパケット送信量情報８０８の一例を示す説明図である。パケット送信量情報８０８は、送信元８０８２、宛先８０８４、ルータ８０８６、及び、パケット送信量８０８８を主に含む。パケット送信量情報８０８は、ある一定期間における当該ルータがルータ８０８６に記載のルータに対してある送信元と宛先との組合せのパケットを送信した数量を示す情報である。
【００４３】
＜通信経路制御装置の動作例＞
次に、通信経路制御装置１００の動作の一例について、図９〜図１４を用いて説明する。図９は、通信経路制御装置１００の全体の動作の一例を示すフローチャートである。図１０〜図１４は、図９のフローチャートのサブフローチャートである。以下、図９の流れに従って全体の動作フローについて説明しながら、図９の各ステップにおいてサブフローがある場合には、適宜サブフローチャートを参照して説明をする。
【００４４】
まず、図９を参照すると、通信経路制御装置１００は、受信部２００において隣接ルータからパケットを受信する（Ｓ１０２）。受信部２００は、次に受信したパケットがデータパケットであるかＡＣＫパケットであるかを判別し、それと共に、ルータ識別情報、送信元情報、及び、宛先情報を取得する（Ｓ１０４）。
【００４５】
そして、受信したパケットがＡＣＫパケットであった場合には、通信経路制御装置１００は、受信割合計算部３００において受信割合計算処理を実行する（Ｓ１０６）。ここで、受信割合計算処理の詳細について図１０を用いて説明する。受信割合計算部３００は、まず受信部２００からルータ識別情報、送信元情報、及び、宛先情報を受け取る。そして、受信割合計算部３００は、記憶部８００から送信元情報と宛先情報との組合せに対応する受信割合情報を参照し（Ｓ３０４）、参照した受信割合情報に、この時点において受信したパケットの情報を加えた受信割合を計算して記憶部８００の受信割合情報８０４を更新する（Ｓ３０６）。
【００４６】
以上説明したステップＳ１０６の受信割合計算処理が終わると、次に、通信経路制御装置１００は、送信割合計算部４００において送信割合計算処理を実行する（Ｓ１０８）。ここで、送信割合計算処理の詳細について図１１を用いて説明する。送信割合計算部４００は、まず受信部２００から送信元情報、及び、宛先情報を受け取る（Ｓ４０２）。そして、送信割合計算部４００は、記憶部８００から送信割合情報８０６を参照し（Ｓ４０４）、上記の送信割合の更新方法に従って送信割合を計算し、記憶部８００の送信割合情報８０６を更新する（Ｓ４０６）。
【００４７】
以上説明したステップＳ１０８の送信割合計算処理が終わると、次に、通信経路制御装置１００は、経路選択部５００において、ＡＣＫパケット経路選択処理を実行する（Ｓ１１０）。ここで、ＡＣＫパケット経路選択処理の詳細について図１２を用いて説明する。まず経路選択部５００は、受信したパケットがＡＣＫパケットである場合にはルーティングテーブルを参照し（Ｓ５０２）、ルーティングテーブルに基づいて送信先である隣接ルータを決定する（Ｓ５０４）。ここで、例えば図２のネットワーク構成におけるルータＲ２の図５に示すルーティングテーブル８０２の例を参照すると、ルータＲ２が送信元がＨ２であり宛先がＨ１であるＡＣＫパケットを受信した場合には、ネクストホップノードとして記述されたＲ１にＡＣＫパケットを送信することが分かる。そして、経路選択部５００が送信先である隣接ルータを決定すると、経路選択部５００は、送信部７００に選択した隣接ルータの情報を伝える（Ｓ５０６）。
【００４８】
以上説明したステップＳ１１０のＡＣＫパケット経路選択処理が終わると、次に、通信経路制御装置１００は、送信部７００において、受信したパケットを送信する（Ｓ１１２）。ここで、送信部７００は、ステップＳ１１０のＡＣＫパケット経路選択処理において選択された隣接ルータにパケットを送信する。
【００４９】
一方、ステップＳ１０４において、受信されたパケットがデータパケットであると判別された場合には、通信経路制御装置１００は、経路選択部５００において、データパケット経路選択処理を実行する（Ｓ１１４）。ここで、データパケット経路選択処理の詳細について図１３を用いて説明する。まず経路選択部５００は、受信部２００から送信元情報、及び、宛先情報を受け取る（Ｓ５１２）。そして、記憶部８００から、受け取った送信元情報及び宛先情報の組合せに対応するデータパケットの隣接ルータ毎のパケット送信量と送信割合とを取得する（Ｓ５１４）。次に経路選択部５００は、取得したパケット送信量の隣接ルータ毎の送信割合が、取得した送信割合の値に近づくように送信先である隣接ルータを決定する（Ｓ５１６）。例えば、パケット送信量情報８０６が図８に示す状態であり、そのときの送信割合情報が図７に示す送信割合情報８０６であったとする。この場合に、経路選択部５００は、その時点までの間にＲ４に送信したパケット数が１９でありＲ５に送信したパケット数が１０であることを知ることが出来る。このとき、このパケット数の割合が図７に示す割合に近づくためには、データパケットをＲ４に送信すればよいことが分かる。このようにして送信先である隣接ルータを決定すると、経路選択部５００は、送信部７００及び送信量計算部６００に決定したルータの識別情報を伝える（Ｓ５１８）。
【００５０】
以上説明したステップＳ１１４のデータパケット経路選択処理が終わると、次に、通信経路制御装置１００は、送信量計算部６００においてパケット送信量計算処理を実行する（Ｓ１１６）。ここで、パケット送信量計算処理の詳細について図１４を用いて説明する。まず、送信量計算部６００は、経路選択部５００から選択された送信先の隣接ルータの識別情報を、また、受信部２００から送信元情報及び宛先情報を受け取る（Ｓ６０２）。そして、受け取った送信元情報及び宛先情報の組合せに対応するパケット送信量を記憶部８００から取得する（Ｓ６０４）。そして、経路選択部５００から受け取った隣接ルータの識別情報を用いてパケット送信量情報を更新する。具体的には、先ほど図７〜図８の例を用いて説明した場合について説明すると、経路選択部５００は隣接ルータＲ４を送信先として選択したため、送信元８０８２がＨ１、宛先８０８４がＨ２、ルータ８０８６がＲ４であるデータのパケット送信量８０８８を「２０」に更新する（Ｓ６０６）。
【００５１】
以上説明したステップＳ１１６のパケット送信量計算処理が終わると、次に、通信経路制御装置１００は、送信部７００において、受信したパケットを送信する（Ｓ１１２）。ここで、送信部７００は、ステップＳ１１４のデータパケット経路選択処理において選択された隣接ルータにパケットを送信する。
【００５２】
＜適用例＞
次に、図１〜図３に示したネットワーク構成における具体的なルータの挙動について説明する。上記にて図１〜図３を用いて本実施形態に係る通信経路制御装置１００の概要について説明したが、ここでは、同じく図１〜図３を用いて、各時点における通信経路制御装置１００の動作とあわせて説明をする。
【００５３】
まず、図１〜図３に示されるネットワークは、ルータＲ１〜ルータＲ７を含んでおり、ホストＨ１及びホストＨ２が接続されている。ルータＲ１〜ルータＲ７は、それぞれ、本実施形態に係る通信経路制御装置１００である。ホストＨ１を送信元とし、ホストＨ２を宛先とするパケットは、ルータＲ１〜ルータＲ７のいずれかを経由してホストＨ２に送信される。また、ホストＨ２を送信元とし、ホストＨ１を宛先とするパケットも同様にルータＲ１〜ルータＲ７のいずれかを経由してホストＨ１に送信される。
【００５４】
ここでは、ホストＨ１からホストＨ２に対してデータパケットを送信する場合について説明する。ＡＣＫパケットは、データパケット１つについて１つ返される。ルータＲ１〜ルータＲ７は、ＡＣＫパケットの受信割合からデータパケットの送信割合を決定するが、ＡＣＫパケット及び送信割合の決定前におけるデータパケットについては、ホップ数に基づいた最短経路を採用し、同一ホップ数の経路が複数ある場合には、パケットを送信先となる隣接ルータの数で等分して送信する。例えば、ホストＨ２からホストＨ１に対して３つのＡＣＫパケットが送信された場合には、Ｒ７は、Ｒ４，Ｒ５，Ｒ６にそれぞれ１つずつパケットを送信する。
【００５５】
ルータＲ１〜ルータＲ７のルーティングテーブルは、既に完成しているものとする。例えば、ルータＲ２のルーティングテーブルは図５に示される。上述の通り、メトリックは、ホップ数である。そして、各ルータの受信割合は、上述の通りルータＲｉが隣接ルータＲｊから受信したＨ２を送信元Ｈ１を宛先とするＡＣＫパケットの受信割合は、αi,j（１≦ｉ，ｊ≦７）と記述される。受信割合の初期値は、αi,j＝０（１≦ｉ，ｊ≦７）とする。ルータＲ２について受信割合の初期値は、α2,4＝α2,5＝０である。
【００５６】
同様に、各ルータの送信割合は、ルータＲｉが隣接ルータＲｊへ送信する、ホストＨ１を送信元、ホストＨ２を宛先とするデータパケットの送信割合はβi,j（１≦ｉ，ｊ≦７）と記述される。上述の通り、初期状態において、経路選択部５００は、同一ホップ数の経路が複数ある場合には、パケットを送信先となる隣接ルータの数で等分して送信する。このため、ルータＲ２について送信割合の初期値は、β2,4＝β2,5＝０．５である。
【００５７】
同様に、各ルータの送信パケット量は、ルータＲｉが隣接ルータＲｊに送信する、ホストＨ１を送信元、ホストＨ２を宛先とするデータパケットの送信量をｘi,j（１≦ｉ，ｊ≦７）とし、その初期値はｘi,j＝０である。例えば、ルータＲ２について送信量の初期値はｘ２,４＝ｘ２,５＝０である。
【００５８】
ルータＲ２について、図１〜図３に示すように、ホストＨ１からホストＨ２に対してデータパケットを送信し、ホストＨ２からホストＨ１に対してＡＣＫパケットを返す例を説明するために、各パラメータの初期値について説明した。ルータＲ２は、この他にも、ホストＨ２からホストＨ１に対してデータパケットを送信するための送信割合β2,１、ホストＨ１からホストＨ２に対してＡＣＫパケットを返す際の受信割合α2,1、及び、ホストＨ２からホストＨ１に対して送信されるデータパケットについてのパケット送信量ｘ２,１を記憶部８００に保持しているが、次に説明する動作はこれらのパラメータを必要としないため、説明を省略する。
【００５９】
上述のような初期条件において、ホストＨ１がホストＨ２に対してデータパケットを６０送信した場合の、ネットワーク中の各リンクを伝送されるパケット数が図１に示される。ここでは、上述の通り、経路選択部５００は、ホップ数に基づいた最短経路を採用し、同一ホップ数の経路が複数ある場合には、パケットを送信先となる隣接ルータの数で等分して送信する。そして、６０のデータパケットを受信したホストＨ２は、ホストＨ１に対してＡＣＫパケットを返す。このときのネットワーク中の各リンクを伝送されるＡＣＫパケットの数が図２に示される。
【００６０】
このときのルータＲ２における処理を以下に説明する。まず、ルータＲ２はルータＲ４からＡＣＫパケットを受信したとする。ルータＲ２の受信部２００は、ルータＲ４から受信したパケットをＡＣＫパケットであると判別する。そして、Ｒ４から受信したパケットであることを受信割合計算部３００に伝える。即ち、受信部２００は、Ｒ４のルータ識別情報を受信割合計算部３００に入力する。また、パケットのＩＰアドレスなどから送信元情報はＨ２であり、宛先情報はＨ１であることがわかるため、この２つの情報を受信割合計算部３００、送信割合計算部４００、経路選択部５００、及び、送信量計算部６００に入力する。
【００６１】
受信割合計算部３００は、このとき、ルータ情報としてＲ４、送信元情報としてＨ２、宛先情報としてＨ１を受信部２００から取得する。そして、受信割合計算部３００は、記憶部８００を参照して、送信元をＨ２、宛先をＨ１とする受信割合を取得する。この時点において、受信割合は初期値となっているため、受信割合α2,4＝α2,5＝０である。受信割合計算部３００は、α2,4＝α2,5＝０の値と、Ｒ４から１パケット受信した情報とを用いて、受信割合をα2,4＝１、α2,5＝０と更新する。
【００６２】
送信割合計算部４００は、送信元情報としてＨ２、宛先情報としてＨ１を受信部２００から取得する。そして、記憶部８００を参照して、送信元をＨ２，宛先をＨ１とする受信割合α2,4＝１、α2,5＝０と送信元をＨ１，宛先をＨ２とする送信割合β2,4＝β2,5＝０．５とを取得する。そして、送信割合の更新方法に従って送信割合を対応する受信割合に基づいて更新する。ここでは、β2,4＝１、β2,5＝０と更新される。
【００６３】
経路選択部５００は、記憶部８００の図５に示すルーティングテーブル８０２を参照する。そして、受信したパケットは宛先がＨ１であるため、ネクストホップノード８０２６を参照してＲ１が送信先の隣接ルータであると決定する。そして決定した送信先の情報を送信部７００に入力する。送信部７００は、経路選択部５００から入力された送信先の情報に従って、Ｒ１にパケットを送信する。
【００６４】
ルータＲ２は、受信したパケット毎に上記の処理を繰り返す。その結果、ルータＲ２は、最終的にルータＲ４から送信されたパケットを２０、ルータＲ５から送信されたパケットを１０の計３０のパケットを処理してＲ１に送信する。従って、受信割合は、α2,4＝２／３、α2,5＝１／３、送信割合は、β2,4＝２／３、β2,5＝１／３となる。このときの受信割合及び送信割合の状態を図６及び図７にそれぞれ示す。
【００６５】
以上説明したようにＡＣＫパケットの受信割合に基づいて、データパケットの送信割合が更新された後、Ｈ１からＨ２に対してデータパケットが送信された場合のネットワーク中の各リンクを伝送されるパケット数が図３に示される。
【００６６】
このときルータＲ２がルータＲ１から初めて受信したデータパケットに対する処理を以下に説明する。まず、ルータＲ２の受信部２００は、Ｒ１から受信したパケットをデータパケットであると判別する。そして、パケットのＩＰアドレスなどから送信元情報はＨ１であり、宛先情報はＨ２であることがわかるため、受信部２００は、この２つの情報を経路選択部５００、及び、送信量計算部６００に入力する。
【００６７】
経路選択部５００は、送信元情報としてＨ１、宛先情報としてＨ２を受信部２００から受け取る。そして、記憶部８００を参照して送信元がＨ１、宛先がＨ２であるパケット送信量ｘ２,４＝ｘ２,５＝０、及び、送信元がＨ１、宛先がＨ２である送信割合β2,4＝２／３、β2,5＝１／３を取得する。ここで、経路選択部５００は、これらの情報に基づいて、パケット送信量が送信割合に近づくように送信先をＲ４と決定する。経路選択部５００は、決定した送信先である隣接ルータＲ４を送信部７００及び送信量計算部６００に入力する。送信部７００は、入力された送信先の情報に基づいてＲ４にパケットを送信する。
【００６８】
送信量計算部６００は、送信元情報Ｈ１、宛先情報Ｈ２を受信部２００から受け取り、経路選択部５００からルータ情報Ｒ４を受け取る。そして、送信量計算部６００は、記憶部８００から送信元をＨ１、宛先をＨ２とするパケット送信量ｘ２,４＝ｘ２,５＝０を取得する。そして、経路選択部５００から受け取ったルータ情報に基づいて、パケット送信量を更新する。ここでは、送信量計算部６００は、パケット送信量をｘ２,４＝１、ｘ２,５＝０と更新する。
【００６９】
＜効果の例＞
以上説明したように、本実施形態に係る通信経路制御装置１００を用いたネットワークにおいては、データパケットの処理量が、送信元ホストＨ１からみたときに同一ホップ数になるルータの集合であるＲ２及びＲ３、並びに、Ｒ４，Ｒ５，及びＲ６のパケット処理量がそれぞれ均等に分散される。このため、例えば図１の例におけるルータＲ５のように複数の経路の合流地点となるルータにおいても、同一ホップ数における他のルータと処理量がほぼ等しくなるため、一部のルータのパケット処理量が多いために引き起こされるパケット遅延に起因してパケットの到着順序がパケットの送信順序と異なる順序となることを回避することが出来る。
【００７０】
以上、添付図面を参照しながら本発明の好適な実施形態について詳細に説明したが、本発明はかかる例に限定されない。本発明の属する技術の分野における通常の知識を有する者であれば、特許請求の範囲に記載された技術的思想の範疇内において、各種の変更例または修正例に想到し得ることは明らかであり、これらについても、当然に本発明の技術的範囲に属するものと了解される。
【００７１】
尚、本明細書において説明した構成は、ネットワークを構成して利用されるもの一般に適用される。例えば、Ｐ２Ｐ（Ｐｅｅｒ  ｔｏ  Ｐｅｅｒ）の仮想ネットワークの構造や無線アドホックネットワークに適用することも出来る。
【００７２】
また、本明細書において、フローチャートに記述されたステップは、記載された順序に沿って時系列的に行われる処理はもちろん、必ずしも時系列的に処理されなくとも、並列的に又は個別的に実行される処理をも含む。また時系列的に処理されるステップでも、場合によっては適宜順序を変更することが可能であることは言うまでもない。
【符号の説明】
【００７３】
１００    通信経路制御装置
２００    受信部
３００    受信割合計算部
４００    送信割合計算部
５００    経路選択部
６００    送信量計算部
７００    送信部
８００    記憶部
８０２    ルーティングテーブル
８０４    受信割合情報
８０６    送信割合情報
８０８    パケット送信量情報
【図１】
2011109471.tif 000004
【図２】
2011109471.tif 000005
【図３】
2011109471.tif 000006
【図４】
2011109471.tif 000007
【図５】
2011109471.tif 000008
【図６】
2011109471.tif 000009
【図７】
2011109471.tif 000010
【図８】
2011109471.tif 000011
【図９】
2011109471.tif 000012
【図１０】
2011109471.tif 000013
【図１１】
2011109471.tif 000014
【図１２】
2011109471.tif 000015
【図１３】
2011109471.tif 000016
【図１４】
2011109471.tif 000017
【図１５】
2011109471.tif 000018