［特別招待講演］ネットワークコーディングとデータ転送の高速化 [Special

୍⯡♫ᅋἲே 㟁Ꮚ᝟ሗ㏻ಙᏛ఍ ಙᏛᢏሗ‫ٻ‬
‫ٻڇڮڞڤکڪڭگڞڠڧڠٻڡڪٻڠگڰگڤگڮکڤٻڠڣگ‬
信学技報
‫ٻۏۍۊۋۀڭٻۇڼھۄۉۃھۀگٻڠڞڤڠڤ‬
社団法人 電子情報通信学会
‫ٻڮڭڠڠکڤڢکڠٻکڪڤگڜڞڤکڰڨڨڪڞٻڟکڜٻکڪڤگڜڨڭڪڡکڤ‬
TECHNICAL
‫ٻڄڏڋڈڏڌڋڍڃڑڈڏڌڋڍڬڞڇڒڈڏڌڋڍڮڞ‬
THE INSTITUTE OF ELECTRONICS,
REPORT OF IEICE.
‫ٻ‬INFORMATION AND COMMUNICATION ENGINEERS
［特別招待講演］ネットワークコーディングとデータ転送の高速化
中里
秀則†
† 早稲田大学理工学術院 〒 105–0123 東京都新宿区大久保 1–2–3
あらまし
ネットワークコーディングを利用することでピア・ツー・ピア方式でのデータの配送を高速化できること
が知られている。一般にネットワークコーディングとは、エンド・ツー・エンドのデータ転送において、送信ノード
以外の中間ノードでも、符号化により、複数のデータから新たなデータを生成することができる仕組みのことを指す。
ピア・ツー・ピアデータ配送システムにおけるネットワークコーディングは、各ピアでデータの符号化をできること
を意味する。本稿では、まず各ピアでデータの符号化が可能なネットワークコーディングとデータ配送の高速化の関
係について述べ、そのシステムにおける最適なネットワークコーディングについて解説する。
キーワード
ネットワークコーディング、コンテンツ配送、ピア・ツー・ピア、ビットトレント、最適化
[Special Invited Talk] Network Coding and Speedup of Data Transfer
Hidenori NAKAZATO†
† Faculty of Science and Engineering, Waseda University
Abstract Network coding is known to speed up peer-to-peer data distribution. In general, network coding means
the mechanism which enables encoding, and consequently generating new data from multiple input data at intermediate nodes in end-to-end communications. In peer-to-peer data distribution systems, network coding means coding
capability at every peer. In this paper, the relation between network coding and acceleration of peer-to-peer data
distribution is explained, and then optimal network coding is discussed.
Key words Network Coding, Content Distribution, Peer-to-Peer, BitTorrent, Optimization,
P2P ファイル共有システムの中で、現在もっとも広く利用さ
1. は じ め に
れているシステムが BitTorrent である [1]。BitTorrent では、
ファイルをダウンロードしながら、一方でファイルの供給元
「ブロック」という単位に
一つのファイルを図 1 に示すように、
にもなるという、ピア・ツー・ピア形式（P2P）でのファイル
分割して転送を行う。ピアは隣接ピアとの間で、このブロック
共有が広く使われている。P2P 以前のファイル共有システムで
を単位として相互に送信、受信を行う。ブロックを隣接ピアか
は、もともとのファイルを保持している一つのピア（サーバ）
らダウンロードしようとするピアは、複数有る隣接ピアが所持
から、複数のピア（クライアント）がそのファイルをダウン
していないブロックをできるだけダウンロードしようとする。
ロードするという、サーバからクライアントへの一方向のデー
これが “Rarest-First” というブロック選択基準である（図 2）。
タ転送が行われる。一方、P2P ファイル共有では、もともとの
また、ブロックのダウンロード要求を受けたピアは、必ずしも
ファイルを保持しているピアだけでなく、そのファイルのダウ
すべてのピアにブロックを転送するのではなく、自分にブロッ
ンロードを完了したピアも、今度はそのファイルのサーバとし
クを送ってくれているピアを優先して、ファイルの転送（アッ
て機能をする。つまり、P2P ファイル共有では、ピアはクライ
プロード）を行う。このポリシーは “Tit-for-Tat” と呼ばれる。
アントであると同時にサーバとしても機能することになる。
ネットワークコーディングとは、データを転送するネットワー
ファイル
1
ブロック
図1
2
3
クの内部でデータの符号化を行うデータ転送方式である [2]。典
4
ピース
BitTorrent におけるファイルのブロック分割
型的なネットワークコーディングの例として示されるのが、図
3 のような、いわゆるバタフライネットワークである。この例
では、情報源であるノード S にある二つの情報 a と b をノー
ド Y と Z まで配送しようとする。ここで情報 a と b は同じサ
イズであり、ノードを結ぶすべてのリンクの帯域は、1 ラウン
—1—
- 33 This article is a technical report without peer review, and its polished and/or extended version may be published elsewhere.
Copyright ©2014 by IEICE
合に、データ転送が高速化される理由についてまとめており、
この結果を受けて、以降の 3., 4., 5. で様々な最適化について説
明を加える。3. では、符号化を行うピアの選択方法について、
F
I
L
4. では転送するブロックの選択方法について、また 5. では符
E
号の生成比率について、それぞれ最適な手法について述べてい
Rarest-Firstブロック選択
Candidates
#
F
2
I
1
L
3
E
3
る。最後に、6. で本稿をまとめ、今後の課題について述べる。
Tit-for-Tat
2. 符号化によるデータ配送の高速化
並列ブロックダウンロード
BitTorrent にランダムリニア符号を適用した方式として、
Avalanche という方式が提案されている [3]。この提案の中で、
符号化を使用しない BitTorrent、すべてのピアで符号化を行う
図 2 BitTorrent のブロック交換
ネットワークコーディング、および情報源のピアのみで符号化を
行うソースコーディングの比較を行っている。この比較結果で
ドで a か b のいずれか一つを配送できる容量である。すると、
もし符号化を使わない場合、ノード W から X へのリンクがボ
は、ソースコーディングでも、符号化を使用しない BitTorrent
に比べて、データの配送時間が 40%程度改善されることが示さ
トルネックとなり、a と b の両方をノード Y と Z に配送する
れている。つまり、すべてのピアで符号化を行わなくてもデー
ためには 2 ラウンド必要になる。一方、ノード W で a と b の
タ配送効率が改善されることがわかる。そこで、まず、情報源
XOR を取るという符号化を行った場合、1 ラウンドで両方の
でのみ符号化を行った場合のデータ転送効率の改善について考
情報の配送が終わる。このように、ネットワークコーディング
えてみる。
を利用すると、ネットワークの帯域を最大限に活用することが
できることが知られている。
S
a
T
a
b
X
A
C
B
D
5
図 4 重複ブロック受信
b
a⊕b
a⊕b
4
U
b
W 符号化
a
3
2
b
S
a
1
図 4 のようなデータ配送の P2P ネットワークがあり、ブロッ
a⊕b
ク 1∼5 のデータを情報源ピア S からピア A∼D に配送するも
のとする。各リンクは、1 ラウンドあたり 2 ブロックのデータ
Y
a
復号
b
Z
復号
a
を転送することができる。符号化を行わないとすると、各ラウ
b
ンドで各ピアに配送されるブロックは、例えば、表 1 のように
なる。ラウンド 2 では、ピア B はブロック 1 と 2 をもってい
図 3 ネットワークコーディングの例
表1
ネットワークコーディングを BitTorrent に適用する場合、図
符号化しない場合のブロック配送
ラウンド
3 の情報 a と b がブロックに対応することになる。BitTorrent
配送済みブロック
ピア A
に適用する符号化方式としては、XOR ではなく、ランダムリ
1
1, 2
ニア符号が使われる [3], [4]。
2
1, 2, 3, 5
Bi , i = 1, 2, · · · , K をブロックとすると、ランダムリニア符
3
ピア B
ピア C
ピア D
3, 4
1, 2
3, 4, 1, 2
3, 4
1, 2, 3, 5, 4 1, 2, 3, 5, 4 1, 2, 3, 4, 5 1, 2, 3, 4
号は
C = α 1 Bi + α 2 B2 + · · · + α K B K
るので、そのブロックが次のラウンドでピア D に送られる。ま
と表すことができる。ここで、α は符号化の係数であり、符号
た、ピア C にもブロック 1 と 2 があり、ピア D にはそれらの
化したデータとともにこの係数のベクトル [α1 , α2 , · · · , αK ](符
ブロックがラウンド 2 の時点では無いので、ブロック 1 と 2 が
号化ベクトル) も送信することにより、受信側で復号すること
ピア D に送られている。つまり、ここでは、冗長にブロック 1
が可能になる。
と 2 がピア B と C からピア D に送信されているため、帯域が
本稿は、これまで我々の研究グループが行なってきたネット
無駄に使われていることになる。
一方、ピア S がもともと保持しているブロック 1∼5 から、
ワークコーディングに係わる研究成果をまとめたものである。
2. では、BitTorrent にネットワークコーディングを適用した場
ランダムリニア符号により 3 つのブロック、ブロック 6 から 8
- 34 -
—2—
が生成されていたとする。ここで、元の 5 つのブロックを得る
容する帯域の総和である。式 (2) は、ピア S が必ずしも情報源
ためには、ブロック 1 から 8 のうち、いずれか 5 ブロックを集
でなく、上流からブロックを受信し、下流へ送信するピアでも
めれば復号することができる。この場合、各ラウンドで各ピア
同様に成り立つ。
に配送されるブロックは、例えば、表 2 のようになり、3 ラウ
3. 符号化器の配置
ンドですべてのピアが 5 ブロックを受け取ることができ、元の
5 ブロックを復号することができるようになる。この例からわ
ブロック受信完了までの時間を短縮できることがわかった。
表 2 符号化する場合のブロック配送
ラウンド
符号化を行わない場合、ピア S からピア i への経路の数が増
配送済みブロック
ピア A
1
1, 2
2
1, 2, 5, 6
3
式 (2) より、D(S, i) をできるだけ小さくすることによって、
ピア B
ピア C
1, 2
3, 4, 7, 8
ピア D
える程、重複したブロックを受信する確率は高まり、その結果、
3, 4
ロックを減少し、D(S, i) を減少させるには、ピア S において
D(S, j) は増大し、遅延も増大する。図 5 の場合、重複するブ
3, 4
ブロックを符号化してブロック数を増加させ、ピア S からピア
1, 2, 5, 6, 4 1, 2, 5, 6, 3 3, 4, 7, 8, 5 3, 4, 7, 8, 1
1 に送るブロックと、ピア S からピア 2 に送るピアに重複が無
かるように、符号化によって、同一の情報を冗長に転送するこ
いようにすればよい。以上から、多くの経路が通過するピアに
とを避けることができ、このことによって、ネットワークを効
おいて符号化を実施し、異なる経路に重複しないブロックを送
率よく活用できることになるのである。
出すれば、データ配送時間を短縮できることがわかる。
情報転送を高速化するために、符号化器を配置するピアを決
uS1
S
定するためには、多くのピアを結ぶ経路上にあるピアを見つけ
uS2
れば良い。あるピアが、他のピア間を結ぶ経路上にある度合い
を示す指標として、媒介中心性 (Betweenness Centrality) [6]
up2
1
と フロー中心性 (Flow Centrality) [7] が提案されている。媒
2
介中心性は、あるピアが、他のピア間を結ぶ何本の経路上にあ
up1
るかを示す。またフロー中心性は、あるピアを経由する、他の
ピア間を結ぶ経路の帯域の総和を表す。
図 5 ソースコーディング
媒介中心性の大きいピアを、符号化を行うピアとして選択す
図 5 のような、２つのピア 1 と 2 それぞれが、直接情報源ピ
ア S と帯域 uS1 、uS2 のリンクで接続され、またピア 1 とピア
2 は他のピアを経由して相互に帯域 up1 と up2 の経路で接続さ
れているネットワークを仮定する。ここで情報源ピア S にある
K 個のブロックをすべてピア 1 と 2 に転送するとする。この場
合、K 個のブロックをピア S からピア 1 に転送するのに要す
る時間は、2 つの経路で転送するブロックに重複が無いものと
仮定すれば、
れば、符号化を行うピアを多くの経路が通過することになり、
重複したブロックを受信する確率を減少できることが期待でき
る。またフロー中心性の大きなピアを、符号化を行うピアとし
て選択すると、多くの経路が通過するばかりでなく、多くのブ
ロックがそのピアを通過することになり、さらに多くの重複の
削減が期待できる。
このような経験則による、アルゴリズが考えられる一方で、
式 (2) から、各ピアに起因する受信完了の遅延を直接求め、大
きな遅延の原因となるピアで符号化を実施することにより、遅
K
uS1 + up1
延を抑えることも可能である。式 (2) から、ピア i に起因して
になる。しかし、ピア S で符号化を行わない場合、両経路で転
ピア j で発生する遅延 d(i, j) は
送されるブロックに重複が発生する可能性が有り、その遅延を
d(i, j) =
考慮した転送時間は
K
uS1 + up1 − D(S, 1)
i を符号化を行うピアとして選択するのである。なお、ここで
送る場合に、ブロックが重複する単位時間当たりの割合である。
図 5 のピア S とピア 1 の間に他のピアがあり（このときピア
1 をピア i と記述することにする）、またピア S とピア i を結
ぶ経路が 3 本以上有る場合、重複するブロックによる遅延を考
慮した転送時間は、式 (1) と類似した以下の式によって求める
K
F (S, i) − D(S, i)
(3)
となり、各ピア i において d(i, j) を求め、d(i, j) の大きなピア
(1)
となる [5]。ここで、D(S, 1) はピア S からピア 1 にブロックを
ことができる。
K
K
−
F (j) − D(i, j)
F (j)
F (j) = F (S, j)、すなわち情報源ピア S からピア j までのすべ
ての経路が許容する帯域の総和である。
これら三つのアルゴリズム、媒介中心性とフロー中心性を
使って符号化を行うピアを選択するアルゴリズム、および大き
な遅延を発生させるピアを符号化ピアとして選択するアルゴリ
ズムの性能を比較すると、遅延に基づくアルゴリズムがこれら
アルゴリズムの中で、すべてのピアで符号化を行う場合に最も
近い性能を示した [5], [8]。すべてのピアで符号化をすれば、当
(2)
然、最も短い時間ですべてのブロックの転送を完了することが
ここで F (S, i) は、ピア S からピア i までのすべての経路が許
できる。5,000 ピア程度のスモールワールドネットワークで評
- 35 -
—3—
価した場合、遅延に基づくアルゴリズムを使って、符号化を行
1 ラウンド目では、二つのブロック B1 と B2 が P 1 に転送
うピアを 250 だけ選んだ場合でも、ブロックの転送完了に掛か
され、以下の各ブロックが、2 ラウンド目に P 1 から P 2 と P 3
る時間の増加は、すべてのピアで符号化を行う場合と比べても
へ転送する候補となる。
10%未満で済んでおり、その有効性が示されているとともに、
すべてのピアで符号化することが処理の無駄であることも示す
ラウンド 1:
P 1 に転送済みのブロック: B1 , B2
ことができた。
P 1 から P 2 に転送する候補ブロック:
媒介中心性を使ったアルゴリズムとフロー中心性を使ったア
A1 = α11 B1 + α12 B2 , A3 = α31 B1 + α32 B2
ルゴリズムを比較した場合、フロー中心性を使う方が効果が高
P 1 から P 3 に転送する候補ブロック:
く、条件によっては媒介中心性のアルゴリズムに比べて 10%程
A2 = α21 B1 + α22 B2 , A4 = α41 B1 + α42 B2
度、遅延を短縮することができる。また、フロー中心性のアル
ゴリズムと遅延に基づくアルゴリズムを比較した場合も、条件
2 ラウンド目以降は、もし選択される転送ブロックが候補ブ
によっては、その間に 10%程度のブロック転送時間の差が見ら
ロックからランダムに選択されると以下の様になる可能性が
れた。
ある。
以上から、ブロック転送時間による性能についてまとめる
と、遅延に基づくアルゴリズムの性能が最も良く、フロー中心
ラウンド 2:
P 1 に転送済みのブロック: B1 , B2 , B3 , B4
性を使ったアルゴリズム、 媒介中心性を使ったアルゴリズムの
P 1 から P 2 に転送する候補ブロック:
順に性能が落ちてく。一方で、計算複雑度は、遅延に基づくア
A3 = α31 B1 + α32 B2
ルゴリズムが O(V E 3 ), フロー中心性を使ったアルゴリズムが
A5 = α51 B1 + α52 B2 + α53 B3 + α54 B4
O(V 2 E 2 ), 媒介中心性を使ったアルゴリズムが O(E) となり、
A7 = α71 B1 + α72 B2 + α73 B3 + α74 B4
媒介中心性を使ったものがたいへん軽量なアルゴリズムとなっ
P 1 から P 3 に転送する候補ブロック:
ている。
A4 = α41 B1 + α42 B2
これら三つのアルゴリズムの詳細および性能比較の詳細は [5]
A6 = α61 B1 + α62 B2 + α63 B3 + α64 B4
および [8] を参照されたい。
A7 = α81 B1 + α82 B2 + α83 B3 + α84 B4
P 2 に転送済みのブロック: A1
4. ブロック選択問題
P 2 から P 4 に転送する候補ブロック: A1
BitTorrent では、隣接ピアからダウンロードするブロック
P 3 に転送済みのブロック: A2
を選択する基準として、“Rarest-First” という基準が適用され
る。この基準では、隣接ピアが保持するブロックの中で最も希
少なブロックを、ダウンロードするブロックとして選択する。
P 3 から P 4 に転送する候補ブロック: A2
ラウンド 3:
P 1 に転送済みのブロック: B1 , B2 , B3 , B4 , B5 , B6
もし、同程度に希少なブロックが存在する場合、その中からラ
P 2 に転送済みのブロック: A1 , A3
ンダムに選択される。しかし、ピアで符号化を行う場合、この
P 2 から P 4 に転送する候補ブロック: A3
基準だけでは不十分である [9]。
P 3 に転送済みのブロック: A2 , A4
P 3 から P 4 に転送する候補ブロック: A4
2
P 4 に転送済みのブロック: A1 , A2
P1
1
P2
このようになると、次のラウンド 4 で P 4 に転送される A3
1
1
1
と A4 は、既に P 4 に転送済みの A1 , A2 と依存関係にあるた
め、P 4 では新たな情報は何も得られないことになってしまう。
P3
この問題は、ピアで符号化を行うために発生する問題であり、
符号化を行わない BitTorrent では発生しない。この発生を防
P4
ぐためには、Rarest-First という基準だけでは不十分で、同程
図 6 ブロック選択問題の例
度に希少なブロックの中での選択基準として、
（ 1 ） 最も近くのピアによって符号化されたブロックを選ぶ
例えば図 6 のような部分ネットワークがあるとする。ピア
（ 2 ） 同程度の近さのピアで符号化されたブロックがある場
P 1 は 1 ラウンド当たり 2 ブロックを受信し、ピア P 2 と P 3
合には、その中で最も新しく符号化されたブロックを選ぶ
に 1 ブロックを送信することができる。ピア P 2 と P 3 は 1 ラ
という基準を採用する必要がある。
ウンド当たり、1 ブロックを受信し、1 ブロックを送信できる。
最も近くのピアによって符号化されたブロックは、符号化を
また、ここではピア P 1 のみ符号化器を備えており、その他の
行ったピアから選択を行うピアまでの経路数が小さいことが期
ピアは受信したブロックを符号化せずにそのまま他のピアの要
待され、重複を防げる可能性が高い。また最も新しく符号化さ
求に応じて転送するものとする。
れたブロックには、それ以前に符号化されたブロックには含ま
- 36 -
—4—
れていない新しいブロックの情報が含まれている可能性が高く、
F(S, x)
重複を防げる可能性が高くなる。
x
uxj
5. 符号化率の最適化
図 5 において、重複するブロックを 0 にするには、ピア S か
j
らピア 1 に送るブロックとピア 2 に送るブロックに重複が無い
upxj
1
m
ようにすれば良いことがわかった。それでは、ブロックの重複
図 8 中間ピア x による符号化
を避ける最低限の符号化を行うとすると、符号化によりどの程
度の冗長度をもたせれば良いのだろうか。
図 8 のような構成を仮定する。符号化を行う中間ピア x か
図 5 において、ピア S からピア 1 に送るブロックとピア 2 に
送るブロックに重複が無く、かつ合計 K 個のブロックがピア 1
ら、その隣接ピア j までには、二つの経路が存在する。一つは
に到着する時刻に、ピア S からの直接経路とピア 2 を経由する
ピア x が直接ピア j に接続する経路であり、その帯域は uxj で
経路の二つの経路で同時に転送を完了する場合が最短時間での
ある。もう一つの経路は、ピア x から、ピア j 以外の隣接ピア
転送完了となる。この条件を満たす最小の符号化後のブロック
を経由してからピア j に到達する経路であり、その帯域は upxj
数は、
K
uS2
uS1
+
uS1 + up1
uS2 + up2
である。
ピア j は、この二つの経路を使って、Kj 個のブロックを
受信する。残りの K − Kj 個のブロックは、ピア x を経由し
となる。この符号化後ブロック数より以上のブロックを符号化
ない経路を通ってピア j は受信することになる。ピア x を経
により生成しても、転送時間をさらに短縮することはできない。
由する上記二つの経路を使って、ピア j が Kj 個のブロック
uSj
j
を受信するのに要する時間を Tj と表すことにする。ここで、
S
T1 <
= T2 <
= ··· <
= Tm と仮定しても一般性を失わないので、そ
の仮定をとることとする。
1
upj
ピア j は二つの経路を同時に使用し、ちょうど Tj の時間で
m
二つの経路で同時に、合計 Kj 個のブロックを受信完了する場
合が最短となり、その時間が Tj である。Tj で受信を停止する
図 7 複数ピアが直接情報源に接続する場合
ことによって、無駄な処理や帯域の使用を回避し、最適なネッ
図 7 のように、情報源ピア S が m 個のピアに直接接続して
いる場合、符号化前には情報源ピア S に K 個のブロックがあっ
たとすると、ブロックの重複を起こさない最小の符号化後のブ
ロック数は、
m
j=1
uSj K
uSj + upj
下流の Tj で受信を停止することになるので、最適なネット
ワーク利用をするためには、ピア x での符号化率も変動させな
ければならないことになる。ピア 1 から m が、ピア x から受
信するブロックの量は、時間とともに、すなわち、ピア j が受
(4)
信を完了するかどうかによって、以下のように変化する:
となる [10]。F (j) は、情報源ピア S からピア j までのすべて
の経路が許容する帯域の総和であるから、
F (j) = uSj + upj
であり、式 (4) は以下のように書き換えることができる。
m
uSj K
F (j)
j=1
トワークの利用ができることになる。
⎧
⎪
⎪
ux1 t + ux2 t + · · · + uxm t,
⎪
⎪
⎪
⎪
⎪
⎨ux1 T1 + ux2 t + · · · + uxm t,
enc(x, t) =
..
⎪
⎪
⎪
.
⎪
⎪
⎪
⎪
⎩u T + u T + · · · + u T ,
x1 1
x2 2
xm m
if 0 < t < T1 ;
if T1 <
= t < T2 ;
if t > Tm .
(6)
一方、ピア x が受信するブロック量は以下のようになる:
(5)
recv(x, t) =
一方、情報源ではない中間のピアが符号化を行う場合、情報
源で符号化を行うのと条件が異なるのは、中間ピアでは、必ず
if 0 < t < Tx ;
⎩K,
if t >
= Tx .
(7)
式 (6) と (7) から、ピア x の符号化率 ex は以下の様に求め
しも情報源にあるすべてのブロックを符号化する必要がない点
である。つまり、符号化を行うブロックの総量を確定できない。
⎧
⎨F (x)t,
ることができる:
そこで、中間ピアについては、符号化後のブロック数ではなく、
符号化前後のブロック数の比率（符号化率）の最適値を求める
こととする。中間ピア i での符号化率が ei であるということ
は、単位時間当たりの入力ブロック数が B であるとすると、単
位時間当たりの出力ブロック数は Bei となる。
- 37 -
—5—
⎧
⎪
(ux1 t + ux2 t + · · · + uxm t)/(F (x)t),
⎪
⎪
⎪
⎪
⎪
if 0 < t < T1 ;
⎪
⎪
⎪
⎪
⎪
⎪
(ux1 T1 + ux2 t + · · · + uxm t)/(F (x)t),
⎪
⎪
⎪
⎪
⎪
if T1 < t < T2 ;
⎪
⎪
⎪
⎪
..
⎪
⎪
⎪
.
⎪
⎨
ex (t) =
(ux1 T1 + ux2 T2 + · · · + uxj−1 Tj−1
⎪
⎪
⎪
⎪ +uxj t + · · · + uxm t)/(F (x)t),
⎪
⎪
⎪
⎪
⎪
if Ti < t < Tj ;
⎪
⎪
⎪
⎪
⎪
.
⎪
..
⎪
⎪
⎪
⎪
⎪
⎪
⎪
(ux1 T1 + ux2 T2 + · · · + uxm Tm )/K,
⎪
⎪
⎪
⎩
if t >
= Tm ;
(8)
ピア x において、その符号化率 ex を式 (8) のように変化させ
れば、重複するブロックによる転送時間の遅延を発生させず、
かつ無駄な符号化を行わない最低限の符号化を行うことがで
きる。
6. む す び
本稿では、具体的にはピア・ツー・ピアファイル共有システ
ムである BitTorremt にネットワークコーディングを適用した
[3] C. Gkantsidis and P.R. Rodriguez, “Network coding for
large scale content distribution,” INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings IEEE, vol.4, pp.2235–
2245vol.4, March 2005.
[4] T. Ho, M. Medard, J. Shi, M. Effros, and D.R. Karger, “On
randomized network coding,” In Proceedings of 41st Annual Allerton Conference on Communication, Control, and
Computing, pp.11–20, 2003.
[5] D. Nguyen and H. Nakazto, “Network coder placement for
peer-to-peer content distribution,” IEICE Transactions on
Communicaitons, vol.E96-B, no.7, pp.1661–1669, July 2013.
[6] L.C. Freeman, “A set of measures of centrality based on
betweenness,” Sociometry, vol.40, no.1, pp.35–41, 1977.
[7] L.C. Freeman, S.P. Borgatti, and D.R. White, “Centrality
in valued graphs: a measure of betweenness based on network flow,” Social Networks, vol.13, pp.141–154, 1991.
[8] D. Nguyen and H. Nakazato, “Centrality-based network
coder placement for peer-to-peer content distribution,” International Journal of Computer Networks and Communications, vol.5, no.3, pp.157–174, May 2013.
[9] D. Nguyen and H. Nakazato, “Rarest-first and coding are
not enough,” Proc. of Globecom 2012, pp.2707–2712, Dec.
2012.
[10] D. Nguyen and H. Nakazato, “Minimal network coding redundancy for peer-to-peer content distribution,” to appear
in Proc. of ICC 2014, June 2014.
場合について、符号化を行うピアの選択、隣接ピアと交換する
ブロックの選択、符号化を行う量の選択における最適化につい
て検討を加えた。しかし、この成果は必ずしも BitTorrent に閉
じて当てはまるものではなく、ルータで符号化を行う場合や、
BitTorent を使わない一般的なピア・ツー・ピアファイル共有
システムなど、中間ノードで符号化を行うシステム一般に適用
ないしは拡張可能である。特に 2. で述べた、冗長性がネット
ワークコーディングにおける高速化の理由であるという点は、
ネットワークコーディングの応用を考える上で重要である。今
後、他のシステムへ適用した場合の課題についても検討を加え
ていく。
また、BitTorrent への適用においても、課題が残っている。
現状、符号化を行うピアの決定や、符号化率を決定するために、
システムの情報を一か所に集める必要がある。ピア・ツー・ピ
アシステムは本来は完全に分散のシステムであるので、集中制
御はあるべき姿ではない。アルゴリズムを分散化する必要があ
る。またピアは通常ダイナミックにシステムへの参加、システ
ムからの離脱を行う。現状のアルゴリズムは、ピアの参加離脱
が無い静的な状態で、すべての情報を収集した上で、解析を行
うという仮定をしているので、ダイナミックな参加離脱に対応
する仕組みについても検討が必要である。
謝辞
本研究の一部は、JSPS 科研費 24500098 の助成を受
けて行われた。
文
献
[1] B. Cohen, “Incentives build robustness in bittorrent,” Proceedings of the First Workshop on the Economics of Peer-to-Peer Systems, pp.68–72, 2003. citeseer.nj.nec.com/cohen03incentives.html
[2] R. Ahlswede, N. Cai, S.-Y. Li, and R.W. Yeung, “Network
information flow,” Information Theory, IEEE Transactions
on, vol.46, no.4, pp.1204–1216, jul 2000.
- 38 -
—6—