کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
450737 694133 2015 17 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Optimal buffer management for 2-frame throughput maximization
ترجمه فارسی عنوان
مدیریت بافر بهینه برای به حداکثر رساندن حداکثر 2 کاراکتر
کلمات کلیدی
تحلیل رقابتی، مدیریت بافر آنلاین، قطعه قطعه بسته الگوریتم حریص
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر شبکه های کامپیوتری و ارتباطات
چکیده انگلیسی

We consider a variant of the online buffer management problem in network switches, called the k-frame throughput maximization problem (k-FTM). Large data, called frames, carried on the Internet are split into small k packets by a sender, and the receiver can reconstruct each frame only if he/she accepts all the k   constituent packets of the frame. Packets pass through network switches on the Internet, and each switch is equipped with a FIFO buffer to temporarily store arriving packets. Since the size of the buffer is bounded, some packets must be discarded if it is full. It is impossible to reconstruct frames including discarded packets any more. Our goal is to maximize the number of reconstructed frames. Kesselman et al. proposed this problem, and showed that any online algorithm has an unbounded competitive ratio even when k=2k=2. Hence, they considered the “order-respecting” variant of k  -FTM. They showed that the competitive ratio of their algorithm is at most (2kB⌊B/k⌋+k) for any B ≥ k, where B   is the size of the buffer. Also, they gave a lower bound of B⌊2B/k⌋ on the competitive ratio when 2B ≥ k and k   is a power of 2. Furthermore, they proved that the competitive ratio of a greedy algorithm is at most (11+8B−1) for any B   ≥ 2 and k=2k=2.We analyze a greedy algorithm for k=2,k=2, and show that its competitive ratio is at most 3 for any B  , improving the previous upper bound of 4B⌊B/2⌋+2(≥10). Moreover, we show that the competitive ratio of any deterministic algorithm is at least 3 for any B   if k=2,k=2, which matches our upper bound.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computer Networks - Volume 91, 14 November 2015, Pages 804–820
نویسندگان
, ,