(57)【要約】【課題】トラヒック状況を考慮しつつネットワーク上の複数の伝送路間の大域的に負荷を分散する。【解決手段】データを伝送するネットワークシステムであって、伝送路で接続された複数の伝送装置を備え、前記各伝送装置は、入力されたデータを転送するために参照され、データの宛先のネットワーク宛に複数の伝送路を設定可能なルーティングテーブルを有し、フローネットワークグラフにおけるフロー最大化アルゴリズムを利用して、前記ネットワークシステムにおけるフロー制御範囲内の伝送路の帯域幅の制約又は前記伝送装置の処理能力の制約を満たすように算出されたルーティング設定が、前記ルーティングテーブルに設定されることを特徴とする。【選択図】図４
2016225729.tif 000002
【特許請求の範囲】
【請求項１】
データを伝送するネットワークシステムであって、
伝送路で接続された複数の伝送装置を備え、
前記各伝送装置は、入力されたデータを転送するために参照され、データの宛先のネットワーク宛に複数の伝送路を設定可能なルーティングテーブルを有し、
フローネットワークグラフにおけるフロー最大化アルゴリズムを利用して、前記ネットワークシステムにおけるフロー制御範囲内の伝送路の帯域幅の制約又は前記伝送装置の処理能力の制約を満たすように算出されたルーティング設定が、前記ルーティングテーブルに設定されることを特徴とするネットワークシステム。
【請求項２】
請求項１に記載のネットワークシステムであって、
前記ルーティングテーブルは、前記設定された複数の伝送路に出力するデータの量の比率を保持し、
前記伝送装置は、前記ルーティングテーブルに保持された比率に従って、一つのネットワーク宛のデータを前記複数の伝送路に分散して出力することを特徴とするネットワークシステム。
【請求項３】
請求項２に記載のネットワークシステムであって、
前記ルーティングテーブルに保持される比率は、前記フロー制御範囲に入力されるデータの量及び前記フロー制御範囲から出力されるデータの量に基づいて決定されることを特徴とするネットワークシステム。
【請求項４】
請求項１に記載のネットワークシステムであって、
前記複数の伝送装置を制御する制御装置を、前記伝送装置と別に備え、
前記制御装置は、
前記フロー制御範囲におけるトラヒックの状況に関する情報を収集し、
前記フロー最大化アルゴリズムを利用してルーティング設定を算出し、
前記算出したルーティング設定を前記伝送装置に出力することを特徴とするネットワークシステム。
【請求項５】
ネットワークシステムにおけるデータ転送制御方法であって、
前記ネットワークシステムは、伝送路で接続された複数の伝送装置と、前記複数の伝送装置を制御する制御部とを有し、
前記各伝送装置は、入力されたデータを転送するために参照され、データの宛先のネットワーク宛に複数の伝送路を設定可能なルーティングテーブルを有し、
前記方法は、
前記制御部が、フローネットワークグラフにおけるフロー最大化アルゴリズムを利用して、前記ネットワークシステムにおけるフロー制御範囲内の伝送路の帯域幅の制約又はルータの処理能力の制約を満たすようにルーティング設定を算出し、
前記伝送装置が、前記算出されたルーティング設定を前記ルーティングテーブルに設定することを特徴とするデータ転送制御方法。
【請求項６】
請求項５に記載のデータ転送制御方法であって、
前記ルーティングテーブルは、前記設定された複数の伝送路に出力するデータの量の比率を保持し、
前記方法は、前記伝送装置が、前記ルーティングテーブルに保持された比率に従って、一つのネットワーク宛のデータを前記複数の伝送路に分散して出力することを特徴とするデータ転送制御方法。
【請求項７】
請求項６に記載のデータ転送制御方法であって、
前記制御部は、前記ネットワークシステムにおけるフロー制御範囲に入力されるデータの量及び前記フロー制御範囲から出力されるデータの量に基づいて、前記ルーティングテーブルに保持される比率を決定することを特徴とするデータ転送制御方法。
【請求項８】
請求項５に記載のデータ転送制御方法であって、
前記ネットワークシステムは、前記制御部を有する制御装置を、前記伝送装置と別に備え、
前記方法は、
前記制御装置が、前記ネットワークシステムにおけるフロー制御範囲におけるトラヒックの状況に関する情報を収集し、
前記制御装置が、前記フロー最大化アルゴリズムを利用してルーティング設定を算出し、
前記制御装置が、前記算出したルーティング設定を前記伝送装置に出力することを特徴とするデータ転送制御方法。
【請求項９】
ネットワークシステムにおけるデータ転送を制御する制御装置であって、
前記ネットワークシステムは、伝送路で接続された複数の伝送装置を有し、
前記制御装置は、前記複数の伝送装置と接続されており、
前記各伝送装置は、入力されたデータを転送するために参照され、データの宛先のネットワーク宛に複数の伝送路を設定可能なルーティングテーブルを有し、
前記制御装置は、
フローネットワークグラフにおけるフロー最大化アルゴリズムを利用して、前記ネットワークシステムにおけるフロー制御範囲内の伝送路の帯域幅の制約又はルータの処理能力の制約を満たすようにルーティング設定を算出し、
算出したルーティング設定を、前記伝送装置が前記ルーティングテーブルに設定するために出力することを特徴とする制御装置。
【請求項１０】
請求項９に記載の制御装置であって、
前記ルーティングテーブルは、前記設定された複数の伝送路に出力するデータの量の比率を保持し、
前記制御装置は、前記ネットワークシステムにおけるフロー制御範囲に入力されるデータの量及び前記フロー制御範囲から出力されるデータの量に基づいて、前記ルーティングテーブルに保持される比率を決定し、
前記伝送装置は、前記ルーティングテーブルに保持された比率に従って、一つのネットワーク宛のデータを前記複数の伝送路に分散して出力することを特徴とする制御装置。
【請求項１１】
請求項９に記載の制御装置であって、
前記ネットワークシステムにおけるフロー制御範囲におけるトラヒックの状況に関する情報を収集し、
前記フロー最大化アルゴリズムを利用してルーティング設定を算出することを特徴とする制御装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データを転送するネットワークシステムに関する。
【背景技術】
【０００２】
電気通信ネットワークにおけるコンピュータ間のパケット伝送において、ネットワーク内のルータ（又は、ルータとしての機能を有する伝送装置。以下、単に「ルータ」と表記する。）は、保持するルーティングテーブルに登録されたルーティング設定に基づいて、パケットを転送する。パケットの転送の失敗や再送制御によるコストの発生を防ぐため、パケットロスが極力生じないようにルーティングを行うことが必要である。
【０００３】
各ルータが保持するルーティングテーブルにルーティング設定を登録する方法として、管理者が手動で登録する方法や、何らかのルーティングプロトコルを用いて自動で登録する方法がある。手動で登録する方法は、管理者の労力を要するという問題がある。特に、大規模なネットワークにおいてルーティング設定を登録したり、ネットワーク構成の変化や伝送路上での障害発生等に対応したりする場合に、問題が顕著である。一方、自動で登録する方法は、管理者の手を介さずルータが自律的にルーティングテーブルを生成するため、管理者の労力を要さないという利点がある。しかし、自動で登録する方法であっても、ルーティング設定は通常ネットワークのリンク状態等の静的な情報にのみ基づいて行われるため、トラヒック状況によっては必ずしも最適なルーティングができない場合がある。
【０００４】
このような問題に対して、ネットワークのトラヒック状況を考慮してルーティングを行う方法が提案されている。例えば、特表２００８−５２７９４１号公報（特許文献１）には、「各々がネットワークの物理リンクの少なくとも１つを経由する特定のルーティングに対応付けられた複数のトラフィック・フローを事前に定義するステップと、トラフィック・フローに従いルーティング・システムを構成するステップと、トラフィック・フローの少なくとも一部に送信されるトラフィックのデータを収集して、収集したデータに基づいてネットワーク内のフローの各々についてトラフィック統計を計算するステップと、計算したトラフィック統計を利用してルーティング・システムの構成を再計算するステップとを含むルーティング方法」が記載されている。また、特開２０１０−２３９４７３号公報（特許文献２）には、「同一通信先端末への複数の通信経路をルーティングテーブルに登録する通信経路登録部と、通信経路ごとに通信先端末までのパケット往復時間をルーティングテーブルに登録するＲＴＴ登録部と、パケット送信時に、パケット往復時間に基づいて通信経路を選択する通信経路選択部とを備える経路選択システム」が記載されている。
【０００５】
また、一般的なルーティングテーブルにおいては、各宛先アドレスに対して唯一つのルーティング設定しか登録できない。このため、一つの宛先へ至る伝送路が複数存在しても、実際の通信に用いられる経路は一つに限られて、一つの伝送路のみに負荷がかかり、その結果、負荷が当該伝送路の許容量を超過し、パケットの伝送に失敗するという問題がある。
【０００６】
このような問題に対して、複数の伝送路の間で負荷を分散するようにルーティングする方法が提案されている。例えば、特開２００６−１０９４５４号公報（特許文献３）には、「制御戦略を策定し、当該制御戦略に応じて制御戦略パラメータＵｔｉｌ＿ｗｅｉｇｈｔを生成し、ネットワーク状態に応じてネットワーク状態パラメータを生成し、制御戦略パラメータ、ネットワーク状態パラメータ、及びネットワーク・トポロジー情報に基づいて、経路選択の候補となる各経路の経路コストを計算し、選択候補経路のうち経路コストが最小となる経路を選択する方法」が記載されている。また、特開２００１−３２０４２０号公報（特許文献４）には、「インターネットプロトコルネットワークを構成する通信装置に設けられる装置であって、通信装置に接続された伝送経路のトラヒック特性を収集するトラヒック特性収集部と、収集されたトラヒック特性を他の通信装置に通知するトラヒック特性通知部と、収集されたトラヒック特性に基づいて負荷を演算する負荷演算部と、求められた負荷情報に基づいて伝送経路を追加するか削除するかの判定を行なう判定部と、求められた負荷を複数の伝送経路間で均等化する負荷均等化部とをそなえるように構成する伝送経路制御装置」が記載されている。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特表２００８−５２７９４１号公報
【特許文献２】特開２０１０−２３９４７３号公報
【特許文献３】特開２００６−１０９４５４号公報
【特許文献４】特開２００１−３２０４２０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
特許文献１及び特許文献２に記載された方法では、トラヒック状況を考慮して何らかの制御ポリシに基づいて最適と考えられる伝送路を求めている。しかしながら、これらの方法は伝送路間の負荷の分散は考慮されておらず、最適経路として算出された一つの伝送路のみに負荷が集中するという問題が生じる。
【０００９】
一方、特許文献３に記載された方法では、一つの伝送路のみに負荷が集中しないよう、複数の伝送路間で負荷を分散している。しかしながら、この方法では時々刻々と変化するトラヒック状況を考慮して伝送路が選択されておらず、トラヒック状況によっては小さい負荷の伝送路が選択されないという問題が生じる。
【００１０】
また、特許文献４に記載された方法では、トラヒック状況を考慮しつつ複数の伝送路間で負荷を分散している。しかしながら、この方法では通信の起点と終点との間の１対１の局所的なルーティングを最適化しているに過ぎず、ネットワーク全体における大域的な最適化するものではないという問題が生じる。
【００１１】
本発明は、このような課題に鑑み創案されたもので、トラヒック状況を考慮しつつネットワーク上の複数の伝送路間の大域的に負荷を分散することを目的とする。
【課題を解決するための手段】
【００１２】
本願において開示される発明の代表的な一例を示せば以下の通りである。すなわち、データを伝送するネットワークシステムであって、伝送路で接続された複数の伝送装置を備え、前記各伝送装置は、入力されたデータを転送するために参照され、データの宛先のネットワーク宛に複数の伝送路を設定可能なルーティングテーブルを有し、フローネットワークグラフにおけるフロー最大化アルゴリズムを利用して、前記ネットワークシステムにおけるフロー制御範囲内の伝送路の帯域幅の制約又は前記伝送装置の処理能力の制約を満たすように算出されたルーティング設定が、前記ルーティングテーブルに設定されることを特徴とする。
【発明の効果】
【００１３】
本発明の代表的な形態によれば、時々刻々と変化するトラヒック状況を考慮しつつネットワーク上の複数の伝送路間の大域的な負荷の均等化を動的に行うことができる。前述した以外の課題、構成及び効果は、以下の実施例の説明により明らかにされる。
【図面の簡単な説明】
【００１４】
【図１】第１の実施例が適用されるネットワークの構成を示す図である。
【図２】第１の実施例の各ルータにおけるルーティングテーブルの例を示す図である。
【図３】第１の実施例のルーティング計算処理の全体を示すフローチャートである。
【図４】第１の実施例が適用されたネットワークの構成を示す図である。
【図５】第１の実施例のコントローラの機能ブロック図である。
【図６】第１の実施例のルーティング計算部が実行する処理のフローチャートである。
【図７】ルーティング計算の手順において生成されるフローネットワークグラフを示す図である。
【図８Ａ】流入するトラヒック量及び流出するトラヒック量を示す図である。
【図８Ｂ】各辺の容量が決定されたフローネットワークグラフを示す図である。
【図９】フロー最大化アルゴリズムを適用して得られる最大フローを示す図である。
【図１０】フォード・ファルカーソンのアルゴリズムの擬似コードを示す図である。
【図１１】最大フローによるルーティングテーブルの更新を示す図である。
【図１２】第２の実施例が適用されるネットワークの構成を示す図である。
【図１３】変換後のフローネットワークグラフを示す図である。
【発明を実施するための形態】
【実施例１】
【００１５】
図１は、第１の実施例が適用されるネットワークの構成を示す図である。
【００１６】
図１に示すネットワークは、ルータ１０１、１０２、１０３が、伝送路で接続されて構成されている。ルータは、下流側ルータ１０１、上流側ルータ１０２、中間ルータ１０３の３種類に分類される。なお、ルータ１０１、１０２、１０３は、データを転送する伝送装置であって、ルータとしての機能を有すればよい。
【００１７】
ルータ１０１、１０２、１０３は、入力されたパケットの転送先を決定する転送制御部と、入力されたパケットの転送先を決定するために参照されるルーティングテーブル（図２参照）と、入力されたパケットを一時的に格納するパケットバッファと、パケットを入出力するインタフェースとを有する。
【００１８】
各伝送路には、図中に数値で示すように「帯域幅」が定められている。各伝送路の帯域幅の値は、パケットを伝送する際にその伝送路が用いられる優先度（ＯＳＰＦ（Open Shortest Path First）におけるコスト値に反比例する）を示す。一般的に、この帯域幅の値は各伝送路の実際の帯域幅と一致又は比例するが、管理者のポリシによって異なる値を指定して運用してもよい。また、伝送路の帯域幅の値は静的に定まっていなくても、トラヒック状況に応じて動的に変化してもよい。本実施例では、伝送路の帯域幅の値は実際の帯域幅と一致している。
【００１９】
本実施例による伝送路の計算は、ネットワーク全体のうち特定の範囲１００（例えば、図１において一点鎖線で囲った制御範囲）に適用される。本実施例による伝送路の計算は、下流側ルータと上流側ルータとを繋ぐ通信のみが行われる場合に最も効果的であるが、コアネットワークに適用することもできる。
【００２０】
以下、本実施例においては、下流側ルータから上流側ルータへと流れるパケットの伝送について示すが、逆方向のパケットを伝送する場合も同様に計算ができる。
【００２１】
図２は、第１の実施例の各ルータが有するルーティングテーブルの例を示す図である。
【００２２】
ルーティングテーブルは、宛先ネットワークアドレス２０２と転送先ルータ２０３との対応表２０１と、各転送先ルータへ転送するパケット量の比率２０４の二つの部分から構成される。対応表２０１は、一般的なルーティングテーブルと同じく、転送すべき各パケットの宛先ネットワークアドレス２０２と、当該パケットが出力される転送先ルータ２０３とを対応付ける。但し、本実施例のルーティングテーブルは、一般的なルーティングテーブルとは異なり、各宛先ネットワークアドレス２０２に対し転送先ルータ２０３を複数指定することができる。ここで複数指定した各転送先ルータへ転送するパケット量は、比率２０４で規定される。本実施例は、ネットワーク内の各ルータについて、図２に示すルーティングテーブルを計算し、最も好適な転送パケット量の比率でパケットを出力することを目的とする。この比率の算出方法については図１１を用いて後述する。
【００２３】
図３は、第１の実施例のルーティング計算処理の全体を示すフローチャートである。
【００２４】
初めに初期ルーティングを計算し、計算された初期ルーティングを各ルータに適用する（３０１）。初期ルーティングは、本発明によるルーティングの計算を実施するまでの間だけ仮に適用されるルーティングである。初期ルーティングは、既存のルーティングプロトコル（例えば、ＯＳＰＦの）を用いて計算することができる。その後、再ルーティングを行う契機毎に（３０２）、本実施例のルーティング計算を行い、計算されたルーティングを各ルータに適用する（３０３）。再ルーティングの契機は、ネットワークのトポロジの変化、トラヒック流量の閾値超過、一定時間の経過等、管理者が定めたポリシに従って設定することができる。
【００２５】
図４は、第１の実施例が適用されたネットワークの構成を示す図である。
【００２６】
図４に示すネットワークは、図１に示すネットワークにコントローラ４０１を追加したものである。コントローラ４０１は、対象とするネットワーク内の各ルータ１０１、１０２、１０３と、制御線４０２を介して通信可能である。制御線は、ネットワーク内の伝送路とは別の専用線を設けているが、ネットワーク内の伝送路（例えば、部分的な帯域）を利用してもよい。コントローラ４０１は、ルータと別個に設けられても、ルータの一つに実装されてもよい。
【００２７】
図５は、第１の実施例のコントローラ４０１の機能ブロック図である。
【００２８】
コントローラ４０１は、隣接関係収集部５０１、トラヒック状況収集部５０２、ルーティング計算部５０３及びルーティング適用部５０４を有する。
【００２９】
まず、隣接関係収集部５０１が、各ルータからルータ同士の隣接関係の情報を収集し、トラヒック状況収集部５０２が、各ルータからトラヒック状況を収集する。その後、隣接関係収集部５０１及びトラヒック状況収集部５０２が収集した情報に基づいて、ルーティング計算部５０３が最適なルーティング設定を算出する。そして、ルーティング適用部５０４が、算出したルーティング設定を各ルータに適用する。
【００３０】
図６は、第１の実施例のルーティング計算部５０３が実行する処理のフローチャートである。
【００３１】
ルーティング計算部５０３は、収集したルータ同士の隣接関係に基づいてフローネットワークグラフ（図７参照）を生成し（６０１）、収集したトラヒック状況に基づいて、当該フローネットワークグラフにおいて欠けている辺の容量を決定し（６０２）、得られたフローネットワークグラフにフロー最大化アルゴリズムを適用して（６０３）、各ルータのルーティングテーブルを各辺のフローで更新する（６０４）。
【００３２】
図７は、ルーティング計算の手順６０１において生成されるフローネットワークグラフを示す図である。
【００３３】
これは、ネットワーク（１００）における各ルータを頂点とし、ルータ間の伝送路を双方向の有向辺とし、各伝送路の帯域幅の値を有向辺の容量（重み）として得られる重み付き有向グラフに、新たな二つの頂点ｓ（７０１）及びｔ（７０２）と、新たな有向辺７０３及び有向辺７０４を付加したものである。有向辺７０３は、頂点ｓを始点とし、各下流側ルータ１０１を終点とする。有向辺７０４は、各上流側ルータ１０２を始点とし、頂点ｔを終点とする。図７において、各有向辺の容量を示した。各ノード間の伝送路の容量は、コントローラ４０１が各ノードから取得する隣接関係情報に含まれる。なお、有向辺７０３及び有向辺７０４の容量が示されていないが、これはルーティング計算の手順６０２において決定される。
【００３４】
フローネットワークグラフは、図示したように可視化されるが、計算機内では、例えば、頂点及び有向辺をオブジェクトで表したり、隣接行列（各行及び各列が頂点に対応し、各成分に有向辺の情報が格納された行列）の形で表したりすることができる。
【００３５】
図８Ａ、図８Ｂは、ルーティング計算の手順６０２において、フローネットワークグラフの辺の容量を決定する方法を示す図である。
【００３６】
図８Ａは、ある時点において収集されたトラヒック状況（単位時間において下流側ノードに流入するトラヒック量の実測値及び上流側ノードから流出するトラヒック量の実測値）を示す。このとき、図８Ｂに示すように、対応するフローネットワークグラフにおける各有向辺７０３の容量は、その終点たる下流側ルータ１０１へと単位時間に流入するトラヒックの総量を設定する。また、各有向辺７０４の容量は、その始点たる上流側ルータ１０２より単位時間に流出するトラヒックの総量を設定する。こうして得られた図８Ｂは、各ルータや伝送路に流すことができるトラヒック量の制約をフローネットワークグラフの辺の容量の形に変換したものとなる。
【００３７】
図９は、ルーティング計算の手順６０３において、フロー最大化アルゴリズムを適用して得られる最大フローを示す図である。
【００３８】
フロー最大化アルゴリズムは、トラヒック量の制約の範囲内で限界まで増やしたトラヒック量を計算するアルゴリズムであり、図９のフロー図には、「最大フロー値／容量」の形式で各伝送路のトラヒック量を記載する。フロー最大化アルゴリズムは、典型的には、フォード・ファルカーソンのアルゴリズムが用いられる。図１０に、フォード・ファルカーソンのアルゴリズムの擬似コードを示す。なお、図１０の擬似コードでは第３行から第５行においてフロー関数ｆの値を全て０に初期化しているが、代わりに同アルゴリズムの前回実行時の結果を用いて初期値を生成してもよい。
【００３９】
図１１は、ルーティング計算の手順６０４において、最大フローによるルーティングテーブルの更新を示す図であり、図９に示すような最大フローのうちの或る一部分のみを例示的に抜き出して示した図である。以下、図１１におけるルータＡ（１１０１）のルーティングテーブル（図２）を生成する方法を示す。なお、図１１において、「最大フロー値／容量」の形式で各伝送路のトラヒック量を記載する。
【００４０】
まず、ルーティングテーブルの各宛先ネットワークアドレス２０２に対し、ルータＡ（１１０１）の転送先である（図１１においてルータＡ（１１０１）からフローが伸びている先の）ルータ１１０２のうち、宛先ネットワークへと至る経路を有するルータを転送先ルータ２０３に設定して、対応表２０１を生成する。例えば、ネットワーク１７２．２１．１．０／２４を宛先とするパケットは、ルータＢ又はルータＣへ転送するという対応付けを対応表２０１に設定する。また、ルータＡ（１１０１）の転送先である各ルータ１１０２の最大フローの量の比率を計算し、計算された最大フローの量の比率を比率２０４に設定する。以上の手順によって、ルータＡ（１１０１）のルーティングテーブルを生成することができる。
【００４１】
実際に、ルータＡが他のルータから受信したパケットを転送する際には、まず、そのパケットの宛先ＩＰアドレスと対応表２０１を参照して、転送先ルータの一覧を求める。その後、求めた転送先ルータの一つを比率２０４で規定される比率でランダムに選択して転送する。例えば、宛先ＩＰアドレスが１９２．１６８．２．５であるパケットを受信した場合、まず、宛先ＩＰアドレス１９２．１６８．２．５を含むネットワーク１９２．１６８．２．０／２４に対応する転送先（ルータＢ、ルータＣ）を求める。比率２０４を参照すると、ルータＢとルータＣへ転送するパケット量の比率は２５：１５であるから、乱数を用いて４０分の２５の確率でルータＢへ、４０分の１５の確率でルータＣへとランダムにパケットを転送する。フロー最大化アルゴリズムによって求められる最大フロー（図９）は、その時点のトラヒック状況において最も多くのパケットを流すことができる伝送路を表すので、この方法によりパケットロスが最も少ない伝送路を求めることができる。
【００４２】
以上に説明したように、本発明の第１の実施例によると、各ルータが保持するルーティングテーブルは、データの宛先となる一つのネットワーク宛に複数の伝送路を設定可能としたので、時々刻々と変化するトラヒック状況を考慮しつつネットワーク上の複数の伝送路間で負荷を分散することができる。これにより、特定の伝送路に負荷が集中し許容量を超過することを防ぎ、ネットワークに生じるパケットロスを低減することができる。
【００４３】
また、ルーティングテーブルには、フローネットワークグラフにおけるフロー最大化アルゴリズムを利用して、ネットワークシステムにおけるフロー制御範囲内の伝送路の帯域幅の制約を満たすように算出されたルーティング設定が設定されるので、ネットワーク全体における大域的に最適な伝送路を各ルータのルーティング設定に動的に反映し、効率的にパケットを分散することができる。
【００４４】
また、ルーティングテーブルは、複数の伝送路に出力するデータの量の比率を保持し、ルータは、ルーティングテーブルに保持された比率に従って、一つのネットワーク宛のデータを複数の伝送路に分散して出力するので、各伝送路の能力に合わせて、出力されるパケットの量を最適化し、パケットを分散して効率的に転送することができる。
【００４５】
また、ルーティングテーブルに保持される比率は、フロー制御範囲に入力されるデータの量及びフロー制御範囲から出力されるデータの量に基づいて決定されるので、入力回線及び出力回線のトラヒックの状況に応じて、各回線の転送量を定めることができる。
決める→比率
【００４６】
また、複数の伝送装置を制御するコントローラをルータと別に設け、コントローラが、フロー制御範囲におけるトラヒックの状況に関する情報を収集し、フロー最大化アルゴリズムを利用してルーティング設定を算出し、ルータに出力するので、現在のトラヒック状況に合わせて一元的に転送量を最適化することができる。また、転送リソースと制御リソースを分けて、統計情報の収集及び伝送路の算出のために生じる計算や、コントローラとルータとの間の通信によって、データ転送のためのリソースが消費され、伝送されるべきトラヒックが阻害されることを防ぐことができる。
【実施例２】
【００４７】
第１の実施例では、ネットワーク内の各伝送路の帯域幅に制約がある例を示したが、本発明は各ルータの処理能力に制約がある場合にも適用可能である。第２の実施例では、各ルータの処理能力に制約がある例を示す。なお、第２の実施例において、簡単のため各伝送路における帯域幅には制約がない例を示すが、各伝送路の帯域幅に制約があり、かつ各ルータの処理能力に制約がある場合についても同様に、本発明を適用可能である。
【００４８】
図１２は、第２の実施例が適用されるネットワークの構成を示す図である。
【００４９】
図１２に示すネットワークは、第１の実施例が適用されるネットワーク（図１）と同様に、ルータ１０１、１０２、１０３が、伝送路で接続されて構成されており、各伝送路に帯域幅が設定される代わりに各ルータに処理能力の制約が設定されている。
【００５０】
この場合、ルーティング計算の手順６０１で、フローネットワークグラフを生成する際、各ルータをフローネットワークグラフの頂点として取り扱う際に変換が必要である。図１３は、変換後のフローネットワークグラフを示す。図１３に示すように、ネットワークの各ルータは、辺の始点のみを集めた頂点と終点のみを集めた頂点の二つに分割される。そして、二つの頂点の間を１本の有向辺で結び、ルータの処理能力を有向辺の重みとする。
【００５１】
フローネットワークグラフの生成以外については、前述した第１の実施例と同様の処理によって好適なパケットの伝送路を求めることができる。
【００５２】
以上に説明したように、本発明の第２の実施例によると、ルーティングテーブルには、フローネットワークグラフにおけるフロー最大化アルゴリズムを利用して、ネットワークシステムにおけるフロー制御範囲内のルータの処理能力の制約を満たすように算出されたルーティング設定が設定されるので、ネットワーク全体における大域的に最適な伝送路を各ルータのルーティング設定に動的に反映し、効率的にパケットを分散することができる。
【００５３】
なお、本発明は前述した実施例に限定されるものではなく、添付した特許請求の範囲の趣旨内における様々な変形例及び同等の構成が含まれる。例えば、前述した実施例は本発明を分かりやすく説明するために詳細に説明したものであり、必ずしも説明した全ての構成を備えるものに本発明は限定されない。また、ある実施例の構成の一部を他の実施例の構成に置き換えてもよい。また、ある実施例の構成に他の実施例の構成を加えてもよい。また、各実施例の構成の一部について、他の構成の追加・削除・置換をしてもよい。
【００５４】
また、前述した各構成、機能、処理部、処理手段等は、それらの一部又は全部を、例えば集積回路で設計する等により、ハードウェアで実現してもよく、プロセッサがそれぞれの機能を実現するプログラムを解釈し実行することにより、ソフトウェアで実現してもよい。
【００５５】
各機能を実現するプログラム、テーブル、ファイル等の情報は、メモリ、ハードディスク、ＳＳＤ（Solid State Drive）等の記憶装置、又は、ＩＣカード、ＳＤカード、ＤＶＤ等の記録媒体に格納することができる。
【００５６】
また、制御線や情報線は説明上必要と考えられるものを示しており、実装上必要な全ての制御線や情報線を示しているとは限らない。実際には、ほとんど全ての構成が相互に接続されていると考えてよい。
【符号の説明】
【００５７】
１０１  下流側ルータ
１０２  上流側ルータ
１０３  中間ルータ
２０１  ルーティングテーブルの対応表
２０４  ルーティングテーブルの転送比率
４０１  コントローラ
５０１  隣接関係収集部
５０２  トラヒック状況収集部
５０３  ルーティング計算部
５０４  ルーティング適用部
【図１】
2016225729.tif 000003
【図２】
2016225729.tif 000004
【図３】
2016225729.tif 000005
【図４】
2016225729.tif 000006
【図５】
2016225729.tif 000007
【図６】
2016225729.tif 000008
【図７】
2016225729.tif 000009
【図８Ａ】
2016225729.tif 000010
【図８Ｂ】
2016225729.tif 000011
【図９】
2016225729.tif 000012
【図１０】
2016225729.tif 000013
【図１１】
2016225729.tif 000014
【図１２】
2016225729.tif 000015
【図１３】
2016225729.tif 000016