کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6875542 1441966 2018 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Online buffer management for transmitting packets with processing cycles
ترجمه فارسی عنوان
مدیریت بافر آنلاین برای انتقال بسته با چرخه پردازش
کلمات کلیدی
مدیریت بافر، تحلیل رقابتی، برنامه ریزی آنلاین، اجرای تا تکمیل،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
In this study, we consider the model with constant density from a theoretical perspective. We first propose some lower bounds for the problem. Azar and Gilon obtained a 4-competitive algorithm for the online buffer management problem for packets with constant density. Here, we present a (2+1B−1)-competitive algorithm for the case B>1 as well as its generalization to the multi-buffer model. Moreover, we prove that the competitive ratio of a deterministic online algorithm is at least four when the buffer size is one. We also conduct experiments to demonstrate the superior performance of the proposed online algorithm against the previous approach.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 723, 2 May 2018, Pages 73-83
نویسندگان
, , , ,