文献

J-GLOBAL ID：201502214727408800   整理番号：15A1207275

2フレームスループット最大化に対する最適バッファ管理

Optimal buffer management for 2-frame throughput maximization

著者 (2件)： KAWAHARA Jun (Graduate School of Information Sci., Nara Inst. of Sci. and Technol., 8916-5 Takayama, Ikoma, Nara, 6300192, JPN) ,  KOBAYASHI Koji M. (National Inst. of Informatics, JPN)
資料名： Computer Networks  (Computer Networks)
巻： 91  ページ： 804-820  発行年： 2015年11月14日 
JST資料番号： A0360B  ISSN： 1389-1286  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 本論文は,ネットワークスイッチにおけるオンラインバッファ管理問題について,kフレームスループット最大化問題(k-FTM)と呼ぶ一変種を考察する。インターネット上で転送されるフレームと呼ぶ大規模データは,送信者により小さいkパケットに分割され,受信者は各フレームをフレームを構成するすべてのパケットが受信できる場合に限り再構成できる。パケットはインターネット上のネットワークスイッチを通過し,各スイッチはFIFOバッファを備え一時的に到着パケットを蓄積する。バッファサイズは有界であるため,若干のパケットはバッファが一杯ならば廃棄しなければならない。廃棄パケットを含むフレームは,もう再構成不可能である。本論文の目標は,再構成フレーム数の最大化である。Kesselmanらはこの問題を提案し,任意のオンラインアルゴリズムはk=2の場合でさえ非有界近似比を有することを示した。従って彼らは,k-FTMの「順序考慮」変種を考察した。彼らはそのアルゴリズムの近似比は,任意のB≧kに対し高々(2kB/f(B/k)+k),ここでBはバッファサイズ,fはfloor関数である。また彼らはB/f(2B/k)の下限を,2B≧kでかつkが2のべきである場合にも与えた。さらに彼らは貪欲アルゴリズムの近似比は,任意のB≧2とk=2に対し高々(11+8/(B-1))であることも証明した。筆者らはk=2に対する貪欲アルゴリズムを解析し,その近似比は任意のBに対し高々3であることを示し,従来の上限である4B/f(B/2)+2(≧10)を改善する。さらに筆者らは任意の決定性アルゴリズムの近似比は,もしk=2ならば任意のBに対し少なくとも3であることを示すが,これは筆者らの上限に一致する。Copyright 2015 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.

シソーラス用語： スイッチ ,  計算機リソース管理 ,  改良 ,  インターネット ,  パケット ,  *バッファ方式 ,  FIFO ,  バッファメモリ ,  通信制御 ,  再構成 ,  精度 ,  計算機アルゴリズム ,  信号フレーム ,  *パケット交換 ,  *最大化問題
準シソーラス用語： オンラインアルゴリズム ,  *スループット最大化 ,  ネットワークスイッチ ,  パケット廃棄 ,  バッファサイズ ,  *バッファ管理 ,  近似精度 ,  最適管理 ,  信号再構成 ,  貪欲法

分類 (2件)： 計算機網  (JC03000K) ,  交換・交換機  (ND11020E)

タイトルに関連する用語 (2件)： スループット最大化 ,  バッファ管理