成 腰 大 学 理 工 学 研 究 報 告 J,Fac,Sci,Tech.,Sei/keiUniv. Vo1.49No.2(2012)pp.101-104
異 な るネ ッ トワー ク遅 延 時 間 を提 供 す る ク ラ ウ ド環 境 に お け る
最 適 資 源 割 当 て アル ゴ リズ ム の 基 礎 評 価
粟 野 勇 輝*1,栗 林 伸 一*2Proposed joint multiple resource allocation method for cloud computing services with
different network delay
Yuuki AWANO *' and Shin-ichi KURIBAYASHI * 2
ABSTRACT : In a cloud computing environment, it is necessary to simultaneously allocate both
processing ability and network bandwidth needed to access it. The authors proposed the joint multiple
resource allocation method in a cloud computing environment that consists of multiple data centers and
each data center provides the different network delay. It is also highly likely that each data center would
provide the different network delay to users at different locations.
This paper proposes to enhance the joint multiple resource allocation method in a cloud computing
environment in order to handle the case where each data center provides the different network delay time
to users at multiple locations. It is demonstrated by simulation evaluations that the proposed method can
reduce the total request blocking probability up to 50%, compared with the conventional methods.
Keywords : Cloud computing , Joint multiple resource allocation. Different network delay
(Received Aug. 29, 2012) 1.ま え が き ク ラ ウ ドコ ン ピ ュー一一テ ィ ン グ環 境(D・(2〕 で は,計 算 能 力 や ス トレー ジだ け で な くそ こに ア クセ ス す るた め の 帯 域 も同 時 に確 保 す る必 要 が あ り,要 求 ご と に貸 し出 す ク ラ ウ ド資 源 種 別 は1種 類 で な く複 数 存 在 す る。 また, ク ラ ウ ドコ ン ピ ュー テ ィ ン グ環 塊 を構 成 す る個 々 の デ ー タセ ン タが 提 供 す るサ ー ビス 品 質 は 均 一 で な く異 な る可 能 性 が 高 い 。 本研 究 室 で は,計 算 能 力 や 帯 域 な ど異 な る資 源 種 別 の 資 源 を同 時 に 割 当 て る こ と を前 提 と した 最 適 資 源 割 当 て 方 式 を提 案 した(3)・(4)。さ らに,計 算 資源 を持 つ 各 セ ン タま で の ネ ッ トワー ク遅 延 時 間 の 違 い を 考 慮 した 最 適 資 源 割 り当 て 方 式(以 後,方 式3)を 明 らか に した 。 さ ら に,文 献(5)で は,ネ ッ トワ ー一一ク 遅延 時 間 だ け で な く, 複 数 の 資源 属性 を考 慮 した 最 適 資 源 割 り当て 方 式 を明 ら *1:理 工 学 部 情 報 科 学 科4年 生(usO92008@cc .seikei.acjp) *2:理 工 学 部 情 報 科 学 科 教 授(kuribayashi@stseikei .acjp) か に した。 しか し,そ れ ら方 式 は 特 定 の ア クセ ス 地 点 だ け を想 定 した もの で あ る。 実 際 の シス テ ム で は,例 えば 同 じセ ン タで あ っ て もア クセ ス 地 点 に よ りネ ッ トワー ク 遅 延 時 間 が 異 な る こ とが想 定 され る。 この た め,本 稿 で は 同 じデ ー タ セ ン タ で あ っ て もア ク セ ス 地 点 に よ りネ ッ トワー ク 遅延 時 間 が 異 な る こ と を想 定 した複 数 資源 同 時割 り当 て 方 式(以 後,方 式4)を 提 案 し,シ ミ ュ レー シ ョン 評価 に よ りそ の有 効性 を明 らか に す る。 な お,今 回 は基 本評 価 を 目的 とす るた め,資 源 属 性 と して ネ ッ トワー ク 遅延 時 間 の み を 考 慮す る。 2.ク ラ ウ ド コ ン ピ ュ ー テ ィ ン グ 環 境 に お け る 資 源 割 当 て モ デ ル クラ ウ ドコン ピュ ー テ ィン グ環 境 に お け る資源 割 当て の 前提 とな るシ ス テ ム モ デル を図1に 示す 。 これ は 文献 (3)∼(5)で も採 用 した もの で あ る。つ ま り,k個 の セ ン タ が 異 な る場 所 に 存在 し,各 セ ンタ は 計 算能 力 と帯域 の2 つ の 資源 種 別 の 資源 を提 供す る。 要 求発 生 時 に,k個 の 一101一
成 践 大 学 理 工 学 研 究 報 告 Vol,49No.2(2012.12)
Center1 Center2 Centerk
f ' Cmax1
α
ノ Cmax2 ■ ■ Cmax Nmaxk雌
Nmax1 膨 劉Nmax2 、 Network ㌧ ノ 己]S・ ・…s(P・ 。cesslng・bility)囮Llnk(B・ ・dwldth)踊 総
闇1留B獅
諸
評鐵
飾ente「
」
図1ク ラ ウ ド環 境 に お ける 資 源 割 当 て モ デ ル CenterlCenter2 Centerk 対 す る 条件 が厳 しい 要 求 の た め に セ ン タ1の 資源 を よ り 多 く確 保 す る こ とが で き る。 と ころ が ア クセ ス地 点Bか らみ る と逆 にセ ンタ1を 積 極 的 に使 用 し よ うとす る た め, セ ン タ1を で き る だ け確 保 しよ う とす る 地 点Aの 対 応 と 競 合す る こ とに な っ て しま う。 Aは できるだけセンタ1を利用 しないようにするの 競 合 に反し、Bはセンタ1をできるだけ利用しようとする (アクセス位 置の違いによるサービス競合) ■ ■ …ii
… … … '… … 肢 爪 …'… 乱:"… 勿'…'… ダ 、tA1 tA2 tAk Network
、 ノ
v
tAjNetworkdelaytimetoaccessCenterjatlocationA 図2セ ン タ ア ク セ ス 時 の ネ ッ ト ワ ー ク 遅 延 時 間 (ア ク セ ス 地 点 毎 に 異 な る) 中か ら最 適 な セ ン タを1つ 選 択 し,そ の 選 択 した セ ン タ か ら計 算 能 力 と帯 域 を 同 時 に そ の 要 求 に 割 当 て る。 計 算 能 力 と帯 域 を別 々 の セ ン タか ら割 当 て る こ と はで きな い 。 サ ー ビス 時 間 が 終 了 す る と,割 当て た 計 算 能 力 と帯 域 は 同 時 に 解 放 され る。 ま た,図2に 示 す よ うに,ア クセ ス 地 点 か ら各 セ ン タ ま で の ネ ッ トワー ク遅延 時 間 は 異 な り,さ ら にそ の 値 は ア クセ ス 地 点 に よっ て も異 な る もの とす る。 3.方 式3の 課 題 と 対 策 案 3.1方 式3の 課 題 ア クセ ス 地 点 毎 に ネ ッ トワー ク遅延 時 間 が 異 な る こ と を想 定 しな い 方 式3に 基 づ き資源 割 り当 て を 実 施 す る と, ア クセ ス位 置 の 違 い に よ るサ ー ビス 競 合 が 発 生 す る可 能 性 が あ る。 例 え ば,図3で は ア クセ ス 地 点Aか らみ る と セ ン タ1は 低 遅 延 の ア クセ ス を 提 供 す るた め,遅 延 時 間 に 対 す る条 件 が 厳 し くな い 要 求 に 対 して は セ ンタ2を 積 極 的 に 選 択 す る。 これ に よ り,今 後発 生 す る遅 延 時 間 に L■ ■■■一■■ツ / ' Center1 Center2 ' 一 〇」薦 十 ' 4 ← さぐ 一ネ 外 ワ、1γー ク 『 戸 \ OsO .5secど
喝
勉聰 0」sec 図3ア ク セ ス位 置 の違 い に よ るサ ー ビス競 合 の例 3.2対 策 案 3.1節 で説 明 した 「ア ク セ ス 地 点 に よ るサ ー ビス競 合 」を緩 和 す る方 式(以 後,方 式4)を 以 下 に 提 案 す る。 (1)基 本 的 な考 え方 全 て の ア ク セ ス 地 点,全 て の 要 求 品質 の 平 均 要 求棄 却 率 を 最小 化 す る こ とを 目的 関数 とす る。 (2)対 策 案 案1.セ ン タ の 空 き 資源 量 が 閾 値(=最 大 資 源 量*alevel) 以 下 に な っ た場 合 に,も っ と も要 求 品 質 が厳 しい 要 求 だ け を受 け付 け る。 案2.セ ン タ 毎 に ア クセ ス 地 点対 応 の 資源 を個 別 に確 保 し,残 りは 共用 す る。 公 平性 を 考 え る と案2が 有 効 な 場合 もあ るが 論理 が複 雑 で あ る こ とか ら,今 回 は案1を 前提 に評 価 を 行 う。 4.方 式4の 有 効 性 評 価 4.1評 価 条 件 1)C言 語 を 用 い た コ ン ピ ュ ー一一タ シ ミ ュ レ ー一一シ ョ ン に よ り評 価 を 行 う。 2)基 礎 的 な 評 価 を 行 うた め,今 回 は ア ク セ ス 地 点 と し てA,Bの2点 を 考 慮 す る 。 ま た,資 源 属 性 と し て ネ ッ ト ワ ー ク遅 延 時 間 だ け を 想 定 す る 。 3)セ ン タ は,セ ン タ1,セ ン タ2の2つ 存 在 し,以 下 の ネ ッ ト ワ ー ク遅 延 時 間 を 提 供 す る も の とす る。 【セ ン タ1】 地 点Aに 対 して は 「優 先 品 質 」(ネ ッ ト ワ ー一一ク 遅 延 時 間 が 短 い),地 点Bに 対 し て は 「通 常 品 質 」(ネ ッ トワ ー一一ク 一102一成 践 大 学 理 工 学 研 究 報 告 Vol.49No.2(2012.12) 遅 延 時 間 が 長 い),を 提 供 。 【セ ン タ2】 地 点Aに 対 し て は 「通 常 品 質 」,地 点Bに 対 し て は 「優 先 品 質 」,を 提 供 。 4)alevelは セ ン タ1に 対 し て の み 有 効 と し,セ ン タ2に 対 し て は 設 定 し な い 。 5)要 求 発 生 比 率 ・要 求 発 生 比 率
地 点A:地 点B=prob _a:(1-prob_a) ・地 点Aに お け る 要 求 発 生 比 率 「通 常 」要 求:prob _10,「 通 常 」 要 求:1.0-prob_10 ・地 点Bに お け る 要 求 発 生 比 率 「通 常 」 要 求:prob _20,「 通 常 」 要 求:1.O-prob_20 6)要 求 が 発 生 す る と,3章 で 提 案 し た 案1に 従 っ て 最 適 な セ ン タ を1つ 選 択 し,必 要 と な る 計 算 能 力 と 帯 域 を そ の セ ン タ か ら 同 時 に 割 当 て る 。 な お,今 回 は 比 較 の た め,方 式3も 評 価 す る 。 7)要 求 毎 に 必 要 と な る 計 算 能 力 と 帯 域 の 大 き さ は 全 要 求 種 別 に 共 通 で,そ れ ぞ れ 平 均C,Nの ガ ウ ス 分 布(分 散 は5)に 従 う。 8)要 求 の 発 生 間 隔 な ら び に は 資 源 割 当 て 時 間 は 全 要 求 10% 累 軽5% 0% 〈 トラ ピ ッ ク 条 件 〉 要 求 発 生 パ ター ン:均 一
&罫%
go%(イ 憂 先) At也 点 (全 要 求 の60%) (全 要 求 の40%) Bt也,点 、(穆箔
方 式3の 値 ◆一 一◇_..』◆ 地 点Aと 地 点Bを 合 わ せ た 全 体 の 要 求 棄 却 率 ◆ ◆ 方 式3の 値 ▲ ▲ ▲ ▲ ▲ 地 点A「 優 先 」の 要 求 棄 却 率 ぐ参考 》瑳斎 」B礎 諭 の要 求麹 痺 ◆ ▲ を ▲ 00.2a40.60.8 セ ン タ1の 資 源 割 当 て 閾 値(alevel) 図4方 式4の 評 価 結 果 例1 に 共 通 で,そ れ ぞ れ 平 均rの 指 数 分 布,H(一 定)に 従 う も の とす る。 割 当 て ら れ た 資 源 は 資 源 割 当 て 時 間 経 過 後 に 同 時 に 解 放 す る。 9)要 求 発 生 パ タ ー ン は, {C=al,N=b1;C=a2,N=b2;…;C=aw,N=bw} の 繰 返 し と す る 。 こ こ で,wは1繰 返 し 内 の 発 生 要 求 数, au(u=1∼w)はu番 目 の 要 求 のCの 大 き さ,b、(u=1∼w) はu番 目の 要 求 のNの 大 き さ,を そ れ ぞ れ 示 す 。 4.2シ ミ ュ レ ー シ ョ ン結 果 と評 価 シ ミ ュ レ ー一一シ ョ ン 結 果 を 図4,図5に 示 す 。 な お, Cmaxl=Nmaxl=30,Cmax2=Nmax2=30,C=N=7,prob _a= 0.6と し た 。 ま た,方 式4と し て 提 案 し た 制 御(案1) は セ ン タ1だ け で 実 施 す る。 図4で は 全 体 要 求 の60%が 地 点Aか ら発 生 し,そ の 90%が 「優 先 」を 要 求,10%が 「通 常 」(prob _10=0.1) を 要 求 す る 。地 点Bか ら発 生 す る 要 求 の10%が 「優 先 」 を 要 求,90%が 「通 常 」(prob20=09)を 要 求 す る 。 地 点Aの 「優 先 」要 求 は セ ン タ1の み 選 択 可 能 で あ る が, 「通 常 」 要 求 は セ ン タ2な ら び に セ ン タ1を 選 択 可 能 で あ る。 一 方,地 点Bの 「通 常 」 要 求 は セ ン タ1を ま ず 選 択 し,空 き 資 源 が な い 時 に は セ ン タ2を 選 択 す る。 横 軸 〈 トラ ピ ッ ク 条 件 〉 要 求 発 生 パ ター ン:均 一(署%
(全 要 求 の40%) Bt也 点 (50%{憂先) 50% (優 先)(通 常) At也 点 (全 要 求 の60%) 方 式3の 値 10%◆ 〒一◇ 一一◆ 地 点Aと 地 点Bを 合 わ せ た 全 体 の 要 求 棄 却 率 ◆ ◆ 累 方 式3の 値 ◆ ◆ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ 瞭5%地 点A「 優 先 」の ◆ ◆ 要 求 棄 却 率 o O.20.40.60.8 セ ン タ1の 資 源 割 当 て 閾 値(alevel) 図5方 式4の 評 価 結 果 例2 一103一成 践 大 学 理 工 学 研 究 報 告 Vol.49No.2(2012.12) は,セ ン タ1に お け る 閾 値 係 数alevelの 値 で あ る 。 図5で は,地 点Aと 地 点Bか ら 発 生 す る 「優 先 一 要 求 と 「通 常 」 要 求 の 比 率 を そ れ ぞ れ50%と し た 場 合 (prob _10=prob_20=0.5)の 評 価 結 果 で あ る 。 図4お よ び 図5よ り,方 式3に 比 べ 方 式4は 全 体 の 要 求 棄 却 率 を 削 減 で き る こ と が わ か る 。 特 に,図4の よ う に,地 点Aか ら の 「優 先 」 要 求 に 対 す る 資 源 に 余 裕 が な い 場 合 に そ の 削 減 効 果 が 大 き く な る(図4の 例 で は 約 半 分)。 こ れ は 以 下 の 理 由 に よ る 。 (1)方 式3で は,地 点Aか ら発 生 す る 「優 先 」 要 求 は セ ン タ1し か 選 択 で き な い に も 関 わ ら ず,地 点Bか ら 発 生 す る 「通 常 」 要 求 が(セ ン タ2も 利 用 で き る に も 関 わ ら ず)セ ン タ1資 源 を 優 先 的 に 使 用 す る 。 こ の た め,地 点Aか ら発 生 す る 「優 先 」 要 求 の 棄 却 率 が 大 き く な っ て し ま う。 地 点Bか ら 発 生 す る 「通 常 」 要 求 は セ ン タ1が 無 理 な ら 資 源 に 余 裕 の あ る セ ン タ2も 選 択 で き る 。 一 方 ,方 式4は セ ン タ1に お い て 「優 先 」 要 求 に 対 す る 資 源 割 り 当 て を 優 先 す る こ と で(地 点Bの 「通 常 」 要 求 ア ク セ ス 制 限)そ の 棄 却 率 を 削 減 し,結 果 と し て 全 体 の 要 求 棄 却 率 も 少 な く す る こ と が で き る 。 (2)今 回 評 価 結 果 は 示 し て い な い が,地 点Aの 「優 先 」 要 求 が 多 く な り過 ぎ る と地 点Bの 「通 常 」 要 求 ア ク セ ス 制 限 効 果 が 薄 れ て く る こ と も 確 認 し て い る 。 [2]J.W.RittinghouseandJ.F.Ransone:"CloudComputing: Imprementation,Management,andSecurity",CRCPress LLC,Aug.2009. [3]津 村,栗 林:"コ ン ピ ュ ー タ ネ ッ ト ワ ー一一ク に お け る 複 数 資 源 同 時 割 当 て 方 式 の 提 案",成 膜 大 学 理 工 学 研 究 報 告VOL43,No.2,pplO7-120(Dec.2006) [4]S.Kuribayashi,"Opt㎞alJointMultipleResource AllocationMethodforCloudComputingEnvironments", IntemationalJoumalofResearchandReviews血 ComputerScience(IJRRCS),Vol.2,No.1,Feb.2011. [5]YUukiAwanoandShil-ichiKuribayashi,c`Reducing PowerConsumptionandImprovingQualityofServicein CloudComput血gEnvironments",Proceedingofthe l5-thIntemationalConferenceonNetwork-Based Infb㎜ationSystems(NBiS-2012),Sep2012. 5.む す び 本稿 は,広 域 に 分 散 した複 数 の デ ー タセ ン タか ら構 成 され る ク ラ ウ ドコ ン ピ ュー テ ィ ン グ環 境 を前 提 に,同 一 セ ン タで あ っ て もア クセ ス 地 点 に よ りネ ッ トワー ク遅 延 時 間 が 異 な る こ と を想 定 した 複 数 資源 同 時 割 り当て 方 式 (方式4)を 提 案 した 。 シ ミ ュ レー一一シ ョン評 価 に よ り, 提 案 方 式 は 従 来 方 式(方 式3)に 比 べ 全 体 の 要 求 棄 却 率 を大 幅 に 削 減 で き る こ とを 示 した 。 今 回 は,基 本 評価 を 行 うた め,資 源 属 性 は ネ ッ トワー ク遅延 時 間 の み を 考 慮 し,ア クセ ス 地 点 数,セ ン タ数 な どを 制 限 した 評 価 の み行 っ た 。 今 後 は,そ れ らの 数 を 増 加 させ た 場 合 の 評価 を 行 い,提 案 方 式 の 有 効 性 とそ の 条 件 を 明 確 に して い く予 定 で あ る。