(57)【要約】【課題】より多くのフローの帯域をパスへ割り当てる際、転送装置及びポートフローの最適な組み合わせを求めることができるパス割当方法を提供する。【解決手段】本発明によるパス割り当て方法は、転送装置から、当該転送装置の出力ポートを経て、当該出力ポートに接続されたパスヘ流れるフローの帯域の合計値が、当該出カポートの容量を超えず、転送装置へ、当該転送装置の入力ポートを経て、当該入力ポートに接続されたパスから流れてくるフローの帯域の合計値が、当該入力ポートの容量を超えず、パスは同一容量の出力ポートと入力ポートのみを接続する、という条件を満たしつつ、ネットワーク全体において、全てのパスを流れている全てのフローの帯域の合計が最も大きくなるように、転送装置のポートとパスとの接続関係、及びパスへのフローの割当関係を規定することを特徴とする。【選択図】        図１
2004260334.tif 000002
【特許請求の範囲】
【請求項１】
有限個の出力ポート及び入力ポートを有する有限個の転送装置が存在し、ある転送装置の１つの出力ポートと別の転送装置の１つの入力ポートとを接続して出力ポートから入力ポートへフローを流すパスを設定することにより構築されるネットワークのパス割り当て方法において、
各々のポートには転送可能な有限の容量が規定され、出力ポートと入力ポートとを接続するパスには転送可能な有限の容量が規定され、パスの容量は出力ポートの容量と入力ポートの容量のいずれか大きい容量と同一とし、転送装置の出力ポートから、当該出力ポートに接続されたパスを介して、別の転送装置の入力ポートヘ流れるフローが有限個あり、各々のフローには有限の帯域が規定され、パスを流れるフローの帯域が当該パスの容量と等しいかそれよりも小さい場合にはフローがパスを流れることができ、それ以外の場合にはフローがパスを流れることができず、ある複数のフローの組合せの帯域の合計値がパスの容量と等しいかそれよりも小さい場合には当該複数のフローの組合せがパスを流れることができ、それ以外の場合には複数のフローの組合せがパスを流れることができない制約下において、
転送装置から、当該転送装置の出力ポートを経て、当該出力ポートに接続されたパスヘ流れるフローの帯域の合計値が、当該出カポートの容量を超えず、
転送装置へ、当該転送装置の入力ポートを経て、当該入力ポートに接続されたパスから流れてくるフローの帯域の合計値が、当該入力ポートの容量を超えず、
パスは同一容量の出力ポートと入力ポートのみを接続する、
という条件を満たしつつ、
ネットワーク全体において、全てのパスを流れている全てのフローの帯域の合計が最も大きくなるように、転送装置のポートとパスの接続関係、および、パスへのフローの割当関係を規定することを特徴とするパス割り当て方法。
【請求項２】
請求項１に記載のパス割り当て方法において、前記転送装置、転送装置が具える入出力インタフェース数及びその容量、転送装置間のフロー容量、インタフェースとパスとの関係、及びパスとフローとの関係を有限集合として明示的に規定して、請求項１において規定した条件を線形関数で表し、ネットワーク全体において、全てのパスを流れている全てのフローの帯域の合計を有限集合の値を組み合わせて算出する線形関数を有することを特徴とするネットワークのパス割り当て方法。
【請求項３】
請求項１に記載のネットワークのパス割り当て方法により規定されたパスの割当を計算し、計算されたパスの割当をネットワークの各転送装置へ設定することによりネットワークのパス割り当てを実行するパス制御サーバであって、
請求項２に記載の線形関数をプログラムとして保持し、
前記転送装置数、転送装置が具える入出力インタフェース数及び容量、転送装置間のフロー容量の各値を入力することにより、前記プログラムが有限集合の取り得る値の範囲を規定し、条件を表した線形関数を用い、当該条件を満たす範囲内で、前記有限集合の値を変化させて種々の値の組み合わせを作成し、目的を表した線形関数を用い、値の組み合わせが表す目的の状態の値を算出し、前記種々の値の組み合わせの中から最適を状態を与える目的値を求め、出力した値に基づいてパスとインタフェースとの接続関係及びパスとフローとの対応関係を求め、求めた関係を各転送装置に設定してネットワークのパス割当を制御することを特徴とするパス制御サーバ。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ネットワーク内のフローを効率よく収容するパス割り当て方法、特にフォトニック転送技術によって構築された大規模ネットワークにおいて効率的にパス配置を算出する場合に最適なパス割り当て方法に関するものである。
【０００２】
【従来の技術】
従来のネットワーク内のフローを収容するパス設計方法の例として、近似解法の１つである欲張り法が考えられる。欲張り法については、２０００年１月に電子情報通信学会から発行された電子情報通信学会論文誌Ｄ−Ｉ  Ｖｏ１．Ｊ８３−Ｄ−Ｉ  Ｎｏ．１の第３頁から第２５頁に掲載された「組合せ最適化問題に対するメタ戦略について」と題する論文に記載されている。
【０００３】
その論文の第６頁２．２によれば、欲張り法は、目的関数への頁献度を示す局所的な評価値に基づいて、実行可能解を直接構成する方法である。欲張り法をパス設計に適用すると、フローを帯域によって降順に並べ、上位のフローから順にフローの帯域とパスの容量とを比較し、フローの帯域がパスの容量以下である場合に、フローをパスヘ割り当て、割り当てられたパスから順に転送装置のポートへ割り当てることを繰り返し、フローの帯域がパスの容量よりも大きくなったとき、割り当てを終了するよう構成されている（例えば、非特許文献１参照）。
【０００４】
【非特許文献１】
電子情報通信学会論文誌、ＶＯＬ．Ｊ８３−Ｄ−１、２０００年１月、３−２５頁  「組合せ最適化問題に対するメタ戦略について」
【０００５】
【発明が解決しようとする課題】
従来の方式の第１の問題点は、最適なパス割り当てが出来ないということである。その理由は、フローの帯域の大きなものから順に割り当てを考えるため、割り当て対象となったフローの帯域がパスの容量よりも大きいため、割り当てを終了した場合に、割り当て対象のフローよりも帯域が小さいフローの帯域がパスの容量と等しいか小さく、パスヘ割り当てることができる可能性が無視されているためである。
【０００６】
従来の方式の第２の問題点は、パス割り当て方法に対するさまざまな解法を試み、適応性を検証することが難しいということである。その理由は、欲張り法を前提とした動作の設計を行っているため、そのほかの解法の適用が適さないためである。
【０００７】
本発明の第１の目的は、より多くのフローの帯域をパスへ割り当てる際、転送装置及びポートフローの最適な組み合わせを求めることができるパス割当方法を提供することにある。
本発明の第２の目的は、従来の方式の１つである欲張り法による最適ではないパス割り当てを改善するため、欲張り法以外のさまざまな解法を適用することができるパス割り当て方法を提供することにある。
【０００８】
【課題を解決するための手段】
本発明によるネットワークのパス割り当て方法は、有限個の出力ポート及び入力ポートを有する有限個の転送装置が存在し、ある転送装置の１つの出力ポートと別の転送装置の１つの入力ポートとを接続して出力ポートから入力ポートへフローを流すパスを設定することにより構築されるネットワークのパス割り当て方法において、
各々のポートには転送可能な有限の容量が規定され、出力ポートと入力ポートとを接続するパスには転送可能な有限の容量が規定され、パスの容量は出力ポートの容量と入力ポートの容量のいずれか大きい容量と同一であり、転送装置の出力ポートから、当該出力ポートに接続されたパスを介して、別の転送装置の入力ポートヘ流れるフローが有限個あり、各々のフローには有限の帯域が存在し、パスを流れるフローの帯域が当該パスの容量と等しいかそれよりも小さい場合にはフローがパスを流れることができ、それ以外の場合にはフローがパスを流れることができず、ある複数のフローの組合せの帯域の合計値がパスの容量と等しいかそれよりも小さい場合には当該複数のフローの組合せがパスを流れることができ、それ以外の場合には複数のフローの組合せがパスを流れることができない制約下において、
転送装置から、当該転送装置の出力ポートを経て、当該出力ポートに接続されたパスヘ流れるフローの帯域の合計値が、当該出カポートの容量を超えず、
転送装置へ、当該転送装置の入力ポートを経て、当該入力ポートに接続されたパスから流れてくるフローの帯域の合計値が、当該入力ポートの容量を超えず、
パスは同一容量の出力ポートと入力ポートのみを接続する、
という条件を満たしつつ、
ネットワーク全体において、全てのパスを流れている全てのフローの帯域の合計が最も大きくなるように、転送装置のポートとパスの接続関係、および、パスへのフローの割当関係を規定することを特徴とする。
【０００９】
本発明によるパス割り当て方法は、パス割り当て方式の設計と定式化からなり、従来技術とは、線形計画の解法を適用できるように方式を設計し定式化した点が異なる。本発明においては、線形計画の枠組みに沿って、パス割り当てにおける前提を定義し、充足すべき制約を示し、達成すべき目的を示すことによりパス割り当て方法を規定している。これにより、ネットワークを構築する際のパス割り当て設計において、線形計画に対する全ての解法を適用することができ、パス割り当ての最適性を改善することができる。
また、転送装置のポート容量を与えるだけで、転送装置間の出力ポートと入力ポートとの最適な接続関係、および、リンクに対するフローの最適な割当関係を求めることができるため、網設計者の作業を削減することができる。
【００１０】
【発明の実施の形態】
次に、本発明の実施の形態について数式を参照して詳細に説明する。
数１は、本発明の基本概念に基づき、線形計画の枠組みに沿って、パス割り当て方式を定式化したものである。数１は、値を最大化することを目的とする目的関数１０００と、目的関数を最大化する際の変数の範囲を制約するための制約式１００１、１００２、１００３、１００４、１００５からなる。数１は、それぞれ次のように規定されている。
【数１】
2004260334.tif 000003
【００１１】
変数は、ｎ台の転送装置からなる有限集合Ｎ、ｍｎ（ｎ−１）通りのフローからなる有限集合Ｍ（１台の転送装置当りｍ通りのフローが発生するとする）、転送装置ｉのｌ通りの出力ＩＦからなる有限集合Ｌｉ、転送装置ｊのｐ通りの入力ポートからなる有限集合Ｇｉ、転送装置ｉ（ｉ∈Ｎ）から転送装置ｊ（Ｇ∈Ｎ）へ向かうｋ番目（ｋ∈Ｍ）のフロー帯域ｆｉｊｋ、転送装置ｉのｌ番目の出力ポートであるＩＦ ＯＵＴｉｌの容量ｉｆ ｏｕｔｉｌ、転送装置ｊのｐ番目の入力ポートであるＩＦ ＩＦｉｐの容量ｉｆ ｉｎｉｐ、転送装置ｊのｉｆ ｏｕｔｉｌと転送装置ｊのｉｆ ｉｎｉｐ間にパスを張るとき１とし、張らないとき０とする０−１変数ｘｉｌｊｐ、フローｆｉｊｋがパスを通るとき１とし、通らないとき０とする０−１変数ｙｉｊｋのように設計されている。
【００１２】
制約式１００１は、転送装置ｉから出力ポートＩＦ ＯＵＴｉｌを使ってパスヘ出力するフローの帯域の合計がｉｆ ｏｕｔｉｌを超えないという制約条件を満たすために設計されている。
制約式１００２は、転送装置ｉにＩＦ ＩＮｊｐを使ってパスから入力するフローの帯域の合計がｉｆ ｉｎｊｐを超えないという制約条件を満たすために設計されている。
制約式１００３は、パスは同じ容量のＩＦ ＯＵＴとＩＦ ＩＮを通るという制約条件を満たすために設計されている。
制約式１００４は、０もしくは１のみをとることができるという０−１変数ｘｉｌｊｐの性質を表すために設計されている。
制約式１００５は、０もしくは１のみをとることができるという０−１変数ｙｉｌｊｐの性質を表すために設計されている。
目的関数１０００は、制約式１００１、１００２、１００３、１００４、１００５を満たす条件の下で、パスを通るフロー帯域の合計を最大にするようにＭからフローを選択することを示すために設計されている。
【００１３】
次に、具体的な実施例を用いて本実施例の動作を説明する。
図１は、本発明が適用されるネットワーク形態の一例である。ネットワーク中には、例えば転送装置１、２、３が存在し、転送装置１は出力ポート１０１、１０２、１０３、および、入力ポート１１１、１１２、１１３を持ち、転送装置２は出力ポート２０１、２０２、２０３、および、入力ポート２１１、２１２、２１３を持ち、転送装置３は出力ポート３０１、３０２、３０３、および、入力ポート３１１、３１２、３１３を持つ。
【００１４】
表１は、各転送装置の出力ポートの容量の一例である。
【表１】
2004260334.tif 000004
表１において、ｉｆ ｏｕｔｉｌは、転送装置ｉのｌ番目の出力ポートであるＩＦ ＯＵＴｉｌの容量を示している。例えば、ｉｆ ｏｕｔｌｌは転送装置１の１番目の出力ポートＩＦ ＯＵＴｌｌの容量を示しており、表１によりその値は例えば１０とする。
【００１５】
表２は、各転送装置の入力ポートの容量の一例である。
【表２】
2004260334.tif 000005
表２において、ｉｆ ｉｎｉｐは、転送装置ｊのｐ番目の入力ポートであるＩＦ ＩＦｉｐの容量を示している。例えば、ｉｆ ｉｎｌｌは、転送装置１の１番目の入力ポートであるＩＦ ＩＦｌｌの容量を示しており、表２によりその値は１０である。
【００１６】
表３は、各転送装置間に流れるフローの帯域の一例である。
【表３】
2004260334.tif 000006
表３において、ｆｉｊｋは、転送装置ｉから転送装置ｊへ向かうｋ番目のフロー帯域を示している。例えば、ｆ１２１は転送装置１から転送装置２へ向かう１番目のフロー帯域を示しており、表３によりその値は９である。
【００１７】
表４は、数２〜数７及び表１〜表３を基に、線形計画の解法の１つである単体法を適用した結果、図２のように得られる各パスにそれぞれ割り当てられるフローの帯域を示す。また、全てのパスの割当帯域の合計値である目的関数値も示す。例えば、図２より、パス４００は転送装置１と転送装置２とを接続し、表４により当該パスの割り当て帯域は１０となる。また、目的関数値は３８である。
【表４】
2004260334.tif 000007
【００１８】
表５は、数２〜数７及び表１〜表３に基づいて、欲張り法を適用した結果、図３のように得られる各パスにそれぞれ割り当てられるフローの帯域を示す。また、全てのパスの割当帯域の合計値である目的関数値も示す。例えば、図３より、パス４０４は転送装置１と転送装置２とを接続し、表５により当該パスの割り当て帯域は１０となる。また、目的関数値３０である。
【表５】
2004260334.tif 000008
【００１９】
図１のネットワークに数１に規定する各制約式を適用した場合、以下のように展開される。
式１０００は、数２のように展開される。
【数２】
2004260334.tif 000009
式１００１における、転送装置１から転送装置２へ向かうフローに関する式は、数３のように展開される。
【数３】
2004260334.tif 000010
式１００２における、転送装置１から転送装置２へ向かうフローに関する式は、数４のように展開される。
【数４】
2004260334.tif 000011
１００３における、転送装置１の１番目の出力ポートＩＦ ＯＵＴｌｌに関する式は、数５のように展開される。
【数５】
2004260334.tif 000012
式１００４は数６のように展開される。
【数６】
2004260334.tif 000013
式１００５は数７のように展開される。
【数７】
2004260334.tif 000014
【００２０】
数２〜数７および表１〜表３を基に、線形計画の解法の１つである単体法を適用すると、図２のように転送装置間にパスが設定され、各パスに割り当てられるフローの帯域は表４のようになり、目的関数値であるフロー帯域の合計は３８となる。
【００２１】
一方、数２〜数７および表１〜表３を基に、欲張り法を適用すると、図３のように転送装置間にパスが設定され、各パスに割り当てられるフローの帯域は表５のようになり、目的関数値であるフロー帯域の合計は３０となり、線形計画の解法を用いる場合に比べて一層小さい値である。
【００２２】
さらに、同様の手順で、数２〜数７および表１〜表３を基に、任意の線形計画の解法を適用し、パスの配置およびフローの帯域並びに目的関数値を求めることもできる。
【００２３】
また、同様の手順で、任意のネットワーク形態におけるパス割り当て方式を、線形計画の枠組みに沿って、例えば数２〜数７および表１〜表３のように展開し、全ての線形計画の解法を適用し、パス配置およびフローの帯域および目的関数値を比較評価することができるため、ネットワーク形態に適した解法を選択することができ、よって、パス割り当ての最適性を改善することができる。
【００２４】
計算されたパスの配置は、ネットワークのパスを制御するパス制御サーバが、転送装置のパス転送テーブルの値を設定することによりネットワーク内に設定される。パス制御サーバとネットワークとの接続関係を図４に示す。例えば、パス４０１を設定し、フローｆ１２１をパス４０１に流す場合、パス制御サーバは、転送装置１のパス転送テーブルを表６のように設定する。パスの計算からパス設定までのパス制御サーバの動作は以下の通りである。
パス制御サーバにおいてパスの計算を行う場合、パス制御サーバは、数１を表現したプログラムと表１〜３を表現するデータベースを有する。計算から設定までのパス制御サーバの動作は、（１）オペレータ等から、表１〜表３のデータを取得し、（２）プログラムにより最大の目的関数を求め、（３）当該目的関数値が表すパスの配置を求め、（４）当該パスを終端する転送装置のパス転送テーブルを設定してネットワーク内にパスを設定する。パス制御サーバの機能ブロックを図５に示す。
【表６】
2004260334.tif 000015
【００２５】
パスの計算は、上述したようにパス制御サーバにおいて行ってもよく、又はオペレータやパス制御サーバとは別の計算サーバが計算した結果をパス制御サーバに投入してパス設定を行うことができる。パス制御サーバが計算を行わない場合、上記（１）、（２）及び（３）の動作をオペレータや別の計算サーバが行い、パス制御サーバにはパス配置が入力され、パス制御サーバは（４）の動作を行うことができる。
【００２６】
【発明の効果】
本発明の効果は、ネットワーク形態に適した解法を選択ことによって、パス割り当ての最適性を改善することができることにある。その理由は、本発明の手順にしたがうことで、任意のネットワーク形態におけるパス割り当て方式を、線形計画の枠組みに沿って、例えば数２〜数７および表１〜表３のように展開することができるため、さまざまな線形計画の解法を適用し、パス配置およびフローの帯域および目的関数値を比較評価することができるためである。
【図面の簡単な説明】
【図１】パスが設定される前の本発明によるネットワーク形態の一例を示す線図である。
【図２】本発明によるネットワークのパス割り当て方法により構築されたネットワーク形態を示す線図である。
【図３】従来の欲張り法により構築されたネットワーク形態を示す線図である。
【図４】パス制御サーバとネットワークとの間の接続配置を示す図である。
【図５】パス制御サーバの機能ブロックを示す図である。
【符号の説明】
１，２，３  転送装置
１０１，１０２，１０３，２０１，２０２，２０３，３０１，３０２，３０３  出力ポート
１１１，１１２，１１３，２１１，２１２，２１３，３１１，３１２，３１３  入力ポート
【図１】
2004260334.tif 000016
【図２】
2004260334.tif 000017
【図３】
2004260334.tif 000018
【図４】
2004260334.tif 000019
【図５】
2004260334.tif 000020