( )

(1)

修士論文

TCP

におけるコネクション分割管理による

転送効率向上に関する研究

矢倉基裕

2000年2月14日奈良先端科学技術大学院大学情報科学研究科情報システム学専攻

(2)

本論文は奈良先端科学技術大学院大学情報科学研究科に修士(工学) 授与の要件として提出した修士論文である。矢倉基裕審査委員：山本平一教授横矢直和教授山口英助教授

(3)

TCP

におけるコネクション分割管理による

転送効率向上に関する研究

3

矢倉基裕

内容梗概インターネットの急速な普及によるトラフィックの増加を支えるため，インターネットの広帯域化が進んでいる．一方，広帯域化にともなってトラフィックも増加している．そのため輻輳の発生を完全に解消することは難しい．また，インターネットのアプリケーションの多くが用いている TCPは，広帯域下で輻輳が発生した場合，利用可能帯域に応じた十分なスループットを得ることは難しい．本研究では，インターネット上での大容量コンテンツの高速転送を効率的に行うことを目的とし，TCP の1コネクションを分割管理して輻輳制御することにより，1コネクションあたりの輻輳制御情報を従来より多く保持し，スループットを向上させる改良手法を提案する．本提案手法の特徴は，パケットロス発生時において，従来の輻輳制御アルゴリズムと比較して，より適切にネットワークの状態を反映した振る舞いを示す点にある．また，サーバ側の TCPの入れ替えだけで利用でき，クライアントは従来のままでよい．本研究においては，本提案手法をUNIXカーネルに対し実装し，実測により評価を行った．その結果，パケットロスのない場合には従来方式と同程度のスループットを実現しつつ，パケットロスのある場合においては従来方式と比べ明確なスループットの向上が確認された．キーワード TCP,輻輳制御, SACK,帯域幅遅延積,サブチャネル 3 奈良先端科学技術大学院大学情報科学研究科情報システム学専攻修士論文, NAIST-IS-MT9851115,2000年2月14日.

(4)

Split-and-Control Concept 3

Motohiro Yakura

Abstract

Since the Internethas come intowide use, the trac onthe Internethas been increasing alarmingly in recent years. Although the bandwidthof the Internetis becoming larger and larger, the trac in the Internet consumes the bandwidth. So itis verydicult toeliminate congestion completely from the Internet. TCP is the transport layer proto col used by the most of applications. TCP works poorly inthe high bandwidth networkswhere packetlossoccurs.

In this paper,our goal is totransfer largedata eectivelyonthe Internet. We proposea new metho d of congestion control which splits aTCP connection into sub-connections and apply existing TCP algorithms to each sub-connection. By splitting a TCP connection, TCP can grasp the network conditions better and the congestion control mechanism works more eciently in data transfer than existing methods. All we need to do is that we modify a TCP stack of server machines.

We implemented and evaluated proposed metho d. We observedimprovement of thoughput on the network environment wherepacket lossoccurs.

Keywords:

TCP,congestion control,SACK, bandwidth-delay product, sub-chanel 3

Master's Thesis, Department of Information Systems, Graduate Scho ol of Information Science, NaraInstituteofScienceandTechnology,NAIST-IS-MT9851115, February14,2000.

(5)

1. はじめに 1 2. 背景 4 2.1 TCP : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 4 2.1.1 TCP の概要 : : : : : : : : : : : : : : : : : : : : : : : : : : 4 2.1.2 TCP コネクション : : : : : : : : : : : : : : : : : : : : : : 5 2.1.3 TCP のフォーマット : : : : : : : : : : : : : : : : : : : : : 7 2.1.4 TCP の信頼性: : : : : : : : : : : : : : : : : : : : : : : : : 9 2.1.5 TCP のフロー制御 : : : : : : : : : : : : : : : : : : : : : : 11 2.1.6 TCP の輻輳制御 : : : : : : : : : : : : : : : : : : : : : : : 12 2.1.7 TCP の再送制御 : : : : : : : : : : : : : : : : : : : : : : : 15 2.2 TCP Reno : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 19 2.3 SACK : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 19 2.4 TCP とセグメントロス: : : : : : : : : : : : : : : : : : : : : : : : 23 2.4.1 セグメントロスの影響 : : : : : : : : : : : : : : : : : : : : 23 2.4.2 本研究の着眼点 : : : : : : : : : : : : : : : : : : : : : : : : 24 3. 関連研究 26 3.1 輻輳制御の改良 : : : : : : : : : : : : : : : : : : : : : : : : : : : : 26 3.2 再送制御の改良 : : : : : : : : : : : : : : : : : : : : : : : : : : : : 26 3.3 SACK 情報の有効利用 : : : : : : : : : : : : : : : : : : : : : : : : 27 3.4 統合的輻輳制御 : : : : : : : : : : : : : : : : : : : : : : : : : : : : 27 3.5 本研究の着眼点との関わり : : : : : : : : : : : : : : : : : : : : : : 28 4. 提案するコネクション分割管理方式 29 4.1 コネクション分割管理方式の概要 : : : : : : : : : : : : : : : : : : 29 4.2 コネクション分割管理方式 : : : : : : : : : : : : : : : : : : : : : : 30 4.2.1 コネクション分割管理方式の定義 : : : : : : : : : : : : : : 30 4.2.2 サブコネクションの定義 : : : : : : : : : : : : : : : : : : : 30

(6)

4.2.3 多重度の定義 : : : : : : : : : : : : : : : : : : : : : : : : : 31 4.2.4 NACK の定義 : : : : : : : : : : : : : : : : : : : : : : : : : 31 4.3 コネクション分割管理方式のデータ構造 : : : : : : : : : : : : : : 31 4.3.1 輻輳制御情報の定義 : : : : : : : : : : : : : : : : : : : : : 31 4.3.2 送信リストの定義 : : : : : : : : : : : : : : : : : : : : : : : 33 4.3.3 送信側 SACKedブロックの定義: : : : : : : : : : : : : : : 34 4.3.4 サブコネクションと送信バッファサイズの関係 : : : : : : 34 4.4 コネクション分割管理方式の動作 : : : : : : : : : : : : : : : : : : 35 4.4.1 サブコネクションによるセグメント送信 : : : : : : : : : : 35 4.4.2 サブコネクション数の動的増減 : : : : : : : : : : : : : : : 35 4.4.3 セグメント送出手順 : : : : : : : : : : : : : : : : : : : : : 35 4.4.4 ACK 受信時の処理 : : : : : : : : : : : : : : : : : : : : : : 36 4.4.5 SACK 受信時の処理 : : : : : : : : : : : : : : : : : : : : : 36 4.4.6 FastRetransmit : : : : : : : : : : : : : : : : : : : : : : : : 37 4.4.7 FastRecovery : : : : : : : : : : : : : : : : : : : : : : : : : 38 4.4.8 FastRecoveryの終了判定と終了処理 : : : : : : : : : : : : 39 4.4.9 再送タイムアウト時 : : : : : : : : : : : : : : : : : : : : : 39 4.5 コネクション分割管理方式のアルゴリズムの意図 : : : : : : : : : 40 4.5.1 コネクション分割管理の意図 : : : : : : : : : : : : : : : : 40 4.5.2 サブコネクション数の動的増減 : : : : : : : : : : : : : : : 41 4.5.3 送信リストについて : : : : : : : : : : : : : : : : : : : : : 41 4.5.4 再送対象の決定について : : : : : : : : : : : : : : : : : : : 41 4.5.5 再送について : : : : : : : : : : : : : : : : : : : : : : : : : 42 4.5.6 FastRecovery時の振る舞いについて : : : : : : : : : : : : 43 4.5.7 FACK 的アルゴリズムについて : : : : : : : : : : : : : : : 44 4.6 コネクション分割管理方式の実装 : : : : : : : : : : : : : : : : : : 44 4.6.1 従来の TCP の動作と実装 : : : : : : : : : : : : : : : : : : 45 4.6.2 コネクション分割管理方式の実装の動作の概要 : : : : : : 45 4.6.3 データ構造 : : : : : : : : : : : : : : : : : : : : : : : : : : 49

(7)

4.6.4 主要な関数について : : : : : : : : : : : : : : : : : : : : : 53 5. 評価 55 5.1 実験1 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 55 5.1.1 概要 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 55 5.1.2 目的 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 55 5.1.3 実験環境 : : : : : : : : : : : : : : : : : : : : : : : : : : : : 56 5.1.4 方法 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 56 5.2 実験1の結果 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 59 5.2.1 転送時間 : : : : : : : : : : : : : : : : : : : : : : : : : : : : 59 5.2.2 FastRetransmit 数と再送タイムアウト数 : : : : : : : : : 63 5.2.3 再送率 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 65 5.2.4 サブコネクションあたりの転送量の変動係数 : : : : : : : : 67 5.2.5 サブコネクションの振る舞い : : : : : : : : : : : : : : : : 69 5.3 実験2 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 76 5.3.1 概要 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 76 5.3.2 目的 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 76 5.3.3 実験環境 : : : : : : : : : : : : : : : : : : : : : : : : : : : : 76 5.3.4 方法 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 76 5.4 実験2の結果 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 77 5.4.1 転送時間 : : : : : : : : : : : : : : : : : : : : : : : : : : : : 77 5.4.2 FastRetransmit 数と再送タイムアウト数 : : : : : : : : : 78 5.4.3 再送率 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 78 5.5 評価のまとめ : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 81 5.5.1 平均転送時間 : : : : : : : : : : : : : : : : : : : : : : : : : 81 5.5.2 FastRetransmit 数と再送タイムアウト数 : : : : : : : : : 81 5.5.3 再送率 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 82 5.5.4 サブコネクションの振る舞い : : : : : : : : : : : : : : : : 82 6. 考察および今後の課題 83

(8)

6.1 サブコネクション間の公平性について : : : : : : : : : : : : : : : 83 6.2 バイトカウンティングについて : : : : : : : : : : : : : : : : : : : 83 6.3 統合的輻輳制御について : : : : : : : : : : : : : : : : : : : : : : : 83 6.4 FACK 的効果 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 84 6.5 他の通信に与える影響 : : : : : : : : : : : : : : : : : : : : : : : : 84 6.6 実装 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 84 7. おわりに 86 謝辞 88 参考文献 89

(9)

図目次

1 TCP におけるコネクション確立手続き : : : : : : : : : : : : : : : 6 2 TCP におけるコネクション終了手続き : : : : : : : : : : : : : : : 6 3 インターネットにおけるプロトコル階層モデル: : : : : : : : : : : 7 4 IPデータグラムにカプセル化された TCP セグメント : : : : : : 8 5 TCP ヘッダ : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 9 6 ウインドウスケールオプション : : : : : : : : : : : : : : : : : : : 12 7 TCP における典型的なcwnd の変化 : : : : : : : : : : : : : : : : 15 8 SACK PERMIT オプション : : : : : : : : : : : : : : : : : : : : : 20 9 SACK オプション: : : : : : : : : : : : : : : : : : : : : : : : : : : 21 10 セグメント A 再送時の状況 : : : : : : : : : : : : : : : : : : : : : 43 11 FreeBSDにおける TCP 関連のデータ構造の関係図 : : : : : : : : 46 12 tcp cb 構造体と関連するデータ構造の関連図 : : : : : : : : : : : : 47 13 tcp cb 構造体からの送信リストの構成 : : : : : : : : : : : : : : : : 53 14 itcp subcb構造体からの送信リストの構成 : : : : : : : : : : : : : 53 15 実験環境 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 56 16 ロス率 0%における平均転送時間 : : : : : : : : : : : : : : : : : : 60 17 ロス率 3%における平均転送時間 : : : : : : : : : : : : : : : : : : 61 18 ロス率 5%における平均転送時間 : : : : : : : : : : : : : : : : : : 62 19 ロス率 3%における典型的な転送例(standard): : : : : : : : : : : 70 20 ロス率 3%における典型的な転送例(proposed) : : : : : : : : : : 72 21 コネクション分割管理方式(proposed)におけるサブコネクションごとの転送の様子 : : : : : : : : : : : : : : : : : : : : : : : : : : : 73 22 コネクション分割管理方式(proposed)における典型的なセグメント再送の例 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 75 23 転送時間が長い場合の典型的な転送状況 : : : : : : : : : : : : : : 79 24 転送時間が長い場合の典型的な転送状況 : : : : : : : : : : : : : : 80

(10)

表目次

1 セグメント紛失確率と帯域幅の関係 : : : : : : : : : : : : : : : : : 23 2 1サブコネクションあたりのバッファ量 S : : : : : : : : : : : : : 57 3 ロス率 3% における 512k バイト転送時の再送タイムアウト数と fast retransmit 数 : : : : : : : : : : : : : : : : : : : : : : : : : : : 64 4 ロス率 5% における 512k バイト転送時の再送タイムアウト数と fast retransmit 数 : : : : : : : : : : : : : : : : : : : : : : : : : : : 64 5 ロス率 3%における 512kバイト転送時の再送率[%] : : : : : : : 66 6 ロス率 5%における 512kバイト転送時の再送率[%] : : : : : : : 66 7 サブコネクションあたりの転送量の変動係数の平均(proposed) : : 68 8 サブコネクションあたりの転送量の変動係数の平均(no FACK) : 68 9 平均転送時間 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 77 10 Fast Retransmit 数と再送タイムアウト数: : : : : : : : : : : : : : 78 11 再送率 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 78

(11)

1.

はじめに

インターネットの代表的なサービスである World Wide Web(以下 WWWと

記す)は世界的規模で普及しており，インターネット利用者の急増の原動力となっている．インターネット利用者の急激な増加にともない，インターネットのトラフィックも著しく増大している．トラフィックの増大に耐えるため，ATMやFast Ethernet，波長多重，ギガビットイーサネットに代表されるように，広帯域なデータリンク層の実用化が進んでいる．その結果，さらに多くの利用者を受け入れることが可能となる．利用者の増加とインターネットの広帯域化にあわせて，WWW 上で利用されるコンテンツは多様化し，容量も年々増大している．たとえば高品質な画像情報や音情報の配信など，広帯域ネットワーク上で大容量コンテンツを高速転送するアプリケーションは今後ますます増加してくるものと考えられる．コンテンツ容量の増加とインターネット利用者の増加の相乗効果により，インターネットの広帯域化が進展すればするほどトラフィックは増加し続ける．そのため，輻輳によるパケットロスを完全に解消することは極めて困難である．リアルタイム性を要求される一部のストリーミングアプリケーション等を除けば，インターネットのアプリケーションのほとんどがトランスポート層プロトコルにTCPを使用している．TCPはコネクション指向の信頼性のあるバイトストリーム通信を提供するため，アプリケーションから利用しやすい．今後も TCP は広く利用されていくと考えられる．大容量コンテンツを高速に転送するためには，広帯域ネットワークのみならず，ネットワーク資源を有効に利用できるトランスポート層プロトコルが必要である． TCP のスループットは TCP に組み込まれている輻輳制御機構と再送制御機構に大きく依存している． TCP の輻輳制御アルゴリズムは広帯域ネットワークを十分に想定していないため，広帯域下で輻輳が発生した場合，利用可能帯域に応じた十分なスループットを得ることは難しい．TCPはセグメントロスが発生する環境では帯域幅に見合ったスループットが得られないことが指摘されている [1]．TCPの輻輳制御アルゴリズムは，セグメントロスが発生するとネットワークへの送信量を2分の1 に大きく減少させる．しかし，通信開始直後と再送タイムアウト直後以外では，

(12)

セグメントロスがない場合の送信量の増加は緩やかである．したがって，広帯域下でセグメントロスが発生すると，ネットワークへの送信量が激減し，セグメントロス発生前のネットワークへの送信量まで復帰するには時間がかかる．このような現象が発生するのは TCPの輻輳制御アルゴリズムがネットワークの状態を，輻輳が発生しているか，輻輳が発生していないかの2つの状態にしか区別しないためであると考えられる． TCP の再送制御アルゴリズムは fastretransmit と呼ばれる高速に再送を行うアルゴリズムを備えてはいるが，通信開始直後や終了直前，またネットワークへの送信量が少ない場合や転送量自体が少ない場合など，fast retransmitで再送できない状況は数多い．TCPのもう一つの再送制御アルゴリズムに再送タイムアウトによる再送がある．再送タイマがタイムアウトした場合にネットワークへの送信量を1パケット分に減らして送信をやり直す．再送タイムアウト値は1 秒ないしは数秒であり，この間は TCPは送信を中断した状態となる．その結果空いた帯域は他の TCPコネクションやストリームなどに利用されてしまうため，再送タイムアウト後のネットワークへの送信量はなかなか増加しない．fastretransmit で再送できない状況が多いにも関わらず，再送タイムアウトのペナルティが大きいことに TCP の再送制御アルゴリズムの問題点がある．本研究では以下の2点に着目して，広帯域ネットワークにおけるTCPのスループットの向上を目指す． 1. セグメントロス発生時にネットワークの状態を多段階に推測し，ネットワークへの送信量の調節を従来よりきめ細やかに行う． 2. fast retransmit の頻度を増加させ，再送タイムアウト待ちの頻度を減らす．本研究では，上記の2点を実現するために，TCPコネクションの分割管理方式を提案する．従来のTCP は，コネクションごとに輻輳制御を行っているが，コネクション分割管理方式では，1本の TCP コネクションを内部で論理的に分割し，各々に対して輻輳制御を行う．これにより TCP コネクション内での輻輳制御の単位が細かくなり，従来よりネットワークの状態を適切に反映したデータ転送が行える．また，分割された単位ごとに再送制御を行うので，fast retransmit による再送機会も増加する．

(13)

本論文では，2章で本研究の背景となる TCP について触れ，3章では本研究

と関連する研究について述べる．4章では本提案手法について詳説し，5章で本

提案手法を評価する．6章において本提案手法に対する考察と今後の課題とすべ

(14)

2.

背景

2.1 TCP

本節では，TCP の各機能の概略と問題点について述べる．

2.1.1 TCP の概要

TCP(TransmissionControl Protocol) は，コネクション指向であり，信頼性のあるバイトストリームサービスを提供するトランスポート層のプロトコルである．コネクション指向とは，通信を行うために事前にコネクションの確立が必要な事を意味する．TCPにおいては，通信時に互いの通信端末(エンド)間で相互に TCP コネクション確立手続きを行ってコネクションを形成し，通信終了時には各エンド間で相互にコネクション終了手続きを行ってコネクションを切断しなければならない．信頼性があるプロトコルとは，送信したデータが欠落したり，入れ替わったり，重複したりすることなく受信側に受信されることを保証することを指す．一方，インターネットのネットワーク層プロトコルであるIP(InternetProtocol)は，信頼性のない，ベストエフォート型のプロトコルである．ベストエフォート型のプロトコルにおいては，送信されたデータが正しく配送されるように最大限の努力は払うが，必ずしも欠落，入れ替わり，重複を発生させないわけではない．TCP は，欠落したデータを再送するための再送制御機構を有している．プロトコル階層的に，TCP は IP の上に位置しており，TCP セグメントは， IP データグラムで運ばれる．TCP はベストエフォート型のIP を配送系に用いて，信頼性のある通信を実現するプロトコルである．バイトストリームサービスとは，送信したデータに対しデータの境界が一切存在しないことを指す．パケットレベルでは送信データは一定値以下に分断されるが，受信側によって連続したデータに復元される．TCPの他に，インターネット

で用いられるトランスポート層プロトコルに UDP(UserDatagramProtocol)が

ある．UDPはバイトストリームサービスを提供しない．

(15)

ンドウサイズを送信側に通知することによって実現している．また，TCP は輻輳の発生時に送信量を調節する輻輳制御機構を有している． 2.1.2 TCP コネクション TCPのコネクション確立および終了の手続きを図1および図2に示す．図の下方向が時間の進む方向であり，図中の矢印がパケットの流れである．コネクション確立手続きはパケットを3つ交換することで行われており，3ウェイハンドシェイクと呼ばれている．コネクション確立及び終了要求を出す方をアクティブ側としてある．例えばWWWサーバとWWWブラウザの場合，コネクション確立時においてはクライアントがアクティブ側，サーバがパッシブ側である．コネクション終了時においては典型的にはサーバがアクティブ側，クライアントがパッシブ側となる．図中のSYN及び FINは，TCPヘッダ中において，コネクション確立と終了を示すために用いられるフラグである．また，図中のconnect()，listen()， accept()，close()は TCP で通信を行うためにアプリケーションが発行するシステムコールを表している．

(16)

SYN N

SYN M ack M+1 ack N+1

Active Open Passive Open

Established connect() listen() accept() 図 1 TCPにおけるコネクション確立手続き FIN N’ FIN M’ ack M’+1 ack N’+1

Active Close Passive Close

close()

(17)

Application Layer Transport Layer Network Layer Link Layer 図 3 インターネットにおけるプロトコル階層モデル 2.1.3 TCP のフォーマット図 3 に，インターネットにおけるプロトコル階層モデルを示す．OSI 参照モデルが7階層であるのに対し，インターネットでは4階層で表現する．インターネットでの4階層のモデルは，実際の運用の結果を基に簡単化されたものである．以下，各層の機能を示す． 1. リンク層 OS のデバイスドライバとネットワークインターフェイスおよび通信ケーブルを指す．物理的な全てのハードウェア的側面を制御する． 2. ネットワーク層パケットのルーティング等，ネットワーク上のパケットの移動を制御する． IP はネットワーク層に含まれる． 3. トランスポート層上位のアプリケーション層に対してエンド間のデータの流れを制御する． TCP，UDPはトランスポート層に含まれる． 4. アプリケーション層特定のアプリケーションの動作を制御する．アプリケーション固有のネットワーク処理に該当する．Telnet や FTP などのネットワークアプリケーションが含まれる．

(18)

IP header TCP header TCP data IP datagram TCP segment 20 bytes 20 bytes MSS MTU 図 4 IPデータグラムにカプセル化された TCP セグメントプロトコル階層的に，TCPは IPの上に位置している．TCPはベストエフォート型のIPを用いて，信頼性のある通信を行うプロトコルである．TCPセグメントは，IPデータグラムにカプセル化される．図4に IPデータグラムにカプセル化された TCP セグメントを示す．セグメ

ント上のデータの大きさの最大値(Max Segment Size．以下，MSS と記す)は

経路上のネットワークの最も小さい MTUにより決定される．MSSは MTUか

ら，20バイトの IP ヘッダと 20バイトの TCPヘッダを減じたものになるため，

MSS=MTU040バイトになる．近年ではMTU 1500バイトのEthernetが経

路上の最小 MTUになる場合が多く，この場合 MSSは 1460バイトになる．

図5に TCP ヘッダを示す．TCPヘッダは20バイトの固定長であるが，TCP

オプションは最大40バイトまで利用できる．1つの TCP オプションは，オプ

ションの種類(Kind)，オプションの長さ(Length)および値からなる．TCPオプ

(19)

0 15 16 31

16bit source port number 16bit destination port number

32bit sequence number

32bit acknowledgement number

16bit window size

16bit urgent pointer

options (if any) (MAX 40bytes)

data (if any) 16bit TCP checksum

4bit header length

reserved

(6bits) 6bit TCP flags

図 5 TCP ヘッダ 2.1.4 TCP の信頼性 TCP は，以下を保証することで信頼性を確保している．送信データが順序が入れ替わって受信側届いた場合，受信側で適切に並び替えること送信データが重複して受信側に届いた場合，受信側で重複分は破棄すること送信データが受信側に届かなければ，届くまで再送すること送信データの内容が変化せずに受信側に届くこと TCP は，送信する全てのデータに対し 1バイト毎にシーケンスナンバーをつけて管理している．TCP はセグメント単位でデータの送信を行う．各セグメン

(20)

トはどのシーケンスナンバーのデータを含むかの情報を保持しているため，送信セグメントの順序が入れ替わって受信側に届いた場合，シーケンスナンバーを参照すれば，送信順序通りに並び替えることが可能である．また，重複して受信したデータに関しても，シーケンスナンバーを利用すれば破棄することは容易である．バイトストリームサービスは，送信されたデータを送信された順序で過不足なしに受信側のアプリケーションプロセスに渡すことにより実現されている．送信データが相手に届くことの保証は，受信側が受信データに対する確認応答 (ACKnowledgement．以下ACKと記す)を送信側に返信することによって実現している．TCPにおける ACKは，ACK返信時点までに順序通りに受信したデータに対する累積 ACK である．すなわち，セグメントロスが発生した場合，受信側が返信する ACKは，ロスしたセグメントの直前のセグメントに対する ACK となる．同じ ACK が返されるため，これを重複 ACK と呼ぶ．送出側で重複 ACK を 3つ受信すると TCP は送出セグメントがロスしたと判断する．セグメントロスの検出を行うと，TCP はロスしたセグメントの再送を行う．再送制御の詳細については後述する．受信側の TCPは，必ずしも受信した全てのセグメントについて ACK を返信するわけではない．ACK によりネットワークが混雑するのは望ましくないためである．返信される ACK数を減らすための方策として，遅延 ACKと呼ばれる機能が定義されている．遅延 ACK は以下の条件を満たすときのみ ACKを返信する． 2MSS 分受信したとき遅延ACK 用のタイマが切れたとき遅延ACK用のタイマの値は，RFC1122[2]において，500ms以下であることと規定されているが，多くの実装では 200msを採用している．FreeBSDの実装においても200msが採用されている．またFreeBSDの実装では，2MSS分受信したときではなく，アプリケーションプロセスが 2MSS 分データを読み出したときとなっている．遅延ACKにより，ACK数が半減するとともに，エンド間で相互にデータをやりとりしているような状況では，返答データに ACK を含めるこ

(21)

とのできる機会が増加するので，効率よくパケットを交換できる．また，フロー制御用のウインドウサイズを通知する場合，windowupdateパケットが送信されるが，これも遅延ACKに含めることができ送信パケットを減少させられる．最後に，送信データの内容が変化せずに受信側に届くことの保証はチェックサムを用いて実現している．チェックサムフィールドを除いた TCP ヘッダと疑似ヘッダ部分のチェックサムを計算し，計算結果の1の補数をTCPヘッダのチェックサムフィールドに記録して送信する．受信側ではセグメント全体を各バイト毎に加算していく．セグメントの内容が変化せずに受信されていれば計算結果が0 になる． 2.1.5 TCP のフロー制御 TCP におけるフロー制御はウインドウベースである．受信側が受信のために利用できるバッファの最大限の大きさ(受信ウインドウ)を送信側に広告し，送信側はそのサイズ以上に送信ウインドウを広げることはしない．図5でもわかるように，受信ウインドウサイズを広告するためのフィールドは 16ビットであるため，広告できるウインドウサイズは2 16 01バイトまでになる．より大きなウインドウをサポートするため，RFC1323[3]では，ウインドウスケールオプションを定義している．図6にウインドウスケールオプションを示す．ウインドウスケールオプションはヘッダに含まれるウインドウサイズに2の何乗を掛けるかを指定するものである．2の14乗まで掛けることが許されており，ウインドウスケールオプションにより，広告可能なウインドウサイズの最大値は(2 16 01)22 14 となる．ウインドウスケールオプションは3ウェイハンドシェイク時にSYN とともに送られる．インターネットにおいては，単にエンド間のみでフロー制御を行うと，ネットワーク中で輻輳が頻発し，TCPのスループットは劇的に悪化することが報告されている [4]．ネットワークの状況に合わせたフロー制御を行う必要がある．TCP においては輻輳をなるべく起こさないようにフロー制御するアルゴリズムが採用されている．これを TCP の輻輳制御と呼ぶ．次項で TCP の輻輳制御について述べる．

(22)

Kind=3 Length=3 Shift Count 0 7 8 15 16 23 図 6 ウインドウスケールオプション 2.1.6 TCP の輻輳制御インターネットにおける輻輳の大部分は経路上の中継ルータで発生する．ルータで輻輳が発生すると，パケットロスが起こる．ルータでの輻輳は，帯域幅の大きいネットワークから帯域幅の小さいネットワークにパケットを交換する場合や，多数のリンクから少数のリンクへのパケットの流れが発生する場合や，ルータの処理限界を超えてパケットが入力された場合に生じる．ネットワークのトラフィックが増加し，ルータに対し複数の入力リンクから多数の同一リンク行きのパケットが入力されると，ルータの出力パケット待ち行列が長くなる．ルータは有限の制限数以下のパケットしか扱えないため，何らかのキューイング操作が必要である．ルータの出力パケットキューイング操作方式にはいくつかある．例えば，TailDropキューイング方式を採用するルータでは，待ち行列の長さが閾値を超えた状態で入力されるパケットは全て棄却する．RED キューイング方式[5]を採用するルータでは，待ち行列の長さが第1閾値を超えると入力パケットをランダムに棄却し始め，第2閾値を超えると全て棄却する．以上のように，パケットロスはネットワークの輻輳によって発生することが多い．しかし，衛星通信や赤外線LAN等の無線通信においては，データリンク層が天候等の様々な要因によって不安定になりやすく，輻輳の発生とは関係なくパケットロスが発生しやすい．今日のインターネットでは，無線リンクは特殊な存在であるが，今後より一般的になると考えられ，無線リンク上で効率よく動作する TCPについて現在盛んに研究が行われている．しかし，パケットロスの発生で輻輳の発生を判断することが非合理なわけでは

(23)

なく，輻輳発生の指標としてパケットロスの発生を用いることは，十分良い近似であると考えられる．TCP においても，パケットロスの発生すなわちセグメントロスの発生で輻輳の発生を推測している． TCPは前述したフロー制御用ウインドウとは別に，輻輳ウインドウ(Congestion Window．以下 cwnd と記す)の大きさも保持する．TCPの輻輳制御は cwndの調整を行う事により実現している．cwnd の値は，TCP のコネクションがその時点でネットワークに送出しても輻輳を起こさないと推測される大きさである． TCP がセグメントを送出する場合においては，ネットワーク中に存在する送出データの量が，フロー制御用ウインドウとcwndのうち小さいものを越えないようにしている．cwndはセグメントロスがない状況ではフロー制御用ウィンドウサイズを上限として単調に増加し続け，セグメントロスの発生により減少する． cwndの大きさによって通信のスループットが変化する．cwndが大きければ高スループット，cwndが小さければ低スループットとなる．一方，cwndの大きさはネットワークの負荷を反映したものでなければならない．ネットワークの負荷が高い時はcwndは小さくしなければならず，ネットワークの負荷が低いときは cwnd は大きくしても良い． TCP において効率の良い転送を行うには，ネットワークの輻輳状況に応じて適切に cwndを調節することが必要である．現在，TCPの輻輳制御のアルゴリズムは RFC2581[6]によって規定されてい

る，slowstartと congestion avoidanceと fastrecoveryの3つがある．ここでは， slowstartと congestionavoidanceについて触れる．両者はcwndの調整を行うア

ルゴリズムである．両者のうちどちらを適用するかの判断は，cwndと slowstart

threshold(以下，ssthreshと記す)と呼ばれる量の大小関係で行われる．ssthresh は近似的にコネクションが利用できる帯域幅遅延積を表している．

以下，slow start アルゴリズムと，congestion avoidance アルゴリズムについて述べる．

Slow Start

(24)

と，セグメントロスなどにより再送タイムアウトが起こった直後に発生する． slowstartでは，ネットワークの状態が明らかでないときに，ネットワークの利用可能帯域をネットワークに大きな負荷をかけずに推測する事と，セグメントの送信と ACK の受信の平衡状態を保ちつつcwnd を ssthresh の値まで増加させることを目的としている．送信側 TCP は cwnd を 1ないしは2セグメントの大きさから始めて，ACKを1つ受信する毎に cwndを 1セグメント分増加させていく．その結果，cwndは時間に対して指数関数的に増加していく．cwndがネットワークの利用可能帯域を越えると輻輳が発生し，送出セグメントのロスが起こる．TCP はその時点での cwnd の半分の値を ssthreshに保存し，cwndを ssthresh に等しくする．その後は congestion avoidanceに移行する． Congestion Avoidance congestion avoidanceフェーズでは，ネットワークの利用可能帯域の変化に対応して送信量を変化させ，セグメント送信とACK受信の平衡状態を実現する事を目的としている．TCPは cwndを ssthreshから始めて，ACK受信毎にcwndを1/cwndずつ増加させる．その結果，cwndは直線的に増加していく．セグメントロスが発生した場合，重複 ACK を 3 つ受信した時点で fast retransmit アルゴリズムが開始され，紛失セグメントの再送を行った後， fastrecoveryアルゴリズムにより，ssthreshにその時点の cwndの半分の値を記録し．cwndをssthreshに設定する．その後は再びcongentionavoidance

アルゴリズムに従い cwndを増加させていく．図7 に TCP における典型的な cwnd の時間変化を示す．cwnd は MSS を単位として示した．ここではMSSは1460バイトである．ただし，他のトラフィックはなく，ボトルネックリンクの帯域を45Mbps，RTTを30msとして，ネットワークシミュレータ ns [7]を用いてシミュレートした結果である．図中の時間0 秒から 0.5秒付近の間に cwndが指数関数的に増加している部分がslow startで

(25)

Time vs. Cwnd

cwnd Cwnd [MSS] Time [s] 0.00 20.00 40.00 60.00 80.00 100.00 120.00 140.00 160.00 180.00 200.00 220.00 240.00 0.00 5.00 10.00 15.00 図 7 TCP における典型的なcwnd の変化ある．cwndが230MSSを越えた付近でセグメントロスが発生し，fastretransmit および fastrecoveryの結果，cwndが減少し congestion avoidanceに移行している．congestion avoidanceでは cwnd は図からも読みとれるように直線的に増加している．congestion avoidanceで，cwndが 157MSSになった時点でセグメントロスが発生しているが，これはcwnd の値がネットワークの帯域幅遅延積に等しくなったからである．slow start 時には cwnd は 230MSS まで達しているが，これは，極めて短い時間間隔に大量のパケットをネットワークに送出してしまう slow start の性質によるものである． 2.1.7 TCP の再送制御送信セグメントのロスが発生した場合，TCPは再送を行わなければならない．また，送信したセグメントはロスせずに受信された場合でも受信側からの ACK

(26)

がロスすれば，TCP は送信セグメントが受信されたかどうかの判断ができないため再送を行わなければならない．前者の場合は 2.1.1節で述べたように，重複 ACK の受信で判断することができる場合があるが，cwnd が小さい場合や，コネクションの終了間際の場合など，重複ACKが返ってこないことがある．後者の場合は，受信側から次のデータに対する新しい ACKをいくら待っても返ってこないことが起こりうる．一定時間待っても ACKがこない場合はロスの判断を

するしかない．重複ACK の受信により引き起こされる再送をfastretransmitと

呼び，ACK待ちのタイムアウトにより引き起こされる再送を再送タイムアウト

と呼ぶ．以下，再送タイムアウトと fast retransmitについて述べる．また，fast

retransmit に引き続いて適用されるfast recoveryについても述べる．再送タイムアウト

あるセグメントを送信してから，一定時間内にそのセグメントに対するACK

が返ってこない場合，TCPはセグメントロスが発生したと判断し再送を行

う．これを再送タイムアウトと呼ぶ．

ロスを判断するまでのタイムアウト値は，エンド間のパケットの往復時間 (Round Trip Time．以下，RTT と記す)を基に決定される．RTTはセグ

メントを送信してから ACKを受け取るまでの時間である．RTTはネットワークの状態によって常に変動しているために，TCPは常に RTTを計測しており，タイムアウト値の決定には計測したRTTを平滑化したものを基に計算している．平滑化した値を用いるのは，細かい RTT の揺れによる影響をできるだけ少なくするためである．再送したセグメントが再び ACKされない場合，再送タイムアウト値は2倍の値に設定され再々送が行われる．再送タイムアウト値は連続して再送タイムアウトが行われると指数関数的に倍増していき最大値に達する．これを指数バックオフと呼ぶ．連続して再送タイムアウトが発生するということはネットワークが混雑しているということであり．そのような状況では再送するパケット自身が輻輳の悪化の原因となる可能性が高いからである．

(27)

重複ACK を 3回連続して受信すると再送タイムアウトを待たずにセグメントの再送を行うアルゴリズムである．重複ACK を 3回待つのは，配送経路上の問題でセグメントの順序入れ替わりが発生する事があるためである．しかし，1つのセグメントが後続する3つのセグメントに追い抜かれて受信されることはほぼあり得なく，セグメントロスが発生した可能性が極めて高いので，この場合は再送を行っても問題はない．fast retransmit はその名の通り，再送タイムアウトと比較すると極めて高速に再送を行える．しかし，重複ACK 3つを受信しなくてはならないので，少なくともロスしたセグメントの後に3つのセグメントを送信していなければならない．コネクション開始時，再送タイムアウト発生時等，cwndが小さい場合や，コネクション終了直前など，ネットワーク中に送出されているデータ量(アウトスタンディングウインドウと呼ぶ)が少ない場合は，fast retransmitが起こりにくいため，このような状況でセグメントロスが発生すると再送タイムアウト待ちになる可能性が高く，スループットが悪くなってしまう． Fast Recovery

セグメントのロスが発生し，重複ACKが 3つ到着して fast retransmitが

引き起こされた場合，輻輳の発生が推測される．そこで，fastretransmit後は，fast recovery と呼ばれる特別なモードに移行する．現在のフローを継続しつつ，最終的にアウトスタンディングウインドウを ssthreshの値にしてから congestion avoidanceに移行したいからである．重複ACK を受信するということは，ロスしたセグメント以外のどれかのセグメントは受信されたことを意味しているので，slowstartに移行することで現在も継続中のフローを削減してしまうのは効率が悪い． fast recoveryは，以下のように機能する．

(28)

3つ目の重複ACK が受信されると，ssthreshが現行の cwnd の 2分の1に設定される． cwndを ssthreshに 3MSSを加えた値に設定する．これは上述のように，重複ACK はロスしたセグメント以外のどれかのセグメントは受信されたことを意味しているからである．別の重複ACK を受信するたびに cwndを MSS単位で増加させる．新しい cwndの値が許す範囲でパケットを送信する．再送セグメントに対する ACKを受信したら，cwndをssthresh に設定する． congestion avoidanceに移行する．

最後に受信した ACKは，fast retransmit によって再送したセグメントに

対する ACK を含んでいる．また，再送したセグメント以降の全てのセグ

メントに対する ACKでもある．

ロスが発生し fastretransmitで再送した後は，fast recoveryを用いることで，アウトスタンディングウインドウを徐々に減らしつつ，最終的にはロ

ス発生時の半分まで引き下げ，congestion avoidanceにつなげている．fast

retransmit と fast recoveryによって，セグメントロス時に再送タイムアウトと比較すると高速で滑らかに再送制御と輻輳制御が行える．

(29)

TCP の最初の実用的な実装は，1980 年にカリフォルニア大学バークレイ校 (UCB)からリリースされた4.2BSDUNIXで行われた．1986年リリースの4.3BSD で性能向上が図られ，1988年リリースのTCPTaho eでは，slowstart，congestion avoidance，fast retransmit の各アルゴリズムが実装された．1990年リリースの TCP Reno では，fast recoveryや，典型的なパケットの処理を高速に行う TCP ヘッダプレディクションなどの機能が追加されている．現在使用されているTCPの実装の多くは TCP Renoをベースにしていると考えられる[8]．また，TCPに関する研究の大部分も TCPRenoのアルゴリズムを対象にして行われており，提案される新たなアルゴリズムの実装は，まず TCP Renoに対する改造という形で行われている．このため，TCPRenoは，TCPを実装する際の参照実装としての存在意義も大きい．最近では，米国MicroSoft社

の Windowsシリーズに実装されている Winsock や，Linux の TCP の実装等，

TCP Renoをベースに実装されていないものも存在するが，これらがTCP Reno

を無視して実装されたとは考えられない．

4.4BSD Lite2を最後に，UCBからの BSDのリリースは行われなくなったが，米国 BSDI社は，BSD/OSとして，BSDベースの OSのリリースをおこなって

おり，また，オープンソースのコミュニティが，FreeBSDや NetBSD，OpenBSD

などをリリースしている．本研究においても，提案手法の実装は FreeBSD 3.3 Releaseに対する改造という形で実現している． 2.3 SACK SACK(Selective ACKnowledgement，選択確認応答) は，RFC2018 [9]で規定されている．TCPにおける ACKは，前述の通り，ACK返信時点までに順序通りに受信できた最大のセグメントナンバーを送信側に通知するが，SACKでは，それに加えて，現在受信されているデータのセグメントナンバーも同時に送信側に通知する．TCPにおいて SACKはTCP オプションとして規定される．

(30)

Kind=4 Length=2

0 7 8 15

図8 SACK PERMIT オプション

まず，3ウェイハンドシェイク時にアクティブオープン側のSYNセグメントに

SACKの利用が可能ならばSACK PERMITオプションを付加する．パッシブオー

プン側も SACKの利用が可能ならば，SYNACKセグメントにSACK PERMIT

オプションを付加して送出する．以後，データ通信時に，受信データがシーケンスナンバー空間で不連続となった場合，通常のTCPと同様に連続して受信している最大のシーケンスナンバーを ACK フィールドに記録するとともに，オプションフィールドが許す範囲で，不連続ながらも受信できたセグメントのブロックをオプションフィールドに記録する．受信ブロックの左端と右端の TCPシーケンスナンバーを記録する．TCP オプションの領域が最大40バイトなので記録できるブロック数は最大4つまでとなるが，RFC1323で規定されている RTT の正確な計測に用いられるタイムスタンプオプションの存在を前提とすると，タイムスタンプオプションは12バイトを必要とするので，最大の SACKブロック数は3となる．このとき，1番目の SACK オプションフィールドには，その ACK の引き金になった受信セグメントを含む受信ブロックを含まなければならない．これは，送信側に，どのセグメントが受信されたかを確実に通知するためである．

SACKオプション付のACKを受け取った送信側では，SACK情報を再送の際に

利用する．送信済みデータのうち，ACK 及び SACKされていない部分を SACK

ホールと呼ぶ．送信側はSACK付きACKを受け取るということは，SACKホー

ルの情報を受け取ることと同値である．

SACKホールは再送の対象となる可能性がある．しかし，セグメントの順序入

れ替わりが発生した場合は，セグメントロスが発生していないにも関わらず送信

(31)

Kind=5 Length

Left Edge of 1st Block

Right Edge of 1st Block

Left Edge of nth Block

Right Edge of nth Block

0 15 16 31

(32)

らといって直ちに再送してよいものではない．

SACKはエンドの双方が対応しなければ機能できない．現在では，標準化され

ておらず，SACK対応のサーバなどは数少ないように，SACKは普及していると

はいえない．しかし，米国Microsoft社のWindows98や，Windows2000はデ

フォルトで SACKに対応している．OS 市場におけるWindowsのシェアは極めて大きく，SACK の普及が著しく進むものと考えられる．再送の際の SACK 情報を利用したTCP の振舞いは RFC2018では明示的には規定されていないものの，「従来方式を踏襲するべし」と述べられている．特に，セグメントの順序入れ替わりに対する堅牢さを保つために，1回だけの SACKホール通知により fastretransmitを行うべきではないと述べられている．また，1つ

の SACK付き ACKにより再送可能なセグメント数としては，slowstart時には

最大2セグメント，congestion avoidance時には最大1セグメントに制限すべきであるとも述べられている．現在では，SACK 情報を利用したTCP の振舞いに関する仕様が定まっていないため，さまざまな実装が存在し，その振舞いも各々違っている．本研究ではピサ大学の L.Rizzo 氏による SACK の実装を利用した [10]．この実装では，再送の際の SACK 情報の利用については，一度でもSACKホール通知を受け取ったセグメントは再送の対象になっている．RFC2018に述べられている「従来通り」

の解釈を，fast retransmit の際の「重複ACKを3つ受け取れば fast retransmit

開始」と同様とすれば，SACKホール通知数が3になった時点で再送の対象にし

なければならないことになり，本研究で利用したSACKの実装はRFC2018に反

することになる．本研究では，RFC2018に沿うため，利用した SACKの実装に

対し，SACKホール通知数をカウントし，SACKホール通知数が3になった時点

(33)

表 1 セグメント紛失確率と帯域幅の関係紛失確率 [%] 帯域幅[Mbps] 1.0 7 0.1 22 0.01 70 2.4 TCP

とセグメントロス

送信セグメントのロスが発生した場合，TCPは 2.1.6 及び，2.1.7で述べたように振る舞う．本節では，この振る舞いの問題点について述べる． 2.4.1 セグメントロスの影響 TCPはセグメントロスが発生する毎に送信量を2分の1にする．これはネットワーク帯域占有率の大幅な低下を引き起こす原因となる． Mathisら [1]の試算によれば，再送タイムアウトが発生しない場合にTCPが占有できる帯域幅の長時間平均は以下で示される． BW = MSS RTT 2 C p 1 2 ただし，BW は帯域幅，p はセグメントロスの確率であり，ロス時には fast

retransemit 及び fastrecoveryアルゴリズムが機能するものとする．また，受信

側 TCPは遅延応答確認を行わないとする．周期的にセグメントロスが発生する場合，C =1:22となることがわかっている． RTT 20ms，MTU 1500byteのネットワークにおいて，セグメントロスの確率と上式による帯域幅 BWの関係を表 1に示す． TCP はセグメントのロス量に関わらず一律で送信量を2分の1にし，その後のcwnd 増加量も一定であるので，ロス発生前後でのスループットの変動が大きく，また，ロス発生時の cwnd の値に cwndが回復するまで時間がかかるため，ネットワークの帯域を有効に利用することができない．

(34)

複数のセグメントがロスするなどして fast retransemit 及び fast recoveryアルゴリズムが機能できず再送タイムアウトが発生した場合はさらに TCPが占有する帯域が低下する．また，再送タイムアウトは最小値が，TCP Reno の場合 1500ms であり，今日のネットワーク状況と比較すると，再送タイムアウト待ちで送信ができない状態は，送信が中断してしまっているとみなすことができる．また，TCP Reno においては，再送タイムアウト時間の粒度は 500ms単位であり，粒度が粗い．再送タイムアウトにより送信が中断し，cwndが極端に低下したTCP コネクションは，他の TCPコネクションやストリーム等にネットワークの開いた帯域を利用されてしまうため，利用できる帯域が減少してしまい．cwndの改善がなかなか行われなくなる．結果として，再送タイムアウトの発生によって劇的にスループットが低下してしまう．また，送信量が少なくなったコネクションの送信量が少ないままになるということは，ネットワーク利用についての公平性も低い． 2.4.2 本研究の着眼点以上より，セグメントロスに対して TCP のスループットを向上するためには，以下のことが考えられる． 1. fast retransmit の頻度を増加させ再送タイムアウト待ちの頻度を減らす 2. セグメントロス発生時にネットワークの状態を多段階に推測し，ネットワークへの送信量の調節を従来よりきめ細やかに行う． 3. 再送タイムアウトの時間を短くする． TCP のスループットの向上を考える際は，コネクション間の公平性や，ネットワークでの輻輳の発生を防止することもあわせて考慮しなくてはならない．公平性が低く，また容易にネットワークの輻輳を招く TCPが広く氾濫してしまうと，インターネット全体でスループットが劇的に低下する可能性があるからである[4]．上記第3項目の再送タイムアウトの時間を短くすることについては，短くしすぎるとセグメントロス発生時のネットワークの輻輳をさらに悪化させてしまう可

(35)

能性が高い．再送タイムアウトは TCP の輻輳制御，再送制御にとって最終的な手段であるため，慎重にならざるを得ない．

(36)

3.

提案するコネクション分割管理方式

本章では，本研究で提案するTCP コネクション分割管理方式について述べる． 4.1

コネクション分割管理方式の概要

本節では本研究で提案するTCPにおける転送効率向上を目的としたコネクション分割管理方式の概要を述べる．コネクション分割管理方式においては，TCP コネクションにおいてデータ送信時に，送信するセグメントを複数のサブコネクションに分配し，各サブコネクションにおいて互いに独立に輻輳制御を行う．すなわち，従来は輻輳制御を1コネクションごとに行うが，分割管理方式においては1コネクション内の複数のサブコネクションごとに輻輳制御を行う．コネクション分割管理方式の利点は，1 つのTCPコネクション中に複数のサブコネクションを形成することにより，1コネクションあたりの輻輳制御の粒度が細かくなり，よりネットワークの状態を反映した振る舞いが行える点である．コネクション分割管理方式の利点は，輻輳などによりセグメントロスが発生する場合に顕著に現れる．輻輳が激しくなく，散発的にセグメントロスが発生する場合，分割管理手法においては，セグメントロスに遭遇したサブコネクションがセグメントロスに対処し，その他のサブコネクションは通常通りセグメント送信を続けるため，コネクション全体としての送信量の減少は少なく，従来のように 2分の1になることはない．輻輳が激しい場合は，セグメントロスが多発し，より多くのサブコネクションがセグメントロスに遭遇するため，コネクション全体としての送信量はロスの発生が少ない場合よりも大きく減少し，全てのサブコネクションがセグメントロスに遭遇した場合は従来通り送信量は2分の1になる．コネクション分割管理方式は TCP 内のみで完結しているため．ネットワーク階層モデルにおいて，TCP 層の上下層とのインターフェイスの変更を必要としない．したがって，TCP を用いて送信する場合に使用する各システムコールなどの API は従来と完全に同一であり，アプリケーションの変更は一切必要としないため，アプリケーションからの利用は非常に容易である．また，IP 層とのイ

(40)

ンターフェイスも変更する必要がない．コネクション分割管理方式は，送信側の修正のみで利用できる．受信側は従来通りの TCPがそのまま利用できるので適用が非常に容易である．例えば WWW においては，サーバ側の TCPを入れ替えるだけでよく，クライアント側のソフトウェアは従来のものがそのまま利用できるので何の対応も必要ではない． 4.2

コネクション分割管理方式

本節では，本研究における用語の定義について述べる． 4.2.1 コネクション分割管理方式の定義送信側TCP コネクション1つについて，送信セグメントの全集合Aを複数の部分集合 S 1;111;nに分ける．各々の部分集合に対して，互いに独立に輻輳制御及び再送制御を行う．この方式をコネクション分割管理方式と定義する． 4.2.2 サブコネクションの定義 S 1;111;n の輻輳制御を行う管理単位をサブコネクションと定義する．サブコネクションはコネクションの下位に位置する存在であり，輻輳制御の観点からは従来の TCPコネクション1つと等価である．1TCP コネクションに属するサブコネクションは，他の TCPコネクションには属さない．各サブコネクションに優先度の差は付けない． 1TCPコネクションでセグメント送信処理中には同時に1つのサブコネクションのみがアクティブになる．アクティブになるとは，送信しようとしているセグメントを当該サブコネクションの輻輳制御の対象にすることを指す．セグメントの送信を行うサブコネクションとは，セグメント送信時においてアクティブになっているサブコネクションである．各送信セグメントは必ずいずれかのサブコネクションに属する．サブコネクションに属するとは，あるサブコネクションによって当該送信セグメントが送信されたと見なすたことである．

(41)

4.2.3 多重度の定義 1 TCP コネクション中の最大可能サブコネクション数をサブコネクションの多重度とする．多重度 n のサブコネクションは，輻輳制御の観点からは従来の TCP コネクション n 本に相当する．サブコネクションの最大数 nは 1 TCPコネクションで一定値である．ある瞬間における 1 TCP コネクションに含まれるサブコネクション数は1以上 n 以下である． 4.2.4 NACK の定義コネクション分割管理方式において，受信側からのSACK情報を利用することにより，SACKホールの決定ができる．送信リスト中で SACKホールに該当するセグメントは NACK されたとみなすことができる．ネットワーク中でのセグメントの入れ替わりのを考慮して，コネクション分割管理方式においては NACK された回数をカウントしている．以下では，NACK された回数を，NACK カウントと呼ぶ． 4.3

コネクション分割管理方式のデータ構造

本節では，コネクション分割管理方式で必要となるデータ構造について述べる． 4.3.1 輻輳制御情報の定義各サブコネクションに対しては従来のTCPにおける輻輳制御を行うため，各サブコネクションは各々の cwnd(以下sc cwndと呼ぶ)，ssthresh(以下sc ssthresh と呼ぶ)，ownd(以下sc owndと呼ぶ)，を持つ．輻輳制御に用いる変数の初期値及び増減のタイミングを述べる． cwnd (コネクションごと) { 初期値は，MSSとする { ACK 受信時に，ACKを受信したサブコネクションに加えられる増分を加算する．

(42)

{ 増分は，ACK を受信したサブコネクションの sc cwndの増加分に等しい．

{ 再送タイムアウト時，コネクションの idle 時，および，ICMPsource

quench (送信量が多すぎる場合にネットワークから送られるメッセージ)受信時は cwnd=MSSにする． { 定常時に満たすべき条件: cwnd=6 sc cwnd sc cwnd (サブコネクションごと) { サブコネクションの congestion windowである． { 初期値を MSSとする．

{ ACK 受信時の増分は，sc cwnd < sc ssthreshで slow start 適用時は 1MSS ACK されるごとに 1MSS，sc cwnd sc ssthresh congestion avoidance時は，1MSS ACK されるごとにMSS

2

=sc cwnd．

{ 再送タイムアウト時，コネクションの idle 時，および，ICMPsource

quench 受信時は sc cwnd =MSSにする． ssthresh (コネクションごと) { 初期値は (2 16 01)22 14 ．ウインドウサイズの最大値． { 条件ssthresh=6sc ssthreshを満たす． sc ssthresh (サブコネクションごと)

{ サブコネクションの slow start thresholdである { 初期値は (2 16 01)22 14 /n． { ロス発生時には，sc ssthresh =max(sc cwnd=2;2MSS) (MSS 単位に切り上げ) ownd (コネクションごと) { 初期値は 0である．

(43)

{ 常に満たすべき条件は ownd=6sc ownd

sc ownd (サブコネクションごと)

{ サブコネクションのアウトスタンディングウインドウである．

{ 初期値は 0である．

{ セグメント送信時の増分は，送信したセグメントの大きさに等しい．

{ ACK および SACK 受信時の減少分は，ACK されたセグメントの大

きさに等しい． 4.3.2 送信リストの定義本研究で提案するコネクション分割管理方式は，送信したセグメントの記録を必要とするため，セグメントの送信のたびに送信したセグメントのシーケンスナンバーを記録する構造を有する．この構造を送信リストと呼ぶ．また，送信リスト中，1つのセグメントに対する部分を，送信リスト項目と呼ぶ．送信リストの各項目は以下の要素を保持する．先頭シーケンスナンバー末端シーケンスナンバー再送処理用シーケンスナンバー管理用情報 { 送信を行ったサブコネクションを同定する情報 { 送信セグメントの属性 { NACK カウント TCP コネクション管理ブロックから参照でき，かつ，各サブコネクション管理ブロックから，そのサブコネクションが送信したセグメントの送信リスト項目のみを参照できる構造を送信リストは有する．送信リスト項目は，このどちらか

(44)

らでもシーケンスナンバー空間上で昇順，または降順に参照できるように整列しておかなければならない．送信リストへの送信リスト項目の追加は以下の場合に限定する． 1. 保持している送信リストに記録されている最大のシーケンスナンバーを持つセグメントのシーケンスナンバーより大きいシーケンスナンバーの送信セグメントを送信した場合． 2. 通信開始時や再送タイムアウト後など，送信リストが空の場合．上記1の制限によって，再送タイムアウト以外の再送，すなわちfastretransmit および， fast recovery 中にセグメントが再送される時には送信セグメントが送信リストに記録されないことになる．再送したセグメントが再びセグメントロスに遭遇した場合，再送したセグメントの再送が必要になる．そのため，送信リスト項目中の再送処理用シーケンスナンバーの部分には以下のシーケンス番号を入れる．初回送信時送信セグメントの先頭シーケンスナンバー再送時再送を行ったサブコネクションがその時点で送信済みの最大のシーケンスナンバーを持つセグメントの末尾のシーケンスナンバー． 4.3.3 送信側 SACKedブロックの定義受信側から送信された SACK 情報を受信した送信側は，SACK 情報を利用するため，送信リストとは別に，SACKされたセグメントを記録しておくSACKed ブロックを保持する．シーケンスナンバー空間上で昇順，または降順に整列しておくのが望ましい． 4.3.4 サブコネクションと送信バッファサイズの関係多重度の上限は送信バッファサイズに依存する．多重度n の場合，1つのサブコネクションあたりには平均すると送信バッファサイズを多重度で割った大きさ