An Optimal Lower Bound for Buffer Management in Multi-Queue Switches

Details An Optimal Lower Bound for Buffer Management in Multi-Queue Switches An Optimal Lower Bound for Buffer Management in Multi-Queue Switches

2010-07-09

arxiv.org/abs/1007.1535v2

Computer Science

Data Structures and Algorithms

Scientific paper

In the online packet buffering problem (also known as the unweighted FIFO variant of buffer management), we focus on a single network packet switching device with several input ports and one output port. This device forwards unit-size, unit-value packets from input ports to the output port. Buffers attached to input ports may accumulate incoming packets for later transmission; if they cannot accommodate all incoming packets, the excess is lost. A packet buffering algorithm has to choose from which buffers to transmit packets in order to minimize the number of lost packets and thus maximize the throughput. We present a tight lower bound of e/(e-1) on the competitive ratio of the throughput maximization, which holds even for randomized algorithms. This improves the previously best known lower bound of 1.4659 and matches the performance of the algorithm random schedule. Our result contradicts the claimed performance of the random permutation algorithm; we point out a flaw in its original analysis.

Affiliated with

Also associated with

No associations

Rating

An Optimal Lower Bound for Buffer Management in Multi-Queue Switches does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with An Optimal Lower Bound for Buffer Management in Multi-Queue Switches, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Optimal Lower Bound for Buffer Management in Multi-Queue Switches will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-644890