2012 年度 卒業論文要旨 劣環境ネットワークにおける Time-Based TTL を用いたトラヒック削除法 学修番号 09175024 1 序論 小倉 凌太 指導教員 朝香 卓也 通信性能の最適化をめざす技術である．代表的なも のとして蓄積形転送や蓄積形運搬転送がある． インターネットは世界中を結ぶ情報交換・共有シス ノードのバッファサイズが有限である時にはメッ テムとして，社会・経済のインフラの役目を果たして セージの転送順序およびバッファサイズがオーバー いる． 「いつでも，どこでも，何でも，誰でも」がネッ フローした際のバッファ制御方式によってルーチング トワークにつながることにより，人々の生活をより豊 の性能が大きく変化する．バッファサイズ管理方式は かにする「ユビキタス社会」を実現させるための大き 大きく分けて”Early Deletion”と”Late Deletion”の 2 な可能性を示している．しかし，現実にはネットワー 種類に分別できる．Early Deletion には Time-Based クインフラの整備が整っていない場所が多くあるた そこで，ネットワークインフラのない環境下で情 TTL と呼ばれるメッセージの生存可能時間をメッセー ジ作成時に与え TTL が 0 になった際メッセージを削 除する方式が存在する．メッセージ TTL は明確な設 報を得るための手段として，Delay and Disruption 定方法が存在しない．ノードの行動パターンが可変 Tolerant Networking [1] (DTN もしくは劣環境ネッ トワーク）技術が注目されている．DTN は当初，惑 であったり，行動パターン自体があらかじめ分かって 星間通信に伴う伝搬遅延に耐えるネットワークのアー 一方，トランスポートプロトコルである TCP には， キテクチャとして提案されていたが，従来の TCP/IP TTL を動的に設定する方式が備わっている．TCP で を用いた通信と異なり，安定したネットワークが必要 は、RTO という値を算出し TTL を設定している． ないことと遅延に対しての耐性があることから従来 RTO とは，TCP におけるパケット送信後，パケット の方法では通信が不可能であった場所での通信方法 の喪失などで一定時間経過後も累積確認応答が変身 として期待されている． されない場合送信側がパケットを再送するまでの待 DTN を用いる環境では宛先までの適切な経路を 機時間を表すものである [2]．この時間は Round Trip 的確に求めることは困難である．そのため，既存の Time (RTT) から算出を行う．実測値を rtt，平滑化 した値を srtt とした場合，srtt は以下のように定義さ め，実現には至っていない． DTN ルーチングの環境では通信可能なノードに同一 内容のメッセージを次々とコピーしていく Epidemic いない場合は適切な TTL を与えることができない． れる． 型のルーチングを用いることがしばしばある．しか し，この方法ではメッセージが到達した後でもメッ セージが複製され続けるためネットワークに不必要 な負荷を与えるとともに，必要となるメッセージが届 きにくいという問題を発生させる．そのため，不必要 なメッセージの複製を抑制する必要がある． そこで，本研究では DTN におけるメッセージ TTL srtt = α ∗ srtt + (1 − α) ∗ rtt (1) ただし，α の推奨値は 0.9 といわれている． 平均偏差を v，計測値を m とすると平均偏差，RTO は以下の式によって算出される． v = v + 0.25(|m − srtt| − v) (2) RT O = 平滑化 rtt + 4 ∗ 平均偏差 (3) を改善することによりネットワーク上のトラヒック量 を削減することで，DTN の性能向上を目指す． 2 関連研究 DTN は時間的・空間的不連続性の下で end-to-end の通信を実現するための中継転送技術である．情報 の送信ノード，中継ノード，受信ノードが連携して， 情報伝達の時間・空間・符号化に関する制御を行い， 3 提案方式 本論文では DTN におけるメッセージの管理方法と して Time-Based TTL を用い，TTL を決定するアル ゴリズムとして TCP における RTO の考え方を用い た方式を提案する．以降この提案方式は O-TTL 制御 方式とする．また，本論文では TCP における RTO を O-RTO，RTT を O-RTT とする．特定の 2 ノード 間で繰り返しメッセージ転送を行う環境を前提とす る．O-RTO の計算式は以下のように定義する． O − RT O = 平滑化 O − RT T + 4 ∗ 平均偏差 (4) 計算時に利用する平滑化 O-RTT は以下のように 定義する． SO-RTT は平滑化された O-RTT を示す． また，平均偏差は RTO を算出する時と同様である． SO − RT T = α ∗ SO − RT T + (1 − α)O − RT T (5) O-TTL 制御方式の利点は大きく 2 つある．1 つ目 図 1: 条件２の時のシミュレーション結果 は，時間経過でトラヒックを削除できる点である．本 制御方式を用いることで，不必要なトラヒックが多く 表 1: バッファサイズ 10 の時のシミュレーション結果 存在したネットワークを必要なトラヒックのみにする こととなる．2 つ目は，TTL を自動で更新すること 項目 である．本制御方式を用いることで 1 回の通信ごと データ種類数 に TTL を更新していくため，よりおかれている環境 トラヒック量 に適した TTL を設定することができる． 4 シミュレーション結果 条件 1 条件 2 条件 3 5 10 20 11143 22515 27594 O-RTO 時のトラヒック量 1141 2480 2909 O-RTO 時の到達率 0.99 0.97 0.84 ると言える．バッファサイズが十分に確保できない場 本研究では，簡易モデルを用い計算機シミュレー 合，到達率の増加量が小さくなりトラヒック量が小さ ションを行った．人同士のすれ違い通信を想定してい い値で不必要に増加するトラヒックを削除すること るため人が携帯して使用する無線デバイスをノード ができるが，到達率がバッファサイズとデータの種類 として扱い，全ての人は Random Way Point に従い 数によるため，必ずしも有効であるとは言い難い． 移動しているものとする．ノード数は 100 個とする． 相手が持っておらず自分が持っているメッセージをす べて通信可能範囲内にいるノードの送信する．通信 可能範囲とは半径が 10m の円状とする．メッセージ がバッファサイズを超えた場合，FIFO 方式を採用す る．シミュレーション範囲は 100 ∗ 100m とする．シ ミュレーションでは時刻 0 にメッセージ送信を一斉に 行い，以降新規のメッセージは発生しないものとす る．評価項目はトラヒック量，データ到達率の２項目 である． 結果を図 1，表 1 に示す．図 1 から，O-RTO はト ラヒック量 2480，到達率 0.97 の時間をとることがわ かる．また表 1 からバッファサイズが十分に確保でき ている場合，O-RTO は到達率 0.95 以上の値をとる 5 結論 本論文では DTN の性能向上方法として，O-RTO を用い TTL を決めることで不必要に増加するトラ ヒックを削除する方法を提案した．結果，バッファサ イズが十分に確保できる時，本提案は有効であった． 今後はより現実的な採用可能性について検証する必 要があると考えられる． 今後の課題は簡易モデルではなく実環境に近い形 でのシミュレーション，あるいは到達率・トラヒック 量と各パラメータの変化ついての関係性について検 証する必要がある． ことがわかり，逆にバッファサイズが不十分の時，到 達率が低い値をとることがわかる．O-RTO 時のトラ ヒック量はデータ種類数に関係なく小さい値をとる． このことからバッファサイズが十分に確保できてい る場合，O-RTO を用いタイムアウト値を設定するこ とで到達率 0.95 以上で不必要に増加するトラヒック を削除することができるため，提案方式は有効であ 参考文献 [1] D. Demmer and K. Fall, ”DTLSR: Delay tolerant routing for developing regions,” ACM NSDR, pp.1-6, 2007. [2] M.Allman，V.Paxson and W.Tevens ”TCP Congestion Control，” RFC 2581, pp.2-8, 1999.
© Copyright 2024 ExpyDoc
