Comments
Description
Transcript
Wireless IP 向き TCP フロー制御の データ駆動実現
平成 15 年度 学士学位論文 Wireless IP 向き TCP フロー制御の データ駆動実現に関する研究 A Study on A Data-Driven Implementation of TCP Flow Control on Wireless IP 1040291 白根 裕太 指導教員 岩田 誠 教授 2004 年 2 月 13 日 高知工科大学 情報システム工学科 要 旨 Wireless IP 向き TCP フロー制御の データ駆動実現に関する研究 白根 裕太 近年の無線通信技術の発展とインターネットの普及を背景として、無線通信機器によるイ ンターネットの利用が増加している。これに伴い、インターネットの標準的プロトコルで ある TCP を、無線通信環境下でも高い信頼性で疎通させるため、Wireless TCP 技術に関 する研究が各所で進められている。これらの研究は大きく、(1)TCP 自身を高信頼化する方 式と、(2) データリンク層でのエラー訂正やパケット再送を高度化して従来の各種 TCP フ ロー制御方式をそのまま活用する方式、に分類される。無線通信環境では、電波伝搬状況を 要因とする伝送品質の変化のため、フロー制御における状態遷移の頻度が高く、集中同期制 御による既存方式を用いると、特に複数フローの並列処理時に処理切替のオーバヘッドの影 響が大きくなる問題がある。このため、複数フローをオーバヘッドなく多重処理する必要性 が優先通信環境よりも高い。 本研究では、(2) の各種 TCP フロー制御方式を無線通信環境で活用することを想定し、 多重パケット・ストリーム処理能力に優れ、かつ、低電力なデータ駆動型チップマルチプロ セッサ (DDCMP) 上に TCP フロー制御機能を実装し、予備的評価を行った。 評価の結果、複数フローを多重したフロー制御の処理切替オーバヘッドが非常に少ないこ とが示され、TCP の多重フロー処理にデータ駆動方式の特徴を活用でき、高速処理が可能 であることが確認された。 キーワード Wireless TCP、フロー制御、データ駆動型プロセッサ –i– Abstract A Study on A Data-Driven Implementation of TCP Flow Control on Wireless IP Yuta SHIRANE Recently, with the development of wireless telecommunication technology and the spread of the Internet services, utilization of the Internet by wireless telecommunication terminals is increasing. It follows in this; in the trenches, it is worked on research about Wireless TCP technology, in order to communication of high reliability under wireless telecommunication. These approaches is broken down into either high reliability TCP or original TCP flow control that be used to upgrading error correcting and packet retransmission in data link layer. At wireless communication, it is necessary to process TCP multi flow without a processing overhead, because TCP have change state by change propagation status at frequent internal and switching from one process is performed at high speed. The objective of this study is an implementation of TCP flow controls by data driven processor which realizes multi packet stream processing and low power consumption, and its implementation are evaluated preliminary in this study. As the result of preliminary evaluation, it was shown that there are very few over heads by processing change, and the feature of a DDMP system could be utilized for multi flow processing of TCP and check that it is possible to high-speed processing. key words Wireless TCP、Fllow Control、Date Driven Multimedia Processor – ii – 目次 第1章 序論 1 第2章 TCP 5 2.1 緒言 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2 TCP 基本機能 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.3 TCP 詳細機能 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.4 TCP の輻輳制御 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.5 TCP Tahoe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.6 TCP Reno(SACK) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.7 TCP newReno . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.8 TCP Vegas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.9 データ駆動での実現の必要性 . . . . . . . . . . . . . . . . . . . . . . . . 20 2.10 結言 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 第3章 データ駆動による マルチフロー処理実現 21 3.1 緒言 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.2 データ駆動型プロセッサでの実現法 . . . . . . . . . . . . . . . . . . . . . 21 3.3 プログラム構成 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.4 受信部のプログラム構成 . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.5 プログラムの問題点・解決案 . . . . . . . . . . . . . . . . . . . . . . . . 27 3.6 結言 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 性能評価 30 緒言 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 第4章 4.1 – iii – 目次 4.2 評価環境 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 4.3 性能評価結果 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.4 結言 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 結論 34 第5章 謝辞 36 参考文献 37 – iv – 図目次 1.1 TCP における状態遷移 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 既存プログラム (左) とデータフロープログラム (右) . . . . . . . . . . . . . 3 2.1 3way handshake . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2 TCP ヘッダーの構成 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.3 Half Close . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.4 TCP の標準的なコネクション . . . . . . . . . . . . . . . . . . . . . . . . 9 2.5 シーケンス番号例 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.6 仮想データフォーマット . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.7 RTT 測定 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.8 TCPTahoe における再送時のフロー制御 . . . . . . . . . . . . . . . . . . . 15 2.9 TCPReno における再送時のフロー制御 . . . . . . . . . . . . . . . . . . . 16 2.10 SACK オプションの例 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.11 TCPnewReno における再送時のフロー制御 . . . . . . . . . . . . . . . . . 19 3.1 世代データの構成 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.2 世代計算の例 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.3 マルチフロー処理対象 TCP フロー制御プログラムの基本構成 (Sender 部) . 23 3.4 TCP フロー制御の送信側モジュール構成 . . . . . . . . . . . . . . . . . . . 24 3.5 TCP フロー制御の受信側モジュール構成 . . . . . . . . . . . . . . . . . . . 26 3.6 新提案プログラム構造 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 –v– 表目次 4.1 モジュールの多重処理効果 (500step) . . . . . . . . . . . . . . . . . . . . . 31 4.2 モジュールの多重処理効果 (600step) . . . . . . . . . . . . . . . . . . . . . 32 4.3 モジュールの多重処理効果 (700step) . . . . . . . . . . . . . . . . . . . . . 32 4.4 モジュールの多重処理効果 (800step) . . . . . . . . . . . . . . . . . . . . . 32 4.5 モジュールの多重処理効果 (900step) . . . . . . . . . . . . . . . . . . . . . 32 – vi – 第1章 序論 近年、モバイル端末の普及により無線通信技術が急速に発展してきており、また、イン ターネットを始めとする様々なデータ通信サービスが広く一般的に利用されるようになって きている。これらに伴い、無線通信機器を用いたデータ伝送サービスへのアクセス要求が高 まってきている。しかし、無線通信は非常に信頼性の低いデータ伝送媒体である。そのた め、無線通信においても信頼性の高いパケット通信を可能にするために Wireless TCP 技術 の研究が各所で進められている。 現在の Wireless TCP の研究のアプローチの方法としては • TCP 自身を更に高信頼化する方法 • データリンク層での制御を高度化することで、従来の各種 TCP フロー制御を活用する 方法 の 2 つが挙げられる。 本稿では、後者の各種 TCP フローを活用し、無線通信に TCP フロー制御を実装するこ とを想定し、TCP フロー制御の研究を行なった。 TCP は IP ネットワークにおける高信頼性のデータ転送を目的としたプロトコルであり、 全二重通信を前提としたパケット再送を可能としている。だが、TCP は無線通信のように、 通信品質の悪い環境に適応するとパケットの再送が頻発し、十分な性能を得ることが難しい。 そこで、現在の Wireless TCP ではデータリンク層で FEC(Forward Error Correction) や ARQ(Automatic Repeat reQuest) に基づく誤り訂正や再送制御を行なうことにより、直接 TCP 層に影響が出ないように工夫されている。 –1– しかし、無線通信では伝送状態が随時変化するため、図 1.1 のような TCP フロー制御の 各状態の切り替えが頻繁に行なわれ、集中同期制御による既存の方式を用いると処理オーバ ヘッドが生じる。そのため、それらの状態切り替えの処理を高速に行なう必要がある。ま た、複数フローを処理した場合に、より顕著に状態切り替えによる処理オーバヘッドが大き く影響してしまう問題がある。そのため、複数のフローを処理しても状態切り替えによる処 理オーバヘッドが発生しない多重処理の必要性が有線通信よりも高い。 図 1.1 TCP における状態遷移 本研究では、各種 TCP フロー制御方式を無線通信に用いることを想定して、複数のパ ケットストリームを多重に処理する能力に優れているデータ駆動型チップマルチプロセッサ を用いて TCP フロー制御の実装を行ない、予備的評価を行なう。 ここで、今回研究に用いるデータ駆動チップマルチプロセッサについて説明する。データ 駆動チップマルチプロセッサの特徴としては、 • 省電力、低発熱 • プログラマブルな高い柔軟性 • 高い並列処理性 が挙げられる。データ駆動プロセッサはノイマン型プロセッサのように、クロックを用いて 動作するのではなく、データを処理する部分のみ電力を消費するため、低消費電力が可能と –2– なっている。また、データ駆動型プロセッサの大きな特徴は、既存のプロセッサとは違い、 データフローによりプログラムを記述することができるという点である。図 1.2 に既存のプ ログラムとフローグラフのプログラムを示す。 図 1.2 既存プログラム (左) とデータフロープログラム (右) 図をで示す通り、ノイマン型プロセッサと同じ処理をデータフローで実現すると、並列処 理可能な部分が増加しているため、その分高速処理が可能になる。また、データ駆動型プロ セッサでは、プログラマブルであるために様々なシステムに柔軟の対応可能である。このよ うなデータ駆動型プロセッサは、多数のフローを効率よく並列に制御することを目的とした TCP フロー制御を実現することに向いていると考える。 以上のアプローチでマルチフローを対象とした TCP フロー制御の実現を図り、その予備 評価を行なう。 ２章では、TCP の無線環境における問題点を明白にするために、TCP の機能についての 説明を行い、TCP それぞれの方式についての説明をし、それをふまえての問題点を述べる。 ３章では、マルチフロー処理を対象とした TCP フローをデータ駆動を用いての実現方法 –3– を説明し、その問題点と解決策を説明する。 ４章では、データ駆動型プロセッサを用いて実現したマルチフロー対象 TCP フロー制御 プログラムの性能評価を行い、データ駆動の特徴を生かした構成であることを確認する。 ５章では、実現した TCP 制御、性能評価をもとに考察を行なう。 –4– 第2章 TCP 2.1 緒言 本章では、TCP の特徴や基本的な機能を説明を行い、さらにデータ駆動方式での実現の 必要性について述べた後、実装する TCP のバージョンの選択理由について説明する。 2.2 TCP 基本機能 TCP(Transmission Control Protocol)[2] とは、OSI 参照モデルのトランスポート層プロ トコルでデータの転送制御を行なっている機能である。TCP の特徴として、 • 非構造化ストリーム • 全二重通信 • コネクション指向 • 高信頼性サービス の 4 つが挙げられる。これより、TCO の特徴に挙げたこれら 4 つについての説明を行なう 1. 非構造化ストリーム 非構造化ストリームとは、TCP が扱うデータが構造を持たないことを意味する。扱う データを単なるデータとみなし、送信側が送ったストリーム列をそのまま受信側に送信 する。その際の送信データの構造の解釈は上位層に任せている。 また、TCP の通信経路に最適なセグメント長を推測し、送信側が送ったストリーム列 –5– 2.2 TCP 基本機能 を通信経路に最適な大きさでアプリケーション構造を全く考慮をせずに分割をする。 2. 全二重通信 全二重通信とは、通信する両者が同時にデータストリームを送受信できることをいう。 したがって、双方のエンドユーザがそれぞれ各方向に流れるシーケンス番号を管理する 必要がある。 3. コネクション指向 TCP を利用する 2 つのアプリケーション (クライアントとサーバ) がデータを交換する 前に、相互のコネクションを確立する必要があるということを意味する。つまり、TCP では送信側がデータを送信する前に受信側とネゴシエートを行ない、受信側の能力や 通信経路を把握し、効率の良い通信を行なうための仕組みである。このネゴシエートに よって、受信側が広告ウィンドウサイズの情報を送信側に送信することによって、送信 側は受信側がどの程度のバッファを用意しているか等を把握することができる。 このコネクションを確立するために、3Way handshake という方法で実現している。 3Way handshake は、 （a）クライアント側から「確立要求 (SYN)」を送信 （b）サーバ側から確立要求 (SYN) と確立要求の確認応答 (ACK) を Piggyback を用い て同時に送信 （c）クライアント側からの確立要求の確認応答 (ACK) の送信、の手順で行なわれる。 また、SYN と ACK は TCP のヘッダフォーマットのフラグに含まれているため、 SYN フラグをオンにして送信すれば確立要求をしたことになる。 図 2.1 に 3Way handshake によるコネクション確立の流れを, 図 2.2 に TCP ヘッダー フォーマットを示す。 –6– 2.2 TCP 基本機能 図 2.1 3way handshake @ A ' ( ) * # $ % & ! , " - 8 ? : 2 ; ; < < = 4 = > > 5 3 / 6 - 0 図 2.2 TCP ヘッダーの構成 –7– @ B . 9 3 + 1 1 7 2 1 2.2 TCP 基本機能 また、コネクション終了はハーフクローズという方法を用いて行なわれる。このハー フクローズは片方ずつコネクションを閉じるようになるため、4 つのパケットが伝送す ることになる。最初に送信側が Active Close というクローズ要求を送信する。Active Close を受け取った受信側はまずコネクション終了要求 FIN を送信する。図 2.3 にハー フクローズによるコネクション終了のフローを示し、図 2.4 に一般的なコネクション確 立から終了までのフローを示す。 図 2.3 Half Close –8– 2.2 TCP 基本機能 図 2.4 TCP の標準的なコネクション 4. 高信頼性サービス 高信頼性サービスとは、送信したパケットが喪失した場合に、喪失したパケットを検 出し、再送するといった機能のことをいう。TCP では以下のように信頼性を保証して いる。 • アプリケーション・データは TCP によって通信に最適なセグメントサイズに分割 される。 • セグメントを送信する際にタイマーを設定し、時間内に ACK が送信されなけれ ば、セグメントを再送する。 • TCP では、コネクションの一方のエンドからデータを受け取ると、ACK を送信 する。 • チェックサムを利用し、目的のデータが送信中に変化していないかをチェックす –9– 2.2 TCP 基本機能 る。変化が認められれば、 そのデータを破棄し、ACK を送信しない。 • TCP セグメントは順番通りに到着しなくてもよい。並び替えが必要であれば受信 側で並び替える。 • TCP は重複したデータを破棄する。 • TCP は各エンドの有限バッファ・サイズの情報をもち、バッファを超えない範囲 でデータの送受信を行なう。 これから、さらに詳しく TCP の機能についての説明を行なう。 • シーケンス番号 シーケンス番号は、送信するパケットの順序を保証しており、損失したパケット を検出する指標となる。ネゴシエートの段階で最初のシーケンス番号を決定して おき、次から、初期シーケンス番号＋ストリーム中の位置で決定していく。2.5 に シーケンス番号の例を示す。 図 2.5 シーケンス番号例 このシーケンス番号の例はアプリケーションが 2500 バイトのデータを TCP に渡 す際に、最適なパケットサイズが 500 バイト、初期シーケンスを 10000 とした場 合の各パケットのシーケンス番号を割り当てる際の例である。図のように、10001 から 500 バイトずつで分割して、そのシーケンス番号も初期シーケンス番号＋スト – 10 – 2.2 TCP 基本機能 リーム中の位置で確定していることが分かる。 • 再送機能 TCP には高信頼性サービスの 1 つに再送機能を持っている。TCP では、再送タイ マーを用いて再送をする方法と重複する ACK が一定以上受け取ったときに再送を 実行する。 （a）再送タイマーによる再送 パケットを送信後、reciver から一定時間以内に ACK が帰ってこなければ、 sender は送信したパケットに問題があったと判断し、パケットを再送する。 （b）重複 ACK による再送 reciver は sender からパケットを受け取ると ACK を sender に送信するが、も し sender からの送信パケットが連続していなかった場合、そのパケットを受 け取るまでは同じ ACK(重複 ACK と呼ぶ) を sender に送信し続ける。sender ではこの重複 ACK が一定回数以上送られ続けるとパケットを損失していると 判断し、パケットを再送する。通常この重複 ACK を 3 回受け取ると sender は再送を行なう。 • チェックサム機構 TCP では、パケットが全て届いているかを確認するための方法として、ェックサ ム機構を持っている。チェックサム機構はデータ部分に仮想的な IP ヘッダを付加 することにより、ヘッダ部、データ部全体でチェックサムを計算する。図 2.6 に仮 想ヘッダフォーマットの構成を示す。 図 2.6 仮想データフォーマット – 11 – 2.3 TCP 詳細機能 チェックサムの計算方法は以下ようになっている。 （a）チェックサム・フィールドを 0 にクリアする （b）データを 16 ビットごとに分割し 1 の補数和を計算 （c）計算結果の 1 の補数がチェックサムとなる (ここで１の補数和というのは足し算をした結果の桁上がり分を最下位ビットに加 算する計算方法のことであり、１の補数の足し算ではないことに注意。) • フロー制御機構 フロー制御機構 [6] は、通信状態に合わせてデータの伝送速度を決定する機能であ る。データの伝送速度の調節には以下のような方法がとられている – 相手の処理速度に合わせる方法・・・受信側が処理できない速度ではデータを 送らない – ネットワークの状態に合わせる方法・・・輻輳制御により混雑しているときは 速度を落とすことにより、輻輳を回避する。ただし、このときの受信側の処理 能力を超えるほどのデータは伝送しない。 フロー制御機構については、この後に詳しく説明を行なう。 2.3 TCP 詳細機能 • タイマー機構 TCP のタイマーにはスロータイマーとファーストタイマーの 2 つが実装されている。 スロータイマーは遅い間隔で起動するタイマーで、500ms ごとにタイマーが起動する。 このタイマーは再送タイマーなどの計算に用いられる。また、ファーストタイマーは早 い間隔で起動するタイマーで、200ms ごとにタイマーを起動している。 • 再送タイマー 再送タイマーとは、パケットを送信後、一定時間たっても ACK が帰ってこなかった場 合にパケットを再送するために用いられているタイマーである。このタイマーはパケッ – 12 – 2.3 TCP 詳細機能 トが送信されるごとにセットされ、再送タイムが過ぎても ACK を受信しなければ、再 送を行なう。再送タイマーに適切な値を設定することが非常に重要であり、タイマーの 設定した値が長すぎるスループットの低下を招き、短すぎると不必要な再送が発生し、 ネットワークに必要以上の負荷を与えてしまう。 再送タイマーの値は、Round Trip Time(RTT) を使って算出される。図 2.7 に RTT の測定する部分を示す。 図 2.7 RTT 測定 図のように RTT とは、データを送信してから送信したデータの ACK を受信するまで の時間のことを示す。長い回線を利用している場合は RTT が長くなるため、再送タイ マーの長めに設定し、逆に短い回線を利用している場合は RTT が短くなるために、タ イマーは短めに設定する必要がある。このように、RTT を利用してタイマーの値を計 算することにより、効率の良い通信を TCP では実現する。 以上が TCP に基本的な機能と詳細な機能の説明である。 – 13 – 2.4 TCP の輻輳制御 2.4 TCP の輻輳制御 TCP の輻輳制御は終端のノードによる自律的な制御であり、この制御により、ある程度 の輻輳の発生を防ぐことができ、輻輳を検出した場合はデータの転送レートを下げることに より輻輳崩壊を防ぐことができるようになっている。 TCP の輻輳制御アルゴリズムはネットワークの状態がわからないことが前提で、パケッ トが損失しないときはネットワークがあいていると判断して転送速度を上げ、逆にパケット が損失する場合は、ネットワークが混んでいると判断して、転送速度を下げるといったよう に非常に単純なアルゴリズムである。転送速度の制御はパラーメータである輻輳ウィンドウ サイズを変えることによって行なっている。輻輳ウィンドウサイズは受信側が通知するウィ ンドウワイズよりも小さい値を採用することにより、受信側の許容量を超えないようにして ネットワークの状態を見ながら通信を行なう。輻輳ウィンドウを増やし方としてはスロース タートと輻輳回避の 2 つがある。 • スロースタート ACK を受け取るたびに 1 個ずつ輻輳ウィンドウサイズを増やしていくアルゴリズム で、実際には指数関数的に増加していくように見える。 • 輻輳回避 ウィンドウサイズ分の１ずつ輻輳ウィンドウサイズを増やしていくアルゴリズムで、線 形的にサイズを増やしていく。 この 2 つのアルゴリズムを組み合わせて、ネットワークにあわせてデータ転送レートを 上げ下げするのが TCP の輻輳制御である。データパケットの損失がない場合は、スロース タートを用いて輻輳ウィンドウサイズを大きくしていく。ここで、輻輳ウィンドウサイズが ssthresh(スロースタートの閾値) を越えると輻輳回避にとって輻輳ウィンドウサイズを大き くするようになる。 パケットを再送した場合、その時に輻輳ウィンドウサイズの 2 分の 1 を ssthresh に設定 しなおして転送速度を下げるようにする。また、タイムアウトによりパケットを再送した場 – 14 – 2.5 TCP Tahoe 合は、輻輳ウィンドウサイズを最小にする。 これより、TCP の各バージョンについての違いの説明を行なう。 2.5 TCP Tahoe TCP Tahoe[3] では、輻輳制御アルゴリズムに Fast Retrasmit アルゴリズムを利用して いる。Fast Retransmit アルゴリズムは、再送タイマー前に迅速にパケットを再送するため のアルゴリズムである。図 2.8 に再送時のフローを示す。 図 2.8 TCPTahoe における再送時のフロー制御 Fast Retransmit アルゴリズムでは、受信側から重複した ACK が 3 回到達すると、送信 側はパケットを喪失している可能性が非常に高いと判断して、パケットを再送する。これ により、再送タイマーによるタイムアウトを待つ前にパケットを迅速に再送できる。また TCP ではパケットを再送した後に、ネットワークを輻輳を回避するために伝送速度を落と – 15 – 2.6 TCP Reno(SACK) すために輻輳ウィンドウサイズを減少させるが、このアルゴリズムでは輻輳ウィンドウサイ ズを 1 に設定し、輻輳ウィンドウサイズを指数関数的に増加させるスロースタートアルゴリ ズムを用いて、再び輻輳ウィンドウサイズを上昇させて伝送速度を上げていく。この方法で は、パケットの伝送エラーが多い通信では頻繁にパケットを再送するために、輻輳制御も頻 発してしまい、そのためにスループットが向上しない問題がある。 2.6 TCP Reno(SACK) TCPReno[4] では、TCPTahoe で利用されていた Fast Retransmit アルゴリズムの問題 点であったパケットを再送した際の輻輳制御により輻輳ウィンドウを１にまで落としてしま うために、スループットの向上が難しいという点を改良した Fast Recovery アルゴリズムを 使用している。図 2.9 に Reno での再送時のフローを示す 図 2.9 TCPReno における再送時のフロー制御 – 16 – 2.6 TCP Reno(SACK) このアルゴリズムでは、Faste Retranmit と同様に受信側から重複した ACK を 3 回受け 取ることにより、パケットが損失している可能性が高いと判断して、パケットを再送する。 再送後に帰ってきた ACK の値が更新されていれば、輻輳ウィンドウを小さくして再送モー ドを抜ける。その際の輻輳ウィンドウの設定は、輻輳制御に入ったときの輻輳ウィンドウサ イズの 1/2 に設定しなおしてスロースタートではなく輻輳回避モードでパケットを再び送 信し始めるようになっている。 また、TCPReno では SACK オプションと呼ばれるオプションを付加して利用されてい ることが多い。この SACK オプションについて説明を行なう。 SACK オプションとは、受信側が具体的にどこまでにパケットを受け取ったかを詳細に 通知するためのオプションである。これを利用することにより、これまで ACK を用いての 予測的に損失パケットを判断して再送していたが、損失しているパケットをより明確に判断 することができるようになる。それにより、効率よくパケットの再送が行なえるようにな る。SACK には SACK Permitted Option と SACK Option の 2 つのオプションがあり。 SACK Permitted Option は、3Way hanshake 時の negotiate の際に通信を行なう相手に SACK Option に対応していることを通知するためのオプションである。SACK Option は TCP ヘッダの中に到着したパケットのシーケンス番号を格納する SACK Option のフォーマットは、最大４ブロックに到着したシーケンス番号を格納して いる。新しく受信したパケットのシーケンス番号の左端と右端を最初のブロックに格納し、 その前に受信したパケットのシーケンス番号の左端と右端を次のブロックといったように４ ブロックまで情報を格納することができる。 表 2.10 に SACK オプションの例を示めす。 – 17 – 2.7 TCP newReno 図 2.10 SACK オプションの例 2.7 TCP newReno TCP newReno[5] では Reno で使用されている Fast Recovery アルゴリズムを改良した アルゴリズムを使用している。図 2.11 に newReno での再送フローを示す。 図の通り、重複 ACK を 3 回受け取ることによって再送する部分までは同じだが、再送を してしまった後の制御に変更を加えている。Reno の Fast Recovery では、パケットを再送 すると輻輳ウィンドウを 1/2 にして伝送速度を落として輻輳回避に戻るようになっていた が、これではパケットが連続して損失していた場合、損失していると確実に分かっていても 再び重複 ACK を 3 回受信してから再送を行なう。また、そのたびに輻輳ウィンドウを 1/2 にするためにスループットが向上しない問題がある。そこで newReno では、重複 ACK を 3 回受け取るまでに送信したパケットの ACK が送られてくるまでは、再送モードを維持し 続けるようになっている。図では、SEG2 のパケットが損失して ACK １を 3 回受け取り、 SEG2 のデータを再送している。しかし帰ってきた ACK のデータは 3 になっており、それ までに送信したデータの ACK 番号ではない。newReno ではこの時、SEG4 のデータも損 失していると認識して SEG4 のデータを再送する。 期待している ACK が戻ってくれば Reno と同じ輻輳制御を行なう。これにより、連続し てパケットが損失していても輻輳制御による大幅なスループットの低下は起こらないように なっている。 – 18 – 2.8 TCP Vegas 図 2.11 TCPnewReno における再送時のフロー制御 2.8 TCP Vegas これまでの TCP の輻輳制御アルゴリズムはネットワークの状態が全くは把握できないこ とを前提としているアルゴリズムで、ネットワークが空いているから伝送速度を上げて、パ ケットに損失がおこるとネットワークが混雑していると判断して伝送速度を落とすという単 純なのもである。 しかし、TCP Vegas[6] ではデータを伝送しながら実際の伝送性能を表す Actual Through- put とこれまでのパケットの送信結果から推測した伝送速度を表す Expected Throughput の２つを計測して、この２つのスループットを比較して輻輳制御を行なう。 – 19 – 2.9 データ駆動での実現の必要性 • Actual Throughput ＜ Expected Throughput 伝送速度を上げる • Actual Throughput ＞ Expected Throughput 伝送速度を落とす • Actual Throughput ＝ Expected Throughput 伝送速度を保つ 2.9 データ駆動での実現の必要性 これまでに述べてきたように、TCP とは高信頼性のデータ転送を行なうプロトコルであ る。しかし、無線通信のような通信品質が悪い環境に適用した場合、パケットの損失が頻繁 に起こるため TCP の再送制御が頻発してしまう。そのために、十分な性能を得ることが困 難である。そのため、現在の無線 LAN ではデータリンク層で FEC や ARQ に基づいて誤 り訂正や再送制御が行なうことにより、品質劣化の影響を直接 TCP パケットに連動させな い工夫がされている。 しかし、無線通信では通信伝送状況が時々刻々と変化してしまうために、これまでに述べ てきた TCP の制御が頻繁に切り替わってしまう。そのため、それらの制御の切り替え処理 を高速に行なう必要性がある。また、複数コネクションを同時に処理を行なった場合、制御 の切り替えによる処理オーバヘッドが、より顕著に現れ、従来のノイマン型プロセッサでこ のオーバヘッドが蓄積してしまい、処理速度に大きな影響を与えてしまうことが考えられ る。そこで、現在は、複数フローを多重処理してもオーバヘッドが起こらない TCP フロー 制御の要請が強い。 そこで、複数のパケットストリーム処理に優れた性能を発揮する DDMP を用いることに より、これらの問題を解決できる TCP フロー制御モジュールが実現できると考えられる。 2.10 結言 本章では、WirelessIP 向き TCP データ駆動方式を実現するために、まず TCP の基本機 能について説明した。次に TCP のバージョンごとのフロー制御について説明し、無線環境 においての TCP 実装の問題点を示し、DDMP での実現の必要性を示した。 – 20 – 第3章 データ駆動による マルチフロー処理実現 3.1 緒言 本章では、マルチ TCP フロー制御の最適なプログラム構成を考え、データ駆動型プロ セッサでの実現方法を示す。 3.2 データ駆動型プロセッサでの実現法 ここでは、マルチフロー対象の TCP フロー制御を実現法について述べる。 マルチフロー処理を対象とするためには、複数のフローを区別する必要がある。本研究で は、この課題をデータ駆動で用いられる世代と呼ばれる識別子を用いる。本研究では、この 世代を用いて複数フローの区別を行なうことによって、マルチフロー対象の TCP フロー制 御を実現する。 ここで、世代について説明を行なう。世代とは、さきほども述べたがデータ駆動で用いら れる識別子である。世代データの構成を図 3.1 に示す。 図のように世代データは 28bit で構成されており、そのなかで BK、FS、CH の３つの領 域に分けられている。データ駆動ではこの世代が完全一致するパケット同士でのみ命令を実 行する特徴をもっている。 図 3.2 に例を示す。 – 21 – 3.2 データ駆動型プロセッサでの実現法 図 3.1 世代データの構成 図 3.2 世代計算の例 この図では右側からデータがさきに入力されるとする。右側にはデータの世代が 0、1 の 順で入力されているのに対し、左側では 1、0 の世代順でデータが投入されている。この場 合、データ駆動ではさきにデータがそろった世代 1 から演算を行い、後からデータがそろっ た世代 0 のデータはその後に演算を行なうようになる。つまりデータ駆動では、命令実行時 にはさきに入力されたデータの対となる同じ世代を持ったデータが入力されない限り、命令 を実行しない。 この特徴をから考えると、複数フローにそれぞれ違う世代データを与えてやることによ り、複数のフローが混在していたとしても同じ世代をもつフロー同士でしか処理を行なわな いことになるために、マルチフロー処理が可能になると考える。 – 22 – 3.3 プログラム構成 3.3 プログラム構成 この章では、作成したプログラムの構成とプログラムに使用しているモジュールの説明を 行なう。 図 3.3 マルチフロー処理対象 TCP フロー制御プログラムの基本構成 (Sender 部) 図 3.3 に今回作成したマルチフロー対象 TCP フロー制御の Sender 部のプログラムの基 本構成を表している。簡単にプログラムの流れを説明する。 1. データ入力部から投入されたデータは、フローチェックモジュールに渡され、入力デー タがどのフローのデータであるかを判断する。 2. 判断されたデータは、同種のフローデータが処理されるフロー制御モジュールへと送ら れ、TCP フロー制御の処理が行なわれる。 3. フロー制御処理が終了したら、メモリーにアクセスして送信すべきデータを読み出し、 読み出したら受信側に送信する。 Sender 部では、送信するデータを一度メモリに格納する。その後トリガーとなるパケッ トを用いて一番最初のパケットをメモリーから読み出し Reciever に送信する。Reciever 部 – 23 – 3.3 プログラム構成 では受け取ったデータをメモリに格納して、受け取ったパケットの世代番号をデータに持た せた後に ACK として Sender に送信するといったデータの流れをとる。 これよりプログラムに使用しているモジュールについての説明をおこなう。 • TCP フロー制御モジュール このモジュールは、TCP のフロー制御を行なうためのモジュールである。図 3.4 に作 成したモジュールの構成を示す。 ! " # $ 図 3.4 TCP フロー制御の送信側モジュール構成 それぞれのモジュールについて簡単に説明する 1. 世代付加モジュール – 24 – 3.4 受信部のプログラム構成 データ駆動では、世代と呼ばれる部分が一致したデータ同士でなければ演算をおこ なえない。 2. タイミングモジュール 今回のプログラムでは、メモリを用いてのカウンター機構を利用している。そのた め、カウンターの情報が更新される前にデータを参照されることを防ぐために、こ のモジュールを用いてカウンターに情報が更新されてから参照するようにタイミン グを取っている。 3. 再送制御モジュール このモジュールでは、TCP のもっとも重要な再送機能を処理しているモジュール である。このモジュールでは、帰ってきた ACK が重複しているかしていないかを 確認する。それによりデータを再送するかを判断している。 4. 輻輳ウィンドウ制御モジュール このモジュールでは、スロースタートと輻輳回避の輻輳制御を行なっているモ ジュールである。 5. パケットロードモジュール このモジュールでは、送信するべきパケット番号をデータとして格納し出力する。 6. パケットカウントモジュール このモジュールでは、現在送信しているパケット数と輻輳ウィンドウを比較してパ ケットがまだ送信可能であるかどうかを判断している。もし送信できるのであれ ば、ロードパケットにトリガーパケットを渡す。 3.4 受信部のプログラム構成 次に図 3.5 に受信部のプログラム構成の図を示す。 – 25 – 3.4 受信部のプログラム構成 図 3.5 TCP フロー制御の受信側モジュール構成 受信部での処理の基本的な流れとして、 1. 受信したデータをメモリに格納する 2. 受信したデータが再送されたデータかどうかを判断する 3. 受信したデータが再送されたデータでなければ ACK を生成し、送信側に ACK を送信 する もし、再送されたデータであれば、それまでに受け取ったデータを確認し、もっ とも最新のセグメント番号の ACK を生成して送信側に送信する – 26 – 3.5 プログラムの問題点・解決案 3.5 プログラムの問題点・解決案 今回構成したプログラムは、下記に示すような問題が発見された。 • プログラム構成の問題 作成したプログラムでは、フロー数分の制御モジュールを用意する必要がある。そのた め、扱うフロ ー数が増加するとプログラムサイズがその分だけ増加するプログラム構 成になっている。 また現在の構成では複数フローといっても、用意された処理モジュール分のフロー数し か処理できない問題もある。 • Timing モジュールの使用による問題 今回のプログラムでは、カウンターの情報が更新されるまで処理を行なわないようにす るために、Timing モジュールを利用している。このモジュールはカウンターの情報が 更新されるまで入力をループさせている。そのため、データの投入間隔を大きく開けた り、逆に縮めたりするとループする ACK の本数が多くなり、パイプラインが詰ってし まい動作しなくなる。 これらの問題を解決するためには、 1. プログラムの共有 2. 次状態の把握 をすることにより、問題を解決できると考えられる。 まず、プログラムを共有することにより、処理するフロー数が増えても、プログラムサイ ズは大きくはならない。共有する方法としては、現在も用いている識別子を用いることによ りプログラムの共有が可能であると考えられる。タイミングモジュールの問題を解決するた めには、それぞれの処理における次状態を定義してテーブルに格納ししておくことにより、 そのテーブルを参照することで次状態を把握するテーブル参照モジュールを追加する必要が あると考える。 – 27 – 3.5 プログラムの問題点・解決案 TCP はプロトコル処理であるために、入力に対して必ずアクションを起こすため、状態 遷移図等を用いることにより、次状態を把握することが可能である。 これらを考慮したプログラム構成を示す。 2 3 1 4 5 & ' 6 7 , 8 % & ' ( )* + . / 9 : , - 0 1 0 ! # " ! $ " 図 3.6 新提案プログラム構造 この考案したプログラムの説明を行なう。 • 世代付与 ここでは、後の作業をスムーズに行うために、世代の付け直しを行っている • FSM for TCP このモジュールで TCP フロー制御を行なっている。 ここで、FSM for TCP モジュール内のモジュールの説明する。 1. 入力分析で入力されたデータが送信データか ACK であるかの判断を行なっている。 2. 次状態 TBL 参照で、それぞれのフローの次状態を把握する 3. 分岐を行い、それぞれのフロー制御モジュールにデータを送る – 28 – 3.6 結言 4. データを送信する データの基本的な流れはこのようになっている。 TCP フロー制御を行なうプログラムを共有することにより、フロー数が増えてもプログ ラムを追加したりする必要がなくなり、またフロー数に関係なく複数フローを処理できるこ とが可能になる。 図 3.6 にあるように、次状態テーブル参照を用意することにより、それぞれのフローの次 状態を把握することが可能になる。これを用いることによりカウンターの更新を待たなくて も、どの状態に移ればよいかを判断できるために、Timing モジュールを使用せずにプログ ラムを構成可能になった。 3.6 結言 本章では、データ駆動を用いた TCP フロー制御のプログラムの構成を説明し、作成した プログラムを問題点を挙げた。また、その問題点を解決するための方法の提案を挙げ、それ に準ずるプログラムの構成を説明した。 – 29 – 第4章 性能評価 4.1 緒言 本章では、前章までに示した TCP フロー制御プログラムのデータ駆動での有効性を示す ために、DDMP シミュレータを用いて予備評価を行う。 比較方法として、DDMP を用いて作成した同じ TCP フロー制御モジュールにシングル フローを投入した場合とマルチフローを処理した場合の 2 つの性能を比較する。 4.2 評価環境 ここでは、作成した TCP フロー制御プログラムをシミュレーションで評価を行なう際の 性能の比較対象と評価環境について述べる。 今回の性能比較を行なった項目は以下ようになっている。 • スロースタートモードでのパケットの応答間隔を測定 (ここで述べている応答間隔は、上位層からデータが投入されてからデータが送信され るまでの時間を示している) • 輻輳回避モードでのスループット (Packet/step) (シミュレーションでは 1step を 3.5ns と定義されている) • 輻輳回避モードでの応答時間を計測 (応答時間の定義はスロースタート時と同じ) これらの項目でシングルフロー時とマルチフロー時のそれぞれにおいて測定を行い、評価 をおこなった。 – 30 – 4.3 性能評価結果 これらの評価を行なうことによって、今回作成したプログラムが DDMP の特徴である並 列処理を十分に生かしたプログラム構成になってるかを確認することができる。 また、今回評価を行なうにあたっての評価の環境としては以下のようになっている。 • 使用するシミュレーションは DDMP シミュレーション • シミュレーションに投入するパケットは DDMP パケットとする • シングルフローは 3000 パケットとする • マルチフローでは 1 フローを 1000 パケットとして、3 フローを投入 3000 パケットとする • パケットの投入間隔は 500step から 950step のものを測定 それぞれの性能を比較する 4.3 性能評価結果 前章で述べた比較内容と環境でプログラムの性能評価をおこなった。 以下の表に、各投入間隔ごとの評価結果を示す。 表 4.1 モジュールの多重処理効果 (500step) slowstart 輻輳回避 応答時間 スループット 応答時間 シングルフロー 57kstep 0.003pkt/step 1253kstep マルチフロー 60kstep 0.008pkt/step 1352kstep これらの結果より、どの場合のマルチフロー処理においてのスループットは約 3 倍程度の – 31 – 4.3 性能評価結果 表 4.2 モジュールの多重処理効果 (600step) slowstart 輻輳回避 応答時間 スループット 応答時間 シングルフロー 55kstep 0.003pkt/step 1138kstep マルチフロー 58kstep 0.008pkt/step 1283kstep 表 4.3 モジュールの多重処理効果 (700step) slowstart 輻輳回避 応答時間 スループット 応答時間 シングルフロー 52kstep 0.003pkt/step 1029kstep マルチフロー 56kstep 0.008pkt/step 1157kstep 表 4.4 モジュールの多重処理効果 (800step) slowstart 輻輳回避 応答時間 スループット 応答時間 シングルフロー 49kstep 0.003pkt/step 947kstep マルチフロー 53kstep 0.008pkt/step 1043kstep 表 4.5 モジュールの多重処理効果 (900step) slowstart 輻輳回避 応答時間 スループット 応答時間 シングルフロー 46kstep 0.003pkt/step 835kstep マルチフロー 48kstep 0.008pkt/step 923kstep – 32 – 4.4 結言 性能を示していることが確認できた。また、応答時間に関しても多少のばらつきは見られる が、ほぼシングルフロー時と同じ程度の応答時間であることも確認できた。 これにより、本研究で作成した TCP フロー制御プログラムは、並列処理に優れておりな おかつマルチ処理を施す際の処理オーバヘッドがほとんどなく TCP フロー制御処理がされ ていることが確認できた。 これにより今回作成した TCP フロー制御プログラムは DDMP の並列処理という特徴を 十分に生かしたプログラム構成になっていることを確認することができた。 4.4 結言 本章では、データ駆動方式を用いた TCP フロー制御プログラムの予備評価を行なった。 評価の結果、今回作成した TCP フロー制御プログラムは DDMP の特徴を十分に生かした プログラム構成になっていることを確認した。 – 33 – 第5章 結論 昨今の情報通信システムの進展は著しく、その恩恵は広く一般に浸透し、インターネット を始めとする様々な情報システムが社会基盤や生活基盤に不可欠になりつつある。また、モ バイル端末の普及を背景に、無線通信技術に一層の躍進が見られ、無線通信環境における多 様化な情報通信の実現が求められ、また、実現されつつある。特に一般に浸透したインター ネットを利便性の高い無線機器で利用することへの要求は大きく、インターネットの標準プ ロトコルである TCP を、無線環境下でも高い信頼性で疎通させるため、各所で Wireless TCP の研究がされるようになった。 しかし、無線通信では電波伝搬状況が非常に変化するため、TCP フロー制御における状 態遷移の頻度が高く、コネクション数に関係なく状態切替を高速にする必要がある。 本研究では複数のパケットストリームを多重に処理する能力に優れているデータ駆動型 チップマルチプロセッサを用いて、複数のフローが処理可能な TCP フロー制御プログラム を作成した。評価結果より、今回実装したプログラムがデータ駆動の特徴を活かしているこ とを示し、高速処理が可能であることを確認した。また、それによりマルチフロー処理時に 処理オーバヘッドがほとんどなく処理できることを示した。 今後の課題を以下に述べる • 提案した方式の高速化 今回提案した方式は、十分にデータ駆動の特徴を活かした構成となっているという結果 を得ることができているが、完全に多重処理時の処理オーバヘッドがなくなっているわ けではない。しかし、ソフトウェアでの高速化を図るには、プログラムの PE 割り当て – 34 – の最適化を行なうことにより可能だが、最適化を完璧に行なうことは非常に困難であ る。そのため、更に高速な TCP フロー制御プログラムをアーキテクチャレベルで検討 する必要があると考える。 • シミュレーションを用いての更なる性能評価 今回の性能評価では、複数フローは 3 フローとして評価を行なった。しかし、フロー 数、パケット数が増えることによる性能の著しい低下などが起こる可能性が考えられ る。そのため今後、更にフロー数を増やしてのシミュレーション性能評価を行なう必要 があると考える。 • DDMP 実機での評価 今回の性能評価は、DDMP シミュレーションを用いて評価を行なった。そのために、 DDMP 実機での評価も必要である。しかし、DDMP シミュレータはアーキテクチャ レベルでのシミュレーションなので、実機で評価を行なったとしても、大きな誤差は出 ないと考えている。 • TCP プロトコル実現のためのその他の制御プログラムの作成 今回のプログラムは、TCP フロー制御を行なうプログラムであり、その他の TCP ヘッ ダ解析やチェックサムといった処理プログラムを作成していない。TCP プロトコル処 理を実現するためには、残りの処理モジュールを作成する必要がある。 • Wireless 環境での性能評価 本研究は Wireless IP 向きの TCP フロー制御を実現することを目的としているため、 上記の課題を解決した後、実際の Wireless 環境での性能評価を行なう必要がある。今 回のシミュレーション評価結果より、実装したプログラムは高速処理可能で、複数フ ローをオーバヘッドなく並列処理できることを確認した。そのため実際の無線環境にお いて複数フローを並列に処理させた場合に集中同期型で既存方式を用いた場合との性能 比較を行い、DDMP での実装の優位性を示す必要がある。 – 35 – 謝辞 本研究に於いて懇切なる御指導、御鞭撻を賜った岩田 誠 教授に心より感謝の意を表し ます。 本研究の基礎としているデータ駆動型アーキテクチャを提唱された寺田 浩詔 教授に心よ り感謝の意を表します。 本研究に於いて、副査をお受け頂き、様々な御助言、御指導を賜った、島村 和典 教授、 浜村 昌則 講師 に心より感謝の意を表します。 本研究を進めるにあたり、適切なる御助言、御指導を賜った 大森 洋一助手 に深く感謝の 意を表します。 ご多忙の中、本研究の指導に貴重な時間を費やして頂いた、林 秀樹 氏、森川 大智 氏、 志摩 浩 氏に心より感謝の意を表します。 日頃から温かい御支援、並びに御助言を頂いた大学院博士課程の于 曉艶 氏に心より感謝 の意を表します。 日頃から温かい御支援、並びに御助言を頂いた大学院生の小倉 通寛 氏、三宮 秀次 氏、 中村 勲二 氏に、感謝の意を表します。 日頃から、多くの御意見、御支援を頂いた大学院生の、大石 祐子 氏、西山 直人 氏に 感謝の意を表します。 日頃から多くの御意見、御支援を頂いた岩田研究室の方々、朝日山 輝久 氏をはじめ、 小笠原 新二 氏、長野 祐介 氏、濱田 康裕 氏、山本 真弘 氏に感謝の意を表します。 日頃から御意見、御支援を頂いた岩田研究室の後輩の方々、河野 恵美 氏、嶋田 栄悟 氏、 高石 克也 氏、高橋 恵理子 氏、藤本 健太郎氏、松本 拓也 氏に感謝の意を表します。 – 36 – 参考文献 [1] H.Terada, et al. “DDMP’s: self-timed super pipelined data-driven multimedia process,” Proc. of IEEE,87(2), 282-296 [2] RFC 793 ”Transmission Control Protocol Darpa Internet Program Protocol Specification,” September 1982 [3] Janey C. Hoe ”Start-up Dynamics of TCP’s Congestion Control and Avoidance Schemes,” Submitted to the Department of Electrical Engineering and Computer Science on May 26, 1995 [4] RFC 2851 ”TCP Congestion Control,” April 1999 [5] RFC 2582 ”The NewReno Modification to TCP’s Fast Recovery Algorithm,” April 1999 [6] Kevin Fall and Sally Floyd,”Simulation-based Comparisons of Tahoe, Reno, and SACK TCP,”Computer Communication Review, 26(3):5-21, July 1996. [7] Lawrence S. Brakmo and L. Peterson,”TCP Vegas: End to End Congestion Avoidance on a Global Internet,” IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS. VOL. 13. NO.8.OCTOBER 1995, 1445-1480 [8] RFC 2018 ”TCP Selective Acknowledgment Options,” October 1996 – 37 –