A Tight Bound on Online Buffer Management for Two-Port Shared-Memory Switches

Koji KOBAYASHI  Shuichi MIYAZAKI  Yasuo OKABE  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E91-D   No.8   pp.2105-2114
Publication Date: 2008/08/01
Online ISSN: 1745-1361
DOI: 10.1093/ietisy/e91-d.8.2105
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Computation and Computational Models
Keyword: 
competitive analysis,  shared memory switches,  buffer management,  

Full Text: PDF(258.9KB)>>
Buy this Article




Summary: 
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{M/K + K - 1}.