Competitive Buffer Management with Class Segregation

Details Competitive Buffer Management with Class Segregation Competitive Buffer Management with Class Segregation

2011-03-30

arxiv.org/abs/1103.6049v2

Computer Science

Data Structures and Algorithms

10 pages

Scientific paper

We introduce a new model for buffer management of network switches with Quality of Service (QoS) requirements and give a tight analysis. Specifically, each network packet is associated with a numerical value, called Class of Service (CoS), which represents its priority. We are furthermore given a network switch with $m$ queues that have individual capacities. Each queue stores packets of a certain CoS, only. A stream of packets arrives over time at the switch and an online algorithm has to decide on the admission and transmission of packets. The objective is to maximize the total CoS-value of the transmitted packets. Our main contribution is a natural online $\GREEDY$ algorithm, which accepts any arriving packet, if the corresponding CoS-queue is not full. It always sends a buffered packet with highest value. We show that this algorithm is 2-competitive. This result is essentially best-possible since we also show a lower bound of $2 - v_m / (\sum_{i=1}^m v_i)$ on the competitiveness of any deterministic online algorithm, where $v_1 <...< v_m$ denote the CoS-values. Hence, whenever $v_m / (\sum_{i=1}^m v_i) \rightarrow 0$, $\GREEDY$ is asymptotically an optimal online algorithm. In practical applications there are often two CoS-values: priority packets (having value $\alpha > 1$) and best-effort packets (having value 1). For this special case, the competitive ratio of the $\GREEDY$ algorithm is at most $(\alpha + 1)/ \alpha$. That is, for $\alpha \rightarrow \infty$, the online algorithm is asymptotically even offline optimal. This upper bound is also close to the lower bound of $(\alpha + 2)/(\alpha + 1)$, which we show for the competitiveness of any deterministic online algorithm.

Affiliated with

Also associated with

No associations

Rating

Competitive Buffer Management with Class Segregation 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 Competitive Buffer Management with Class Segregation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Competitive Buffer Management with Class Segregation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-244480