Laboratory of Mathematical Logic at PDMI

Понедельник, 26 ноября, ауд. 106. Начало в 13:00.

Докладчик: Сергей Николенко (ПОМИ РАН).

Тема: FIFO Queueing Policies for Packets with Heterogeneous Processing: How Laziness Proves Upper Bounds.

Abstract

Modern network processors (NPs) increasingly deal with packets that require heterogeneous processing. We consider the problem of managing a bounded size input queue buffer where each packet requires several rounds of processing before it can be transmitted out. The goal of admission control policies is to maximize the total number of successfully transmitted packets. Processing order can have a significant impact on the performance of buffer management policies even if the order of transmission is fixed. We introduce a new class of policies (semi-FIFO, with lazy policies being the most important innovation) and prove lower and upper bounds on the competitive ratio of these policies. Further, we conduct a comprehensive simulation study that validates our results.

Доклад по работам:

1. K. Kogan, A. Lòpez-Ortiz, S.I. Nikolenko, A.V. Sirotkin. A Taxonomy of Semi-FIFO Policies. Accepted to the 31st IEEE International Performance Computing and Communications Conference (IPCCC 2012).

2. K. Kogan, A. Lòpez-Ortiz, S.I. Nikolenko, A.V. Sirotkin, D. Tugaryov. FIFO Queueing Policies for Packets with Heterogeneous Processing, Accepted to the 1st Mediterranean Conference on Algorithms (MedAlg 2012), arXiv:1204.5443v1 [cs.NI].