スライディングウインドウを考慮したDynamicTCPAclmowledgment問題

• Item type: SIG Technical Reports(1)
• 公開日: 2007-01-23
• タイトル: スライディングウインドウを考慮したDynamicTCPAclmowledgment問題
• タイトル / 言語: en
• タイトル: Dynamic TCP Acknowledgment with Sliding Window
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 電気通信大学大学院情報システム学研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Systems University of Electro-Communications
• 著者名: 古賀, 久志
• 著者名(英): Hisashi, Koga
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: ＴＯＰプロトコルにおける通信では受信者はパケットを受信すると到達確認(acknowledgment 以下ack)を送信者に返して，送信が成功したことを知らせる．受信者は各到着パケットに１度ずつackを返すのではなく，複数の到着パケットに対して１度のackでまとめて到達確認を済ますことが出来る．この機構を使うとａｃｋ回数を減らせるが 逆に送信ホストによる到達確認が遅れ通信が遅滞するという欠点もある．DynamicTCPacknowledgment問題はこのトレードオフに対するオンライン最適化問題である．しかしながら、従来のDynamicTCPAcknowledgement問題の枠組では 受信者がackをなかなか返さない場合に送信者が自主的に送信を抑えるスライディングウインドウの機構を考慮していない．そこで本研究では スライディングウインドウの機構を組み込んだDynamicTCPAcknowledgement問題を定式化して オンラインアルゴリズムの性能を競合比解析を用いて評価する．特にウインドウサイズが固定値Ｗであると仮定して解析を行い 受信者がＷを知らされていれば２－competitiveなオンラインアルゴリズムを構築できるのに対し，Ｗを知らされていない場合には 従来の枠組での最適オンラインアルゴリズムを含むアルゴリズムクラスの競合比の下限値が送信者が送ろうとする単位時間辺りの最大パケット数に依存してしまうことを示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In TCP protocol, each packet arriving at the receiver must be acknowledged by the receiver in order to notify the sender that the transmission was successful. However, each packet need not be acknowledged individually. Instead, the receiver is allowed to acknowledge multiple packets with a single acknowledgement by postponing the acknowledgement. Though this mechanism is advantageous with respect to reduce the number of acknowledgements, delaying acknowledgements may add excessive latency to the TCP connection. Dooly et al. formulated this trade-off as the dynamic TCP acknowledgement problem. However, their framework does not consider the concept of sliding window that restricts the maximum number of packets that the sender can inject into the network without notified acknowledgements. In this paper, we propose a new problem in which the sliding window is integrated into the dynamic TCP acknowledgement problem realistically. We evaluate the performance of on-line algorithms with competitive analysis, assuming that the window size is a constant integer W>\. We show that there exists a 2-competitive deterministic on-line algorithm if on-line algorithms know the value of W beforehand. By contrast, if they do not know W, the lower bound of the competitive ratio for an algorithm class containing the optimal on-line algorithm for the original framework by Dooly et al. that is 2-competitive now depends on the maximum number of packets that the sender wishes to send per unit time.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2007, 号 5(2007-AL-110), p. 1-8, 発行日 2007-01-23
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会