Randomized qeue management for DiffServ

摘要: We focus on the online problem of queue management in networks providing differentiated services. As DiffServ, packets are divided into two priority groups. Low assigned value 1 and high α > 1. The goal is to maximize total that sent. Restricted FIFO queues, must be sent by order their arrival, however we allowed preempt from queue.Several deterministic algorithms for this model have been presented previous papers. Currently, best algorithm known has a competitive ratio 1.304 worst case [17]. In work consider randomized algorithms. Our main result an policy outperforms any achieves 1.25, using single random bit. This lower than bound 1.281 [19]. then derive general 1.197.A natural extension assign arbitrary packet values input packets. achieved 1.75 [7]. present comparison based with same ratio. Since no better 2, believe demonstrates potential randomization outperform policies, as model.