誤り訂正符号を用いた トランスポート層プロトコルの実装と評価

Presentation on theme: "誤り訂正符号を用いた トランスポート層プロトコルの実装と評価"— Presentation transcript:

1 誤り訂正符号を用いた トランスポート層プロトコルの実装と評価
株式会社インターネットイニシアティブ サービスオペレーション本部 カスタマーサポート 島津 圭佑 東京理科大学　島津圭佑　でも大丈夫(表記も含め) pptのデザインについて 横線が入っていて, 見にくいので　他のものを使いましょう ヘッダの訂正機能について　->　必要な量とかは評価するの?

2 背景 通信経路ではノイズや輻輳でデータに欠損が発生 放送のような1対多や多対多通信が増加
1対1通信では再送を行うことで対処 放送のような1対多や多対多通信が増加 大量の再送要求が発生してしまうため再送困難 再送が困難な環境で高品質なデータに対する 要求の増加 誤り訂正符号を用いた通信の発展

3 Forward Error Correction (FEC:前方誤り訂正)
元データに特定の計算をし, 冗長データを付加し 誤りや損失を訂正可能にした符号 符号化とは訂正可能な符号にすること 復号とは元のデータに戻すこと アルゴリズムやパラメータによって, 復号の計算時間 やどの程度訂正可能かが変化 例: リードソロモン(RS)符号 冗長データの半分の量まで訂正可能 前方誤り訂正についてもう少し詳しく話す 練習で10分6秒

4 通信におけるFECの適応法 複数パケットを集めて訂正 パケットごとに訂正 多少パケットが喪失した場合も訂正可能
復号の開始までに待ち時間が存在 パケットごとに訂正 ヘッダの訂正も可能 即座に復号可能 パケットが喪失した場合訂正不可能

5 既存研究 RFC 6363 (2011年 10月 公布) Forward Error Correction (FEC) Framework
信頼性のないトランスポート層のプロトコルの上で 運用 受信端末が使う復号器の指定法は未定義 RFC6364で送受信端末間で復号器指定の 事前やり取りについて記載 実装見てみよう

6 既存研究(送信) アプリケーション (1)分割された元データ (3)ソースブロック FEC フレームワーク FEC スキーマ
(2)ソースブロックの構築 (6)FECのソースブロックと 　訂正ブロックの構築 FEC　スキーマ (4)符号化 (5)FECソース 　ペイロードID 　訂正ペイロードID 　訂正シンボル (7)FECのソースブロックと訂正ブロック トランスポート層(UDPやDCCP)

7 既存研究(受信) アプリケーション (6)分割された元データ (5)複数のソースデータ FEC フレームワーク FEC スキーマ
(4)復号 (3)FECソース 　ペイロードID 　訂正ペイロードID 　訂正シンボル (1)FECのソースブロックと訂正ブロック トランスポート層(UDPやDCCP)

8 問題点 既存のトランスポート層の上に定義している UDPなどのトランスポート層のプロトコルには, 誤りを検出し破棄する機能がある パケット1
パケット2 パケット3 パケット4 パケット5 パケット6 1符号単位

9 問題点 既存のトランスポート層の上に定義している UDPなどのトランスポート層のプロトコルには, 誤りを検出し破棄する機能がある パケット1
パケット2 パケット3 パケット4 パケット5 パケット6 1符号単位

10 提案手法 パケットに誤りがあっても破棄をしないFECの使用を 前提としたプロトコルをトランスポート層で定義する
パケット1 パケット2 パケット3 パケット4 パケット5 パケット6 消失 1符号単位

11 提案手法(誤り訂正法) オレンジ:共通ヘッダ, 黄色:FEC毎のヘッダ 青:元データ, 黄緑:冗長データ, 赤:ビット誤り パケット1
パケット2 パケット3 パケット4 パケット5 パケット6 消失

12 提案手法(送信) アプリケーション (1)元データと 各種要件 (3)元データと 訂正率 FEC スキーマ FEC フレームワーク
　(7)共通ヘッダの作成 FEC　スキーマ 　(4)符号化 　(5)FECヘッダの作成 (6)符号化データ (8)作成したデータ ネットワーク層(IPなど)

13 提案手法(受信) アプリケーション (8)複数の元データ (7)複数の元データ FEC フレームワーク FEC スキーマ
　(2) 共通ヘッダ の訂正 　(3) ポートの指定 FEC　スキーマ (5) FECへッダ の訂正 (6)復号 (4) シークエンス番号 　　データ (1)送られてきたデータ ネットワーク層(IPなど)

14 実験で使用される用語の定義 選択率とは誤りを入れるパケットを選択する率である 挿入率とは選択されたパケットに誤りを挿入する率である
パケット内で起こるバースト的な誤りを再現できる 誤り率とは, 復号後に残ったデータの誤りの率である 受信時間とは, データの送信から復号終了までの 時間である

15 実験手順 送信端末はデータを符号化し, 既存手法，提案手法 それぞれ送信する
送信端末はデータを符号化し, 既存手法，提案手法 それぞれ送信する 中継機は, 選択率, 挿入率を任意に設定し, 誤りを挿入し受信端末に送信する 受信端末はデータを復号し, その結果を計測する 送信 端末 中継機 受信 端末

16 実験1 1.1MBの画像データを(100,80)RS符号で符号化し, 既存手法と提案手法のプロトコルでそれぞれ送信する
10%の誤りまで訂正出来る 1パケットあたり既存手法では1040オクテット, 提案手法では1052オクテットである 1400パケットが作成された 挿入率を0.1%に固定する 選択率0%から80%まで変更する 結果は10回の平均値である

17

18 グラフが怪しすぎてヤバい 負ける要素しかないのに勝ってるよ(´―｀)

19 実験2 1.1MBの画像データを(100,80)RS符号で符号化し, 既存手法と提案手法のプロトコルでそれぞれ送信する
10%の誤りまで訂正出来る 1パケットあたり既存手法では1040オクテット, 提案手法では1052オクテットである 1400パケットが作成された 選択率を10%に固定する 挿入率0.1%から20%までに変更する 結果は30回の平均値である

20

21

22 考察 挿入率が低い場合, 提案手法は誤り率の面で 既存手法より優れている
挿入率が低い場合, 提案手法は誤り率の面で 既存手法より優れている 挿入率が高くなるに従って, 提案手法の誤り率は 既存手法との差が小さくなる 選択率が増加した場合, 下位ヘッダに誤りが挿入され, トランスポート層までデータが渡されない 受信にかかる時間は, 同程度である 応答なしで通信するため, 1対多の通信に 利用可能である

23 今後の課題 中継機でフレームチェックシークエンスの再計算を 行っているため，再計算なしでの検証をする
中継機でフレームチェックシークエンスの再計算を 行っているため，再計算なしでの検証をする 提案手法のプロトコルの使用するためには, 双方の端末 に新たに実装する必要がある 復号状況に応じて, FECの種類や符号化率の変更を 可能にする機構の実装をする FCSについて調べる L2を見るのが辛い・・・

24 まとめ 誤り訂正符号の使用を前提としたトランスポート層の プロトコルを提案し評価した
誤り訂正符号の使用を前提としたトランスポート層の プロトコルを提案し評価した 挿入率が低い場合, 誤り率は選択率が高いほど 提案手法が既存手法に比べて優れている 挿入率が高くなると, 提案手法は既存手法に 誤り率が漸近する

25 UDP(User Datagram Protocol)
トランスポート層に属するプロトコル 信頼性を持たない チェックサムはヘッダとペイロードに対し, 誤りが 存在しないかを計算 存在した場合パケットを破棄 IPv4では使用は任意　IPv6では必須 送り元ポート 宛先ポート チェックサム データ長

26 Forward Error Correction (FEC:前方誤り訂正)
元データに特定の計算をし, 冗長データを付加し 誤りや損失を訂正可能にした符号 符号化とは訂正可能な符号にすること 復号とは元のデータに戻すこと アルゴリズムやパラメータによって, 復号の計算時間 やどの程度訂正可能かが変化 前方誤り訂正についてもう少し詳しく話す

27 Reed-Solomon(RS)符号 FECの一種であり, DVDやQRコードの 誤り訂正手法として使用されている
GF(2m)上で符号化, 復号する m=8として1バイトを1シンボルとすることが多い 冗長データ数の半分まで訂正が可能である k=元データ, n = k+冗長データとするRS符号を (n,k)RS符号と略記する

28 Reed-Solomon(RS)符号 FECの一種であり, DVDやQRコードの 誤り訂正手法として使用されている
GF(2m)上で符号化, 復号する m=8として1バイトを1シンボルとすることが多い 冗長データ数の半分まで訂正が可能である

29 系統的符号 符号語が元データ部分と冗長データ部分に 分けられる符号 系統的でない符号は符号語から復号なしで 元データを知ることは出来ない
符号語が元データ部分と冗長データ部分に 分けられる符号 例: InfomationScience wxpd 系統的でない符号は符号語から復号なしで 元データを知ることは出来ない FECとしては以下のようなものがある ハミング符号 リードソロモン符号 非正則LDPC符号

30 既存研究 RFC 6364 Session Description Protocol(SDP)を用いてFECの パラメータ指定を行う
FECの種類や, そのFEC構成に必要になるデータ SDPは, 記述の仕方を定義し, 配送法は定義していない

31 問題点 既存のトランスポート層の上に定義している UDPなどのトランスポート層のプロトコルには, 誤りを検出し破棄する機能がある

32 設計指針 ユニ, マルチに囚われない プロトコルを理解していない場合でも, データをほぼ直 すことが可能
どのタイミングから受信してもある程度受信可能 通信に合うように誤り訂正符号のアルゴリズム及び内 部の値の変更可能 これが出来る利点を述べる必要あり? 新しい符号化法の追加を, 符号器と復号器の追加で可 能にする 途中で符号化率等の変更が可能である

33 提案手法 チェックサムを用いない新しいプロトコルを提案 FECの使用に特化したトランスポート層を定義
ヘッダを定義 処理の規定 RFCに即した形で説明する必要はありそう 送信する結局のデータもそうだが, アプリケーションから送信するまでの機構や受信からアプリケーションに返すまでの機構の説明も必要

34 提案手法(パケットの構成) データリンク層以下は省略する ヘッダの訂正をそれぞれ行う IPヘッダ FEC共通 ヘッダ FEC毎の ヘッダ
20オクテット FEC毎の ヘッダ データ部 ヘッダの訂正をそれぞれ行う

35 提案手法 チェックサムを用いないFECの使用に特化した 新しいトランスポート層のプロトコルを提案
ヘッダの訂正が可能 ヘッダや処理を規定 パケット1 パケット2 パケット3 パケット4 パケット5 パケット6 消失 RFCに即した形で説明する必要はありそう 送信する結局のデータもそうだが, アプリケーションから送信するまでの機構や受信からアプリケーションに返すまでの機構の説明も必要

36 提案手法 チェックサムを用いないFECの使用に特化した 新しいトランスポート層のプロトコルを提案
ヘッダの訂正が可能 ヘッダや処理を規定 パケット1 パケット2 パケット3 パケット4 パケット5 パケット6 消失 RFCに即した形で説明する必要はありそう 送信する結局のデータもそうだが, アプリケーションから送信するまでの機構や受信からアプリケーションに返すまでの機構の説明も必要 復号するブロック

37 提案手法 このヘッダに続き, FEC毎に固有のヘッダを付与 ヘッダ長はFEC毎のヘッダの長さ 新しいFECが作成された場合に拡張可能
冗長データはヘッダの訂正に用いる ポート データ長 シークエンス番号 冗長データ ブロックの開始シークエンス フラグ FEC No ヘッダ長 ヘッダに対して内符号で誤り訂正を行う (固定アルゴリズムでok) 先頭50バイトをみる　パリティは6バイト程度 ポートも計算するようにすると処理機構変わるな 　1, IPヘッダでこのプロトコルが選択されている 　2, 内符号を用いてヘッダの修正を行う 　3, ポートを用いて以降の処理を行う あーFWに弾かれそう・・・ 系統的符号にした方が懸命かな

38 提案手法 フレームワークのヘッダに続き, FEC毎に固有の ヘッダを付与 新しいFECが作成された場合に拡張可能
冗長データはヘッダの訂正に用いる ポート データ長 シークエンス番号 冗長データ ブロックの開始シークエンス フラグ FEC No ヘッダ長 ヘッダに対して内符号で誤り訂正を行う (固定アルゴリズムでok) 先頭50バイトをみる　パリティは6バイト程度 ポートも計算するようにすると処理機構変わるな 　1, IPヘッダでこのプロトコルが選択されている 　2, 内符号を用いてヘッダの修正を行う 　3, ポートを用いて以降の処理を行う あーFWに弾かれそう・・・ 系統的符号にした方が懸命かな 定義したフレームワークのヘッダ

39 提案手法 このヘッダに続き, FEC毎に固有のヘッダを付与 新しいFECが作成された場合に拡張可能 冗長データはヘッダの訂正に用いる
ポート データ長 シークエンス番号 冗長データ ブロックの開始シークエンス フラグ FEC No ヘッダ長 ヘッダに対して内符号で誤り訂正を行う (固定アルゴリズムでok) 先頭50バイトをみる　パリティは6バイト程度 ポートも計算するようにすると処理機構変わるな 　1, IPヘッダでこのプロトコルが選択されている 　2, 内符号を用いてヘッダの修正を行う 　3, ポートを用いて以降の処理を行う あーFWに弾かれそう・・・ 系統的符号にした方が懸命かな IPヘッダ FEC共通 ヘッダ 20オクテット FEC毎の ヘッダ データ部 66オクテット (冗長6オクテット含む) ヘッダの訂正を行う範囲

40 提案手法(ヘッダの誤り訂正) ヘッダとFEC毎のヘッダの訂正 データ部と異なり, 特定のFECを用いる
ヘッダが誤るとデータがどの位置のものか不明なため パケットを集めての訂正は不可 データ部と異なり, 特定のFECを用いる リードソロモン符号で元データ60オクテット, 冗長データ6オクテット FEC毎のヘッダが短い場合, データの一部も符号化される

41 提案手法(パケットの構成) データリンク層以下は省略する 66オクテット (冗長6オクテット含む) ヘッダの訂正を行う範囲 IPヘッダ
FEC共通 ヘッダ 20オクテット FEC毎の ヘッダ データ部 66オクテット (冗長6オクテット含む) ヘッダの訂正を行う範囲

42 提案手法(フラグ) フラグに1オクテット分用意しているが定めたものは 以下の3つ 終了ブロックフラグ 系統的符号フラグ 冗長データフラグ
フラグに1オクテット分用意しているが定めたものは 以下の3つ 終了ブロックフラグ 終了処理に使用 系統的符号フラグ 冗長データフラグ 系統的符号の場合, 未知のFECであっても 元データを抽出可能

43 提案手法(未知の系統的符号のFEC) フラグにより系統的符号であり, 冗長データである パケットは判明 誤り訂正能力は全くない パケット1
フラグにより系統的符号であり, 冗長データである パケットは判明 誤り訂正能力は全くない パケット1 パケット2 パケット3 パケット4 パケット5 パケット6 消失

44 提案手法(誤り訂正法) オレンジ:提案ヘッダ, 黄色:FEC毎のヘッダ オレンジ+黄色がパケット内の訂正を行う範囲
水色:元データ, 黄緑:冗長データ, 赤:ビット誤り パケット1 パケット2 パケット3 パケット4 パケット5 パケット6 消失

45 実装 共通ヘッダのヘッダ訂正用のFECとして, (20,14)RS符号を用いる FECスキーマとしてRS符号を用いる
RS符号のヘッダの訂正は(16,12)RS符号を用いる

46

47

48

49 受信時間について 誤り率と復号時間に相関はなさそう パケットが全て届いるときは早い 選択率によって復号時間が僅かに増加する傾向がある
timeoutの待ち時間がないため 選択率によって復号時間が僅かに増加する傾向がある

50 現在実装中 FECフレームワークの部分は, Linuxのカーネルにある, net/ipv6/udplite.cを変えて実装中
check_sumを使用しないプロトコルであり, ipv6では非推奨であるため, 変更にリスクがない check_sumは使用しないが, 検査はしている (一定の値でないとrejectされる)ため, 大幅に変更 FECスキーマについては, B4,M1時に作成したものを 流用する

51 今後行う実験 FEC Frameworkで通信した場合と新プロトコルで 通信した場合の誤り訂正率の変化について
パケット内ノイズ誤りについて チェックサムによる影響が出るため, 変化すると考えられる パケットロストについて 理論的にこちらは変化がないと考えられる FEC Frameworkで通信した場合と新プロトコルで 通信した場合での転送速度の差について 確実に計算量は増えている. ただしボトルネックがネットワーク にある場合は 速度に影響は少ないのではないか 　<–要検証

52 まとめ 誤り訂正符号の適用に適したプロトコルを提案 現在実装中 今後行う実験の紹介 IPv6ではUDPにチェックサムがあるため不適当である
ヘッダの訂正が可能である FEC毎のヘッダ内にパラメータを書くため, ネゴシエーションをする必要がない ヘッダのパラメータを変更することで, 通信中も柔軟に 符号の変更が可能である 現在実装中 トランスポート層のプロトコルとして実装している 符号化, 復号部分は, B4, M1で作ったものを流用する 今後行う実験の紹介 FECは何度も使う語なので, きちんと紐付けを行うこと ヘッダに対して誤り訂正符号を用いることも提案手法なので, きちんと言うこと ヘッダは固定FECだが, データの方は自由なFECを使えることを強く言うこと ネゴシエーションしなくても良いのも強み　-> RFCはどうなっている? FEC Frameworkの実装はどうするの?　->　最悪　提案手法のパケット内誤りが有るものは破棄すれば良い

53 今後の課題 ヘッダの冗長データの確認 終了処理 FECスキーマの微調整 細かい指定なしで誤り訂正能力を決める機能
計算速度や訂正能力が適切であるか 終了処理 待ちを打ち切るタイミング FECスキーマの微調整 細かい指定なしで誤り訂正能力を決める機能 1/15までに論文が仕上げられるようにかなり頑張る

54 ご清聴ありがとうございました 標準化される見込みは? 3.5層と4層どちらの実装が良いか考えよう!

55 開発日記 v6でのソケット作成がv4とかなり違うことに 驚く v6でソケット開くプログラムがどこにあるか 分からない
そうだUDPLITEを書き換えよう ヘッダ付けている関数が変な名前 udp_v6_push_pending_frames　という関数内

56 開発日記 sendmsgとrcvmsgを直す
内部の関数定義したりでudp.cにも手を加える udpliteの場合, check sumを見ていないと思いきや, 計算していないだけでcheck sumの値が 異なるとダメらしい・・・　65535に設定されている そのためヘッダがどうにもうまくいかない・・・ 昨晩のマーチで直った TCPのフラグメント部分とtimeout部分読む必要あり・・・

57 絶望 rs符号のSource codeを作ってくれる プログラム発見(小松崎くん使う可能性ある?)
receiveプログラム立てずにsendするとハングアップする 書き換えた時にコメントアウトした部分の影響か 見なかったことにします・・・　->ナオタ raw_sockで取ろうとしてもハングする・・・　->ハングはナオタ

58

59

60