超 大 容量 映像配 信 ネットワー クに向けた波長群 マル チキャストの実 現 及び構 成 に関する研 究長谷川 浩
名古屋 大学 大学 院 工 学 研 究科電 子情報 システム専 攻〒4 6 4 ‑ 8 6 0 3 愛 知 県名古 屋市 千種 区不老 町

Grooming and Design of Waveband Muiticast Trees in Hierarchica1 0pticalorks for Future Video Distribution Services
Path Neti‖
Hiroshi Hasegawa
Dept.of Electrical Engineering and Oomputer Science,Nagoya University
Furo―cho,Chikusa一ku,Nagoya 464‑8603,」APAN
1,ま えがき
現する受動素子を用 いて、効率的にデータの複製 をブロードバンドアクセスの急速な進展により、バックボ実現する。一方 で、光 パスネットワークでは光 パスを電ーンネットワー クにおけるlPトラフィック量は大幅 に増気信号 への変換なしに経路制御するため、送信元 か加し続けている。また、高精細映像配信等 の大容量を要求する新たなサービスの登場 により、今後もこの低傾 向が続くと予 想 される。そこで現在、大容量化 口ら受信先に至るまで同 一 の波長 が使用され(波長連続性制約)、かつ経 由する光 ファイバの中で、他 の全消費電 力化を目指し、光ファイバ 中に多重された波長 の異なる多数 の信号(波長 パス)を 、波長をラベルる。波長連続性制約 は、マルチキャスト通信を行わないネットワークにおいても、光 パスの経路と波長割 当をとして電気信号 への変換なしに光 スイッチで経路制御する光ネットワーク(一階層光 パスネットワーク)が 実適切 に割り当て光ファイバ資源 の最小化を目指す最適化を極めて困難(NP完 全)に する。しかし、光 パス用化され始めているが、将 来予測される膨大なトラフ
ィックは必 要 なファイバ数 とのべ波長 パス数 の大幅なマルチキャストでは、マルチキャストする通信経路 の最適化(シュタイナー木構築問題)自 体 がすでに計 算 コ増大を意味する。ファイバ数や波長数 の増大 は、波ストの高 い問題 で有り(NP困難)、複数 の通信 の関係性を考慮 しながらネットワー ク全体での光 パスの配置長単位 で経路制御する光スイッチの規模拡大をもたらし、ノードの高 コスト化を招く。そこで、複数 の波長パスを波長群 パスとして論理的 に束ね 一 括して中継処
理 し、光 スイッチ規模を抑制しながら超大容量通信を実現する多階層光 パスネットワー ク[13]が 検討 されている。多階層光 パスネットワークを効率 的に実現する上では、クロスコネクトノードのアーキテクチャ[4‑7]、波長群 パスを扱う上で必要となる合分波器[8,9]、そしてパスの階層構造を維持 しながら適切 に波長 ・波長ー群番号 と経路を割り当てるネットワ ク設計手法[10,11]の 連携が不可欠 である。
一 方、従来型 の光 パスネットワークにおいては、映o ht)サービスを効像配信等 のP2MP(pOht to mttt中率化するために、光 パスマルチキャスト技術 が検討 されてきた。P等 の電気処理 に依存するネットワークでは、デー タの複製を電気的に作成することで複数宛先へのデータ配信を可台ヨこする。これに対し、光ネットワークでは、スター カプラと呼ばれる光 の合流 口
分配 を実ての光 パスと異なる波長を用 いていることが必要 であの準最適値を導くことが一つの大きな課題 である。
本研究 では、波長群 パスによる超大容量化 の可能性 と、光 パスマルチキャストの重要性 に鑑 み、階層化
光 パスネットワークにおける効率的なマルチキャスト通信 の実現を目指した。これ にあたり、階層化光 パスネ
ットワークのノード装置 におけるマルチキャスト動作 の実現法をまず示 した。続 いて、波長 マルチキャストツリ
ー設立要求の集合 として与 えられる通信需要を、的確 に波長群 マルチキャストツリーに収容 してこれを最適化し、占有 ハードウェア量を削減する、新 たな波長群 マルチキャストネットワーク設計手法を新 たに提 案 した。この手法 では、波長マルチキャスト通信相互間の類似性を測る尺度を新 たに導入 し、互 いに類似 したと見なせる波長 マルチキャスト設立要求を探 索する。続いてこれらの要求を波長群 マルチキャストツリー設計として定式化し、単 一 のシュタイナー木構築 問題 として整数線形計画 問題 とし、解決する。数値実験 により、

一
光 ノー ド装 置 における占有 ポ ー ト数 が、従 来 型 の 階
層 型 光 パスネ ットワー クにおけるそれ と比 較 して大 幅 に削 減 され ることを示 した。
2.階 層 化 光 パ スノー に の マル チキ ャスト実 現
光ファイバ通信で一般的 である高密度 の波長多重通信(DWDM:Dense Wavelength Division Muttiplexing)では、複 数 の波長 の異なる信号を多重 して光ファイバ 中を伝 送 し、伝 送後 に波長 が異なることを利用 して分離することで、単一 光 ファイバをあたかも複 数 の光 ファイバが並列に存在す

図 3階 層型 OXC(HOXC)るように扱 い、大容量通信 を実現 している。具 体的 には、C波長 パスを扱う光クロスコネクト(Optic』Cross―oonnect,OXC)は 図 2に示 すような構造を持 つ。一 方、波長 パスと波帯 と呼 ばれ る特 定の周波数領域 において、肝U―Tで 国際

長群 パスの階層化光 パスを扱う光クロスコネクトノー ドは、一的 に標準 化された等 間隔周波数グリッド上で定 義される波長 が用 いられる。現在 一 般的であるのは、100GHz間 隔 の般 に、図 3に示 すように波長群 パスを扱う波長群クロスコネ

40波 長、50GHz間 隔 の80‑96波 長 である。
これ ら多数の波長を、適 当なルー ルに従 つて幾 つかのグ
ルー プに分割 し卜可能な限りこのグルー プ単位でルー ティングするのが多階層光 パスネットワー クである。分割後 の波クトと、波長 パスを扱 う波長クロスコネクトとをスタックした構造を持 つ。階層化光 パスネットワー クでは、可能な限り波長群 パス単位 でのルー ティングを行う。また、波長 パス単位での処理が必 要 となる、波長 パスのadd/drop処 理や、複も波長群 についても定義される。また、波長 パスは必ず波数 の波長群 パス間 で、包含され ている波長 パスを入れ 替えるgrooming処 理を行う際 には、当該波長群 パスは一 端そのノードで終端 され、波長 パス毎 に分解 された上で波長長群 パスを経 由して伝送される(図1)。なお、以降では、通クロスコネクHこてルー ティングが行われる。

パスを単 にパスと呼び、poht to
常 のpoint to pointのmukipointのマルチキャストツリー を単 にツリー と呼ぶ。ツリ波長群 クロスコネクトおよび波 長クロスコネクトの実 現 には、合波器[9]と マN)
平面光波 回路等 で実現 された分波器 ・ー も波長及び波長群それぞれに定義され、波長 ツリー は波クススイッチを組み合わせるアー キテクチャ[5]と 、波長群長群 ツリー のみ に含まれうる。

選択 スイッチ[12]お よび波長選択スイッチを組 み合わせるアーキテクチャ[6](図 4)が主 に想 定され る。本研究では

長番号 のグルー プは波長群 と呼 ばれ 、パスは波長 について

近年の波長選択 スイッチの普 及とスイッチ規模 削減 に向け
optical fiber
wavebanS path/!
/wavetength path

た検討 の進展 に鑑みて、図 5に示す、add/drOp部 分を分離 した、選択 スイッチベー スのノードアー キテクチャを仮定して議論を行 つた。この選 択 スイッチベー スのノードでは、入力光ファイバからの信号 はスター カプラにより複 製 され て全ての選択スイッチに配信され、各選択 スイッチ側ではいずファイバの関 係
図 1波 長 パス ・波長群 パス ロ

れの入 カファイバからの信号を出力するかを選択する。複数 の波長群選 択 スイッチが、同 一 入 カファイバからの信号を選択 したとき、波長群 パスのマルチキャスト動作 が実現される。この際、電 気信号 へ の変換を経ない、受動素子 であるスター カプラのみを用いた信号 複製 のため、入 力と出力

図2‑階層型OXCの双 方で波長群 パスは同 一 の波長群を用 いるという制狽」
約 は付与されるものの、効率 的なマル チキャストが可 能 になる (図6)。
一波長群 マルチキャストの実現 で必 要 となるもう つの処

理が、波長群 マル チキャストツリー に含まれている幾 つかの波 長 マルチキャストツリー の一 部 から信号を受信 インター フ

波長 マルチキャスト

ェー スまで導く処理(drop処 理 )で ある。このdrop処 理においては、波 長群クロスコネクHこおいては、隣接 ノードヘ配
信 される信号と、波長クロスコネクHこ導く信号 の双方を出力し、波 長クロスコネクHこおいてはdrop処 理 が必要 と波長群 マルチキヤストなる波長のみを抽 出するという形 で実現する。

叩▲

WXC

I 図! ￨ l i l
使用ポー ト数 :l

図 6ポ ー ト数削減 の例

3マ ル チキ ャス 嬬 要 の 類 似 性 に基 づ くツリー 集 約ーを用 いた 波 長 群 マル チキ ャストツリ 構 築 法
3日
1マ ル チキ ャス 踊 要 の 類 似 性 の 尺 度
前節 で述 べ たように、多階層光 パスネットワー クにおいては複 数 の波長 パスが集約され 、波長群 パスに収容される。
波長変換 のための装置を仮定 せず、ある波長 パスが複数WBXC
図 4 従 来 型 選 択 スイッチ ベ ー ス H O X C
ｐｄ ▲Ю▲の連 続した波長群 パスを経 由する場合、それらの波長群パスは同 一 の波長群 に対応 していなくてはならない。また、波長群 パスには適切な経路 ,波長群 番号 が与えられる。
以上のプロセスを適切 に実施 し、最 終的 に必要となるフアイバ数およびノー ドのハー ドウェア規模 を極 力少なくすることが目的となる。
波長群最適化 に関してはこ
後 者 の波長群 パスの経路 ・れのみをとつてもNP完 全で計算 困難 である。しかし前者 は多階層光 パスネットワー クに特有 の最適化 であり、特 に波長群 パスをどのノード間 にどれだけの本数を設定するか、および各波長 パスをいずれ の波 長群 パスに収容するかのいずれ についても高 い 自由度 がある一 方 で、探 索領域 が広大であつて続く問題が計算 困難 であることから、目的関数を直接最適化することは難しく、近似的な尺度を導入してWBXC
図 6 add/drop分
離型選択 スイッチベース HOXC

前 者 の課題 について準最適解を得 た後、後者 の課題を近似的 に解くことが一 般的 であり、おそらく現実的なアプローチである。
これまで、このパス配置最適化問題 においては、始点 口終点 が近い波長 パスの集合を探 索 し、これ を波長群 パス網 に同時 に収容するという戦略 が有効であることが示されている [11]。この戦略 の有効性 は、始 点 ・終 点が近 い波
一長 パスを適切な地 点で一 端集約し、集約後 に単 の波長群 パスに収容 していること、この波長群 パスの利用率 が高く、かつ波長単位 の処理をせずに多くの中継 ノー ドを経 由する

グルーカ 後 、波長 ツ舛 設定要求集 合 ￨よ嫌 も ごれ を 戸ことから生まれている。
一波 長 ツリー では終 点 の数 が複数存在 しうることから、同力控 集 合をなが 窃 彩 宏 九の波長群 マル チキャストツリー に効率よく収容できるというこ

上記で得られた波長ツリー 要 求 の各集合 について、共通 の始点 から、波長ツリー の終 点の和集合を端 点とする最 小重とを評価 する上では、全く別個 の評価 尺度を導 入する必要がある。そこで我 々は、各ツリー における終 点の集合について、集 合 の拡張と、一 般化 した包含関 係を定義 して、包含みツリー を整数線形計画問題として定式化 し、lBM CPLEX
等 のソルノ村こよって解く。(上記集約 により単 一 ツリー の構に最低 限必要 な集 合 の拡張度合 いを尺度とする方 式を提築問題 に帰着されるため、最適木を直接計算 した。定式案する。

化の詳細は本研究 に関わる学 会原稿等 をご覧 いただきたい)

3 . 2 炊 拡 大 と一 般 化 包 含 関 係
ラフ中のノード及びエッジ無向グラフG=(LE)(LE:グk)全体の集合)に おいて、ノード集合V。⊆Vのk次 拡大イを以下で定義する。

tXtX十k)iitフ
C711n】
θたれ,フp("■)≦Чさ〕
鳥ただし、んθp(れ,■)(純 ,れC7)は 、mか らnまでの最 短 のホップ数 (たどり着 くために最 小 限必 要 な経 由リンク数 )で ある。
このとき、二 つのノー ド集 合 71,72⊆ y間 の 距 離 d"を 以下で定 義 する。

図 79x9正方格子型トポロジを)θ)〕γ7 2イ・⊆d ( L晦″) = 叫n t y⊆ぢ比化 包 含 関 係 に基 づ く波 長 ツリー 集 約 および 波 長 群 ツリー 最 適 設 計 法
3日
3‑般Super headendよ り多数 のHeadendへ の映像配信アプ
リケーションを念頭 に置き、始点及び終点集合対で与えられる波長ツリー要求について、全てのツリーの始点は同一であるとする。ただし、終点集合 については必ずしも一致しないものとする。この時、提案する波長ツリー集約手続きの概要を以下 に示す。
図 8 British Telecomネットワー ク

基 X波 長 ソt,一集約法)
待 陶 物 含関係 ￨こ
波長群内 の 嬢 敦 郷 汐 吃 身 務 れた波長 ンリー設定'め為tK身
終 点集 合の距離おド
婁ぷ =〔 を.,…,tD〕tこー要求対 を選 おミてこれ シ 療 合浸 イ1をなち波長 ツiジ。初 〕の海
近 ι島もの波長 ツグ
翔 舷 秘 幹 汐 弱 諭 距離 おミ
ー要求 想 び さら1こ
和集 合をする。どの手続きを、藤 台ー要求 の 窟数 力喫 坊 初 【題離 力閉桟5波長 ノ!ブを購成 ラー要求 をま 切 脇 チる。これらの波長 ン1ブ」途定義)お｀値(男10個 の波 長群 に均 等 に分割 されているものとする。
単 一 のSuper headendより、複 数のheadendへの配信を模 擬するため、まず一 つの点をランダムに選 んでSuperheadendと なる始 点とし、残りの点からランダムに選 んだ20点をheadendの集 合とした (図8)。各波長 ツリー 設 立 要求は、この始点 から、後者 の点集合 からランダムに選択 した5点 への配信を実施するツリー の構築要 求として与えられ るものとする。波長 ツリー要求を複 数与え、前節 で示した提案法 により適宜波長群 ツリー 要求としてまとめた上で、シュ回図タイナー 木構築問題を解 いて波長群 ツリー を決定する。また、波長群 ツリー に集約を行わず、各波長ツリー 設 立要 求

○ ノー ド( 通信拠 点)

9始 点 ・終点配置 の例に対してシュタイナー 木構築 問題を解 いた、一 階層形光 パ
スネットワー クにおける最適波 長 ツリー も算 出し、比較に用いる(図9および10)。
以上の手続きを20回 繰り返して、ポー ト数を平均化する。続 いて、多階層光 パスネットワー クで必要となるポー ト数を、一 階層形光 パスネットワのそれで正規 化した値を図XX

軍 弧難X固̲波12に示す。効果はトポロジに依存するものの、適切な集約を実施することで大きくポー ト数が削減できることが示されXている。

【二尊 浄淳T文杓甲く働長 MCTl
― 波長 MCT2‑波 長 MCT35む す び□

i波長群 MCT

図 1 0 波 長 M O T の 構築 図 11波 長群 MOTの 構 築

本論文では,波 長マルチキャストツリーを論理的に東ねた
波長群マルチキャストツリーの階層化光パスネットワークヘの導入と,波 長群マルチキャストツリーの最適構築 による利用 ハードウエアの最小化を提案し,数 値実験によリスイッチポート数 の削減効果を明らかにした。

4数1値例

光信号 を直接処理可能なノード装置は相対 的 に高価 であり、そのハー ドウェア規模 は、アー キテクチャにより異なる

4' 7x78・‑フ x78・ 3095

8T B=4BI B二89x98=4‑9x9B・ 8‑一 ―09が、一 般 的 には入 出カポー ト数 で見積もられ る。以下 では、ー
従来 の一 階層型光 パスネットワー クにおいて波長ツリ の収容 に必要 となるポー ト数と、多階層型光 パスネットワー クにおいて、波長群 ツリー の収 容 に必要となるポー ト数を比較 し、波長群 ツリー として集約することで大きくポート数が削減されることを示す。
本評価 では、7x7および9× 9の正 方格 子形トポロジ(9x9のみ 図 7)およびBritish Tdecomネットワー ク(図8)を用 い、各隣接 ノー ド間 には十 分な本数 のフアイバが存在するものとする。各 ファイノ村こは80個 の波長 が収容され、この波 長は各 々が4もしくは8イ
国の波長 のグルー プとなる、20もしくはだ‐ ‐/ャ
‐十̲…

O S
081624324048566472

波長MCr亨マンド敏
図 1 2 提 案 手 法 におけるポ ー ト数 削減 効 果( B i 波 長 群 あたりの波 長 数 )80

6関 連 研 究 発 表
1.蜂須賀 悠介,長 谷川 浩,佐 藤 健 一,「階層化光パスネットワークにおける波長群 マルチキャスト配信」電子情報通信学会 2011年総合大会,2011年3月
ichi Sato,
2 Yusuke Hachisuka,Hiroshi Hasegawar Ken―
Design Algorithm of Waveband Muiticast Tree in
Hierarchica1 0ptical Path Networks that UtiHzes Groupingof Destination Node Sets,"

Proc SPIE 8310,831003( 2 0 1 1 ) , 2 0 1 1 年1 1 月
3 蜂 須賀 悠介, 長 谷 川 浩, 佐 藤 健 ― , 「受信 ノー ド群
間 の一 般化包含関係を用 いた波長群 マル チキャストツリー
設計法」フォトエックネットワー ク研究会学生ワー クショップ
予稿集, 2 0 1 2 年 3 月

7謝 辞
本研究を支援くださいました貴財団に厚く御礼申し上げます。
参 考 文献,Proct OFC,pp.356‑358,Feb.1999.
[1]K.Harada et.aに,Proct ECOC,pp.269‑270,Oct。 2000̀
[2]L Noirie ettaに[3]K.Sato and H.Hasegawa,lEiCE Trans Comrnun.,volE90‑B,noi 8,pp.1890‑1902,Aug 2007.
[ 4 ] X C a o e t t a L o, u」r n a l o f O p t i c a l N e t w o r k i n g , v o L 5 ,no,12,pp.1043‑1055,Dec.2006.
EiCE Trans Oommun,,vol E91‑B,[ 5 ] S . K a k e h a s h i e t , aI にno.10,pp.3174‑3184,Oct.2008[6]S,Mitsui et.aL,Proc,Photonics in Switching,S‑04‑1,2008.
l,Proc̀Photonics in Switching,Fri12‑2,[ 7 ] R . H ヤa k o e taⅢ
2009̀[8]S Chandrasekhar et.al,lEEE Photon TechnoL Lett,
vol.17,No.3,pp.579‑581,Mar 2005
,lEEE Photon Technol Lett,voL 1 9,
[9]S Kakehashiet.aに
no. 16,pp. 1197‑1199,Aug。 15,2007.
[10]S.Verrna?nd」.P Jue,OSA 3 0pt.Netw.,vo1 5,noll,pp.790‑806,Nov.2006[11]1.Yagyu et.aに,lEEE」 SAC,Supp.on 00N,voL 26,no.
6,Au宮 。2008,pp.22‑31.