Tight Analysis of Priority Queuing for Egress Traffic

DOI10.1007/978-3-319-12691-3_34MaRDI QIDQ2942419zbMATH OpenOpenAlexFDO

Authors Jun Kawahara, Koji M. Kobayashi, Tomotaka Maeda

Publication date 11 September 2015

Published in Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1207.5959

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Queues and service in operations research (90B22) Deterministic scheduling theory in operations research (90B35)

Abstract: Recently, the problems of evaluating performances of switches and routers have been formulated as online problems, and a great amount of results have been presented. In this paper, we focus on managing outgoing packets (called {em egress traffic}) on switches that support Quality of Service (QoS), and analyze the performance of one of the most fundamental scheduling policies {em Priority Queuing} (

P Q

) using competitive analysis. We formulate the problem of managing egress queues as follows: An output interface is equipped with

m

queues, each of which has a buffer of size

B

. The size of a packet is unit, and each buffer can store up to

B

packets simultaneously. Each packet is associated with one of

m

priority values

a l p h a_{j}

(

1 l e q j l e q m

), where

a l p h a_{1} l e q a l p h a_{2} l e q c d o t s l e q a l p h a_{m}

,

a l p h a_{1} = 1

, and

a l p h a_{m} = a l p h a

and the task of an online algorithm is to select one of

m

queues at each scheduling step. The purpose of this problem is to maximize the sum of the values of the scheduled packets. For any

B

and any

m

, we show that the competitive ratio of

P Q

is exactly

2 - m i n_{x i n [1, m - 1]} f r a c a l p h a_{x + 1} s u m_{j = 1}^{x + 1} a l p h a_{j}

. That is, we conduct a complete analysis of the performance of

P Q

using worst case analysis. Moreover, we show that no deterministic online algorithm can have a competitive ratio smaller than

1 + f r a c a l p h a^{3} + a l p h a^{2} + a l p h a a l p h a^{4} + 4 a l p h a^{3} + 3 a l p h a^{2} + 4 a l p h a + 1

.

Recommendations

Cites work

Cited in

(2)

This page was built for publication: Tight Analysis of Priority Queuing for Egress Traffic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2942419)