Source author record

Seiji Yoshimoto

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Discrete Mathematics

Catalog footprint

Research overview

2works

2topics

1close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2013arXiv

Buffer Management of Multi-Queue QoS Switches with Class Segregation

In this paper, we focus on buffer management of multi-queue QoS switches in which packets of different values are segregated in different queues. Our model consists of $m$ queues and $m$ packet values $0 < v_{1} < v_{2} < ... < v_{m}$ . Recently, Al-Bawani and Souza [IPL 113(4), pp.145-150, 2013] presented an online algorithm GREEDY for buffer management of multi-queue QoS switches with class segregation and showed thatif $m$ queues have the same size, then the competitive ratio of GREEDY is $1+r$ , where $r=\max_{1 \leq i \leq m-1} v_{i}/v_{i+1}$ . In this paper, we precisely analyze the behavior of GREEDY and show that it is $(1+r)$ -competitive for the case that $m$ queues do not necessarily have the same size.

preprint2011arXiv

Greedy Algorithms for Multi-Queue Buffer Management with Class Segregation

In this paper, we focus on a multi-queue buffer management in which packets of different values are segregated in different queues. Our model consists of m packets values and m queues. Recently, Al-Bawani and Souza (arXiv:1103.6049v2 [cs.DS] 30 Mar 2011) presented an online multi-queue buffer management algorithm Greedy and showed that it is 2-competitive for the general m-valued case, i.e., m packet values are 0 < v_{1} < v_{2} < ... < v_{m}, and (1+v_{1}/v_{2})-competitive for the two-valued case, i.e., two packet values are 0 < v_{1} < v_{2}. For the general m-valued case, let c_i = (v_{i} + \sum_{j=1}^{i-1} 2^{j-1} v_{i-j})/(v_{i+1} + \sum_{j=1}^{i-1}2^{j-1}v_{i-j}) for 1 \leq i \leq m-1, and let c_{m}^{*} = \max_{i} c_{i}. In this paper, we precisely analyze the competitive ratio of Greedy for the general m-valued case, and show that the algorithm Greedy is (1+c_{m}^{*})-competitive.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.