(57)【特許請求の範囲】
【請求項１】
通信フローのうち、品質値が予め決められた第１の閾値より悪い品質不良フローと、品質値が予め決められた第２の閾値より良い品質良好フローとを抽出するとともに、前記品質不良フローと前記品質良好フローとが同一の輻輳リンクを通過している場合、前記品質良好フローを、経路を移動する候補となる移動対象候補フローとして抽出する移動対象候補抽出部と、
前記移動対象候補抽出部が抽出した前記移動対象候補フローの移動先の経路の候補となる移動先経路候補を、前記同一の輻輳リンクを通過しない経路となるように抽出する経路抽出装置と、
前記移動対象候補抽出部が抽出した前記移動対象候補フローを、経路の移動を実施する移動対象フローに決定する移動対象フロー決定部と、
を備えることを特徴とする通信システム。
【請求項２】
前記移動対象フロー決定部は、
前記経路抽出装置が抽出した前記移動先経路候補に移動させたときの前記移動対象候補フローの品質値が、前記品質不良フローの品質値よりも所定の閾値以上悪化しない場合、前記移動対象候補フローを前記移動対象フローに決定する、
ことを特徴とする請求項１に記載の通信システム。
【請求項３】
前記移動対象候補抽出部は、
前記通信フローのうち、前記移動対象フロー決定部により前記移動対象フローとして決定された通信フロー以外の通信フローを、前記移動対象候補フローとしてさらに抽出し、
前記移動対象フロー決定部は、
前記移動対象候補抽出部によりさらに抽出された前記移動対象候補フローを前記移動先経路候補に移動させたときの品質値が移動前の品質値より向上する場合、当該さらに抽出された前記移動対象候補フローを前記移動対象フローに決定する、
ことを特徴とする請求項１または請求項２に記載の通信システム。
【請求項４】
通信フローのうち、品質値が予め決められた第１の閾値より悪い品質不良フローと、品質値が予め決められた第２の閾値より良い品質良好フローとを抽出するとともに、前記品質不良フローと前記品質良好フローとが同一の輻輳リンクを通過している場合、前記品質良好フローを、経路を移動する候補となる移動対象候補フローとして抽出する移動対象候補抽出部と、
前記移動対象候補抽出部が抽出した前記移動対象候補フローを、前記同一の輻輳リンクを通過しない経路に移動を実施する移動対象フローに決定する移動対象フロー決定部と、
を備えることを特徴とする経路制御装置。
【請求項５】
移動対象候補抽出部が、通信フローのうち、品質値が予め決められた第１の閾値より悪い品質不良フローと、品質値が予め決められた第２の閾値より良い品質良好フローとを抽出するとともに、前記品質不良フローと前記品質良好フローとが同一の輻輳リンクを通過している場合、前記品質良好フローを、経路を移動する候補となる移動対象候補フローとして抽出する手順と、
移動対象フロー決定部が、前記移動対象候補抽出部が抽出した前記移動対象候補フローを、前記同一の輻輳リンクを通過しない経路に移動を実施する移動対象フローに決定する手順と、
を有することを特徴とする経路制御方法。
【請求項６】
コンピュータに、
通信フローのうち、品質値が予め決められた第１の閾値より悪い品質不良フローと、品質値が予め決められた第２の閾値より良い品質良好フローとを抽出するとともに、前記品質不良フローと前記品質良好フローとが同一の輻輳リンクを通過している場合、前記品質良好フローを、経路を移動する候補となる移動対象候補フローとして抽出する移動対象候補抽出ステップと、
前記移動対象候補抽出ステップにより抽出された前記移動対象候補フローを、前記同一の輻輳リンクを通過しない経路に移動を実施する経路移動対象フローに決定する移動対象フロー決定ステップと、
を実行させるための経路制御プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信システム、経路制御装置、経路制御方法及び経路制御プログラムに関する。
【背景技術】
【０００２】
インターネット等の一般的なＩＰ（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ：インターネット・プロトコル）通信網においては、パケットの通信経路はＯＳＰＦ（Ｏｐｅｎ  Ｓｈｏｒｔｅｓｔ  Ｐａｔｈ  Ｆｉｒｓｔ）等により決定される。その際、経路探索手法としてダイクストラ法が利用されているため、通信経路は、常に最短ホップ数の経路となる。そのため、ネットワーク内のある一部分への通信トラフィック集中による輻輳の発生により、必要な帯域が確保できずに品質低下が生じる場合がある。その一方、他の部分では通信トラフィックが少なく、ネットワークリソースが余っているという状態が発生する場合があるという問題がある。
【０００３】
これを解決する手法として、非特許文献１には、トラフィック量に応じて最適なメトリック（ｍｅｔｒｉｃ）を算出することで経路の最適化を行う経路制御手法が開示されている。また、非特許文献２には、通信トラフィックの空間分布と時間分布を最適化する経路計算手法が開示されている。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Internet traffic engineering by optimizing OSPF weights，Proc. IEEE INFOCOM，vol. 2，pp.519-528，Mar. 2000、http://www.ecse.rpi.edu/Homepages/koushik/shivkuma-teaching/sp2003/case/CaseStudy/fortz-te-infocom00.pdf
【非特許文献２】藪崎仁史、松原大典、「時間軸を考慮した経路計算アルゴリズムの検討」、電子情報通信学会、新世代ネットワークワークショップ ２００９、http://www.ieice.org/~nwgn/file_ws09/12_yabusaki.pdf
【発明の概要】
【発明が解決しようとする課題】
【０００５】
非特許文献１や非特許文献２では、現在のトラフィックの状態や過去のトラフィックの時間変動情報を利用して、通信する際の経路を決定し、一度決定された経路は通信が完了するまで変更されない。
しかし、一般的に通信はいつどの程度のトラフィックが流れるか分からないし、一つの通信フローにおけるトラフィック量も変動するため、ネットワーク内の一部においてトラフィック量が増大し、輻輳による通信フローの品質低下が発生するという問題がある。
【０００６】
そこで本発明は、上記問題に鑑みてなされたものであり、通信フローの品質低下を防止することを可能とする通信システム、経路制御装置、経路制御方法及び経路制御プログラムを提供することを課題とする。
【課題を解決するための手段】
【０００７】
（１）本発明は前記事情に鑑みなされたもので、本発明の一態様は、通信フローのうち、品質値が予め決められた第１の閾値より悪い品質不良フローと、品質値が予め決められた第２の閾値より良い品質良好フローとを抽出するとともに、前記品質不良フローと前記品質良好フローとが同一の輻輳リンクを通過している場合、前記品質良好フローを、経路を移動する候補となる移動対象候補フローとして抽出する移動対象候補抽出部と、前記移動対象候補抽出部が抽出した前記移動対象候補フローの移動先の経路の候補となる移動先経路候補を、前記同一の輻輳リンクを通過しない経路となるように抽出する経路抽出装置と、前記移動対象候補抽出部が抽出した前記移動対象候補フローを、経路の移動を実施する移動対象フローに決定する移動対象フロー決定部と、を備えることを特徴とする通信システムである。
【０００８】
（２）上記に記載の通信システムにおいて、本発明の一態様は、前記移動対象フロー決定部が、前記経路抽出装置が抽出した前記移動先経路候補に移動させたときの前記移動対象候補フローの品質値が、前記品質不良フローの品質値よりも所定の閾値以上悪化しない場合、前記移動対象候補フローを前記移動対象フローに決定する、ことを特徴とする。
【０００９】
（３）上記に記載の通信システムにおいて、本発明の一態様は、前記移動対象候補抽出部が、前記通信フローのうち、前記移動対象フロー決定部により前記移動対象フローとして決定された通信フロー以外の通信フローを、前記移動対象候補フローとしてさらに抽出し、前記移動対象フロー決定部は、前記移動対象候補抽出部によりさらに抽出された前記移動対象候補フローを前記移動先経路候補に移動させたときの品質値が移動前の品質値より向上する場合、当該さらに抽出された前記移動対象候補フローを前記移動対象フローに決定する、ことを特徴とする。
【００１０】
（４）本発明の一態様は、通信フローのうち、品質値が予め決められた第１の閾値より悪い品質不良フローと、品質値が予め決められた第２の閾値より良い品質良好フローとを抽出するとともに、前記品質不良フローと前記品質良好フローとが同一の輻輳リンクを通過している場合、前記品質良好フローを、経路を移動する候補となる移動対象候補フローとして抽出する移動対象候補抽出部と、前記移動対象候補抽出部が抽出した前記移動対象候補フローを、前記同一の輻輳リンクを通過しない経路に移動を実施する移動対象フローに決定する移動対象フロー決定部と、を備えることを特徴とする経路制御装置である。
【００１１】
（５）本発明の一態様は、移動対象候補抽出部が、通信フローのうち、品質値が予め決められた第１の閾値より悪い品質不良フローと、品質値が予め決められた第２の閾値より良い品質良好フローとを抽出するとともに、前記品質不良フローと前記品質良好フローとが同一の輻輳リンクを通過している場合、前記品質良好フローを、経路を移動する候補となる移動対象候補フローとして抽出する手順と、移動対象フロー決定部が、前記移動対象候補抽出部が抽出した前記移動対象候補フローを、前記同一の輻輳リンクを通過しない経路に移動を実施する移動対象フローに決定する手順と、を有することを特徴とする経路制御方法である。
【００１２】
（６）本発明の一態様は、コンピュータに、通信フローのうち、品質値が予め決められた第１の閾値より悪い品質不良フローと、品質値が予め決められた第２の閾値より良い品質良好フローとを抽出するとともに、前記品質不良フローと前記品質良好フローとが同一の輻輳リンクを通過している場合、前記品質良好フローを、経路を移動する候補となる移動対象候補フローとして抽出する移動対象候補抽出ステップと、前記移動対象候補抽出ステップにより抽出された前記移動対象候補フローを、前記同一の輻輳リンクを通過しない経路に移動を実施する経路移動対象フローに決定する移動対象フロー決定ステップと、を実行させるための経路制御プログラムである。
【発明の効果】
【００１５】
本発明によれば、通信フローの品質低下を防止することができる。
【図面の簡単な説明】
【００１６】
【図１】本実施形態における通信システムの概略ブロック図である。
【図２】本実施形態における経路制御装置の概略ブロック図である。
【図３】トポロジ情報記憶部に記憶されているテーブルＴ１の一例である。
【図４】フロー情報記憶部に記憶されているテーブルＴ２の一例である。
【図５】本実施形態の経路制御装置による品質値向上の効果を説明するための図である。
【図６】本実施形態における経路制御決定部の概略ブロック図である。
【図７】第２の抽出部の処理を説明するための図である。
【図８】本実施形態における通信システムの処理の流れの一例を示すフローチャートである。
【図９】図８のステップＳ１０４における移動処理決定処理の流れの一例を示したフローチャートである。
【図１０】フロー情報記憶部に記憶されているテーブルＴ２の一例であるテーブルＴ２−２である。
【図１１】トポロジ情報記憶部に記憶されているテーブルＴ１の一例であるテーブルＴ１−２である。
【図１２】図１０のテーブルＴ２−２において品質値の値が格納された後のテーブルである。
【図１３】フロー情報記憶部に記憶されているテーブルＴ２の一例であるテーブルＴ２−４とトポロジ情報記憶部に記憶されているテーブルＴ１の一例であるテーブルＴ１−３である。
【図１４】トポロジ情報記憶部に記憶されているテーブルＴ１の一例であるテーブルＴ１−４である。
【発明を実施するための形態】
【００１７】
以下、本発明の実施形態について、図面を参照して詳細に説明する。図１は、本実施形態における通信システムの概略ブロック図である。通信システム１は、ＮＷ情報収集装置１００と、経路制御装置２００と、経路抽出装置３００と、パケット転送装置制御装置４００とを備える。また、同図に置いて、通信システム１が全体最適を図るために経路制御を行う対象となる制御対象ネットワーク１０が示されている。制御対象ネットワーク１０は、一例として、パケット転送装置１１、…、１７の七つのパケット転送装置を備える。なお、パケット転送装置の数はこれに限らず、制御対象ネットワーク１０に応じた任意の数を取り得るものとする。
【００１８】
パケット転送装置１１、…、１７は、例えば、ルータやスイッチ等である。パケット転送装置１１、…、１７は、パケット転送装置制御装置４００と接続しており、パケット転送装置制御装置４００からの指示に従って通信経路を変更する。
具体的には、例えば、パケット転送装置１１、…、１７がＯｐｅｎＦｌｏｗ対応スイッチの場合、パケット転送装置１１、…、１７は、パケット転送装置パケット転送装置制御装置４００としてのＯｐｅｎＦｌｏｗコントローラからの指示に従って通信経路を変更する。
【００１９】
また、同図に、通信フローの一例として、通信フロー２０が示されている。通信フロー２０は、パケット転送装置１２、パケット転送装置１３、パケット転送装置１４、パケット転送装置１５を順に通る通信フローである。この通信フロー２０は、制御対象ネットワークを流れる何らかのサービスを実現するための通信フローである。以下、通信フローを単にフローともいう。
【００２０】
ＮＷ情報収集装置１００が、制御対象ネットワーク１０のトポロジを管理する。具体的には、例えば、ＮＷ情報収集装置１００は、以下のようにしてトポロジを示すトポロジ情報を生成する。ＮＷ情報収集装置１００は、パケット転送装置１１、…、１７に一意となるノードＩＤを付与する。また、ＮＷ情報収集装置１００は、パケット転送装置間の各リンクにも一意となるリンクＩＤを付与する。ここで、リンクとは、二つのパケット転送装置が他のパケット転送装置を経由せずに直接繋がっている通信経路である。また、リンクＩＤは、リンクを一意に識別可能な情報である。
【００２１】
その上で、ＮＷ情報収集装置１００は、リンクＩＤ、ソース（Ｓｒｃ）ノードＩＤ及び到達（Ｄｓｔ）ノードＩＤの組合せとしてトポロジ情報を生成する。ＳｒｃノードＩＤは、リンクのＳｒｃ側のパケット転送装置を一意に識別可能な情報である。ＤｓｔノードＩＤは、リンクのＤｓｔ側のパケット転送装置を一意に識別可能な情報である。
【００２２】
また、ＮＷ情報収集装置１００は、制御対象ネットワーク内からパケット情報を収集する。そして、ＮＷ情報収集装置１００は、収集したパケット情報に基づいて、各リンクの通信品質を示す品質値情報（例えば、遅延時間、ゆらぎ、パケットロス等）と各リンクの帯域使用率とを算出する。また、ＮＷ情報収集装置１００は、収集したパケット情報に基づいて、ネットワーク内を流れている通信フローを示すフロー情報（例えば、フローＩＤ、始点ノード、終点ノード、通過経路等）を生成する。
【００２３】
例えば、パケット転送装置１１、…、１７のミラーポートにパケット収集装置が設置されている場合、ＮＷ情報収集装置１００は、パケット収集装置がキャプチャしたパケット情報から各リンクの品質値情報を算出し、フロー情報を生成する。具体的には、例えば、ＮＷ情報収集装置１００は、パケットの到達時刻の差を利用して、遅延時間又はゆらぎを算出する。また、例えば、ＮＷ情報収集装置１００は、パケットロス率を、パケット収集装置が収集したパケット数の差から算出する。また、例えば、ＮＷ情報収集装置１００は、単位時間当たりのバイト数に基づいて、帯域使用率を算出する。
【００２４】
ＮＷ情報収集装置１００は、生成したトポロジ情報、各リンクの品質値情報、各リンクの帯域使用率及びフロー情報を経路制御装置２００へ出力する。
【００２５】
経路制御装置２００は、ＮＷ情報収集装置１００から入力された、各リンクの品質値情報およびフロー情報に基づき、通信フロー内の経路を移動する移動対象フローを決定する。具体的には、例えば、経路制御装置２００は、以下のようにして移動対象フローを決定する。経路制御装置２００は、フローの品質値情報に基づいて、移動対象候補フローを抽出する。そして、経路制御装置２００は、抽出した移動対象候補フローを経路抽出装置３００に出力して、品質値が最良の経路を示す移動先経路候補を経路抽出装置３００から取得する。そして、経路制御装置２００は、現在の経路の品質値と移動先経路候補の品質値とを比較し、改善が見込まれるか否か判定する。
【００２６】
そして、経路制御装置２００は、改善が見込まれるフローについて、移動処理をパケット転送装置制御装置４００に指示する。これにより、パケット転送装置制御装置４００がパケット転送装置１１、…、１７に対して経路変更処理を実施する。
これにより、経路制御装置２００は、ネットワークの状態を常に監視し、流れている通信フローも含めて動的に経路変更を実施することにより、常にネットワーク全体を最適化することができる。
【００２７】
経路抽出装置３００は、経路制御装置２００から入力された移動対象候補フロー内の経路を移動させたときの品質値に基づいて、経路を抽出する。具体的には、例えば、経路抽出装置３００は、移動対象候補フロー内の経路を移動させたときの移動対象候補フローの品質値が最良となる経路を抽出する。経路抽出装置３００は、抽出した移動先経路候補を経路制御装置２００へ出力する。なお、この抽出方式は何でも良い。
パケット転送装置制御装置４００は、経路制御装置２００からの指示に基づいて、制御対象ネットワーク１０内のパケット転送装置１１、…、１７に対して、経路変更を指示する。
【００２８】
図２は、本実施形態における経路制御装置２００の概略ブロック図である。経路制御装置２００は、ＮＷ情報取得部２１０と、トポロジ情報記憶部２２０と、フロー情報更新部２３０と、フロー情報記憶部２４０と、経路制御決定部２５０と、経路情報送信部２７０とを備える。
【００２９】
ＮＷ情報取得部２１０は、ＮＷ情報収集装置１００からトポロジ情報、各リンクの品質値情報、各リンクの帯域使用率及びフロー情報を取得する。そして、ＮＷ情報取得部２１０は、取得したトポロジ情報、各リンクの品質値情報及び各リンクの帯域使用率を基に、トポロジ情報記憶部２２０に記憶された情報を更新する。また、ＮＷ情報取得部２１０は、フロー情報をフロー情報更新部２３０に出力する。  
なお、ＮＷ情報取得部２１０は、ＮＷ情報収集装置に対して、取得したいリンクの情報を与え、当該リンクの情報のみを取得するようにしても良い。
【００３０】
トポロジ情報記憶部２２０には、リンクＩＤ、そのリンクＩＤのリンクのＳｒｃノードＩＤ、そのリンクＩＤのリンクのＤｓｔノードＩＤ、そのリンクＩＤが示すリンクの品質値情報及びそのリンクＩＤが示すリンクの帯域使用率が関連付けられて記憶されている。
【００３１】
フロー情報更新部２３０は、ＮＷ情報取得部２１０から入力されたフロー情報に基づき、フロー情報記憶部２４０に記憶された情報を更新する。フロー情報更新部２３０は、フロー情報を更新した更新通知を経路制御決定部２５０へ出力する。
【００３２】
フロー情報記憶部２４０には、フローＩＤ、そのフローＩＤが示すフローの始点ノード、そのフローＩＤが示すフローの終点ノード、そのフローＩＤが示すフローの経路及びそのフローＩＤが示すフローの品質値情報が関連付けられて記憶されている。ここで、フローＩＤは、フローを一意に識別可能な情報である。また、始点ノードは、制御対象ネットワーク１０において、当該フローが入ってきたパケット転送装置を識別する情報である。また、終点ノードは、制御対象ネットワーク１０において、当該フローが出て行くパケット転送装置を識別する情報である。経路は当該フローが通過するリンクリストである。品質値情報は、フローが通過する経路内の各リンクの品質値から算出されるフローの品質値を示す情報である。
【００３３】
経路制御決定部２５０は、フロー情報記憶部２４０に格納されているネットワーク内のフロー情報を参照し、経路の移動対象候補となる移動対象候補フローを決定する。また、経路制御決定部２５０は、決定した移動対象候補フローを経路抽出装置３００へ出力し、経路抽出装置３００に移動先経路候補を抽出させる。そして、経路制御決定部２５０は、経路抽出装置３００が抽出した移動先経路候補を経路抽出装置３００から取得する。
【００３４】
そして、経路制御決定部２５０は、現在の品質値と移動先経路候補の品質値とを比較し、移動先経路候補の品質値が現在の品質値（移動対象候補フロー品質値）よりも改善するか否か判定する。経路制御決定部２５０は、移動先経路候補の品質値が現在の品質値よりも改善する場合、移動対象候補フローを移動対象フローに決定する。そして、経路制御決定部２５０は、決定した移動対象フローの移動先経路情報を経路情報送信部２７０へ出力する。
【００３５】
ここで、経路制御決定部２５０は、移動対象候補抽出部２５１と、移動対象フロー決定部２６１とを備える。移動対象候補抽出部２５１は、通信フローの品質値に基づいて、通信フローのうち該通信フローに含まれる経路を移動する候補となる移動対象候補フローを抽出する。また、後述する第２の抽出処理において、移動対象候補抽出部２５１は、通信フローの品質値と該通信フローを構成するリンクの帯域利用率とに基づいて、移動対象候補フローを抽出する。移動対象候補抽出部２５１の処理の詳細は、後述する。
【００３６】
移動対象フロー決定部２６１は、経路抽出装置３００が抽出した移動先経路候補の品質値が移動対象候補フローの品質値よりも改善する場合、移動対象候補フローを経路の移動を実施する移動対象フローに決定する。換言すれば、移動対象フロー決定部２６１は、移動対象候補抽出部２５１が抽出した移動対象候補フローのうち、経路の移動により通信フローの品質値が改善される移動対象候補フローを、経路の移動を実施する経路移動対象フローに決定する。移動対象フロー決定部２６１の処理の詳細は後述する。
【００３７】
経路情報送信部２７０は、経路制御決定部２５０から入力された各移動対象フローの移動先経路情報をパケット転送装置制御装置４００へ送信する。これにより、パケット転送装置制御装置４００は、経路情報送信部２７０から受信した移動先経路情報に基づき、パケット転送装置１１、…、１７内の経路情報を更新する。
【００３８】
図３は、トポロジ情報記憶部２２０に記憶されているテーブルＴ１の一例である。テーブルＴ１において、リンクＩＤ、ＳｒｃノードＩＤ、ＤｓｔノードＩＤ、品質値及び帯域使用率が一組のデータとして格納される。品質値及び帯域使用率は、それぞれＮＷ情報収集装置１００から受け取った品質値情報及び帯域使用率の格納領域である。このように、トポロジ情報記憶部２２０には、リンクＩＤ毎に、ＳｒｃノードＩＤ、ＤｓｔノードＩＤ、品質値及び帯域使用率が関連付けられて記憶されている。
【００３９】
図４は、フロー情報記憶部２４０に記憶されているテーブルＴ２の一例である。テーブルＴ２において、フローＩＤ、始点ノード、終点ノード、経路及び品質値の組が一組のデータとして格納される。
【００４０】
続いて、移動対象候補抽出部２５１の処理の目的について説明する。移動対象候補抽出部２５１は、以下の三つの目的により、移動対象候補フローの抽出をそれぞれ実施する。第１の目的は、移動対象候補抽出部２５１は、品質の悪い通信フローの経路を変更し、通信フローの品質値の向上を図るものである。この第１の目的のために移動対象候補フローを抽出する処理を第１の抽出処理と称する。第２の目的は、品質の良い通信フローの経路を変更し、当該通信フローが通過するリンクを共有する他の品質の悪い通信フローの品質値の向上を図るものである。この第２の目的のために移動対象候補フローを抽出する処理を第２の抽出処理と称する。第３の目的は、上記以外の通信フローについても、通信フローの品質値が向上する場合には、通信フローの経路を変更するものである。この第３の目的のために移動対象候補フローを抽出する処理を第３の抽出処理と称する。
【００４１】
図５は、本実施形態の経路制御装置２００による品質値向上の効果を説明するための図である。同図において、ネットワーク内のフローの品質値の頻度分布３０が示されている。ここで、頻度分布３０の縦軸は頻度で横軸は品質値である。同図において、矢印３１は、第１の抽出処理によって頻度分布が移動する方向を示している。また、矢印３２は、第２の抽出処理によって頻度分布が移動する方向を示している。また、矢印３３は、第３の抽出処理によって頻度分布が移動する方向を示している。
また、第１〜第３の抽出処理によって頻度分布３０が頻度分布３５に変更されることが示されている。また、破線で示された頻度分布３４は、頻度分布３０と同じ頻度分布を表している。ここで、頻度分布３４及び頻度分布３５の縦軸は頻度で横軸は品質値である。
【００４２】
第１の抽出処理及び第２の抽出処理は分散を小さくする働きとなる。これにより、経路制御装置２００は、利用者の間で、品質の公平性を実現することができる。第３の抽出処理は品質値の平均を品質値の良い方向へ移動させる働きとなる。これにより、経路制御装置２００は、全体的な品質値を向上させることができる。
【００４３】
図６は、本実施形態における経路制御決定部２５０の概略ブロック図である。移動対象候補抽出部２５１は、輻輳リンク抽出部２５２と、品質不良フロー抽出部２５３と、品質良好フロー抽出部２５５と、第２の抽出部２５６と、第３の抽出部２５７とを備える。
輻輳リンク抽出部２５２は、トポロジ情報記憶部２２０を参照して、帯域使用率が予め決められた閾値以上となる輻輳リンクを抽出し、抽出した輻輳リンクを第２の抽出部２５６へ出力する。
【００４４】
また、輻輳リンク抽出部２５２は、フロー情報記憶部２４０を参照し、輻輳リンクにおいて、当該リンクを経由するフローの中に品質値が予め決められた閾値を下回るものが含まれるリンクを抽出する。以降、このリンクを「品質不良フロー経由輻輳リンク」と呼ぶ。ここで、閾値は、絶対値でも良いし、パーセンタイル値でもよい。輻輳リンク抽出部２５２は、抽出した品質不良フロー経由輻輳リンクを移動対象フロー決定部２６１の後述する移動先経路候補取得部２６２へ出力する。
【００４５】
品質不良フロー抽出部２５３は、第１の抽出処理を実行する。具体的には、品質不良フロー抽出部２５３は、フロー情報記憶部２４０を参照して、品質値が予め決められた第１の閾値より悪い品質不良フローを抽出する。ここで、例えば、品質値が遅延時間の場合には、第１の閾値も遅延時間に関する閾値であり、品質不良フロー抽出部２５３は、遅延時間が予め決められた第１の閾値より大きい品質不良フローを抽出する。また、例えば、品質値がパケットロスの場合には、第１の閾値もパケットロスに関する閾値であり、品質不良フロー抽出部２５３は、パケットロスが予め決められた第１の閾値より大きい品質不良フローを抽出する。
また、品質不良フロー抽出部２５３は、抽出した品質不良フローを移動対象候補フローとする。そして、品質不良フロー抽出部２５３は、この移動対象候補フローを示す移動対象候補フロー情報を移動対象フロー決定部２６１の後述する移動先経路候補取得部２６２へ出力する。
【００４６】
品質良好フロー抽出部２５５は、品質不良フロー抽出部２５３によって移動対象候補フローとして抽出されたが、その後の移動対象フロー決定部２６１の判定によって移動対象フローに決定されなかった移動対象候補フローが存在した場合に処理を実施する。以降、このフローを「経路制御対象外の品質不良フロー」と呼ぶこととする。
【００４７】
具体的には、品質良好フロー抽出部２５５は、経路制御対象外の品質不良フローを移動対象フロー決定部２６１から取得した場合、フロー情報記憶部２４０を参照して、品質値が予め決められた第２の閾値より高い品質良好フローを抽出する。そして、品質良好フロー抽出部２５５は、抽出した品質良好フローを経路制御対象外の品質不良フローとともに第２の抽出部２５６へ出力する。
【００４８】
第２の抽出部２５６は、第２の抽出処理を実行する。具体的には、第２の抽出部２５６は、品質良好フロー抽出部２５５が抽出した品質良好フローと経路制御対象外の品質不良フローとが、同一の輻輳リンクを通過している場合、品質良好フローを移動対象候補フローとして抽出する。換言すると、第２の抽出部２５６は、品質値が予め決められた第１の閾値より品質値が悪く、移動対象フロー決定部２６１の判定によって移動対象フローに決定されなかった品質不良フローと、品質値が予め決められた第２の閾値より良い品質良好フローとが、同一の輻輳リンクを通過している場合、品質良好フローを移動対象候補フローとして抽出する。第２の抽出部２５６は、抽出した移動対象候補フローを示す移動対象候補フロー情報を移動対象フロー決定部２６１の後述する移動先経路候補取得部２６２へ出力する。
【００４９】
第３の抽出部２５７は、第３の抽出処理を実行する。具体的には、第３の抽出部２５７は、フロー情報記憶部２４０を参照して、品質不良フロー抽出部２５３と第２の抽出部２５６により移動対象候補フローとして抽出され、移動対象フロー決定部２６１の判定によって移動対象フローに決定されなかった通信フロー全て、もしくはその一部をランダムに選択し、選択した通信フローを移動対象候補フローとして抽出する。そして、第３の抽出部２５７は、抽出した移動対象候補フローを示す移動対象候補フロー情報を移動対象フロー決定部２６１の後述する移動先経路候補取得部２６２へ出力する。
【００５０】
移動対象フロー決定部２６１は、移動先経路候補取得部２６２と、品質推定部２６３と、経路変更判定部２６４とを備える。
移動先経路候補取得部２６２は、移動対象候補抽出部２５１が抽出した移動対象候補フローの移動先の経路候補である移動先経路候補を取得する。具体的には、移動先経路候補取得部２６２は、品質不良フロー抽出部２５３、第２の抽出部２５６又は第３の抽出部２５７のいずれかから入力された移動対象候補フロー情報と、輻輳リンク抽出部２５２から入力された品質不良フロー経由輻輳リンク情報を経路抽出装置３００へ出力し、経路抽出装置３００から新たな移動先経路候補を取得する。
【００５１】
品質推定部２６３は、移動先経路候補取得部２６２が取得した移動先経路候補に、移動対象候補フローを移動させた際の品質値を推定する。
経路変更判定部２６４は、現在の移動対象候補フローの品質値と品質推定部２６３が推定した品質値との比較に基づいて、その移動対象候補フローの経路を変更するか否か判定する。具体的には、例えば、経路変更判定部２６４は、現在の移動対象候補フローの品質値と品質推定部２６３が推定した品質値とを比較し、予め決められた閾値以上の改善が見込まれる場合、経路の移動の対象となる移動対象フローに決定する。
ここで、第２の抽出部２５６によって抽出された移動対象候補フローについては、経路変更判定部２６４は、経路制御対象外の品質不良フローの品質値と品質推定部２６３が推定した品質値とを比較し、移動対象候補フローの品質値が、品質不良フローの品質値よりも、閾値以上に悪くならない場合、経路の移動の対象となる移動対象フローに決定する。
【００５２】
この閾値は、第１〜３の抽出処理それぞれの場合毎に、異なる値を設定してもよい。例えば、第１の抽出処理では閾値を小さく設定することで少しでも品質が良くなるのであれば、経路変更判定部２６４は、第１の抽出処理で抽出された移動対象候補フローを移動対象フローとして決定してもよい。
一方、第３の抽出処理では閾値をある程度大きく設定することで、大幅に品質が改善できるもののみを移動対象フローとして決定してもよい。
【００５３】
なお、経路抽出装置３００は、移動先経路候補取得部２６２から入力された品質不良フロー経由輻輳リンク情報に含まれるリンクが、移動先経路に含まれないように経路を決定する。これにより、経路フローを移動することで、品質の悪いフローの品質を更に悪化させることを防ぐことができる。また、経路抽出装置３００による移動先経路探索の際、これらのリンクを探索対象となるトポロジから除外することで、経路探索処理の効率化も実現できる。
【００５４】
またこれを実現するために、移動対象フロー決定部２６１は、品質不良フロー経由輻輳リンクを除外したトポロジ情報をあらかじめ準備し、それを移動先経路探索の対象トポロジ情報として経路抽出装置３００へ渡してもよい。
【００５５】
図７は、第２の抽出部２５６の処理を説明するための図である。同図において、「状態ａ」は二つのフローが通過するリンクの帯域使用率が低い場合を、「状態ｂ」は二つのフローが通過するリンクの帯域使用率が高い場合を示した図である。「状態ａ」において、パケット伝送装置５１とパケット伝送装置５２との間のリンク５３の帯域使用率が低いことが示されている。「状態ｂ」において、パケット伝送装置５４とパケット伝送装置５５との間のリンク５６の帯域使用率が高いことが示されている。また、「状態ａ」も「状態ｂ」も品質の良いフローと品質の悪いフローとが同じリンクを使用している。
【００５６】
一般に、輻輳が発生すると品質が低下する可能性が高い。そのため、「状態ａ」では、品質が悪くなった原因箇所は、上図のリンクでない可能性が高い。一方、「状態ｂ」は当該リンクの帯域使用率が高いため、そこが品質低下の要因となっている可能性がある。そのため、第２の抽出部２５６は、「状態ａ」の時は品質の良いフローを移動対象候補フローとせず、「状態ｂ」の時は品質の良いフローを移動対象候補フローとして抽出する。
【００５７】
図８は、本実施形態における通信システム１の処理の流れの一例を示すフローチャートである。通信システム１は、以下のステップＳ１０１〜Ｓ１０５の処理を繰り返し実施する。
まず、ステップＳ１０１において、ＮＷ情報取得部２１０は、ＮＷ情報収集装置１００から各リンクの品質値情報及びフロー情報を取得する。ここで、品質値情報は、例えば、各リンクのリンクＩＤ、ＳｒｃノードＩＤ、ＤｓｔノードＩＤ、品質値及び帯域使用率を示す情報である。また、フロー情報は、例えば、各フローのフローＩＤ、始点ノード、終点ノード及び通過経路である。
【００５８】
次に、ステップＳ１０２において、ＮＷ情報取得部２１０は、ＮＷ情報収集装置１００から取得した各リンクの品質値情報をトポロジ情報記憶部２２０のテーブルＴ１に格納する。なお、制御対象ネットワークのトポロジ（リンクＩＤ／ＳｒｃノードＩＤ／ＤｓｔノードＩＤ）については、ＮＷ情報取得部２１０で管理している情報を事前に把握できているものとする。
【００５９】
次に、ステップＳ１０３において、フロー情報更新部２３０は、ＮＷ情報収集装置１００から得られた各フローの通過経路、およびトポロジ情報から得られるフローの通過経路の各リンクの品質値情報から、フローの始点ノードから終点ノードまでの品質値を算出する。フロー情報更新部２３０は、算出した品質値を、フローＩＤ、始点ノード、終点ノード及び経路と関連付けてフロー情報記憶部２４０のテーブルＴ２に格納する。
【００６０】
また、フロー情報更新部２３０は、ＮＷ情報取得部２１０が受け取ったフロー情報とフロー情報記憶部２４０を照合し、フローの追加又は削除を行う。また、フローが通過する各リンクの品質値情報をトポロジ情報記憶部２２０から参照し、フローの始点ノードから終点ノードまでの品質値を算出し、フロー情報記憶部２４０のテーブルＴ２を更新する。
【００６１】
ここで、フローの品質値情報は、リンクの品質値情報と同一の品質指標であるとは限らない。例えば、リンクの品質値情報が単一の品質指標（遅延時間、パケットロス、ゆらぎ等のいずれか）で構成される場合には、フローの品質値も始点ノードから終点ノードまでの当該品質指標を用いることが想定されるが、リンクの品質値情報が複数の品質指標で構成される場合には、それらを用いて算出される別の品質指標（例えば、ＱｏＥ（Ｑｕａｌｉｔｙ  ｏｆ  Ｅｘｐｅｒｉｅｎｃｅ）等）をフローの品質値情報としてもよい。ここで、ＱｏＥとは、利用者の体感の品質であり、ネットワーク自体ではなく、その上で提供されるアプリケーションサービスの体感品質のことである。またリンクの品質値情報が単一の品質指標であっても、それが帯域利用率等であれば、フローの品質値情報は利用帯域幅等の異なる品質指標となる場合もある。
【００６２】
次に、ステップＳ１０４において、経路制御決定部２５０は、移動対象候補抽出部２５１により移動対象候補フローを選定する。そして、経路制御決定部２５０は、移動対象フロー決定部２６１により移動対象候補フローのうち、経路の移動により通信フローの品質値が改善される移動対象候補フローを、経路の移動を実施する経路移動対象フローに決定する。この処理の詳細は後述する。
【００６３】
次に、ステップＳ１０５において、経路情報送信部２７０が、経路移動対象フローを示す経路移動対象フロー情報と移動先経路情報とをパケット転送装置制御装置４００へ渡す。これにより、パケット転送装置制御装置４００は、経路の移動処理を実施する。
【００６４】
以上、通信システム１は、ステップＳ１０１〜Ｓ１０５の処理を繰り返し実施することで、ネットワーク内を流れる通信フローが変化しても、常に全体の通信フローが最適になるように通信経路を制御することができる。
【００６５】
図９は、図８のステップＳ１０４における移動処理決定処理の流れの一例を示したフローチャートである。
まず、ステップＳ２０１において、輻輳リンク抽出部２５２は、輻輳リンクを抽出する。また、輻輳リンク抽出部２５２は、品質不良フロー経由輻輳リンクを抽出し、ステップＳ２０２へ遷移する。
【００６６】
次に、ステップＳ２０２において、品質不良フロー抽出部２５３は、上述した第１の抽出処理により移動対象候補フローを抽出し、ステップＳ２０３へ遷移する。
次に、ステップＳ２０３において、移動対象フロー決定部２６１は、第１の抽出処理により抽出された移動対象候補フローの経路を移動するか否か判定する。移動対象候補フローの経路を移動すると判定した場合（ステップＳ２０３  ＹＥＳ）、移動対象フロー決定部２６１は、その移動対象候補フローを経路移動対象フローに決定し（ステップＳ２０４）、ステップＳ２１０へ遷移する。
【００６７】
一方、抽出された複数の移動対象候補フロー内に、経路を移動しないと判定したフローが存在した場合（ステップＳ２０３  ＮＯ）、移動対象フロー決定部２６１は、その移動対象候補フローを経路制御対象外の品質不良フローとし（ステップＳ２０５）、ステップＳ２０６へ遷移する。
次に、ステップＳ２０６において、品質良好フロー抽出部２５５は、品質良好フローを抽出し、ステップＳ２０７へ遷移する。
【００６８】
次に、ステップＳ２０７において、第２の抽出部２５６は、第２の処理により経路移動対象フローを抽出する。具体的には、第２の抽出部２５６は、品質良好フローと経路制御対象外の品質不良フローが同一の輻輳リンクを通過しているとき、当該品質の良いフローを経路移動対象フローとして抽出し、ステップＳ２０８へ遷移する。
【００６９】
次に、ステップＳ２０８において、移動対象フロー決定部２６１は、第２の抽出処理により抽出された移動対象候補フローの経路を移動するか否か判定する。移動対象候補フローの経路を移動すると判定した場合（ステップＳ２０８  ＹＥＳ）、移動対象フロー決定部２６１は、その移動対象候補フローを経路移動対象フローに決定し（ステップＳ２０９）、ステップＳ２１０へ遷移する。移動対象候補フローの経路を移動しないと判定した場合（ステップＳ２０８  ＮＯ）、移動対象フロー決定部２６１は、ステップＳ２１０へ遷移する。
【００７０】
次に、ステップＳ２１０において、第３の抽出部２５７は、第３の抽出処理により移動対象候補フローを抽出する。具体的には、第３の抽出部２５７は、品質不良フロー抽出部２５３と第２の抽出部２５６により移動対象候補フローとして抽出され、移動対象フロー決定部２６１の判定によって移動対象フローに決定されなかった通信フロー全て、もしくはその一部をランダムに選択し、選択した通信フローを移動対象候補フローとして抽出する。
【００７１】
次に、ステップＳ２１１において、移動対象フロー決定部２６１は、第３の抽出処理により抽出された移動対象候補フローの経路を移動するか否か判定する。移動対象候補フローの経路を移動すると判定した場合（ステップＳ２１１  ＹＥＳ）、移動対象フロー決定部２６１は、その移動対象候補フローを経路移動対象フローに決定し（ステップＳ２１２）、その処理を終了する。移動対象候補フローの経路を移動しないと判定した場合（ステップＳ２１１  ＮＯ）、移動対象フロー決定部２６１はその処理を終了する。以上で、本フローチャートの処理を終了する。
【００７２】
続いて、一実施例として、リンクの品質値情報およびフローの品質値情報（全体最適化する品質）の品質指標として遅延時間を例に、経路制御装置２００の処理を説明する。以下、リンクＩＤがＬｋ（ｋは正の整数）のリンクを単にリンクＬｋと呼ぶ。例えば、リンクＩＤがＬ３のリンクをリンクＬ３と呼ぶ。また、フローＩＤがＦｋのフローを単にフローＦｋと呼ぶ。例えば、フローＩＤがＦ１のフローをフローＦ１と呼ぶ。
【００７３】
経路制御装置２００は、トポロジ（リンクＩＤ／ＳｒｃノードＩＤ／ＤｓｔノードＩＤ）を事前に把握している。そのため、ＮＷ情報取得部２１０は、ＮＷ情報収集装置１００から得られた各リンクの品質値情報を、トポロジ情報記憶部２２０に記憶されているテーブルＴ１の品質値と帯域使用率のカラムに値を格納する。
【００７４】
次に、フロー情報更新部２３０は、ＮＷ情報収集装置１００から得られたフロー情報（通過経路）を、フロー情報記憶部２４０のテーブルＴ２の経路のカラムに値を格納する。
もし、ＮＷ情報収集装置１００から得られた情報に、フロー情報記憶部２４０に含まれない新規のフロー情報が存在する場合には、フロー情報更新部２３０は、新たなレコードを生成し、ＮＷ情報収集装置１００から得られた情報（例えば、フローＩＤ、始点ノード、終点ノード及び経路）を格納する。また、フロー情報記憶部２４０に格納されているフローＩＤのうち、ＮＷ情報収集装置１００から得られた情報に含まれないフロー情報が存在する場合、フロー情報更新部２３０は、当該フローをフロー情報記憶部２４０から削除する。
【００７５】
次に、フロー情報更新部２３０は、トポロジ情報記憶部２２０を参照し、各フローの経路（リンクリスト）に含まれる、各リンクの品質値を取得する。
例えば、あるフローの経路が図１０のテーブルＴ２−２であったとする。図１０は、フロー情報記憶部２４０に記憶されているテーブルＴ２の一例であるテーブルＴ２−２である。同図のテーブルＴ２−２には、フローＩＤ、始点ノード、終点ノード、経路及び品質値が一組のデータとして記憶されている。そして、テーブルＴ２−２には、フローＩＤがＦ１で、始点ノードがＮ１で、終点ノードがＮ２で、経路がリンクＬ１、リンクＬ２、リンクＬ３であるデータが記憶されている。
【００７６】
また、例えば、各リンクの品質値情報が図１１のテーブルＴ１−２であったとする。図１１は、トポロジ情報記憶部２２０に記憶されているテーブルＴ１の一例であるテーブルＴ１−２である。同図のテーブルＴ１−２には、リンクＩＤ、ＳｒｃノードＩＤ、ＤｓｔノードＩＤ、品質値及び帯域使用率が一組のデータとして記憶されている。この例では、品質値は遅延時間である。そして、テーブルＴ１−２には、リンクＩＤがＬ１、Ｌ２、Ｌ３の三組のデータを保持している。例えば、リンクＩＤがＬ１の場合、ＳｒｃノードＩＤがＮ１で、ＤｓｔノードＩＤがＮ１０で、品質値が１０ｍｓである。
【００７７】
この条件で、フロー情報更新部２３０は、テーブルＴ１−２を参照して、各リンクの遅延時間の和「２３ｍｓｅｃ」をフローの始点ノードから終点ノードまでの遅延時間として算出する。そして、算出したフローの始点ノードから終点ノードまでの遅延時間を、フロー情報記憶部２４０に記憶されているテーブルＴ２−２のフローＩＤがＦ１の品質値に格納する。これにより、フロー情報記憶部２４０は、図１２に示すテーブルＴ２−３を保持する。
図１２は、図１０のテーブルＴ２−２において品質値の値が格納された後のテーブルである。同図のテーブルＴ２−３において、フローＩＤがＦ１に対応する品質値に２３ｍｓｅｃが格納されている。
【００７８】
なお、最適化対象となる品質指標が時間以外であれば、フロー情報更新部２３０は、それぞれの品質指標に合わせた算出処理により、フローの品質値を算出する。
【００７９】
図１３は、フロー情報記憶部２４０に記憶されているテーブルＴ２の一例であるテーブルＴ２−４とトポロジ情報記憶部２２０に記憶されているテーブルＴ１の一例であるテーブルＴ１−３である。なお、テーブルＴ２−４及びテーブルＴ１−３において、処理に必要の無い情報は記載していない。
同図のテーブルＴ２−４は、フローＩＤ、経路及び品質値の組を保持している。ここで、品質値は遅延時間である。また、同図のテーブルＴ１−３は、リンクＩＤ及び帯域使用率の組を保持している。
【００８０】
図１３に示されたテーブルＴ２−４がフロー情報記憶部２４０に記憶されており、テーブルＴ１−３がトポロジ情報記憶部２２０に記憶されている場合に、輻輳リンク抽出部２５２は、以下の処理を行う。例えば、輻輳リンクを抽出するための帯域使用率の閾値が８０％であったとすると、輻輳リンク抽出部２５２は、リンクＩＤがＬ３及びＬ４であるリンクを輻輳リンクとして抽出する。
【００８１】
続いて、輻輳リンク抽出部２５２は、品質不良フローが通過する輻輳リンクを抽出する。第２の抽出部２５６は、輻輳リンクすなわちリンクＩＤがＬ３とＬ４のリンクを通過するフローにおいて、品質値が予め決められた閾値よりも悪いものが存在するか否かを判定する。ここで、その閾値を５０ｍｓｅｃとすると、フローＩＤがＦ２とＦ６のフローが品質不良フローに該当するので、輻輳リンク抽出部２５２は、そのフローが通過するリンクＬ４を、品質不良フロー経由輻輳リンクとして抽出する。
【００８２】
続いて、移動対象候補フローの抽出の処理例について説明する。品質不良フロー抽出部２５３は、例えば、絶対値で閾値を指定する場合、その値より悪い品質値が付与されているフローを、移動対象候補フローとしてフロー情報記憶部２４０から抽出する。本例の場合には、品質指標として遅延時間を用いているため、品質不良フロー抽出部２５３は、品質値が閾値より大きなフローを移動対象候補フローとして抽出する。
【００８３】
図１３のテーブルＴ２−４は、フロー情報記憶部２４０に記憶されているテーブルＴ２の一例であり、フローＩＤ、経路及び品質値の組を保持している。例えば、フローＩＤがＦ１のフローは、品質値が９ｍｓｅｃであることが示されている。
【００８４】
ここで、例えば第１の閾値を５０ｍｓｅｃとすると、品質不良フロー抽出部２５３は、遅延時間が５０ｍｓｅｃより大きいフローであるフローＩＤがＦ２とＦ６のフローを、移動対象候補フローとして抽出する。なお、第１の閾値は、絶対値ではなくパーセンタイル値等で指定してもよい。
【００８５】
続いて、第２の抽出部２５６による第２の抽出処理を説明する。
図１３に示されたテーブルＴ２−４がフロー情報記憶部２４０に記憶されており、テーブルＴ１−３がトポロジ情報記憶部２２０に記憶されている場合に、第２の抽出部２５６は、以下の処理を行う。前提として、フローＦ２は、品質不良フロー抽出部２５３により第１の抽出処理において移動対象候補フローとして抽出されたが、その後に移動対象フロー決定部２６１によって経路制御の対象外と判断されたとする。
【００８６】
例えば、閾値を２０ｍｓｅｃとして、品質の良いフローを品質値が２０ｍｓｅｃ未満のフローに定めたとする。このとき、品質良好フロー抽出部２５５は、フローＦ１及びフローＦ４の二つのフローを品質良好フローとして抽出する。
【００８７】
続いて、第２の抽出部２５６は、その品質良好フローＦ１及びＦ４と、経路制御対象外の品質不良フローＦ２とが、同一の輻輳リンクを通過しているか否か判定する。第２の抽出部２５６は、図１３のテーブルＴ２−４を参照して、品質良好フローＦ１と経路制御対象外の品質不良フローＦ２が共有するリンクであるリンクＬ１とリンクＬ２とを抽出する。
【００８８】
また、第２の抽出部２５６は、図１３のテーブルＴ２−４を参照して、品質良好フローＦ４と経路制御対象外の品質不良フローＦ２が共有するリンクであるリンクＬ２とＬ４を抽出する。また、第２の抽出部２５６は、図１３のテーブルＴ１−３を参照して、輻輳リンクとして帯域使用率が８０％以上のリンクＬ３とＬ４を抽出する。
【００８９】
そして、第２の抽出部２５６は、品質良好フローＦ１が輻輳リンクであるリンクＬ３又はＬ４のいずれも含まないので、品質良好フローＦ１と経路制御対象外の品質不良フローＦ２とが、同一の輻輳リンクを通過していないと判定する。一方、第２の抽出部２５６は、品質良好フローＦ４が輻輳リンクであるリンクＬ４を含むので、品質良好フローＦ４と経路制御対象外の品質不良フローＦ２とが、同一の輻輳リンクを通過していると判定する。そして、第２の抽出部２５６は、同一の輻輳リンクを通過していると判定した品質良好フローＦ４を、移動対象フローとして抽出する。
なお、第１の抽出処理と同様に、品質の良いフローを決める閾値は、絶対値ではなくパーセンタイル値等で指定してもよい。
【００９０】
続いて、第３の抽出部２５７による第３の抽出処理について説明する。前提として、図１３のテーブルＴ２−４のフローＦ２とＦ６が第１の抽出処理により移動対象候補フローとして抽出され、第２の抽出処理によりフローＦ４が移動対象候補フローとして抽出されたものとする。
この前提で、第３の抽出部２５７は、上記のフローを除くフローＦ１、Ｆ３、Ｆ５について、その全て、もしくは一部をランダムに選択し、移動対象候補フローとして抽出する。
【００９１】
続いて、移動対象フロー決定部２６１の処理例を、品質不良フロー抽出部２５３による第１の抽出処理の直後に実施される処理を例に説明する。
例えば、品質不良フロー抽出部２５３による第１の抽出処理において、図１３のテーブルＴ２−４のフローＦ６が移動対象候補フローとして抽出されたとする。ここで、フローＦ６の品質値（この例では、遅延時間）は、６６ｍｓｅｃである。
また、輻輳リンク抽出部２５２により、品質不良フローが通過する輻輳リンクとして、図１３のテーブルＴ１−３のリンクＬ３が抽出されたものとする。ここで、リンクＬ３の帯域使用率は、８５％である。
【００９２】
移動対象フロー決定部２６１は、これらの情報を経路抽出装置３００に渡して、フローＦ６の移動先経路候補を取得する。ここで、例えば、移動対象フロー決定部２６１は、移動先経路候補として、リンクＬ７、Ｌ８及びＬ９を取得したとする。
続いて、移動対象フロー決定部２６１は、移動先経路候補に含まれるリンクの品質値をトポロジ情報記憶部２２０から参照し、推定品質値を算出する。
【００９３】
図１４は、トポロジ情報記憶部２２０に記憶されているテーブルＴ１の一例であるテーブルＴ１−４である。なお、トポロジ情報記憶部２２０に記憶されているテーブルＴ１のうち、処理に利用しない部分は記載していない。同図のテーブルＴ１−４において、リンクＬ７の品質値が６ｍｓｅｃで、リンクＬ８の品質値が７ｍｓｅｃで、リンクＬ９の品質値が１１ｍｓｅｃである。ここで、品質値は遅延時間である。
【００９４】
このとき、移動対象フロー決定部２６１は、リンクＬ７の品質値とリンクＬ８の品質値とリンクＬ９の品質値とを加算して、推定品質値として２４（＝６＋７＋１１）ｍｓｅｃを算出する。そして、移動対象フロー決定部２６１は、図１３のテーブルＴ２−４を参照して、フローＦ６の品質値である６６ｍｓｅｃを現在の品質値として取得する。
移動対象フロー決定部２６１は、現在の品質値（６６ｍｓｅｃ）と推定品質値（２４ｍｓｅｃ）とを比較すると、現在の品質値より品質の改善が見込まれるので、フローＦ６  を移動対象フローに決定し、その移動先経路を「リンクＬ７、Ｌ８及びＬ９」とする。
【００９５】
なお、移動対象フロー決定部２６１は、この移動対象フローの決定処理を、移動対象候補フローの抽出処理で抽出したフロー毎に実施する。
また、第２の抽出処理の直後では、移動対象フロー決定部２６１は、移動先経路候補の推定品質値と比較する現在の品質値に、経路制御対象外の品質不良フローの品質値を用いる。
【００９６】
以上、本実施形態によれば、経路制御装置２００は、新たに流れ始めるフローだけでなく、既に流れているフローについても、品質不良フローを移動させるだけでなく、品質不良フローと輻輳リンクを共有する品質良好フローを移動対象候補フローとして抽出する。また、経路制御装置２００は、それ以外のフローを移動対象候補フローとして抽出する。
そして、経路制御装置２００は、経路を移動した後の推定品質値を算出して、品質値の改善が見込まれるフローを移動対象フローに決定する。そして、経路制御装置２００は、移動対象候補抽出部２５１による移動対象候補フロー抽出処理と移動対象フロー決定部２６１による移動対象フロー決定処理を繰り返し実施することにより、フロー全体の品質値を常に最適化することができる。
【００９７】
また、本実施形態において、経路制御装置２００は、品質値として様々な指標を利用することが出来るため、品質値として帯域使用率を用いた場合、部分的な輻輳の抑制やネットワークリソースの利用率向上効果が期待できる。
また、経路制御装置２００は、品質値としてＱｏＥを用いた場合、ユーザの満足度の最適化またはユーザの満足度の向上が図れるため、ユーザによる解約率の低減が期待できる。
また、経路制御装置２００は、ネットワークに求められる要件の一つである公平性を、定めた品質値によって保つことができる。
【００９８】
なお、本実施形態における経路制御装置２００は、通信フローの品質値に基づいて、移動対象候補フローを抽出したが、これに限らず、予め決められた重要な通信フローを移動対象候補フローの一つとしてもよい。
【００９９】
また、複数の装置を備えるシステムが、本実施形態の経路制御装置２００の各処理を、それらの複数の装置で分散して処理してもよい。
また、本実施形態の経路制御装置２００の各処理を実行するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、当該記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することにより、経路制御装置２００に係る上述した種々の処理を行ってもよい。
【０１００】
なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものであってもよい。また、「コンピュータシステム」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、フラッシュメモリ等の書き込み可能な不揮発性メモリ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。
【０１０１】
さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリ（例えばＤＲＡＭ（Ｄｙｎａｍｉｃ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ））のように、一定時間プログラムを保持しているものも含むものとする。また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【０１０２】
以上、本発明の実施形態について図面を参照して詳述したが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【符号の説明】
【０１０３】
１  通信システム
１０  制御対象ネットワーク
１１、１２、１３、１４、１５、１６、１７  パケット転送装置
２０  通信フロー
１００  ＮＷ情報収集装置
２００  経路制御装置
２１０  ＮＷ情報取得部
２２０  トポロジ情報記憶部
２３０  フロー情報更新部
２４０  フロー情報記憶部
２５０  経路制御決定部
２５１  移動対象候補抽出部
２５２  輻輳リンク抽出部
２５３  品質不良フロー抽出部
２５５  品質良好フロー抽出部
２５６  第２の抽出部
２５７  第３の抽出部
２６１  移動対象フロー決定部
２６２  移動先経路候補取得部
２６３  品質推定部
２６４  経路変更判定部
２７０  経路情報送信部
３００  経路抽出装置
４００  パケット転送装置制御装置
【図１】
0005723806.tif 000002
【図２】
0005723806.tif 000003
【図３】
0005723806.tif 000004
【図４】
0005723806.tif 000005
【図５】
0005723806.tif 000006
【図６】
0005723806.tif 000007
【図７】
0005723806.tif 000008
【図８】
0005723806.tif 000009
【図９】
0005723806.tif 000010
【図１０】
0005723806.tif 000011
【図１１】
0005723806.tif 000012
【図１２】
0005723806.tif 000013
【図１３】
0005723806.tif 000014
【図１４】
0005723806.tif 000015