(57)【要約】【課題】パスペアのトラヒック分布を考慮した単純な比較演算でパスグループを作成し、短い計算時間でネットワーク全体のリソースを有効活用したスケジューリングを行う。【解決手段】リング状に接続された各ノード間に設定されるパスについて、論理的につなげるとリングを一周する複数のパスの集合をループとしてリストアップし、さらにループごとに構成パスのトラヒックの標準偏差をトラヒック偏差として算出して対応付けたループテーブルを作成し、該ループテーブルを参照してトラヒック偏差が所定の閾値以下となり、かつ構成パス数が所定の許容範囲になる条件で、１または複数のループを組合せてパスグループを作成するパスグループ作成手段を備え、スケジューリングは、パスグループの構成パスの組合せによりスケジュールテーブルを決定する。【選択図】  図１
2016100679.tif 000002
【特許請求の範囲】
【請求項１】
複数のノードがリンクを介してリング状に接続され、各ノード間に設定されるパスとタ
イムスロットの割当状態を示すスケジュールテーブルを決定するスケジューリングを行う
ネットワークシステムにおいて、
前記各ノード間に設定されるパスについて、論理的につなげるとリングを一周する複数
のパスの集合をループとしてリストアップし、さらにループごとに構成パスのトラヒック
の標準偏差をトラヒック偏差として算出して対応付けたループテーブルを作成し、該ルー
プテーブルを参照してトラヒック偏差が所定の閾値以下となり、かつ構成パス数が所定の
許容範囲になる条件で、１または複数のループを組合せてパスグループを作成するパスグ
ループ作成手段を備え、
前記スケジューリングは、前記パスグループの構成パスの組合せにより前記スケジュー
ルテーブルを決定する
ことを特徴とするネットワークシステム。
【請求項２】
請求項１に記載のネットワークシステムにおいて、
前記パスグループ作成手段は、前記ループテーブルを参照して構成パス数が多いループ
から順番に探索し、前記トラヒック偏差が前記所定の閾値以下となるループがない場合に
、該閾値を大きい値に変更してループの探索を継続し、前記パスグループとして確定した
ループの構成パスと重複するパスを含むループを除外して、次のパスグループとなるルー
プの探索を継続する処理を行う
ことを特徴とするネットワークシステム。
【請求項３】
請求項１に記載のネットワークシステムにおいて、
前記パスグループ作成手段は、前記ループテーブルを参照してトラヒック偏差が小さい
ループから順番に探索するか、または構成パス数が多いループから順番でかつトラヒック
偏差が小さいループから順番に探索し、前記トラヒック偏差が前記所定の閾値以下となる
ループがない場合に、該閾値を大きい値に変更してループの探索を継続し、前記パスグル
ープとして確定したループの構成パスと重複するパスを含むループを除外して、次のパス
グループとなるループの探索を継続する処理を行う
ことを特徴とするネットワークシステム。
【請求項４】
請求項１に記載のネットワークシステムにおいて、
前記パスグループ作成手段は、前記条件に該当するループが前記パスグループとなり、
前記条件に該当するループの数が１または０になったときに、前記パスグループに割り当
てられていないパスを所定数ずつパスグループとして振り分ける処理を行う
ことを特徴とするネットワークシステム。
【請求項５】
複数のノードがリンクを介してリング状に接続され、各ノード間に設定されるパスとタ
イムスロットの割当状態を示すスケジュールテーブルを決定するスケジューリングを行う
ネットワークシステムの制御方法において、
前記各ノード間に設定されるパスについて、論理的につなげるとリングを一周する複数
のパスの集合をループとしてリストアップし、さらにループごとに構成パスのトラヒック
の標準偏差をトラヒック偏差として算出して対応付けたループテーブルを作成するステッ
プ１と、
前記ループテーブルを参照してトラヒック偏差が所定の閾値以下となり、かつ構成パス
数が所定の許容範囲になる条件で、１または複数のループを組合せてパスグループを作成
するステップ２とを有し、
前記スケジューリングは、前記パスグループの構成パスの組合せにより前記スケジュー
ルテーブルを決定する
ことを特徴とするネットワークシステムの制御方法。
【請求項６】
請求項５に記載のネットワークシステムの制御方法において、
前記ステップ２は、前記ループテーブルを参照して構成パス数が多いループから順番に
探索し、前記トラヒック偏差が前記所定の閾値以下となるループがない場合に、該閾値を
大きい値に変更してループの探索を継続し、前記パスグループとして確定したループの構
成パスと重複するパスを含むループを除外して、次のパスグループとなるループの探索を
継続する処理を行う
ことを特徴とするネットワークシステムの制御方法。
【請求項７】
請求項５に記載のネットワークシステムの制御方法において、
前記ステップ２は、前記ループテーブルを参照してトラヒック偏差が小さいループから
順番に探索するか、または構成パス数が多いループから順番でかつトラヒック偏差が小さ
いループから順番に探索し、前記トラヒック偏差が前記所定の閾値以下となるループがな
い場合に、該閾値を大きい値に変更してループの探索を継続し、前記パスグループとして
確定したループの構成パスと重複するパスを含むループを除外して、次のパスグループと
なるループの探索を継続する処理を行う
ことを特徴とするネットワークシステムの制御方法。
【請求項８】
請求項５に記載のネットワークシステムの制御方法において、
前記ステップ２は、前記条件に該当するループが前記パスグループとなり、前記条件に
該当するループの数が１または０になったときに、前記パスグループに割り当てられてい
ないパスを所定数ずつパスグループとして振り分ける処理を行う
ことを特徴とするネットワークシステムの制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＴＤＭ（時分割多重化）方式を用いたネットワークシステムおよびその制御
方法に関する。
【背景技術】
【０００２】
図８は、ＴＤＭ方式を用いたネットワークシステムのスケジューリング例を示す。
図８において、ノードＡ〜Ｅはリンクを介してリング状に接続され、事前にデータを送
受信するタイミング（以下、ＴＳ（タイムスロット）という）を決めて運用される。ここ
で、ＴＳの割当状態を示すテーブルをスケジュールテーブル、スケジュールテーブルを決
定する演算をスケジューリングとする。スケジューリングでは、ノード間のパスが経由す
るリンクで共通のＴＳを割り当て、同一リンクで同じＴＳは使えないものとする。
【０００３】
図８に示すスケジュールテーブルでは、繰り返し単位のＴＤＭフレーム長ｔを 500μs 
として 100μs のＴＳ１〜ＴＳ５を設定し、ノードＡ，Ｃ間のパスＡ−Ｃに１ＴＳ（２Ｇ
bps ）を割り当て、ノードＢ，Ｄ間のパスＢ−Ｄに２ＴＳ（４Ｇbps ）を割り当てる例を
示す。この場合、パスＡ−ＣにＴＳ１が割り当てられ、パスＢ−ＤにＴＳ２，ＴＳ３が割
り当てられる。
【０００４】
このようなスケジューリングについては、様々なヒューリスティック解法が提案されて
いる。従来は、与えられたトポロジ、トラヒックに対して１パスずつ、順次割り当てるＴ
Ｓを探索する方法（非特許文献１）が一般的である。しかし、各パスに対して、パスが経
由するすべてのリンクでＴＳの空塞状況をチェックする必要があり、ネットワークシステ
ムの大規模化が困難であった。この問題に対して、階層化スケジューリング（非特許文献
２）が提案されている。
【０００５】
階層化スケジューリングでは、複数のパスを論理的に束ねて複数のグループに分割し、
図９に示すように、各グループ単位にスケジューリングを行ってスケジュールテーブルを
作成し、各スケジュールテーブルをつなぎ合わせて全体のスケジューリングを行う。この
とき、各グループに着目したスケジューリングと、各グループのスケジューリング結果の
調停処理を行うスケジューリングの階層構造となるので、着目するパス数およびＴＳ数が
小規模となって計算時間が短くなるとともに、ネットワークシステムの大規模化にも対応
することができる。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】X. Zhang and C. Qiao, “Pipelined transmission scheduling in all-optical TDM/WDM rings, ”in Proc. Int. Conf. Computer Communication and Networks, pp.144-149, Sept. 1997.
【非特許文献２】中川, 服部, 片山, 小川，“パスグルーピングを用いた光ＴＤＭリソース割当方式の性能評価，”2014年電子情報通信学会ソサイエティ大会，B-12-15,2014年９月.
【非特許文献３】X. Cao et al.,“Waveband Switching in Optical Networks, ”IEEE Commun. Mag., vol.41, no.4, pp.105-112, Apr. 2003.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
複数のパスをグループ化する際に、非特許文献２に記載のFirst-Fit やFirst-Fit path
pair 方式、非特許文献３に記載の波長群パス網におけるグループ化方式では、割当効率
が低下し、同一リソースで収容可能なトラヒック量が低下または同一トラヒック量を収容
するための所要リソース量が増加する課題がある。
【０００８】
図１０は、First-Fit path pair 方式によるグルーピングの例を示す。
図１０において、ネットワーク情報に基づきノードＡ〜Ｅに設定されるパス情報は、パ
スＩＤ、始点ノード、終点ノードから構成される。トラヒック情報は、パスごとの割当Ｔ
Ｓ数を示す。トラヒック情報は定期的に更新される。パスペアテーブルは、２つのパスを
つなげるとリングを一周するパスの組合せを示す。ホップ数は、パスを構成するリンク数
であり、ネットワーク情報から取得し、ノード追加やリンク追加がない限り固定する。Fi
rst-Fit path pair 方式では、パスペアテーブルのパスペアを昇順に２組ずつ組合せてパ
スグループが形成される。スケジュールテーブルは、パスグループ１であるパスペア１（
パス１，５）とパスペア２（パス２，９）のスケジューリング結果を示す。
【０００９】
ここで、パスペアテーブルは、トラヒック情報の更新により随時更新されるが、First-
Fit path pair 方式によるパスペアの組合せが固定であるため計算時間は抑制される。し
かし、パスペアを昇順にグループ化したために、図１０のスケジュールテーブルに示すよ
うに、グループ化しない場合に他のパスが使用できたＴＳも使用できなくなり、割当効率
が低下することがある。
【００１０】
図１１は、波長群パス網におけるグルーピングの例を示す。
ここでは、経路が同一または通過するリンクが同一である４つのパスをグルーピングす
る。例えば、グループ１では、ノードＢ−Ｃ間を通過するパスをグルーピングしたもので
ある。この場合、複数のパスで同一のＴＳを共用することはないので、不使用ＴＳが発生
し、割当効率が低下することがある。
【００１１】
本発明は、パスのトラヒック分布を考慮した単純な比較演算でパスグループを作成し、
短い計算時間でネットワーク全体のリソースを有効活用したスケジューリングを可能とす
るネットワークシステムおよびその制御方法を提供することを目的とする。
【課題を解決するための手段】
【００１２】
第１の発明は、複数のノードがリンクを介してリング状に接続され、各ノード間に設定
されるパスとタイムスロットの割当状態を示すスケジュールテーブルを決定するスケジュ
ーリングを行うネットワークシステムにおいて、各ノード間に設定されるパスについて、
論理的につなげるとリングを一周する複数のパスの集合をループとしてリストアップし、
さらにループごとに構成パスのトラヒックの標準偏差をトラヒック偏差として算出して対
応付けたループテーブルを作成し、該ループテーブルを参照してトラヒック偏差が所定の
閾値以下となり、かつ構成パス数が所定の許容範囲になる条件で、１または複数のループ
を組合せてパスグループを作成するパスグループ作成手段を備え、スケジューリングは、
パスグループの構成パスの組合せによりスケジュールテーブルを決定する。
【００１３】
第１の発明のネットワークシステムにおいて、パスグループ作成手段は、ループテーブ
ルを参照して構成パス数が多いループから順番に探索し、トラヒック偏差が所定の閾値以
下となるループがない場合に、該閾値を大きい値に変更してループの探索を継続し、パス
グループとして確定したループの構成パスと重複するパスを含むループを除外して、次の
パスグループとなるループの探索を継続する処理を行う。
【００１４】
第１の発明のネットワークシステムにおいて、パスグループ作成手段は、ループテーブ
ルを参照してトラヒック偏差が小さいループから順番に探索するか、または構成パス数が
多いループから順番でかつトラヒック偏差が小さいループから順番に探索し、トラヒック
偏差が所定の閾値以下となるループがない場合に、該閾値を大きい値に変更してループの
探索を継続し、パスグループとして確定したループの構成パスと重複するパスを含むルー
プを除外して、次のパスグループとなるループの探索を継続する処理を行う。
【００１５】
第１の発明のネットワークシステムにおいて、パスグループ作成手段は、条件に該当す
るループがパスグループとなり、条件に該当するループの数が１または０になったときに
、パスグループに割り当てられていないパスを所定数ずつパスグループとして振り分ける
処理を行う。
【００１６】
第２の発明は、複数のノードがリンクを介してリング状に接続され、各ノード間に設定
されるパスとタイムスロットの割当状態を示すスケジュールテーブルを決定するスケジュ
ーリングを行うネットワークシステムの制御方法において、各ノード間に設定されるパス
について、論理的につなげるとリングを一周する複数のパスの集合をループとしてリスト
アップし、さらにループごとに構成パスのトラヒックの標準偏差をトラヒック偏差として
算出して対応付けたループテーブルを作成するステップ１と、ループテーブルを参照して
トラヒック偏差が所定の閾値以下となり、かつ構成パス数が所定の許容範囲になる条件で
、１または複数のループを組合せてパスグループを作成するステップ２とを有し、スケジ
ューリングは、パスグループの構成パスの組合せによりスケジュールテーブルを決定する
。
【００１７】
第２の発明のネットワークシステムの制御方法において、ステップ２は、ループテーブ
ルを参照して構成パス数が多いループから順番に探索し、トラヒック偏差が所定の閾値以
下となるループがない場合に、該閾値を大きい値に変更してループの探索を継続し、パス
グループとして確定したループの構成パスと重複するパスを含むループを除外して、次の
パスグループとなるループの探索を継続する処理を行う。
【００１８】
第２の発明のネットワークシステムの制御方法において、ステップ２は、ループテーブ
ルを参照してトラヒック偏差が小さいループから順番に探索するか、または構成パス数が
多いループから順番でかつトラヒック偏差が小さいループから順番に探索し、トラヒック
偏差が所定の閾値以下となるループがない場合に、該閾値を大きい値に変更してループの
探索を継続し、パスグループとして確定したループの構成パスと重複するパスを含むルー
プを除外して、次のパスグループとなるループの探索を継続する処理を行う。
【００１９】
第２の発明のネットワークシステムの制御方法において、ステップ２は、条件に該当す
るループがパスグループとなり、条件に該当するループの数が１または０になったときに
、パスグループに割り当てられていないパスを所定数ずつパスグループとして振り分ける
処理を行う。
【発明の効果】
【００２０】
本発明は、ループをリストアップし、さらにループごとにトラヒック偏差を算出して対
応付けたループテーブルを作成し、ループテーブルを参照してトラヒック偏差が所定の閾
値以下となり、かつ構成パス数が所定の許容範囲になる条件で、１または複数のループを
組合せてパスグループを作成してスケジューリングを行うことにより、スケジュールテー
ブル上でＴＳの凹凸が抑制され、ＴＳリソースを有効活用することができる。
【００２１】
また、構成パス数が多いループから順番に探索し、パスグループとして確定したループ
の構成パスと重複するパスを含むループを除外して、次のパスグループとなるループの探
索を行うことにより、短時間でパスグループを作成することができる。
【図面の簡単な説明】
【００２２】
【図１】本発明のネットワークシステムにおけるパスグループ作成手段の構成例を示す図である。
【図２】ループ作成部１１およびトラヒック偏差演算部１２の処理例を示す図である。
【図３】ループの構成パスとトラヒック偏差の関係を示す図である。
【図４】ループ選択・組合せ演算部１４の処理例(1) を示す図である。
【図５】ループ選択・組合せ演算部１４の処理例(2) を示す図である。
【図６】ループ選択・組合せ演算部１４の処理例(3) を示す図である。
【図７】パス振分演算部１５の処理例を示す図である。
【図８】ＴＤＭ方式を用いたネットワークシステムのスケジューリング例を示す図である。
【図９】階層化スケジューリングの例を示す図である。
【図１０】First-Fit path pair 方式によるグルーピングの例を示す図である。
【図１１】波長群パス網におけるグルーピングの例を示す図である。
【発明を実施するための形態】
【００２３】
図１は、本発明のネットワークシステムにおけるパスグループ作成手段の構成例を示す
。
図１において、パスグループ作成手段は、ループ作成部１１、トラヒック偏差演算部１
２、ループテーブル１３、ループ選択・組合せ演算部１４、パス振分演算部１５により構
成される。なお、パスグループ作成手段は、ノード間のスケジュールテーブルを管理する
ネットワークコントローラ（スケジューラ）に設けられる。各ノードは、ネットワークコ
ントローラにトラヒック情報（要求ＴＳ数）を提供し、ネットワークコントローラから通
知されるスケジュールテーブルに応じたＴＳでＴＤＭ信号を転送する。
【００２４】
図２は、ループ作成部１１およびトラヒック偏差演算部１２の処理例を示す。
図２において、ノードＡ〜Ｅがリング状に接続されたフルメッシュ網において、各ノー
ド間に設定されるパスにＩＤを付与する。ここでは、始点（送信元）ノードと終点（宛先
）ノードの昇順に１〜20を付与する。さらに、各パスのトラヒック情報として、制御タイ
ミングにおける要求ＴＳ数（割当ＴＳ数）が対応付けられる。トラヒック情報は随時更新
される。
【００２５】
ループ作成部１１は、パス情報（パスＩＤ、始点ノード、終点ノード）を入力し、論理
的につなげるとリングを１周する複数のパスの集合を「ループ」としてリストアップする
。一般にＮノードリングのフルメッシュ網では、ループの構成パス数は２，３，…，Ｎパ
スとなり、構成パス数ごとのパタン数は、構成パス数ｉに対して NＣi であり、５ノード
リングで実現可能なループ数は26となる。
【００２６】
トラヒック偏差演算部１２は、各パスのトラヒック情報を入力し、ループ作成部１１で
リストアップされたループごとに、構成パスのトラヒック（割当ＴＳ数）に対応する標準
偏差（トラヒック偏差）を演算する。図３に、ループ19，20における構成パスとトラヒッ
ク偏差の関係を示す。ループ19は、パス７（Ｂ−Ｄ），パス16（Ｄ−Ｅ），パス18（Ｅ−
Ｂ）で構成され、それぞれのＴＳ数は７，２，５なのでトラヒック偏差は2.52となる。ル
ープ20は、パス11，16，19で構成され、それぞれのＴＳ数は３，２，３なのでトラヒック
偏差は0.58となる。
【００２７】
このようにして、ループＩＤ、パス数、構成パスと、トラヒック偏差を対応付けたルー
プテーブル１３が生成される。図２に示すループテーブル１３は、ループ１〜26について
、構成パス数２〜５の昇順および構成パスＩＤ１〜20の昇順にソートしている。
【００２８】
本発明の特徴は、ループ選択・組合せ演算部１４において、ループテーブル１３の１ま
たは複数のループを組み合わせてパスグループを作成するときに、トラヒック偏差が小さ
いループから選択し、かつ構成パスが重複しないループを組み合わせる。このとき、ネッ
トワーク情報から得られるパス数Ｍ（上記の例では20）に対して、作成するパスグループ
数Ｇ（例えば５）を設定すると、１パスグループの構成パス数の目安はＭ／Ｇ（例えば４
）となり、１パスグループの構成パス数の許容範囲をＭ／Ｇ±α（例えばα＝１とすると
３〜５）とする。１パスグループの構成パス数の許容範囲は、Ｍ／Ｇに対して非対称であ
ってもよい（例えば３〜６）。
【００２９】
ここで、トラヒック偏差が小さいループから選択するには、ループ選択・組合せ演算部
１４において、ループテーブル１３を構成パス数の降順に探索し、かつ同じ構成パス数で
はループＩＤの昇順に探索し、トラヒック偏差が閾値以下となるループを見つける方法が
ある。閾値以下のループがなければ、閾値をアップして同様の探索を継続する。この場合
には、構成パス数の多い方からパスグループとなるループが選択されるので、図４〜図６
を参照して以下に説明するように探索効率を高めることができる。
【００３０】
また、ループ選択・組合せ演算部１４において、ループテーブル１３をトラヒック偏差
の昇順にソートしておき、トラヒック偏差の昇順に探索してトラヒック偏差が閾値以下と
なるループを見つける方法でもよい。この場合には、探索する最初のループのトラヒック
偏差が閾値以下であればすぐにループが見つかり、閾値以下でなければ、それ以降のルー
プを探索する必要がなく、閾値をアップして同様の探索を継続する。
【００３１】
また、ループ選択・組合せ演算部１４において、ループテーブル１３を構成パス数ごと
にトラヒック偏差の昇順にソートしておき、構成パス数の降順にかつトラヒック偏差の昇
順に探索してトラヒック偏差が閾値以下となるループを見つける方法でもよい。この場合
には、構成パス数とトラヒック偏差の両面から探索効率を高めることができる。
【００３２】
また、ループ選択・組合せ演算部１４では、１または複数のループを選択してパスグル
ープが順次作成されるが、ループテーブル１３にはパスグループが作成されるごとに、パ
スグループに割り当てられていないパス（未割当パス）を記録しておく（詳しくは後述す
る）。
【００３３】
図４は、ループ選択・組合せ演算部１４の処理例(1) を示す。
図４において、ループ選択・組合せ演算部１４は、ループテーブル１３の構成パス数の
降順に、かつループＩＤの昇順にループを探索し、以下に示す条件を満たすループが見つ
かったときにパスグループテーブル１６に追記する。ここでは、構成パス数が５のループ
26、次に構成パス数が４のループ21，22，23，24，25の順、以下構成パス数が３，２のル
ープの順に探索が進む。
【００３４】
パスグループを確定する条件は、
(a) ループのトラヒック偏差が所定の閾値以下（例えば閾値が１）
(b) 構成パス数が所定の許容範囲（例えば３〜５）
とする。ここでは、構成パス数が５のループ26はトラヒック偏差が1.30で条件(a) を満足
しないので選択せず（図中の×）、次のループ21はトラヒック偏差が0.96で条件(a) を満
足し、かつ構成パス数が４で条件(b) を満足するのでパスグループ１として確定し（図中
の○）、ループ21の構成パス１，６，11，13をパスグループテーブル１６へ書き込む。
【００３５】
なお、条件(a) を満足するループがない場合は、閾値をアップした条件(a')等に変更し
ながら同様の探索を行う。また、条件(b) を満足しない場合は、パスグループに組合せる
次のループの探索を行い、組合せる複数のループの合計の構成パス数が条件(b) を満足す
るまで、条件(a),(a')，…を変更しながらループの探索を行う。
【００３６】
次に、パスグループ１を確定させたループ選択・組合せ演算部１４は、次のパスグルー
プを作成する準備として、パスグループ１のループ21の構成パスと重複するパスを含むル
ープを除外し、探索対象となるループを絞るためのループテーブル１３の更新を行う。こ
こでは、パスグループ１のループ21と、その構成パス１，６，11，13と重複するパスを含
むループ１，３，…，20，22〜26に「除外」のフラグをたて、ループテーブル13から除外
する。更新されたループテーブル１３を図４および図５に示す。このとき、未割当パスは
、全20パスからパスグループ１の構成パス１，６，11，13を除いた16パスとなる。
【００３７】
図５において、ループ選択・組合せ演算部１４は、ループテーブル１３の構成パス数の
降順に、かつループＩＤの昇順にループを探索し、上記の条件(a),(b) を満たすループが
見つかったときにパスグループテーブル１６に追記する。ここでは、構成パス数が３のル
ープ15，16，19、次に構成パス数が２のループ２，４，６，７，９，10の順に探索が進む
。しかし、いずれのトラヒック偏差も１を超えていて条件(a) を満足しないので、閾値を
例えば２にアップした条件(a')に変更して同様の探索を行う。この場合、ループ15はトラ
ヒック偏差が1.15で新たな条件(a')を満足し、かつ構成パス数が３で条件(b) を満足する
のでパスグループ２として確定し、ループ15の構成パス２，12，17をパスグループテーブ
ル１６へ書き込む。
【００３８】
なお、ループテーブル１３を構成するループ数が所定数以下になった場合に、ループテ
ーブル１３の構成パス数の降順に、かつループＩＤの昇順にループを探索する方式ではな
く、ループテーブル１３をトラヒック偏差の昇順にソートしておき、全ループをトラヒッ
ク偏差の昇順に探索する方式に変更してもよい。
【００３９】
次に、パスグループ２を確定させたループ選択・組合せ演算部１４は、次のパスグルー
プを作成する準備として、パスグループ２のループ15と、その構成パス２，12，17と重複
するパスを含むループ２，４，９，16がループテーブル13から除外される。更新されたル
ープテーブル１３を図５および図６に示す。このとき、未割当パスは、全20パスからパス
グループ１の構成パス１，６，11，13と、パスグループ２の構成パス２，12，17を除いた
13パスとなる。
【００４０】
図６において、ループ選択・組合せ演算部１４は、ループテーブル１３の構成パス数の
降順に、かつループＩＤの昇順にループを探索し、上記の条件(a'),(b)を満たすループが
見つかったときにパスグループテーブル１６に追記する。ここでは、構成パス数が３のル
ープ19、次に構成パス数が２のループ６，７，10の順に探索が進む。しかし、ループ19の
トラヒック偏差は２を超えて条件(a')を満足せず、次のループ６もトラヒック偏差は２を
超えて条件(a')を満足せず、次のループ７はトラヒック偏差が1.41で条件(a')を満足する
が、構成パス数が２で条件(b) を満足しない。よって、組合せるべきループの探索を続け
る。しかし、トラヒック偏差が２以下の条件(a')を満足するループがないため、閾値を例
えば３にアップした条件(a")に変更して同様の探索を行う。
【００４１】
この場合、構成パス数が３のループ19はトラヒック偏差が2.52で条件(a")を満足するが
、その構成パス18がループ７の構成パスと重複するので不可となり、次のループ６が対象
となる。ループ６はトラヒック偏差が2.12で条件(a")を満足し、かつ構成パスの重複もな
く、さらに構成パス数が２でループ７と合わせて４となり、条件(b) を満足する。よって
、ループ７，６をパスグループ３として確定し、その構成パス７，８，14，18をパスグル
ープテーブル１６へ書き込む。
【００４２】
次に、パスグループ３を確定させたループ選択・組合せ演算部１４は、次のパスグルー
プを作成する準備として、パスグループ３のループ６，７と、その構成パス７，８，14，
18と重複するパスを含むループ19がループテーブル１３から除外され、ループ10が残る。
更新されたループテーブル１３を図６および図７に示す。このとき、未割当パスは、全20
パスからパスグループ１，２，３の構成パスを除いた９パス（３，４，５，９，10，15，
16，19，20）となる。ループ選択・組合せ演算部１４は、ループテーブル１３で探索可能
なループが１または０になった時点で処理を終了し、パス振分演算部１５に通知する。
【００４３】
図７において、パス振分演算部１５は、未割当パス３，４，５，９，10，15，16，19，
20をパスグループ４，５に振り分ける。ここでは、パスグループテーブル１６に残ってい
るループ10の構成パス16，20をパスグループ４に振り分け、残りの未割当パス３，４，５
，９，10，15，19について、パスＩＤの昇順に２パスをパスグループ４とし、残り５パス
をパスグループ５として振り分ける。あるいは、単純にパスＩＤの昇順に４パスをパスグ
ループ４とし、残り５パスをパスグループ５として振り分けてもよい。
【００４４】
以上の処理により完成したパスグループ１〜５からなるパスグループテーブル１６は、
図７に示すものとなる。スケジュールテーブルは、このようなパスグループテーブル１６
に基づいて作成されるが、例えばループを含むパスグループ１〜４は、スケジュールテー
ブル上でＴＳの凹凸が抑制され、ＴＳリソースを有効活用したスケジューリングができる
ことがわかる。
【符号の説明】
【００４５】
１１  ループ作成部
１２  トラヒック偏差演算部
１３  ループテーブル
１４  ループ選択・組合せ演算部
１５  パス振分演算部
１６  パスグループテーブル
【図１】
2016100679.tif 000003
【図２】
2016100679.tif 000004
【図３】
2016100679.tif 000005
【図４】
2016100679.tif 000006
【図５】
2016100679.tif 000007
【図６】
2016100679.tif 000008
【図７】
2016100679.tif 000009
【図８】
2016100679.tif 000010
【図９】
2016100679.tif 000011
【図１０】
2016100679.tif 000012
【図１１】
2016100679.tif 000013