The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Le problème de gestion du tampon en ligne formule le problème des politiques de mise en file d'attente des commutateurs réseau prenant en charge la garantie QoS (Qualité de Service). Pour ce problème, plusieurs modèles sont considérés. Dans cet article, nous nous concentrons sur les commutateurs de mémoire partagée avec préemption. Nous prouvons que le ratio de compétitivité de la plus longue file d'attente (LQD) la politique est (4M-4)/(3M-2) dans le cas de N=2, où N est le nombre de ports de sortie dans un commutateur et M est la taille du tampon. Cela correspond à la limite inférieure donnée par Hahne, Kesselman et Mansour. De plus, dans le cas d'arbitraire N, nous améliorons le ratio de compétitivité de LQD de 2 à 2 - (1/M) minutesK = 1, 2, ..., N{
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copier
Koji KOBAYASHI, Shuichi MIYAZAKI, Yasuo OKABE, "A Tight Bound on Online Buffer Management for Two-Port Shared-Memory Switches" in IEICE TRANSACTIONS on Information,
vol. E91-D, no. 8, pp. 2105-2114, August 2008, doi: 10.1093/ietisy/e91-d.8.2105.
Abstract: The online buffer management problem formulates the problem of queueing policies of network switches supporting QoS (Quality of Service) guarantee. For this problem, several models are considered.In this paper, we focus on shared memory switches with preemption. We prove that the competitive ratio of the Longest Queue Drop (LQD) policy is (4M-4)/(3M-2) in the case of N=2, where N is the number of output ports in a switch and M is the size of the buffer.This matches the lower bound given by Hahne, Kesselman and Mansour.Also, in the case of arbitrary N, we improve the competitive ratio of LQD from 2 to 2 - (1/M) minK = 1, 2, ..., N{
URL: https://global.ieice.org/en_transactions/information/10.1093/ietisy/e91-d.8.2105/_p
Copier
@ARTICLE{e91-d_8_2105,
author={Koji KOBAYASHI, Shuichi MIYAZAKI, Yasuo OKABE, },
journal={IEICE TRANSACTIONS on Information},
title={A Tight Bound on Online Buffer Management for Two-Port Shared-Memory Switches},
year={2008},
volume={E91-D},
number={8},
pages={2105-2114},
abstract={The online buffer management problem formulates the problem of queueing policies of network switches supporting QoS (Quality of Service) guarantee. For this problem, several models are considered.In this paper, we focus on shared memory switches with preemption. We prove that the competitive ratio of the Longest Queue Drop (LQD) policy is (4M-4)/(3M-2) in the case of N=2, where N is the number of output ports in a switch and M is the size of the buffer.This matches the lower bound given by Hahne, Kesselman and Mansour.Also, in the case of arbitrary N, we improve the competitive ratio of LQD from 2 to 2 - (1/M) minK = 1, 2, ..., N{
keywords={},
doi={10.1093/ietisy/e91-d.8.2105},
ISSN={1745-1361},
month={August},}
Copier
TY - JOUR
TI - A Tight Bound on Online Buffer Management for Two-Port Shared-Memory Switches
T2 - IEICE TRANSACTIONS on Information
SP - 2105
EP - 2114
AU - Koji KOBAYASHI
AU - Shuichi MIYAZAKI
AU - Yasuo OKABE
PY - 2008
DO - 10.1093/ietisy/e91-d.8.2105
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E91-D
IS - 8
JA - IEICE TRANSACTIONS on Information
Y1 - August 2008
AB - The online buffer management problem formulates the problem of queueing policies of network switches supporting QoS (Quality of Service) guarantee. For this problem, several models are considered.In this paper, we focus on shared memory switches with preemption. We prove that the competitive ratio of the Longest Queue Drop (LQD) policy is (4M-4)/(3M-2) in the case of N=2, where N is the number of output ports in a switch and M is the size of the buffer.This matches the lower bound given by Hahne, Kesselman and Mansour.Also, in the case of arbitrary N, we improve the competitive ratio of LQD from 2 to 2 - (1/M) minK = 1, 2, ..., N{
ER -