Microsoft PowerPoint - chapter6_2012.ppt [互換モード]

Size: px

Start display at page:

Download "Microsoft PowerPoint - chapter6_2012.ppt [互換モード]"

こごろううみのなか
6 years ago
Views:

1 章誤り制御電子情報工学科年前期ネットワークアーキテクチャ情報科学センター / ネットワークデザイン研究センター福田豊 Agenda 学ぶ主な内容は以下のつ誤りを検出する方法誤り検出後, 訂正する方法誤り検出方法パリティ,CRC 誤り制御 ARQ,FEC ARQ 方式の紹介とその性能評価誤り訂正 Layer と Layer における誤り制御 1 情報. 1 はじめに (1) 伝送路における電気的な雑音等により内容が変化中継ノードでバッファあふれ ( 輻輳 :congestion) が発生し, 情報全体が消失受信側へ正しい情報が伝送されない場合に, 誤り制御が必要種類に大別 ARQ (Automatic Repeat request) FEC (Forward Error Correction) はじめに () ARQ 送信情報に冗長情報を付加し, その情報により受信側で誤りを検出受信側で誤りが検出されると, 送信側は再送により消失データを回復するほとんどのコンピュータネットワークで利用はじめに () FEC 送信情報に冗長情報を付加その情報により受信側では誤り検出とその誤り訂正を行うそのため冗長情報は多くなり, 複雑な符号器が必要用途 : 衛星通信,FA,CD, 携帯電話はじめに () 誤り制御が行われるLayer データリンク層トランスポート層アプリケーション層トランスポート層インターネット層データリンク層物理層 TCP/IP protocol stac 1

2 はじめに () データリンク層イーサネット (FCS による誤り検出 ) 最近の傾向光ファイバの導入により伝送誤りが軽減高速化の為に中継ノードのプロトコル処理を簡素化リンクごとの誤り制御を最小限にし, 主に End-to-End 間で品質保持はじめに () トランスポート層 TCP:Transmission Control Protocol 下位層に依存せず,End-to-End で誤り制御を行っている UDP:User Datagram Protocol UDP は End-to-End での誤り制御を行わない UDP ではアプリケーションが誤り制御を行う ( 必要な場合 ) 7. 誤り検出 (1) ビット誤り検出方法データの他に誤りを検出するために必要な情報を付加して伝送し, 受信側では付加された情報をもとに誤りがあるかを判断真の情報と付加情報を合わせて符号語誤り検出可能な符号を誤り検出符合誤りを正しく訂正して元の情報に訂正可能な符号を誤り訂正符号符号それぞれによって検出, 訂正可能な範囲が存在パリティチェック方式 (1) 文字コードの 1 の数に着目して文字の誤り検出を行う ASCII コードは各文字を 7 ビットで表現これに誤り検出用に 1 ビット ( チェックビット ) を付加し 8 ビットにするチェックビットは 8 ビットで構成されるコードの 1 の数の合計が常に偶数 ( または奇数 ) になるように決定偶数になるようにする偶数パリティ奇数になるようにする奇数パリティ 8 9 パリティチェック方式 () 例 A は ascii コードで偶数パリティ奇数パリティ受信側では,8 ビットごとに 1 の数をチェック奇数個のビット誤りが検出可能 CRC(Cyclic Redundancy Chec)(1) 伝送誤りのパターンエラーはランダムに発生するよりは, 連続的に発生するバースト誤りバースト誤りを想定した誤り検出方法巡回符号を用いた CRC HDLC, イーサネットのデータリンク層に使用 10 11

3 CRC() 原理例送信したい情報は 78 受信側との間であらかじめ決めた除数は 98 桁の冗長なデータを付加 / 98 の余りは (98-8) = 781 は必ず 98 で割り切れる送信する情報は 781 受信側で受取ったデータを 98 で割って余りがなければ下桁を除いたデータが真のデータ CRC() 多項式の表現 n ビットからなるビット系列 (a n-1, a, a 1, a 0 ) を下記のように表現 F n ( ) an 1 a a1 a0 例 (1, 1, 0, 0, 0, 1) F( ) 1 1 CRC() 演算は以下の代数的法則に従うものとする加減算 a modulo = 排他的論理和 (Exclusive OR) 乗除算代数的法則に従うが, 係数はmoduloの加法に従う b a b c c a i b i j a b c j c 1 例 1 例 CRC() ( )( ( ) ) ( ) ( ) 1 CRC() 巡回符号の作成ヘッダ m ビットペイロード CRC チェックビット 1. mビットのパケットを (m-1) 次の多項式 M() で表現. 任意に r (r < m) 次の多項式 G() を定め, 以下の手順に従ってCRCチェックビットを作る 1. r (G() の次数 ) 個の 0 を m ビットのパケットの後に付ける. すなわち多項式 r M(). 多項式 r M() を多項式 G() で割り, 余り R() を求めるこの R() が CRC チェックビット 1 CRC(7) したがって送られる符号語 F() は r F( ) M ( ) R( ) F() は常に G() で割り切れる G() を生成多項式と呼ぶ受信側では, 受信パケットを生成多項式 G() で割り, 割り切れれば誤りなく正しく受信できたものと判断割り切れなければ誤りが発生したと判断生成多項式 G() は送信側, 受信側双方で予め共有 17

4 CRC(8) 生成多項式 G() は送信側, 受信側双方で例. 予め共有送りたい情報パケット :(1, 0, 1, 0) 生成多項式 : G( ) 多項式 : M ( ) r M ( ) r M ( ) G( ) F( ) ( ) CRCチェックビットR() を求めると (1, 0,1, 0, 0,1,1) M ( ) R( ) r 余り( ) これが実際に送られる CRC(9) CRC の誤り検出能力は? 受信した情報 :Y() n n 伝送誤り : e( ) en 1 en e1 e 受信したデータのj 桁目に伝送誤りが発生 e j-1 = 1 そうでない場合は e j-1 = 0 データの i+1 桁目から上位 n ビットに渡って誤りが発生した場合, i Y ( ) F( ) e( ) (+ はEx-OR) CRC(10) 長さ r 以下のバースト誤りであれば,e() は G() で割り切れることはない生成多項式 G() の次数が r 次であれば, r ビット以下のバースト誤りを検出可能 r+1ビット以上のバースト誤りでも,e() が G() で割り切れない場合は, 誤り検出可能 CRC(11) 生成多項式 :G() 以下のつが国際標準として採用 G G G CRC CRC CRC CCITT ( ) ( ) ( ) シフトレジスタによる割り算回路巡回符号を使用する場合割り算機能があればよい進数の割り算回路は簡単なシフトレジスタで実現可能生成多項式が次式で表されるときの割り算を実行する回路排他的論理和 m G( ) g g g m 1 0 遅延素子例.(1) M(),G() が下記の場合の CRC チェックビットを求める M ( ), G( ) この場合の割り算を行うシフトレジスタ回路を下記に示す生成多項式の係数 g i のうち 0 である部分は, それに対応するフィードバック回路および Ex-OR 回路を取り除くことができる r 0 r 1 r g 0 係数機 g 1 g m-1 g 0 g 1 7 8

5 例.() 割算の過程送信データは 0 ~ bit までの 7 bit になるシフト回数送信データ r o r 1 r 割り算の余りは 010 例.() 割算の過程回目のシフトまでは, 送信データおよびレジスタの内容がそれぞれ1ビットずつ右にシフトする回目のシフト最終段から1が出力されそれがフィードバックの演算が行われ, その結果 111 がレジスタに残る 001 : 回目のシフトが行われた直後のレジスタの内容 110 : フィードバック回路による減算の項上記の動作を繰り返し, 最後にレジスタに残った 010 がこの割算の余りとなるしたがって符号語 F() は下記になる F( ) 9 0. ARQ パリティや CRC により伝送誤りを検出誤りの回復の為に送信側は再度同一のパケットを再送 (retransmission) 代表的な再送方式 Stop-and-wait ARQ Go-bac-N ARQ Selective-repeat ARQ Stop-and-wait ARQ(1) 最も単純な ARQ 受信側は 1 つのパケットを正しく受信するごとに送信側に送達確認情報 (ACK:Acnowledgement) を送る送信側は 1 つのパケットを送信後, 一定の時間内 ( タイムアウト時間 ) に ACK を受信しないときは, そのパケットを再送 1 Stop-and-wait ARQ() パケット送受信 1 1 Stop-and-wait ARQ() パケットを送信してから,ACKを受信するまでに要する時間往復伝播遅延時間パケットおよびACKの伝送時間の和ネットワーク内の伝送遅延時間 ACK

6 Stop-and-wait ARQ() タイムアウトタイムアウト時間だけ待っても ACK が受信されないタイムアウトが発生した送信パケットが喪失したり誤りが発生した場合だけでなく, 返送されるACKが喪失したり誤りが発生した場合によってもタイムアウトが発生タイムアウトが発生した場合同一のパケットを再送 Stop-and-wait ARQ() あるパケットの送信後, そのパケットの ACK を受け取るまで次のパケットの送信を行わない送受信側ともに, バッファが 1 つで済むパケット送信後それに対する ACK を受信するまでの間伝送路は空になり, 伝送効率は悪いアプリケーション例 TFTP (Trivial File Transfer Protocol) UDP を用い,ARQ として Stop-and-wait ARQ Stop-and-wait ARQ() 問題点パケット送信後そのACKを受け取るまで次のパケットの伝送を行わない伝送距離が長い衛星通信等では無視できない Stop-and-wait ARQ() 例 : 衛星通信衛星 : 地上より約 000 Km 上空伝播遅延時間 = 0 ms = x 000 Km/ x 10 m/s ACKを含めるとさらに倍 = 80 ms 衛星回線の伝送速度 :0 Kb/s パケット長 :1000 bit パケット伝送時間 :0 ms 通信回線が空きになる時間 = 80 / (80+0)= 9% 無駄が多すぎる! 7 8 Go-bac-N(1) 連続した番号をパケットに付与し, 連続して送出 i 番目に送られたパケットに誤りを検出した場合, (i + 1) 番目以降に受け取られたパケットは棄却廃棄タイムアウト時間再送 Go-bac-N() バッファ Stop-and-wait ARQ: バッファは 1 つでよかった Go-bac-N ARQ: 再送用バッファが必要スループット特性が良好であり, 実装が比較的容易なため, 現在最も用いられている方式 TCPも Go-bac-N ARQ を採用ただし, 受信側において伝送誤り後に正常に到着したパケットを蓄積し, 無駄な再送を省く実装になっている 9 0

7 Selective-repeat ARQ(1) 受信側にもバッファを用意誤りが検出されたパケットのみ再送廃棄タイムアウト時間再送 Selective-repeat ARQ() 伝送効率は Go-bac-N よりも優れている必要となる機構パケットの順序を整える機構パケットは必ずしも順番に到着しない受信側にパケット順序制御のためのバッファが必要実際のシステムではバッファが有限であるため, 順序制御中にバッファがあふれると, あふれたパケットも再送する必要がある 1 ARQ プロトコルの性能比較 (1) 平均伝送遅延時間特性 (n=0, p=0.01) ARQ プロトコルの性能比較 () 最大スループット特性 (n=0) n : パケットの送受信に要する単位時間 ARQ プロトコルの性能比較 () 往復伝播遅延時間 (p=0.01) ARQ プロトコルの性能比較 () 性能評価 Selective-repeat 方式が最も優れている Go-bac-N 方式は,n および p がある程度小さい場合, 良好な特性を提供できる特に p が小さければ Selective-repeat 方式と遜色ない Stop-and-wait 方式は n および p の両方ともかなり小さくなければ良好な特性は期待できない 7

8 . 誤り訂正 (FEC) 誤り訂正符合ブロック符号送信すべき情報をある長さ ( 例えばビット ) のブロックに分割し, 各ブロックごとに冗長な情報を付加ランダム誤り訂正符号 : ハミング符号,BCH 符号バースト誤り訂正符号 : リードソロモン符号畳み込み符号情報ビットが逐次符号器に入力されると, それ以前に入力された, ある長さの情報との演算を行うことで符号語を生成ビタビ符号ハミング符号 (1) つの符号語 a,, a, a, a ) と ( b,, b, b, ( n 1 n b1 において,a i b i となる個所の総数を, これらつのハミング (Hamming) 距離と定義する例 : (1, 0, 0, 1) と (1, 1, 0, 0) のハミング距離は ) 7 8 ハミング符号 () m bit 長のパケットと r bit 長のチェックビットを持った符号語の場合 : 符号語のビットパターン : m+r 各符号間のハミング距離が少なくとも以上となるようにするある符号のうち 1 bit が誤ったとしても, 他の符号語からのハミング距離が以上であるため, 誤りを検出し訂正可能符号語 : 真の情報と付加情報をあわせたものハミング符号 () 例 m = 1 bit,r = bit ビットパターン : = 8 通り (0,0,0) を符号語, さらにそれよりハミング距離がの (1,1,1) だけを許される符号語とする送信されるのはこのつのパターンだけ 9 0 ハミング符号 () 例 ( 続き ) (0,0,0) を伝送し,1 bit 誤りが発生したとき (0,0,1), (0,1,0), (1,0,0) のいずれかに変わる (1,1,1) を伝送し,1 bit 誤りが発生したとき (1,1,0), (1,0,1), (0,1,1) のいずれかに変わる (0,0,0) から変わったものと (1,1,1) から変わったものの間のハミング距離は 1 例 (1, 1, 0) を (0, 0, 1), (0, 1, 0), (1, 0, 0) と比較すると, ハミング距離は 1 どちらの符号語かを区別することができる 1 ハミング符号 () 一般に符号語間の最短ハミング距離が d min であるとき d a min (.0) で与えられる a 個までの誤りを訂正可能前ページの例では,1 bit の誤りを訂正可能この考え方に基づいて構成される符号をハミング符号 8

Microsoft PowerPoint - chapter6_2013.ppt [互換モード]

Microsoft PowerPoint - chapter6_2013.ppt [互換モード] 6. 6 データリンク層, トランスポート層における誤り制御 6 章誤り制御電子情報工学科 3 年前期ネットワークアーキテクチャ情報科学センター / ネットワークデザイン研究センター福田豊誤り制御データリンク層トランスポート層データリンク層 HDLC イーサネットトランスポート層 TCP アプリケーション層トランスポート層インターネット層データリンク層物理層 TCP/IP protocol