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