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

スポンサーリンク

概要

• 論文の詳細を見る

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

• （社）電子情報通信学会の論文
• 2008-08-01

著者

• Okabe Yasuo

  Kyoto Univ. Kyoto Jpn

• Okabe Yasuo

  Academic Center For Computing And Media Studies Kyoto University

• MIYAZAKI Shuichi

  Academic Center for Computing and Media Studies, Kyoto University

• KOBAYASHI Koji

  Graduate School of Informatics, Kyoto University

• Miyazaki Shuichi

  Kyoto Univ. Kyoto‐shi Jpn

• Miyazaki Shuichi

  Academic Center For Computing And Media Studies Kyoto University

• Kobayashi Koji

  Graduate School Of Informatics Kyoto University

関連論文

• A (2-c(logN)/N)-Approximation Algorithm for the Stable Marriage Problem(Invited Papers from New Horizons in Computing)
• Computational Complexities of University Interview Timetabling
• Multi-Bit Embedding in Asymmetric Digital Watermarking without Exposing Secret Information
• Unsupervised Anomaly Detection Based on Clustering and Multiple One-Class SVM
• A Tight Upper Bound on Online Buffer Management for Multi-Queue Switches with Bicodal Buffers
• A Tight Bound on Online Buffer Management for Two-Port Shared-Memory Switches
• A Clustering Method for Improving Performance of Anomaly-Based Intrusion Detection System
• A Comparative Study of Unsupervised Anomaly Detection Techniques Using Honeypot Data
• The Online Graph Exploration Problem on Restricted Graphs
• Special Section on New Challenge for Internet Technology and its Architecture
• Special Section on Discrete Mathematics and Its Applications
• FOREWORD

もっと見る 閉じる

スポンサーリンク