| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2020-10-23 15:40 先読みを許す2-遅延制限バッファ管理問題に対する最適なオンラインアルゴリズム ○小林浩二（東大）  COMP2020-15 |
|
| 抄録 | （和） | 遅延制限付きバッファ管理問題は，Kesselmanら（STOC 2001, SIAM Journal on Computing 33(3), 2004）によって提案された，Quality of Service対応のスイッチ内のバッファからのパケット転送に焦点をあてたオンライン問題であり，その定義は以下の通りである．時間の経過とともにパケットがバッファに到着する．各パケットには{em 到着時間}と{em 制限時間}と{em 価値}が設定されており，アルゴリズムは各整数時間にバッファから高々1つパケットを転送出来る．パケットをその到着時間以降にその制限時間までに転送した場合，アルゴリズムはその価値を{em 利得}として得る．本問題の目的は利得の最大化である．高々$s$回転送する機会があるパケットのみが到着する問題を{boldmath $s$}{em-遅延制限}問題と言い，$s geq 2$の場合，Hajek (CISS 2001)は任意の決定性アルゴリズムの競合比は$(1 + sqrt{5})/2 geq 1.618$以上であることを示した．また，Vesel{'y}ら(SODA 2019)はその競合比を達成するアルゴリズムを示した．B{"o}hmら（ISAAC 2016, Theoretical Computer Science 776, 2019）は$s = 2$の場合に，{em 先読み}の能力を導入した．先読みは次の時刻に到着するパケットをオンラインアルゴリズムが知ることが出来る能力であり，B{"o}hmらはこの能力を利用して競合比が$(-1 + sqrt{13})/2 leq 1.303$となる決定性アルゴリズムを設計した．また，先読みを利用した任意の決定性アルゴリズムの競合比が$(1 + sqrt{17})/4 geq 1.280$以上であることを示した． 本稿では，競合比が$(1 + sqrt{17})/4$となる先読みを用いた最適な決定性アルゴリズムを示す． |
| （英） | The bounded delay buffer management problem proposed by Kesselman et~al. (STOC 2001 and SIAM Journal on Computing 33(3), 2004) is an online problem focusing on buffer management of a switch supporting Quality of Service. The problem definition is as follows: Packets arrive to a buffer over time and each packet is specified by the {em release time}, {em deadline} and {em value}. An algorithm can transmit at most one packet from the buffer at each integer time and can gain its value as the {em profit} if transmitting a packet by its deadline after its release time. The objective of this problem is to maximize the gained profit. We say that an instance of the problem is {boldmath $s$}{em-bounded} if for any packet, an algorithm has at most $s$ chances to transmit it. For any $s geq 2$, Hajek (CISS 2001) showed that the competitive ratio of any deterministic algorithm is at least $(1 + sqrt{5})/2 geq 1.618$. Recently, Vesel{'y} et~al. (SODA 2019) designed an online algorithm matching the lower bound. B{"o}hm et al.~(ISAAC 2016 and Theoretical Computer Science 776, 2019) introduced the {em lookahead} ability to an online algorithm, and this ability enables the algorithm to know packets arriving at the next time step. For $s=2$, they showed that upper and lower bounds on the competitive ratio of any deterministic algorithm are $(-1 + sqrt{13})/2 leq 1.303$ and $(1 + sqrt{17})/4 geq 1.280$, respectively. In this paper, for the 2-bounded model with lookahead, we design an algorithm with a matching competitive ratio of $(1 + sqrt{17})/4$. |
|
| キーワード | （和） | オンラインバッファ管理 / 競合比解析 / 先読み / スケジューリングアルゴリズム / スイッチ / / / |
| （英） | online buffer management / competitive analysis / lookahead / scheduling algorithm / switch / / / | |
| 文献情報 | 信学技報, vol. 120, no. 209, COMP2020-15, pp. 26-32, 2020年10月. | |
| 資料番号 | COMP2020-15 | |
| 発行日 | 2020-10-16 (COMP) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2020-15 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2020-10-23 - 2020-10-23 |
| 開催地（和） | 大阪大学 |
| 開催地（英） | Osaka Univ. |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2020-10-COMP |
| 本文の言語 | 日本語 |
| タイトル（和） | 先読みを許す2-遅延制限バッファ管理問題に対する最適なオンラインアルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | Optimal online packet scheduling for 2-bounded delay buffer management with lookahead |
| サブタイトル（英） | |
| キーワード(1)（和/英） | オンラインバッファ管理 / online buffer management |
| キーワード(2)（和/英） | 競合比解析 / competitive analysis |
| キーワード(3)（和/英） | 先読み / lookahead |
| キーワード(4)（和/英） | スケジューリングアルゴリズム / scheduling algorithm |
| キーワード(5)（和/英） | スイッチ / switch |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 小林 浩二 / Koji M. Kobayashi / コバヤシ コウジ |
| 第1著者 所属（和/英） | 東京大学 (略称： 東大) The University of Tokyo (略称： UT) |
| 第2著者 氏名（和/英/ヨミ） | / / |
| 第2著者 所属（和/英） | (略称： ) (略称： ) |
| 第3著者 氏名（和/英/ヨミ） | / / |
| 第3著者 所属（和/英） | (略称： ) (略称： ) |
| 第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著者 所属（和/英） | (略称： ) (略称： ) |
| 講演者 | 第1著者 |
| 発表日時 | 2020-10-23 15:40:00 |
| 発表時間 | 35分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2020-15 |
| 巻番号（vol） | vol.120 |
| 号番号（no） | no.209 |
| ページ範囲 | pp.26-32 |
| ページ数 | 7 |
| 発行日 | 2020-10-16 (COMP) |
[研究会発表申込システムのトップページに戻る]