Comments
Description
Transcript
λグリッドネットワークにおいて デッドラインを考慮した波長割り当て
信学技報 TECHNICAL REPORT OF IEICE. 社団法人 電子情報通信学会 THE INSTITUTE OF ELECTRONICS, INFORMATION AND COMMUNICATION ENGINEERS λ グリッドネットワークにおいて デッドラインを考慮した波長割り当てスケジューリング 宮城 洋之† 林谷 昌洋† 石井 大介† 荒川 豊† 山中 直明† † 慶應義塾大学理工学部情報工学科 〒 223–8522 神奈川県横浜市港北区日吉 3–14–1 E-mail: †[email protected] あらまし 近年，光ネットワーク技術の発展によりグリッドシステムとして λ グリッドに関する研究が盛んに行なわ れている．また，グリッド環境を提供するサービスが登場している．サービスによってジョブの終了時刻に対する要 求が異なるため，デッドラインを考慮した波長割り当て方式を考える必要がある．従来のジョブスケジューリングで はデッドラインを考慮せず，ジョブ実行時間が最短となるように短期間で多くの波長タイムスロットを割り当てるた め，デッドラインが短い呼のブロック率が劣化するという問題がある．そこで本稿では，λ グリッドネットワークに おいてデッドラインが短い呼のブロック率を改善するために，デッドラインを考慮した波長タイムスロット割り当て スケジューリングを提案する．提案方式では，デッドラインに応じ長期間でタイムスロットを予約することにより， デッドラインの短い呼のブロック率を低減できる．計算機シミュレーションにより，デッドラインを考慮しない波長 タイムスロット割り当て方式と比較して，提案方式は低負荷時にブロック率を 1∼2 オーダ改善できることを示す． キーワード λ グリッド，デッドラインスケジューリング，波長割り当て，WDM，フォトニックネットワーク A Deadline-Scheduling Scheme for Wavelength Assignment in λ Grid Networks Hiroyuki MIYAGI† , Masahiro HAYASHITANI† , Daisuke ISHII† , Yutaka ARAKAWA† , and Naoaki YAMANAKA† † Dept. of Information and Computer Science, Faculty of Science and Technology, Keio University Hiyoshi 3–14–1, Kohoku-ku, Yokohama, 223–8522 Japan E-mail: †[email protected] Abstract A lambda grid system has been proposed as a huge computer grid system, based on an advanced photonic network technology. It is important to assign wavelengths for jobs in a lambda grid network. Considering with services and various services request such as the different end time of jobs. Thus, job deadline for wavelength assignment is very essential. The conventional job scheduling assigns a lot of time slots to a call in a short term in order to finish a job fast, so there is the problem that the blocking probability of short deadline calls is degraded. Therefore, we propose a deadline-scheduling scheme for a wavelength assignment in a lambda grid network to guarantee calls Qos. Our proposed scheme assigns time slots to a call in a long term according to its deadline. Thus, it can reduce the blocking probability of short deadline calls. Computer simulations show that our proposed scheme can reduce from one order to two the blocking probability compared with the conventional one under low load. Key words λ Grid, Deadline Scheduling, Wavelength Assignment, WDM, Photonic Network 1. ま え が き レージ，さらには観測機器，さまざまなデバイスなど，多くの ネットワーク技術の発展と計算機の高性能化に伴い，グリッ 規模な仮想計算機として機能させるインフラストラクチャを構 ドコンピューティングに関する研究が盛んに行なわれている [1]． 成する技術である．グリッドコンピューティングにより構成さ グリッドコンピューティングは，広域に分散した計算機やスト れた大規模仮想計算機を用いることで，単体の計算機では解読 リソースをネットワークを介して統合的に接続し，ひとつの大 —1— することが難しい大規模な科学技術計算や大量データの高速処 式では，デッドラインに応じて短い波長からタイムスロットを 理が可能となり，より高度な処理能力を得ることができると期 予約することにより，長期間でタイムスロットを予約する．そ 待されている．グリッド環境を実現するためには，地理的に分 の効果により，早い時刻，長い波長のタイムスロットをデッド 散したさまざまなコンピューティングに関する膨大なリソース ラインの短い呼が予約可能なタイムスロットとして確保するこ を動的に共有し，複数の計算機を用いて並列処理させることが とができる．さらに波長タイムスロットを有効に利用するため 重要な課題となっている．そのため，グリッドコンピューティ に仮予約を行なう．デッドライン短い呼が発生しなかった場合， ングでは，リソース情報やジョブの処理に必要な入力データ， 提案方式はデッドラインの短い呼に確保したタイムスロットを 出力データなど，大容量データの転送を行なう必要がある．そ 効率的に利用することができない．そこで提案方式はデータサ こで，近年の光ネットワーク技術の発展により，グリッド環境 イズ分タイムスロットを予約するのに加え，仮予約することで の構築に WDM(Wavelength Division Multiplexing) や光パス 波長タイムスロットの有効活用を図る．そのため，デッドライ を導入した λ グリッドに関する研究が行なわれている [2], [3]． ンを考慮しない波長タイムスロット割り当て方式と比較して， WDM 技術を用いることによりネットワーク全体の通信容量 提案方式ではデッドラインが短い呼のブロック率を大きく低減 が増加し，より高速なデータ通信が可能となり，光パスを設定 し，全体のブロック率を改善することができる．計算機シミュ することにより帯域が保証され，信頼性のあるデータ通信が可 レーションにより特性評価を行ない，提案方式の有効性を示す． 能となるためである．さらに，グリッド環境では波長情報もリ ソース情報として管理することが要求され，波長をタイムス ロットに分割し，管理するシステムが提案されている [4]∼[6]． 2. システムモデル 図 1 に λ グリッド環境モデルを示す．グリッドコンピュー 波長情報を管理することにより，ネットワークの状況をより詳 ティングにおいて，マスタと呼ばれるスケジューラがコンピュー 細に把握でき，状況に適したデータ通信が可能となる． ティングに関するリソースを管理している．各サイトにはマス 一方，グリッドシステムとして企業における IT リソースの タが存在し，各マスタは定期的にサイト間でローカルサイト 効率的活用やデータ共有，データセンタの運用コスト削減など の情報を交換する．サイト間で交換する情報は各サイトの負 ビジネス利用を目的としたサービスが登場し，また将来的には 荷や計算能力，データストレージの容量，デバイス情報など オンデマンドにグリッド環境を利用できるサービスの検討がな である．実際にジョブを実行する場合，まずユーザはローカル されている [7]．広域ネットワーク上の特定多数のユーザに対し サイトのマスタにアプリケーションの実行を依頼する．マスタ て提供するグリッド上の計算リソース，サービスはその性能や はジョブを複数のジョブに分割し，スケジューリングを行ない 質，経済性が多岐にわたり，ユーザはこのようなグリッド環境 ネットワークに接続されたサイトに分割されたジョブを分配す を利用する場合に課金がなされることが予想される．そのため， る．ジョブを受け取ったサイトはジョブを実行し，ローカルサ ユーザは最短時間でジョブを実行できるサービスを選択するの イトのマスタに結果を返す．ローカルサイトのマスタは結果を ではなく，規定時間内に処理を終えることのできる低コストな 集結し，ユーザへ結果を返す．ここで，データは地理的に分散 サービスを選択するようになる．さらに，ジョブの種類によっ し保存されているため，ジョブの実行に伴いサイト間でデータ て優先度が異なり，ジョブの終了する時刻に対する要求が異な 転送の要求が発生する．ユーザは実行するジョブに対しあらか る．したがって，様々なジョブを扱う場合，ジョブの終了する じめジョブ実行完了時間を指定する．マスタは指定されたジョ 時刻に対する要求が異なるため，デッドラインを考慮したジョ ブ実行完了時間に基づいて，データ転送完了時間のデッドライ ブスケジューリング [8] が重要である．さらに，ジョブ実行の ンを決定する．データ転送要求 (以下，呼とする) の発生した計 流れを考えた場合，ジョブの実行までに入力データを転送する 算機はマスタに転送するデータサイズ，デッドライン，転送先 必要がある．したがって，λ グリッド環境ではジョブに対する を通知する．各サイト間にはあらかじめ複数波長を用いた光パ 波長割り当て方法が重要となり，デッドラインを考慮した波長 スが設定されているものとし，各波長はタイムスロットに分割 割り当てスケジューリングを考える必要がある．従来のジョブ される．マスタは呼に対しタイムスロットを割り当て，呼を発 スケジューリングでは最短実行時間でジョブを実行することを 生した計算機は割り当てられたタイムスロットを使用してデー 目標としているため，データ送信完了時間を最短にする必要が タ転送を行なう．タイムスロットの割り当てスケジューリング あり，要求が発生した順に波長を割り当てる．そのため，従来 は 1 タイムスロット時間内に行なうものとし，現時刻以降のタ の波長割り当て方式では早い時刻，短い期間で大量の波長タイ イムスロットを割り当てる． ムスロットを予約する可能性が高くなり，早い時刻の波長タイ ムスロットはすべて予約され，デッドラインの短い呼がデッド ラインまでに波長タイムスロットを予約できない可能性が高い． 3. Greedy スケジューリング方式 従来のジョブスケジューリングではデータ転送時間を含めジョ したがって，デッドラインを考慮しない従来の波長割り当て方 ブ実行時間が最短となるサイトを決定するため，送信完了時間 式ではデッドラインの短い呼のブロック率が劣化し，全体とし が最短となるようにタイムスロットを予約する．これは各呼の てブロック率が劣化するという問題がある． デッドラインの要求を考慮しないアプローチであり，以後この そこで，本稿ではブロック率を改善するため，デッドライン ような予約方式を Greedy 方式と呼ぶ．図 2 に Greedy 方式に を考慮した波長割り当てスケジューリングを提案する．提案方 おける空きタイムスロット探索手順を示す．Greedy 方式は現在 —2— 䍃䍃䍃Reserved 䍃䍃䍃Unused data size = 4 deadline = 8 Reserve 㱗0 3 㱗1 4 㱗2 1 㱗3 2 time 図 3 Greedy 方式によるタイムスロット予約方法 (data size, deadline) 図 1 λ グリッド環境モデル Deadline Start 㱗0 㽲(8, 10) 㱗1 㽳(6, 10) 㱗2 㽴(2, 4) 㱗3 㱗0 㽲 㽳 deadline = 4 㱗1 time deadline = 10 図 4 Greedy 方式における問題点 㱗2 㱗3 約する．そのため，短い時間間隔でタイムスロットが多く予約 time 図 2 Greedy 方式における空きタイムスロット探索順序 されている時刻にデッドラインの短い呼が発生した場合，デッ ドラインの短い呼はブロックされる可能性が高くなる．した 時刻から利用可能なタイムスロットの順に各呼の指定するデー タサイズ分のタイムスロットを予約する．図 3 にデータサイズ 4，デッドライン 8 の呼が発生した場合における Greedy 方式 によるタイムスロット予約方法を示す．図中に示す番号が空き タイムスロットを発見する順番となる．各呼が指定するデッド ラインまでにデータサイズ分タイムスロットが予約できた場合 に，そのタイムスロットを用いてデータ転送を行なう．デッド ラインまでにデータサイズ分タイムスロットが予約できなかっ た場合に呼はブロックされる．Greedy 方式はデッドラインの 要求を考慮せず波長を選択してしまうため，デッドラインに関 わらず，各波長のタイムスロットを先頭から予約してしまう． 連続して呼が到着する場合やデータサイズが大きい呼が発生す る場合，現在時刻から近傍にある多くのタイムスロットが予約 される可能性が高い．したがって，直後にデッドラインの短い 呼が発生する場合，デッドラインまでに必要なタイムスロット が予約できず，デッドラインの短い呼はブロックされる可能性 が高くなる．そのため，Greedy 方式は全体のブロック率が劣 化するという問題がある．図 4 に Greedy 方式における問題点 (8,10), を示す．データサイズ，デッドラインが (6,10), がって，デッドラインの短い呼のブロック率を低減させるため に，デッドラインに応じて長い時間間隔でタイムスロットを予 約する方式を提案する． 図 5 に提案方式における空きタイムスロット探索手順を示す． 提案方式は短い波長の順にデッドライン時刻から空きタイムス ロットを探索し，データサイズ分空きタイムスロットを確保で きた場合に予約成功となる．そのため，使用波長数を抑え，長 い時間間隔でタイムスロットを予約することができる．デッド ライン時刻から予約することで，直後に発生するデッドライン の短い呼に対して空きタイムスロットを確保できる可能性が高 くなる． しかしながら，提案方式は短い波長の順にタイムスロットを 予約するため，長い波長の利用効率が低下する．また，デッド ライン時刻からタイムスロットを予約するため，現時刻におけ るタイムスロットの利用率も低下する．そこで，提案方式では タイムスロットの利用効率を改善するためにタイムスロットの 仮予約を行なう．マスタはスケジューリング時にデータサイズ 分のタイムスロットを予約し，そのタイムスロットをデータ転 送要求を出した計算機に割り当てるだけではなく，タイムス ロット使用効率を改善させるために長い波長からのタイムス の呼に対しては図中 ロットを仮予約し，そのタイムスロットも計算機に割り当てる． の太枠に囲まれたタイムスロットを割り当てるが，最後の 仮予約したタイムスロットはどの呼も使用可能であるが，デー 呼に対してはデッドライン時刻 4 までにタイムスロットを割り タを送信する 1 タイムスロット前になるまで，他の呼がその 当てることができず，デッドラインの短い呼 がブロックされ タイムスロットを予約しなかった場合のみ，その仮予約タイム てしまう． スロットを割り当てられた計算機はデータ転送を開始すること (2,4) の呼が順に発生した場合に， ， 4. 提 案 方 式 Greedy 方式では送信完了時間を最短とするため，短い時間 間隔で短い波長から長い波長に至る大量のタイムスロットを予 ができる．仮予約したタイムスロットを使用する場合，予約タ イムスロットとして割り当てられたタイムスロットが仮予約の タイムスロット使用分不必要になるため，予約していたタイム —3— Deadline Release a tentative reserved slot another call made and make a new reservation. data size = 2 deadline = 4 Start 㱗0 㱗1 㱗0 㱗2 㱗1 㱗3 㱗2 time 図 5 提案方式における空きタイムスロット探索順序 2 1 㱗3 t1 t2 t3 t4 t5 t6 t7 t8 … time 図 8 提案方式における仮予約解放の例 Deadline 㱗0 トは太枠に囲まれた 1∼4 のタイムスロットであり，数字は空 㱗1 きタイムスロット発見順序である．予約するタイムスロットは 㱗2 時刻の早い順に時刻 t3 , t6 , t7 , t8 である．図 6 に示した順序で 㱗3 空きタイムスロットの探索を行なった場合，予約タイムスロッ Start time 図 6 仮予約における空きタイムスロット探索順序 ト 3 に対して，時刻 t2 までに空きタイムスロットが存在しな いため仮予約をすることができない．一方，予約タイムスロッ ト 2 に対しては時刻 t5 までの空きタイムスロットのうち，図 6 䍃䍃䍃Reserved の探索順序に従って，破線に囲まれた 2 のタイムスロットを仮 䍃䍃䍃Unused 䍃䍃䍃Tentative Reserved data size = 4 れた 1,4 のタイムスロットを仮予約する．したがって，データ deadline = 8 サイズ 4，デッドライン 8 の呼は 4 つの予約スロット，3 つの Reserve 㱗0 3 2 1 㱗1 仮予約タイムスロットを割り当てられる． 4 㱗2 2 㱗3 仮予約タイムスロットはデータ転送の 1 タイムスロット前ま 4 でに，他の呼によって仮予約が解放されていなかった場合に， 1 t1 t2 t3 t4 予約する．同様に予約タイムスロット 1,4 に対して破線に囲ま t5 t6 t7 t8 … time 図 7 提案方式の予約・仮予約の例 スロットで予約時刻が最も遅いタイムスロットの予約を解放す る．1 つの呼に対して過剰にタイムスロットを仮予約しないた めに，マスタは最大でデータサイズ分のタイムスロットを仮予 約として割り当てる．また，仮予約は早い時刻，長い波長のタ イムスロット使用効率を向上させることが目的であるため，仮 予約は予約したタイムスロットより前の時刻のタイムスロット のみ対象とする．他の呼は仮予約されたタイムスロットをでき る限り使用しないように予約・仮予約をする．仮予約されたタ イムスロットを予約しなければデッドラインを満たせない場合 のみ，他の呼が仮予約したタイムスロットを解放し，そのタイ ムスロットを予約することができる． 図 6 に仮予約における空きタイムスロット探索順序を示す． 早い時刻，長い波長のタイムスロット使用効率を向上させるた めに長い波長から仮予約するタイムスロットを探索する．仮予 約は予約をするタイムスロットをデータサイズ分決定した後 に行なう．仮予約タイムスロット決定時では予約したタイムス ロットの時刻をすべて把握し，予約されたそれぞれのタイムス ロットに対して仮予約を行なうタイムスロットを 1 つ探索する． 仮予約の対象となるタイムスロットは予約したタイムスロット の時刻よりも早く，どの呼にも予約・仮予約されていないタイ ムスロットである． 図 7 に提案方式の予約・仮予約の例を示す．ここで，データ そのタイムスロットを使用してデータ転送を行なうことができ る．仮予約タイムスロットを使用時にはマスタに仮予約が解放 されていないか問い合わせをする．解放されていない場合，そ のタイムスロットを使用してデータ転送を行なう．仮予約タイ ムスロット 2 の直前の時刻 t2 になり，他の呼が仮予約タイム スロット 2 の仮予約を解放しなかった場合，時刻 t3 になった場 合にこの仮予約タイムスロット 2 を使用してデータ転送を行な う．したがって，時刻 t3 には予約スロット 3，仮予約タイムス ロット 2 を使用してデータ転送を行なう．そして，予約時刻が 最も遅い予約タイムスロット 4 を予約解放する．他の呼がタイ ムスロットの仮予約を解放していた場合，このタイムスロット を使用してデータ転送を行なうことはできず，時刻 t3 には予約 スロット 3 のみを使用してデータ転送を行なう． 図 8 に提案方式において他の呼の仮予約を解放し予約する例 を示す．データサイズ 2，デッドライン 4 の呼に対しデッドラ イン 4 までに空きタイムスロットは 1 つのみである．したがっ て，次にマスタは他の呼の仮予約を解放し，そのタイムスロッ トを予約する．図中に示す太線に囲まれたタイムスロット 2 に おける他の呼の仮予約を解放し，予約を行なう．他の呼の仮予 約を解放する場合，新たに仮予約は行なわない． 以上から提案方式はデッドラインを考慮してタイムスロット を予約し，さらに仮予約によりタイムスロットの利用効率を高 めることができるため，Greedy 方式と比較してデッドライン が小さい呼のブロック率を低減し，全体のブロック率を改善す ることができる． サイズ 4，デッドライン 8 の呼に対し，予約するタイムスロッ —4— 表 1 発生する呼 Greedy Proposed without Tentative Reservation Proposed データサイズ デッドライン 発生確率 [slots] [slots] 0 10 2∼4 5∼10 0.5 長いデッドライン 2∼4 20∼40 0.45 長いデッドライン 5∼15 40∼80 0.05 短いデッドライン Blocking Probability 呼の種類 5. 特 性 評 価 本章では，計算機シミュレーションにより提案方式における 通過トラヒック量及びブロック率について特性評価を行ない， Greedy 方式と比較検討する．特定のサイト間に着目し，あらか 10 -1 10 -2 10 -3 10 -4 じめ光パスは設定されており，波長数は 4 であるとする．呼の 到着は ON/OFF モデルに従い，ON 状態で呼が到着し，OFF 状態では呼が到着しないもとのする．ON 状態，OFF 状態各々 0 0.1 0.2 0.3 の期間長は，幾何分布に従う．呼はデッドラインの長い呼，短 0.6 0.7 図 9 負荷に対するブロック率 イズ，デッドラインは表 1 に示す範囲でランダムに決定される． ， 0.5 Load い呼に分類され，各々1/2 の確率で発生する．各呼のデータサ デッドラインの長い呼は 0.4 2と 種類発生するが，それぞれ Generated Traffic Greedy Proposed without Tentative Reservation Proposed の発生割合は 0.45 と 0.05 であるとする． 図 9 に Greedy 方式，仮予約を用いない提案方式，仮予約 15 を用いた提案方式の負荷に対するブロック率を示す．ここで， Greedy 方式は提案方式と比較し，ブロック率が劣化している ことが分かる．これは，Greedy 方式は短期間でタイムスロット を予約するため，デッドラインの長い呼でも早い時刻のタイム スロットを予約してしまい，デッドラインの短い呼のブロック Traffic [slots/time] 負荷は 1 タイムスロット時間における呼の発生率と定義する． 10 5 Max 率が劣化してしまうためである．仮予約を用いない提案方式の ブロック率は Greedy 方式と比較し改善している．これはデッ ドラインに応じて長期間でタイムスロットを予約するためであ る．さらに，仮予約を用いた提案方式はブロック率が最も改善 0 0 10 20 30 40 50 Time[slot] している．これはデッドラインに応じて長期間でタイムスロッ トを予約することに加え，仮予約を用いることによりタイムス 図 10 通過・オーバーロードトラヒック量 ロットを効率的に利用しているためである． 図 10 に Greedy 方式，仮予約を用いない提案方式，仮予約を ヒックに対してデッドラインを考慮し長期間で予約するため， 用いた提案方式の通過トラヒック量，オーバーロードトラヒッ Greedy 方式と比較してオーバーロードトラヒック量が低減し ク量を示す．ここで，通過トラヒックは 1 タイムスロット時間 ている．しかし，長期間でタイムスロットを予約するため，図 に実際にデータ転送を行ない使用したタイムスロット数と定義 10 に示すように通過トラヒック量が小さく，タイムスロットが する．波長数は 4 であるため，1 タイムスロット時間に送信可 効率的に利用されないことが分かる．仮予約を用いた提案方式 能なタイムスロット数は 4 であり，最大通過トラヒック量は 4 は，トラヒックの発生と同時に通過トラヒック量が最大となる となる．4 を超えたトラヒックはオーバーロードトラヒックと が，Greedy 方式と異なりオーバーロードトラヒックがほとん してブロックされる．オーバーロードトラヒックはデッドライ ど発生しておらず，仮予約を用いることにより，タイムスロッ ン時刻までに要求するデータサイズ分タイムスロットが確保で トを効率的に使用することができることが分かる．したがって， きなかった場合に発生する． 仮予約を用いた提案方式は Greedy 方式と比較し，デッドライ Greedy 方式はトラヒックの発生と同時に通過トラヒックは 最大となっており，短期間でトラヒックを通過させているが， オーバーロードトラヒックが多くなっていることが分かる．こ ンの短い呼をより多く処理することが可能である． 図 11 に Greedy 方式，仮予約を用いた提案方式における， デッドラインの長い呼の発生割合 α に対するブロック率を示 れは，Greedy 方式はデッドラインを考慮していないため，デッ す．ここで，α は全体の呼の発生数に対するデッドラインの長 ドラインの短い呼を処理することができない可能性が高くな い呼の発生数と定義する．また，負荷は 0.3 であるとし，表 2 るためである．一方，仮予約を用いない提案方式では発生トラ に，発生させる呼はデッドラインの長い呼，短い呼のデータサ —5— 表 2 発生する呼 呼の種類 サイズ分タイムスロットを予約するのに加え，仮予約すること データサイズ デッドライン 発生確率 [slots] [slots] 短いデッドライン 2∼4 5∼10 1−α 長いデッドライン 2∼4 20∼40 α 案方式は低負荷時にブロック率を 1∼2 オーダ改善することを また，本稿ではデッドラインを考慮したジョブスケジューリ ングの必要性から，デッドラインを考慮した波長割り当てに着 10 目したが，本稿で提案した波長割り当て方式を用いたジョブス ケジューリングの提案・検討，実装を今後の課題とする． -2 10 Blocking Probability ションにより特性評価を行ない，Greedy 方式と比較して，提 示し，提案方式の有効性を示した． Greedy Proposed -1 で波長タイムスロットの有効活用を図った．計算機シミュレー 謝辞 本研究は文部科学省 COE「アクセス網高度化光・電 子デバイス技術」プログラム，日本学術振興会科学研究者補助 -3 10 金によって行われた．関係者各位に深謝する． 文 -4 10 -5 10 -6 10 -7 10 0 0.2 0.4 0.6 0.8 1 Rate of Long Deadline Call 図 11 デッドラインの長い呼の発生割合に対するブロック率 (Load = 0.3) イズ，デッドラインを示す．Greedy 方式はデッドラインの長 い呼の発生割合に依存せずブロック率はほぼ一定となっている ことが分かる．これは Greedy 方式はデッドラインを考慮せず にタイムスロットを予約することにより，ブロック率がデッド ラインに依存しないためである．一方，提案方式はデッドライ ンの長い呼の発生割合によらず Greedy 方式と比較しブロック 率が改善している．さらに，デッドラインの長い呼の発生割合 が増加するに従いブロック率が改善してことが分かる．これは 提案方式はデッドラインを考慮し，タイムスロット予約を行う ため，デッドラインの長い呼の割合が増大した場合，デッドラ インを考慮する効果が大きくなるためである．したがって，提 献 [1] I.Foster , C.Kesselman, “The grid: blueprint for a new computing infrastructure,” Morgan Kufmann, Nov. 1998. [2] 原井 洋明, 村田 正幸, “分散計算環境構築のための光パス構成 法,” 信学技報 IN2005-89, 2005 年 10 月. [3] S.Figueira, S.Naiksatam, H.Cohen, D.Cutrell, P.Daspit, D.Gutierrez, D.B.Hoang, T.Lavian, J.Mambretti, S.Merrill, F.Travostino “DWDM-RAM: Enabling Grid Services with Dynamic Optical Networks,” IEEE CCGrid 2004, pp.707714, Illinois, Chicago, Apr. 2004. [4] H.Lee, M.Veeraraghavan，H.Li, E.K.P.Chong “Lambda scheduling algorithm for file transfers on high-speed optical circuits,” Proc. IEEE CCGrid 2004, pp.617-624, Illinois, Chicago, Apr. 2004. [5] A.Banerjee, W.Feng, B.Mukherjee, D.Ghosal “Routing and Scheduling Large File Transfers over Lambda Grids,” Proc. PFLDnet 2005, Lyon, France, Feb. 2005. [6] Neena R. Kaushik, Silvia M. Figueira, “A Dynamically Adaptive Hybrid Algorithm for Scheduling Lightpaths in Lambda-Grids,” Proc. IEEE/ACM CCGRID/GAN 2005, pp.418-425, Cardiff, May 2005. [7] Business on GRID COMPUTING, http://premium.nikkeibp.co.jp/grid/index.shtml [8] 竹房 あつ子, 松岡 聡, “グリッド計算環境でのデッドラインを 考慮したスケジューリング手法の性能,” 信学論 (D), J86-D-I, no.9, pp.661-670, 2003 年 9 月. [9] K.Ranganathan, I.Foster, “Decoupling Computation and Data Scheduling in Distributed Data-Intensive Applications,” Proc. IEEE HPDC 2002, pp. 352-358, Edinburgh, Scotland, July 2002. 案方式は Greedy 方式と比較し，どのようなトラヒックパター ンにおいても有効であり，デッドラインの長い呼の発生割合が 大きい状況下において，特に効果を発揮することが分かる． 6. 結 論 本稿ではブロック率を改善するため，デッドラインを考慮し た波長割り当てスケジューリングを提案した．提案方式では， デッドラインに応じて短い波長からタイムスロットを予約する ことにより，長期間でタイムスロットを予約する．その効果に より，早い時刻，長い波長のタイムスロットをデッドラインの 短い呼が予約可能なタイムスロットとして確保することができ る．さらに波長タイムスロットを有効に利用するために仮予約 を行なうことを提案した．デッドラインの短い呼が発生しない 場合，提案方式はデッドラインの短い呼に確保したタイムスロッ トを効率的に利用することができないため，提案方式はデータ —6—