Paper Abstract and Keywords |
Presentation |
2020-10-23 15:40
Optimal online packet scheduling for 2-bounded delay buffer management with lookahead Koji M. Kobayashi (UT) COMP2020-15 |
Abstract |
(in Japanese) |
(See Japanese page) |
(in English) |
The bounded delay buffer management problem proposed by Kesselman et~al. (STOC 2001 and SIAM Journal on Computing 33(3), 2004) is an online problem focusing on buffer management of a switch supporting Quality of Service. The problem definition is as follows: Packets arrive to a buffer over time and each packet is specified by the {em release time}, {em deadline} and {em value}. An algorithm can transmit at most one packet from the buffer at each integer time and can gain its value as the {em profit} if transmitting a packet by its deadline after its release time. The objective of this problem is to maximize the gained profit. We say that an instance of the problem is {boldmath $s$}{em-bounded} if for any packet, an algorithm has at most $s$ chances to transmit it. For any $s geq 2$, Hajek (CISS 2001) showed that the competitive ratio of any deterministic algorithm is at least $(1 + sqrt{5})/2 geq 1.618$. Recently, Vesel{'y} et~al. (SODA 2019) designed an online algorithm matching the lower bound. B{"o}hm et al.~(ISAAC 2016 and Theoretical Computer Science 776, 2019) introduced the {em lookahead} ability to an online algorithm, and this ability enables the algorithm to know packets arriving at the next time step. For $s=2$, they showed that upper and lower bounds on the competitive ratio of any deterministic algorithm are $(-1 + sqrt{13})/2 leq 1.303$ and $(1 + sqrt{17})/4 geq 1.280$, respectively.
In this paper, for the 2-bounded model with lookahead, we design an algorithm with a matching competitive ratio of $(1 + sqrt{17})/4$. |
Keyword |
(in Japanese) |
(See Japanese page) |
(in English) |
online buffer management / competitive analysis / lookahead / scheduling algorithm / switch / / / |
Reference Info. |
IEICE Tech. Rep., vol. 120, no. 209, COMP2020-15, pp. 26-32, Oct. 2020. |
Paper # |
COMP2020-15 |
Date of Issue |
2020-10-16 (COMP) |
ISSN |
Online edition: ISSN 2432-6380 |
Copyright and reproduction |
All rights are reserved and no part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopy, recording, or any information storage and retrieval system, without permission in writing from the publisher. Notwithstanding, instructors are permitted to photocopy isolated articles for noncommercial classroom use without fee. (License No.: 10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
Download PDF |
COMP2020-15 |
Conference Information |
Committee |
COMP |
Conference Date |
2020-10-23 - 2020-10-23 |
Place (in Japanese) |
(See Japanese page) |
Place (in English) |
Osaka Univ. |
Topics (in Japanese) |
(See Japanese page) |
Topics (in English) |
|
Paper Information |
Registration To |
COMP |
Conference Code |
2020-10-COMP |
Language |
Japanese |
Title (in Japanese) |
(See Japanese page) |
Sub Title (in Japanese) |
(See Japanese page) |
Title (in English) |
Optimal online packet scheduling for 2-bounded delay buffer management with lookahead |
Sub Title (in English) |
|
Keyword(1) |
online buffer management |
Keyword(2) |
competitive analysis |
Keyword(3) |
lookahead |
Keyword(4) |
scheduling algorithm |
Keyword(5) |
switch |
Keyword(6) |
|
Keyword(7) |
|
Keyword(8) |
|
1st Author's Name |
Koji M. Kobayashi |
1st Author's Affiliation |
The University of Tokyo (UT) |
2nd Author's Name |
|
2nd Author's Affiliation |
() |
3rd Author's Name |
|
3rd Author's Affiliation |
() |
4th Author's Name |
|
4th Author's Affiliation |
() |
5th Author's Name |
|
5th Author's Affiliation |
() |
6th Author's Name |
|
6th Author's Affiliation |
() |
7th Author's Name |
|
7th Author's Affiliation |
() |
8th Author's Name |
|
8th Author's Affiliation |
() |
9th Author's Name |
|
9th Author's Affiliation |
() |
10th Author's Name |
|
10th Author's Affiliation |
() |
11th Author's Name |
|
11th Author's Affiliation |
() |
12th Author's Name |
|
12th Author's Affiliation |
() |
13th Author's Name |
|
13th Author's Affiliation |
() |
14th Author's Name |
|
14th Author's Affiliation |
() |
15th Author's Name |
|
15th Author's Affiliation |
() |
16th Author's Name |
|
16th Author's Affiliation |
() |
17th Author's Name |
|
17th Author's Affiliation |
() |
18th Author's Name |
|
18th Author's Affiliation |
() |
19th Author's Name |
|
19th Author's Affiliation |
() |
20th Author's Name |
|
20th Author's Affiliation |
() |
Speaker |
Author-1 |
Date Time |
2020-10-23 15:40:00 |
Presentation Time |
35 minutes |
Registration for |
COMP |
Paper # |
COMP2020-15 |
Volume (vol) |
vol.120 |
Number (no) |
no.209 |
Page |
pp.26-32 |
#Pages |
7 |
Date of Issue |
2020-10-16 (COMP) |
|