(57)【要約】【課題】  少ないインタフェース数で１対１および多対多のパス割当てを実現すること。【解決手段】  ノード間を流れるトラヒック量を格納するトラヒックテーブル１０８を記憶し、前記トラヒックテーブル１０８を参照して、各ノード間の双方向のトラヒック量のうち多い方のトラヒック量を基準として、すべての帯域を利用する条件の下でできるだけ多くの１対１パスの割当てを行い、前記割当てで割当て切れなかった残余のトラヒックについて、ノード間ごとに双方向の残余トラヒックの和を計算して、前記トラヒックテーブル１０８を更新し、残余トラヒックの和を参照して、多対多パスの帯域をちょうど利用するような前記残余トラヒックの和の組合せを探索し、前記組合せに対応するノード間に多対多パスを割当てる。【選択図】      図１
2006295627.tif 000002
【特許請求の範囲】
【請求項１】
記憶手段と演算手段を備えた計算機が実行するパス配置方法であって、
前記記憶手段が、ノード間を流れるトラヒック量を格納するトラヒックテーブルを記憶し、
前記演算手段が、前記トラヒックテーブルを参照して、各ノード間の双方向のトラヒック量の中で多い方のトラヒック量を基準として、割当てる１対１パスのすべての帯域を利用する条件の下でできるだけ多くの１対１パスの割当てを行い、
前記割当てで割当てることのできなかった残余トラヒックを示すように前記トラヒックテーブルを更新し、
前記トラヒックテーブルに記録された残余トラヒックから同じノードペア間を流れる双方向の残余トラヒック量の和を求め、
前記双方向の残余トラヒック量の和の値を用いて、ノードペアの組合せに含まれるノードペア間で和をとった累積和の値を求め、
前記累積和の値を用いて、前記ノードペアの組合せの中で多対多パスに収容できるトラヒック量の上限値を下回り、かつ、最も上限値に近い値となる組合せを探索し、
前記組合せに対応するノード間に前記多対多パスを割当て、
前記組合せに含まれるノードペア間に流れる前記双方向の残余トラヒックを前記割当てた多対多パスに収容すること
を特徴とするパス配置方法。
【請求項２】
記憶手段と演算手段を備えた計算機が実行するパス配置方法であって、
前記記憶手段が、ノード間を流れるトラヒック量を格納するトラヒックテーブルを記憶し、
前記演算手段が、前記トラヒックテーブルを参照して、各ノード間の双方向のトラヒック量のうち、多い方のトラヒック量を基準として、割当てる１対１パスのすべての帯域を利用する条件の下でできるだけ多くの１対１パスの割当てを行い、
前記割当てで割当てることのできなかった残余トラヒックを示すように前記トラヒックテーブルを更新し、
前記トラヒックテーブルに記録された残余トラヒックから同じノードペア間を流れる双方向の残余トラヒック量の和を求め、
前記残余トラヒック量の和が０より大きく、かつ、最小となる条件を満たすノードペアを探索し、
前記ノードペアが配置する多対多パスの対地となり、かつ、前記ノードペア間を流れる双方向トラヒックを前記多対多パスに収容する条件の下で求めた前記多対多パスの対地のノードと前記多対多パスの対地でないノードの間を流れる残余トラヒックのうち、
前記多対多パスに収容できる前記残余トラヒックの数が最も多く、かつ、前記トラヒックにおける各方向に流れる残余トラヒック量の和の値と前記多対多パスに収容したトラヒック量の累積和が最小となり、かつ、前記残余トラヒック量の和と前記累積和との和が前記多対多パスで収容できるトラヒック量の上限値を下回るという条件を満たす前記対地でないノードを選択し、
前記ノードと前記多対多パスの対地との間を通る残余トラヒックのうち、前記累積和の計算で使用された残余トラヒックを前記多対多パスに収容し、
前記ノードを前記多対多パスの対地の一部として選択することで、前記多対多パスの対地と収容するトラヒックとを決定すること
を特徴とするパス配置方法。
【請求項３】
記憶手段と演算手段を備えた計算機が実行するパス配置方法であって、
前記記憶手段が、ノード間を流れるトラヒック量を格納するトラヒックテーブルを記憶し、
前記演算手段が、前記トラヒックテーブルを参照して、各ノード間の双方向のトラヒック量のうち、多い方のトラヒック量を基準として、割当てる１対１パスのすべての帯域を利用する条件の下でできるだけ多くの１対１パスの割当てを行い、
前記割当てで割当てることのできなかった残余トラヒックを示すように前記トラヒックテーブルを更新し、
前記トラヒックテーブルに記録された残余トラヒックを参照して、同じノードペア間を流れる双方向の残余トラヒック量のうち、量の多い方のトラヒック量の値を選択し、
前記多い方のトラヒック量の値を用いて組合せに含まれるノードペアの間で和をとった値が、多対多パスに収容できるトラヒック量の上限値を下回り、かつ、最も上限値に近い値となる条件を満たす組合せを探索し、
前記組合せに対応するノード間に前記多対多パスを割当て、
前記組合せに含まれるノードペア間を流れる双方向トラヒックを前記割当てた多対多パスに収容すること
を特徴とするパス配置方法。
【請求項４】
記憶手段と演算手段を備えた計算機が実行するパス配置方法であって、
前記記憶手段が、ノード間を流れるトラヒック量を格納するトラヒックテーブルを記憶し、
前記演算手段が、前記トラヒックテーブルを参照して、各ノード間の双方向のトラヒック量のうち、多い方のトラヒック量を基準として、割当てる１対１パスのすべての帯域を利用する条件の下でできるだけ多くの１対１パスの割当てを行い、
前記割当てで割当てることができなかったノード間の残余トラヒック量を示すように前記トラヒックテーブルを更新し、
前記トラヒックテーブルに記録された残余トラヒックを参照して、前記ノードペア間を流れる双方向の残余トラヒックのうち、量の多い方のトラヒック量の値が０より大きく、かつ、最小であるノードペアを探索し、
多対多パスに収容できる残余トラヒックの量が最も多く、かつ、各ノード間の残余トラヒックの中で量が多い方向の残余トラヒック量の和が最小となり、かつ、前記和が前記多対多パスで収容できるトラヒック量の上限値を下回るという条件を満たす対地でないノードを選択し、
前記和の計算に使用した双方向トラヒックを前記多対多パスに収容し、
前記ノードを前記多対多パスの対地の一部として選択することで、前記多対多パスの対地と収容するトラヒックとを決定すること
を特徴とするパス配置方法。
【請求項５】
記憶手段と演算手段を備えた計算機が実行するパス配置方法であって、
前記記憶手段が、ノード間を流れるトラヒック量を格納するトラヒックテーブルを記憶し、
前記演算手段が、前記トラヒックテーブルを参照して、各ノード間の双方向のトラヒック量のうち、多い方のトラヒック量を基準として、割当てる１対１パスのすべての帯域を利用する条件の下でできるだけ多くの１対１パスの割当てを行い、
前記割当てで割当てることができなかったノード間の残余トラヒックを示すように前記トラヒックテーブルを更新し、
前記トラヒックテーブルに記録された残余トラヒックを参照して、０より大きい残余トラヒックを選択し、
前記残余トラヒックの始点のノードまたは終点のノードを始点または終点とする０より大きい残余トラヒックから選択した残余トラヒックの組合せに含まれる残余トラヒックの個数が最大となる前記残余トラヒックの組合せを探索し、
前記残余トラヒックの始点および終点となるノードを対地とする多対多パスを配置し、
前記残余トラヒックを前記多対多パスに収容し、
前記多対多パスの対地のノードと前記多対多パスの対地でないノード間を流れる残余トラヒックの中で前記多対多パスに収容できるトラヒックの数が最も多く、かつ、各ノード間の残余トラヒックの中で量が多い方向の残余トラヒック量の和が最小となり、かつ、前記和が前記多対多パスで収容できるトラヒック量の上限値を下回るという条件を満たす対地でないノードを選択し、
前記和の計算に使用した双方向トラヒックを前記多対多パスに収容し、
前記ノードを前記多対多パスの対地の一部として選択することで、前記多対多パスの対地と収容するトラヒックとを決定すること
を特徴とするパス配置方法。
【請求項６】
前記計算機が、パスを割当て可能な資源を管理する資源管理テーブルをさらに備え、
前記演算手段が、前記資源管理テーブルを参照して、所定の残余トラヒックの和を収納する１対１パスおよび多対多パスを設定できない場合に、前記１対１パスおよび前記多対多パスの設定ならびにトラヒックテーブルの更新を中止して、収納し切れなかった残余トラヒックを出力すること
を特徴とする請求項１ないし請求項５のいずれか１項に記載のパス配置方法。
【請求項７】
ネットワークシステムが、前記計算機とネットワークシステムの伝送装置にパスを設定するパス設定装置とトラヒックを伝送する前記伝送装置とを備えて、
前記計算機が、パスの配置を計算して、計算結果を前記パス設定装置に通知し、
前記パス設定装置が、前記計算結果に従って前記伝送装置にパスを設定し、
前記伝送装置が、前記トラヒックのあて先に応じて、設定された前記パスを選択し、前記パスの経路に従って前記トラヒックを伝送すること
を特徴とする請求項１ないし請求項６のいずれか１項に記載のパス配置方法。
【請求項８】
計算機が、
パス割当てを行う演算手段と、
トラヒック量を記録するトラヒックテーブルと、
パスの割当て計算を行うためのプログラムであるパス割当て部と、
前記トラヒックテーブルに記録されているトラヒック量を更新するトラヒック量計算部と、
前記トラヒックテーブル、前記パス割当て部およびトラヒック量計算部を記憶する記憶手段とを含むパス配置装置であって、
請求項１ないし請求項６のいずれか１項に記載のパス配置方法を実行すること
を特徴とするパス配置装置。
【請求項９】
前記計算機が、設定パス情報とパス設定用プログラムとをさらに備え、
前記計算機自身が計算したパスの配置の計算結果または通信手段によって他のパス配置装置から受け取ったパスの配置の計算結果に従って前記伝送装置にパスを設定すること
を特徴とする請求項８に記載のパス配置装置。
【請求項１０】
前記計算機が、ルーチングテーブルとデータ振り分け用プログラムとをさらに備え、
所定の指示に従って前記パスを自身に対して設定し、前記パスの配置の計算結果に従って前記パスのトラヒック流量を設定し、前記パスおよび流量の設定に従ってトラヒックを伝送すること
を特徴とする請求項８に記載のパス配置装置。
【請求項１１】
請求項１ないし請求項７のいずれか１項に記載のパス配置方法または請求項８ないし請求項１０のいずれか１項に記載のパス配置装置を計算機で実現することを特徴とするパス配置プログラム。
【請求項１２】
請求項１ないし請求項７のいずれか１項に記載のパス配置方法または請求項８ないし請求項１０のいずれか１項に記載のパス配置装置を計算機で実現するパス配置プログラムを記録することを特徴とする記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パス配置方法、パス配置装置、パス配置プログラムおよびパス配置プログラムを記録した記憶媒体に関する。特に、ポイント−ポイント間のパスに加えて、マルチポイント−マルチポイント間のパスの配置に関する。
【背景技術】
【０００２】
ネットワークや電気回路などで、拠点（ノード）や素子間を流れるトラヒック量や電流量が与えられるときに、これらの量を収容するパスや銅線を設計する方法は、これまで多くの方法が存在していた。このうち、少ないネットワーク資源や少ないデバイスでこれらの量を収容する方法について、多くの方法が存在する。これらの方法が対象とするシステムは、２ノード間を結ぶパスを設定するもの、もしくは、３ノード間以上を結ぶが、方向が片方向であるものが挙げられる。ネットワーク内において、ルータ間で仮想トンネルを設定し、その中にトラヒックを収容するときは２ノード間を結ぶパスを設定する場合に相当し、電気回路で設計するときは３ノード間以上で方向が片方向である場合が関係する場合が存在する。このようなパス設計方法が必要な技術分野として、ルータ間の伝送経路を明示的に設定するコネクションオリエンテッド型伝送方式が存在する。
【０００３】
光伝送方式に対応する技術には、以下の２つの技術が知られている。まず、非特許文献１は、２ルータ間を結ぶパスのみで与えられたトラヒック量を収容するときに、パケット遅延が小さくなるようにパスを設定する方法を記述している。非特許文献２は、１つのルータから複数のルータへとデータを配送する１対多のパスを用いてマルチキャストトラヒックを収容するパスを設計する方法を示している。従来の光信号を用いた伝送方式では、これらのパスを用いた伝送方式のみが対象とされていたため、これらの方式を用いることで、目的に適したパスを設定することが可能であった。
【非特許文献１】B. Mukherjee, D. Banerjee, S. Ramamurthy, A. Mukherjee, "Some principles for designing a wide-area WDM optical network," IEEE/ACM Transaction on Networking, vol.4, issue 5, pp.684-696, Oct.(1996)
【非特許文献２】E. Miller, R. Libeskind-Hadas, D. Barnard, W. Chang, K. Dresner, W. M. Turner, J.R. Hartline, "On the complexity of virtual topology design for multicasting in WDM trees with tap-and-continue and multicast-capable switches," IEEE Journal on Selected Areas in Communications, vol.22, pp.1601-1612, Nov.(2004)
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、パスを形成するときに考えられる伝送形態としては、１対１型、１対多型のほかに、多対多型の伝送形態が考えられる。この多対多型の伝送形態では、１対１型や１対多型のパスを使用した場合に比べて、パケット等をコピーする回数が減るため、これを利用することで転送コスト削減を実現することができるというメリットが存在する。ただし、スループットについては、信号衝突などの問題があるために、１対１型や１対多型の方式に比べて小さくなる。この多対多型の伝送方式を利用して与えられたトラヒック量を収容できるパス配置を決定する方法を考えた場合、従来の方式である前記２方式では、多対多型の伝送形態を考慮していないため、多くのパケットがネットワークの中を流れることになる。また、多対多型を用いない場合には、パスが設定されるたびに信号の送受信を行うインタフェースの数は増加し、その結果、トラヒックを収容するための設備のコストは増加する。
【０００５】
そこで、本発明では、このような問題を鑑み、インタフェースの削減を目的としたパス配置方法を提供することを課題とする。
【課題を解決するための手段】
【０００６】
前記課題を解決するため、本発明では、記憶手段が、ノード間を流れるトラヒック量を格納するトラヒックテーブルを記憶し、演算手段が、前記トラヒックテーブルを参照して、各ノード間の双方向のトラヒック量の中で多い方のトラヒック量を基準として、割当てる１対１パスのすべての帯域を利用する条件の下でできるだけ多くの１対１パスの割当てを行い、前記割当てで割当てることのできなかった残余トラヒックを示すように前記トラヒックテーブルを更新し、前記トラヒックテーブルに記録された残余トラヒックから同じノードペア間を流れる双方向の残余トラヒック量の和を求め、前記双方向の残余トラヒック量の和の値を用いて、ノードペアの組合せに含まれるノードペア間で和をとった累積和の値を求め、前記累積和の値を用いて、前記ノードペアの組合せの中で多対多パスに収容できるトラヒック量の上限値を下回り、かつ、最も上限値に近い値となる組合せを探索し、前記組合せに対応するノード間に前記多対多パスを割当て、前記組合せに含まれるノードペア間に流れる前記双方向の残余トラヒックを前記割当てた多対多パスに収容する。
【０００７】
この構成によれば、１対１パスだけでなく、多対多パスも、割当てることができ、所望のトラヒック量を格納するためのパスを設定することができる。
【０００８】
また、本発明（請求項２）では、記憶手段が、ノード間を流れるトラヒック量を格納するトラヒックテーブルを記憶し、演算手段が、前記トラヒックテーブルを参照して、各ノード間の双方向のトラヒック量のうち、多い方のトラヒック量を基準として、割当てる１対１パスのすべての帯域を利用する条件の下でできるだけ多くの１対１パスの割当てを行い、前記割当てで割当てることのできなかった残余トラヒックを示すように前記トラヒックテーブルを更新し、前記トラヒックテーブルに記録された残余トラヒックから同じノードペア間を流れる双方向の残余トラヒック量の和を求め、前記残余トラヒック量の和が０より大きく、かつ、最小となる条件を満たすノードペアを探索し、前記ノードペアが配置する多対多パスの対地となり、かつ、前記ノードペア間を流れる双方向トラヒックを前記多対多パスに収容する条件の下で求めた前記多対多パスの対地のノードと前記多対多パスの対地でないノードの間を流れる残余トラヒックのうち、前記多対多パスに収容できる前記残余トラヒックの数が最も多く、かつ、前記トラヒックにおける各方向に流れる残余トラヒック量の和の値と前記多対多パスに収容したトラヒック量の累積和が最小となり、かつ、前記残余トラヒック量の和と前記累積和との和が前記多対多パスで収容できるトラヒック量の上限値を下回るという条件を満たす前記対地でないノードを選択し、前記ノードと前記多対多パスの対地との間を通る残余トラヒックのうち、前記累積和の計算で使用された残余トラヒックを前記多対多パスに収容し、前記ノードを前記多対多パスの対地の一部として選択することで、前記多対多パスの対地と収容するトラヒックとを決定する。
【０００９】
この構成によれば、１対１パスだけでなく、多対多パスも、高速に割当てることができ、所望のトラヒックを収容するためのパスを設定することができる。
【００１０】
また、本発明（請求項３）では、記憶手段が、ノード間を流れるトラヒック量を格納するトラヒックテーブルを記憶し、演算手段が、前記トラヒックテーブルを参照して、各ノード間の双方向のトラヒック量のうち、多い方のトラヒック量を基準として、割当てる１対１パスのすべての帯域を利用する条件の下でできるだけ多くの１対１パスの割当てを行い、前記割当てで割当てることのできなかった残余トラヒックを示すように前記トラヒックテーブルを更新し、前記トラヒックテーブルに記録された残余トラヒックを参照して、同じノードペア間を流れる双方向の残余トラヒック量のうち、量の多い方のトラヒック量の値を選択し、前記多い方のトラヒック量の値を用いて組合せに含まれるノードペアの間で和をとった値が、多対多パスに収容できるトラヒック量の上限値を下回り、かつ、最も上限値に近い値となる条件を満たす組合せを探索し、前記組合せに対応するノード間に前記多対多パスを割当て、前記組合せに含まれるノードペア間を流れる双方向トラヒックを前記割当てた多対多パスに収容する。
【００１１】
この構成によれば、１対１パスだけでなく、多対多パスも、柔軟に割当てることができ、所望のトラヒックを収容するためのパスを設定することができる。
【００１２】
また、本発明（請求項４）では、記憶手段が、ノード間を流れるトラヒック量を格納するトラヒックテーブルを記憶し、演算手段が、前記トラヒックテーブルを参照して、各ノード間の双方向のトラヒック量のうち、多い方のトラヒック量を基準として、割当てる１対１パスのすべての帯域を利用する条件の下でできるだけ多くの１対１パスの割当てを行い、前記割当てで割当てることができなかったノード間の残余トラヒック量を示すように前記トラヒックテーブルを更新し、前記トラヒックテーブルに記録された残余トラヒックを参照して、前記ノードペア間を流れる双方向の残余トラヒックのうち、量の多い方のトラヒック量の値が０より大きく、かつ、最小であるノードペアを探索し、多対多パスに収容できる残余トラヒックの量が最も多く、かつ、各ノード間の残余トラヒックの中で量が多い方向の残余トラヒック量の和が最小となり、かつ、前記和が前記多対多パスで収容できるトラヒック量の上限値を下回るという条件を満たす対地でないノードを選択し、前記和の計算に使用した双方向トラヒックを前記多対多パスに収容し、前記ノードを前記多対多パスの対地の一部として選択することで、前記多対多パスの対地と収容するトラヒックとを決定する。
【００１３】
この構成によれば、１対１パスだけでなく、多対多パスも、高速かつ柔軟に割当てることができ、所望のトラヒックを収容するためのパスを設定することができる。
【００１４】
また、本発明（請求項５）によれば、記憶手段が、ノード間を流れるトラヒック量を格納するトラヒックテーブルを記憶し、演算手段が、前記トラヒックテーブルを参照して、各ノード間の双方向のトラヒック量のうち、多い方のトラヒック量を基準として、割当てる１対１パスのすべての帯域を利用する条件の下でできるだけ多くの１対１パスの割当てを行い、前記割当てで割当てることができなかったノード間の残余トラヒックを示すように前記トラヒックテーブルを更新し、前記トラヒックテーブルに記録された残余トラヒックを参照して、０より大きい残余トラヒックを選択し、前記残余トラヒックの始点のノードまたは終点のノードを始点または終点とする０より大きい残余トラヒックから選択した残余トラヒックの組合せに含まれる残余トラヒックの個数が最大となる前記残余トラヒックの組合せを探索し、前記残余トラヒックの始点および終点となるノードを対地とする多対多パスを配置し、前記残余トラヒックを前記多対多パスに収容し、前記多対多パスの対地のノードと前記多対多パスの対地でないノード間を流れる残余トラヒックの中で前記多対多パスに収容できるトラヒックの数が最も多く、かつ、各ノード間の残余トラヒックの中で量が多い方向の残余トラヒック量の和が最小となり、かつ、前記和が前記多対多パスで収容できるトラヒック量の上限値を下回るという条件を満たす対地でないノードを選択し、前記和の計算に使用した双方向トラヒックを前記多対多パスに収容し、前記ノードを前記多対多パスの対地の一部として選択することで、前記多対多パスの対地と収容するトラヒックとを決定する。
【００１５】
この構成によれば、１対１パスだけでなく、多対多パスも、高速に割当てることができ、所望のトラヒックを収容するためのパスを設定することができる。
【００１６】
また、本発明（請求項６）では、前記演算手段が、前記資源管理テーブルを参照して、所定の残余トラヒックの和を収納する１対１パスおよび多対多パスを設定できない場合に、前記１対１パスおよび前記多対多パスの設定ならびにトラヒックテーブルの更新を中止して、収納し切れなかった残余トラヒックを出力する。
【００１７】
この構成によれば、ネットワーク資源が不足している場合にも対応できる。
【００１８】
また、本発明（請求項７）では、計算機が、パスの配置を計算して、計算結果を前記パス設定装置に通知し、前記パス設定装置が、前記計算結果に従って前記伝送装置にパスを設定し、前記伝送装置が、前記トラヒックのあて先に応じて、設定された前記パスを選択し、前記パスの経路に従って前記トラヒックを伝送する。
【００１９】
この構成によれば、適切なパス配置を行うネットワークシステムを構成することができる。
【００２０】
また、本発明（請求項８）では、計算機が、パス割当てを行う演算手段と、トラヒック量を記録するトラヒックテーブルと、パスの割当て計算を行うためのプログラムであるパス割当て部と、前記トラヒックテーブルに記録されているトラヒック量を更新するトラヒック量計算部と、前記トラヒックテーブル、前記パス割当て部およびトラヒック量計算部を記憶する記憶手段とを含むパス配置装置であって、前記のパス配置方法を実行する。
【００２１】
これによれば、適切なパス配置を行うパス配置装置を構成することができる。
【００２２】
また、本発明（請求項９）では、前記計算機自身が計算したパスの配置の計算結果または通信手段によって他のパス配置装置から受け取ったパスの配置の計算結果に従って前記伝送装置にパスを設定する。
【００２３】
この構成によれば、計算したパス配置に従って、伝送装置にパスを設定する。
【００２４】
また、本発明（請求項１０）では、計算機が、ルーチングテーブルとデータ振り分け用プログラムとをさらに備え、所定の指示に従って前記パスを自身に対して設定し、前記パスの配置の計算結果に従って前記パスのトラヒック流量を設定し、前記パスおよび流量の設定に従ってトラヒックを伝送する。
【００２５】
この構成によれば、計算したパスに従って、トラヒックの伝送が行われる。
【発明の効果】
【００２６】
本発明によれば、１対１型のパス（Ｐ−Ｐパス）に加えて多対多型のパス（ＭＰ−ＭＰパス）についても割当てを行うことができ、これにより、回線帯域を有効に活用しつつ、割当てに必要なインタフェース数を削減することができる。
【発明を実施するための最良の形態】
【００２７】
<<第１の実施形態>>
本発明の第１の実施形態について、適宜図面を参照しながら詳細に説明する。
本実施形態では、１対１型パスと１対多型パスのインタフェース削減を目的とした設定方法について述べる。本方式で使用される装置として、パス設定箇所計算装置（パス配置装置）１０、情報収集装置２０、パス設定装置３０および伝送装置４０が挙げられる。本実施形態では、光通信ネットワークを対象として、パスを設定するシステムを示す。また、本実施形態では、１対１型、１対多型および多対多型のいずれもが利用可能な光ネットワークを前提とし、１対１型および多対多型のいずれのパスも設定可能とする。
【００２８】
［システム構成］
図１は、本実施形態におけるパス設定箇所計算装置を説明する図である。
パス設定箇所計算装置（パス配置装置）１０は、ネットワークのトポロジや他のネットワークと接続しているルータ間を流れるトラヒック量などの情報が与えられたときに、トラヒックを収容するパスの設定箇所を、使用するインタフェース数が少なくなるように計算を行う。パス設定箇所計算装置１０は、ネットワークのトポロジなどの情報を他の装置または管理者により入力してもらうため、外部装置や入力装置などとのインタフェースを備える構成としてもよい。
【００２９】
パス設定箇所計算装置１０は、記憶媒体１０１、処理部１０９および通信部１１０を含んで構成される。記憶媒体１０１は、ハードディスクやＣＤ−ＲＯＭ（Compact Disk Read Only Memory）などで構成され、トポロジトラヒック交流各種プログラム１０２を含んでいる。そして、このトポロジトラヒック交流各種プログラム１０２は、記憶媒体１０１から後記するメモリ１０７に読み込まれて、その中に含まれるプログラムが稼動可能な状態になる。これらのプログラムについては、後記する。
【００３０】
処理部１０９は、ＣＰＵ（Central Processing Unit）１０３、メモリ１０７を含んで構成される。ＣＰＵ１０３は、所定の演算機能を備えたものであればよく、機種などは限定されない。メモリ１０７は、例えば半導体の記憶素子を用いて構成することができ、前記のＣＰＵ１０３から利用できるものであればよい。そして、メモリ１０７には、トラヒック量を記録したトラヒックテーブル１０８とともに、前記のトポロジトラヒック交流各種プログラム１０２が読み込まれて稼動可能な形のトポロジトラヒック交流各種プログラム１０６となって含まれる。トポロジトラヒック交流各種プログラム１０６には、パス割当て部１０４およびトラヒック量計算部１０５が含まれる。ＣＰＵ１０３は、パスの設定箇所を計算する際に、パス割当て部１０４を用いて、トラヒックテーブル１０８を参照して、パスを割当てる箇所を決定する。また、ＣＰＵ１０３は、トラヒック量計算部１０５を用いて、トラヒックテーブル１０８に含まれるトラヒック量に対する所定の計算処理を行い、トラヒックテーブル１０８の更新処理を行う。そして、後記する情報収集装置２０との間で、情報収集の要求や収集された情報をやり取りする。
【００３１】
通信部１１０は、通信を行う機能を担っている構成要素であり、本実施形態では光通信ネットワークを対象としているので、光通信の通信媒体１１１に対してのインタフェースを備えている。なお、通信部１１０は、光通信以外の通常のイーサネット（登録商標）などのネットワークに対応する機能を持っているものでもよい。
【００３２】
図２は、本実施形態における情報収集装置を説明する図である。
情報収集装置２０は、ネットワーク内のトラヒックやトポロジなどを観測する装置から、これらの情報を収集する装置である。情報収集装置２０にもネットワークのトポロジなどの情報を他の装置、または管理者により入力してもらうことを想定するため、外部装置や入力装置とのインタフェースを持つこととしてもよい。
情報収集装置２０は、記憶媒体２０１、処理部２０６および通信部２０７から構成される。記憶媒体２０１は、トポロジトラヒック交流収集用プログラム２０２を含んでいる。そして、このトポロジトラヒック交流収集用プログラム２０２は、記憶媒体２０１から後記するメモリ２０４に読み込まれて、稼動可能な状態になる。また、稼動したトポロジトラヒック交流収集用プログラム２０５によって集められた情報は、記憶媒体２０１に記録された後、パス設定箇所計算装置１０からの依頼に応じて提供される。
【００３３】
処理部２０６は、ＣＰＵ２０３およびメモリ２０４を含んで構成される。そして、メモリ２０４には、前記した記憶媒体２０１のトポロジトラヒック交流収集用プログラム２０２から読み込まれて稼動可能な状態になったトポロジトラヒック交流収集用プログラム２０５を含む。トポロジトラヒック交流収集用プログラム２０５は、光ネットワークの設定状況（トポロジ）および光ネットワークのトラヒック交流の情報を収集する。そして、この情報を前記のパス設定箇所計算装置１０に送る。通信部２０７は、パス設定箇所計算装置１０の通信部１１０と同様なので、説明を省略する。
【００３４】
図３は、パス設定装置を説明する図である。
パス設定装置３０は、パス設定箇所計算装置１０から受け取ったパスの設定箇所情報に応じてパスを設定する装置である。
パス設定装置３０は、記憶媒体３０１、処理部３０８および通信部３０９を含む。記憶媒体３０１には、設定パス情報３０２およびパス設定用プログラム３０３が記録されている。これらは、パスを設定するために必要なパスの経路情報などの情報と、パスを実際に設定するために必要なシグナリングプロトコルなどのパス設定用プログラムである。
【００３５】
処理部３０８は、ＣＰＵ３０４およびメモリ３０５を含む。メモリ３０５には、設定パス情報３０６およびパス設定用プログラム３０７が含まれる。そして、設定パス情報３０６に従って、パス設定用プログラム３０７がパス設定を実行する。
通信部３０９は、前記の通信部１１０と同様のものであり、ネットワーク越しに情報を受信し、受信した情報に基づきパスを設定する指示を送るメッセージを送信する。
【００３６】
図４は、伝送装置を説明する図である。
伝送装置４０は、データを伝送用信号に変換し、相手先の伝送装置に送る装置である。本実施形態で設定されるパスは、同一伝送装置間に複数のパスが設定され、その中には１対１型パスと多対多型パスが存在する。多対多型パスは、複数の対地間トラヒックにより共有されるため、各伝送装置からデータを流す割合を決める必要がある。このため、伝送装置４０は、この割合情報をパス設定箇所計算装置から取得する。この情報に従い伝送装置４０は、信号を送信し、そして、時間的割合を決定し、時間的割合に従って信号を送信する。
【００３７】
伝送装置４０は、記憶媒体４０１、データ処理部４０５、バッファ４０９および通信部４１０を含んで構成される。
記憶媒体４０１には、データを送信するために使用するパスを示すルーチングテーブル４０２やデータの送信割合を決定し、その割合に応じて信号を送信するデータ振り分け用プログラム４０３などが記録されている。
【００３８】
データ処理部４０５は、データ振り分け用プログラム４０３を実行して、送られてきたデータを処理する。データ処理部４０５は、ＣＰＵ４０４およびメモリ４０６を含んで構成され、メモリ４０６には、記憶媒体４０１に含まれていたルーチングテーブル４０２およびデータ振り分け用プログラム４０３が読み込まれて、稼動が可能な形でルーチングテーブル４０８およびデータ振り分け用プログラム４０７として含まれる。
【００３９】
バッファ４０９は、トラヒックのデータを振り分けてデータを送受信する際に、一時的にデータを貯めておくために用いる。
通信部４１０は、パス設定箇所計算装置１０の通信部１１０と同様のものである。そして、伝送装置４０においては、データ送信のための信号の送信や、外部装置からの信号ならびにデータの受信、パス設定箇所計算装置などの外部装置から情報を取得するために、他の装置と通信を行う。
【００４０】
図５は、パス設定機能付き伝送装置を説明する図である。
図５に示すように、伝送装置４０の一変形例として、パス設定装置３０と伝送装置４０とが同一装置内に存在する場合も考えられる。
図４に示した伝送装置４０との違いは、記憶媒体４０１にパス設定用プログラム３０３が存在することであり、パス設定用のメッセージを作成する機能が追加されている。
パス設定機能付き伝送装置５０の構成要素は、すべてパス設定装置３０または伝送装置４０に存在する構成要素であるので、同じ符号を付して説明を省略する。
【００４１】
なお、図５に示した例では、パス設定装置３０および伝送装置４０を１つの装置に共存させているが、これに限らず、パス設定箇所計算装置１０、情報収集装置２０、パス設定装置３０および伝送装置４０のうちのいずれか２つ以上を１つの装置にまとめてもよく、その組み合わせ方も限定されない。
【００４２】
［パス割当て処理］
パス設定箇所計算装置１０、情報収集装置２０、パス設定装置３０および伝送装置４０で構成される本実施形態の光通信ネットワークシステムにおいては、パス設定箇所計算装置１０がパスを割当ての処理を行う。以下、本実施形態におけるパス割当て処理について説明する。
【００４３】
パス割当て処理は、パスが通過するノードの集合を示すＶと、光ファイバやＷＤＭ（Wavelength Division Multiplexing、波長分割多重）による波長多重をおこなうことで１本または複数の光パスを追加することができる区間を示すエッジ集合ＥとからなるトポロジＧ＝（Ｖ，Ｅ）に対して行われる。このため、処理に対する入力として、パスの端点となりうるノードの集合Ｓおよびノードｉからノードｊに向かうトラヒック量ｄijの集合Ｄを入力とする。ただし、前記したように、Ｖはノードの集合、Ｅは１本または複数の光パスを追加することができる区間を示すエッジの集合であり、ノードの集合Ｓはノードの集合Ｖの部分集合である（Ｓ⊆Ｖ）。
また、トラヒック量ｄijのｉ，ｊはノードの集合Ｓに含まれる要素であり（ｉ，ｊ∈Ｓ）、トラヒック量ｄijはトラヒックを運ぶのに必要なパスの本数で表現している。
そして、発見されたパスの集合ＴおよびＴの中のパスを用いて通すトラヒック量を引いた後のノードｉからノードｊに向かうトラヒック量ｄ’ijを出力とする。なお、この割当て終了後のトラヒック量ｄ’ijは、資源が足りている場合はすべて０となっていて、資源が不足している場合は（例えば、光通信ネットワークの特定の場所で光ファイバの本数が足りなかった場合など）、０でないトラヒック量があることになる。
【００４４】
また、１本のＰ−ＰパスおよびＭＰ−ＭＰパスは、両方向に同じ帯域の伝送能力を持つことを前提とする。例えば、ノード１とノード２との間のＰ−Ｐパス１本では、ノード１からノード２に向けてのトラヒックを運ぶための１の帯域を持つと同時に、ノード２からノード１に向けてのトラヒックを運ぶための１の帯域を持つ。また、ＭＰ−ＭＰパスにおいては、マルチキャストの通信を行えるものとする。このため、ノード１から出された信号はノード２ならびにノード３に到達する。よって、ノード１からノード２に向かうトラヒックとノード１からノード３に向かうトラヒックをＭＰ−ＭＰパス内に収容することが可能である。また、ＭＰ−ＭＰパスにつながるノードすべてが送信ノードとなりうるので、ノード２、ノード３から出された信号も同様にＭＰ−ＭＰパスにつながるノードへと到達する。よって、ノード１，２，３を結ぶＭＰ−ＭＰパスは、それぞれのノードの間を流れるトラヒックを収容することが可能になる。
【００４５】
トラヒックの収容方法として、ＭＰ−ＭＰパスに接続するノード間を結ぶすべてのトラヒックを収容する場合や、ノード間を結ぶトラヒックの一部を収容する場合がある。ＭＰ−ＭＰパスに接続するノード間を結ぶすべてのトラヒックを収容する場合の例として、ノード１，２，３を結ぶＭＰ−ＭＰパスは、ノード１とノード２の間、ノード１とノード３の間およびノード２とノード３の間のトラヒックを収容する場合が挙げられ、ノード間を結ぶトラヒックの一部を収容する場合の例としては、ノード１とノード２の間およびノード２とノード３の間のトラヒックのみを収容する場合が存在する。
【００４６】
たとえば、あるパスが接続するノード間すべてを結ぶすべてのトラヒックを収容する場合、そのパスにつながるノードに向かうトラヒックを設定するパスを用いて転送するようにルーチングテーブルに記載する。また、ノード間を結ぶトラヒックの一部を収容する場合、収容されたトラヒックのあて先となるノードあてのトラヒックを設定するパスを経由して転送されるようにルーチングテーブルを設定し、収容されないトラヒックのあて先となるノードあてのトラヒックは、設定するパス以外のパスを経由して転送されるようにルーチングテーブルを設定する。
【００４７】
これら２つの収容方法は、後述するパス配置方法により決定された収容トラヒックの選び方によって決まる。すなわち、パスの対地となるノード間を結ぶトラヒックをすべて収容するようにパス配置方法を決定すると、パスに接続するノード間を結ぶすべてのトラヒックを収容する収容方法でトラヒックは収容され、パスの対地となるノード間を結ぶトラヒックのうち、その一部のみを収容する場合、ノード間を結ぶトラヒックの一部を収容する収容方法により、選択されたトラヒックのみを収容する。
【００４８】
ＭＰ−ＭＰパスは、マルチキャスト通信だけでなく、ＭＰ−ＭＰパスに接続する２つのノードが同時にデータ送信するとき、双方向のユニキャスト通信を実現する。双方向通信時には、収容するトラヒック量として最大１本分のトラヒックを収容することが可能である。
【００４９】
図６は、パス割当て処理の流れを説明する図である。
まず、この処理では、トラヒックテーブル１０８のトラヒック量ｂijのすべての値をパスの帯域Ｗで割る（Ｓ５）。そして、トラヒックテーブル１０８のトラヒック量ｄijとその逆向きのトラヒック量ｄjiから、予め与えられた所定の計算方法により、導出された値の数だけ、ノードｉとノードｊの間にＰ−Ｐパスを設定する（Ｓ１０）。
ここで、用いられる計算方法は、例えば、ノードｉとノードｊの間の両方の向きのうち、大きい方の値を超えない最大の整数値だけＰ−Ｐパスを設定する。
すなわち、トラヒック量ｄijとその逆向きのトラヒック量ｄjiがそれぞれ１．８と２．２だったとすると、大きい方の値を超えない最大の値は２なので、２本Ｐ−Ｐパスを設定する。なお、ここでの計算方法は、前記の最大の整数を用いる計算方法に限定されない。
【００５０】
次に、設定されたＰ−Ｐパスの帯域の量だけ、トラヒック量ｄij，ｄjiから引いた値を新たなトラヒック量ｄij，ｄjiの値とする。ただし、このとき、値が０を下回る場合は０を代入する（Ｓ１５）。例えば、ステップＳ１０においてＰ−Ｐパスを２本設定したとすると、各トラヒック量ｄij，ｄjiの値から２を引くことになるが、トラヒック量ｄijが１．８の場合は、１．８から２を引くと０を下回るので、０を代入する。
【００５１】
そして、トラヒックテーブル１０８を参照して、ＭＰ−ＭＰパス割当てを行う（Ｓ２０）。このステップの処理の詳細については、後記する。さらに、この処理の結果割当てられたＭＰ−ＭＰパスをパス設定装置３０が設定する（Ｓ２５）。この設定において、トラヒックテーブル１０８はすべて０か否かを調べる（Ｓ３０）。０ではない要素がある場合には（Ｓ３０のＮｏ）、ステップＳ２０に戻って処理を繰り返す。すべて０だった場合には（Ｓ３０のＹｅｓ）、完成したパスの割当てをネットワークで接続された管理端末などに出力し（Ｓ３５）、処理を終了する。
【００５２】
図７は、第１の実施形態におけるＭＰ−ＭＰパスの割当ての処理を説明する図である。
この処理では、まず、トラヒックテーブル１０８中のすべてのノードの組合せについて、トラヒック量ｄij，ｄjiの和として求めたｂijを調査し、利用効率ρに対して、
ρ−Σｂij≧０
を満たす組合せを選択する（Ｓ５０）。
【００５３】
そして、この結果に対して、すべてのｂijが０の組合せだけか否かを判定する（Ｓ５５）。０の組合せだけである場合は（Ｓ５５のＹｅｓ）、解なしであることをネットワークで接続された管理端末などに通知し（Ｓ７５）、処理を終了する。
【００５４】
０の組合せ以外の組合せが含まれている場合は（Ｓ５５のＮｏ）、０以外の値が入っているｂijの数が最も多い組合せを選択する（Ｓ６０）。そして、当該組合せの中から予め与えられた所定の条件に合致する組合せを選択する（Ｓ６５）。ここでの予め与えられた所定の条件とは、例えば、パスが運ぶことができるトラヒックの余剰量に相当するρ−Σｂijが最大となるもの、あるいは、最小となるものを選択するという条件である。
【００５５】
そして、組合せに含まれるノードを結ぶパスＴを解として出力し（Ｓ７０）、処理を終了する。本実施形態では、与えられたトラヒック量を収容することができる光パスを設定するためにインタフェースや光ファイバなどの装置を増設することを考えているため、割当てに使える資源は充分に使用できるという前提になっている。このため、トラヒック量ｄij，ｄjiおよびその和であるｂijはすべて０となって終了しているため、これらの出力を行っていない。しかし、資金などの問題で機器を用意できない場合、光パスに収容できないトラヒックが発生する可能性がある。この場合、収容し切れていないトラヒック量を出力してもよい。
【００５６】
以下、図８から図１３を用いて、第１の実施形態におけるパス割当て処理の具体例を示す。これ以後は、与えられたトラヒック量を収容することができる光パスを設定するためにインタフェースや光ファイバなどの設備を増設するので、トラヒックをすべて収容するまでインタフェースなどの装置を追加することができるという前提とする。また、利用効率ρが１という前提として、ρに関する説明を省略する。
【００５７】
図８は、トラヒックテーブルの具体例を示す図である。図８に示したトラヒックテーブル１０８ａでは、第１の実施形態のパス割当て処理の例における初期状態のトラヒック量を示している。なお、トラヒックテーブル１０８ａでは、ノード１からノード４の４つのノードについてのトラヒック量を示しており、この初期状態では、例えば、ノード１とノード２の間のトラヒック量について、ノード１からノード２に向かうトラヒック量と、ノード２からノード１に向かうトラヒック量を区別して記録している。
【００５８】
図９（ａ）は、図８のトラヒックテーブルの情報を基にＰ−Ｐパスの割当てを行った結果を示す図であり、図９（ｂ）は、Ｐ−Ｐパスの割当てに伴うトラヒックテーブルの更新を説明する図である。
まず、図８のトラヒックテーブル１０８ａの情報を基にＰ−Ｐパスの割当てを行う場合に、ノード間の双方向のトラヒック量のうち、大きいほうのトラヒック量を基準として、そのトラヒック量を超えない最大の整数の値と同じ本数だけＰ−Ｐパスを割当てる。
図９（ｂ）のトラヒックテーブル１０８ｂに示した例では、符号５０２で示したノード１からノード４へのトラヒック量が１．５であり、符号５０３で示したノード４からノード１へのトラヒック量が０．８であるので、符号５０２で示したノード１からノード４へのトラヒック量を基準として、トラヒック量１．５に対してＰ−Ｐパスを１本割当てる。そして、符号５０２，５０３で示したトラヒック量からそれぞれ１ずつ引いて、結果として、０．５および０となる。なお、符号５０３のトラヒック量０．８から１を引くと−０．２となるが、このような０未満になる場合はそのままの負の数にするのではなく、０とする。
【００５９】
このような割当てをすべてのノード間に行うと、図９（ａ）に示した結果のトポロジ５０１が得られる。この例では、ノード３とノード４の間には、Ｐ−Ｐパスを割当てないので、エッジは結ばれておらず、ノード１とノード２の間には、Ｐ−Ｐパスを２本割当てているので、エッジが２本結ばれている。
【００６０】
図１０は、ＭＰ−ＭＰパスを割当てるための前処理を説明する図であり、図１０（ａ）は、割当てたＭＰ−ＭＰパスのトポロジを示す図であり、図１０（ｂ）は、ＭＰ−ＭＰパスを割当てるために前処理を行った後のトラヒックテーブルを示す図である。なお、図１０（ａ）の例では、ＭＰ−ＭＰパスがまだ設定されていないが、各ノードは中心の長方形で示された交換機にあたる装置を通じて潜在的にＭＰ−ＭＰパスを設定が可能な装置構成になっている。
【００６１】
この処理では、まず、図９（ｂ）で示した同じノード間で両方向のトラヒック量についての和をとってトラヒックテーブル１０８ｂ（図９（ｂ）参照）を更新し、図１０（ｂ）に示すようなトラヒックテーブル１０８ｃを得る。そして、トラヒックテーブル１０８ｃのトラヒック量（ｂijに該当）の中からＭＰ−ＭＰ（多対多型）パスを検索する。ここでは、符号５０４で示されているパス１−２−３のように構成するエッジ１−２およびエッジ１−３のトラヒック量の両者の和がちょうど１になるようなパスを検索する。符号５０４で示されているパス１−２−３は、１−３および２−３のトラヒック量が、それぞれ０．３および０．７なので、あわせるとちょうど設定される１本のＭＰ−ＭＰパスの帯域をすべて使う形になる。
【００６２】
図１１は、ＭＰ−ＭＰパスの設定を説明するための図であり、図１１（ａ）は、検索の結果得られたＭＰ−ＭＰパスのトポロジを示す図であり、図１１（ｂ）は、ＭＰ−ＭＰパスの設定に伴って更新を行った結果として得られるトラヒックテーブルを示す図である。
図１０（ｂ）で示した検索の結果、得られたＭＰ−ＭＰパスは、図１１（ａ）において、符号５０５によって示されている。そして、図１１（ｂ）のトラヒックテーブル１０８ｄにおいて符号５０６によって示されているパス１−２−３に対応する部分から、新たに設定したＭＰ−ＭＰパスに対応するトラヒック量を引いて、当該トラヒック量を０とする。
【００６３】
図１２は、第１の実施形態におけるＭＰ−ＭＰパスの設定を説明するための図であり、図１２（ａ）は、検索の結果得られたＭＰ−ＭＰパスのトポロジを示す図であり、図１２（ｂ）は、トラヒックテーブルを示す図である。
図１２（ａ）は、図１１（ａ）と同じ状態のままなので、説明を省略する。
図１２（ｂ）では、トラヒックテーブル１０８ｅにおいて、次に設定するＭＰ−ＭＰパスの候補を２つ示している。この例では、符号５０７で示されているパス１−２−４と符号５０８で示されているパス２−３−４とが候補となる。ここで、符号５０７で示されているパス１−２−４の方は、必要とするトラヒック量の転送能力が合わせて０．８であるのに対して、符号５０８で示されているパス２−３−４の方は、合わせてちょうど１となる。よって、ここでは、まず、符号５０８で示されているパス２−３−４を設定して、その後に符号５０７で示されているパス１−２−４を設定する。これらのパスを設定して、トラヒックテーブル１０８ｅから対応するトラヒック量を引くと、トラヒックテーブル１０８ｅのトラヒック量はすべて０となり、ＭＰ−ＭＰパスの設定が終了する。
【００６４】
図１３は、パスの設定結果を示す図であり、図１３（ａ）は、割当て結果のトポロジを示す図であり、図１３（ｂ）は、割当て結果に応じて必要となるインタフェース数を示す図である。
図１３（ａ）では、ＭＰ−ＭＰパス１−２−４を符号５０９、ＭＰ−ＭＰパス２−３−４を符号５１０、ＭＰ−ＭＰパス１−２−３を符号５１１で示し、Ｐ−Ｐパスは符号５１２で示している。
【００６５】
図１３（ｂ）に示すように、前記した方法でＰ−Ｐパスだけではなく、ＭＰ−ＭＰパスも割当てるとすると、パスの設定に対応して必要になるインタフェースの数は２３であるのに対して、Ｐ−Ｐパスのみで割当てを行うとすると、インタフェースの数は２６必要になる。なお、図９（ｂ）を参照して、Ｐ−Ｐパスのみを用いてすべてのトラヒックを収容するときのＰ−Ｐパスを数えると、１−２間で３本、１−３間で２本、１−４間で２本、２−３間で３本、２−４間で２本、３−４間で１本の合計１３本が必要になるが、このとき、インタフェースはＰ−Ｐパスの両端に１つずつ必要なので２６個必要になることがわかる。それに対して、３ノード間にまたがるＭＰ−ＭＰパスを割当てるとすると、Ｐ−Ｐパスは、図９（ｂ）に示したように合計７本で、これに対応するインタフェース数は１４個が必要になる。加えてＭＰ−ＭＰパスを３本割当てると、これに対応してインタフェース数はさらに９個必要になるのでＭＰ−ＭＰパスを割当てる場合には、合計２３個のインタフェースで済むことがわかる。
これにより、本実施形態で示したパスの割当て方法を行えば、インタフェースを節約することができる。
【００６６】
図１４は、Ｐ−ＰパスおよびＭＰ−ＭＰパスの設定に対応してルーチングテーブルを構成した例を示す図である。図１４に示すように、ルーチングテーブル５１５は、ルート情報（行先）５１６とパス５１７と転送トラヒック量５１８とから構成される。この例に示されているように、１つのルータであるルータＡに対するルーティングを行う場合にも、ルータＡに到達することが可能な複数のパスを用いて、総和として必要なトラヒック転送量をまかなう。マルチキャストグループに関しても、同様に複数のパスを転送に用いる。
【００６７】
第１の実施形態によれば、Ｐ−Ｐパスだけでなく、ＭＰ−ＭＰパスも設定することで、少ないインタフェース数で所定のトラヒックを収納するパス割当てを行うことができる。この結果、特に光通信システムにおいては、回線の帯域を有効に活用し、少ないコストで通信システムを構成することができる。
【００６８】
<<第２の実施形態>>
本発明の第２の実施形態は、第１の実施形態とパスの割当て処理だけが異なる。そして、第２の実施形態におけるシステム構成およびパスの割当て処理以外の処理は第１の実施形態と同じであるので、説明を省略する。
【００６９】
［パス割当て処理］
図１５は、第２の実施形態におけるパス割当て処理を説明する図である。
この処理においては、まず、与えられた所定の条件に従い、トラヒックテーブル１０８からｂijを選択する（Ｓ２００）。このとき、例えば、０でない最小のｂijを選ぶという条件で選択してもよいが、条件の設定はこれに限定されない。
【００７０】
次に、ノードｉ，ｊとパスで接続するノードの集合Ｓとエッジ＜ｉ，ｊ＞からトポロジＧを構成する（Ｓ２０５）。そして、ｂijの累積和ＣTにｂijを加える（Ｓ２１０）。ここで、累積和ＣTは、各ステップにおけるｂijの累積和を表す。
【００７１】
そして、ノードｋとノードの集合Ｓに含まれるノード間を流れるトラヒック量ｂijすべての和ＳＵＭに対し、ＣT＋ＳＵＭ＜ρとなるようなノードｋを探す（Ｓ２１５）。このとき、ｋ（ノードｋ）の選び方として、たとえば、ＳＵＭの値が最小となるようなｋ（ノードｋ）を選ぶという条件で選択してもよいが、条件の設定はこれに限定されない。
そして、前記ノードｋがあったか否かを判定する（Ｓ２２０）。そのようなノードｋがあった場合には（Ｓ２２０のＹｅｓ）、エッジ＜ｋ，ｉ＞をパスＴの一部として加え、ノードｋを集合Ｓに加え（Ｓ２４５）、ステップＳ２１５に戻って処理を繰り返す。
【００７２】
条件を満たすノードｋがなかった場合（Ｓ２２０のＮｏ）、Ｓの一部Ｓ’のノードとノードｋの間で流れるトラヒックの和Σｂijと累積和ＣTの和がパスの利用効率ρより小さくなるようなｋ（ノードｋ）を求める（Ｓ２２５）。
【００７３】
そして、前記のｋのうち、パスに収容できるｂkiの数が最も多く、かつ、トラヒックの余剰量の値が所定の条件に合致したｋ（ノードｋ）を選択する（Ｓ２３０）。ここでの所定の条件とは、例えば、トラヒックの余剰量（１−ＣT−Σｂij）が最大または最小であることなどが挙げられるが、この条件に限定されない。
【００７４】
そして、この選択の結果、条件に合致するｋ（ノードｋ）があるか否かを判定する（Ｓ２３５）。条件に合致するｋ（ノードｋ）がない場合には（Ｓ２３５のＮｏ）、ここまでに求めたパスＴを結果として返し（Ｓ２４０）、ステップＳ２５５に進む。条件に合致するｋがある場合には（Ｓ２３５のＹｅｓ）、パスＴに収容されていないエッジ＜ｋ，ｊ＞に対応するｂkiが所定の条件を満たす場合に、＜ｋ，ｊ＞をＣと呼び、このＣに対するトラヒックの余剰量ａCを求め、エッジ＜ｋ，ｊ＞をパスＴの一部とし、ノードｋをノード集合Ｓに加えて（Ｓ２５０）、ステップＳ２５５に進む。
このとき、エッジ＜ｋ，ｊ＞を選ぶ条件として、最も大きいｂkiを持つものを選ぶなどの条件が考えられるが、この条件に限定されるものではない。また、割当てることのできるトラヒック量は、パスを収容できるトラヒックの余剰量ａCに相当する量である。エッジ＜ｋ，ｊ＞間を流れるトラヒック量ｄkj，ｄjkのうち、余剰量ａCに相当するトラヒック量をパスに収容することになるが、その配分方法として様々な方法が存在する。その方法としては、ａCの値を１／２にし、それぞれの値に相当するトラヒック量ｄij，ｄjiを引いてパスに割当てる、ｄij，ｄjiのうち値の小さいもしくは値の大きい方からａCに相当するトラヒックを割当てるなどが考えられるが、これらの方法に限定されるものではない。
【００７５】
そして、ステップＳ２５５では、パスＴに含まれるエッジ間のトラヒック量をトラヒックｄij，ｄjiから引き、ノードｋを通るトラヒックｄkj，ｄjkからトラヒック量ａCにあたる量を所定の条件に従って分配し、それぞれｄkj，ｄjkから引く。そして、残ったｄijの集合Ｄ’をネットワークで接続された管理端末などに出力して（Ｓ２６０）、処理を終了する。なお、パス割当てに使える資源に制限を前提としなかった本実施形態では、残ったｄijはすべて０であるが、後記する変形例では、対象とする光通信ネットワークシステムの資源を管理してパスの割当てを行うので、資源の不足から、パスに割当てることができないトラヒックが残ることがある。
【００７６】
以下、図１６から図２１を用いて、第２の実施形態におけるパス割当て処理の具体例を示す。これ以後は、話をわかりやすくするために、ネットワーク資源は充分に余裕があり、利用効率ρが１という前提でρに関する説明を省略する。また、ここで説明の対象とするトラヒックテーブルは、第１の実施形態の例で取り上げたトラヒックテーブル１０８ａと同じであり、この段階から第１の実施形態の例におけるトラヒックテーブル１０８ｃまでの処理も同じなので説明を省略する。そして、後記する図１６（ｂ）のトラヒックテーブル１０８ｆはトラヒックテーブル１０８ｃと同じものである。これ以降の処理は、第１の実施形態と第２の実施形態で異なっており、ここでは、これ以降の処理について説明を行う。
【００７７】
図１６は、第２の実施形態において、ＭＰ−ＭＰパスの割当て処理を説明する図であり、図１６（ａ）は、検索対象のＭＰ−ＭＰパスのトポロジを示す図であり、図１６（ｂ）は、設定対象のトラヒックテーブルを示す図である。
図１６（ａ）の符号５１９に示すパスは、ＭＰ−ＭＰパス検索の起点となるパスである。これは、後記する図１６（ｂ）において符号５２０で示されたノード１とノード２のパスに該当する。
【００７８】
この処理では、まず、一番少ない（ただし、０ではない）トラヒック量のパスを選択する。図１６（ｂ）の例では、符号５２０で示されたノード１とノード２のパスを選択することになる。そして、これをＭＰ−ＭＰパスの一部とする。
【００７９】
図１７は、第２の実施形態におけるＭＰ−ＭＰパスの割当て処理を説明する図であり、図１７（ａ）は、検索対象のＭＰ−ＭＰパスのトポロジを示す図であり、図１７（ｂ）は、設定対象のトラヒックテーブルを示す図である。
図１７（ａ）には、２つのＭＰ−ＭＰパスの候補が示されている。まず、符号５２１は、ＭＰ−ＭＰパス１−２−３を示している。そして、符号５２２は、ＭＰ−ＭＰパス１−２−４を示している。
【００８０】
図１７（ｂ）では、トラヒックテーブル１０８ｇにおいて、これらのＭＰ−ＭＰパスに対応するトラヒック量が示されている。符号５２１のＭＰ−ＭＰパス１−２−３は、符号５２０と符号５２３で示されている合計１．３のトラヒック量に対応するトラヒックを通信の対象とするが、実際の帯域は１しかないので、そのうちのトラヒック量１だけを収容する。そして、符号５２２のＭＰ−ＭＰパス１−２−４は、符号５２０と符号５２４で示されている合計１．２のトラヒック量に対応するトラヒックを通信の対象とするが、実際の帯域は１しかないので、そのうちのトラヒック量１だけを収容する。このように２つの候補があるが、このうち、符号５２１のＭＰ−ＭＰパス１−２−３を選択すると、パスに収容できるトラヒック量が多く（符号５２２のＭＰ−ＭＰパス１−２−４と同じ１を収容）、かつ、残余帯域（パスに収容しきれなかった帯域）が最も大きい。よって、ここでは、符号５２１のＭＰ−ＭＰパス１−２−３を選択する。
【００８１】
図１８は、第２の実施形態におけるＭＰ−ＭＰパスの割当て処理を説明する図であり、図１８（ａ）は、設定されたＭＰ−ＭＰパスのトポロジを示す図であり、図１８（ｂ）は、ＭＰ−ＭＰパス１−２−３設定後のトラヒックテーブルを示す図である。
図１８（ａ）に示すように、ここまでの処理でＭＰ−ＭＰパス１−２−３が設定され、図１８（ｂ）に示すようなトラヒックテーブルに更新される。この状態から、ここまでと同様の処理によって再度ＭＰ−ＭＰパスを設定する。
【００８２】
図１９は、第２の実施形態におけるＭＰ−ＭＰパスの割当て処理を説明する図であり、図１９（ａ）は、検索対象のＭＰ−ＭＰパスのトポロジを示す図であり、図１９（ｂ）は、設定対象のトラヒックテーブルを示す図である。
図１９（ａ）では、符号５５０で示されているＭＰ−ＭＰパス２−３−４が次の処理の候補として示されている。この候補は図１９（ｂ）において、図１６において示したのと同様に最小のトラヒック量である符号５５１で示されているトラヒック量に着目して選択し、これとパスの接続が可能な符号５５２で示されるノード２−ノード３間のトラヒック量および符号５５３で示されているノード３−４間のトラヒック量を選択した結果、これらが候補となった。しかし、他に候補がないので、このままＭＰ−ＭＰパス２−３−４を設定する。
【００８３】
図２０は、第２の実施形態におけるＭＰ−ＭＰパスの割当て処理を説明する図であり、図２０（ａ）は、検索対象のＭＰ−ＭＰパスのトポロジを示す図であり、図２０（ｂ）は、設定対象のトラヒックテーブルを示す図である。
図２０（ａ）には、残りのトラヒック量に対応するＭＰ−ＭＰパスの候補であるＭＰ−ＭＰパス１−３−４が示されている。
図１９を用いて説明した前記のパス割当て処理を行うと、図２０（ｂ）のトラヒックテーブル１０８ｈには、０ではないトラヒック量は符号５２６と符号５２７で示したトラヒック量しか残らない。このとき、残ったトラヒック量の中で最も小さいのは、符号５２７で示したトラヒック量である。ここを基点としてＭＰ−ＭＰパスを設定する候補を検索すると符号５２６で示したトラヒック量との組合せによって、前記の図２０（ａ）に示したＭＰ−ＭＰパスの候補であるＭＰ−ＭＰパス１−３−４が決定される。そして、これに対応して、符号５２６と符号５２７で示したトラヒック量も０に更新して、パス割当て処理を終了する。
【００８４】
図２１は、第２の実施形態におけるパスの設定結果を示す図であり、図２１（ａ）は割当て結果のトポロジを示す図であり、図２１（ｂ）は、割当て結果に応じて必要となるインタフェース数を示す図である。
図２１（ａ）では、ＭＰ−ＭＰパス１−３−４を符号５２８、ＭＰ−ＭＰパス１−２−３を符号５２９、ＭＰ−ＭＰパス２−３−４を符号５３０として示し、Ｐ−Ｐパスは符号５３１で示している。この例では、第１の実施形態と同じ帯域を割当てた結果になっており、第２の実施形態におけるヒューリスティクスを用いた高速な処理でも、所定の精度以上の割当て結果が期待できることを示している。
【００８５】
図２１（ｂ）に示されている結果は、図１３（ｂ）で示したものと同じであり、パスの設定に対応して必要になるインタフェースの数は２３であるのに対して、Ｐ−Ｐパスのみで割当てを行うとすると、インタフェースの数は２６必要になる。これにより、本実施形態で示したパスの割当て方法を行えば、インタフェースを節約することができることが改めて確認された。
【００８６】
第２の実施形態によれば、第１の実施形態と同様に、Ｐ−Ｐパスだけでなく、ＭＰ−ＭＰパスも設定することで、少ないインタフェース数で所定のトラヒックを収納するパス割当てを行うことができる。そして、第２の実施形態によれば、ヒューリスティクスを用いて、高速にパス割当てを行うことができる。
【００８７】
<<その他の実施形態>>
ここまで、第２の実施形態について説明してきたが、第２の実施形態においてＭＰ−ＭＰパスを設定するための基点となるノードの組を設定する方法は、前記の方法に限定されず、その他の方法がある。具体的には、以下に説明する方法でＭＰ−ＭＰパスの設定を行うためのノードの組を決定してもよい。
【００８８】
図２２は、第２の実施形態の変形例を説明する図である。
まず、最大値を保存するための変数ＭＡＸを用意して０に初期化し、ノードの組を（０，０）に初期化する（Ｓ１００）。そして、２つのノードの組（ｉ，ｊ）を選択する（Ｓ１０５）。ｉ，ｊいずれかのノードが端点となっているｉ，ｊ間のトラヒック量ｂijのうち、０でないｂijを数える（Ｓ１１０）。
【００８９】
そして、０でないｂijの数がＭＡＸ以上か否かを判定する（Ｓ１１５）。その結果、ＭＡＸ未満の場合は（Ｓ１１５のＮｏ）、そのまま更新を行わずにステップＳ１２５に進む。ＭＡＸ以上の場合は（Ｓ１１５のＹｅｓ）、ＭＡＸの値と（ｉ，ｊ）の組を更新し（Ｓ１２０）、ステップＳ１２５に進む。
【００９０】
ステップＳ１２５では、すべてのノードの組を調べたか否かを判定する。その結果、すべての組を調べ終わっていない場合（Ｓ１２５のＮｏ）、ステップＳ１０５に戻って処理を繰り返す。すべての組を調べ終わっている場合には（Ｓ１２５のＹｅｓ）、ＭＡＸの値とそのＭＡＸの値に対応する（ｉ，ｊ）の組を出力して（Ｓ１３０）、処理を終了する。
【００９１】
本変形例によれば、ノード２つ（ｉ，ｊ）を選択し、いずれかのノードが端点となっているｂijのうち、値が０でないものの数が最も多いノードを選択することができる。これによれば、より実際的なパス割当ての状況に対応できる。
【００９２】
図２３は、第１の実施形態および第２の実施形態におけるＰ−Ｐパス割当て処理についての変形例を説明する図であり、図２３（ａ）は計算前のトラヒックテーブルを示す図であり、図２３（ｂ）は計算後に更新されたトラヒックテーブルを示す図である。
第１の実施形態および第２の実施形態においては、図９に示したＰ−Ｐパスの割当てを行った後に、図１０で示したようにｂij＝ｄij＋ｄjiの値を計算してトラヒックテーブルを更新していた。しかし、このｂijを求める際に、このような計算に限定される必要はなく、他の方法で設定してもよい。例えば、ｂijに対応するｄij，ｄjiのうちの大きい値（最大値）をｂijとして設定してもよい。
【００９３】
具体的には、図２３（ａ）のトラヒックテーブル例５３４に示すようにトラヒック量を設定していた場合には、符号５３５で示されるトラヒック量と符号５３６で示されるトラヒック量を比較して、そのうちの大きい値（最大値）をｂijとして、図２３（ｂ）の符号５４０で示されているトラヒック量にその値を設定するような方法をとってもよい。同様に、符号５３７と符号５３８の例では、符号５３７で示されるトラヒック量と符号５３８で示されるトラヒック量を比較して、そのうちの大きい値（最大値）をｂijとして、図２３（ｂ）の符号５４１で示されているトラヒック量にその値を設定する。
この変形例によれば、Ｐ−Ｐパスで収容するトラヒックについて、実際的な扱いができるようになる。
【００９４】
また、第１および第２の実施形態においては、光通信システムの資源には余裕があり、必要な資源は必ず割当てることができるという前提になっていた。しかしながら、実際のシステムでは、資源は限定されており、必ずしもすべてのトラヒックを収納できるのに充分な回線帯域が確保できるとは限らない。このような状況に対応して、光通信システムの資源を管理するテーブル（図示せず）を備えて、パスを割当てるごとにこの資源を管理するテーブルを更新する構成をとってもよい。この場合には、パスの割当て処理を終了した後に、設定したパスで収容し切れなかったトラヒック量が示されることになる。
【００９５】
ここまで、本発明の実施形態について、特に光通信システムなどの通信システムを前提として説明を行ってきたが、本発明の適用対象は、通信システムに限定されない。たとえば、電気回路や液体（物質）を輸送するパイプラインなどの対象にも適用することができる。すなわち、トラヒック量を電流量や物質量に置き換えて考えることができ、これにより回路の配線や輸送ルートの割当てにも応用できる。
【００９６】
なお、本発明は、その趣旨を逸脱しない範囲で変更が可能である。例えば、パスの割当て処理を行うための演算手段を並列化して、割当て処理を高速化してもよい。また、本発明のすべての実施形態は、演算手段を用いて、それぞれの実施形態に対応する計算機のプログラムを読み込んで実行することで実現される。
【図面の簡単な説明】
【００９７】
【図１】パス設定箇所計算装置を説明する図である。
【図２】情報収集装置を説明する図である。
【図３】パス設定装置を説明する図である。
【図４】伝送装置を説明する図である。
【図５】パス設定機能付き伝送装置を説明する図である。
【図６】パス割当て処理の流れを説明する図である。
【図７】第１の実施形態におけるＭＰ−ＭＰパスの割当ての処理を説明する図である。
【図８】トラヒックテーブルの具体例を示す図である。
【図９】（ａ）は、図８のトラヒックテーブルの情報を基にＰ−Ｐパスの割当てを行った結果を示す図であり、（ｂ）は、Ｐ−Ｐパスの割当てに伴うトラヒックテーブルの更新を説明する図である。
【図１０】ＭＰ−ＭＰパスを割当てるための前処理を説明する図であり、（ａ）は、割当てたＭＰ−ＭＰパスのトポロジを示す図であり、（ｂ）は、ＭＰ−ＭＰパスを割当てるために前処理を行った後のトラヒックテーブルを示す図である。
【図１１】ＭＰ−ＭＰパスの設定を説明するための図であり、（ａ）は、検索の結果得られたＭＰ−ＭＰパスのトポロジを示す図であり、（ｂ）は、ＭＰ−ＭＰパスの設定に伴って更新を行った結果として得られるトラヒックテーブルを示す図である。
【図１２】第１の実施形態におけるＭＰ−ＭＰパスの設定を説明するための図であり、（ａ）は、検索の結果得られたＭＰ−ＭＰパスのトポロジを示す図であり、（ｂ）は、トラヒックテーブルを示す図である。
【図１３】パスの設定結果を示す図であり、（ａ）は割当て結果のトポロジを示す図であり、（ｂ）は、割当て結果に応じて必要となるインタフェース数を示す図である。
【図１４】Ｐ−ＰパスおよびＭＰ−ＭＰパスの設定に対応してルーチングテーブルを構成した例を示す図である。
【図１５】第２の実施形態におけるパス割当て処理を説明する図である。
【図１６】第２の実施形態において、ＭＰ−ＭＰパスの割当て処理を説明する図であり、（ａ）は、検索対象のＭＰ−ＭＰパスのトポロジを示す図であり、（ｂ）は、設定対象のトラヒックテーブルを示す図である。
【図１７】第２の実施形態におけるＭＰ−ＭＰパスの割当て処理を説明する図であり、（ａ）は、検索対象のＭＰ−ＭＰパスのトポロジを示す図であり、（ｂ）は、設定対象のトラヒックテーブルを示す図である。
【図１８】第２の実施形態におけるＭＰ−ＭＰパスの割当て処理を説明する図であり、（ａ）は、設定されたＭＰ−ＭＰパスのトポロジを示す図であり、（ｂ）は、ＭＰ−ＭＰパス１−２−３設定後のトラヒックテーブルを示す図である。
【図１９】第２の実施形態におけるＭＰ−ＭＰパスの割当て処理を説明する図であり、（ａ）は、検索対象のＭＰ−ＭＰパスのトポロジを示す図であり、（ｂ）は、設定対象のトラヒックテーブルを示す図である。
【図２０】第２の実施形態におけるＭＰ−ＭＰパスの割当て処理を説明する図であり、（ａ）は、検索対象のＭＰ−ＭＰパスのトポロジを示す図であり、（ｂ）は、設定対象のトラヒックテーブルを示す図である。
【図２１】第２の実施形態におけるパスの設定結果を示す図であり、（ａ）は割当て結果のトポロジを示す図であり、（ｂ）は、割当て結果に応じて必要となるインタフェース数を示す図である。
【図２２】第２の実施形態の変形例を説明する図である。
【図２３】第１の実施形態および第２の実施形態におけるＰ−Ｐパス割当て処理についての変形例を説明する図であり、（ａ）は計算前のトラヒックテーブルを示す図であり、（ｂ）は計算後に更新されたトラヒックテーブルを示す図である。
【符号の説明】
【００９８】
１０      パス設定箇所計算装置（パス配置装置、計算機）
２０      情報収集装置
３０      パス設定装置
４０      伝送装置
５０      パス設定機能付き伝送装置
１０１    記憶媒体
１０２    トポロジトラヒック交流各種プログラム
１０３    ＣＰＵ
１０４    パス割当て部
１０５    トラヒック計算部
１０６    トポロジトラヒック交流各種プログラム
１０７    メモリ
１０８    トラヒックテーブル
１０９    処理部
１１０    通信部
１１１    通信媒体
【図１】
2006295627.tif 000003
【図２】
2006295627.tif 000004
【図３】
2006295627.tif 000005
【図４】
2006295627.tif 000006
【図５】
2006295627.tif 000007
【図６】
2006295627.tif 000008
【図７】
2006295627.tif 000009
【図８】
2006295627.tif 000010
【図９】
2006295627.tif 000011
【図１０】
2006295627.tif 000012
【図１１】
2006295627.tif 000013
【図１２】
2006295627.tif 000014
【図１３】
2006295627.tif 000015
【図１４】
2006295627.tif 000016
【図１５】
2006295627.tif 000017
【図１６】
2006295627.tif 000018
【図１７】
2006295627.tif 000019
【図１８】
2006295627.tif 000020
【図１９】
2006295627.tif 000021
【図２０】
2006295627.tif 000022
【図２１】
2006295627.tif 000023
【図２２】
2006295627.tif 000024
【図２３】
2006295627.tif 000025