成蹊大学理工学研究報告
J. Fac. Sci. Tech., Seikei Univ.
Vol.43 No.2 (2006) pp.107-120（特別研究費に係る論文）

コンピュータネットワークにおける複数資源同時割当て方式の提案
津村重宏*1, 栗林 伸一*２

Simultaneous resource allocation method for computer communication networks
Shigehiro TSUMURA*1 , Shin-ichi KURIBAYASHI*2
ABSTRACT: In computer communication networks, many servers, distributed in various locations, offer
processing ability for each service request. To utilize the processing ability of the servers, it is necessary
to allocate simultaneously both the processing resources and the access bandwidth that connects theserver to the backbone network. Resource allocation in computer communication networks can bemodeled as multiple resource pairs in the system, each resource pair comprising server (computing
resource) and access bandwidth (network resource), and both computing and network resources being
allocated simultaneously in one selected resource pair.
This paper proposes a method for the efficient joint resource allocation method of both computing andnetwork resources. It is assumed that there are multiple centers distributed in the network and each center
includes both servers and its access bandwidth to the backbone network. The key idea of the proposed
method is first to identify the resource type (computing or network) for which the requested amount is
the largest proportion of the maximum resource of that type, and then, from the centers that could meetthe request, to select the center with the least available amount of the selected resource type. This paper
also proposes an extension of the joint resource allocation method for the case where each service request
declares the maximum permitted network delay time, and where both the size of resource and the
network delay time are considered in the selection of a center. It is demonstrated by simulation
evaluations that the proposed methods could reduce the request loss probability and also reduce the total
amount of the resources required by up to 20%, compared with the conventional method.
Keywords: resource allocation, computer communication network, utility computing, grid computing(Received September 28, 2006)

１．まえがきス，グリッドコンピューティング(2)，ブロードバンド・
ユビキタスネットワーク(3)などが今後社会インフラとしてコンピュータネットワークでは，地理的に分散して設導入された場合，この傾向はさらに強まると想定される。

置されたサーバの計算能力とそのサーバとクライアント

この形態では，同時に発生する複数の要求それぞれにを接続するアクセス帯域を要求毎に提供する。近年の動対して，複数のサーバの中から最適なサーバを選択しそ向として，ユーザが自前のサーバやネットワークを構のサーバの計算能力を割当てることが経済的なサービス

築・運用するのではなく，必要な時に必要な量の計算能提供上重要な課題となる。また，サーバを利用するため

力と帯域をネットワーク運用業者などから借り受けるユにはそこに接続するためのネットワーク帯域も 同時にーティリティサービスやコンバージドサービスを利用す必要になる，ここで，中継バックボーンネットワークは(1)

る傾向が強くなってきている 。ユーティリティサービ*1：工学研究科物理情報工学専攻博士前期課程学生*2：理工学部情報科学科教授 (Professor, Dept. of

一般に広帯域であり，ネットワーク資源（帯域）の割当てを考える場合には特にサーバと中継バックボーンネッ
トワーク間のアクセス帯域を意識する必要がある。

Computer and Information Science, e-mail:このため，コンピュータネットワークにおける資源割

kuribayashi@st.seikei.ac.jp)

−107−

当ては，
「サーバとアクセス帯域の 資源セット が複数ることを目的に，要求を分割する方式ならびに割当て資存在し，要求発生毎にその中から資源セットを１つ選択

源を移し変えることで新たな要求を処理する方式を６章し，要求された計算能力（コンピューティング資源）とで提案する。簡単なシミュレーションにより，その有効アクセス帯域（ネットワーク資源）の両方を 同時に性を評価する。７章では，要求棄却率を削減する他の同割当てるモデル」と考えることができる。一般に，要求時割当て方式を提案する。８章はまとめである。

される計算能力と帯域の大きさは同じではないため（かつ要求毎に大きさも異なる），１つの資源種別だけを考慮

２．コンピュータネットワークの資源割当てモデル

したアルゴリズムを複数種別資源の割当てに適用しても最適な割当ては期待できない。

コンピュータネットワークの構成を図１に示す。地理

このため，本稿では，コンピューティング資源とネッ的に分散した複数のセンタが存在し，各センタにはサー

トワーク資源という２つの資源種別の資源を 同時にバ（計算能力）と中継バックボーンネットワークに接続割当てることを前提とした最適資源割当て方式を検討すするためのアクセス帯域が存在する。クライアントは，る（本稿では，以後 複数資源同時割当て方式 と呼ぶ）。

計算能力とそこに接続するための帯域をシステム資源管

また，本稿では要求棄却率（２つの資源種別で必要な量理装置に要求する。システム全体の資源はシステム資源の資源を割当てられないために要求が拒否される割合）

管理装置により管理され，システム資源管理装置はクラを最小化することを目的に検討を行う。

イアントからの要求毎に資源を割当て，解放する。ここ

ところで，類似の研究として，文献(4)はグリッドシス

で，クライアントとサーバ間を接続するためには中継バ

テムにおけるデッドラインスケジューリング方式を提案

ックボーンネットワーク内の帯域も必要となるが，一般している。これは，サーバ（コンピューティング資源）に各センタのアクセス帯域に比べて中継バックボーンネとネットワークの両方を考慮したサーバ選択方式であり，ットワークの帯域は非常に大きく，資源割当てのネック

サーバの処理時間とネットワークの転送時間の総和が最となるのはアクセス帯域と想定される。そこで，本稿でも長いサーバを選択し（但し，許容最大サービス完了時

はネットワーク資源として各センタのアクセス帯域のみ

刻（デッドライン）までにサービスを完了できることがを扱うものとする。

条件），より多くのジョブを処理することを狙ったもので各センタはサーバ（計算能力）とアクセス帯域のセットを持つ.

ある。文献(4)は複数のジョブがサーバならびにネットワ
ークを順番に利用する待ち行列モデルを前提としている。

センタＡ

センタＢ

一方，本稿では，クライアントはショブの処理でなく，CmaxA

専用の計算能力と帯域を要求するモデルを前提としていNmaxAる点が異なる。クライアントは，割当てられた資源を用いて独自のジョブやアプリケーションサービスを実施する。従来から CPU 貸し，帯域貸しと言われているサービスに近いモデルである。さらに，本稿では，計算能力

CmaxB

センタＫ

・・・

NmaxB

CmaxK
NmaxK

中継バックボーンネットワーク
システム資源管理装置

・・・
クライアントと帯域の資源セットが複数存在し，要求発生時にその中：サーバ(計算能力）

から資源セットを１つ選択し，そこから計算能力と帯域の両方を 同時に 割当ることを前提としている点も異クライアントクライアント：アクセス帯域（ネットワーク資源）

Cmaxj：センタｊの最大コンピューティング資源量（
計算能力）
Nmaxj：センタｊの最大ネットワーク資源量（帯域）なる。

図１．コンピュータネットワークの構成

２章では，コンピュータネットワークの資源割当てモ
デルについて述べる。３章では，複数種別の資源を同時に割当てる場合の課題を整理する。４章では，複数資源

図２は図１を前提とした資源割当てモデルである。Ｋを同時に割当ることを前提とした最適資源割当て方式を個の異なるセンタが存在し，各センタは計算能力（コン

提案し，シミュレーション評価により従来方式に比べた

ピューティング資源）とアクセス帯域（ネットワーク資有効性を明らかにする。また，５章では，ネットワーク源）の「資源セット」を持つ。要求発生時に，Ｋ個の中遅延を考慮した複数資源の同時割当て方式を提案し，４から最適なセンタを１つ選択し，その選択したセンタか章と同じくシミュレーション評価により従来方式に比べ

らコンピューティング資源とネットワーク資源を 同時た有効性を明らかにする。さらに，要求棄却率を低下す

に

−108−

その要求に割当てる。コンピューティング資源とネ

ットワーク資源を別々のセンタから割当てることはできだから）。その後，要求④はコンピューティング資源のない。また，割当てられた資源は各要求専用であり，他空きが多いセンタ B を選択する（｛①の大きさ＋③の大要求と共有されない。クライアントは割当てられた専用

きさ｝＞②の大きさ だから）。この時点で，コンピュー資源を用いて，ジョブ処理やアプリケーションサービス

ティング資源に着目すると両方のセンタの使用量はほぼを実行する。

均等になっているが，一方のネットワーク資源に着目す
ると全く使用量は均等になっていない。これは，コンピ

センタＡ

センタＢ

センタＫ

コンピューティング
資源(CmaxA)

コンピューティング
資源(CmaxB)

コンピューティング
資源(CmaxK)ューティング資源だけに着目すると要求③はセンタ A
を選択するが，ネットワーク資源に着目すると①の大きさ＞②の大きさのため要求③はセンタ B を選択すべきで・・
ネットワーク資源(NmaxA)

ネットワーク資源(N maxB )あったと言える。これにより，両センタのネットワーク

ネットワーク資源(N maxK)

資源使用量の均等化は崩れた。
ところで，要求①，要求②，要求③，要求④が使用するコンピューティング資源の大きさに大きな差は無い。

Cmax ：
各センタの最大コンピューティング資源量（
計算能力）
Nmax：各センタの最大ネットワーク資源量（帯域）

そのため，センタ A とセンタ B を選択する要求を入れ*各要求毎にＫ個のセンタから１つのセンタを選択し、要求されたコンピュー
ティング資源ならびにネットワーク資源を同時にそのセンタから割当てる．

替えてもコンピューティング資源の均等化は維持される。

図２．コンピュータネットワークの資源割当てモデル

一方，要求①と要求③が使用するネットワーク資源の大きさは，要求②と要求④が使用するネットワーク資源の３．複数資源同時割当ての課題

大きさに比べて相当大きい。このため，要求②と要求③を入れ替えることで，両センタのネットワーク資源使用

一般に，要求される計算能力と帯域の大きさは同じで量は均等に近くなる。ここで提案したセンタ選択を行っはなく，かつ要求毎に大きさも異なる。このため，従来た例を図３(2)に示す。図３(1)に比べ，コンピューティン

提案されている１つの資源種別を前提とした資源割当て

グ資源ならびにネットワーク資源ともに両センタの資源(5)~(9)を２章で述べた複数資源同時割当てにそのま量は均等化されていることがわかる。つまり，１つの資ま適用しても最適な割当ては期待できない。以下にセン源種別だけでなく，２つの資源種別を同時に考慮するこ

タ数２を前提に例を説明する。

とにより両センタの資源使用量を均等化することが可能

方式＜例１＞ 図３は２つのセンタの資源使用量をできるである。

だけ均等化するようにセンタ選択を行うケースである。

＜例２＞ 図４は極力一方のセンタに詰め込むことにまず，コンピューティング資源だけに注目した資源割当

よって，その後発生するより大きな要求にできるだけ対て例を図３(1)に示す。図３(1)において，要求①はまずセ応できるようにセンタ選択を行うケースである。まず，

ンタ A を選択する（センタ A，センタ B のどちらでもコンピューティング資源だけに注目した資源割当て例を同じ条件で選択可能であり，たまたまセンタ A を選択）。

図４(1)に示す。図４(1)において，要求①はまずセンタ A

次に，要求②はコンピューティング資源の空きが多いセを選択する（センタ A，センタ B のどちらでも同じ条件

ンタ B を選択し，要求③はコンピューティング資源の空で選択可能であり，たまたまセンタ A を選択）
。次に，きが多いセンタ A を選択する（①の大きさ＜②の大きさ

要求②はコンピューティング資源の空きが少ないセンタ

センタA

センタB
空き

空き
コンピュー
ティング資源③

コンピュー
ティング資源③①

ネットワーク
資源（１）コンピューティング資源のみ着目して割当てた場合

②

空き
コンピュー
ティング資源空き
ネットワーク資源i ：i番目の要求②①

ネットワーク資源（２）両方の資源種別に着目して割当てた場合

図３ 複数資源同時割当ての課題例（両センタの使用量を均等化する場合）

−109−

④
③

①

空き
④
②

センタB
空き

コンピュー
ティング資源④②①

ネットワーク
資源

センタA

空き
④
③

センタA

センタB
②

コンピュー
ティング資源①

空き

ネットワーク
資源

②
①

コンピュー
ティング資源ネットワーク
資源（１）
コンピューティング資源のみ着目して割当てた場合

センタA

センタB
空き

空き

④

コンピュー
ティング資源

④
③

①

コンピュー
ティング資源空き④

ネットワーク
資源

③

④

空き
③
②

空き
ネットワーク
資源

①

③
②

（２）
両方の資源種別に着目して割当てた場合

i ：i番目の要求

図４ 複数資源同時割当ての課題例（極力片方のセンタに詰め込み，一方のセンタを空けておく場合）

A を選択し，要求③はセンタ A のコンピューティング資ト廃棄率などに影響される）などがある。例えば，クラ源の空きがなくなったため，センタ B を選択する（｛①

イアントとサーバ間の応答遅延時間を 100ｍ秒以下のクの大きさ＋②の大きさ｝＝総資源量 だから）。その後，イック応答を必要とする要求に対しては，ネットワーク

要求④もセンタ A のコンピューティング資源に空きがな

資源（帯域）に空きがあっても 100ｍ秒以上のネットワ

いためセンタ B を選択する。この時点で，コンピューテ

ーク遅延がかかるものは選択できない。このように，仮ィング資源に着目するとセンタ A に詰め込まれているに資源に空きがあっても，その資源属性から資源割当て

が，ネットワーク資源に着目するとセンタ A ではなくセ条件を満足できないために要求棄却となるケースを極力

ンタ B に詰め込まれ，かつコンピューティング資源とネ削減できる方式が必要である。これを５章で提案する。

ットワーク資源それぞれに空きはあるにも関わらず同じ

さらに，要求棄却率を低下させる手段として，１つのセンタで両方の資源を確保できない

虫食い状態 が発センタで処理しきれない場合には複数のセンタで処理す生している。これは，要求③発生時にセンタ A のコンピる（要求分割），または割当て資源を移し変えることで新ューティング資源に空きがないためセンタ B を選択した

たな要求を処理する（資源移し変え），などが考えられ，が，ネットワーク資源に着目すると要求③はセンタ A を６章で提案する。これらはコンピューティング資源のみ選択すべきであった。これにより，両資源ともにセンタが対象である。

A に詰め込むことができなくなった。
ところで，コンピューティング資源だけみると，要求４．複数資源同時割当て①と要求②でセンタ A のコンピューティング資源は全て使用されるが，センタ A のネットワーク資源には空き

本章では，計算能力（コンピューティング資源）とアがある。一方，ネットワーク資源だけみると，要求③とクセス帯域（ネットワーク資源）の資源セットを持つ複要求④でセンタ B のネットワーク資源は全て使用される数のセンタの中からセンタを１つ選択し，その選択したが，センタ B のコンピューティング資源には空きがある。

センタからコンピューティング資源とネットワーク資源

このため，要求②と要求④を入れ替えることで 虫食いを同時に割当てることを前提とした最適資源割当て方式

状態 を回避できる。これを図４(2)に示す。つまり，１を提案する(10),(11)。

つの資源種別だけでなく，２つの資源種別を同時に考慮することにより２つの資源種別共に一方のセンタに詰め

4．1 資源割当てアルゴリズム

込むことが可能となる。

まず，比較のため従来方式の１つであるシーケンシャ

このように，複数種別の資源を同時に割当てる場合に(8)ル方式 の割当てアルゴリズムを以下に定義する。

は，片方の資源種別だけでなく両方の資源種別を同時に＜シーケンシャル方式＞（方式Ⅰ）考慮した割当て方式を検討する必要がある。これを４章(i) センタ選択で提案する。また，複数種別の資源を同時に割当てる方

要求発生毎に，K 個のセンタの中から順番に（ラウン

式を評価する場合，資源属性についても考慮する必要がドロビン）センタを１つ選択する。もし，選択したセンある。例えば，ネットワーク資源属性としては，ネット

タに十分な資源の空きがなければ次のセンタを選択する。

ワーク遅延，実行スループット（ビット誤り率やパケッ

全てのセンタに十分な空きがない場合にはその要求を棄−110−却する。なお，要求発生毎に最初に選択するセンタは，資源量の大きさ｝／XC0

前の要求で最終的にどのセンタが選択されたかに関わら

XC0：全てのセンタの中で最も総コンピューテ

ず，決まった順番に選ぶ。

ィング資源量（割当て可能な最大コンピュ(ii) 資源割当て

ーティング資源量）が小さいセンタの総コ
ンピューティング資源量(i)で選択されたセンタのコンピュータ資源とネット
ワーク資源を同時に要求に割当てる。

XN＝｛要求が必要とするネットワーク資源量(iii) 資源の解放の大きさ｝／XN0，

資源割当て時間が終了した段階で割当て要求を解放

XN0：全てのセンタの中で最も総ネットワークする。

資源量（割当て可能な最大ネットワーク
資源量）が小さいセンタの総ネットワー

次に，新たに提案する複数資源同時割当て方式の割当

ク資源量てアルゴリズムを以下に示す。これは，できるだけ込み

例えば，総コンピューティング資源量が５０と１００合っているセンタを選択することにより，今後発生するのセンタが存在した場合，XC0 は５０となる。

大きな資源量を必要とする要求にできるだけ対応できるようにするのが狙いである。

(ii) センタ選択(i)で決定したキー資源に着目し，空き資源量が最も少＜方式Ⅱ＞ないセンタを選択する。但し，コンピューティング資源(i) キー資源の特定ならびにネットワーク資源を必要量確保できることが条

センタの選択において，２つの資源種別の中で注目す件である。また，条件を満足するセンタが複数存在する

る資源種別を「キー資源」と定義する。もし，XC≧XN

場合には，その中からランダムにセンタを１つ選択する。

ならコンピューティング資源をキー資源と判断する。そなお，条件を満足するセンタが１つも存在しない場合にうでない場合にはネットワーク資源をキー資源と判断す

は要求を棄却する。

る。また，コンピューティング資源とネットワーク資源(iii) 資源割当ての単位はＭＩＰＳと b/s （ビット／秒）で異なる．この(ii)で選択されたセンタのコンピュータ資源とネット

ため，必要量／総資源量 という相対値を用いて両者のワーク資源を同時に要求に割当てる。

大きさを比較する。

(iv) 資源の解放
資源割当て時間が終了した段階で割当て要求を解放

ここで，XC＝｛要求が必要とするコンピューティング
方式Ⅱで割当てた場合

センタA

要求6

要求5

要求4

要求3

要求2

要求1

（Ｂ）

（Ｂ）

（Ａ）

（Ａ）

（
Ａ）

（
Ａ）

センタB

コンピュー
ティング資源ネットワーク
資源
選択したセンタ＜参考＞

センタBしか空いていないのでセンタBを選択

コンピュー
ティング資源ネットワーク
資源

コンピュー
ティング資源ネットワーク資源

センタAのほうが着目した資源の空きが少ないためセンタＡを選択

方式Ⅰで同じ要求を割当てた場合
センタA
要求6

要求5

要求4

要求3

要求2

要求1

（Ｂ）

（Ａ）

（
Ｂ）

（Ａ）

（Ｂ）

（Ａ）

センタB

コンピュー
ティング資源ネットワーク
資源
コンピュー
ティング資源ネットワーク
資源

コンピュー
ティング資源センタを順番に選択
空 いているのに使 えない（虫食い状態）

図５．方式Ⅱの資源割当てイメージ−111−

ネットワーク
資源

する。

5) 要求の発生間隔は平均ｒの指数分布に従う。資源割当方式Ⅱを前提としたコンピューティング資源とネットて時間 H は一定とする。割当てられた資源は資源割当

ワーク資源の同時割当てイメージを図５に示す。この図て時間経過後に解放される。

からわかるように，方式Ⅰでは各センタの資源が虫食い

6) 要求の発生パターンは「｛Ｃ＝ｉ１，Ｎ＝ｊ１；Ｃ＝i２，状態となるのに比べ，方式Ⅱは虫食い状態にならず，よ

N=ｊ2；

り多くの要求を処理できることがわかる。４．
２節では，うに記述する。ここで，ｎ個は要求の数，ｉｋ(ｋ=１〜どの範囲でどの程度方式Ⅱが有効になるかシミュレーシn)はｋ番目の要求のＣの大きさ，ｊｋ(ｋ=１〜n)はｋ番

ョン評価を行う。

目の要求のＮの大きさ，をそれぞれ表す。また，今回の… ；C＝ｉｎ，Ｎ＝ｊｎ｝の繰り返し」のよ

評価では以下の３つの基本発生パターン（図６）を用い
4．2 シミュレーション評価て，提案方式の基本特性を明らかにする。

4．2．1 シミュレーション条件

・発生パターン①：｛Ｃ＝ｘ，Ｎ＝ｘ｝

1) 評価モデルは，図２の資源割当てモデルでセンタ数がＣとＮの大きさが同じパターン

２の場合を前提とする。つまり，ロケーションが異なる

・発生パターン②：｛Ｃ＝2×α,Ｎ＝2；
Ｃ＝2,Ｎ＝2×α｝

２つのセンタ A，B が存在し，それぞれのセンタにはコンピューティング資源とそれにアクセスするためのＣとＮの大きさが交互に凸凹するパターン（α帯域（ネットワーク資源）が存在する。要求発生時に，は凸凹の度合いを評価するための係数）

資源割当てアルゴリズムに従い，センタ A またはセン・発生パターン③：｛（Ｃ＝3,Ｎ＝3）×5；
Ｃ＝3×β,Ｎ＝3×β｝

タ B を選択する。
2）Ｃ言語を用いたコンピュータシミュレーションによりＣとＮの大きさが同じで，時折大きい要求が発評価を行う。

生するパターン（βは大きさの度合いを評価す

3) 要求毎に必要となるコンピューティング資源量とネるための係数）

ットワーク資源量の大きさはガウス分布に従うもの

4．2．2 シミュレーション評価と分析とする。また，それぞれの大きさの平均値をＣ，Ｎで図７および図８に示すシミュレーション結果より，以示す。

下の諸点が明らかである。

4) センタＡ，センタＢのコンピューティング資源の総量

1) 発生パターン①では方式Ⅰと方式Ⅱの差が無いこと（最大使用可能な資源量）をそれぞれＣmaxA，ＣmaxＢとがわかる（図７＜パターン①＞）。これは，方式Ⅰの処する。センタ A，センタ B のネットワーク資源の総量理できる要求の数と，方式Ⅱの処理できる要求の数がをそれぞれＮmaxA，ＮmaxＢとする。

同じだからである。

要求1

要求2

要求1

要求4

コンピュー
ティング資源コンピュー
ｐ１Ｃ ティング資源

ｑ２

コンピュー
ｐ２ ティング資源

ネットワーク資源

ネットワークｐ１Ｎ 資源

ｐ２

ｑ２ 資源

要求3

要求2

要求1

ｐ３

ｐ３

ｐ３

ｐ３

ネットワーク【発生パターン①】【発生パターン②】（コンピューティング資源とネットワーク
資源の要求が凸凹の場合）｛Ｃ＝p1C，Ｎ＝p1N｝の繰り返し｛Ｃ＝p2，Ｎ＝q2；Ｃ＝q2, Ｎ＝p2｝の繰り返し

ｘ３＊この例ではｘ３＝３個【発生パターン③】（時折大きな要求が発生する場合）｛（Ｃ＝p3，Ｎ＝p3）
×x3；Ｃ＝q3, Ｎ＝q3｝の繰り返し＊図は発生間隔に従って発生する要求の資源量を右から順番に並べたものである（要求が連続発生するわけではない）．
・発生パターン②〜③は図示されているパターンが繰り返し発生するものとする．

図６ 要求発生パターン

−112−

ｑ３
ｑ３

2) 発生パターン②では方式Ⅱの方が方式Ⅰよりも要求

30＞）。これは，方式Ⅰは図５に示したような虫食い状態が起こりやすいのに対して，方式Ⅱは１つのセンタにできるだけ詰め込むので虫食い状態になりにくいためと考えられる。また，方式Ⅱの有効性は比率αに関係

要求棄却率[%]

棄却率が小さくなることがわかる（図７＜パターン②
方式Ⅰ
方式Ⅱ
15

することがわかる。
0

さらに，図８のセンタ数が２のときに，方式Ⅱで方式

3ｘ＜パターン①＞｛Ｃ＝ｘ，Ｎ＝ｘ｝

2

Ⅰと同じ要求棄却率を維持するように総資源量を削減していったところ，方式Ⅱは最大で 10％程度総資源量

4203) 発生パターン③では方式Ⅱのほうが方式Ⅰよりも要求棄却率が小さくなることがわかる（図７＜パターン③＞）。方式Ⅱは時折発生する大きい要求を処理できるからである。これは，一つのセンタに詰め込むことに要求棄却率[%]を削減できる。
方式Ⅰ
10

方式Ⅱ

よって，できるだけもう一方のセンタを空けておくからである。また，方式Ⅱの有効性は比率βが大きいほ01.4

ど有効であることがわかる。

1.6

1.8

2.0

比率α

4) 奇数の場合を除いて，センタの数を増加させても上記＜パターン②＞｛Ｃ＝2×α,Ｎ＝2；Ｃ＝2,Ｎ＝2×α｝の 2)は成立する（図８）。センタ数が奇数の場合，発生15パターンが②であると方式Ⅱを用いても図５に示した要求棄却率[%]

ような虫食い状態が発生しやすくなるためである。
以上から，方式Ⅱは要求発生パターンが②または③の場合に従来方式に比べ有利となり，最大で 10％の総資源

方式Ⅰ
10

5
方式Ⅱ

量を削減することが可能である。
0

5
4
比率β
＜パターン③＞｛（Ｃ＝3,Ｎ＝3）×5；
Ｃ＝3×β,Ｎ＝3×β｝

５．ネットワーク遅延を考慮した複数資源同時割当て方式

CmaxA=CmaxB=20,NmaxA=NmaxB=20; r=1分;
H=10分（パターン①＆パターン②）,
H=5分（パターン③）

本章では，ネットワーク資源の資源属性であるネット
ワーク遅延を考慮した複数資源同時割当て方式（方式Ⅲ）
を提案する

3

図７ シミュレーション結果（方式Ⅰ vs. 方式Ⅱ）(11),(12)。クライアントは，要求時にコンピューティング資源とネットワーク資源の大きさ，資源割当て時間だけでなく，許容最大ネットワーク遅延 L も指定

5．1 方式Ⅲの資源割当てアルゴリズム

することを前提とする。例えば，要求によってはクイッ(i) センタ選択

ク応答を必要とするものもあり，その場合には資源に空ネットワーク遅延の最も大きなセンタを選択する。但きがあってもネットワーク遅延の大きなセンタは選択でし，ネットワーク遅延は L 以下であり，かつコンピュ

きない。提案する方式の狙いは，できるだけネットワー

ーティング資源ならびにネットワーク資源を必要量確

ク遅延の大きなセンタを選択し（但し，許容最大ネット

保できることが条件である。また，条件を満足するセン

ワーク遅延以下が条件），今後発生する許容最大ネットワ

タが複数存在する場合には，方式Ⅱと同様に相対的に大ーク遅延の小さな要求にできるだけ多く対応できるようきい要求の資源種別に着目して，空きが最も少ないセンにすることである。つまり，方式Ⅲでは方式Ⅱの様に要タを選択する。なお，条件に合うセンタが存在しない場

求資源の大きさに着目するのではなく，ネットワーク遅合には要求を棄却する。

延に着目するのが基本的な違いである。

−113−

(iii) 資源の解放

10

資源割当て時間が終了した段階で割当て要求を解放

要求棄却率[%]する。
方式Ⅰ

方式Ⅲの資源割当てイメージを図９に示す。この例では，方式Ⅱはネットワーク遅延の小さなセンタ A に詰め5込むように働くため，L の小さな要求は棄却されやすくなるのに対し，方式Ⅲはネットワーク遅延の大きなセン
タ B を極力選択するため L の小さな要求にも対応しやす
くなることがわかる。

方式Ⅱ
0
2

3

4
センタ数

6

5

5．2 シミュレーション評価
5．2．1 シミュレーション条件＜パターン②＞｛Ｃ＝4,Ｎ＝2；Ｃ＝2,Ｎ＝4｝1) 基本的には 4．2．1 と同じ条件とする。

Cmax=Nmax =20（全センタ）; r=1.4分（
センタ数2）,
r=0.93分（センタ数3）,r=0.7分（センタ数4）,
r=0.56分（センタ数5）,r=0.47分（センタ数6）;
H=10分2) 評価モデルは，図２の資源割当てモデルに各センタそれぞれのネットワーク遅延を追加して，センタ数が２の場合を前提とする。センタ A，センタ B のネットワ

図８ シミュレーション結果（センタ数増加の影響）
図８ シミュレーション結果（センタ数増加の影響）

ーク遅延をそれぞれ tA=0.1 分，tB=0.5 分とする。
3) 要求の許容最大ネットワーク遅延 L は 0.1 分もしくは(ii) 資源割当て

0.5 分とし，0.1 分の要求が発生する割合を P とする。

(i)で選択されたセンタのコンピュータ資源とネット
ワーク資源を同時に要求に割当てる。

センタA
tA=0.1分方式Ⅲで割当てた場合
要求6

要求5

要求4

要求3

要求2

L=0.1分（Ａ）

L=0.5分（Ｂ）

L=0.5分（Ｂ）

L=0.1分 L=0.1分
（
Ａ）
（
Ａ）

センタB
tB =0.5分

要求1

コンピュー
ティング資源ネットワーク
資源
選択したセンタ

L=0.5分（Ｂ）

コンピュー
ティング資源L以内で最も大きいネットワーク
遅延であるセンタBを選択

Lを満たせるのはセンタAだけなのでセンタAを選択

ネットワーク
資源

コンピュー
ティング資源ネットワーク
資源許容最大ネットワーク遅延：L＜参考＞
方式Ⅱで同じ要求を割当てた場合

センタB
tB=0.5分

センタA
tA=0.1分

要求棄却
要求6

要求5

要求4

要求3

要求2

L=0.1分
（）

L=0.5分（Ａ）

L=0.5分（Ａ）

L=0.1分 L=0.1分
（
Ａ）
（
Ａ）

要求1

コンピュー
ティング資源ネットワーク
資源
選択したセンタ

L=0.5分（Ｂ）

Lを満たせるセンタA センタAのほうが着目
Lを満たせるのはした資源の空きが少ない センタAだけなのでに空きがないのでためセンタＡを選択
センタAを選択要求棄却

コンピュー
ティング資源たまたま
センタBを選択

図９．方式Ⅲの資源割当てイメージ−114−

ネットワーク
資源

コンピュー
ティング資源ネットワーク
資源

Lを満たせないためセンタBが空いているのに使えない

5．2．2 シミュレーション評価と分析ないと実行できない要求には適用できない。また，本章

図 10 に示すシミュレーション結果より，以下の諸点がでは１つの要求に対して複数のセンタを使って処理を実明らかである。なお，４章において方式Ⅱが方式Ⅰより行する場合でも，各センタに要求されたネットワーク資も有利であることが明らかになったことから，ここでは源を同じように確保するものとする。

方式Ⅱと方式Ⅲの比較を行う。

以下に，割当てアルゴリズムを示す。

１）要求発生パターンに関係なく，
方式Ⅲが有利となる。

(1) 必要な資源を確保できるセンタが１つ以上存在する

つまり，Ｐが０％または 100％近辺以外であれば，方式Ⅲの方が方式Ⅱよりも要求棄却率が小さく，かつよ場合：４章で提案した方式Ⅱを提供する。
(2) 必要な資源を確保できるセンタが存在しない場合：

り多くの要求を処理できる。例えば，図 10＜パターンi) センタ選択＆資源割当て①＞の場合には，Ｐ=50％では方式Ⅱはおよそ r=5 分①

全てのセンタの空きコンピューティング資源量ので要求棄却が発生するが，方式Ⅲは r=2 分以下になら総和が要求されたコンピューティング資源量（ｚ）

ないと発生しない。

以上かどうかチェックし，真なら②の処理を行う。
偽なら要求は棄却する。

これは，方式Ⅱでは，割当ての途中でセンタ A の方が詰まった状態になると，次の要求を混み合っている②

コンピューティング資源の空きが最も小さいセン

センタ A に詰め込んでしまい，後で発生する許容最大タにまず着目し（新たな要求に必要なネットワーク

ネットワーク遅延が 0.1 分の要求を処理できなくなっ資源が確保できることが条件），
そのセンタの空き資てしまう場合があるからと考えられる。一方，方式Ⅲ

源量全てまたはまだ不足している分（ｚ１）だけ，では，センタ A が混み合っていても許容最大ネットワ

新たな要求に割り当てる。ネットワーク資源についーク遅延が 0.5 分であればセンタ B を選択する。このては，コンピューティング資源を割当てた全てのセ

ため，センタ A の資源を空けておくことができ，後でンタに対して，要求が必要とする資源量を割当てる。

発生する許容最大ネットワーク遅延が 0.1 分の要求が③

要求棄却されにくい。

（ｚ−ｚ１）＝０になるまで，②の処理を繰り返す。②の処理を繰り返しても条件を満足するセンタが存在しない場合には，要求は棄却する。

２）図 10＜パターン②＞のＰ＝67％のときに，方式Ⅲで
方式Ⅱと同じ要求棄却率を維持するように総資源量をii) 資源の解放
資源割当て時間が終了した段階で割当てた全ての資削減していったところ，方式Ⅲは最大で 15％程度総資源量を削減できる。

源を解放する。

以上から，方式Ⅲは要求発生パターンに関係なく方式

6．2 資源移し変えを考慮した複数資源同時割当て方式(10)

Ⅱならびに従来方式に比べ有利であり，最大で 15％の総（方式Ⅴ）資源量を削減することが可能である。これは，センタ選

特定センタの割当て済のコンピューティング資源の一択において，ネットワーク遅延が一番大きな制約になる

部を他センタに移し変えることにより，そのセンタの空からと言える。なお，方式Ⅲはネットワーク遅延を考慮

き資源量を拡大することで大きな資源量を必要とする要しない場合には適用できないため，ネットワーク遅延を求を受け付けられるようにすることが考えられる（図考慮する必要のない資源割当てにおいては４章で提案し12）。

た方式Ⅱが最適と言える。

但し，このためには処理中のプロセスを無中断で移動する（プロセス移動）ことが前提となり，それに対応で６．要求分割または資源移し変えを考慮した複数資

きない要求は対象外である。

源同時割当て方式

以下に，割当てアルゴリズムを示す。
(1) 必要な資源を確保できるセンタが１つ以上存在する

6．1 要求分割を考慮した複数資源同時割当て方式（方
(10)

式Ⅳ）

１つのセンタでは必要なコンピューティング資源を確保できない場合には，要求を分割し複数のセンタの資源を割当てることにより要求棄却を減らす方策が考えられる（図 11）。但し，１つのセンタで必要な資源を確保し−115−

場合：４章で提案した方式Ⅱを提供する。

3.0

6.0

ほとんどが許容最大ネットワーク遅延を満たせないためによる要求棄却

領域X

3.0

要求棄却率[%]

平均発生間隔r[分][r=3.3分]

領域Y

方式Ⅱ
1.5

領域Z
方式Ⅲ
0

0

0
50
100
許容最大ネットワーク遅延が0.1分の要求の発生割合P[%]

0

50
100
許容最大ネットワーク遅延が0.1分の要求の発生割合P[%]＜パターン①＞｛Ｃ＝4，Ｎ＝4｝
3.0

4.0

ほとんどが許容最大ネットワーク遅延を満たせないためによる要求棄却

領域X

2.0

要求棄却率[%]

平均発生間隔r[分][r=2.0分]

領域Y

方式Ⅱ
1.5

領域Z
方式Ⅲ
0

0

0
50
100
許容最大ネットワーク遅延が0.1分の要求の発生割合P[%]

0
50
100
許容最大ネットワーク遅延が0.1分の要求の発生割合P[%]＜パターン②＞｛Ｃ＝4,Ｎ＝2；Ｃ＝2,Ｎ＝4｝
1.0[r=2.5分]

領域X

2.0

要求棄却率[%]

平均発生間隔r[分]

4.0

領域Y

ほとんどが許容最大ネットワーク遅延を満たせないためによる要求棄却

方式Ⅱ
0.5

領域Z
方式Ⅲ
0
0
50
100
許容最大ネットワーク遅延が0.1分の要求の発生割合P[%]

0
0
50
100
許容最大ネットワーク遅延が0.1分の要求の発生割合P[%]＜パターン③＞｛（
Ｃ＝2,Ｎ＝2）
×3；Ｃ＝6,Ｎ＝6｝
CmaxA=CmaxB=20,NmaxA=NmaxB=20; H=4分
領域X:方式Ⅱと方式Ⅲともに要求棄却が発生する
領域Y:方式Ⅱのみ要求棄却が発生する
領域Z:方式Ⅱと方式Ⅲともに要求棄却が発生しない

図10 シミュレーション結果（方式Ⅱ vs. 方式Ⅲ）

−116−

センタＡ

④ もし，移動できるセンタがなければ，コン

センタＢ

ピューティング資源の空きがその次に大き
コンピュー
ティング資源なセンタに着目して同じチェックを行う。

コンピューティング資源⑤

全てのセンタについてチェックしても条件を満たすセンタがない場合には，
新たな要

要求

求は要求棄却とする。

コンピュー
ティング資源ネットワーク資源

ネットワーク資源ii) 資源の解放

ネットワーク
資源

資源割当て時間が終了した段階で割当て資源を解放する。
6．3 シミュレーション評価＊ネットワーク資源はセンタＡ，センタＢともに確保

図11．要求分割（方式Ⅳ）の資源割当てイメージ
図11 要求分割（方式Ⅳ）の資源割当てイメージ(2) 必要な資源を確保できるセンタが存在しない場合：

6．3．1 シミュレーション条件
方式 IV ならびに方式Ⅴの大まかな効果を評価するため，方式Ⅱ，方式Ⅲに比べ簡単なシミュレーシi) センタ選択＆資源割当て

ョンを行う。また，方式Ⅱと比較することにより，方式①

コンピューティング資源の空きが最も大きいセン

Ⅳならびに方式 V の効果を評価する。

タにまず着目し（新たな要求に必要なネットワーク

1) 基本的には 4．2．1 に合わせる。

資源が確保できることが条件），
そのセンタで割当て

2) 要求毎に必要となるコンピューティング資源量とネ済の資源を新たな要求に必要な分だけ他センタに移ットワーク資源量の大きさは一定とし，それぞれＣ，

動させることができるかどうかチェックする。

Ｎで示す。

②

3) 要求の発生間隔 r は一定とする。

移動先センタはコンピューティング資源の空きが4) 方式Ⅳは要求分割が起こりやすいと想定される以下

次に大きくかつ移動分の空きが存在しているものを選択する。この際，ネットワーク資源も同時に移動の発生パターンでのみ評価する。

する必要があるため，ネットワーク資源にも空きが｛Ｃ=6,Ｎ=3；Ｃ=3,Ｎ=6｝（ＣとＮの大きさが交互に凸あることが条件となる。

凹するパターン）
5) 方式Ⅴは資源移し変えの起こりやすいと想定される③ 条件を満たすセンタがあれば，移動させた資源（コ
ンピューティング資源とネットワーク資源の両方）

以下の発生パターンのみで評価する。

をそのセンタから割当て直す。新たな要求に対して{C=4,N=2；C=3,N=2；C=2,N=2；C=3,N=2}

は，割当て済の資源を移動させ資源に空きができた
6．3．2 シミュレーション評価と分析センタから必要なコンピューティング資源を割当て

表１，表２に示すシミュレーション結果より，要求分

る。

要求
コンピュー
ティング資源ネットワーク
資源

センタA

センタB

センタA

センタB

コンピュー
ティング資源コンピュー
ティング資源コンピュー
ティング資源コンピュー
ティング資源ネットワーク資源

ネットワーク資源

ネットワーク資源

ネットワーク
資源

資源移し変え資源割当て

図12．資源移し変え（方式Ⅴ）の資源割当てイメージ

−117−

(14)

割または資源移し変えを行うことにより要求棄却率は減る方式

少するが，その効果はわずかであることがわかる。処理開始を遅らせる方式ではなかった。

の複雑性を考えると，方式Ⅳまたは方式Ⅴは方式Ⅱに比＜方式Ⅶ＞べて有利とは必ずしも言えない。

割当て可能な資源がない場合には，要求された資源量よりも小さな資源を割当てること（結果として資源割当

表１ 方式Ⅳと方式Ⅱの比較結果

要求棄却率はあったが，２つの資源種別に着目して割当て分割を考慮しない（方式Ⅱ）

分割を考慮する
（方式Ⅳ）

11%

10%

て時間が指定された長さよりも長くなる）により，同時に割当てる資源量を少なくし，今後発生するより多くの要求に備える方式。但し，ストリーミング配信など要求資源量を変更できない要求には適用できない。処理イメ＜条件＞要求パターン｛Ｃ＝6,Ｎ＝3；Ｃ＝3,Ｎ＝6｝（C,Nは一定）
CmaxA =CmaxB =21,NmaxA=NmaxB=21; r=1分; H=9分

ージを図 14 に示す。なお，図 13 と同様に一方の資源種
別のみを抽出した例を示す。

表２ 方式Ⅴと方式Ⅱの比較結果＜方式Ⅷ＞
資源移し変えを資源移し変えを考慮しない（方式Ⅱ） 考慮する（方式Ⅴ）
要求棄却率

6%

方式Ⅶとは逆に，（要求時に割当て可能な空き資源がない場合に）要求された資源量よりも大きな資源を割当

4%てて処理を早く完了させ，新たに到着する大きな資源量＜条件＞要求パターン｛Ｃ＝4,Ｎ＝2；Ｃ＝3,Ｎ＝2 ；Ｃ＝2,Ｎ＝2 ；Ｃ＝3,Ｎ＝2 ｝（C,Nは一定）
CmaxA=CmaxB=20,NmaxA=NmaxB=20; r=1分; H=13分を必要とする要求に備える方式。
＜方式Ⅸ＞
方式Ⅵと同様に資源割当て開始時刻を遅らせる機能を

７．要求棄却率を削減する他の割当て方式

方式Ⅶに追加した方式。
＜方式Ⅹ＞

４章から６章で提案した方式Ⅱ，Ⅲ，Ⅳ，Ⅴ以外に，(13)

表３に示す他の割当て方式が考えられる。これらの方方式Ⅵと同様に資源割当て開始時刻を遅らせる機能を方式Ⅷに追加した方式。

式については，今後評価していく予定である。以下に，

８．むすび

各方式の概要を説明する。
＜方式Ⅵ＞割当て可能な資源がない場合には，資源割当て開始をコンピュータネットワークにおいて，コンピューティ

遅らせることにより要求を受け付ける方式。ただし，許ング資源（計算能力）とネットワーク資源（帯域）を同

容最大 資源割当て終了時刻 までに資源割当てを終了時に割当てることを前提とした最適資源割当て方式（方することが条件。処理イメージを図 13 に示す。なお，

式Ⅱ，方式Ⅲ）を提案した。シミュレーション評価の結実際の処理は２つの資源種別に対して実施されるが，図果，提案方式は従来方式に比べ要求棄却率を低下させ，

13 は一方の資源種別のみを抽出した例を示す。また，今最大で 15％の資源を削減することが可能であることをまで１つの資源種別に着目して資源割当て開始を遅らせ明らかにした。また，資源割当て条件としてネットワー

表３ 複数資源同時割当て方式の分類

条件対応する提案方式

Ⅲ

Ⅳ

Ⅴ

Ⅵ

Ⅶ

Ⅷ

Ⅸ

Ⅹ
.

＜１つのセンタだけでは要求資源を確保できない場合の対処＞
①要求棄却
②要求分割
③資源移し変え④資源割当て開始遅れ＜センタ選択におけるネットワーク遅延の考慮＞①考慮しない②考慮する＜要求資源量の変更＞①変更しない②変更する②−１小さくすることを許容②−２大きくすることを許容
注） 方式Ⅲ以降は方式Ⅱとの差分のみ表示．

Ⅱ

○
○
○
○

○

○
○
○

：今回評価した方式

−118−

○

○

○
○

○

ク遅延を考慮しない場合には方式Ⅱ，ネットワーク遅延評価を行う。また，今回提案した方式は，上りと下りのを考慮する場合には方式Ⅲ，が最適な方式であることを両方向の帯域を同時に割当てることを前提とした ATM

示した。さらに，要求棄却率を低下させるための方策を

網

網羅的に整理し，今後評価すべき方式を明らかにした。

択にも応用可能であり，その評価も進めていく予定であ

今後，本稿で評価していない同時割当て方式の有効性(15)，ＭＰＬＳ網(16)

ならびにＧＭＰＬＳ網

のパス選

る。

処理中の
要求量総和

処理中の
要求量総和
資源割当て時間

③

総資源量

総資源量

②

要求の大きさ

②

③

①

①

時間

時間
①

(17)

②

③

①

要求棄却

発生要求

②

資源割当て開始時刻を遅らせて要求受付

③

発生要求
方式Ⅵ）
＜資源割当て開始遅れを許容する場合＞（＜資源割当て開始遅れを許容しない場合＞

i ：i番目の要求

図13 方式Ⅵの資源割当てイメージ（一方の資源種別の例のみ示す）

処理中の
要求量総和

処理中の
要求量総和
③

総資源量

総資源量

③の許容最大 資源
割当て終了時刻

③

②
②

①

①
時間

時間
①

②

③

①

要求棄却

発生要求
＜方式Ｉ
Ｉ
＞

②

③

発生要求

①の許容最大 資源
割当て終了時刻＜方式Ⅶ＞②の許容最大 資源
割当て終了時刻

i ：i番目の要求

図14 方式 Ⅶの資源割当てイメージ例（ 一方の資源種別の例のみ示す）

参考文献

F.Berman, “A study of deadline scheduling forclient-server systems on the computational grid”,
Proceedings

of

the

10th

http://www.japan-telecom.co.jp/english/newsrelease/

Symposium

on

High

Performance

2006/feb/0209/0209.html

Computing.

(1) “ULTINA On Demand Platform”(2) “The Open Grid Services Architecture, Version 1.5”,

Distributed

ATM system”, Electronics and communications in(3) 平成１８年度「情報通信白書」総務省

Japan, Part 1, Vol.74, No.9, pp.30-42, 1991.

http://www.johotsusintokei.soumu.go.jp/whitepaper/(6) T.Takeda, T.Ohba, I.Inoue and S.Urushidani,

whitepaper01.html
A.Takefusa,

International(5) S.Kuribayashi, “Bandwidth assignment control inOpen Grid Forum Document GFD-80.

(4)

IEEE

“Resource Management in Layer 1 Virtual Private
H.Casanova,

S.Matsuoka,

and

−119−

Networks”, IEICE Trans., Vol.E88-B, No.8,pp.3343-

3352, 2005.

allocation of multiple resources for computer(7) S.Shiokawa and S.TAsaka, “Bandwidth allocation

communications networks”, APCC2006 (2006.8).

considering priorities among multimedia components(12) 津村，栗林，田邉：“遅延時間を考慮した複数資源

in mobile networks”, IEICE Trans. Commu.,

同時割当て方式の有効性評価”，電子情報通信学会 総
合大会

Vol.E84-B, No.5, PP.1344-1355, 2001.
(8)

K.Aida, A.Takefusa, H.Nakada, S.Matsuoka,

S.Sekiguchi,

andU.Nagashima,(13)

津村，栗林，田邉，“サービス開始遅れを許容する

複数資源同時割当て方式の提案”， 電子情報通信学会“Performance2006 ソサイエティ大会 B-7-5 (2006.9)

evaluation model for scheduling in global computing
systems”, International Journal of High-Performance

B-7-148 (2006.3)(14)

池永, 川原, 尾家，“QoS 経路制御における受付遅Computing Application, Vol.14, No.3, pp.268-279,

延の導入とその効果について”，

2000.

技術研究報告 IN2001-96, pp45-50 (2001.11)(9)電子情報通信学会

R.Buyya, D.Abramson, and J.Giddy, “Nimrod/G:(15) T.Ogawa, S.Kuribayashi, A.Senoh, T.Ushiki,

An architecture for a resource management andS.Shiraishi and T.Sampei, “ATM signaling VC set-up

scheduling system in a global computational grid”,

methods and bandwidth selection methods inProceedings of the HPC ASIA’2000.

B-ISDN”, Technical report of IEICE, SSE94-182,(10)

栗林，津村，田邉：“ブロードバンド・ユビキタス

ネットワークにおける複数種別資源の最適同時割当て

1995.(Japanese)(16) IETF RFC3031 “Multiprotocol Label Switching方式”， 電子情報通信学会 研究会資料 IN2005-105(2005.11)

Architecture“(17) IETF RFC3945 “Generalized Multi-Protocol Label(11) S.Tsumura and S.Kuribayashi, “Simultaneous−120−

Switching (GMPLS) Architecture”