高能率大容量ファイル転送方式とその視覚化手法
著者
住田 智雄
学位授与大学
東洋大学
取得学位
博士
学位の分野
工学
報告番号
甲第234号
学位授与年月日
2009-03-25
URL
http://id.nii.ac.jp/1060/00003954/
Creative Commons : 表示 - 非営利 - 改変禁止 http://creativecommons.org/licenses/by-nc-nd/3.0/deed.ja2008年度
博士論文
高能率大容量ファイル転送方式とその視覚化手法
学籍番号：4660040001
住田智雄
東洋大学大学院工学研究科情報工学専攻博士後期課程
目次
第1章 はじめに
第2章
2、1 2．2 準備 転送方式 2．1．1 順序非保存ブロック転送方式一一．．．．．．．．．．． 2．1．1．1 NBT ． 2．1．1．2 Network DMA．．． 2．1．2 従来のNBTの問題点．．． 2．1．2．1 ATMを用いることの問題点．．．．．．．． 2．1．2．2 マルチキャスト機能の代替．．． 2．1．3 Explicit Multi−unicast（XCAST）．．．．．．．．．．， 2．1．3．1 XCASTの概要 2．1．3．2 XCASTの動作原理．．．．．、．．．．．． ネットワークの視覚化．．．．．． 22．1 視覚化対象（ネットワークモデル） 2．2．1．1 ランダムネットワーク．．．．．．．．．．． 2．2．1．2 スケールフリーネットワーク（BAモデル） 2．2．1．3 優先的選択がない場合のBAモデル．．．． 2．2．2 既存の視覚化手法／ツール．．．．．．．．．．．．．．． 81112466677811136811111111111222222
目次
第3章
3．1 3．2 3．34533
第4章
4．1 4．2 4．3第5章
5．1 5．2 NBT on X⊂ASTの提案と検証 NBT on XCAST ．，．．．．．．．． ． NBT on XCASTが必要とする機能． ． ． ． 3．2．1 制御情報管理機能．．、．．．． ． ． ． ． 3．22 コネクション制御管理機能 ．． ． ． NBT on XCASTの有効性の検討．． ． 3．3．1 ユニキャストの場合．．．．．． ． ．．． ．．． 3．3．2 NBT on XCASTの場合．．． ． NBT on XCASTの転送能力 ． NBT on XCASTの再送方式 ， ． NBT on XCASTの動作確認実験 実験概要 ．．．．．．，．．．．．．．．．． ． ． ． ．． 4工1 実験用ネットワーク構成 ．．．．． 4．1．2 NBT on XCASTのシステム構成 ． 4．1．3 実験用プログラム．．．．．．．．．．． ． ．． ． ．． 動作確認実験の結果 ．．．．．．．．．．． ． ．．． 4．2．1 サーバの動作結果．．．．．．．．． ． ． 4．2．2 ルータの動作結果．．．◆．．．．． ． 結果のまとめ．．．．．．．．．．．．．．． ．．． ． NBT on XCASTの視覚化手法 視覚化パターン．．．．．．．． 5．Ll 視覚化パターン1．．．． 5⊥2 視覚化パターンH．．．． 5．1．3 視覚化パターンIIIa．．． 5．1．4 視覚化パターン皿b．． 描画条件 ．．．．．．．．．．．．00225577113333333344
666789923444444455
54 ． ．． ． ． 55 ．． ． ．． 56 ． 57 ． ． ． ． ． ， 57 ． ． ． ． ． ． 58 ． ． ． ． 、 ． 59 25．3
第6章
6．1 6．2 6．3 6．4 6．5 6．6第7章
7．1 7．2 5．2．1 視覚化パターン1の条件．．．．．．． 5．2．2 視覚化パターンll， mの条件．．．． 描画アルゴリズム 5．3．1 視覚化パターン1のアルゴリズム．． 5．3．2 視覚化パターン皿bのアルゴリズム NBT on XCASTの視覚化評価実験 視覚化手法の実装 視覚化パターン1の実行結果．．．． 視覚化パターンHの実行結果 ．．． 評価および考察．．．． 視覚化パターン1の考察．．．．．． 視覚化パターンllの考察．．．．．． 適用例 具体的な適用例．． 既存手法との比較 第8章 まとめと今後の課題 謝辞 参考文献 著者業績 付録A ランダムネットワーク スケールフリーネットワーク向け 描画ツール0ぴ14﹁0ρ0
5ρ0ρOρ0ρU
0♂0り09・3ρ07・
だ067−7・7・7・7・
OO80
7°7−8
82 85 86 90 914
図目次
01⊥ワ錫345
123456789111111222222222222222
−∩∠34
つ0333
想定するネットワークモデルNBTの送信イメージ
各クライアントの受信イメージ図、、 Network DMAの受信イメージ．．．Network DMAの再送手順
マルチキャストのコストー、．、．．．．．．．．．、、．．．、、、、．、 XCASTパケットの構成図．．．．．． XCASTヘッダの構成図．．．．．．． XCASTの動作．．．．． ランダムネットワークの次数分布．． BAモデルの次数分布 BAモデルの次数分布（両対数をプロットしたもの）、 優先的選択のないモデルの次数分布． 優先的選択の無いモデルの次数分布（両対数をプロットしたもの） Pajekで作成したランダムネットワーク（ノード数200，平均次数4）NBT on XCASTの動作概要
コネクションの概念図． 有効性の検討図の一例． 遠いクライアントから送信する場合234458899245679111111111222222
−⊥ピOρU8
30δつ03
3．5 3．6 3．7 近いクライアントから送信する場合 クライアント毎に再送する場合 ．．．
XCASTグループ毎に再送する場合
0りつ04
つ044
−⊥9一904’0
44444
NBT on XCASTを実装したネットワーク． ． ． NBT on XCASTのシステム構成図．．．． 最初のクライアントの参加．．◆．．．．．． ． 2番目のクライアントの参加t．．．．．．．．． ．．． ． ．． ルータの動作結果 ．．．．．．．．．．．．．． ．．．．． ．．7．7・0ピー︵∠
4−445’0
5．1 5．2 5．3 5．4 視覚化パターン1．．． 一一、 ．．． 視覚化パターンll ． ． ． ．．． ． 視覚化パターンMa ． ． 視覚化パターンHlb ． ． ．． ．．．67189
⊂U︻OFO5
123456789666666666
ユ234
77．77
視覚化パターン1（ノード数200）．．．．．．．．．．．．．．．．． 視覚化パターン1（ノード数400）．．．．．．．．．．．．．．．．． ． 視覚化パターン1（ノード数800）．．．．．．．．．．．．．．．．． ． 視覚化パターンll（ノード数200） ．．．．．．．．．．．．．．，． ． 視覚化パターンll（ノード数400）．．．．．．．．．．．．．．．． 視覚化パターンll（ノード数800） ．．．．，．．．．．．．．．．． ．． 視覚化パターンll（ノード数200，クライアントを選択した場合）． ．． 視覚化パターン皿（ノード数400，クライアントを選択した場合） ． 視覚化パターン皿（ノード数800，クライアントを選択した場合） ． 視覚化パターンMbの使用例1 ． ． 視覚化パターン皿bの適用例2 ． ． 適用例3 ．．．．． 適用例4 ．．．．、 ・ ・ ． ． ． ． ・ ■ ■ ● ・ ・ ， ． ． ・ ・ ◆ ■ ．112334455777777777
． ． ． ． ． 78 ． ． ． ． ． ． ． ． ． 79 ． ．． ． ． ． 80 ．．．．．． ．． 81図目次 6
−り白3
AAA
ランダムネットワーク（ノード数200）．．，．． ． ． ． BAモデルネットワーク（ノード数200）．．．．． ． ． ◆ 優先的選択のないネットワーク（ノード数200） ． ． ．n∠003
0己0∪0ゾ
表目次
3．1 3．2 3．3 3．4 制御情報（サーバ側）．．．．．．．．．．．．．．．．．．．．．．．．． 制御情報（クライアント側）．．．．．．．．．．．．．．．．．．．．．． 理論的解析による評価．．．．．．．．．．．．．．．．．．．．．．．． NBT on XCASTにおける再送方法と再送タイミングの組み合わせ340∩∠
つOqδ44
8
第1章
はじめに
現在，インターネット関連の技術の成長とともに，インターネットを利用するユーザ数 も常に増加してきている．また，ブロードバンドの普及率も，2007年の50．9％から2008 年の57．1％と年々増加している．そして，光ファイバーケーブルを用いて100Mbpsの 高速サービスを提供するFTTH（Fiber to the Home）などのネットワークの高速化と並 行して，ハードディスクやサービスコンテンツも大容量化の傾向が顕著になってきてい る．しかしながら，このように著しい発展を遂げるインターネットにも様々な問題が生 じてきていることも事実である．その1つとして，大容量データを配信するために必要 となる帯域の増大，データ転送方式の不適合などが挙げられる．MPEG−2により圧縮さ れた2時間前後の映画は約5GByteのデータ量になるが，この大容量データを広帯域な ADSL（40Mbps）を用いた場合，約15分でダウンロードできる．また近年では，ブルー レイディスクなどさらに大容量のデータを保存できる新世代光ディスク規格も登場して いる．高速・広帯域なインターネット環境が整ってきている現在，上述したように大容 量データの配信も可能になってきている．しかしながら，同一のGByteクラスのデータ ファイルを複数のクライアントが要求してきた場合，現在利用しているユニキャスト方式 ではサーバで必要な数だけデータを作成し，クライアントに向けて送信する．またクライ アントまでの途中経路が重なる部分においても，同一のパケットが複数個存在することに なる．このユニキャスト方式では，サーバへの余計な負荷，帯域の無駄遣いといった問題点が生じることになる．このような問題点を解決するための転送方式を提案し，そのプロ トコルを実装し，検証することは重要な課題の1つであるといえる． そこで本研究では， ・蓄積型大容量データファイルの転送 ・複数のクライアントを対象とした同一内容のデータファイルの効率的な送信 ・転送方式にマルチキャストを採用（後述するExplicit Multi−unicast） を前提とし，大容量ファイル転送を効率的に行う方式として先に提案されている順序非保 存ブロック転送方式（NBT：Non−ordered Block Transfer）の改良と実装，その性能評価を 行う． クライアントから要求されたデータをサーバが送信している間に，異なるタイミングで 他のクライアントから同一のデータを要求された場合を想定する．従来のユニキャスト方 式では，新たにデータを作成しデータの最初から送信する．そのため中継ネットワーク上 に複数個の同一内容のパケットが存在することになり，ネットワークの利用効率が大幅に 低下する．この利用効率の低下を防止するために，途中から同一データを要求したクライ アントに対して，マルチキャストでデータパケットを転送し，残りの部分は新たに転送す る順序非保存ブロック転送方式を利用し，中継ネットワークの利用効率の向上を目指して いる［1］． また，新しいプロトコルを提案する際にシミュレーションを行うことが必要不可欠であ る．提案したプロトコルの動作確認や状況ごとの動作分析などのモニタリングが必要とな るためである．そこで，シミュレーションを行うための新たな視覚化手法について提案す る．現在，様々な可視化ツールが研究されているが，基本的にある時点でのネットワーク トポロジを可視化するためのツールであり，本研究で提案するプロトコルに必要となる部 分的な状況の把握やクライアント毎の受信状況の把握，動的なネットワークに対して十分 に状況把握ができるような対応がなされていない．また，マルチキャスト対応の視覚化も 近年になって開発されている状況である．そのため，提案したプロトコルの動作確認や状 況ごとの動作分析などのモニタリングに特化した視覚化機能をもつようなシミュレーショ
第1章はじめに
10
ンの開発が必要となる．本研究では，複雑ネットワークの分野で研究されている実ネット ワークに近い特徴を持ったネットワークトポロジを作成した上で，動的なネットワークの 可視化を対象とする．さらに，インターネットの輻較状態やデータの送受信状況の可視化 に焦点を絞る．また，視覚化対象によって異なる視覚化手法を用いることで，様々な状況 に対応できるようにする．このような輻較状態などの回線状況，データの流れ，クライア ントの受信状況の把握などをリアルタイムに視覚的に把握することで，問題解決の糸口を 見つけることが容易になると考えられる． 以上を背景として，本研究では，大容量データを効率的に配信するプロトコル，ならび にそのプロトコルを実際の問題に適用する場合に必要となる視覚化手法を提案する．第2章
準備
本章では，本研究の背景となる順序非保存ブロック転送方式の構成と機能，問題点，そ の問題点を解決するために採用した既存のXCASTについて述べる．次に，提案プロト コルのための視覚化手法の関連研究について述べる．2．1転送方式
2．1．1 順序非保存ブロック転送方式
インターネット環境の整備が進む中，様々な種類のサービスが出現しており，大容量メ ディア配信サービスもその1つである．大容量メディア配信サービスは，複数のクライ アントへ大容量メディア配信を行うサービスであり，十分なインターネット環境と最適な 転送方式が求められる．しかし，従来の転送方式であるユニキャスト方式では，複数の クライアントがほぼ同時に同一の大容量ファイルを要求してきた場合に個別に転送を行 うため，中継ネットワーク上に同一のパケットが複数個存在し，帯域の無駄遣いとなる， また，同一内容のデータを複数個作成することでサーバにも無駄な負荷がかかることに なる．そこで，上記の問題点の解決策として，サーバからのデータ送信順序，および中継 ネットワーク制御方法を最適化して，ネットワークの利用効率を向上させる順序非保存ブ ロック転送方式（NBT：Non−ordered Block Transfer）が提案されている［1］［2］． NBTで第2章 準備
12
は，同一内容の大容量データを異なるタイミングで要求してきた複数のクライアントに対 して，それぞれの経路が重なっている部分に関しては同一のパケットを転送し，経路が分 かれるルータにおいてパケットのコピーを生成するマルチキャスト転送方式により，ネッ トワークの利用効率向上を目指すプロトコルである． しかしながら，論文［1］［2］では，マルチキャスト方式について詳細な検討は行われてい ない．また，論文［3］［4］では，ATMマルチキャストを用いたNBTの検討を行っている が具体的な実装までには至っておらず，また後述する問題点もある．そこで本研究では， 論文［3］［4］の問題点を解決するマルチキャストプロトコルを用いたNBTの検討を行い， 実装を行う． 2．1．1．1 NBT 本項では，NBTを用いることを想定したネットワークモデルを図2．1に示し，それに 基づいてNBTの動作手順を説明する，ト且
サーバ繊
」、
クライアントAL三」．
＿f クライアントC 図2．1想定するネットワークモデル」、
ライアントB サーバ1台，ルータ2台，クライアント3台で構成されるネットワークモデルを想定す る．クライアントAがサーバに対して大容量データを要求すると，サーバはクライアン トAに向けてデータを送信する．ここで，サーバがクライアントAに向けてデータを送 信している間にクライアントBがクライアントAと同じ大容量データを要求すると仮定 する．従来のユニキャスト方式では，サーバはクライアントAに送信中の大容量データ とは別に，クライアントBに向けて新規にデータパケットを作成し，新たにデータの最初から送信する．このユニキャスト方式では，ネットワーク上を同一内容のパケットが複数 個送信されることになり，帯域の無駄遣いとなる．また，同じデータパケットを複数個作 成・送信するサーバにも負荷がかかることになる， その解決策として提案されているのが順序非保存ブロック転送方式（NBT：Non− ordered Block Transfer）である． NBTでは，クライアントB，クライアントCがファ イルの転送時間内の異なるタイミングで同一内容の大容量データを要求してきた場合，個 別に送信するのではなく，経路が重なっている部分に対しては同一パケットを送信し，分 岐点であるルータで必要がある場合にコピーしてそれぞれに送信する．構成として，サー バは同一データに対しては一度に1つしかパケットを送｛，…しない． 図2．2にNBTを用いた送信の空間的なイメージを示す．ファイルの転送時間内の異な データファイルの最後 図2．2NBTの送信イメージ るタイミングで他のクライアントから大容量データの要求があった場合，送信中のデータ ファイルの途中からそのクライアントに送信を開始する．データファイルの最後の送信が 終了すると，再びそのデータファイルの最初から送信を開始する． 次に各クライアントの受信の時間的なイメージを図2．3に示す． ここでも，クライアントAが大容量データを受信している間（to∼tl）に，異なるタイ ミングでクライアントB，クライアントCが同じ大容量データを要求してきたと仮定す る（tl∼t2）．クライアントBは，クライアントAとデータの送信が重なる部分（tl∼t3） をクライアントAと共に受信する．クライアントAが全てのデータを受信し終わると （t3），クライアントBは大容量データの残りの部分（t3∼t4・・ to∼tl）を受信し始める． クライアントCも同様に，クライアントBと重なる部分（t2∼t4）を一緒に受信し，クラ
第2章準備
14
tl 『1
クラィァントAコ
クライアントB クライアントC tl tj tf t5・ 時間 図2．3各クライアントの受信イメージ図 イアントBが受信し終わると（t4），残りの部分（t4∼t5＝tl∼亡2）を受信する． このように，サーバは新たなクライアントに対してデータの最初から送信を行う必要が ないため，サーバの負荷軽減につなげることが可能である． また，大容量メモリ間の蓄積情報転送方式であるNetwork DMA（Network Direct Memory Access）という技術を用いれば， NBTにおけるデータ転送においてファイルの どの部分から送信するかは自由に制御できる同． 2．1．1．2 Network DMA本項では，NBTで必要となる技術の1つであるNetwork DMAについて説明する．
Network DMAのイメージを図2．4に示す． Network DMAはブロックデータととも Network DMAでは，メモリオフセットアドレスを 使用するため，クライアント側では指定された メモリアドレスに格納される， このため，受信した順序に束縛されることなく， データは正しいメモリアドレスに格納されていく， 図2．4 Network DMAの受信イメージにそのメモリアドレスを通信パケットに格納する転送方式である．通信パケットは， TCP（Transmission Control Protocol）のようにシーケンス番号で認識されるのではな く，メモリオフセットアドレスにより認識される．Network DMAはメモリオフセットア ドレスで認識されるため，クライアント側のコンピュータにおいてホストメモリに書き込 む際にCPUでの処理を省くことができ，直接メモリに書き込むという特徴がある．デー タファイルを約64KByteごとに分割し，これにメモリオフセットアドレスを追加したも のをブロック単位として扱う．メモリオフセットアドレスを使用するため，クライアント 側では指定されたメモリアドレスのメモリに格納される．このため，受信した順序に束縛 されることがなくなる． また，Network DMAは， TCPで用いられているGo Back Nによる再送ではなく Selective−retransmissionを用いている．図2．5にNetwork DMAの再送手順を示す． サーバ クライアント 再送要求された アドレスを スタック CRC32エラー CRG32エラー ALL OK 図2．5 Network DMAの再送手順 TCPでのGo Back Nでは，サーバは一定時間を経過したらタイムアウトし，送信が正 しく行われなかったとして再送を行うが，そのエラーが生じたセグメントだけでなく，そ れ以降の正しく送信されたセグメントも再送することになる．これは，スループットが減 少する原因になる．Network DMAで採用しているSelective−retransmissionでは，輻鞍
第2章 準備 16 などの原因でパケットの到着が確認できなかった場合，クライアントはそのパケットのメ モリオフセットアドレスを用いて再送要求NAK（Negative Acknowledge）をサーバに向 けて送信する．サーバでは，NAKで要求されたメモリオフセットアドレスについて，全 てのデータ転送後にまとめて再送を行う方法をとっている．クライアントは全てのデータ 受信が確認された場合のみ，ACK（Acknowledge）をサーバに返す． NBTでは，このよう なプロトコルを採用することによって，高速化を図っている．
2．1．2 従来のNBTの問題点
先に提案されたNBTでは， ATMのマルチキャスト機能を用いている［3］［4］． ATMを 用いないとすると代替のマルチキャスト機能が必要となる．本節では，その問題点につい て簡単に述べる． 2．1．2．1 ATMを用いることの問題点 先に提案されたNBTでは，下位層にATM（Asynchronous Transfer Mode：非同期転 送モード）を用いている．ATMを用いる利点としては，データや音声などの様々なメ ディアからの情報を全てセルと呼ばれる固定長ブロックに区切って多重化・転送するため 扱いやすい．また，セル内のヘッダ部分から接続先がわかるのでハードウェアで高速に接 続・転送が可能である点である．しかしATMを用いた場合，データリンク層に依存する ため，ATM網を敷設した場所でしか使用できないという使用場所の制限が生じる． 2．12．2 マルチキャスト機能の代替 ATMマルチキャストの代わりに， IPマルチキャストを使用することを検討する．マル チキャストには，送信側ベースのマルチキャストと受信側ベースのマルチキャストの2種 類がある［6］． 送信側ベースのマルチキャストプロトコルは，ST−ll（Stream Protocol Versionll）や MTP（Multicast Transport Protocol）などが挙げられる． ST』は固定経路リンクを定 義しているため，リンクまたはノードが故障した場合，代替経路が再確立されるまで送受信が保留されるという欠点がある．次にMTPは，全ての制御トラピックを，データ伝送 の伝送率を制御するマスタを通して流す必要があるため，プロトコルにおけるオーバー ヘッドの大きさが潜在的な問題になっている． 次に受信側ベースのマルチキャストプロトコルであるが，受信者側制御であるためサー バが各クライアントの異なる詳細な情報を把握することができない．NBTではクライア ント毎に制御情報が異なるため，受信側ベースのマルチキャストプロトコルは使用できな い．また，NBT実装に必要となると予想される課金システムの構築が困難になるといっ た問題点も生じる． 他にも，通常のマルチキャストは，多数のマルチキャストグループをサポートするよう に設計されているため，IP電話や遠隔会議，ネットワークゲームといった少人数による マルチキャストグループの場合，コストの面で問題が生じる． 以上のことから本研究では，データリンク層に依存しないIPマルチキャストプロトコ ルの1つであり，送信側ベースのマルチキャストであるExplicit Multi−unicastと呼ばれ るプロトコルを採用することにする． 2．1．3 Explicit Multi−unicast（XCAST） 本研究で使用を提案するExplicit Multi−unicast（以下， XCAST）について述べる． XCASTは， RFC5058で提案されている新しいマルチキャストプロトコルの1つである ［7］． 2．1．3．1 XCASTの概要 従来のマルチキャストは多数のメンバから構成されるマルチキャストグループをサポー トするために設計されている，しかし，IP電話や遠隔会議ネットワークゲームなど少 数のメンバで構成されるマルチキャストグループの場合にはコストがかかってしまう．図 2．6にマルチキャストのコスト図を示す．図2．6に示すように，従来のマルチキャストで はコストがかかるメンバ数に対して，XCASTで代替する． また，従来のIPマルチキャストが1つのマルチキャストアドレスで複数のクライアン
第2章 準備
18 コスト ＜ コスト高 XCASTが補う メンバ数 図2．6 マルチキャストのコスト lPヘッダ XCASTヘッダUDPヘッダ pay load 図2．7 XCASTパケットの構成図トアドレスを指定するのに対し，XCASTはXCASTヘッダ内で明示的に複数のクライ
アントアドレスを指定する，このことからXCASTは，サーバ側でクライアントの管理 が可能になる送信側ベースのプロトコルである．図2．7にXCASTパケットの構成図，図 2．8にXCASTヘッダの構成図を示す． XCASTヘッダは固定長部分（最初の12バイト） と可変長部分から構成される． 2．1．3．2 XCASTの動作原理 図2．9にXCASTの動作を示す．説明の簡単化のために，途中継路上のルータは全て XCASTに対応しているものとし， XCASTパケットの他の詳細も省略している［7］． サーバからXCASTパケットを受信したルータの動作は以下の通りである． 1．パケット内にリストされた宛先毎の11ext hopを決定するために，ユニキャスト ルーティングテーブルを参照． 2．next hopに基づいた宛先毎の分割0 31 VERS l ON A X D P R NBR OF DEST CHECKSUM
CHA洲EL lDENTlFlER
PROTO lD LENGTH RESV
List of Addresses and DSCPs List of Port Numbers VERS I ON＝XCASTのバージョン A＝匿名ビット X＝XCASTビット D＝DSCPビット P＝ポートビット NBR OF DEST＝宛先数 CHECKSUM＝XCASTヘッダのチェックサム CHANNEL IDENTIFIER＝チャンネル識別子 PRO†ID＝ヘッダに続くプロトコルの指定 LENGTH＝XCASTヘッダの長さ RESV＝R二予約 図2．8XCASTヘッダの構成図 ケ ト ’f−t
k−一岬ぎ
」， クライアントA レ■：：コ」
〆 ライアントB 治 辿 〔 ■IPへ・ダ ■XCASTへ・ダ ロペ・・一・ 」， クライアントC 図2．9 XCASTの動作 3．next hop毎にパケットを複製 4．複製されたパケットの宛先リストを変更 5．変更したパケットのコピーをnext hopに転送 6．next hopの宛先が1つの場合，その宛先に対してはユニキャストパケットとして パケットを送信（最適化） 上述した手順に従って，図2．9におけるXCASTの動作について説明する．ここでサー第2章 準備
20
バからクライアントA，クライアントB，クライアントCに向けてパケットを送信する と仮定する．サーバからXCASTパケットを受信したルータAでは， XCASTヘッダを解析しnext
hopを決定するためにユニキャストルーティングテーブルを参照する．その結果，クライ アントAに向けた経路とルータBに向けた経路を見つける．次に，検出したそれぞれの 経路に応じた宛先の分割とパケットの複製を行う．次に，複製したパケットの宛先リスト を変更するが，ここでクライアントAに向けた経路はクライアント数がAのみの1つで あるため，ユニキャストパケットとなる．ルータBに向けた経路はまだクライアント数が B，Cの複数であるため， XCASTパケットとして次のルータBに転送される． XCASTパケットを受信したルータBも同様にXCASTヘッダを解析するが，ルータBはクライ
アントB，クライアントCに対する最終中継ルータであるため，それぞれのクライアント に向けてユニキャストパケットを送信する． XCASTは，現在でも利用されているユニキャストルーティングテーブルを用いる．ま た，XCASTヘッダ内で各クライアントを把握できることから，送信側ベースのマルチ キャストプロトコルであり，サーバ側でクライアント情報を管理するNBTの実装に最適 である． 本節では，NBTで使用を提案するXCASTについて述べた． XCASTを用いる利点は， ・データリンク層に依存しないため，使用領域に制限がない． ・送信者はあらかじめ受信者を把握している． ・パケットはユニキャストルーティングテーブルに基づいて受信者まで配送される． ●多数のグループやソースが存在可能． ・実装が容易 などが挙げられる．2．2 ネットワークの視覚化
本節では，XCASTを用いた順序非保存ブロック転送方式のための視覚化に関する関連 知識について述べる．2．2．1視覚化対象（ネットワークモデル）
これまで，実ネットワークのネットワークモデルとして考えられてきたランダムネット ワークは，正方格子のように規則的なネットワーク構造ではなく，不規則性を有するネッ トワーク構造である．しかし，実ネットワークは，ランダムネットワークとは異なる特徴 であるスケールフリー性を持っている［8］［9］．そこで，本節ではランダムネットワークモ デルと本研究で使用対象となるスケールフリーネットワークについて述べる（具体的なグ ラフ描画については付録参照のこと）． 2．2．1．1 ランダムネットワーク これまで，インターネット，WWW（World Wide Web）などの複雑なネットワークの 構造はランダムネットワーク構造であると考えられてきた．ランダムネットワークは，そ れぞれのノード同士をランダムにリンクで結ぶことで生成される．ランダムネットワーク の生成アルゴリズムを以下に示す［10］． Step1：ノード数1Vと平均次数〈k＞を指定． Step2：次のように結合確率pを定義 〈k＞ （2．1） P＝ N−1 Step3：全てのノードの組み合わせに対して，上記の結合確率pでノード間にリンクを 結合．第2章 準備
22
Q25Q2
Q15ま
Ql
QC5 00舌
図2、10 ランダムネットワークの次数分布図2．10にノード数2000，平均次数4のネットワークを20個生成し，その次数分布の 平均を取ったグラフを示す． 図2．10に示したように，ランダムネットワークの次数分布は，指定した平均次数と同 じ次数を持つノードが最も多く，平均次数より大きい次数を持つノードの個数は急激に減 少する．これはボアソン分布と呼ばれ，以下の式に従う．
P（k）一・一〈・〉〈IP （2．2）
ランダムネットワークは，次数の小さいノードは存在するが，次数の非常に大きなノー ドは存在しないネットワークである．しかし，現実の様々なネットワークは，次数分布が ボアソン分布に従わないようなネットワーク構造を持っている［8］［9］． 2．2．1．2 スケールフリーネットワーク（BAモデル） これまで，インターネットやWWW，代謝ネットワーク，共著ネットワークなどのネッ トワーク構造についての研究が行われ，現実のネットワークの構造が明らかになってきた ［8］［9］．その結果，実ネットワークの特徴は，次数の小さいノードの存在する確率は非常に 大きいが，次数が大きくなるにつれてその確率は小さくなる．しかし，非常に大きい次数 を持つノードの存在する確率は，ランダムネットワークのボアソン分布よりは大きい．こ の特徴を持つ代表的なBarabdsi−Albertモデル（BAモデル）のネットワーク生成アルゴ リズムを以下に示す［10］． Step1：mo個のノードを用いて完全グラフを生成． Step2：ネットワークの中からm個のノードを以下のような確率で選択． rl（i）。d， （2．3） ここで，kiはノードiの次数とし， n（のはノードiを選ぶ確率がそのノードの次数 毎に比例することを表す． Step3：m本のリンクを持つ新たなノードをStep2で選ばれたネットワーク内のノードに 追加． Step4：Step2とStep3を繰り返す．第2章準備
24
QB Q7 Q6 Q5 蓮Q4 Q3 Q2 Q1 図2．11 BAモデルの次数分布 本研究ではアルゴリズムのパラメータmをm＝1としたためループのない木構造にな る．m＞1の場合は，ループのあるネットワークが生成される． 図2．11にノード数2000のネットワークを20個生成し，その次数分布の平均を取った グラフを，図2．12に，図2．11の次数分布を両対数プロットしたグラフを示す．このよう に，次数分布が直線になり，べき乗則に従っていることがわかる， 次数分布がべき乗則に従う性質をスケールフリー性といい，スケールフリー性を持つ ネットワークをスケールフリーネットワークという．スケールフリーネットワークの次数 分布は， P（k）c（k−7 （2．4） と表すことができる．ここで7はべき指数であり，多くのネットワークが7＝2∼3で ある［8］［91． このスケールフリー性を特徴付ける生成概念として，優先的選択（preferential attach− ment）と成長するネットワーク（growth network）がある［10］［11］．優先的選択とは，次 数の多いノードほどノードが追加される確率が高く，時間がたつほどにさらに次数が大きN“
㌔
図2．12BAモデルの次数分布（両対数をプmットしたもの） くなることであり，成長するネットワークとは，ノード数やリンク数が固定でなく，時間 とともに次々と追加されていくことである．この2つの生成概念に基づいて，べき乗則に 従った次数分布を持つネットワークが生成される．第2章 準備
26
2．2．13 優先的選択がない場合のBAモデル 前項では，スケールフリーネットワークを生成するために必要な条件として，優先的選 択と成長するネットワークについて述べた．本項では，この条件の重要性の確認のため， 優先的選択という条件がない場合について述べる［10］． 優先的選択のないネットワークモデルを生成するために，前項のアルゴリズムのStep2 を変更したアルゴリズムを以下に示す． Step1：mo個のノードを用いて完全グラフを生成． Step2’：ネットワーク内のm個のノードをランダムに選択． Step3：m本のリンクを持つ新たなノードをStep2’で選ばれたネットワーク内のノードに 追加． Step4：Step2’とStep3を繰り返す． 優先的選択のない帥モデルの汰数分布 O．6 0．5 0．4 書・・ O、2 01 0 0 5 ’こ 話0斥
・i麟轟
15 20 図2．13 優先的選択のないモデルの次数分布優先的選択のないBAモデルの攻数分布 O．1 0．Ol 竃 ： o．OOOOI IB ’ 100 図2．14 優先的選択の無いモデルの次数分布（両対数をプロットしたもの）
第2章 準備
28
また，図2．13に，ノード数2000のネットワークを20個生成し，その次数分布の平均 をとったグラフを，図2．14にその両対数プロットした場合のグラフを示す． このように，優先的選択の無いネットワークモデルでは，実ネットワークの特徴に近い スケールフリーネットワークが生成されないことがわかる． 以上のことから，本研究で使用するネットワークモデルは，実ネットワークの特徴に近 い特徴を持ったスケールフリーネットワークを生成し，その目的に応じた視覚化を対象と する．2．22 既存の視覚化手法／ツール
情報視覚化分野では，対象となるオブジェクトをわかりやすく表示するための美的描画 条件の提案や効率的なアルゴリズムが開発されている［12］［13］［14］［15］［16］［17］［18］［19］［20］． また，視覚化ツールも開発されている［21］．たとえば，代表的なネットワーク分析ツール ではPajekなどがある［22］．例として，図2．15に， Pajekで作成したノード数200，平 均次数4のランダムネットワークを示す．またネットワーク分野では，リンクを有向グラ フや木構造で表現する手法を用いて，複雑で大規模なインターネットの構造を視覚化する 研究が行われている．たとえばCaidaでは，ネットワークトラヒックやネットワーク構 造など，様々なネットワーク情報を視覚化するためのツールを提供している［23］．また近 年では，アドホックネットワークのための視覚化シミュレータも研究されている［24］［25］． しかしながら，これらのネットワーク可視化ツールやネットワーク分析ツールは，ネッ トワークのトポロジを描画し，様々な指標を計算することはできるが，基本的にある時点 でのネットワークトポロジを可視化するためのツールである．最近になって，動的なネッ トワークの可視化を対象とした研究も行われている［26］．これは，シミュレーションに よって構築した動的なネットワークをリアルタイムに描画し，全体的な動的な変化を理解 しやすくするための機能を提供している．1nyout 〔㎞ePtthly 跨酬誕 陸垣ra牌 胤† 〔吊，mos ε馴， fP拍 M領 h佃
●
＼ノー× ，一●
30
第3章
NBT on XCASTの提案と検証
2章では，提案されているNBTとその問題点について述べた．先に提案しているATM マルチキャストを用いたNBTでは，使用場所の制限などの問題がある．また実際に実装 までは至っていない．以下では，本研究で提案するXCASTを用いたNBTとその実現方法について検討する．また，XCASTを用いたNBTをNBT on XCASTと命名する．
3．1 NBT on XCAST
2章で述べたマルチキャストプロトコルの欠点を補う新しいマルチキャストプロトコルとして，RFC5058でXCASTが提案されている［7］． NBTを実装する上でXCASTを川
いる利点として， ・データリンク層に依存しないため，使用領域に制限がない． ・送信側制御であるため，各クライアントの異なる情報を把握しやすい． ・多数のグループやソースが存在可能． ●実装が容易． などが挙げられる．上記のことから，NBTを実装する上で最適なプロトコルである［27］．本研究では，このプロトコルを用いてNBTを実装する．図3．1にNBT on XCASTの
動作概要を示し，この図を用いてNBT on XCASTの動作について説明する．O t t2 t
クラィァン・・［＝コ＝：工＝コ
t t5 クライアントB クライアントC 時間 図3．1NBT oll XCASTの動作概要 クライアントAが受信しているデータと同一のデータを，クライアントBが時間tlに 要求，その後クライアントCが時間t2に同一のデータを要求したと想定する．まず，ク ライアントAのみの場合（to∼tl）は，サーバはユニキャストパケットとしてクライア ントAにデータを送信する．クライアントBが時間tlに同一データを要求すると，ク ライアントが複数になるため，サーバはクライアントA，クライアントBのアドレスを XCASTヘッダ内に明示的に示し， XCASTパケットとして送信を始める（t1∼t2）．次 にクライアントCが時間t2に同一データを要求すると，時間t2∼t3においてクライアントA，クライアントB，クライアントCのアドレスをXCASTヘッダ内に明示的に示
し，先ほどと同様にXCASTパケットとして送信する．時間t3になると，クライアント Aは要求したデータを全て受信したので，参加していたXCASTグループから離脱する． 時間t3でデータの最後に達するが，まだデータを受信しているクライアントが存在する ので，サーバは送信していたデータの最初から再び送信を開始する．クライアントB，ク ライアントCは時間t3∼t4において，受信していないデータの前半部分を受信し始め る．この時点でクライアントB，クライアントCの2つのクライアントが存在するため， サーバはXCASTパケットとしてデータを送信することになる．以下同様にして，全て のクライアントが要求したデータを受信し終えるまで，サーバは繰り返しデータを送信し 続ける．第3章 NBT on XCASTの提案と検証
32
3．2 NBT on XCASTが必要とする機能
本節では，NBT on XCASTを実装する上で必要となる機能について説明する．クライ アント毎に異なる制御情報を管理する機能とコネクションを管理する機能の2つがある． NBT on XCASTを適用する環境では，これらの機能が備わっていると想定する． 3．2．1 制御情報管理機能 NBT on XCASTで必要となる制御情報には，サーバ用の制御情報とクライアント用の 制御情報の2種類がある．サーバ側の制御情報で管理する必要があるパラメータは以下の ものがある．表3．1にサーバ側で使用する制御情報とその説明を示す． また，クライアント側で管理するパラメータは以下のものがある．表3．2にクライアン ト側で使用する制御情報とその説明を示す．表3．1 制御情報（サーバ側） 制御情報 説明 コンテンツ 各クライアントが要求するコンテンツ． ｡数コンテンツに対応． クライアント数 同一の大容量データを要求してきたクラ Cアント数．最後のクライアントに対し ﾄ，データ送信の終了時に必要． 蓄積型大容量データの最初・最後のメモ 潟Iフセット 複数のクライアントが大容量データを要 ≠ｵてきた場合，繰り返しデータを送信
ｷるために必要
クライアントに送信するデータの最初と ﾅ後のメモリオフセット 各クライアントが必要なデータを受信終ｹ時に，XCASTグループから削除する
鼾№ﾉ必要
送信したメモリオフセット 途中参加のクライアントに関して必要と ﾈるパラメータ． 次に送信するメモリメモリオフセット クライアントでのパケットロス検出で使 p． 送信済みデータサイズ 現在までに送信したデータサイズ． 蓄積型大容量データの全サイズ 送信するデータの全サイズ．クライアン gでのパケットロス検出で使用．第3章NBT on XCASTの提案と検証
34
表3．2制御情報（クライアント側） 制御情報 説明 コンテンツグループ クライアントが要求するコンテンツ．複 買Rンテンツ対応． 送受信状態 自分の参加状態を把握するために使用． 受信開始位置と受信終了位置 クライアント毎に異なる受信開始位置と 信終了位置． クライアントが要求したデータの最初と ﾅ後のメモリオフセット クライアントが要求したデータの最初の ＜c潟Iフセットと最後のメモリオフセ bト． 現在受信したメモリオフセット クライアントが現在受信したメモリオフ Zット．パケットロス検出に必要． 次に受信するメモリオフセット クライアントが次に受信する予測メモリ Iフセット．パケットロス検出に必要 受信したデータサイズ 現在までに受信したデータのサイズ． 蓄積型大容量データのサイズ 受信するデータのサイズ．クライアント ﾅのパケットロス検出で使用．3．2．2 コネクション制御管理機能
NBT on XCASTでは， NBT転送データと制御情報データのコネクションは別々のコ ネクションとした．つまり，データ転送用コネクション（XCAST／UDP）と制御情報用 コネクション（TCP）の2つのコネクションを使用した．図3．2にコネクションの概念図 を示す．このようにコネクションを2つに分けて管理することで，全体の制御が容易に なる． ・……・一・一怐c………●
r− ff クライアントA」
if・一一・i］v−tStA
データ送信用コネクション クライアントC ・・…・…・…… ｧ御情報用コネクション 図3．2 コネクションの概念図 蓄積型大容量データを要求する各クライアントは，制御情報用コネクションを用いて サーバにデータを要求する．サーバは，現在のクライアント状況やデータ配信状況など NBTを利用する上で必要な各種情報を，制御情報用コネクションを用いてクライアント に送信する．次にサーバは，クライアント毎に作成した制御情報管理テーブルを参照しな がら，データ転送用コネクションを用いて各クライアントヘデータを送信する．3．3 NBT on XCASTの有効性の検討
本節では，従来のユニキャスト方式と提案したNBT on XCASTとの比較を行い， NBT on XCASTの有効性の検討を行う［28］．第3章NBT on XCASTの提案と検証
36
蓄積型大容量データを送信する際に，従来のユニキャスト方式では，同一内容のデータ を要求してきたクライアントに対して個別に送信するため，中継ネットワーク上に複数の 同一内容のパケットが存在することになる．また，マルチキャスト方式はその同報性によ り，ある一定期間だけ待機した後に，その待機中にデータの要求を行ったクライアントに 対して一斉に配信する方式である．このため，マルチキャストクライアントは，自分が要 求を行ってから実際にデータが配信されるまでの待ち時間が発生する．提案手法で採用し たXCASTでは，クライアントが要求を行った時点からデータを配信することが可能で あるため，クライアントの待ち時間が発生しない．以上のことから，NBT on XCASTで は，複数のクライアントに対して途中までの経路が重なる部分に関しては，マルチキャス トの特徴から1つのパケットが存在するので，帯域消費量は最小に押さえることができ る．また，マルチキャスト方式で発生する待ち時間についても改善できる． ユニキャスト方式とNBT on XCAST方式の場合を比較するための比較検討を行う ネットワーク図を図3．3に示す．説明の簡単化のために，単純化したネットワーク図を用 いて有効性の検討を行う． 今，サーバからルータまで距ee Lの等間隔でn個直鎖状に接続されているとする．各 ルータには1つずつクライアントが接続されているとする． クライアント2 クライアントn」 」
φ ．：t サーバ v ルータ1 ルータ（n−1）lY6Y煕…●Y已
i 」， 」， i
i クライアント1 クライアント（n−1） i nL 図3．3 有効性の検討図の一例各クライアントに大容量データを転送するのに必要な帯域幅B，時間T，伝送距離L の積の和である帯域距離消費量Aをもってネットワーク利用効率を示す指標とする，な お，ルータ間の中継網の消費の削減が本研究の主題であるため，ルータとクライアント間 のアクセスラインの伝送距離は無視する． 3．3．1 ユニキャストの場合 従来のユニキャスト方式では，同一内容のデータを要求してきたクライアントに対して それぞれ個別にデータを作成し送信する．この場合，各クライアントに対して個別の帯域 が必要になるため，ユニキャスト方式の帯域距離消費量ALは，以下の式で与えられる． n
Au−DBTL一牛n（n＋1） （3ユ）
iニ1 従来のユニキャスト方式では，同一内容のデータを要求してきたクライアントに対して 個別に送信する．そのため，中継ネットワーク上に同一内容の複数のパケットが存在する ことになり，サーバの負荷の増大，ネットワーク利用効率の低下の原因となる．式（3．1） から，ユニキャスト方式の帯域距離消費ig Auは，クライアント数nの2乗に比例するこ とがわかり，スケーラブルでないといえる．3・3・2 NBT on XCASTの場合
NBT on XCASTの有効性の検討を行うために，クライアントnからクライアント1 へ送信を始める場合と，クライアント1からクライアントnへ送信を始める場合で見て いく． ①クライアントnから送信を始める場合． 簡単化のため，クライアントnからクライアント1に向けて順番に間隔T／nをおいて 送信を開始すると仮定する．図3．4にクライアントnからクライアント1に向けた送信 のイメージを示す． 図中の色付き部分が，そのクライアントがサーバから最も遠い位置となる時間帯であ る．この時間帯とクライアントが接続されるルータまでの距離の積を加算すると，NBT第3章 NBT on XCASTの提案と検証
38
クライアントn nLクライアー）1，T／・＝（n−1）・
クライアント（n−2） ： ： クライアント2 クライアント1 （n−2）L［＝＝ココ2L
iT／n L 時間t 図3．4 遠いクライアントから送信する場合 OII XCASTの帯域距離消費量An（遠いクライアントから送信する場合）を求めることが できる． T T TAnニBT・nL十B・一（n−1）L十B・一（n−2）L十…十B・−L
n n γλ一n肌＋B募L巳
z＝1 （3．2） n−1 ＝BTL（n＋ 2） BTL ＝2（3n −1） 式（3．2）から，NBT on XCASTを用いた場合の帯域距離消費量．Aれは，クライアント 数nに比例することがわかる， （ii）クライアント1から送信を始める場合 （i）とは逆に，クライアント1からクライアントnに向かって間隔T／nをおいて送信を 開始すると仮定する．図3．5にクライアント1からクライアントnに向けた送信イメー ジを示す．T クライアント1 クライアン・・】・川 クライアント3 k l ： ： クライアント（n−1） クライアントn L
￡コ＝：＝：コ2L
・／・рd：［＝：＝］3L
［：［＝：コ（・−1）・
1，T／n−・L
時間t 図3．5 近いクライアントから送信する場合 図の色付き部分がそのクライアントがサーバから最も近い位置となる時間帯である． この時間帯とクライアントが接続されるルータまでの距離の積を加算すると，NBT on XCASTの帯域距離消費量An（近いクライアントから送信する場合）を求めることがで きる． T 7「 BT T ／4n＝一・nL十B−・2L→−B−・3L−←… 十B−・（n−1）一｝−BT・nL n n n γL−B；L￡＋BT・nL （3．3）
i＝ 1 BTL＝2（3卜1）
式（3．3）から，NBT on XCASTを用いた場合の帯域距離消費量Anは，クライアント 数nに比例することがわかる． また式（32），（3．3）が等しくなることから，NBT on XCASTを用いた場合の帯域距離 消費量Anは，順序に関係なくクライアント数nに比例し，従来のユニキャスト方式と比 べてNBT on XCASTの有効性が期待できる．第3章 NBT on XCASTの提案と検証
40
表3．3 理論的解析による評価 一 転送方式 帯域距離消費量：クライアント数に対するオーダー 従来 ユニキャスト方式 ん一牛π（n十1）・0（η2） 本研究NBT on XCAST方式
A。一牛（3η一1）・0（η） 以上の結果を表3．3にまとめる．3．4 NBT on XCASTの転送能力
本節では，NBT on XCASTの転送能力について述べる［29］． ファイルサイズG，帯域幅Bとするとファイルの転送時間Tは以下の式で与えられる． GT二万 （3・4）
そのファイルの転送を同時に要求するクライアント数をn，サーバが同時にm個のデー タを処理可能とすると，単位時間当たりの総転送数Nhは，次の式で与えられる．N・一：一竿 （3・5）
m＝1，tn＝64（XCASTグループの上限メンバ数［7］）， BニIGb・it／s， G＝5GBとす ると，1日あたりに処理できるクライアント数1Vは， 1V＝1．4×105 （3．6） となる．これは，IGbit／sのアクセス網が利用可能という条件下ではあるが，実用性があ る数字であると考えられる．3．5 NBT on XCASTの再送方式
本節では，インターネットの輻綾や障害などの原因によってパケットロスが発生した場 合に，その部分のデータを再送する方式について考察する［29］［30］． NBT on XCASTの再送方式には，それぞれ2通りの再送方法，および再送タイミング が考えられる． 再送方法 （i）クライアント毎に損失したパケットをユニキャストで再送する． （li）同じデータを要求したクライアントが属するXCASTグループに対して，損失し たパケットをXCASTで再送する．第3章NBT on XCASTの提案と検証
42
再送タイミング （hi）サーバが各クライアントからパケットの再送要求を受けた時点で個別に再送する． （iv）サーバが，一通りのファイルを送信し終えた後，再送要求のあったパケットを一括 して再送する． NBT on XCASTの再送は，上記の再送方法と再送タイミングの4通りの組み合わせ で考えることができる．表3．4に，NBT on XCASTにおける再送方法と再送タイミング の組み合わせを示す． 表3．4 NBT on XCASTにおける再送方法と再送タイミングの組み合わせ 再送方法 再送タイミング 再送要求受信時 一括 ユニキャスト （i），（苗） （i），（討）NBT on XCAST
（皿），（通） （皿），（w） 次に，表3．4に示した組み合わせについて考察する．また，クライアント毎に再送する 場合とXCASTグループに対して再送する場合のイメージ図についても示す， 1）クライアント毎に再送する場合 図3．6にクライアント毎に再送する場合のイメージ図を示す． クライアント毎に再送を行う場合，全てのクライアントのデータ受信状況を個別に管理 しなければならない．また，クライアント毎に再送するため，個別にパケットを作成する 必要がある．たとえば，図3．6では，各クライアントが共通のパケット番号「5」を要求 していると仮定する（他のパケット番号はクライアント毎に異なるとする）．サーバでは， 再送要求のあったパケット番号「5」を再送を必要とするクライアント数分作成し，送信 する．これはサーバの負担の原因になる．また，ネットワーク上に同じパケットが複数個 存在することになり，ネットワーク帯域の無駄遣いの原因になる．このように，同じ内容のパケットを複数のクライアントに送信する場合は効率的ではない．この方式を採用する 場合は，再送はタイミング世）で転送するのが妥当であると考えられる．
1
13
サーバ口＼
●ト
受信者状況管理 クライアント＃1：3，5 クライアント＃2：5，84 」，＿41㍉
ク漣ク誹2ク注藩
35 58 59 …i
図3．6 クライアント毎に再送する場合 C第3章NBT on XCASTの提案と検証
44
2）XCASTグループに対して再送する場合 図3．7にXCASTグループ毎に再送する場合のイメージ図を示す． XCASTグループに一括して再送を行う場合，クライアントが再送要求を行ってから， 実際に再送データを受信するまでに時間がかかる可能性があるが，再送する際に作成され るパケットは1つだけなので，サーバの負荷が軽減される．たとえば，図3．7では，各ク ライアントが共通のパケット番号「5」を要求していると仮定する（他のパケット番号はク ライアント毎に異なるとする）．サーバでは，再送要求のあったパケット番号「5」を作成 する．グループに対して再送を行うため，作成するパケットは再送要求を行ったクライア ント数に関係なく一つである．これにより，サーバの負担の軽減につながる．また，ネッ トワーク上の再送パケットも一つですむため，ネットワーク帯域の節約につながる．再送 はタイミング（iv）で行う． ●、 ノ サ 0直ξー （siiiiii））ルータ／1・一
受信者状況管理 グループA：3，5，8，9 グループB： グループn：」
．〆 クライアント＃1 35 ＿i、 クライアント＃2 5 8 ・一…・ vi、， クライアント＃nA■田βc
5 9 図3．7XCASTグループ毎に再送する場合 以上のことから，NBT on XCASTにおけるパケットロスの再送については，ファイル46
第4章
NBT on XCASTの動作確認実験
第3章で提案したNBT on XCASTの構成に基づいて，本章ではNBT on XCASTの
実装方法について述べる［31］［32］．本研究では，Ct 1一語で実装を行った．4．1実験概要
本節では，NBT on XCASTの実装方法ならびに実験方法について述べる． NBT oll XCASTを用いてデータを送信するサーバ用のプログラムと，サーバにデータを要求する クライアント用のプログラムが構成要素となる．4．1．1 実験用ネットワーク構成
NBT on XCASTに必要なプログラムは，サーバ用，クライアント用各プログラムとルータのXCASTプログラムの3種類である，図4．1にNBT on XCASTを実装した
ネットワークを示す． サーバと各クライアントに，今回作成したそれぞれのプログラムを実装する．また， サーバ，ルータにはXCASTを実装する．サーバ tl クライアント r 一s ．79．65．110 ルータ
●
133．79．65． ライアント ！ o ジ 133．79．65．126 NBT on XCASTを実装したネットワーク 133．79．65．81 図4．14．1．2 NBT on XCASTのシステム構成
図4．2に作成したNBT on XCASTのシステム構成図を示す． ．、………NBT on XCAST………・、 ．’………XCASTグループー一一・’一・、 i 1 i ；i−←4・パ…
l／↑制御情報の更新 i i’・
図4．2 NBT on XCASTのシステム構成図 データの最初の要求者であるクライアントの転送要求は，まずNBT on XCASTの制 御情報部に接続される．制御情報部では，NBT on XCASTに関する必要な情報を作成 し，それをクライアントに送信する．その後，制御情報部はデータ転送部をスレッドとし第4章NBT on XCASTの動作確認実験
48
て起動する［33］．次に，データ転送部では，クライアントが要求したデータを制御情報に 基づいて送信する．ここで，NBT on XCASTで必要な制御情報を刻々と変化するため， 制御情報部とデータ転送部は常に制御情報の更新と交換を行う．以下に，更新する必要が ある制御情報を示す． ・クライアント識別番号 ・各クライアントへの送信開始データブロック番号 ・各クライアントへの送信終了データブロック番号 ●現在送信中のデータブロック番号 ・次に送信するデータブロック番号 ・送信済みデータサイズ 2番目以降のクライアントは，最初のクライアントと同様に制御情報部に接続され，最 新の制御情報を取得した後，XCASTグループに参加してデータ転送部から要求したデー タの受信を開始する．クライアント毎に異なるデータ受信終了条件は，サーバとクライア ント間の制御情報に基づいて決定される． また，複数のクライアントからの異なるデータの転送要求に対しては，各クライアント からの要求を要求受信時に識別することによって対応する．同じデータを要求した複数のクライアントを1つのXCASTグループにまとめ，異なるXCASTグループを複数作成
することによって，複数の異なるデータ要求に対応する． 4．1．3 実験用プログラムXCASTのプログラムを用いるためには，サーバやクライアントは全てXCAST対
応である必要がある．これは，クライアントへのサービス面を考慮した場合，NBT onXCASTには適さない．しかし，クライアントはXCAST対応の必要はないがサーバに
対してXCASTグループに参加するために必要な情報を送信する必要がある． そこで本研究では，NBT on XCASTに必要となる制御情報を利用して，クライアントがXCAST非対応でもXCASTグループに参加できるようにした．またサーバでは，最
初のクライアントのデータ要求受信後，制御情報作成やデータ転送処理を行い，XCAST パケットの作成・転送を行う．2番目以降のクライアントに対しても同様の処理が必要で あるが，NBT on XCASTの主題であるサーバの負荷の軽減といったことから，同じ処理 をクライアント数分繰り返すことは問題である．そこで，2番目以降のクライアントは制 御情報作成などの必要最小限の処理を行ったあとは，XCASTヘッダのアドレス追加（削 除）のみでデータ転送が開始（終了）できるようにした［34］［35］［36］［37］［38］．
