6スライド/枚 - 九州工業大学

今日の授業の内容
Kyushu Institute of Technology
計算機通信基礎(９)
前回の授業の内容について
4. インターネットの技術
2014年度
4. インターネットの技術
 4.1 経路制御
 4.2 誤り制御
 4.3 フロー制御と輻輳制御
九州工業大学大学院
情報工学研究院
塚本和也
2
Kyushu Institute of Technology
前回の授業内容について
前回小テスト解答例１．
Kyushu Institute of Technology
インターネット上で用いられているネットワーク技術
について、その特徴を解説する
 経路制御：
 データグラム方式（とバーチャルサーキット方式）
 IPとIPアドレス
 バーチャルサーキット：
 利点：経路を事前に確立するため、高い信頼性を提供可能。
クラス化、サブネット化、NAT/NAPT
輻輳の解消が速やかに可能。
 経路制御プロトコル
 欠点：経路確立までに登録が必要となるため、時間がかかる。
IGP：距離ベクトル型、リンク状態型
EGP：パスベクトル型
ルータの処理負荷が大きい。
境界ルータ
（EGP）
Si
 データグラム＋ホップバイホップ通信：
 利点：迅速に通信開始可能。
Si
Si
Si
ルータ
（IGP）
Si
ルータの処理負荷が小さく、スケーラビリティが高い
Si
Si
Si
Kyushu Institute of Technology
1. 経路制御方式である「バーチャネルサーキット」と「データグラム
＋ホップバイホップ通信」の違いについて、それぞれ利点と欠点
を明示した上で説明せよ。
 欠点：遅延やパケット廃棄が発生し、信頼性が低い。
IGP
輻輳の解消に時間がかかる
Si
Si
3
前回小テスト解答例 2.
4
前回小テスト解答例 3.
Kyushu Institute of Technology
2. IPアドレスの使用用途、及び、それによる効果と問題点について
、それぞれ説明せよ。また、その問題点を解決するための方法に
ついても説明せよ。
Kyushu Institute of Technology
3. 経路制御プロトコルの種類について最初に説明した上で、それ
ぞれのプロトコルの特徴や制御上の違いについて説明せよ。
 経路制御プロトコルの種類は3種類
 IPアドレスの使用用途：
 距離ベクトル型のRIP：距離と方向による経路制御
 (1)ホスト（計算機）の識別、(2) 経路決定
 リンク状態型のOSPF：ネットワーク全体の接続状況を把握して経路制御
 クラス化による効果
 パスベクトル型のBGP：到達できるネットワークのリストを利用して経路制御
 経路制御を容易にした。
 制御上の違い
ルータ内の経路表のエントリ数を削減（スケーラビリティの向上）
 RIPとOSPF：AS内プロトコル ⇒ ネットワーク資源の有効利用が目的
 クラス化の問題点
 BFPはAS間プロトコル ⇒ 契約に基づく経路制御が目的
 アドレスの利用効率が悪い（ネットワーク規模に応じた柔軟な割当が不可）
 問題点の解決方法
 IPv6アドレスの導入（アドレス空間拡大）、
プライベートIPアドレスの導入（NAT導入）プライベート
ネットワーク
サーバ＋
NAT機能
境界ルータ
（EGP）
Si
Si
Si
インターネット
Si
5
ルータ
（IGP）
Si
Si
Si
IGP
Si
Si
Si
6
1
4.2 誤り制御
(4.2) 誤り検出と誤り回復
Kyushu Institute of Technology
1. ビット誤り：パケットは到着したが、ビットが正しくない場合
 トランスポート，インターネット，データリンクの各プロトコルに
2. パケット廃棄：パケットがネットワーク内で廃棄される

Kyushu Institute of Technology
誤り検出機能、回復機能は、様々な層で行われている
（一つの層だけで行われるのではない！）
誤り検出機能
インターネットにおける経路制御（４．１節）
⇒ 宛先ホストに正しくパケットを配送できない可能性
備わっている
ネットワーク内のルータで輻輳が発生し、バッファあふれが発生
 各ヘッダに「チェックサム」, 「チェックシーケンス」フィールドが存在
 送信側：計算した値をヘッダに格納
 受信側：受信情報を元に再度チェックサムを計算
⇒不一致の場合、誤りを検出可能
～パケット誤り（packet error)と呼ぶ
正確な通信を行うには
1. パケット誤りを検出（誤り検出）
誤りを回復する機能は主にトランスポート層で実装
2. その誤りを回復（誤り回復）
～上記をまとめて誤り制御（error control)と呼ぶ
7
(4.2) TCPの誤り検出と回復機能
 UDP ⇒ 誤り回復機能を保持せず
 TCP ⇒ 誤り回復機能を備える
8
(4.2) Explicit手法とImplicit手法
Kyushu Institute of Technology
誤り検出：
Kyushu Institute of Technology
Explicit手法（パケット誤りを陽に通知）の実装例
～選択的確認応答(selective acknowledgement)
 TCPのヘッダ内の「確認応答番号」フィールドを用いる
誤り回復：
 新しいTCPにオプションとして搭載し始められている
1. 受信側で行う場合：受信パケットを用いて誤りを検出し、そ
Implicit手法（パケット誤りを推定）の実装例
～累積確認応答(cumulative acknowledgement)
の誤りを訂正（error correction)する
～ FEC (Forward Error Correction)方式と呼ぶ
 従来のTCPで広く用いられてきた
 冗長なデータが必要なため、利用シーンが限られる
 正しく受信できたシーケンス番号の最大値のみを伝える
2. 送信側で行う場合：送信者から再度パケットを送信
 パケット誤りの判断の方法
～ ARQ(Automatic Repeat reQuest)方式と呼ぶ
 タイムアウト(timeout) ⇒ 長い時間、確認応答が戻ってこない
～重度の輻輳が発生したと判断
 重複確認応答(duplicate acknowledgement: 重複ACK) ⇒
確認応答は戻ってくるが、一部欠損～軽度の輻輳が発生したと判断
 誤り検出方法として２種類が存在
受信側からパケット誤りを陽に知らせる（Explicit手法）
受信側から陽には知らせず、送信側で推定（Implicit手法）
9
4.2(a) 受信側におけるビット誤り検出1
10
4.2(a) 受信側におけるビット誤り検出2
Kyushu Institute of Technology
ビット誤り
Kyushu Institute of Technology
ビット誤りの検出
 雑音により，送信したビット列の信号が正しく受信機に
 送信側：冗長(redundant)な情報を真のデータに付加して伝送
伝わらない場合を指す
 引き起こす原因は雑音（ノイズ）と呼ばれる
 受信側：受信情報に誤りが含まれているかを判断
 誤り検出可能な符号 ⇒ 誤り検出符号
 誤りを訂正可能な符号 ⇒ 誤り訂正符号
 何らかのエネルギーによる雑音（熱雑音）
 他の伝送媒体との干渉によるもの（クロストーク）
 電力線などからの雑音（スパイク雑音）
 IP,UDP,TCP：
 チェックサムフィールドにパリティチェック(parity check)方式を採用
⇒ 奇数個のビット誤りは検出できるが、偶数個のビット誤りは検出不可
 雑音から守るための手段
 導線で回りを被覆する同軸ケーブル
 光ファイバ（光通信）
インターネットで採用
雑音が小さく、低いビット誤り
 一方で
 空気を介した通信（無線通信）
⇒ 雑音の影響を強く受けるため、高いビット誤りが発生
11
 データリンク層：
 CRC(Cyclic Redundancy check)符号が使われている
⇒ 連続的（バーストと呼ぶ）なビット誤りを高い確率で検出可能
KビットのFCS(フレームチェックシーケンス）を用いると、Kビット以下
の誤りを完全に、Kビット以上も高い確率で検出可能
12
2
4.2(b) 送信側におけるパケット誤り検出1
4.2(b) 送信側におけるパケット誤り検出2
Kyushu Institute of Technology
Kyushu Institute of Technology
 累積確認応答を用いて送信側でパケット誤りを検出する場合、
送信側：
 7番目のセグメントがネットワーク上で廃棄されると仮定
 受信側が4.2(a)の機能を用いて検出した誤りを把握（推定）
 送信側では7番の確認応答を複数受信する ⇒ 重複ACK
～パケット再送を決定する
 3つの重複ACKを受信するとセグメント廃棄と判断し，廃棄パケットを再送
パケット誤り検出方法：
～高速再送(fast retransmit)と呼ぶ
 TCPセグメントのヘッダ内の「シーケンス番号」と「確認応答番号」
を用いる
 重複ACKも返ってこないような場合，重度の輻輳と判断
 再送タイムアウト時間(Retransmission Time Out, RTO)の設定
～タイムアウト時間が経過してもACKを受信できない場合、パケットを再送
 送信側：送信するセグメントに連続するシーケンス番号を付与
 シーケンス番号は「バイト単位」でセグメントの先頭バイトを格納
5
受信セグメント
 受信側：正しく受信したセグメントの次のシーケンス番号
 「次のセグメントの先頭のバイト番号」
6
6
ACK番号
7
廃棄
7
8
9 10 11
7
7
7
7
時間
～累積確認応答、と呼ばれる
多くのTCPプロトコルがパケット誤りの検出に用いる
重複ACK
13
4.2(c) 誤り回復のための再送
14
(4.2(c)) 誤り回復:Stop-and-wait ARQ
Kyushu Institute of Technology
 TCPは送信側による再送（ARQ方式）により誤りを回復
 ARQには3種類
Kyushu Institute of Technology
 送受信ホストは同時通信不可 ⇒ 半二重通信 (half-duplex)
 基本動作：
1. stop-and-wait ARQ方式
 送信側は直前に送信したパケットに対するACKを受信するまで、
次のパケットを送信できない
2. Go-back-n ARQ 方式
 ACKが戻ってこない場合、タイムアウトが発生し、パケットを再送
3. selective ACK (選択的 ACK) ARQ方式
 通信性能： 1パケットの伝送時間/RTT
 現在のTCPで用いられている方式：
～ Go-back-n と selective ACK
 1RTT時間内に1パケットしか送信できないため
 500Byteのパケットを1Mb/sで送信する場合 ⇒ 伝送効率は 10%程度
 TCP TahoeとReno：Go-back-n
 SACKオプション付きTCP：selective ACK
 SACK（Selective ACK)：選択的確認応答
～正しく受信できたブロックを複数個、通知する事ができる
廃棄パケット
⇒ ブロックの間（ギャップ）を廃棄パケットと判断可能
⇒ 複数個のパケットを一度に再送可能
＊ TCPヘッダのオプションフィールド長の制限から最大再送可能数は決定
～広域ネットワークに不向き、短距離で遅いネットワークには利用可
送信側
5
6
無線LANで
利用されている
受信側
ACK
15
(4.2(c)) 誤り回復:Go-back-n ARQ
(4.2(c)) 誤り回復:Selective ACK ARQ
Kyushu Institute of Technology
Kyushu Institute of Technology
 基本動作
 送受信ホストが同時に通信可能な全二重通信が重要
 基本動作
 受信側から送信するACKにおいて、正しく受信したパケット範囲（ブロック）
 受信側でパケット誤りを検出すると，それに対するACKは返さず，その後に正
しく受信したパケットに対してACKを返す ⇒ 累積確認応答
 送信側でパケット誤りを検出し、再送したパケット以降の全パケットを再送
を知らせる ⇒ 選択的確認応答 (Selective ACK)
 ブロックのギャップから誤りパケットを把握し、再送
 実現に必要な機能（受信側）
～受信側で誤り検出後の受信パケットの蓄積/順序制御が不要（実装が容易）
～ stop-and-waitより効率がよい送信が可能（通信性能が向上）
2. アプリケーションに順序通りにパケットを渡すための制御
5 6 7 8 9 10 11 12 13 7 8 9
6 7
RTTが大きい場合、または高速ネットワークで有効
廃棄
廃棄
受信
送信
7 7 7 7
重複ACK
実装は困難
1. 廃棄パケット後に受信したパケットを蓄積するバッファを用意
 下図ではパケット8～13を既に受信しているが、再度再送（下図、橙箱）
送信
16
5
6
7
8
受信
17
1～5 1～6
9
10 11 12 13
1～6 1～6 1～6 1～6
8
8，9 8～10 8～11
7
14 15
18
3
4.3 フロー制御と輻輳制御
4.3(a) 輻輳の検出
Kyushu Institute of Technology
ネットワークを介した通信を考えてみる…
Kyushu Institute of Technology
送信側で輻輳を検出するための手段は以下の2種類
 １．相手ホストの処理能力、ルータの利用状況を考えず送信
1. ネットワークからの明示的な輻輳通知 (explicit
 ２．処理しきれずパケットが廃棄される
notation)を利用
 ３．再送が行われる
 フレームリレー，ATMなどで採用されている
⇒ルータへの機能の追加実装が必要（複雑な機構になる）
～検討はされているが、普及はしていない
 ４．再送パケットの増加により輻輳が発生する
通信ホストの処理能力を考慮して送信することが必要
2. 送信側で輻輳発生を予測する (implicit notation)
 フロー制御 (flow control)
ネットワーク内の輻輳(congestion)解消のためのフロー
制御も必要
 TCPではパケット廃棄によって輻輳を判断
⇒ パケット廃棄が発生するまで輻輳と判断できない
～輻輳の検出が遅れる可能性が高い
 輻輳制御 (congestion control)
19
4.3(b) フロー制御
20
4.3(b) フロー制御
Kyushu Institute of Technology
Kyushu Institute of Technology
2. ウィンドウフロー制御：
輻輳検出時にパケットの転送速度を低下、それ以外は
転送速度を増加～フロー制御として2種類存在
 TCPでは、さらに緩やかなフロー制御を採用
1. レ－ト制御(rate control)：
～ある時間間隔内で連続して送信可能なデータ量を制御
 各ルータで発生するバッファ待機パケット数を減少させるための制御
～各ルータが次ルータに送信する際に、パケットの送信間隔を制御
 ある時間間隔 ⇒ 往復伝搬遅延時間（RTT）
 連続送信可能なデータ量 ⇒ ウィンドウサイズ
ルータ
• 次ルータには自分以外に2台ルータが接続
⇒同時に3パケットが到着する可能性がある
• 送信速度を1/3に低下させよう
ルータ
緩やかな制御によってパケットの連続送信が可能
ルータ
～実装が容易
～通信性能が向上可能
ルータ
 インターネットでの実現は困難
1. 細かい時間単位(制度の高いタイマ)での制御が必要
2. 他のルータの出力レートを把握するのは不可能
ウィンドウサイズの決定方法が重要
21
4.3(b) フロー制御
22
4.3(b) フロー制御
Kyushu Institute of Technology
ウィンドウサイズの決定方法：
～相手ホストの処理能力とネットワークの利用状況を考慮
Kyushu Institute of Technology
ウィンドウ制御
 送信パケットの内、現在送信可能な領域をウィンドウで示す
 ウィンドウの開始点とウィンドウサイズ
 受信ホストが送信ホストに、処理可能なデータ量を
「告知ウィンドウ (advertised window: awnd)
（バッファの残りサイズ）」を通知
 送信側は、ネットワーク内の輻輳状況に応じて「輻輳ウィンドウ
(congestion window: cwnd)」を変化させる
 ウィンドウサイズ ⇒
ネットワーク内部に存在するパケット数の最大値
 ウィンドウサイズはネットワーク状態に応じて変化
⇒ どのように変更するかを次スライドから説明
ウィンドウサイズ（送信量）＝ min (awnd, cwnd)
（基本的にawnd > cwnd ⇒ 送信量はcwndで決定される）
ACKを受信したパケット
送信されたがACK
を受信していない
パケットの最大数
未送信パケット
ウィンドウ
cwnd
Si
5 6 7 8 9 10 11 12 13 14
Si
awnd
23
24
4
4.3(c) TCPにおける動的なウィンドウサイズ制御
4.3(c) TCPにおける動的なウィンドウサイズ制御
Kyushu Institute of Technology
1RTT毎にウィンドウサイズで規定された量のパケットを
連続して送信
⇒ウィンドウサイズを推定した輻輳状態に応じて、
1RTT毎に動的に変化させる
 パケット廃棄がなく，全てのパケットのACKが返ってくる場合：
～次のRTTの輻輳ウィンドウサイズを増加
 パケット廃棄を検出した場合：
～輻輳が発生したと判断し、輻輳を回避するために
ウィンドウサイズを減少
Kyushu Institute of Technology
TCPが通過する経路を他のTCPも共有する
⇒1つのTCPが利用可能な回線容量（帯域、bandwidth)
を知ることは極めて困難となる
ネットワーク内で
競合する他のTCP
の情報を把握できない
：
：
TCPは試行錯誤して、ウィンドウサイズを大きくしたり、
小さくしながら、他のTCPと帯域を共有
 輻輳を検出した場合 ⇒ 急激にウィンドウサイズを小さくする
 輻輳が生じない場合 ⇒ 利用可能な帯域まで早く到達するた
めに早くウィンドウサイズを大きくしたい（でも輻輳は避けたい）
 ウィンドウサイズの増減をどのように行うか？
25
(4.3(c)) 動的なウィンドウサイズ変更：増加
TCP TahoeとRenoを例にウィンドウサイズの変化方法を説明
(4.3(c)) 動的なウィンドウサイズ変更：減少
Kyushu Institute of Technology
(1)増加時（パケット廃棄が生じない場合）：
 タイムアウトまたは重複ACKによってセグメントの
廃棄を検出すると、ssthreth = cwnd/2に更新
cwnd
4
 スロースタートモード
送信
1
1
2
2
3
受信
 Cwndも減少させる
Tahoe
ACK
cwnd ≦ ssthresh
(Slow Start Threshold)
1つのACK毎にcwnd=cwnd+1
スロー
スタート
3
4
⇒ 1RTTでcwndが2倍に増加
 輻輳回避モード
cwnd ＞ ssthresh
1RTT毎にcwnd=cwnd+1
Kyushu Institute of Technology
(2)減少
 ウィンドウサイズの制御に2つのモード：
～スロースタートモードと輻輳回避モード
モード切替は閾値（ssthresh)を用いる ssthresh
 動作概要
輻輳回避
5
⇒ 1RTTでcwndが1増加
4
5
6
7
8
9
10
11
12
ACK
ACK
cwnd = 1
Reno
タイムアウト発生：cwnd = 1
重複ACK発生時： cwnd = cwnd/2
（廃棄セグメントの再送が成功するまでの限定処理）
⇒高速リカバリー(fast recovery)、と呼ぶ
ACK
ACK
ACK
ACK
27
4.3(c) 動的なウィンドウサイズ変更1
28
4.3(c) 動的なウィンドウサイズ変更2
Kyushu Institute of Technology
Kyushu Institute of Technology
 TCP Renoにおけるcwndの変化
 TCP Tahoeにおけるcwndの変化
スロースタート
モード
スロースタート
モード
輻輳回避モード
輻輳回避モード
輻輳回避モード
22
Ssthresh
16
11
0 1 2 34
cwnd
22
cwnd
26
更新
Ssthresh
10
16
Ssthresh
11
0 1 2 34
時間 [RTT]
29
高速リカバリー
更新
Ssthresh=cwnd
10
時間 [RTT]
ネットワーク資源を複数のTCPで公平に効率よく共用する
30
5
今日のまとめ
Kyushu Institute of Technology
誤り制御とフロー制御技術を紹介した
 誤りは「ビット誤り」と「パケット廃棄」の2種類
 誤り制御
 誤り検出技術：データリンク、インターネット、トランスポート層
 誤り回復技術：トランスポート層（TCP）
Go-back-n ARQ及び選択的ACK ARQが利用されている
 フロー制御
 相手ホストの処理能力を考慮 ⇒ フロー制御
 ネットワークの利用状況を考慮 ⇒ 輻輳制御
 TCPのフロー制御 ⇒ ウィンドウフロー制御
次回講義：5章インターネットの始まりと発展
31
6

Download Report