6. 6 データリンク層, トランスポート層における誤り制御 6 章誤り制御 電子情報工学科 3 年前期ネットワークアーキテクチャ情報科学センター / ネットワークデザイン研究センター福田豊 誤り制御 データリンク層 トランスポート層 データリンク層 HDLC イーサネット トランスポート層 TCP アプリケーション層トランスポート層インターネット層データリンク層物理層 TCP/IP protocol stack 53 TCP における誤り制御 パケット廃棄の検出 パケット廃棄検出の方法 Karn のアルゴリズム 廃棄パケットの再送 誤り制御方式 アプリケーション層 トランスポート層 インターネット層 データリンク層 Selective-repeat 物理層 TCP/IP protocol stack パケット廃棄の検出 (1) 本節に入る前に... 一般的な パケット Layer ごとに呼び方が異なる Layer2 : フレーム Layer3 : データグラム Layer4 : セグメント 以後, セグメントを用いる 54 55 パケット廃棄の検出 (2) TCP におけるセグメントの廃棄の検出方法は 2 種類 送信側がもつタイマーのタイムアウトにより検出 Karn のアルゴリズム 重複 ACK ビット誤りの検出方法 送信側でセグメント全体のチェックサムを計算しヘッダに書き込む 受信側で再び同じ演算を行い, 誤りを検出 56 タイムアウトによる検出 (1) TCP 受信側は新しいセグメントを受取るたびに常に ACK を返す 送信側はセグメントを送るたびに毎回タイマーをスタートさせて ACK を待つ タイムアウトすると,TCP はセグメントは廃棄されたものと判断し再送を行う タイムアウト トラヒックの変動によりセグメントが受信側へ到達するまでの時間は変化 遅延の変動を考慮してタイムアウトを決める必要がある 57 1
タイムアウトによる検出 (2) 再送タイムアウト RTO (Retransmission Time Out) の決定方法 RTT の平均 (average) と偏差 (deviation) を用いる RTO = average + 4 deviation RTT の平均と偏差の計算 error = measurement average average = average + σ error (6.26) (6.23) (6.24) deviation = deviation + σ ( error deviation) (6.25) タイムアウト発生時の問題点 セグメントを送信しタイマが時間切れになると TCP は同じセグメントを再送 そのセグメントの ACK が戻ってきたとき, もとのセグメントの ACK なのか, 再送したセグメントの ACK なのか, 区別することができない 往復伝播遅延 RTT がトラヒックの影響で急増したとき それまでの RTO がタイムアウト RTT の見積もりが小さいままであると, 再びタイムアウトを起こす可能性が高い 58 59 Karn のアルゴリズムとタイマバックオフ Karn のアルゴリズム 再送タイマの RTT の計測は行わない セグメントの再送が続く間は, 再送タイムアウトの値を 2 倍ずつ増加させる timeout = γ timeout ( 通常 γ = 2) (6.27) 重複 ACK によるセグメント廃棄検出 (1) セグメントの廃棄をタイムアウトのみで検出すると セグメントの廃棄が生じるたびに, タイムアウト期間だけ送信が停止 スループット特性を著しく劣化させる タイムスタンプオプション 4.4BSD から採用 送信側は TCP のヘッダの option field に送信時刻を書き込む 受信側は ACK を返す際にその時刻もコピーして返す 送信側は RTT を正確に計算可能 60 重複 ACK によりセグメント廃棄を検出し, そのセグメントをすぐに再送する (fast retransmit) 61 重複 ACK によるセグメント廃棄検出 (2) TCP では累積確認応答を用いている 例 : 20 番目までのセグメントを受信しており, それまですべてのセグメントを受信している場合は,21 番目のセグメントの送信を促す ACK を返す 続いて 22 番目のセグメントが到着した場合,21 番目のセグメントの送信を促す ACK を返す 重複 ACK 送信側 累積確認応答 受信側 セグメントサイズ 1,500 Byte 最初の送信 2000 ~ 3499 の 1500 Byte を送信 Ack は 3500 を送信 3499 までは受信できており, 次に受取るセグメントが 3500 62 63 2
重複 ACKによるセグメント廃棄検出 (3) 重複 ACKの例 送信セグメント 20 21 22 23 セグメント廃棄 ACK 21 21 21 20 22 23 受信セグメント 20 番まで連続して受信, 次は21 番 重複 ACK によるセグメント廃棄検出 (4) 重複 ACK が発生する場合 セグメントが途中の経路の変更によって到着順序が逆転 あるセグメントが廃棄され, それ以降のセグメントが到着 fast retransmit 順序の逆転による重複 ACK を考慮 送信側は 3 個以上の重複 ACK が連続して戻ってきた場合, セグメントが破棄されたと判断し, タイムアウトを待たずにそのセグメントの再送を行う 重複 ACK を用いる効果 タイムアウトよりも早くセグメント廃棄を検出可能 スループット特性の改善 64 65 Delayed ACK ホスト A と通信している場合 すぐさま ACK を返すのではなく,A にデータを送る際に ACK を付加して送信する ある時間 ( 通常 200ms) 経っても A にデータを送らない場合は,ACK だけを送信する 廃棄セグメントの再送 (1) 現在一般的なTCPが採用している ARQ 受信側にもバッファを用意し, 廃棄されたセグメント以降のセグメントを受信バッファに蓄積し, 無駄な再送を省いている Selective-repeat:TCP with Sack option Windows2000 以降で採用 66 67 廃棄セグメントの再送 (2) SACK ヘッダの option field の option 種別で SACK を明示 (option 種別に SACK を示す 4 を入れて送信 ) 廃棄セグメントの再送 (3) SACK(2) セグメントの廃棄を検出した場合は, この option field を用いて再送すべきセグメントを通知 通知できるのは 3 次まで バイト単位 68 69 3
廃棄セグメントの再送 (4) TCP SACK: 最初のセグメントだけが廃棄された場合 廃棄セグメントの再送 (5) TCP SACK: 複数のセグメントが廃棄された場合 70 71 まとめ (1) 誤り制御 輻輳や伝送エラーによる情報誤りを回復 ARQ,FEC 誤り制御が行われる Layer データリンク層, トランスポート層 誤り検出 真の情報 + 付加情報 = 符号語 パリティチェック方式 CRC 方式 CRC まとめ (2) m ビットのパケットを (m-1) 次の多項式 M(X) で表現 任意に r(r<m) 次の多項式 G(X) を定め, 以下の手順に従って CRC チェックビットを作る r(g(x) の次数 ) 個の0をmビットのパケットの後に付ける. すなわち多項式 X r M(X) 多項式 X r M(X) を多項式 G(X) で割り, 余りR(X) を求める 符号語 F(X) は r F( X ) X M ( X ) R( X ) 72 73 まとめ (5) シフトレジスタによる CRC 巡回符号を使用する場合割り算機能があればよい 2 進数の割り算回路は簡単なシフトレジスタで実現可能 ARQ Stop-and-wait Selective-repeat まとめ (6) Stop-and-wait 15 ACK 16 74 75 4
まとめ (7) 13 14 15 16 17 18 19 20 21 15 16 17 18 19 廃棄 タイムアウト時間 再送 まとめ (8) Selective-repeat 13 14 15 16 17 18 19 20 21 15 22 23 24 25 廃棄 タイムアウト時間 再送 76 77 まとめ (9) ARQ の性能評価 Selective-repeat が最も優れている 方式は,n および p がある程度小さい場合, 良好な特性を提供できる Stop-and-wait 方式は n および p の両方ともかなり小さくなければ良好な特性は期待できない (n = スロット, p = パケットに誤りが生じる確率 ) まとめ (10) 誤り訂正 (FEC) ブロック符号 送信すべき情報をある長さ ( 例えばkビット ) のブロックに分割し, 各ブロックごとに冗長な情報を付加 ランダム誤り訂正符号 : ハミング符号,BCH 符号 バースト誤り訂正符号 : リード ソロモン符号 畳み込み符号 情報ビットが逐次符号器に入力されると, それ以前に入力されたある長さの情報との演算を行うことで符号語を生成 ビタビ符号 78 79 まとめ (11) ハミング符号 2つの符号語 ( an,, a3, a2, a1) と ( bn,, b3, b2, b1 ) において,a i b i となる個所の総数を, これら2つのハミング (Hamming) 距離と定義する 一般に符号語間の最短ハミング距離がd min であるとき a d min 1 2 で与えられる a 個までの誤りを訂正可能 この考え方に基づいて構成される符号をハミング符号 まとめ (14) TCP における誤り制御 セグメントの廃棄 廃棄セグメントの再送 セグメントの廃棄の検出 タイムアウト RTO = average + 4 deviation Karnのアルゴリズム (1) 再送タイマのRTTの計測は行わない (2) セグメントの再送が続く間は, 再送タイムアウトの値を2 倍ずつ増加させる 重複 ACK 重複 ACKを3 回受取るとそのセグメトをすぐに再送 (fast retransmit) Delayed ACK 80 83 5
まとめ (15) TCP における廃棄セグメントの再送 ARQ としては Go-back-N,Selective-repeat 最近では Selective-repeat を利用した TCP with SACK option 参考文献 岩波講座インターネット第 1 巻 インターネット入門 尾家祐二, 後藤滋樹, 小西和憲, 西尾章治郎 ISBN4-00-011051-9 岩波講座インターネット第 3 巻 トランスポートプロトコル 村山公保, 西田佳史, 尾家祐二 ISBN4-00-011053-5 84 85 6