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

• KOBAYASHI Koji

  Graduate School of Informatics, Kyoto University

• MIYAZAKI Shuichi

  Academic Center for Computing and Media Studies, Kyoto University The Institute of Electronics, Information and Communication Engineers

• OKABE Yasuo

  Academic Center for Computing and Media Studies, Kyoto University The Institute of Electronics, Information and Communication Engineers

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/Mmin_k=1,2,…,N{[M/k]+K-1}.

Journal

• IEICE Transactions on Information and Systems

  IEICE Transactions on Information and Systems E91-D (8), 2105-2114, 2008

  The Institute of Electronics, Information and Communication Engineers

Keywords

• competitive analysis
• shared memory switches
• buffer management

Details

• CRID: 1390001204377755648
• NII Article ID: 10026805230
• NII Book ID: AA10826272
• DOI: 10.1093/ietisy/e91-d.8.2105
• ISSN: 17451361
• ISSN: 09168532
• Web Site: https://www.jstage.jst.go.jp/article/transinf/E91.D/8/E91.D_8_2105/_pdf
• Text Lang: en
• Data Source:
  • JaLC
  • Crossref
  • CiNii Articles
• Abstract License Flag: Disallowed