Chapter 3

Chapter 3
Transport Layer
A note on the use of these ppt slides:
We’re making these slides freely available to all (faculty, students, readers).
They’re in PowerPoint form so you can add, modify, and delete slides
(including this one) and slide content to suit your needs. They obviously
represent a lot of work on our part. In return for use, we only ask the
following:
 If you use these slides (e.g., in a class) in substantially unaltered form,
that you mention their source (after all, we’d like people to use our book!)
 If you post any slides in substantially unaltered form on a www site, that
you note that they are adapted from (or perhaps identical to) our slides, and
note our copyright of this material.
Computer Networking:
A Top Down Approach
Featuring the Internet,
2nd edition.
Jim Kurose, Keith Ross
Addison-Wesley, July
2002.
Thanks and enjoy! JFK/KWR
All material copyright 1996-2002
J.F Kurose and K.W. Ross, All Rights Reserved
Transport Layer
3-1
Chapter 3: トランスポート層
目標:
 トランスポート層サービ
スの背後にある原理の
理解:




多重化／逆多重化
高信頼データ転送
フロー制御
輻輳制御
 インターネットにおけるトラン
スポート層について学習:



UDP: コネクションレストランス
ポート
TCP: コネクション指向トランス
ポート
TCP 輻輳制御
Transport Layer
3-2
Chapter 3 内容
 3.1 トランスポート層サー
ビス
 3.2 多重化と逆多重化
 3.3 コネクションレス型ト
ランスポート: UDP
 3.4 高信頼データ転送の
原理
 3.5 コネクション指向型トラ
ンスポート: TCP




セグメント構造
高信頼データ転送
フロー制御
コネクション管理
 3.6 輻輳制御の原理
 3.7 TCP 輻輳制御
Transport Layer
3-3
トランスポートサービスとプロトコル
 異なるホスト間で実行されるアプ
リ間に論理的通信を提供
 トランスポートプロトコルはエンド
システムにおいて実行


送信側：アプリケーションメッ
セージをセグメントに分割し，
ネットワーク層に渡す
受信側：セグメントからメッセ
ージを再構成し，アプリケー
ション層に渡す
 アプリケーションにとってひとつ以
上のプロトコルが利用可能
 インターネット: TCP と UDP
application
transport
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
application
transport
network
data link
physical
Transport Layer
3-4
トランスポート層とネットワーク層

ネットワーク層: ホスト間
の論理的通信

トランスポート層: プロセ
ス間の論理的通信

ネットワーク層サービスに
依存し，その機能を強化す
る
家庭での類似:
12 人の子供が12人の子供
に手紙を送る
 プロセス = 子供
 アプリケーションメッセー
ジ = 封筒内の手紙
 ホスト = 家庭
 転送プロトコル = アンとビ
ル
 ネットワーク層プロトコル=
郵便サービス
Transport Layer
3-5
インターネットトランスポート層プロトコル
 高信頼，順序保証配送:
TCP



輻輳制御
フロー制御
コネクションセットアップ
application
transport
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
 低信頼，順序非保証配送:
UDP

“best-effort” IP に特別な
機能を追加しない（プロセス
識別のみ）
 利用できないサービス:
 遅延保証
 帯域保証
network
data link
physical
network
data link
physical
application
transport
network
data link
physical
Transport Layer
3-6
Chapter 3 内容
 3.1 トランスポート層サー
ビス
 3.2 多重化と逆多重化
 3.3 コネクションレス型ト
ランスポート: UDP
 3.4 高信頼データ転送の
原理
 3.5 コネクション指向型トラ
ンスポート: TCP




セグメント構造
高信頼データ転送
フロー制御
コネクション管理
 3.6 輻輳制御の原理
 3.7 TCP 輻輳制御
Transport Layer
3-7
多重化／逆多重化
始点ホストにおける多重化:
複数ソケットからデータを集め，
（後に逆多重で用いられる）ヘッ
ダを付加してまとめる
終点ホストにおける逆多重化:
受信セグメントを適切なソケットに
転送
= socket
application
transport
network
link
= process
P3
P1
P1
application
transport
network
P2
P4
application
transport
network
link
link
physical
host 1
physical
host 2
physical
host 3
Transport Layer
3-8
逆多重化はどのように機能するか
 ホストはIPデータグラムを受信



各データグラムは，送信IPア
ドレス，受信IPアドレス
各データグラムは，ひとつのト
ランスポート層セグメントを運
ぶ
各セグメントは，送信ポート番
号と受信ポート番号をもつ
（特定のアプリの有名なポート
番号を思い出そう）
32 bits
始点ポート番号終点ポート番号
他のヘッダフィールド
アプリケーションデータ
（メッセージ）
 ホストは，適切なソケットにセグメ
ントを向けるためにＩＰアドレスとポ
ート番号を使う
TCP/UDP セグメントフォーマット
Transport Layer
3-9
コネクションレス型の逆多重化
 ポート番号を付与してソケッ
トを生成：
DatagramSocket mySocket1 = new
DatagramSocket(99111);
DatagramSocket mySocket2 = new
DatagramSocket(99222);
 UDP ソケットは
（終点ＩＰアドレス，終点ポート
番号）
で識別される
 ホストがUDPセグメントを
受信すると：


セグメント内の終点ポート番
号をチェック
UDPセグメントをそのポート
番号をもつソケットに向ける
 同一ソケットにむけられた
異なる始点ＩＰアドレスある
いはまた異なる始点ポート
番号をもつIPデータグラム
Transport Layer 3-10
コネクションレス型の逆多重化（つづき）
DatagramSocket serverSocket = new DatagramSocket(6428);
P3
P1
P1
P3
SP: 6428
SP: 6428
DP: 9157
DP: 5775
SP: 9157
client
IP: A
DP: 6428
SP: 5775
server
IP: C
DP: 6428
Client
IP:B
始点ポート番号は“返信アドレス”として使用される
Transport Layer
3-11
コネクション指向型の逆多重化
 TCP ソケットは次の４つの
値によって識別される:




始点IPアドレス
始点ポート番号
終点IPアドレス
終点ポート番号
 終点ホストは，4つの値を
使ってセグメントをアプリケ
ーションソケットに向ける
 サーバホストは同時に多数
のTCPソケットをサポートす
るかもしれない：

各ソケットは自身の４つの値
によって識別される
 Ｗｅｂサーバは各クライアン
トに対して異なるソケットを
持つ

非継続型 HTTP は各リクエ
ストに対して異なるソケットを
持つ
Transport Layer 3-12
コネクション指向型の逆多重（つづき）
P3
P3
SP: 80
SP: 80
DP: 9157
DP: 5775
SP: 9157
client
IP: A
DP: 80
P1
P1
P4
SP: 5775
server
IP: C
DP: 80
Client
IP:B
Transport Layer 3-13
Chapter 3 内容
 3.1 トランスポート層サー
ビス
 3.2 多重化と逆多重化
 3.3 コネクションレス型ト
ランスポート: UDP
 3.4 高信頼データ転送の
原理
 3.5 コネクション指向型トラ
ンスポート: TCP




セグメント構造
高信頼データ転送
フロー制御
コネクション管理
 3.6 輻輳制御の原理
 3.7 TCP 輻輳制御
Transport Layer 3-14
UDP: User Datagram Protocol [RFC 768]
 “余計な機能のない,” “余計な
部分を削った” インターネットト
ランスポートプロトコル
 “ベストエフォート” サービス，
UDPセグメントは， may be:
 失われる


アプリへの非順序保証配
信
コネクションレス：


送信，受信間でハンドシェ
イク不要
各 UDP セグメントは互い
に独立に扱われる
なぜ UDP は存在する
のか？
 （遅延の原因となりうる）コ
ネクション設定不要
 単純：送受信側でコネク
ション状態なし
 小さいセグメントヘッダ
 輻輳制御なし：UDP は，
所望の速度で送信可能
Transport Layer 3-15
UDP: さらに
 ストリーミングマルチメディアア
プリケーションによく利用され
る
Length, in
 廃棄への耐性
bytes of UDP
segment,
 速度に敏感
including
 他の UDP アプリ
header
 DNS
 SNMP
 アプリ層で追加されたUDPを
介した高信頼転送

アプリケーション独自のエ
ラー回復！
32 bits
始点ポート番号終点ポート番号
長さ
チェックサム
アプリケーションデータ
（メッセージ）
UDP セグメントフォーマット
Transport Layer 3-16
UDP チェックサム
目的: 転送セグメント中の“誤り”を検出する（例えば，ビット
反転など）
始点ホスト:
終点ホスト:
 セグメントの内容を16ビット整
 受信セグメントの内容の和をチェ
数の系列として扱う
 チェックサム: セグメントの内
容の和の１の補数
 始点ホストは，UDPチェックサ
ムフィールドにチェックサム値
を入力
ックサムフィールドを含めて計算
 全てのビットが１となる
 NO – 誤り検出
 YES – 誤り未検出．誤りはな
いのか？
0110011001100110
+0101010101010101
+0000111100001111
=1100101011001010
1の補数=0011010100110101
Transport Layer 3-17
Chapter 3 内容
 3.1 トランスポート層サー
ビス
 3.2 多重化と逆多重化
 3.3 コネクションレス型ト
ランスポート: UDP
 3.4 高信頼データ転送の
原理
 3.5 コネクション指向型トラ
ンスポート: TCP




セグメント構造
高信頼データ転送
フロー制御
コネクション管理
 3.6 輻輳制御の原理
 3.7 TCP 輻輳制御
Transport Layer 3-18
高信頼データ転送の原理
 アプリ層，トランスポート層，リンク層において重要
 重要課題トップ１０！
 低信頼性チャネルの特徴が高信頼データ転送プロトコル
(rdt: reliable data transfer) の複雑さを決定付ける
Transport Layer 3-19
高信頼データ転送：はじめに
rdt_send(): 上位層（例：アプリ層）
から呼び出される．データを終点ホスト
側で上位層に渡してください．
送信側
udt_send(): rdt によって呼び
出される．低信頼性チャネルを介
してパケットを終点ホストに転送
deliver_data():上位層にデータを配
信するためにrdtによって呼び出される．
受信側
rdt_rcv(): チャネルの終点ホスト側
にパケットが到着すると呼び出される
Transport Layer 3-20
高信頼データ転送：はじめに
以後:
 高信頼転送プロトコル(rdt)の始点ホスト，終点ホスト
を順に発展させる
 一方向転送のみを考える

ただし，制御情報は両方向に流れる
 始点ホスト，終点ホストを記述するために有限状態マ
シン (FSM: finite state machines) を用いる
状態遷移を引き起こすイベント
状態遷移によってとられるアクション
状態: この状態にいるとき，
次のイベントによって次
状態が一意に決定され
る
state
1
event
actions
state
2
Transport Layer 3-21
Rdt1.0: 高信頼チャネルを介した高信頼転送
 下層チャネルは完全に信頼できる
 ビットエラーなし
 パケット損失なし
 始点ホストと終点ホストは分離:
 始点ホストはデータを下層チャネルに送信する
 終点ホストは下層チャネルからデータを読む
Wait for
call from
above
rdt_send(data)
packet = make_pkt(data)
udt_send(packet)
sender
Wait for
call from
below
rdt_rcv(packet)
extract (packet,data)
deliver_data(data)
receiver
Transport Layer 3-22
Rdt2.0: ビットエラーのあるチャネル
 下層チャネルでパケット内のビット反転が発生しうる
 UDPチェックサムはビットエラーを検出できる

疑問: 誤りからどのように回復するか:

acknowledgements (ACKs): 終点ホストが受信パケットはＯＫで
あると明示的に伝える






negative acknowledgements (NAKs): 終点ホストが受信パケッ
トに誤りがあると明示的に伝える
始点ホストは NAK を受信するとパケットを再送する
Ack, NAK を使ったヒューマンプロトコルは？
rdt2.0 における新メカニズム(rdt1.0を上回る):
誤り検出
受信側からのフィードバック：終点ホストから始点ホストへの制御
メッセージ(ACK, NAK)
Transport Layer 3-23
rdt2.0: FSM の記述
rdt_send(data)
snkpkt = make_pkt(data, checksum)
udt_send(sndpkt)
rdt_rcv(rcvpkt) &&
isNAK(rcvpkt)
Wait for
Wait for
call from
ACK or
udt_send(sndpkt)
above
NAK
rdt_rcv(rcvpkt) && isACK(rcvpkt)
L
始点ホスト
終点ホスト
rdt_rcv(rcvpkt) &&
corrupt(rcvpkt)
udt_send(NAK)
Wait for
call from
below
rdt_rcv(rcvpkt) &&
notcorrupt(rcvpkt)
extract(rcvpkt,data)
deliver_data(data)
udt_send(ACK)
Transport Layer 3-24
rdt2.0: 誤りがない場合
rdt_send(data)
sndpkt = make_pkt(data, checksum)
udt_send(sndpkt)
rdt_rcv(rcvpkt) &&
isNAK(rcvpkt)
Wait for
Wait for
call from
ACK or
udt_send(sndpkt)
above
NAK
rdt_rcv(rcvpkt) && isACK(rcvpkt)
L
rdt_rcv(rcvpkt) &&
corrupt(rcvpkt)
udt_send(NAK)
Wait for
call from
below
rdt_rcv(rcvpkt) &&
notcorrupt(rcvpkt)
extract(rcvpkt,data)
deliver_data(data)
udt_send(ACK)
Transport Layer 3-25
rdt2.0: 誤りがある場合
rdt_send(data)
sndpkt = make_pkt(data, checksum)
udt_send(sndpkt)
rdt_rcv(rcvpkt) &&
isNAK(rcvpkt)
Wait for
Wait for
call from
ACK or
udt_send(sndpkt)
above
NAK
rdt_rcv(rcvpkt) && isACK(rcvpkt)
L
rdt_rcv(rcvpkt) &&
corrupt(rcvpkt)
udt_send(NAK)
Wait for
call from
below
rdt_rcv(rcvpkt) &&
notcorrupt(rcvpkt)
extract(rcvpkt,data)
deliver_data(data)
udt_send(ACK)
Transport Layer 3-26
rdt2.0 の致命的欠陥！
ACK/NAK が壊れたらどう
する？
重複の取り扱い:
 始点ホストは終点ホストで何が
ーケンス番号を付与する
 もし，ACK/NAKが誤った場合
は，始点ホストは現在のパケッ
トを再送する
 終点ホストは（上位層に上げず
に）重複パケットを廃棄する
起こっているかわからない！
 単純に再送はできない：重複
受信の可能性あり
どするか？
 終点ホストからのACK/NAKに
対して始点ホストがACK/NAK
を返す．それが失われたらどう
するか？
 再送する，しかしこれは正しく
受信されたパケットの再送信を
引き起こす
 始点ホストは，各パケットにシ
stop and wait
始点ホストは，１パケットを
送信し，受信応答を待つ
Transport Layer 3-27
rdt2.1: 始点ホストでの ACK/NAKs 誤りの扱い
rdt_send(data)
sndpkt = make_pkt(0, data, checksum)
udt_send(sndpkt)
rdt_rcv(rcvpkt) &&
( corrupt(rcvpkt) ||
Wait
for
Wait for
isNAK(rcvpkt) )
ACK or
call 0 from
udt_send(sndpkt)
NAK 0
above
rdt_rcv(rcvpkt)
&& notcorrupt(rcvpkt)
&& isACK(rcvpkt)
rdt_rcv(rcvpkt)
&& notcorrupt(rcvpkt)
&& isACK(rcvpkt)
L
rdt_rcv(rcvpkt) &&
( corrupt(rcvpkt) ||
isNAK(rcvpkt) )
udt_send(sndpkt)
L
Wait for
ACK or
NAK 1
Wait for
call 1 from
above
rdt_send(data)
sndpkt = make_pkt(1, data, checksum)
udt_send(sndpkt)
Transport Layer 3-28
rdt2.1: 終点ホストでの ACK/NAKs 誤りの取り扱い
rdt_rcv(rcvpkt) && notcorrupt(rcvpkt)
&& has_seq0(rcvpkt)
rdt_rcv(rcvpkt) && (corrupt(rcvpkt)
extract(rcvpkt,data)
deliver_data(data)
sndpkt = make_pkt(ACK, chksum)
udt_send(sndpkt)
rdt_rcv(rcvpkt) && (corrupt(rcvpkt)
sndpkt = make_pkt(NAK, chksum)
udt_send(sndpkt)
rdt_rcv(rcvpkt) &&
not corrupt(rcvpkt) &&
has_seq1(rcvpkt)
sndpkt = make_pkt(ACK, chksum)
udt_send(sndpkt)
sndpkt = make_pkt(NAK, chksum)
udt_send(sndpkt)
Wait for
0 from
below
Wait for
1 from
below
rdt_rcv(rcvpkt) && notcorrupt(rcvpkt)
&& has_seq1(rcvpkt)
rdt_rcv(rcvpkt) &&
not corrupt(rcvpkt) &&
has_seq0(rcvpkt)
sndpkt = make_pkt(ACK, chksum)
udt_send(sndpkt)
extract(rcvpkt,data)
deliver_data(data)
sndpkt = make_pkt(ACK, chksum)
udt_send(sndpkt)
Transport Layer 3-29
rdt2.1: ディスカッション
始点ホスト:
 パケットにシーケンス番
号を付与
 二つのシーケンス番号
(0,1) で十分．なぜか？
 受信ACK/NAKに誤りが
あるかどうかチェックする
必要あり
 ２倍の状態

状態は，現在のパケットの
シーケンス番号が０か１か
を記憶しておかなければな
らない
終点ホスト:
 受信パケットが重複かど
うかをチェックしなければ
ならない

状態は，所望のパケットシ
ーケンス番号が0か1かを
示している
 注意：受信ホストは，最後
のACK/NAKが送信側に
正しく受信されたかどうか
を知ることはできない
Transport Layer 3-30
rdt2.2: NAK フリープロトコル
 ACKのみを使って rdt2.1 と同一機能を実現
 NAKの代わりに，終点ホストは最後に正しく受信されたパ
ケットに対する ACK を送信

終点ホストは，最後に正しく受信されたパケットのシーケンス番号を
ACKに陽に含まなければならない
 始点ホストは，重複ACKに対して NAK と同様に対処する：
パケットの再送
Transport Layer 3-31
rdt2.2: 始点ホスト，終点ホストの FSM（一部）
rdt_send(data)
sndpkt = make_pkt(0, data, checksum)
udt_send(sndpkt)
rdt_rcv(rcvpkt) &&
( corrupt(rcvpkt) ||
Wait for
Wait for
isACK(rcvpkt,1) )
ACK
call 0 from
0
udt_send(sndpkt)
above
sender FSM
fragment
rdt_rcv(rcvpkt) &&
(corrupt(rcvpkt) ||
has_seq1(rcvpkt))
udt_send(sndpkt)
Wait for
0 from
below
rdt_rcv(rcvpkt)
&& notcorrupt(rcvpkt)
&& isACK(rcvpkt,0)
receiver FSM
fragment
L
rdt_rcv(rcvpkt) && notcorrupt(rcvpkt)
&& has_seq1(rcvpkt)
extract(rcvpkt,data)
deliver_data(data)
sndpkt = make_pkt(ACK1, chksum)
udt_send(sndpkt)
Transport Layer 3-32
rdt3.0: 誤りと廃棄があるチャネル
新しい仮定: 下層チャネル
はパケット(data, ACK)を
損失する可能性がある
アプローチ: 始点ホストは，“適
切な” 時間 ACK を待つ
チェックサム，シーケンス
番号，ACK，再送が助けに
なるが，不十分
れば再送
 もしパケット（またはACK）が（廃
棄ではなく）たんに遅れたのなら:

疑問: ロスをどう扱うか？


始点ホストは，失われたデ
ータやACKを待って，再送
する
おいおい: 具合悪い？
 この時間内に ACK を受信しなけ

再送が重複するが，シーケン
ス番号で対処できる
終点ホストは，最後に受信し
たパケットのシーケンス番号
を記述しなければならない
 カウントダウンタイマーが必要

Transport Layer 3-33
rdt3.0: 始点ホスト
rdt_send(data)
sndpkt = make_pkt(0, data, checksum)
udt_send(sndpkt)
start_timer
rdt_rcv(rcvpkt)
L
rdt_rcv(rcvpkt)
&& notcorrupt(rcvpkt)
&& isACK(rcvpkt,1)
rdt_rcv(rcvpkt) &&
( corrupt(rcvpkt) ||
isACK(rcvpkt,0) )
timeout
udt_send(sndpkt)
start_timer
rdt_rcv(rcvpkt)
&& notcorrupt(rcvpkt)
&& isACK(rcvpkt,0)
stop_timer
stop_timer
timeout
udt_send(sndpkt)
start_timer
L
Wait
for
ACK0
Wait for
call 0from
above
L
rdt_rcv(rcvpkt) &&
( corrupt(rcvpkt) ||
isACK(rcvpkt,1) )
Wait
for
ACK1
Wait for
call 1 from
above
rdt_send(data)
rdt_rcv(rcvpkt)
L
sndpkt = make_pkt(1, data, checksum)
udt_send(sndpkt)
start_timer
Transport Layer 3-34
rdt3.0: 動作
Transport Layer 3-35
rdt3.0: 動作
Transport Layer 3-36
rdt3.0 の性能
 rdt3.0 は動作するが，性能は悪い
 例: 1 Gbps リンク，15 ms エンド間伝播遅延, 1KB パケット:
Ttransmit =
U



L (packet length in bits)
8kb/pkt
=
= 8 microsec
R (transmission rate, bps)
10**9 b/sec
sender
=
L/R
RTT + L / R
=
.008
30.008
= 0.00027
microsec
onds
U sender: 利用率 – 始点ホストが送信している時間割合
30ms ごとに 1KB パケット -> 1 Gbpsリンク上で33kB/sec スループット
ネットワークプロトコルが物理的資源の利用を制約している！
Transport Layer 3-37
rdt3.0: stop-and-wait の動作
sender
receiver
first packet bit transmitted, t = 0
last packet bit transmitted, t = L / R
first packet bit arrives
last packet bit arrives, send ACK
RTT
ACK arrives, send next
packet, t = RTT + L / R
U
sender
=
L/R
RTT + L / R
=
.008
30.008
= 0.00027
microsec
onds
Transport Layer 3-38
パイプラインプロトコル
パイプライン: 始点ホストは，ACK を待つことなく複数のパ
ケットを送信できる


シーケンス番号の範囲が増加する
始点ホスト／終点ホストにおけるバッファリング
 2種類の一般的なパイプラインプロトコル形式:
selective repeat（選択的再送）
go-Back-N,
Transport Layer 3-39
パイプライン: 利用率の改善
sender
receiver
first packet bit transmitted, t = 0
last bit transmitted, t = L / R
first packet bit arrives
last packet bit arrives, send ACK
last bit of 2nd packet arrives, send ACK
last bit of 3rd packet arrives, send ACK
RTT
ACK arrives, send next
packet, t = RTT + L / R
利用率は３倍に増加!
U
sender
=
3*L/R
RTT + L / R
=
.024
30.008
= 0.0008
microsecon
ds
Transport Layer 3-40
Go-Back-N
始点ホスト:
 パケットヘッダ内に k ビットのシーケンス番号
 最大 N までのウインドウ, 連続する ACK 身受信のパケット
 ACK(n): シーケンス番号 n までの（n を含む）連続する全パケットへ正常
受信を通知 – 累積
 重複 ACK をまるめこむ
 ACK未受信パケットに対するタイマー
 timeout(n): ウインドウ内の n 以上のシーケンス番号のパケットを再送
Transport Layer 3-41
GBN: 始点ホストの拡張
rdt_send(data)
L
base=1
nextseqnum=1
rdt_rcv(rcvpkt)
&& corrupt(rcvpkt)
if (nextseqnum < base+N) {
sndpkt[nextseqnum] = make_pkt(nextseqnum,data,chksum)
udt_send(sndpkt[nextseqnum])
if (base == nextseqnum){
start_timer
}
nextseqnum++
}
else
refuse_data(data)
timeout
start_timer
Wait
udt_send(sndpkt[base])
udt_send(sndpkt[base+1])
…
udt_send(sndpkt[nextseqnum-1])
rdt_rcv(rcvpkt) &&
notcorrupt(rcvpkt)
base = getacknum(rcvpkt)+1
If (base == nextseqnum)
stop_timer
else
start_timer
Transport Layer 3-42
GBN: 終点ホストの拡張 FSM
default
udt_send(sndpkt)
L
Wait
expectedseqnum=1
sndpkt =
make_pkt(expectedseqnum,ACK,chksum)
rdt_rcv(rcvpkt)
&& notcurrupt(rcvpkt)
&& hasseqnum(rcvpkt,expectedseqnum)
extract(rcvpkt,data)
deliver_data(data)
sndpkt = make_pkt(expectedseqnum,ACK,chksum)
udt_send(sndpkt)
expectedseqnum++
ACKのみ: 正しく受信したパケットに対して，順序どおりに正しく
受信された最大シーケンス番号に対してACK を送信


重複 ACK を生成するかもしれない
Expectedseqnum のみを記憶しておく必要あり
 順序誤りのパケット:
 廃棄-> 終点ホストのバッファリングなし！
 最大順序シーケンス番号をもつ ACK パケットの再送
Transport Layer 3-43
GBN
の動作
Transport Layer 3-44
選択的再送
 終点ホストは，正しく受信された個々のパケットに ACK
を送信する

必要に応じ，上位層に順序正しく配送するためにパケットをバ
ッファリング
 始点ホストは，ACK 未受信のパケットのみを再送
 ACK 未受信のパケットごとに始点ホストタイマー
 始点ホストウインドウ
 N 累積シーケンス番号
 送信済の ACK 未受信のパケットのシーケンス番号を制限
Transport Layer 3-45
選択的再送: 始点ホスト，終点ホストのウインドウ
Transport Layer 3-46
選択的再送
始点ホスト
上位層からのデータ :
 ウインドウ内で有効なシーケン
ス番号があれば，パケット送信
timeout(n):
 パケット nを再送し，タイマーを
リセット
ACK(n)（[sendbase,sendbase+N]間）:
 パケット n は受信されたものと
記録
 n がACK未受信の最小パケット
であったなら，ウインドウベース
を次の ACK 未受信パケットに
移動
終点ホスト
パケット n（[rcvbase, rcvbase+N-1] 内）
 ACK(n)を送信
 順序がおかしい: バッファリング
 順序どおり: （バッファ内に含まれる
順序どおりのパケットも含めて）上
位層に配信し，ウインドウをまだ未
受信のパケットに進める
パケット n（[rcvbase-N,rcvbase-1] 内）
 ACK(n)
その他:
 無視
Transport Layer 3-47
選択的再送の動作
Transport Layer 3-48
選択的再送:ジレンマ
例:
 シーケンス番号: 0, 1, 2, 3
 ウインドウサイズ = 3
 終点ホストは二つのシナリオ間
の差がわから
 (a) では，重複データを新規デー
タとして上位層に誤配送する
疑問: シーケンス番号の大きさとウ
インドウサイズの間の関係は？
ウインドウサイズ＜シーケンス番
号
課題：
いくらにセットするのが良いか？
Transport Layer 3-49
Chapter 3 内容
 3.1 トランスポート層サー
ビス
 3.2 多重化と逆多重化
 3.3 コネクションレス型ト
ランスポート: UDP
 3.4 高信頼データ転送の
原理
 3.5 コネクション指向型トラ
ンスポート: TCP




セグメント構造
高信頼データ転送
フロー制御
コネクション管理
 3.6 輻輳制御の原理
 3.7 TCP 輻輳制御
Transport Layer 3-50
TCP: 概要
RFCs: 793, 1122, 1323, 2018, 2581
 ポイント・ツー・ポイント:
 １始点ホスト，１終点ホスト
 全二重データ:

 高信頼，順序保証，バイト

ストリーム：

メッセージの境界なし
 パイプライン:
 TCP 輻輳制御，フロー制御
によりウインドウ設定

同一コネクション上での双
方向データフロー
MSS: maximum segment
size，最大セグメントサイズ
 コネクション指向型:

送信＆受信バッファ
データ交換の前に，ハンド
シェイク (制御メッセージ交
換) により，始点ホスト，終
点ホストの状態を設定
 フロー制御:
socket
door
application
writes data
application
reads data
TCP
send buffer
TCP
receive buffer
socket
door

始点ホストが終点ホストを
過負荷にすることはない
segment
Transport Layer 3-51
TCP セグメント構造
32 bits
URG: 緊急データ
(通常未使用)
ACK: ACK 番号
有効
PSH: 上位層に直ちに渡す
(通常未使用)
RST, SYN, FIN:
コネクション設定
(セットアップ，
終了コマンド)
Internet
チェックサム
(UDPと同様)
source port #
dest port #
sequence number
acknowledgement number
head not
UA P R S F
len used
checksum
Receive window
Urg data pnter
Options (variable length)
データのバイト
単位でのカウン
ト(セグメントで
はない!)
終点ホストが
次に受信を
望むバイト番
号
application
data
(variable length)
Transport Layer 3-52
TCP シーケンス番号とACK
シーケンス番号:
 セグメントデータの開
始バイトのバイトスト
リームにおけるバイト
単位の通し番号
ACK:
 次に受信すべきバイ
トのシーケンス番号
 累積 ACK
質問: 終点ホストは，順序逆
転して到着したセグメント
をどのように扱うのか
 答え: TCP RFCは規
定せず，実装者任せ
Host A
User
types
‘C’
Host B
host ACKs
receipt of
‘C’, echoes
back ‘C’
host ACKs
receipt
of echoed
‘C’
simple telnet scenario
time
Transport Layer 3-53
TCP ラウンドトリップ時間とタイムアウト
疑問: TCPはどのよう
にタイムアウト時間
を設定するのか？
 RTTより長い時間
 しかし，RTTは可変
 短すぎると…: はやま
ったタイムアウト
 不要な再送
 長すぎると…: セグメン
トロスに対する応答が
遅い
疑問： RTTをどのように見積もる
か?
 SampleRTT: セグメント送信から
ACK受信までの時間を測定
 再送は無視
 SampleRTT は変動するので，より
安定した値が欲しい

最近のいくつかの測定結果の平
均，最新の RTT ではない
Transport Layer 3-54
TCP ラウンドトリップ時間とタイムアウト
EstimatedRTT = (1- )*EstimatedRTT + *SampleRTT
 指数加重移動平均
 過去のサンプルの影響は指数的に減少
 典型的な値:  = 0.125
Transport Layer 3-55
RTT 推定の例:
RTT: gaia.cs.umass.edu to fantasia.eurecom.fr
350
RTT (milliseconds)
300
250
200
150
100
1
8
15
22
29
36
43
50
57
64
71
78
85
92
99
106
time (seconnds)
SampleRTT
Estimated RTT
Transport Layer 3-56
TCP ラウンドトリップ時間とタイムアウト
タイムアウトの設定
 EstimtedRTT ＋ “安全マージン”

EstimatedRTTの変動大 -> より大きな安全マージン
 SampleRTT がEstimatedRTTからどの程度変動するかの一次推定:
DevRTT = (1-)*DevRTT +
*|SampleRTT-EstimatedRTT|
(推奨値,  = 0.25)
タイムアウト値の設定:
TimeoutInterval = EstimatedRTT + 4*DevRTT
Transport Layer 3-57
Chapter 3 内容
 3.1 トランスポート層サー
ビス
 3.2 多重化と逆多重化
 3.3 コネクションレス型ト
ランスポート: UDP
 3.4 高信頼データ転送の
原理
 3.5 コネクション指向型トラ
ンスポート: TCP




セグメント構造
高信頼データ転送
フロー制御
コネクション管理
 3.6 輻輳制御の原理
 3.7 TCP 輻輳制御
Transport Layer 3-58
TCP 始点ホストのイベント:
アプリからのデータ受取り:
タイムアウト:
 シーケンス番号つきセグ
 タイムアウトを引き起こし
メントの生成
たセグメントの再送
 タイマ再起動
 シーケンス番号は，セグ
メントの1バイト目のバイト Ack受信:
ストリーム値
 ACKがセグメントに対して
 タイマ未動作ならタイマ起
初めてのものなら
動 (ACK未受信の最も古
 どこまで ACK されたのか
いセグメントに対するタイ
を更新
マ）
 もし未決着のセグメントが
あれば，タイマを起動
 タイムアウト間隔:
TimeOutInterval
Transport Layer 3-59
NextSeqNum = InitialSeqNum
SendBase = InitialSeqNum
loop (forever) {
switch(event)
event: data received from application above
create TCP segment with sequence number NextSeqNum
if (timer currently not running)
start timer
pass segment to IP
NextSeqNum = NextSeqNum + length(data)
event: timer timeout
retransmit not-yet-acknowledged segment with
smallest sequence number
start timer
event: ACK received, with ACK field value of y
if (y > SendBase) {
SendBase = y
if (there are currently not-yet-acknowledged segments)
start timer
}
} /* end of loop forever */
TCP
送信ホスト
(単純化)
コメント:
• SendBase-1: 最も
最近に累積 ACK さ
れたバイト
例:
• SendBase-1 = 71;
y= 73の場合，終点
ホストは73以上を望
んでおり，y >
SendBaseであるか
ら，新規データは
ACK される
Transport Layer 3-60
TCP: 再送シナリオ
Host A
X
loss
Sendbase
= 100
SendBase
= 120
SendBase
= 100
time
SendBase
= 120
ACK損失の場合
Host B
Seq=92 timeout
Host B
Seq=92 timeout
timeout
Host A
time
早まったタイムアウトの場合
Transport Layer 3-61
TCP 再送シナリオ (つづき)
timeout
Host A
Host B
X
loss
SendBase
= 120
time
累積ACKの場合
Transport Layer 3-62
TCP ACK 生成
[RFC 1122, RFC 2581]
終点ホストにおけるイベント
終点ホストにおけるアクション
予定したシーケンス番号のセグメント
到着，このシーケンス番号のセグメン
トまでの全データはACK済み
ACK を遅らせる，正しい順序の次のセ
グメントの到着を 500ms 待つ，この間
に到着がない場合，当然 ACK を送信
予定したシーケンス番号のセグメント
の到着，ACK の送信待ち状態のセ
グメントが存在する
２つのセグメントに対する累積 ACK を
直ちに送信
予定したシーケンス番号より大きい
値のセグメントの到着，データ欠損の
検出
予定するシーケンス番号（欠損部の小さ
い側）を示す重複ACKを直ちに送信
受信データの欠損部を部分的または
完全に埋めるセグメントの受信
そのセグメントが欠損部の番号の小さい
側から連続している場合は，直ちに
ACK を送信
Transport Layer 3-63
高速再送
 タイムアウト間隔は，相対
的に長い：

損失パケット再送前の長期
遅延
 重複ACKによるセグメント
ロスの検出

始点ホストは，しばしば連
続してセグメントを送信す
る

セグメントが廃棄された場
合，重複 ACK が送信され
る傾向がある
 始点ホストが同一データに
対する ACK を３つ受信し
た場合，ACKが対象とする
セグメントが失われた後の
セグメントに対するものと
推定する:

高速再送：タイマが切れる前
にセグメントを再送
Transport Layer 3-64
高速再送アルゴリズム:
event: ACK received, with ACK field value of y
if (y > SendBase) {
SendBase = y
if (there are currently not-yet-acknowledged segments)
start timer
}
else {
increment count of dup ACKs received for y
if (count of dup ACKs received for y = 3) {
resend segment with sequence number y
}
既に ACK を受信したセグメント
に対する重複 ACK
高速再送
Transport Layer 3-65
Chapter 3 内容
 3.1 トランスポート層サー
ビス
 3.2 多重化と逆多重化
 3.3 コネクションレス型ト
ランスポート: UDP
 3.4 高信頼データ転送の
原理
 3.5 コネクション指向型トラ
ンスポート: TCP




セグメント構造
高信頼データ転送
フロー制御
コネクション管理
 3.6 輻輳制御の原理
 3.7 TCP 輻輳制御
Transport Layer 3-66
TCP フロー制御
 TCPコネクションの終点ホ
ストは受信バッファをもつ：
フロー制御
始点ホストが速く送信しす
ぎることにより終点ホストの
バッファをオーバフローさせ
ることがないようにする
 スピード制御サービス：ア
プリケーション読み出し速
度に送信速度を調整する
 アプリプロセスは，バッフ
ァからの読み出しに遅れ
るかもしれない
Transport Layer 3-67
TCP フロー制御: どのように動作するか
 終点ホストは，セグメント
(TCP 終点ホストは，ことなる順
序で到着したセグメントを廃
棄すると仮定)
 バッファ内の空きスペース
内にRcvWindow 値を含
むことで，空きスペースを
通知
 始点ホストは，ACK未受
信のデータをRcvWindow
に制限

受信バッファがオーバフロ
ーしないことを保証
= RcvWindow
= RcvBuffer-[LastByteRcvd LastByteRead]
Transport Layer 3-68
Chapter 3 内容
 3.1 トランスポート層サー
ビス
 3.2 多重化と逆多重化
 3.3 コネクションレス型ト
ランスポート: UDP
 3.4 高信頼データ転送の
原理
 3.5 コネクション指向型トラ
ンスポート: TCP




セグメント構造
高信頼データ転送
フロー制御
コネクション管理
 3.6 輻輳制御の原理
 3.7 TCP 輻輳制御
Transport Layer 3-69
TCP コネクション管理
Recall: TCP 始点ホストと終点ホ
ストは，データセグメント交換の
前にコネクションを設定する
 TCP 変数の初期化:
 シーケンス番号
バッファ，フロー制御情報（
例，受信ウインドウ）
 クライアント：コネクション開始
側

Socket clientSocket = new
Socket("hostname","port
number");

ｻｰﾊﾞ: クライアントによってコン
タクトをうける
Socket connectionSocket =
welcomeSocket.accept();
スリーウェイハンドシェイク:
Step 1: クライアントホストは，TCP
SYN セグメントをサーバに送信
 初期シーケンス番号を記述
 データなし
Step 2: サーバホストは，SYNを受
信すると，SYNACKセグメントで応答

サーバはバッファを割当る
サーバの初期シーケンス番号を
記述
Step 3: クライアントは，SYNACKを受
信すると，ACKセグメントで応答する
．このセグメントはデータを含みうる

Transport Layer 3-70
TCP コネクション管理(つづき)
client
コネクションの終了:
client closes socket:
clientSocket.close();
close
Step 1: クライアントエンドシス
close
FINを受信すると，ACKで応
答，FINを送信
timed wait
テムは，TCP FIN 制御セグメ
ントをサーバに送信
Step 2: serverサーバは，
server
closed
Transport Layer 3-71
TCP コネクション管理(つづき)
Step 3: client はFINを受信す
ると，ACKで応答

client
server
closing
タイムアウトに入る – 受信
した FIN に対して ACK で
応答するため
closing
Step 4: serverはACKを受信
注意: わずかな変更で，同時に
timed wait
すると，コネクションをクローズ
FIN （双方が同時にコネクショ
ンを終了する場合）を行う場合
closed
を取り扱うことができる
closed
Transport Layer 3-72
TCP コネクション管理(つづき)
TCP server
lifecycle
TCP client
lifecycle
Transport Layer 3-73
Chapter 3 内容
 3.1 トランスポート層サー
ビス
 3.2 多重化と逆多重化
 3.3 コネクションレス型ト
ランスポート: UDP
 3.4 高信頼データ転送の
原理
 3.5 コネクション指向型トラ
ンスポート: TCP




セグメント構造
高信頼データ転送
フロー制御
コネクション管理
 3.6 輻輳制御の原理
 3.7 TCP 輻輳制御
Transport Layer 3-74
輻輳制御の原理
輻輳:
 簡単にいうと: “多くのソースが大量のデータをネットワークが
扱うことができる速度より速く送信している”
 フロー制御とは異なる！
 現象:
 パケット廃棄 (ルータにおけるバッファオーバーフロー)
 遅延大 (ルータバッファにおける待ち)
 非常に重要な問題のトップ１０！
Transport Layer 3-75
輻輳の原因/コスト：シナリオ１
Host A
 始点ホスト２，終点
lout
lin : original data
ホスト２
 ルータ１，無限バッ
Host B
unlimited shared
output link buffers
ファ
 再送なし
 輻輳時は遅延大
 最大スループット
達成可能
Transport Layer 3-76
輻輳の原因/コスト：シナリオ２
 ルータ１，有限バッファ
 始点ホストは，ロスしたパケットを再送
Host A
Host B
lin : original
data
l'in : original data, plus
retransmitted data
lout
finite shared output
link buffers
Transport Layer 3-77
輻輳の原因/コスト：シナリオ２
= l
(goodput)が成立
out
in
 ロス発生時のみの“完璧な”再送： l > l
out
in
 （廃棄されていなくとも）遅延大のパケットの再送は，同じ
 常に
l
完璧な再送の場合よりも）
l
ルータの空きバッファ検出可能な場合
l
を増大させる
lout
に対し，（
in
in
パケットロスを正確に検出可能な場合
タイムアウト値が小さくパケットロス
を正確に検出できない場合
輻輳のコスト:
 ある “goodput” に対してより多くの再送
 不必要な再送：リンクは同一パケットの複数のコピーを伝送
Transport Layer 3-78
輻輳の原因/コスト：シナリオ３
質問: l と l
が大きく
in
in
なると，何が起こるか？
 始点ホスト４
 マルチホップパス
 タイムアウト/再送
Host A
lin : original data
lout
l'in : original data, plus
retransmitted data
finite shared output
link buffers
Host B
Transport Layer 3-79
輻輳の原因/コスト：シナリオ３
l
H
o
s
t
A
o
u
t
H
o
s
t
B
輻輳の別のコスト:
 パケット廃棄が発生した場合，そのパケットのために利用
された上流リンクの帯域は浪費されたことになる！
Transport Layer 3-80
輻輳制御へのアプローチ
輻輳制御のための２つの基本的アプローチ:
エンド間輻輳制御:
 ネットワークからの陽なフィー
ドバックなし
 輻輳は，エンドシステムが観測
する遅延やロスから推定され
る
 TCP によってとられるアプロー
チ
ネットワーク支援型輻輳制
御:
 ルータがエンドシステムにフィ
ードバックを提供
 輻輳かどうかを示す１ビット
(SNA, DECbit, TCP/IP
ECN, ATM)

始点ホストが送信可能な
速度
Transport Layer 3-81
ケーススタディ: ATM ABR 輻輳制御
ABR: available bit rate:
 エラスティックサービス（
elastic service）
 始点ホストのパスが低負荷
なら：

送信ホストは利用可能な
帯域を使用すべき
 始点ホストのパスが輻輳して
いるなら：

始点ホストは，最小保証
速度まで速度を落とすべ
き
資源管理 (RM: resource
management)セル:
 始点ホストによって送信され，デー
タセルの間に分散して挿入される
 RMセル内のビットはスイッチによ
って設定される(ネットワーク支援
型)
 NI bit: レート非増加（中程度
の輻輳）
 CI bit: 輻輳通知
 RMセルは，これらのビットを保持し
たまま，終点ホストによって始点ホ
ストに送り返される
Transport Layer 3-82
ケーススタディ: ATM ABR 輻輳制御
 RMセル内の２バイト明示的レート(ER: explicit rate)フィールド
 輻輳スイッチは，セル内のER値を下げる
 パス上の最小対応レートに送信レートを適応できる
 データセル内のEFCIビット: 輻輳スイッチ内で1にセットされる
RMセルにEFCIビットがセットされている場合，終点ホストは，
次にくる RMセル内のCIビットに1をセットして送り返す
Transport Layer 3-83
Chapter 3 内容
 3.1 トランスポート層サー
ビス
 3.2 多重化と逆多重化
 3.3 コネクションレス型ト
ランスポート: UDP
 3.4 高信頼データ転送の
原理
 3.5 コネクション指向型トラ
ンスポート: TCP




セグメント構造
高信頼データ転送
フロー制御
コネクション管理
 3.6 輻輳制御の原理
 3.7 TCP 輻輳制御
Transport Layer 3-84
TCP 輻輳制御
 エンド間制御 (ネットワーク支援な
し)
 始点ホストは，伝送を制限:
LastByteSent-LastByteAcked
 CongWin
 大雑把に言うと
rate =
CongWin
Bytes/sec
RTT
 CongWin は，知覚されたネットワ
ーク輻輳に応じて，動的に制御され
る
始点ホストはどうやって輻輳
を知覚するのか?
 ロスイベント = タイムアウ
トまたは３重複 ACK
 TCP 始点ホストは，ロス
イベントの後，レート
(CongWin) を減少させる
３つのメカニズム:



AIMD（加算増加，乗算減
少）
スロースタート
タイムアウトへの対応
Transport Layer 3-85
TCP AIMD
乗算的減少: ロスイベント認
識後，CongWin を半減
させる
加算的増加: ロスイベントが
ない場合，RTTごとに
CongWin を 1 MSS だ
け増加：プロービング
congestion
window
24 Kbytes
16 Kbytes
8 Kbytes
time
Long-lived TCP connection
Transport Layer 3-86
TCP スロースタート
 コネクション開始時，
CongWin = 1 MSS


例: MSS = 500 bytes &
RTT = 200 msec
初期レート = 20 kbps
 コネクション開始時は，最
初のロスイベントまで，レー
トを指数関数的に増加させ
ることが望ましい
 利用可能帯域はおそらく
MSS/RTT より十分大きい

相当なレートまで，すばやく
上昇させることが望ましい
CongWin=1MSSから線形増加させた場合，
20Kbpsに達するのにどれだけ時間がかかるか。
また，指数増加させた場合どれだけの時間がかかるか。
Transport Layer 3-87
TCP スロースタート (つづき)
 コネクション開始時，最初


RTTごとに CongWin を倍
増
ACK受信ごとに CongWin
をインクリメント
Host B
RTT
のロスイベントまでレート
を指数関数的に増加：
Host A
 まとめると…: 初期レート
は小さいが，指数関数的
に増加
time
Transport Layer 3-88
改善（セグメントロスが起こったときの対処）
フィロソフィー:
 ３つの重複ACK受信後：

CongWin を半減
その後，ウインドウを線形
増加
 しかし，タイムアウトイベント
後は：
 CongWin を1 MSSに設定
 その後，window を指数関
数的に増加


• ３つの重複 ACKは，セグメ
ントをいくらかは配送できる
ということを示している
• ３つの重複 ACK 以前にタ
イムアウトは，“より強い警
告”である
閾値に到達後，線形的に
増加
Transport Layer 3-89
改善 (つづき)
14
congestion window size
(segments)
質問: いつ指数増加から
線形増加に切り替え
るべきか？
答え: CongWin がタイ
ムアウト以前の半分
の値に到達したとき
実装:
 可変閾値
 ロスイベント時，閾値は，ロス
12
10
8
6
4
threshold
2
0
1
TCP
Tahoe
TCP
Reno
2 3
6 7
4 5
8 9 10 11 12 13 14 15
Transmission round
Series1
Series2
イベント直前の CongWin の半
分に設定
Transport Layer 3-90
まとめ: TCP 輻輳制御
 CongWin が Threshold 以下のとき，始点ホストはス
ロースタートフェーズに入り，ウインドウを指数的に増加
させる
 CongWin が Threshold を超えると，始点ホストは，
輻輳回避フェーズに入り，ウインドウを線形的に増加させ
る
 ３重ACK受信後，Threshold を CongWin/2 に設定
し，CongWin を閾値に設定する
 タイムアウト発生後は，閾値を CongWin/2 に設定し，
CongWin を 1 MSS に設定する
Transport Layer 3-91
TCP 公平性
公平性の目的: K本のTCPセッションが帯域 R の同一ボト
ルネックリンクを共有している場合，各セッションは平均
R/Kの速度を持つべきである
TCP connection 1
TCP
connection 2
bottleneck
router
capacity R
Transport Layer 3-92
TCP はなぜ公平化？
２本の競合セッション:
 加算増加は，スループット増加時，傾き１の増加を与える
 乗算減少は，スループットを比例的に減少させる
R
等しい帯域分割
廃棄: ウインドウを半減
輻輳回避: 加算増加
廃棄: ウインドウ半減
輻輳回避: 加算増加
Connection 1 throughput R
Transport Layer 3-93
公平性 (つづき)
公平性と UDP
 マルチメディアアプリは
TCP を使わないことが多
い

輻輳制御による速度調整
を望まない
 代わりに UDP を使用:

一定レートで音声／映像を
送信，パケット廃棄への耐
性
 研究テーマ: TCP
friendly
公平性と並列TCPコネクション
 アプリがホスト間で複数コネク
ションをはることを妨げるもの
はない
 Webブラウザはこれを実行
 例: レート R のリンクが9コネ
クションをサポート：


新規アプリが1TCPを設定すれ
ば，レート R/10 を得る
新規アプリが 9 TCPを設定すれ
ば，レート R/2 を得る
Transport Layer 3-94
遅延モデル
Q: リクエスト送信後，Webサー
バからオブジェクトを受信す
るのにどのくらいの時間を要
するか？
輻輳を無視すると，遅延は以下
に影響される:
記号と仮定:
 クライアント・サーバ間は帯域
R の１リンク
 S: MSS (bits)
 O: オブジェクトサイズ (bits)
 再送なし (廃棄なし，誤りなし)
ウインドウサイズ:
 TCP コネクション設定
 最初の仮定: 固定輻輳ウイン
 データ伝送遅延
ドウ，W セグメント
 その後，スロースタートをモデ
ル化した可変ウインドウに
 スロースタート
Transport Layer 3-95
固定輻輳ウインドウ (1)
ケース１:
WS/R > RTT + S/R: ウインドウ
内のデータを全て送信する前
にウインドウ内の第１セグメ
ントに対する ACK が返ってく
る
遅延 = 2RTT + O/R
Transport Layer 3-96
固定輻輳ウインドウ (2)
ケース２:
 WS/R < RTT + S/R: ウイン
ドウ内のデータを送信した後
，ACKが返ってくるのを待つ
遅延 = 2RTT + O/R
+ (K-1)[S/R + RTT - WS/R]
Transport Layer 3-97
TCP 遅延モデル: スロースタート (1)
ウインドウがスロースタートに従って増加すると仮定
オブジェクト転送遅延が以下の式で与えられることを示す:
Latency  2 RTT 
O
S
S

 P  RTT    (2 P  1)
R
R
R

ここで，P はサーバで TCP がアイドルとなる回数であり，
P  min{Q, K  1}
- ここで，Q は，オブジェクトが無限サイズとしたときに，サーバがアイドルとなる回数
- K は，オブジェクト全てを送信するのに必要なウインドウ回数
Transport Layer 3-98
TCP 遅延モデル: スロースタート (2)
遅延要素:
• 2 RTT：コネクション設定
と要求に対するもの
• O/R：オブジェクト転送の
ため
• スロースタートによりサー
バがアイドルとなる時間
initiate TCP
connection
request
object
first window
= S/R
RTT
サーバーアイドル回数:
P = min{K-1,Q}
例:
• O/S = 15 セグメント
• K = 4 ウィンドウ
•Q=2
• P = min{K-1,Q} = 2
サーバは P=2 回アイドル
second window
= 2S/R
third window
= 4S/R
fourth window
= 8S/R
complete
transmission
object
delivered
time at
client
time at
server
Transport Layer 3-99
TCP 遅延モデル (3)
S
 RTT  サーバがセグメント送
R
信開始してから ACK を受信するまでの時間
S
 k番目のウインドウを
R
送信するのに
要する時間
2 k 1
initiate TCP
connection
request
object
first window
= S/R

S
k 1 S 

RTT

2
 k番目のウインドウ後の
 R

R
ア
イドル時間
RTT
second window
= 2S/R
third window
= 4S/R
P
O
delay   2 RTT   idleTim ep
R
p 1
P
O
S
S
  2 RTT   [  RTT  2 k 1 ]
R
R
k 1 R
O
S
S
  2 RTT  P[ RTT  ]  (2 P  1)
R
R
R
fourth window
= 8S/R
complete
transmission
object
delivered
time at
client
time at
server
Transport Layer 3-100
TCP Delay Modeling (4)
K = オブジェクト全てを送信するのに必要なウインドウ回数
K をどのように計算するか？
K  min{k : 20 S  21 S    2 k 1 S  O}
 min{k : 20  21    2 k 1  O / S}
O
 min{k : 2  1  }
S
O
 min{k : k  log2 (  1)}
S
O


 log2 (  1)
S


k
無限サイズのオブジェクトに対してサーバがアイドルとなる回数 Q の計算も同
様（テキストの課題）
Transport Layer 3-101
HTTP モデリング
 Web ページが以下から構成されると仮定:


1 基本 HTML ページ (サイズ O bits)
M 個の画像 (各サイズ O bits)
 非継続型 HTTP:


M+1 TCP コネクションが順番に設定される
応答時間 = (M+1)O/R + (M+1)2RTT + アイドル時間の総和
 継続型 HTTP:



2 RTT ：ベース HTML ファイルを要求，受信するための時間
1 RTT ：M画像を要求，受信するための時間
応答時間 = (M+1)O/R + 3RTT + アイドル時間の総和
 非継続型 HTTP （X 本の並列コネクション）




M/X は整数と仮定
1 TCP はコネクション用
M/X セットの画像用並列コネクション
応答時間 = (M+1)O/R + (M/X + 1)2RTT + アイドル時間の総和
Transport Layer 3-102
HTTP 応答時間 (秒単位)
RTT = 100 msec, O = 5 Kbytes, M=10 and X=5
20
18
16
14
12
10
8
6
4
2
0
non-persistent
persistent
parallel nonpersistent
28
100
1
10
Kbps Kbps Mbps Mbps
狭帯域に対しては，伝送時間がコネクション，応答時間において主要因
継続型コネクションは，並列コネクションに対して若干の改善を与えるのみ
Transport Layer 3-103
HTTP 応答時間 (秒単位)
RTT =1 sec, O = 5 Kbytes, M=10 and X=5
70
60
50
non-persistent
40
persistent
30
20
parallel nonpersistent
10
0
28
100
1
10
Kbps Kbps Mbps Mbps
RTTが大きくなると，TCP設定，スロースタート遅延が応答時間において大きな要因になる．
継続型コネクションは，特に帯域遅延積大のネットワークにおいて，重大な改善をもたらす．
Transport Layer 3-104
Chapter 3: まとめ
 トランスポート層サービスの背
後にある原理:
 多重化，逆多重化
 高信頼性データ転送
 フロー制御
 輻輳制御
 インターネットにおける事例と
実装
 UDP
 TCP
Next:
 ネットワークのエッジ（
アプリ層，トランスポ
ート層）を離れて
 ネットワークのコアに
Transport Layer 3-105

Download Report