(57)【要約】【課題】本発明は、共有プロテクションを導入したエラスティック光パスネットワークにおいて、予備経路の周波数スロットの共有度を向上することを目的とする。【解決手段】本願発明の経路及び周波数帯域の決定方法は、複数のノードが光ファイバで接続されたネットワーク上において、光信号を送受信するノード間の経路に当該光信号の伝送容量に応じた周波数帯域を割り当てるエラスティック光パスネットワークを用いた経路及び周波数帯域の決定方法であって、ノード間の現用経路の候補を列挙する現用経路列挙手順と、現用経路の各候補について、現用経路とは独立した予備経路を決定する予備経路決定手順と、決定した予備経路について、他の予備経路と周波数スロットが最も共有可能な周波数スロットを決定する周波数スロット決定手順と、列挙した現用経路のなかから、ファイバの使用本数が最も少なくなる現用経路を決定する現用経路決定手順と、を順に有する。【選択図】図３
2014045463.tif 000002
【特許請求の範囲】
【請求項１】
複数のノードが光ファイバで接続されたネットワーク上において、光信号を送受信するノード間の経路に当該光信号の伝送容量に応じた周波数帯域を割り当てるエラスティック光パスネットワークを用いた経路及び周波数帯域の決定方法であって、
前記ノード間の現用経路の候補を列挙する現用経路列挙手順と、
現用経路の各候補について、現用経路とは独立した予備経路を決定する予備経路決定手順と、
決定した予備経路について、他の予備経路と共有される周波数スロットが大きくなるように周波数スロットを決定する周波数スロット決定手順と、
列挙した現用経路のなかから、ファイバの所要資源量が少なくなるように現用経路を決定する現用経路決定手順と、
を順に有する経路及び周波数帯域の決定方法。
【請求項２】
前記現用経路決定手順で決定した現用経路で使用される予備経路のなかから、他の予備経路と共有している周波数スロットの割合が他の予備経路よりも小さい予備経路又は利用されていない周波数スロットが他の光ファイバよりも大きな光ファイバに収容されている予備経路及び当該予備経路の現用経路を除去し、除去した現用経路及び予備経路を再度決定する再割当手順を、
前記現用経路決定手順の後にさらに有することを特徴とする請求項１に記載の経路及び周波数帯域の決定方法。
【請求項３】
前記再割当手順において、
前記現用経路列挙手順、前記予備経路決定手順、前記周波数スロット決定手順及び前記現用経路決定手順を実行することによって、除去した現用経路及び予備経路を再度決定することを特徴とする請求項２に記載の経路及び周波数帯域の決定方法。
【請求項４】
複数のノードが光ファイバで接続されたネットワーク上において、光信号を送受信するノード間の経路に当該光信号の伝送容量に応じた周波数帯域を割り当てるエラスティック光パスネットワークを用いた経路及び周波数帯域の決定プログラムであって、
現用経路列挙部が、前記ノード間の現用経路の候補を列挙する現用経路列挙手順と、
予備経路決定部が、現用経路の各候補について、現用経路とは独立した予備経路を決定する予備経路決定手順と、
周波数スロット決定部が、決定した予備経路について、他の予備経路と共有される周波数スロットが大きくなるように周波数スロットを決定する周波数スロット決定手順と、
現用経路決定部が、列挙した現用経路のなかから、ファイバの所要資源量が少なくなるように現用経路を決定する現用経路決定手順と、
を順にコンピュータに実行させるための経路及び周波数帯域の決定プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のノードが光ファイバで接続されたネットワーク上において、光信号を送受信するノード間の経路及び周波数帯域を決定するための方法に関する。
【背景技術】
【０００２】
複数のノードが光ファイバで接続されたネットワーク上において、光信号を送受信するノード間の経路に、光信号の伝送容量に応じた必要最小限の周波数帯域を割り当てるエラスティック光パスネットワークが提案されている（例えば、非特許文献１参照。）。エラスティック光パスネットワークに割り当てられる周波数帯域は、従来の光パスネットワークのように、光パスが固定的な周波数間隔である周波数グリッドに基づいて割り当てられるのではなく、ある周波数幅を１スロット単位としたスロットの個数によって柔軟に決定される。
【０００３】
例えば、周波数間隔が５０ＧＨｚで固定されたネットワークにおいては、２０ＧＨｚに相当する伝送容量の通信需要がある場合、５０ＧＨｚだけの周波数帯域を消費してしまっていた。一方で、エラスティック光パスネットワークでは、前記通信需要に対し、例えば１２．５ＧＨｚ単位のスロットを２個割り当て、残りの周波数帯域を他の通信需要に割り当てることができる。このため、エラスティック光パスネットワークは、周波数資源を有用に利用することができる。
【０００４】
一方で、共有プロテクションを導入した光パスネットワークの設計方法が提案されている（例えば、非特許文献２参照。）。共有プロテクションでは、光信号を送受信する経路として用いる現用経路と、現用経路の故障時に用いる予備経路と、を設け、現用経路間で予備経路の一部を共有する。こうすることで、予備経路のために用意すべき光ファイバの数やファイバ内の周波数資源といったファイバの所要資源量を減らすことができる。このため、共有プロテクションを導入した光パスネットワークの設計方法を採用することで、光ファイバ資源を有効に利用することができる。
【０００５】
図１５に、共有プロテクションを導入した光パスネットワークの一例を示す。複数のノード９１ａ〜９１ｋが光ファイバで接続されている。ノード９１ａからノード９１ｄへ光信号を送信し、ノード９１ｅからノード９１ｋへ光信号を送信する場合、ノード９１ａからノード９１ｄへ光信号を伝送する現用経路９３Ｕａｄとノード９１ｅからノード９１ｋへ光信号を伝送する現用経路９３Ｕｅｋとが独立している。また、現用経路９３Ｕａｄとは独立の予備経路９３Ｆａｄ及び現用経路９３Ｕｅｋとは独立の予備経路９３Ｆｅｋが設けられており、予備経路９３Ｆａｄと予備経路９３Ｆｅｋはノード９１ｆ、９１ｇ、９１ｈを共有しており、ノード９１ｆからノード９１ｈまでのリンクを共有している。
【０００６】
エラスティック光パスネットワークにおいて共有プロテクションを導入すれば、周波数資源及び光ファイバ資源の有効利用につながる。この場合、エラスティック光パスネットワークを構成するための制約があるとともに、共有プロテクションを導入するための制約があり、これら両方の制約を満たす必要がある。
【０００７】
例えば、エラスティック光パスネットワークでは、経路の始点から終点まで同じスロットの組を使用しなければならないという同一スロット制約、同一ファイバにおいて１つのスロットを複数の通信需要に割り当てることができないというスロット衝突制約、という制約がある。一方、共有プロテクションでは、異なる対地にある現用経路同士を独立にし、かつ、同一対地にある現用経路と予備経路を独立にしなければならないという制約がある。ここで、現用経路同士が独立とは、経路の始点と終点を含み、どのノードも共有しないことをいう。現用経路と予備経路が独立とは、これらの経路の始点と終点を除き、どのノードも共有しないことをいう。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】Ｍａｓａｈｉｋｏ  Ｊｉｎｎｏ，  Ｂａｒｔｌｏｍｉｅｊ  Ｋｏｚｉｃｋｉ，  Ｈｉｄｅｈｉｋｏ  Ｔａｋａｒａ，  Ａｔｓｕｓｈｉ  Ｗａｔａｎａｂｅ，  Ｙｏｓｈｉａｋｉ  Ｓｏｎｅ，  Ｔａｋａｆｕｍｉ  Ｔａｎａｋａ，  ａｎｄ  Ａｋｉｒａ  Ｈｉｒａｎｏ，  “Ｄｉｓｔａｎｃｅ−Ａｄａｐｔｉｖｅ  Ｓｐｅｃｔｒｕｍ  Ｒｅｓｏｕｒｃｅ  Ａｌｌｏｃａｔｉｏｎ  ｉｎ  Ｓｐｅｃｔｒｕｍ−Ｓｌｉｃｅｄ  Ｅｌａｓｔｉｃ  Ｏｐｔｉｃａｌ  Ｐａｔｈ  Ｎｅｔｗｏｒｋ”，  ＩＥＥＥ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  Ｍａｇａｚｉｎｅ，ＰＰ．１３８−１４５，  Ａｕｇｕｓｔ  ２０１０
【非特許文献２】Ｐｉｎ−Ｈａｎ  Ｈｏ，  Ｈｕｓｓｅｉｎ  Ｔ．  Ｍｏｕｆｔａｈ，  “Ｓｈａｒｅｄ  Ｐｒｏｔｅｃｔｉｏｎ  ｉｎ  Ｍｅｓｈ  ＷＤＭ  Ｎｅｔｗｏｒｋｓ”，  ＩＥＥＥ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  Ｍａｇａｚｉｎｅ，  ＰＰ．  ７０−７６，  Ｊａｎｕａｒｙ  ２００４
【非特許文献３】Ｘｕ  Ｓｈａｏ，  Ｙｏｎｇ−Ｋｅｅ  Ｙｅｏ，  Ｚｈａｏｗｅｎ  Ｘｕ，  Ｘｉａｏｆｅｉ  Ｃｈｅｎｇ，  Ｌｕｙｉｎｇ  Ｚｈｏｕ，  “Ｓｈａｒｅｄ−Ｐａｔｈ  Ｐｒｏｔｅｃｔｉｏｎ  ｉｎ  ＯＦＤＭ−ｂａｓｅｄ  Ｏｐｔｉｃａｌ  Ｎｅｔｗｏｒｋｓ  ｗｉｔｈ  Ｅｌａｓｔｉｃ  Ｂａｎｄｗｉｄｔｈ  Ａｌｌｏｃａｔｉｏｎ”，  ＯＦＣ／ＮＦＯＥＣ  Ｔｅｃｈｎｉｃａｌ  Ｄｉｇｅｓｔ，  ２０１２
【非特許文献４】Ｒａｍｅｓｈ  Ｂｈａｎｄａｒｉ，  “Ｓｕｒｖｉｖａｂｌｅ  Ｎｅｔｗｏｒｋｓ”，  ＫＬＵＷＥＲ  ＡＣＡＤＥＭＩＣ  ＰＵＢＬＩＳＨＥＲＳ，  ＰＰ．１７５−１８２，１９９９
【非特許文献５】Ｊａｎｅ  Ｍ．  Ｓｉｍｍｏｎｓ，  “Ｏｐｔｉｃａｌ  ｎｅｔｗｏｒｋ  Ｄｅｓｉｇｎ  ａｎｄ  Ｐｌａｎｎｉｎｇ”，  Ｓｐｒｉｎｇｅｒ，  Ｐ．６８，２００８
【発明の概要】
【発明が解決しようとする課題】
【０００９】
エラスティック光パスネットワークにおいて共有プロテクションを導入するに際し、予備経路については周波数スロットの共有度が高いことが好ましいが、エラスティック光パスの制約を考慮することが必要となる。
【００１０】
そこで、本発明は、共有プロテクションを導入したエラスティック光パスネットワークにおいて、予備経路の周波数スロットの共有度を向上することを目的とする。
【課題を解決するための手段】
【００１１】
本願発明の経路及び周波数帯域の決定方法は、複数のノードが光ファイバで接続されたネットワーク上において、光信号を送受信するノード間の経路に当該光信号の伝送容量に応じた周波数帯域を割り当てるエラスティック光パスネットワークを用いた経路及び周波数帯域の決定方法であって、前記ノード間の現用経路の候補を列挙する現用経路列挙手順と、現用経路の各候補について、現用経路とは独立した予備経路を決定する予備経路決定手順と、決定した予備経路について、他の予備経路と共有される周波数スロット数が大きくなるように周波数スロットを決定する周波数スロット決定手順と、列挙した現用経路のなかから、ファイバの所要資源量が少なくなるように現用経路を決定する現用経路決定手順と、を順に有する。
【００１２】
本願発明の経路及び周波数帯域の決定方法では、前記現用経路決定手順で決定した現用経路で使用される予備経路のなかから、他の予備経路と共有している周波数スロットの割合が他の予備経路よりも小さい予備経路又は利用されていない周波数スロットが他の光ファイバよりも大きな光ファイバに収容されている予備経路及び当該予備経路の現用経路を除去し、除去した現用経路及び予備経路を再度決定する再割当手順を、前記現用経路決定手順の後にさらに有してもよい。
【００１３】
前記再割当手順において、前記現用経路列挙手順、前記予備経路決定手順、前記周波数スロット決定手順及び前記現用経路決定手順を実行することによって、除去した現用経路及び予備経路を再度決定してもよい。
【００１４】
本願発明の経路及び周波数帯域の決定プログラムは、複数のノードが光ファイバで接続されたネットワーク上において、光信号を送受信するノード間の経路に当該光信号の伝送容量に応じた周波数帯域を割り当てるエラスティック光パスネットワークを用いた経路及び周波数帯域の決定プログラムであって、現用経路列挙部が、前記ノード間の現用経路の候補を列挙する現用経路列挙手順と、予備経路決定部が、現用経路の各候補について、現用経路とは独立した予備経路を決定する予備経路決定手順と、周波数スロット決定部が、決定した予備経路について、他の予備経路と共有される周波数スロット数が大きくなるように周波数スロットを決定する周波数スロット決定手順と、現用経路決定部が、列挙した現用経路のなかから、ファイバの所要資源量が少なくなるように現用経路を決定する現用経路決定手順と、を順にコンピュータに実行させる。
【発明の効果】
【００１５】
本発明によれば、共有プロテクションを導入したエラスティック光パスネットワークにおいて、予備経路の周波数スロットの共有度を向上することができる。
【図面の簡単な説明】
【００１６】
【図１】実施形態１に係るネットワークの一例を示す。
【図２】実施形態１に係る経路及び周波数帯域の決定装置の構成の一例を示す。
【図３】実施形態１に係る経路及び周波数帯域の決定方法の一例を示すフローチャートである。
【図４】実施形態１に係るコストｃｊｂの説明図である。
【図５】実施形態１に係るすべてのトラフィックパターンの割り当てが終了したときの、現用経路及び予備経路の一例を示す。
【図６】実施形態２に係る経路及び周波数帯域の決定装置の構成の一例を示す。
【図７】実施形態２に係る再割当手順の第１例を示す。
【図８】周波数スロットの共有度Ｒｄの説明図である。
【図９】ファイバの利用率Ｆｄの説明図である。
【図１０】ファイバの削減の説明図である。
【図１１】本実施形態に係る再割当手順の第２例を示す。
【図１２】本実施形態に係る再割当手順の第３例を示す。
【図１３】再割当手順を終了後の現用経路及び予備経路の一例を示す。
【図１４】実施形態２の発明と従来発明との必要ファイバ数の比較結果の一例を示す。
【図１５】共有プロテクションを導入した光パスネットワークの一例を示す。
【発明を実施するための形態】
【００１７】
添付の図面を参照して本発明の実施形態を説明する。以下に説明する実施形態は本発明の実施の例であり、本発明は、以下の実施形態に制限されるものではない。なお、本明細書及び図面において符号が同じ構成要素は、相互に同一のものを示すものとする。
【００１８】
（実施形態１）
図１に、本実施形態に係るネットワークの一例を示す。本実施形態では、一例として、複数のノード９１−０１〜９１−２５が光ファイバで接続されたネットワークにおいて、ノード９１−０１からノード９１−１７へ光信号を送信するトラフィックパターン１と、ノード９１−０３からノード９１−１５へ光信号を送信するトラフィックパターン２と、ノード９１−０９からノード９１−２３へ光信号を送信するトラフィックパターン３とを有する場合について説明する。
【００１９】
本実施形態に係る経路及び周波数帯域の決定方法は、ネットワーク上において、光信号を送受信するノード間の経路に光信号の伝送容量に応じた周波数帯域を割り当てる経路決定方法において、ＩＴＳＡ（Ｉｔｅｒａｔｉｖｅ  Ｔｗｏ  Ｓｔｅｐ  Ａｐｐｒｏａｃｈ）を用いて経路を求める。具体的には、本実施形態に係る経路及び周波数帯域の決定方法は、現用経路列挙手順と、予備経路決定手順と、周波数スロット決定手順と、現用経路決定手順と、を順に有する。
【００２０】
図２に、本実施形態に係る経路及び周波数帯域の決定装置の一例を示す。本実施形態に係る経路及び周波数帯域の決定装置は、現用経路列挙手順を実行する現用経路列挙部１１と、予備経路決定手順を実行する予備経路決定部１２と、周波数スロット決定手順を実行する周波数スロット決定部１３と、現用経路決定手順を実行する現用経路決定部１４と、を備える。本実施形態に係る経路及び周波数帯域の決定装置は、現用経路列挙部１１、予備経路決定部１２、周波数スロット決定部１３及び現用経路決定部１４として機能させる経路及び周波数帯域の決定プログラムを、コンピュータに実行させることで実現してもよい。
【００２１】
現用経路列挙手順では、現用経路列挙部１１が、ノード間の現用経路の候補を列挙する。予備経路決定手順では、予備経路決定部１２が、現用経路の各候補について、現用経路とは独立した予備経路を決定する。周波数スロット決定手順では、周波数スロット決定部１３が、決定した予備経路について、他の予備経路と共有される周波数スロットが大きくなるように周波数スロットを決定する。現用経路決定手順では、現用経路決定部１４が、列挙した現用経路のなかから、ファイバの資源量が最も少なくなる現用経路を決定する。これらの手順を実行することによって、新規通信需要を割り当てる際に、所要のファイバ資源量が少なくなるように経路及び周波数スロットの組み合わせを有するパスを選択することができる。
【００２２】
図３は、本実施形態に係る経路及び周波数帯域の決定方法の一例を示すフローチャートである。ステップＳ１０１では、トラフィックパターンを１つ抽出する。トラフィックパターンは始点と終点の組み合わせ及び必要な周波数スロット数を含む。始点と終点の組み合わせは、例えば、トラフィックパターン１の始点であるノード９１−０１と終点であるノード９１−１７である。
【００２３】
ステップＳ１０２では、現用経路列挙部１１が始点と終点をつなぐ経路を探索することにより、現用経路の候補を列挙する。例えば、ノード９１−０１からノード９１−１７へ到達可能な経路のリストを列挙する。現用経路の候補は、例えば、Ｋ−ｓｈｏｒｔｅｓｔ−ｐａｔｈアルゴリズムを用いて探索する。
【００２４】
ステップＳ１０３では、予備経路決定部１２が現用経路の候補の１つを選択する。このとき、同一スロット制約及びスロット衝突制約を満たすように周波数スロットを選択する。また、連続した番号の周波数スロットを割り当てるスロット連続制約も満たすようにする。これにより、エラスティック光パスネットワークを構成するための制約を満たす。
【００２５】
Ｋ−ｓｈｏｒｔｅｓｔ−ｐａｔｈアルゴリズムは、始点と終点をつなぐ経路のうち、Ｋ本の経路を経路の短い順に抽出するアルゴリズムである（例えば、非特許文献４参照。）。ノード９１−０１からノード９１−１７にて前記アルゴリズムを用いて２本のパスを抽出すると、例えば、９１−０１、９１−０６、９１−１１、９１−１６、９１−１７の経路と、９１−０１、９１−０６、９１−１１、９１−１２、９１−１７の経路が抽出される。
【００２６】
ステップＳ１０４では、予備経路決定部１２が、選択した現用経路に対して、異なる対地にある現用経路同士が独立であり、かつ、同一対地にある現用経路と予備経路が独立である共有プロテクションの制約を満たす予備経路を決定する。例えば、現用経路と独立な最短経路を１つ求める。最短経路は、例えば、Ｄｉｊｋｓｔｒａ法を用いて算出する（例えば、非特許文献５参照。）。現用経路の候補が９１−０１、９１−０２、９１−０７、９１−１２、９１−１７である場合、Ｄｉｊｋｓｔｒａ法を用いると、予備経路は９１−０１、９１−０６、９１−１１、９１−１６、９１−１７が選択される。
【００２７】
ステップＳ１０５では、周波数スロット決定部１３が、現用経路及び予備経路候補のコストを最大値に設定する。コストは、周波数スロットの数及びホップ数で定められる。最大値は、想定しうる周波数スロット数の最大値とホップ数の最大値の積よりも大きくなるように設定する。
【００２８】
ステップＳ１０６〜Ｓ１１０では、周波数スロット決定部１３が、周波数スロット番号をずらしながら、ステップＳ１０４で決定した予備経路を用いた場合に、コストが最小になる周波数スロットを決定する。例えば、現用経路と予備経路の各リンクでコストを計算し、各リンクのコストの総和をファイバコストとして求める（Ｓ１０７）。そして、ファイバコストがこれまで算出したコストの中で最も小さくなるようにコスト値を更新する（Ｓ１０８、Ｓ１０９）。これを最後のスロット番号まで走査することにより（Ｓ１１０）、ファイバコストが最も小さくなるような周波数スロット番号が決定される。
【００２９】
ここで、各リンクの現用経路のコストｃｊｗ及び予備経路のコストｃｊｂは、例えば次式で表される。
（式１）
ｃｊｗ＝ｎｄｗ
ｃｊｂ＝ｎｄｂ−ｂｉ+ε
ここで、ｎｄｗ、ｎｄｂはそれぞれ、ｄの現用経路及び予備経路の周波数スロット数であり、ｂｉはファイバｊ内のｉ番目から数えてｎｄｂ個のスロット集合のうち、他の予備経路と共有可能な周波数スロットの数であり、εはｃｊｂが０となるのを防ぐための０＜ε＜１の十分小さな正数である。調べている経路やスロット番号で、必要数のスロットを確保できない場合や現用経路同士が独立でなくスロットの共有ができない場合はコストは無限大とすればよい。
【００３０】
図４にスロット数６のリンクＬ１〜Ｌ３に対してスロット数３の予備パスを設定する際のコスト算出例を示す。ｉ＝０からｉ＝３までの計４回の場合について、各リンクに対するコストを算出する。この例では、ｉ＝２が予備パスのコストが最小となり、これに現用パスのコストを加えることによってファイバコストが算出される。
【００３１】
予備経路決定部１２及び周波数スロット決定部１３は、ステップＳ１０２で列挙したすべての現用経路の候補について、ステップＳ１０３からステップＳ１１０までを行う（Ｓ１１１）。
ステップＳ１１３では、現用経路決定部１４が、ステップＳ１０２で列挙したすべての現用経路のうち、コストが最も小さくなる現用及び予備の経路と当該経路の周波数スロットを、ステップＳ１０１で抽出したトラフィックパターンに対して割り当てる（Ｓ１１３）。例えば、ステップＳ１０３にて求めた現用パスのコスト及びステップＳ１０６〜Ｓ１１０にて求めた最小の予備パスのコストの和が最小になるような現用パスと予備パスとを決定する。これにより、トラフィックパターンｄ＝１の場合、ノード９１−０１からノード９１−１７へ到達可能な現用経路のリストのなかで、ファイバコストが最小になるすなわち使用するファイバ資源量が最小の現用及び予備パスを割り当てることができる。
【００３２】
なお、ファイバコストが最小になるときの経路及び周波数スロットの組み合わせを実現するために光ファイバを増設する必要のあるリンクがあれば、そのリンクに光ファイバを増設する（Ｓ１１２）。
【００３３】
現用経路列挙部１１、予備経路決定部１２、周波数スロット決定部１３及び現用経路決定部１４は、ステップＳ１０１〜Ｓ１１３を、他のトラフィックパターンについても行う。本実施形態では、トラフィックパターンｄ＝２のノード９１−０３からノード９１−１５への経路及びトラフィックパターンｄ＝３のノード９１−０９からノード９１−２３への経路についてもステップＳ１０１〜Ｓ１１３を行い、ファイバコストが最小になるときの、経路及び周波数スロットの組み合わせを、現用経路及び予備経路に割り当てる。
【００３４】
図５に、本実施形態に係るすべてのトラフィックパターンの割り当てが終了したときの、現用経路及び予備経路の一例を示す。ノード９１−０１からノード９１−１７への経路、ノード９１−０３からノード９１−１５への経路及びノード９１−０９からノード９１−２３への経路について、現用経路９３Ｕ１、９３Ｕ２及び９３Ｕ３が独立であり、現用経路と予備経路は互いに独立であり、予備経路９３Ｒ２及び９３Ｒ３のうちのノード９１−０８とノード９１−１３のリンクが共有になっている。
【００３５】
現用経路９３Ｕ１、９３Ｕ２及び９３Ｕ３と予備経路９３Ｒ１、９３Ｒ２及び９３Ｒ３の組み合わせはファイバコストが最小になるものを選択している。このため、本実施形態に係る経路及び周波数帯域の決定方法は、共有プロテクションを導入したエラスティック光パスネットワークにおいて、使用するファイバ内の周波数資源量を少なくすることができる。
【００３６】
（実施形態２）
本実施形態では、予備経路用の周波数スロットの共有度が低い経路や、利用率の低い光ファイバに収容されている経路を取り除き、ＩＴＳＡで再収容する。そのために、本実施形態に係る経路及び周波数帯域の決定方法は、再割当手順を現用経路決定手順の後にさらに有する。
【００３７】
図６に、本実施形態に係る経路及び周波数帯域の決定装置の一例を示す。本実施形態に係る経路及び周波数帯域の決定装置は、実施形態１で説明した現用経路決定部１４の後段に、再割当手順を実行する再割当部１５を更に備える。再割当部１５は、共有度算出部５１と、共有度再割当部５２と、ファイバ利用率算出部５３と、ファイバ利用率再割当部５４と、を備える。本実施形態に係る経路及び周波数帯域の決定装置は、現用経路列挙１１、予備経路決定部１２、周波数スロット決定部１３及び現用経路決定分１４、再割当部１５として機能させる経路及び周波数帯域の決定プログラムを、コンピュータに実行させることで実現してもよい。
【００３８】
再割当手順では、再割当部１５が、現用経路決定手順で決定した現用経路で使用される予備経路のなかから、周波数スロットの共有度が小さい予備経路及び当該予備経路の現用経路か或いはファイバの利用率が小さいファイバに含まれる予備経路及び当該経経路の現用経路を除去し、除去した現用経路及び予備経路を再度決定する。
【００３９】
図７に、本実施形態に係る再割当手順の第１例を示す。再割当手順では、共有度算出部５１が全ての予備パスについて周波数スロットの共有度Ｒｄを求め（Ｓ７０２）、共有度再割当部５２が共有度Ｒｄの小さな予備パスをもつ現用及び予備パスをネットワークから取り除く（Ｓ７０３）。周波数スロットの共有度は、予備パスが他の予備パスとどのくらい周波数スロットを共有しているかの程度、すなわち、他の予備パスと共有している周波数帯域の割合を表す。このため、ステップＳ７０３では、他の予備パスと共有している周波数帯域の割合が小さな予備パスをネットワークから取り除く。そして、共有度再割当部５２が、残った予備パスを同一リンクにおける並列ファイバ間で集約し、可能ならファイバを削減する（Ｓ７０４）。そして、共有度再割当部５２が取り除いた現用パス及び予備パスをＩＴＳＡを用いて再配置する（Ｓ７０５）。すなわち、ステップＳ７０５における再配置は、現用経路列挙手順、予備経路決定手順、周波数スロット決定手順及び現用経路決定手順を実行することによって、除去した現用パス及び予備パスを再度決定する。
【００４０】
次に、ファイバ利用率算出部５３が全てのファイバに対してファイバの利用率を計算し（Ｓ７０６）、ファイバ利用率再割当部５４がファイバの利用率が低いパスをネットワークから取り除く（Ｓ７０７）。ファイバの利用率は、１本のファイバ内に、連続して利用されている周波数スロットがどれだけあるかを表す。このため、ステップＳ７０７では、利用されていないスロットが他のファイバよりも多いファイバに含まれるパスをネットワークから取り除く。そして、ファイバ利用率再割当部５４が、残ったパスを同一リンクにおける並列ファイバ間で集約し、可能ならファイバを削減する（Ｓ７０８）。そして、ファイバ利用率再割当部５４が、取り除いた現用パス及び予備パスをＩＴＳＡを用いて再配置する（Ｓ７０９）。すなわち、ステップＳ７０９における再配置は、現用経路列挙手順、予備経路決定手順、周波数スロット決定手順及び現用経路決定手順を実行することによって、除去した現用パス及び予備パスを再度決定する。
ステップＳ７０２からステップＳ７０９を指定回数繰り返す（Ｓ７１０）。
【００４１】
ここで、ステップＳ７０２における周波数スロットの共有度Ｒｄは、トラフィックパターンをｄ、予備パスのホップ数をｈｄ、予備経路をｒｂ、経路中のリンク（ファイバ）ｌにおいてスロットを共有しているパス本数の平均値（ｄ自身も含む）をｓｌとすると、例えば、次式で表される。
【数２】
2014045463.tif 000003
周波数スロットの共有度Ｒｄが大きい予備パスほど共有度が大きく、周波数スロットの共有度Ｒｄが小さい予備パスほど共有度が小さい。
【００４２】
例えば、図８に示すように、周波数スロット数が５の予備パス１と周波数スロット数が３の予備パス２が共有しているリンクがある場合、当該リンクにおける予備パス１とスロットを共有しているパス本数の平均値ｓｌは（１+１+２+２+２）／５＝１．６となり、予備パス２とスロットを共有しているパス本数の平均値ｓｌは（２+２+２）／３＝２．０となる。予備パス１の各リンクにおけるｓｌを算出し、これらｓｌの和を予備パスのホップ数で除算することで、予備パス１の周波数スロットの共有度Ｒｄを算出することができる。
【００４３】
また、ステップＳ７０６におけるファイバの利用率Ｆｄは、トラフィックパターンをｄ、現用経路をｒｗ、予備経路をｒｂ、経路中のリンク（ファイバ）をｌ、リンクｌにおいて未使用の周波数スロットの総数と未使用の連続した周波数スロットの集合の総数の和をＥｌとすると、例えば、次式で表される。
【数３】
2014045463.tif 000004
Ｆｄの値が小さいほどファイバの利用率が高くなり、Ｆｄの値が大きいほどファイバの利用率が低くなる。
【００４４】
例えば、図９に示すように、周波数スロットが１６スロットのリンクｌにおいて、スロット番号＃１〜＃４、＃８、＃９、＃１２、＃１４、＃１５の周波数スロットが利用され、その他の周波数スロットが未使用の場合、未使用の周波数スロットの総数は７であり、未使用の連続した周波数スロットの集合の数は４であるため、Ｅｌは７＋４＝１１となる。
【００４５】
ここで、ファイバの利用率Ｆｄについては、現用経路及び予備経路の両方に対して計算する。例えば、トラフィックパターンｄ＝１であれば、図５に示す現用経路９３Ｕ１及び予備経路９３Ｒ１の両方の各ファイバｌについてＥｌを算出し、これらＥｌのなかで最も小さい値をファイバの利用率Ｆｄとして算出する。
【００４６】
式２におけるＥｌは、隣接するスロット間で利用状況が反転する回数を用いてもよい。例えば、図９に示すように、スロット番号＃４と＃５の間、スロット番号＃７と＃８の間、スロット番号＃９と＃１０の間、スロット番号＃１１と＃１２の間、スロット番号＃１２と＃１３の間、スロット番号＃１３と＃１４の間、スロット番号＃１５と＃１６の間で利用状況が反転している場合、利用状況が反転する回数は７回であるためＥｌ＝７となる。
【００４７】
式２におけるＥｌは、未使用スロットの総数を用いてもよい。例えば、図９の例では、未使用の周波数スロットの総数は７であるため、Ｅｌ＝７となる。
【００４８】
式２におけるＥｌは、隣接するスロット間で利用状況が反転する回数と、未使用スロットの総数との積を用いて算出してもよい。例えば、図９に示すように、未使用の周波数スロットの総数は７であり、隣接するスロット間で利用状況が反転する回数は７である場合、Ｅｌは７×７＝４９となる。
【００４９】
ステップＳ７０４及びＳ７０８におけるファイバの削減について、図１０を参照しながら説明する。２本の光ファイバが並列に配置され、１本の光ファイバに現用経路のパス１と予備経路のパス２が割り当てられ、もう１本の光ファイバに予備経路のパス３が割り当てられ、パス１とパス２の周波数スロットは異なり、パス２の周波数スロットにパス３の周波数スロットが含まれるとする。この状態で、ステップＳ７０３又はＳ７０７において、パス２が取り除かれた場合、並列ファイバ間で予備経路のパス３を移動することによって、パス３用の光ファイバが不要になる。このような場合に、ステップＳ７０４及びＳ７０８では、光ファイバを削減する。
【００５０】
ステップＳ７０３及びＳ７０７における取り除くパスの数は、一定としてもよいが、これに限られない。
例えば、ステップＳ７０３では周波数スロットの共有度の低い一定割合Ｐ１のパスを取り除き、ステップＳ７０７ではファイバの利用率の低い一定割合Ｐ２のパスを取り除いてもよい。
また、繰り返し回数の２回目以降は、繰り返し回数に比例して取り除く割合を減らしていき、最終的にその割合は０になるようにしてもよい。これにより、ステップＳ７０４、Ｓ７０５、Ｓ７０８及びＳ７０９の処理時間が減少する。
なお、一定割合Ｐ１及びＰ２は、実験的に決定すればよい。
【００５１】
また、ステップＳ７０３及びＳ７０７における取り除くパスの数及びステップＳ７１０における繰り返し数を任意の固定値にし、ステップＳ７１０の後に、各繰り返しのなかでステップＳ７０９の終了時点で必要なファイバ数が最も少ない回数における、現用経路及び予備経路並びにこれらの周波数スロットの組み合わせの経路に決定する手順をさらに有してもよい。例えば、繰り返し回数を１０回とした場合、１０回分のステップＳ７０９の割り当て後のネットワーク構成における必要なファイバ数を比較する。
【００５２】
また、ステップＳ７１０に代えて、ステップＳ７０９の終了時点における必要なファイバ数を記録しておき、前回のステップＳ７０９の終了時点における必要なファイバ数よりも多くなった場合に、前回のステップＳ７０９の終了時点における、現用経路及び予備経路並びにこれらの周波数スロットの組み合わせの経路に決定してもよい。例えば、繰り返しの回数を１０回とし、８回目の必要ファイバ数が１２、９回目の必要ファイバ数が１４である場合、８回目の経路に決定する。
【００５３】
図１１及び図１２に、本実施形態に係る再割当手順の第２例及び第３例を示す。
図１１のように、再割当手順は、ステップＳ７０６からステップＳ７０９を取り除き、予備パスの共有度のみに基づいた再割当を実施しても良い。また逆に、図１２のように、再割当手順は、ステップＳ７０２からステップＳ７０５を取り除き、ファイバの利用率のみに基づいた再割当を実施しても良い。
【００５４】
図１３に、再割当手順を終了後の現用経路及び予備経路の一例を示す。図５で示した予備経路９３Ｒ１はいずれの予備経路とも共有されておらず、周波数スロットの共有度が低かったのに加え、ファイバの利用率も低かった。しかし、再割当手順を行い、ノード９１−０１からノード９１−１７へのパス１を配置しなおすことで、図１３に示すように、予備経路９３Ｒ１の周波数スロットの共有度を高めることができる。
【００５５】
図１、図５及び図１３に示す５×５格子状トポロジにおいて、ステップＳ７０３及びＳ７０７の取り除くトラフィックパターンを一定割合（Ｐ１，Ｐ２）＝（０．１、０．５）とし、ステップＳ７１０において繰り返す指定回数を１００回として、必要ファイバ数を従来手法（非特許文献３参照。）と比較した結果を図１４に示す。本実施形態で説明した方法を用いて算出した必要ファイバ数と、非特許文献３に記載の手法で求めた必要ファイバ数とについて、一様ランダムトラフィックを２０回発生させたときの平均値を求め、本実施形態で説明した方法を用いて算出した必要ファイバ数を、非特許文献３に記載の手法で求めた必要ファイバ数で割った値を示す。本実施形態で説明した方法を用いることにより、図１４に示すように、非特許文献３に記載の手法で求めた必要ファイバ数よりも、光ファイバ数を最大で８％削減することができる。
【産業上の利用可能性】
【００５６】
本発明は情報通信産業に適用することができる。
【符号の説明】
【００５７】
１１：現用経路列挙部
１２：予備経路決定部
１３：周波数スロット決定部
１４：現用経路決定部
１５：再割当部
５１：共有度算出部
５２：共有度再割当部
５３：ファイバ利用率算出部
５４：ファイバ利用率再割当部
９１−０１〜９１−２５、９１ａ〜９１ｋ：ノード
９３Ｕ１、９３Ｕ２、９３Ｕ３、９３Ｕａｄ、９３Ｕｅｋ：現用経路
９３Ｒ１、９３Ｒ２、９３Ｒ３、９３Ｆａｄ、９３Ｆｅｋ：予備経路
【図１】
2014045463.tif 000005
【図２】
2014045463.tif 000006
【図３】
2014045463.tif 000007
【図４】
2014045463.tif 000008
【図５】
2014045463.tif 000009
【図６】
2014045463.tif 000010
【図７】
2014045463.tif 000011
【図８】
2014045463.tif 000012
【図９】
2014045463.tif 000013
【図１０】
2014045463.tif 000014
【図１１】
2014045463.tif 000015
【図１２】
2014045463.tif 000016
【図１３】
2014045463.tif 000017
【図１４】
2014045463.tif 000018
【図１５】
2014045463.tif 000019