| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2014-04-24 15:15 オンラインフレーム転送量最大化問題における競合比の改良 小林浩二（NII）・○川原 純（奈良先端大）・宮崎修一（京大）  COMP2014-6 |
|
| 抄録 | （和） | 本稿では，$k$個のパケットからなるフレーム転送量最大化問題（$k$-FTM）と呼ばれる，ネットワーク上におけるスイッチのオンラインバッファ管理問題の一問題について考える．本問題は，大きなフレームが$k$個のパケットに分割されてインターネット上で転送され，受信者は$k$個全てのパケットを受信できたときに限りフレームを再構成可能という状況をモデル化したものである．Kesselmanらは本問題に対して，$k=2$の場合でさえ任意のアルゴリズムの競合比は発散することを示した．そこで，入力に制限を加えた$k$-FTM（$k$-OFTM）を考え，任意のバッファの大きさ$B (geq k)$に対して，その競合比が高々$frac{ 2kB }{ lfloor B/k rfloor } + k$となるアルゴリズムを考案した．また，彼らは$2B geq k$かつ$k$が2の冪のとき，任意の決定性アルゴリズムの競合比の下限$frac{ B }{ lfloor 2B/k rfloor}=Omega(k)$を示した． 本稿において，我々は$k$-OFTMに対する競合比の上限と下限を改良している．主要な結果として，彼らの上界$O(k^{2})$を$frac{5B + lfloor B/k rfloor - 4}{lfloor lfloor B/k rfloor / 2 rfloor} = O(k)$へ改良し，下界$Omega(k)$に漸近的に一致させている．また，任意の$k geq 2$と任意の$B$に対する，決定性アルゴリズムの競合比の下限$2k-1$と，任意の$k geq 3$と任意の$B$に対する，確率アルゴリズムの初めての非自明な競合比の下限$k-1$を与える． |
| （英） | We consider a variant of the online buffer management problem in network switches, called the $k$-frame throughput maximization problem ($k$-FTM). This problem models the situation where a large frame is fragmented into $k$ packets and transmitted through the Internet, and the receiver can reconstruct the frame only if he/she accepts all the $k$ packets. Kesselman et~al. introduced this problem and showed that its competitive ratio is unbounded even when $k=2$. They also introduced a restricted variant of $k$-FTM, called $k$-OFTM. They proposed an online algorithm and showed that its competitive ratio is at most $frac{ 2kB }{ lfloor B/k rfloor } + k$ for any $B ge k$, where $B$ is the size of the buffer. They also presented a lower bound of $frac{ B }{ lfloor 2B/k rfloor } = Omega(k)$ for deterministic online algorithms when $2B geq k$ and $k$ is a power of $2$. In this paper, we improve upper and lower bounds on the competitive ratio of $k$-OFTM. Our main result is to improve an upper bound of $O(k^{2})$ by Kesselman et~al. to $frac{5B + lfloor B/k rfloor - 4}{lfloor B/2k rfloor} = O(k)$ for $Bgeq 2k$, which matches their lower bound of $Omega(k)$ asymptotically. We also present an improved lower bound of $frac{2B}{lfloor {B/(k-1)} rfloor} + 1$ on the competitive ratio of deterministic online algorithms for any $k geq 2$ and any $B geq k-1$, and the first nontrivial lower bound of $k-1$ on the competitive ratio of randomized algorithms for any $k geq 3$ and any $B$. |
|
| キーワード | （和） | オンライン問題 / 競合比解析 / バッファ管理 / パケット断片化 / / / / |
| （英） | Online Problem / Competitive Analysis / Buffer Management / Packet Fragmentation / / / / | |
| 文献情報 | 信学技報, vol. 114, no. 19, COMP2014-6, pp. 37-44, 2014年4月. | |
| 資料番号 | COMP2014-6 | |
| 発行日 | 2014-04-17 (COMP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2014-6 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2014-04-24 - 2014-04-24 |
| 開催地（和） | 東北大学 |
| 開催地（英） | Tohoku University |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2014-04-COMP |
| 本文の言語 | 日本語 |
| タイトル（和） | オンラインフレーム転送量最大化問題における競合比の改良 |
| サブタイトル（和） | |
| タイトル（英） | Improved Bounds for Online $k$-Frame Throughput Maximization in Network Switches |
| サブタイトル（英） | |
| キーワード(1)（和/英） | オンライン問題 / Online Problem |
| キーワード(2)（和/英） | 競合比解析 / Competitive Analysis |
| キーワード(3)（和/英） | バッファ管理 / Buffer Management |
| キーワード(4)（和/英） | パケット断片化 / Packet Fragmentation |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 小林 浩二 / Koji Kobayashi / コバヤシ コウジ |
| 第1著者 所属（和/英） | 国立情報学研究所 (略称： NII) National Institute of Informatics (略称： NII) |
| 第2著者 氏名（和/英/ヨミ） | 川原 純 / Jun Kawahara / カワハラ ジュン |
| 第2著者 所属（和/英） | 奈良先端科学技術大学院大学 (略称： 奈良先端大) Nara Institute of Science and Technology (略称： NAIST) |
| 第3著者 氏名（和/英/ヨミ） | 宮崎 修一 / Shuichi Miyazaki / ミヤザキ シュウイチ |
| 第3著者 所属（和/英） | 京都大学 (略称： 京大) Kyoto University (略称： Kyoto Univ.) |
| 第4著者 氏名（和/英/ヨミ） | / / |
| 第4著者 所属（和/英） | (略称： ) (略称： ) |
| 第5著者 氏名（和/英/ヨミ） | / / |
| 第5著者 所属（和/英） | (略称： ) (略称： ) |
| 第6著者 氏名（和/英/ヨミ） | / / |
| 第6著者 所属（和/英） | (略称： ) (略称： ) |
| 第7著者 氏名（和/英/ヨミ） | / / |
| 第7著者 所属（和/英） | (略称： ) (略称： ) |
| 第8著者 氏名（和/英/ヨミ） | / / |
| 第8著者 所属（和/英） | (略称： ) (略称： ) |
| 第9著者 氏名（和/英/ヨミ） | / / |
| 第9著者 所属（和/英） | (略称： ) (略称： ) |
| 第10著者 氏名（和/英/ヨミ） | / / |
| 第10著者 所属（和/英） | (略称： ) (略称： ) |
| 第11著者 氏名（和/英/ヨミ） | / / |
| 第11著者 所属（和/英） | (略称： ) (略称： ) |
| 第12著者 氏名（和/英/ヨミ） | / / |
| 第12著者 所属（和/英） | (略称： ) (略称： ) |
| 第13著者 氏名（和/英/ヨミ） | / / |
| 第13著者 所属（和/英） | (略称： ) (略称： ) |
| 第14著者 氏名（和/英/ヨミ） | / / |
| 第14著者 所属（和/英） | (略称： ) (略称： ) |
| 第15著者 氏名（和/英/ヨミ） | / / |
| 第15著者 所属（和/英） | (略称： ) (略称： ) |
| 第16著者 氏名（和/英/ヨミ） | / / |
| 第16著者 所属（和/英） | (略称： ) (略称： ) |
| 第17著者 氏名（和/英/ヨミ） | / / |
| 第17著者 所属（和/英） | (略称： ) (略称： ) |
| 第18著者 氏名（和/英/ヨミ） | / / |
| 第18著者 所属（和/英） | (略称： ) (略称： ) |
| 講演者 | 第2著者 |
| 発表日時 | 2014-04-24 15:15:00 |
| 発表時間 | 35分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2014-6 |
| 巻番号（vol） | vol.114 |
| 号番号（no） | no.19 |
| ページ範囲 | pp.37-44 |
| ページ数 | 8 |
| 発行日 | 2014-04-17 (COMP) |
[研究会発表申込システムのトップページに戻る]