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

Size: px

Start display at page:

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

もえりあいきょう
5 years ago
Views:

1 6. 6 データリンク層, トランスポート層における誤り制御 6 章誤り制御電子情報工学科 3 年前期ネットワークアーキテクチャ情報科学センター / ネットワークデザイン研究センター福田豊誤り制御データリンク層トランスポート層データリンク層 HDLC イーサネットトランスポート層 TCP アプリケーション層トランスポート層インターネット層データリンク層物理層 TCP/IP protocol stack 53 TCP における誤り制御パケット廃棄の検出パケット廃棄検出の方法 Karn のアルゴリズム廃棄パケットの再送誤り制御方式アプリケーション層トランスポート層インターネット層データリンク層 Selective-repeat 物理層 TCP/IP protocol stack パケット廃棄の検出 (1) 本節に入る前に... 一般的なパケット Layer ごとに呼び方が異なる Layer2 : フレーム Layer3 : データグラム Layer4 : セグメント以後, セグメントを用いるパケット廃棄の検出 (2) TCP におけるセグメントの廃棄の検出方法は 2 種類送信側がもつタイマーのタイムアウトにより検出 Karn のアルゴリズム重複 ACK ビット誤りの検出方法送信側でセグメント全体のチェックサムを計算しヘッダに書き込む受信側で再び同じ演算を行い, 誤りを検出 56 タイムアウトによる検出 (1) TCP 受信側は新しいセグメントを受取るたびに常に ACK を返す送信側はセグメントを送るたびに毎回タイマーをスタートさせて ACK を待つタイムアウトすると,TCP はセグメントは廃棄されたものと判断し再送を行うタイムアウトトラヒックの変動によりセグメントが受信側へ到達するまでの時間は変化遅延の変動を考慮してタイムアウトを決める必要がある 57 1

2 タイムアウトによる検出 (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 の見積もりが小さいままであると, 再びタイムアウトを起こす可能性が高い 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 までは受信できており, 次に受取るセグメントが

3 重複 ACKによるセグメント廃棄検出 (3) 重複 ACKの例送信セグメントセグメント廃棄 ACK 受信セグメント 20 番まで連続して受信, 次は21 番重複 ACK によるセグメント廃棄検出 (4) 重複 ACK が発生する場合セグメントが途中の経路の変更によって到着順序が逆転あるセグメントが廃棄され, それ以降のセグメントが到着 fast retransmit 順序の逆転による重複 ACK を考慮送信側は 3 個以上の重複 ACK が連続して戻ってきた場合, セグメントが破棄されたと判断し, タイムアウトを待たずにそのセグメントの再送を行う重複 ACK を用いる効果タイムアウトよりも早くセグメント廃棄を検出可能スループット特性の改善 Delayed ACK ホスト A と通信している場合すぐさま ACK を返すのではなく,A にデータを送る際に ACK を付加して送信するある時間 ( 通常 200ms) 経っても A にデータを送らない場合は,ACK だけを送信する廃棄セグメントの再送 (1) 現在一般的なTCPが採用している ARQ 受信側にもバッファを用意し, 廃棄されたセグメント以降のセグメントを受信バッファに蓄積し, 無駄な再送を省いている Selective-repeat:TCP with Sack option Windows2000 以降で採用廃棄セグメントの再送 (2) SACK ヘッダの option field の option 種別で SACK を明示 (option 種別に SACK を示す 4 を入れて送信 ) 廃棄セグメントの再送 (3) SACK(2) セグメントの廃棄を検出した場合は, この option field を用いて再送すべきセグメントを通知通知できるのは 3 次までバイト単位

4 廃棄セグメントの再送 (4) TCP SACK: 最初のセグメントだけが廃棄された場合廃棄セグメントの再送 (5) TCP SACK: 複数のセグメントが廃棄された場合まとめ (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 ) まとめ (5) シフトレジスタによる CRC 巡回符号を使用する場合割り算機能があればよい 2 進数の割り算回路は簡単なシフトレジスタで実現可能 ARQ Stop-and-wait Selective-repeat まとめ (6) Stop-and-wait 15 ACK

5 まとめ (7) 廃棄タイムアウト時間再送まとめ (8) Selective-repeat 廃棄タイムアウト時間再送まとめ (9) ARQ の性能評価 Selective-repeat が最も優れている方式は,n および p がある程度小さい場合, 良好な特性を提供できる Stop-and-wait 方式は n および p の両方ともかなり小さくなければ良好な特性は期待できない (n = スロット, p = パケットに誤りが生じる確率 ) まとめ (10) 誤り訂正 (FEC) ブロック符号送信すべき情報をある長さ ( 例えばkビット ) のブロックに分割し, 各ブロックごとに冗長な情報を付加ランダム誤り訂正符号 : ハミング符号,BCH 符号バースト誤り訂正符号 : リードソロモン符号畳み込み符号情報ビットが逐次符号器に入力されると, それ以前に入力されたある長さの情報との演算を行うことで符号語を生成ビタビ符号まとめ (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

6 まとめ (15) TCP における廃棄セグメントの再送 ARQ としては Go-back-N,Selective-repeat 最近では Selective-repeat を利用した TCP with SACK option 参考文献岩波講座インターネット第 1 巻インターネット入門尾家祐二, 後藤滋樹, 小西和憲, 西尾章治郎 ISBN 岩波講座インターネット第 3 巻トランスポートプロトコル村山公保, 西田佳史, 尾家祐二 ISBN

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

Microsoft PowerPoint - chapter6_2012.ppt [互換モード] 章誤り制御電子情報工学科年前期ネットワークアーキテクチャ情報科学センター / ネットワークデザイン研究センター福田豊 Agenda 学ぶ主な内容は以下のつ誤りを検出する方法誤り検出後, 訂正する方法誤り検出方法パリティ,CRC 誤り制御 ARQ,FEC ARQ 方式の紹介とその性能評価誤り訂正 Layer と Layer における誤り制御 1 情報. 1 はじめに (1) 伝送路における電気的な雑音等により内容が変化