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
O problema de gerenciamento de buffer online formula o problema de políticas de enfileiramento de switches de rede que suportam garantia de QoS (Qualidade de Serviço). Para este problema, vários modelos são considerados. Neste artigo, focamos em switches de memória compartilhada com preempção. Provamos que a relação competitiva da Queda de Fila Mais Longa (LQD) a política é (4M-4)/(3M-2) no caso de N=2, onde N é o número de portas de saída em um switch e M é o tamanho do buffer.Isso corresponde ao limite inferior fornecido por Hahne, Kesselman e Mansour.Além disso, no caso de arbitrário N, melhoramos a relação competitiva de LQD de 2 a 2 - (1/M) minK = 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.
Copiar
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
Copiar
@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},}
Copiar
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 -