Type of Publication: Journal Articles
Authors: Zvi Lotker, B.Patt-Shamir
Title: Nearly optimal FIFO buffer management for two packet classes
Name of the Journal: Computer Networks
Year: 2003
Volume: 42
Issue: 4
Pages: 481 - 492
Abstract: We consider a FIFO buffer with finite storage space. An arbitrary input stream of packets arrives at the buffer, but the output stream rate is bounded, so overflows may occur. We assume that each packet has value which is either 1 or α, for some α > 1. The buffer management task is to decide which packets to drop so as to minimize the total value of lost packets, subject to the buffer space bound, and to the FIFO order of sent packets. We consider push-out buffers, where the algorithm may eject packets from anywhere in the buffer. The best lower bound on the competitive ratio of on-line algorithms for buffer management is approximately 1.28. In this paper we present an on-line algorithm whose competitive ratio is approximately 1.30 for the worst case α. The best previous general upper bound was about 1.888. © 2003 Elsevier Science B.V. All rights reserved.
Keywords: Buffer storage;Quality of service;Competitive intelligence;Data communication systems;Synchronization;Algorithms; ,
Last Updated: 9/4/2007 12:00:00 AM
Powered by Rami Palombo © 2005
Search in: Google Scholar  |  Scitation