複数サービスを提供する通信設備の選定手法に関する研究
2005MT107 鈴木 一弘
2005MT113 武田 裕平
指導教員 奥村 康行

1. はじめに
近年，新規インフラを引く必要のあるＦＴＴH の普及が進み，AＤＳＬからＦＴＴＨへの配線の移行やサービスの多様化，加入世帯の増加などがあり，数百万配線を管理する通信事業所のビル内では，非常に多くの配線開通，変更，削除の要求が発生している．
この膨大な配線経路で，これら全ての行為を人間の手のみで行うことは容易ではない．特に膨大な配線経路データを視覚からの確認となると，人的ミスが発生する確率が高くなる他，検索に多大な時間を要する．そこで，先行研究では，膨大な配線データから顧客のサービス要求に最適な配線経路を迅速且つ正確に選定するため，制約充足問題 （Constraint SatisfactionProblem，以下 CSP と略記） を応用した選定手法を提案している．本研究では，先行研究で提案されたアクセスネットワークモデル[1][2]に，新たに WDM を設置したモデルを考え，CSP を応用したプログラムを二通りの方法で作成した．最適化ソフトウェアの Cplex(以下，Cplex と略記)によるプログラムについては鈴木が，C 言語によるプログラムについては武田が担当した．

プボックスの中には，光スプリッタが組み込まれているため，ドロップボックスの種類にもよるが，１つのドロップボックスで複数の顧客に配線することが可能となる．
CR，J-CR1，J-CR2 とは，ケーブルラック（以下，cr と略記）のことである．cr とは，コネクトポート（以下，CP と略記）がたくさん集まった箱のことである．この cr 内の各CP には，cr 内部を配線せず，cr 外部を予め，ドロップボックスから CR までの配線，CR から J-CR1 までの配線，
J-CR1 から J-CR2 までの配線，J-CR2 から OLT までの配線を接続しておく．そして，顧客からの要望があった
際，制約条件を満たすよう，cr 内の各 CP を図 2 のように接続することで，サービス提供が可能となる．
WDM とは，光波長分割多重方式の装置のことである．
これは，光ファイバを通過する光信号が，他の波長の光信号と干渉しないという性能を利用し，一つのファイバで複数の光信号を送ることが可能となる．
OLT とは，データや映像などのサービスを伝送する装置のことで，光回線終端装置という．

2. 制約充足問題（CSP）とは
CSP は，ある問題に対して複数の制約を見つけ出し，この複数ある制約を満たすもの，状態を見つけ出す手法である．[3][4]CSP の中の複数の制約を定式化することにより，制約をより明確に表すことが可能となる．これを CSP 定式化という．また，CSP 定式化をすることにより，プログラム中に複数の制約条件を表せ，条件分岐させることに役立つ．

図 1．顧客の要望後のアクセスネットワークモデル図

3. 通信設備の選定について
本研究では，顧客がどのサービスを受けたいのかに基づき，通信事業所外の各顧客から通信事業所内の光回線終端装置までの配線開通，変更，削除を行っていく際，どのような配線経路でサービス提供が実現されるのか．図 1 のようなアクセスネットワークモデルを構成し，検証した．
3.1 アクセスネットワークのモデルについて
ドロップボックスとは，電信柱の辺りにある白いボックスのことで，別名「光クロージャ」と言われている．このドロッ

図 2．要望があった際の cr 内の接続
3.2 モデルに対する CSP 定式化について
本研究では，WDM の性能を活かし，WDM の後ろに新たに J-CR2 を設置することで，J-CR2 の内部を各サービスに対応した配線選定をするだけで，顧客にサービス提供ができるようになり，アクセスネットワーク上での配線開通が，より一層自由度が高まり，顧客からの要望により柔軟な対応ができる構成を考えた．

3.2.1 CSP 定式化の例について必要がある．これは，CSP 定式化をする前に各部位を変CSP 定式化を行うには，以下のような手順を踏む．
数宣言しなければ，制約条件を定式化することができな
例えば，顧客側からのドロップボックス番号と通信事いからだ．そこで，以下のように変数の宣言をした．
業所側からのドロップボックス番号が一致してなくてはな
らないと制約がある時，図 3 のように顧客側からみたドロ＜ドロップボックスとＣＲ間の変数＞
ップボックス番号を変数 X，通信事業所側からみたドロッ・ドロップボックス 番号：Oa
プボックス番号を変数 Y とする．変数 X={1，2}，Y={1，2}・ドロップボックスのＣＰ番号：Obが与えられた時，この制約を満たす変数 X，Y の要素は・CR 番号：Oc
X={1}の時，Y={1}にならなくてはならない．つまり，制約を・CR のＣＰ番号：Od
定式化すると X=Y のようになる．このように制約を抽出し，＜CR と J-CR1 の間の変数＞
その制約に対する変数を宣言し，その変数を用いて制・CR 番号：IOa
約に当てはまるよう式にする．これが CSP 定式化の手順
・CR の CP 番号：IOb
である．
・J-CR１番号：IOc
・J-CR１の CP 番号：IOd
ドロップボックス＜J-CR1 と OLT 間の変数＞
・J-CR1 番号：IEa１・J-CR1 の CP 番号：IEb
・EQP 番号：IEc
・EQP のパッケージ（PKG）番号：IEd＜J-CR1 と WDM 間の変数＞
２・WDM 番号：IWa
通信事業所
・WDM の CP 番号：IWb
顧客・J-CR1 の CP 番号：IWc
図 3．CSP 定式化の例＜WDM と J-CR2 間の変数＞
・WDM 番号：Wa
3.2.2 モデルの制約条件について・WDM の CP 番号:Wb
本研究のアクセスネットワークモデルには，どのような・J-CR2 番号：Wc
制約条件があるか．考えられる制約条件を検証した．
・J-CR2 の CP 番号：Wd
1．顧客から見たドロップボックスの番号と CR から見た
＜J-CR2 と OLT 間の変数＞
ドロップボックスの番号は，一致してなくてはならな
・J-CR2 番号：Eaい．
・J-CR2 の CP 番号：Eb
2．CR の CP が互いに繋がっているか，ドロップボック
・EQP 番号：Ec
ス側からみた CR の CP が空きであるか，J-CR1 から・EQP のパッケージ（PKG）番号：Ed
みた CR の CP が空きでなくてはならない．
＜顧客の変数＞
3．J-CR１の CP が互いに繋がっているか，CR からみ・サービスタイプ：Tた J-CR1 の CP が空きであるか，J-CR2 からみた・ドロップボックス番号：Ua
J-CR1 の CP が空きでなくてはならない．
＜光回線終端装置（OLT）の変数＞
4．J-CR1 からみた WDM と J-CR2 からみた WDM が・サービスタイプ：Ee
同一でなくてはならない．これを前提とした上で，・EQP 番号：Ef
J-CR2 からみた WDM の CP が OLT の EQP タイプ
・EQP のパッケージ（PKG）番号：Egと繋がっているか，J-CR1 からみた WDM の CP が空きであるか，J-CR2 からみた WDM の CP が空き
3.2.4 モデルの CSP 定式化についてでなくてはならない．
この変数宣言した変数を用いて，制約条件を CSP 定
5．J-CR2 の CP が互いに繋がっているか，J-CR1 から式化した．
見た J-CR2 の CP が空きであるか，OLT から見た
<P1>Ua=Oa
J-CR2 の CP が空きでなくてはならない．
<P2>Od=IOb∨Od=NULL∨IOｂ＝NULL
6．顧客の指定したサービスタイプと OLT のサービス<P3>IOｄ＝IEｂ∨IOｄ＝NULL∨IEｂ＝NULL∨IWｃ＝タイプは一致してなくてはならない．
NULL
3.2.3 モデルの変数宣言について
この制約条件に基づき，CSP の定式化を行う前に，まず CP 番号や顧客，サービスなどをすべて変数宣言する<P4>IWa＝Wa（Wb＝Ec∨IWｂ＝NULL∨Wb＝NULL）<P5>Wd＝Eb∨Wd＝NULL∨Eｂ＝NULL<P6>T＝Ee3.2.5 CSP 定式化の説明について<P1>ドロップボックスに関する説明
Ｕa と Oa は，どちらもドロップボックスの変数である．
Ua=Oa は，ドロップボックスが同じでないと，接続することができないこと表している．
<P2>CR に関する説明
Od=IOb は，スプリッタの関係で同じドロップボックスからの配線であると，他の顧客によりすでに開通された配線は通過することができるということを表している．
Od=NULL∨IOb=NULL は，配線が開通してない時のことである．この時は空いているポートを探していくということを表している．
<P3>J-CR1 に関する説明
IOd=IEb は，スプリッタの関係で同じ CR からの配線であると，他の顧客によりすでに開通された配線は通過できるということを表している．
IOd=NULL∨IEb=NULL は，配線が開通してない時のことである．この時は空いているポートを探していくということを表している．
<P4>WDM に関する説明
IWa=Wa は，J-CR から見た WDM 番号と J-CR2 から見た WDM 番号が同じでなくてはならないということを表している．
IWa=Wa を前提とした上で，Wb=Ec は，他の顧客によりすでに開通された配線は通過できるということを表している．また，IWb=NULL∨Wb=NULL は，配線が開通してない時のことを表している．この時は空いているポートを探していくということを表している．
<P5>J-CR2 に関する説明
Wd=Eb は，WDM の関係で同じ WDM からの配線であると他の顧客によりすでに開通された配線は通過できるということを表している．
Wd=NULL∨Eb=NULL は，J-CR2 内の配線が開通してない時のことである．この時は空いているポートを探していくということを表している．
<P6>サービスに関する説明
T と Ee は，どちらもサービスタイプの変数宣言である．T=Ee は，顧客の要望するサービスタイプと OLTのサービスタイプが同じでないと，接続することができないこと表している．

4. CSP 定式化を用いた制約プログラム
CSP 定式化により，制約条件を的確にまとめることができた．この CSP 定式化した制約条件をプログラムに組み込み，制約プログラムを用いることで，人間の手で配線経路選定するより，迅速且つ正確に実行することが可能か検証した．

4.1 アクセスネットワークモデルの規模
本研究では，図 1 のアクセスネットワークモデルに対応したプログラムを，C 言語と Cplex の環境で作成し，双方のプログラムのアクセスネットワークモデルの規模を，
表 1 のように設置した．双方の規模が異なるのは，Cplexが変数制限のあるタイプで実行したため，C 言語と同じ規模での比較ができなかった．
表 1．アクセスネットワークモデルの規模
C 言語
Cplex
顧客の世帯数30,000 世帯

100 世帯CR，J-CR1，J-CR2 のCP 数
スプリッタ分岐の種類

各 35,001
ポート局外 8 分岐
局内 4 分岐
3 種類
7 種類

13，4，12ポート

光回線終端装置の種類
サービスの種類

4.2 プログラムの開発規模とその流れ作成した双方のプログラム規模は，C 言語が main 関
数と sub 関数を合わせて 1,179 ステップ，Cplex が main
関数 280 ステップ程度，data 関数 10 ステップ程度である．
まず，サービスを受けたい人の人数を決め，その人数の配線経路選定にかかる検索時間と最適配線経路を表示するプログラムを作成した．検索時間を短縮し，迅速且つ正確に配線経路選定を行うことが可能か，C 言語とCplex との双方を比べ，検証した．以下，プログラムの大まかな流れを図 4 で示す．

図 4．プログラムの流れ
プログラムの流れを更に詳しく記載すると，以下①から⑦のようになる．以下，サービスの種類をα，β，γの三種類とする．
①：顧客が受けたいサービスをα，β，γの中から一つまたは複数個選ぶ．
②：ドロップボックスの中の 8 分岐スプリッタについて，何個目の 8 分岐スプリッタを通過するかを，顧客が受けたいサービスに対応させ決める．また，その 8分岐スプリッタの 8 つの枝の内，どの枝を通るのかを決める．
③：CR の CP について，CR と J-CR1 間にある何個目の 4 分岐スプリッタを通過するかを決める．
④：③で決めた CR と J-CR1 間の 4 分岐スプリッタの 4つの枝の内，空いている枝を選定し，どの枝を通るのかを決める．ドロップボックス内の同一 8 分岐スプ
リッタを通過した顧客の配線選定については，既に繋がっている 4 分岐スプリッタの枝を選定する．
⑤：J-CR1 の CP について，空いている配線を選定する．サービスが 1 つの場合は光回線終端装置に繋げる．サービスが複数個の場合は WDM を選定する．
⑥：各 WDM から出ている 4 本の Fiber から J-CR2 内で要望されている各サービスを繋ぐ．4 本のうち，繫ない Fiber は無反射終端に繋ぐ．
⑦：プログラムにより選定された最適配線経路とその検索時間を出力する．

図 5．出力結果の配線経路図
配線経路選定は，Cplex 環境下だと，顧客 100 人分の検索時間は約 0.735 秒，C 言語にて 30,000 人分を検索すると約 33 秒で計算された．100 人当たりでは約0.0767 秒に相当する．また，Cplex 環境下では，変数制限のあるタイプで実行したため，100 人分以上の配線選定ができなかった．

5. まとめ

4.3 プログラムの動作結果
本研究で構成した図 1 のアクセスネットワークモデル
に関し，作成した制約プログラムを用い検証した．複数の顧客がサービスをランダムで依頼すると仮定して，本研究で完成したプログラムを実行させた．
まず，何人の顧客がサービスを依頼するのかを決定する．プログラム上で各一人一人の顧客についてランダムで受けるサービス(3 種類)，計 7 通りのサービスを割り振り，どの配線経路が最適なのか．また，その結果を出すまでの検索時間は何秒かかるのか，を表示させる．
例えば，C 言語と Cplex のプログラムにて，100 人の顧客の配線経路の検索を行う．その中の一例として，顧客100 番の配線選定結果と，それに対応する配線経路図を図 5 に示す．

本研究で，通信事業所で行われる配線選定に関して，CSP を応用し，定式化することで，プログラム中に組み込むことが可能になり，配線経路選定をより迅速且つ正確に行うことが可能であることを示した．
本研究では，C 言語環境下での制約を組み込んだプ
ログラムと，Cplex との双方からの検証結果から，双方に利点があることがわかった．
C 言語のプログラムは，Cplex に比べプログラム規模が大きくなったが，細かい制約指定まで可能なため，処理速度は Cplex に比べ，比較的速かった．
一方，Cplex は，プログラムに定式化した制約を組み込むだけで最適解を求めることができ，プログラムを小さくまとめることができた．しかし，処理速度が C 言語に比べ，比較的遅かった．

顧客：00100↓
ドロップボックス内のスプリッタ番号（8 分岐スプリッタ）：
00027 番目
8 分岐スプリッタの枝：5 本目↓
CR の CP 番号（4 分岐スプリッタの番号）：00017 番目
4 分岐スプリッタの枝：1 本目↓J-CR1 の CP 番号（WDM 全体の番号）：00026 番目↓
サービスを 2 種類のみ繋ぐ WDM2 の番号：00011 番目
J-CR2 の CP 番号（α，β，γ，無反射終端）：（22 番目，*，21 番目，*）※無反射終端を[*]とする↓
EQP タイプ：α-OLT と γ-OLT

参考文献[1] Kenichi Tayama, Shiro Ogasawara, Tetsuya
Yama-mura, and Yasuyuki Okumura ：“Flexible
Allocation of Optical Access Network Resources
Using Constraint Satisfaction Problem”, IEICE
TRANS．COMMUN. , VOL.E90-B, NO.7,
pp.1674-1681, JULY 2007.
[2] 野末晴久, 中島一, 田山健一, 山村哲哉 : “複雑な所外設備に対応する柔軟な光アクセス設備選定手法”, 信学総合大会, B-14-3, pp.525, 2006.
[3] 伊庭斉志 『探索のアルゴリズムと技法 基本的アプ
ローチとその評価』 サイエンス社, 2002 年.
[4] 石畑清 『アルゴリズムとデータ構造』 （岩波講座
ソフトウェア科学３）岩波書店, 2000 年.
[5] ILOG：“ＩＬＯＧ ＯＰＬ Ｄｅｖｅｌｏｐｍｅｎｔ Ｓｔｕｄｉｏ”，
http://www.ilog.com/products/oplstudio/trial.cfm.
,2008.5.