超 大 容量 映像配 信 ネットワー クに向けた波長群 マル チキャストの
実 現 及び構 成 に関する研 究
長谷川 浩
名古屋 大学 大学 院 工 学 研 究科電 子情報 システム専 攻
〒4 6 4 - 8 6 0 3 愛 知 県名古 屋市 千種 区不老 町
Grooming and Design of Waveband Muiticast Trees in Hierarchica1 0ptical
orks 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次 拡大イ
を以下で定義する。
tX
tX十
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への配信を
模 擬するため、まず一 つの点をランダムに選 んでSuper
headendと なる始 点とし、残りの点からランダムに選 んだ20
点をheadendの集 合とした (図8)。各波長 ツリー 設 立 要求
は、この始点 から、後者 の点集合 からランダムに選択 した5
点 への配信を実施するツリー の構築要 求として与えられ る
ものとする。波長 ツリー要求を複 数与え、前節 で示した提
案法 により適宜波長群 ツリー 要求としてまとめた上で、シュ
回図
タイナー 木構築問題を解 いて波長群 ツリー を決定する。ま
た、波長群 ツリー に集約を行わず、各波長ツリー 設 立要 求
○ ノー ド( 通信拠 点)
9始 点 ・
終点配置 の例
に対してシュタイナー 木構築 問題を解 いた、一 階層形光 パ
スネットワー クにおける最適波 長 ツリー も算 出し、比較に用
いる(図9および10)。
以上の手続きを20回 繰り返して、ポー ト数を平均化す
る。続 いて、多階層光 パスネットワー クで必要となるポー ト
数を、一 階層形光 パスネットワのそれで正規 化した値を図
XX
軍 弧
難
X
【
二尊 浄
淳
T文
杓
固
_波
12に示す。効果はトポロジに依存するものの、適切な集約
を実施することで大きくポー ト数が削減できることが示され
甲
く
X
ている。
働
長 MCTl
― 波長 MCT2
-波 長 MCT3
5む す び
□
i波
長群 MCT
図 1 0 波 長 M O T の 構築 図 11波 長群 MOTの 構 築
本論文では,波 長マルチキャストツリーを論理的に東ねた
波長群マルチキャストツリーの階層化光パスネットワークヘ
の導入と,波 長群マルチキャストツリーの最適構築 による利
用 ハードウエアの最小化を提案し,数 値実験によリスイッチ
ポート数 の削減効果を明らかにした。
4数
1
値例
光信号 を直接処理可能なノード装置は相対 的 に高価 で
あり、そのハー ドウェア規模 は、アー キテクチャにより異なる
4
' 7x78・
-フ x78・ 3
095
8T B=4
BI B二8
9x98=4
-9x9B・ 8
-一 ―
09
が、一 般 的 には入 出カポー ト数 で見積もられ る。以下 では、
ー
従来 の一 階層型光 パスネットワー クにおいて波長ツリ の
収容 に必要 となるポー ト数と、多階層型光 パスネットワー ク
において、波長群 ツリー の収 容 に必要となるポー ト数を比
較 し、波長群 ツリー として集約することで大きくポート数が削
減されることを示す。
本評価 では、7x7および9× 9の正 方格 子形トポロジ(9x9
のみ 図 7)およびBritish Tdecomネ
ットワー ク(図8)を用 い、
各隣接 ノー ド間 には十 分な本数 のフアイバが存在するもの
とする。各 ファイノ村こは80個 の波長 が収容され、この波 長
は各 々が4もしくは8イ
国の波長 のグルー プとなる、20もしくは
だ
‐ ‐/ャ
‐十_…
O S
0
8
16
24
32
40
48
56
64
72
波長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 Grouping
of 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.,vol
E90-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,no
ll,pp.790-806,Nov.2006
[11]1.Yagyu et.aに,lEEE」 SAC,Supp.on 00N,voL 26,no.
6,Au宮 。2008,pp.22-31.
© Copyright 2024 ExpyDoc
