ボンドグラフと熱伝導解析による EHA熱解析ツールの開発

(1)

Kyushu Institute of Technology

4. インターネットの技術

計算機通信基礎(９)

2014年度

九州工業大学大学院

情報工学研究院

塚本和也

Kyushu Institute of Technology

今日の授業の内容



前回の授業の内容について



4. インターネットの技術



4.1 経路制御



4.2 誤り制御



4.3 フロー制御と輻輳制御

2

前回の授業内容について



インターネット上で用いられているネットワーク技術

について、その特徴を解説する

経路制御： データグラム方式（とバーチャルサーキット方式） IPとIPアドレス クラス化、サブネット化、NAT/NAPT 経路制御プロトコル IGP：距離ベクトル型、リンク状態型 EGP：パスベクトル型 3 Si Si Si Si Si Si Si Si Si Si Si Si Si Si SiSi Si Si Si Si ルータ（IGP） IGP 境界ルータ（EGP）

前回小テスト解答例１．

1. 経路制御方式である「バーチャネルサーキット」と「データグラム＋ホップバイホップ通信」の違いについて、それぞれ利点と欠点を明示した上で説明せよ。 バーチャルサーキット： 利点：経路を事前に確立するため、高い信頼性を提供可能。輻輳の解消が速やかに可能。 欠点：経路確立までに登録が必要となるため、時間がかかる。ルータの処理負荷が大きい。 データグラム＋ホップバイホップ通信： 利点：迅速に通信開始可能。ルータの処理負荷が小さく、スケーラビリティが高い 欠点：遅延やパケット廃棄が発生し、信頼性が低い。輻輳の解消に時間がかかる 4

前回小テスト解答例

2.

2. IPアドレスの使用用途、及び、それによる効果と問題点について、それぞれ説明せよ。また、その問題点を解決するための方法についても説明せよ。 IPアドレスの使用用途： (1)ホスト（計算機）の識別、(2) 経路決定 クラス化による効果 経路制御を容易にした。ルータ内の経路表のエントリ数を削減（スケーラビリティの向上） クラス化の問題点 アドレスの利用効率が悪い（ネットワーク規模に応じた柔軟な割当が不可） 問題点の解決方法 IPv6アドレスの導入（アドレス空間拡大）、プライベートIPアドレスの導入（NAT導入） 5 プライベートネットワークインターネットインターネットサーバ＋ NAT機能

前回小テスト解答例

3.

3. 経路制御プロトコルの種類について最初に説明した上で、それぞれのプロトコルの特徴や制御上の違いについて説明せよ。 経路制御プロトコルの種類は3種類 距離ベクトル型のRIP：距離と方向による経路制御 リンク状態型のOSPF：ネットワーク全体の接続状況を把握して経路制御 パスベクトル型のBGP：到達できるネットワークのリストを利用して経路制御 制御上の違い RIPとOSPF：AS内プロトコル ⇒ ネットワーク資源の有効利用が目的 BFPはAS間プロトコル ⇒ 契約に基づく経路制御が目的 6 Si Si Si Si Si Si Si Si Si Si Si Si Si Si SiSi Si Si Si Si ルータ（IGP） IGP 境界ルータ（EGP）

(2)

4.2 誤り制御

インターネットにおける経路制御（４．１節）

⇒ 宛先ホストに正しくパケットを配送できない可能性

1. ビット誤り：パケットは到着したが、ビットが正しくない場合 2. パケット廃棄：パケットがネットワーク内で廃棄される  ネットワーク内のルータで輻輳が発生し、バッファあふれが発生～パケット誤り（packet error)と呼ぶ



正確な通信を行うには

1. パケット誤りを検出（誤り検出） 2. その誤りを回復（誤り回復）～上記をまとめて誤り制御（error control)と呼ぶ 7

(4.2) 誤り検出と誤り回復



誤り検出機能、回復機能は、様々な層で行われている

（一つの層だけで行われるのではない！）



誤り検出機能

トランスポート，インターネット，データリンクの各プロトコルに備わっている 各ヘッダに「チェックサム」, 「チェックシーケンス」フィールドが存在 送信側：計算した値をヘッダに格納 受信側：受信情報を元に再度チェックサムを計算 ⇒不一致の場合、誤りを検出可能



誤りを回復する機能は主に

トランスポート層

で実装

UDP ⇒ 誤り回復機能を保持せず TCP ⇒ 誤り回復機能を備える 8

(4.2) TCPの誤り検出と回復機能



誤り検出：

TCPのヘッダ内の「確認応答番号」フィールドを用いる



誤り回復：

1. 受信側で行う場合：受信パケットを用いて誤りを検出し、その誤りを訂正（error correction)する

～ FEC (Forward Error Correction)方式と呼ぶ

冗長なデータが必要なため、利用シーンが限られる

2. 送信側で行う場合：送信者から再度パケットを送信

～ ARQ(Automatic Repeat reQuest)方式と呼ぶ

誤り検出方法として２種類が存在

受信側からパケット誤りを陽に知らせる（Explicit手法）

受信側から陽には知らせず、送信側で推定（Implicit手法）

9

(4.2) Explicit手法とImplicit手法



Explicit手法（パケット誤りを陽に通知）の実装例

～選択的確認応答

(selective acknowledgement)

新しいTCPにオプションとして搭載し始められている



Implicit手法（パケット誤りを推定）の実装例

～累積確認応答

(cumulative acknowledgement)

従来のTCPで広く用いられてきた 正しく受信できたシーケンス番号の最大値のみを伝える パケット誤りの判断の方法 タイムアウト(timeout) ⇒ 長い時間、確認応答が戻ってこない～重度の輻輳が発生したと判断

重複確認応答(duplicate acknowledgement: 重複ACK)⇒ 確認応答は戻ってくるが、一部欠損～軽度の輻輳が発生したと判断

10

4.2(a) 受信側におけるビット誤り検出1



ビット誤り

雑音により，送信したビット列の信号が正しく受信機に伝わらない場合を指す 引き起こす原因は雑音（ノイズ）と呼ばれる 何らかのエネルギーによる雑音（熱雑音） 他の伝送媒体との干渉によるもの（クロストーク） 電力線などからの雑音（スパイク雑音） 雑音から守るための手段 導線で回りを被覆する同軸ケーブル 光ファイバ（光通信） 一方で 空気を介した通信（無線通信） ⇒ 雑音の影響を強く受けるため、高いビット誤りが発生 11 雑音が小さく、低いビット誤り

4.2(a) 受信側におけるビット誤り検出2



ビット誤りの検出

送信側：冗長(redundant)な情報を真のデータに付加して伝送 受信側：受信情報に誤りが含まれているかを判断 誤り検出可能な符号 ⇒ 誤り検出符号 誤りを訂正可能な符号 ⇒ 誤り訂正符号 IP,UDP,TCP： チェックサムフィールドにパリティチェック(parity check)方式を採用 ⇒ 奇数個のビット誤りは検出できるが、偶数個のビット誤りは検出不可 データリンク層：

CRC(Cyclic Redundancy check)符号が使われている ⇒ 連続的（バーストと呼ぶ）なビット誤りを高い確率で検出可能

KビットのFCS(フレームチェックシーケンス）を用いると、Kビット以下の誤りを完全に、Kビット以上も高い確率で検出可能

12 インターネットで採用

(3)

4.2(b) 送信側におけるパケット誤り検出1



送信側：

受信側が4.2(a)の機能を用いて検出した誤りを把握（推定）～パケット再送を決定する



パケット誤り検出方法：

TCPセグメントのヘッダ内の「シーケンス番号」と「確認応答番号」を用いる 送信側：送信するセグメントに連続するシーケンス番号を付与 シーケンス番号は「バイト単位」でセグメントの先頭バイトを格納 受信側：正しく受信したセグメントの次のシーケンス番号 「次のセグメントの先頭のバイト番号」～累積確認応答、と呼ばれる 13 多くのTCPプロトコルがパケット誤りの検出に用いる

4.2(b) 送信側におけるパケット誤り検出2

累積確認応答を用いて送信側でパケット誤りを検出する場合、 7番目のセグメントがネットワーク上で廃棄されると仮定 送信側では7番の確認応答を複数受信する ⇒ 重複ACK 3つの重複ACKを受信するとセグメント廃棄と判断し，廃棄パケットを再送～高速再送(fast retransmit)と呼ぶ 重複ACKも返ってこないような場合，重度の輻輳と判断

再送タイムアウト時間(Retransmission Time Out, RTO)の設定～タイムアウト時間が経過してもACKを受信できない場合、パケットを再送 5 6 7 8 9 10 11 受信セグメント ACK番号 6 7 7 7 7 7 重複ACK 廃棄時間 14

4.2(c) 誤り回復のための再送

TCPは送信側による再送（ARQ方式）により誤りを回復

ARQには3種類

1. stop-and-waitARQ方式

2. Go-back-nARQ 方式

3. selective ACK(選択的 ACK) ARQ方式

現在のTCPで用いられている方式：～ Go-back-nとselective ACK

TCP TahoeとReno：Go-back-n SACKオプション付きTCP：selective ACK SACK（Selective ACK)：選択的確認応答～正しく受信できたブロックを複数個、通知する事ができる ⇒ ブロックの間（ギャップ）を廃棄パケットと判断可能 ⇒ 複数個のパケットを一度に再送可能＊ TCPヘッダのオプションフィールド長の制限から最大再送可能数は決定 15 廃棄パケット

(4.2(c)) 誤り回復:Stop-and-wait ARQ

送受信ホストは同時通信不可 ⇒ 半二重通信(half-duplex) 基本動作： 送信側は直前に送信したパケットに対するACKを受信するまで、次のパケットを送信できない ACKが戻ってこない場合、タイムアウトが発生し、パケットを再送 通信性能：1パケットの伝送時間/RTT 1RTT時間内に1パケットしか送信できないため 500Byteのパケットを1Mb/sで送信する場合 ⇒ 伝送効率は 10%程度～広域ネットワークに不向き、短距離で遅いネットワークには利用可 5 6 ACK 送信側受信側 16 無線LANで利用されている

(4.2(c)) 誤り回復:Go-back-n ARQ

送受信ホストが同時に通信可能な全二重通信が重要 基本動作 受信側でパケット誤りを検出すると，それに対するACKは返さず，その後に正しく受信したパケットに対してACKを返す ⇒ 累積確認応答 送信側でパケット誤りを検出し、再送したパケット以降の全パケットを再送 下図ではパケット8～13を既に受信しているが、再度再送（下図、橙箱）～受信側で誤り検出後の受信パケットの蓄積/順序制御が不要（実装が容易）～ stop-and-waitより効率がよい送信が可能（通信性能が向上） 7 7 7 7 5 6 7 8 9 10 11 12 13 7 8 9 6 7 送信受信重複ACK 廃棄 17

(4.2(c)) 誤り回復:Selective ACK ARQ

基本動作 受信側から送信するACKにおいて、正しく受信したパケット範囲（ブロック）を知らせる ⇒選択的確認応答(Selective ACK) ブロックのギャップから誤りパケットを把握し、再送 実現に必要な機能（受信側） 1. 廃棄パケット後に受信したパケットを蓄積するバッファを用意 2. アプリケーションに順序通りにパケットを渡すための制御 5 6 7 8 9 10 11 12 13 7 14 15 送信 1～6 8～11 1～6 8～10 1～6 8，9 1～6 8 1～5 1～6 受信廃棄 18 RTTが大きい場合、または高速ネットワークで有効実装は困難

(4)

4.3 フロー制御と輻輳制御



ネットワークを介した通信を考えてみる…

１．相手ホストの処理能力、ルータの利用状況を考えず送信 ２．処理しきれずパケットが廃棄される ３．再送が行われる ４．再送パケットの増加により輻輳が発生する

通信ホスト

の処理能力を考慮して送信することが必要

フロー制御 (flow control)

ネットワーク内の輻輳(congestion)解消

のためのフロー

制御も必要

輻輳制御 (congestion control) 19

4.3(a) 輻輳の検出



送信側で輻輳を検出するための手段は以下の2種類

1. ネットワークからの明示的な輻輳通知 (explicit notation)を利用 フレームリレー，ATMなどで採用されている ⇒ルータへの機能の追加実装が必要（複雑な機構になる）～検討はされているが、普及はしていない 2. 送信側で輻輳発生を予測する(implicit notation) TCPではパケット廃棄によって輻輳を判断 ⇒ パケット廃棄が発生するまで輻輳と判断できない～輻輳の検出が遅れる可能性が高い 20



輻輳検出時にパケットの転送速度を低下、それ以外は

転送速度を増加～フロー制御として2種類存在

1. レ－ト制御(rate control)： 各ルータで発生するバッファ待機パケット数を減少させるための制御～各ルータが次ルータに送信する際に、パケットの送信間隔を制御 インターネットでの実現は困難 1.細かい時間単位(制度の高いタイマ)での制御が必要 2.他のルータの出力レートを把握するのは不可能

4.3(b) フロー制御

21 ルータルータルータルータ • 次ルータには自分以外に2台ルータが接続 ⇒同時に3パケットが到着する可能性がある • 送信速度を1/3に低下させよう

4.3(b) フロー制御

2. ウィンドウフロー制御：

TCPでは、さらに緩やかなフロー制御を採用～ある時間間隔内で連続して送信可能なデータ量を制御 ある時間間隔 ⇒ 往復伝搬遅延時間（RTT） 連続送信可能なデータ量 ⇒ ウィンドウサイズ



緩やかな制御によってパケットの連続送信が可能

～

実装が容易

～通信性能が向上可能

22 ウィンドウサイズの決定方法が重要

ウィンドウサイズ（送信量）＝

min (awnd, cwnd)

（基本的にawnd > cwnd ⇒ 送信量はcwndで決定される）

4.3(b) フロー制御



ウィンドウサイズの決定方法：

～

相手ホストの処理能力

と

ネットワークの利用状況

を考慮

受信ホストが送信ホストに、処理可能なデータ量を

「告知ウィンドウ(advertised window: awnd)

（バッファの残りサイズ）」を通知 送信側は、ネットワーク内の輻輳状況に応じて「輻輳ウィンドウ (congestion window: cwnd)」を変化させる 23 Si Si SiSi cwnd awnd

4.3(b) フロー制御



ウィンドウ制御

送信パケットの内、現在送信可能な領域をウィンドウで示す ウィンドウの開始点とウィンドウサイズ ウィンドウサイズ ⇒ ネットワーク内部に存在するパケット数の最大値 ウィンドウサイズはネットワーク状態に応じて変化 ⇒ どのように変更するかを次スライドから説明 55 66 77 88 99 1010 1111 1212 1313 1414 ウィンドウ ACKを受信したパケット未送信パケット 24 送信されたがACK を受信していないパケットの最大数

(5)

4.3(c) TCPにおける動的なウィンドウサイズ制御



1RTT毎にウィンドウサイズで規定された量のパケットを

連続して送信

⇒ウィンドウサイズを推定した輻輳状態に応じて、

1RTT毎に動的に変化

させる

パケット廃棄がなく，全てのパケットのACKが返ってくる場合：～次のRTTの輻輳ウィンドウサイズを増加 パケット廃棄を検出した場合：～輻輳が発生したと判断し、輻輳を回避するためにウィンドウサイズを減少 ウィンドウサイズの増減をどのように行うか？ 25

4.3(c) TCPにおける動的なウィンドウサイズ制御



TCPが通過する経路を他のTCPも共有する

⇒1つのTCPが利用可能な回線容量（帯域、bandwidth)

を知ることは極めて困難となる



TCPは試行錯誤して、ウィンドウサイズを大きくしたり、

小さくしながら、他のTCPと帯域を共有

輻輳を検出した場合 ⇒ 急激にウィンドウサイズを小さくする 輻輳が生じない場合 ⇒ 利用可能な帯域まで早く到達するために早くウィンドウサイズを大きくしたい（でも輻輳は避けたい） 26 ：：ネットワーク内で競合する他のTCP の情報を把握できない TCP TahoeとRenoを例にウィンドウサイズの変化方法を説明

(4.3(c)) 動的なウィンドウサイズ変更：増加



(1)増加時（パケット廃棄が生じない場合）：

ウィンドウサイズの制御に2つのモード：～スロースタートモードと輻輳回避モードモード切替は閾値（ssthresh)を用いる 動作概要 スロースタートモード cwnd ≦ ssthresh (Slow Start Threshold)

1つのACK毎にcwnd=cwnd+1 ⇒ 1RTTでcwndが2倍に増加 輻輳回避モード cwnd ＞ ssthresh 1RTT毎にcwnd=cwnd+1 ⇒ 1RTTでcwndが1増加 1 2 3 4 5 6 7 8 9 10 11 12 cwnd ssthresh ACK ACK ACK ACK ACK ACK ACK 1 2 3 4 5 4 送信受信スロースタート輻輳回避 27

(4.3(c)) 動的なウィンドウサイズ変更：減少



(2)減少



タイムアウトまたは重複ACKによってセグメントの

廃棄を検出すると、ssthreth = cwnd/2に更新



Cwndも減少させる

Tahoe cwnd = 1 Reno タイムアウト発生：cwnd = 1 重複ACK発生時： cwnd = cwnd/2 （廃棄セグメントの再送が成功するまでの限定処理） ⇒高速リカバリー(fast recovery)、と呼ぶ 28

4.3(c) 動的なウィンドウサイズ変更1

29 0 1 2 3 4 10 cw nd 16 スロースタートモード輻輳回避モード Ssthresh 時間[RTT] 22 11 Ssthresh 更新 TCP Tahoeにおけるcwndの変化

4.3(c) 動的なウィンドウサイズ変更2

30 ネットワーク資源を複数のTCPで公平に効率よく共用する 0 1 2 3 4 10 cw nd 16 スロースタートモード輻輳回避モード Ssthresh 時間[RTT] 22 11 _{Ssthresh=cwnd} 更新輻輳回避モード高速リカバリー TCP Renoにおけるcwndの変化

(6)

今日のまとめ



誤り制御とフロー制御技術を紹介した

誤りは「ビット誤り」と「パケット廃棄」の2種類 誤り制御 誤り検出技術：データリンク、インターネット、トランスポート層 誤り回復技術：トランスポート層（TCP）

Go-back-n ARQ及び選択的ACK ARQが利用されている フロー制御 相手ホストの処理能力を考慮 ⇒ フロー制御 ネットワークの利用状況を考慮 ⇒ 輻輳制御 TCPのフロー制御 ⇒ ウィンドウフロー制御



次回講義：

5章インターネットの始まりと発展

31

ボンドグラフと熱伝導解析による EHA熱解析ツールの開発

4. インターネットの技術

計算機通信基礎(９)

九州工業大学大学院

情報工学研究院

塚本 和也

今日の授業の内容



前回の授業の内容について



4. インターネットの技術



4.1 経路制御



4.2 誤り制御



4.3 フロー制御と輻輳制御

前回の授業内容について



インターネット上で用いられているネットワーク技術

について、その特徴を解説する

前回小テスト 解答例 １．

前回小テスト 解答例

2.

前回小テスト 解答例

3.

4.2 誤り制御

インターネットにおける経路制御（４．１節）

⇒ 宛先ホストに正しくパケットを配送できない可能性



正確な通信を行うには

(4.2) 誤り検出と誤り回復



誤り検出機能、回復機能は、様々な層で行われている

（一つの層だけで行われるのではない！）



誤り検出機能



誤りを回復する機能は主に

トランスポート層

で実装

(4.2) TCPの誤り検出と回復機能



誤り検出：



誤り回復：

(4.2) Explicit手法とImplicit手法



Explicit手法（パケット誤りを陽に通知）の実装例

～選択的確認応答

(selective acknowledgement)



Implicit手法（パケット誤りを推定）の実装例

～累積確認応答

(cumulative acknowledgement)

4.2(a) 受信側におけるビット誤り検出1



ビット誤り

4.2(a) 受信側におけるビット誤り検出2



ビット誤りの検出

4.2(b) 送信側におけるパケット誤り検出1



送信側：



パケット誤り検出方法：

4.2(b) 送信側におけるパケット誤り検出2

4.2(c) 誤り回復のための再送

(4.2(c)) 誤り回復:Stop-and-wait ARQ

(4.2(c)) 誤り回復:Go-back-n ARQ

(4.2(c)) 誤り回復:Selective ACK ARQ

4.3 フロー制御と輻輳制御



ネットワークを介した通信を考えてみる…

通信ホスト

の処理能力を考慮して送信することが必要

ネットワーク内の輻輳(congestion)解消

のためのフロー

制御も必要

4.3(a) 輻輳の検出

塚本和也

前回小テスト解答例１．

前回小テスト解答例

前回小テスト解答例

転送速度を増加～フロー制御として2種類存在

～通信性能が向上可能

ウィンドウサイズ（送信量）＝

5章インターネットの始まりと発展