オンラインフレーム転送量最大化問題における競合比の改良

Abstract

本稿では, k個のパケットからなるフレーム転送量最大化問題(k-FTM)と呼ばれる, ネットワーク上におけるスイッチのオンラインバッファ管理問題の一問題について考える.本問題は, 大きなフレームがk個のパケットに分割されてインターネット上で転送され, 受信者はk個全てのパケットを受信できたときに限りフレームを再構成可能という状況をモデル化したものである. Kesselmanらは本問題に対して, k=2の場合でさえ任意のアルゴリズムの競合比は発散することを示した.そこで, 入力に制限を加えたk-FTM (k-OFTM)を考え, 任意のバッファの大きさB(≧k)に対して, その競合比が高々(2kB)/([B/k])+kとなるアルゴリズムを考案した.また, 彼らは2B≧kかつkが2の冪のとき, 任意の決定性アルゴリズムの競合比の下限B/([2B/k])=Ω(k)を示した.本稿において, 我々はk-OFTMに対する競合比の上限と下限を改良している.主要な結果として, 彼らの上界O(k^2)を(5B+[B/k]-4)/([[B/k]/2])=O(k)へ改良し, 下界Ω(k)に漸近的に一致させている.また, 任意のk≧2と任意のBに対する, 決定性アルゴリズムの競合比の下限2k-1と, 任意のk≧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 (2kB)/([B/k])+k for any B≧k, where B is the size of the buffer. They also presented a lower bound of B/([2B/k])=Ω(k) for deterministic online algorithms when 2B≧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 (5B+[B/k]-4)/([B/2k])=O(k) for B≧2k, which matches their lower bound of Ω(k) asymptotically. We also present an improved lower bound of (2B)/([B/(k-1)])+1 on the competitive ratio of deterministic online algorithms for any k≧2 and any B≧k-1, and the first nontrivial lower bound of k-1 on the competitive ratio of randomized algorithms for any k≧3 and any B.