誤り訂正符号を用いたトランスポート層プロトコルの実装と評価株式会社インターネットイニシアティブサービスオペレーション本部カスタマーサポート島津圭佑背景通信経路ではノイズや輻輳でデータに欠損が発生 • • 1対1通信では再送を行うことで対処放送のような1対多や多対多通信が増加 • • 大量の再送要求が発生してしまうため再送困難再送が困難な環境で高品質なデータに対する要求の増加 • • 2 誤り訂正符号を用いた通信の発展 Forward Error Correction (FEC:前方誤り訂正) 元データに特定の計算をし, 冗長データを付加し誤りや損失を訂正可能にした符号 • • • 符号化とは訂正可能な符号にすること復号とは元のデータに戻すこと • アルゴリズムやパラメータによって, 復号の計算時間やどの程度訂正可能かが変化 • 例: リードソロモン(RS)符号 • 3 冗長データの半分の量まで訂正可能通信におけるFECの適応法複数パケットを集めて訂正 • • • 多少パケットが喪失した場合も訂正可能復号の開始までに待ち時間が存在パケットごとに訂正 • • • • 4 ヘッダの訂正も可能即座に復号可能パケットが喪失した場合訂正不可能既存研究 RFC 6363 (2011年 10月公布) Forward Error Correction (FEC) Framework • • 全てに共通するFECを用いた通信の骨組みを提供アプリケーションとFECを分割 • • • 任意のFECの使用が可能 • 信頼性のないトランスポート層のプロトコルの上で運用 • 受信端末が使う復号器の指定法は未定義 • 5 RFC6364で送受信端末間で復号器指定の事前やり取りについて記載既存研究(送信) アプリケーション (1)分割された元データ (3)ソースブロック FEC フレームワーク (2)ソースブロックの構築 (6)FECのソースブロックと訂正ブロックの構築 (7)FECのソースブロックと訂正ブロックトランスポート層(UDPやDCCP) 6 FEC スキーマ (4)符号化 (5)FECソースペイロードID 訂正ペイロードID 訂正シンボル既存研究(受信) アプリケーション (6)分割された元データ (5)複数のソースデータ FEC フレームワーク (2)FECソースブロックと FEC訂正ブロック (1)FECのソースブロックと訂正ブロックトランスポート層(UDPやDCCP) 7 FEC スキーマ (4)復号 (3)FECソースペイロードID 訂正ペイロードID 訂正シンボル問題点既存のトランスポート層の上に定義している • • UDPなどのトランスポート層のプロトコルには, 誤りを検出し破棄する機能があるパケット1 パケット2 パケット3 パケット4 パケット5 パケット6 1符号単位 8 問題点既存のトランスポート層の上に定義している • • UDPなどのトランスポート層のプロトコルには, 誤りを検出し破棄する機能があるパケット1 パケット2 パケット3 パケット4 パケット5 パケット6 1符号単位 9 提案手法 • • パケットに誤りがあっても破棄をしないFECの使用を前提としたプロトコルをトランスポート層で定義するフレームワークで使用する共通ヘッダとデータ部の符号化で使用するFECのヘッダを作成する • • データ部は, 任意のFECを使用可能である共通ヘッダ, FECヘッダをそれぞれ誤り訂正するパケット1 パケット2 パケット3 パケット4 パケット5 パケット6 10 1符号単位消失提案手法(誤り訂正法) オレンジ:共通ヘッダ, 黄色:FEC毎のヘッダ青:元データ, 黄緑:冗長データ, 赤:ビット誤り • • パケット1 パケット2 パケット3 パケット4 パケット5 パケット6 11 消失提案手法(送信) アプリケーション (1)元データと各種要件 (3)元データと訂正率 FEC スキーマ (4)符号化 (5)FECヘッダの作成 FEC フレームワーク (2)FECを選択 (7)共通ヘッダの作成 (6)符号化データ (8)作成したデータネットワーク層(IPなど) 12 提案手法(受信) アプリケーション (8)複数の元データ (7)複数の元データ FEC スキーマ (5) FECへッダの訂正 (6)復号 FEC フレームワーク (2) 共通ヘッダの訂正 (3) ポートの指定 (4) シークエンス番号データ (1)送られてきたデータネットワーク層(IPなど) 13 実験で使用される用語の定義 • • 選択率とは誤りを入れるパケットを選択する率である挿入率とは選択されたパケットに誤りを挿入する率である • • • パケット内で起こるバースト的な誤りを再現できる誤り率とは, 復号後に残ったデータの誤りの率である受信時間とは, データの送信から復号終了までの時間である 14 実験手順 • 送信端末はデータを符号化し, 既存手法，提案手法それぞれ送信する • 中継機は, 選択率, 挿入率を任意に設定し, 誤りを挿入し受信端末に送信する • 受信端末はデータを復号し, その結果を計測する送信端末 15 中継機受信端末実験1 • 1.1MBの画像データを(100,80)RS符号で符号化し, 既存手法と提案手法のプロトコルでそれぞれ送信する • • • • • • 10%の誤りまで訂正出来る 1パケットあたり既存手法では1040オクテット, 提案手法では1052オクテットである 1400パケットが作成された挿入率を0.1%に固定する選択率0%から80%まで変更する結果は10回の平均値である 16 挿入率0.1% 誤り率 90 80 70 誤り率(%) 60 50 既存手法 40 提案手法 30 20 10 0 0 17 20 40 選択率(%) 60 80 挿入率0.1% 受信時間 3.5 2.738sec 3.0 時間(sec) 2.5 2.0 既存手法 1.5 提案手法 1.295sec 1.0 0.5 0.0 0 18 10 20 30 40 選択率(%) 50 60 70 80 実験2 • 1.1MBの画像データを(100,80)RS符号で符号化し, 既存手法と提案手法のプロトコルでそれぞれ送信する • • • • • • 10%の誤りまで訂正出来る 1パケットあたり既存手法では1040オクテット, 提案手法では1052オクテットである 1400パケットが作成された選択率を10%に固定する挿入率0.1%から20%までに変更する結果は30回の平均値である 19 選択率10% 誤り率 6 5 誤り率(%) 4 既存手法 3 提案手法 2 1 0 0 20 5 10 挿入率(%) 15 20 選択率10% 受信時間 3.5 3.0 時間(sec) 2.5 2.0 既存手法 1.5 提案手法 1.0 0.5 0.0 0 21 5 10 挿入率(%) 15 20 考察 • 挿入率が低い場合, 提案手法は誤り率の面で既存手法より優れている • 挿入率が高くなるに従って, 提案手法の誤り率は既存手法との差が小さくなる • 選択率が増加した場合, 下位ヘッダに誤りが挿入され, トランスポート層までデータが渡されない • 受信にかかる時間は, 同程度である • 応答なしで通信するため, 1対多の通信に利用可能である 22 今後の課題 • 中継機でフレームチェックシークエンスの再計算を行っているため，再計算なしでの検証をする • 提案手法のプロトコルの使用するためには, 双方の端末に新たに実装する必要がある • 復号状況に応じて, FECの種類や符号化率の変更を可能にする機構の実装をする 23 まとめ • 誤り訂正符号の使用を前提としたトランスポート層のプロトコルを提案し評価した • 挿入率が低い場合, 誤り率は選択率が高いほど提案手法が既存手法に比べて優れている • 挿入率が高くなると, 提案手法は既存手法に誤り率が漸近する 24