Improved Competitive Ratios of Online Buffer Management Algorithms for Multi-Queue Switches in QoS Networks

摘要

The online buffer management problem formulates the problem of queuing policies of network switches supporting QoS (Quality of Service) guarantee. For this problem, a lot of models have been considered. Among others, we focus on multi-queue switches in QoS Networks proposed by Azar et alAzar et al introduced the relaxed model in order to achieve a good upper bound on the competitive ratio for this model. In this paper, we improve the competitive ratios of several multi-queue models by improving an upper bound for the relaxed model. We propose an online algorithm DS (Dual Scheduling) for the relaxed model. This algorithm works for (either preemptive or non-preemptive) 2-value model, but it uses as subroutines online algorithms for the non-preemptive unit-value model, which has been extensively studied. The performance of DS depends on the performance of the algorithms used as subroutines. The followings are a couple of examples of the improvement on the competitive ratios of multi-queue models using our result: (i) We improved the competitive ratio of deterministic algorithms for the non-preemptive 2-value model from 4 to 3.177 for large enough B. a switch can store up to B packets simultaneously, (ii) We proved that the competitive ratio of randomized algorithms for the non-preemptive 2-value model is at most 17/2-30~(1/2) ≌ 3.023 for large enough B.%オンラインバッファ管理問題は，近年のネットワークにおける主要な論点となっているQoS（Quality of Service）保証実現のための，スイッチのキュー管理をオンライン問題として定式化した問題であり，様々なモデルが考案されている．本論文ではAzarらによって考案されたQoSネットワーク上のマルチキュースイッチを扱ったモデルを取り上げる．Azarらは本モデルの競合比の上限を得るために，“the relaxed model”というモデルを導入している．我々はrelaxed modelに対するオンラインアルゴリズムDSを提案することにより競合比を改良し，その結果としてマルチキュースイッチモデルの競合比の改良を行った．以下は本論文におけるマルチキュースイッチモデルの競合比の改良の一例である．（i）プリエンプション不可能，かつパケットの価値が2値であるモデルにおいて，十分大きなBに対して，決定性アルゴリズムの競合比の上限を4から3．177に改良した．Bは各キューが同時に保持できるパケットの最大数である．（ii）プリエンプション不可能，かつパケットの価値が2値であるモデルにおいて，十分大きなBに対して，乱択アルゴリズムの競合比の上限が高々17/2-30~(1/2) ≌3.023であることを示した.