Buffer overflow management in QoS switches

摘要: We consider two types of buffering policies that are used in network switches supporting QoS (Quality Service). In the FIFO type, packets must be released order they arrive; difficulty this case is limited buffer space. bounded-delay each packet has a maximum delay time by which it released, or otherwise lost. study cases where incoming streams overload buffers, resulting loss. our model, an intrinsic value; goal to maximize total value transmittedOur main contribution thorough investigation natural greedy algorithms various models. For model we prove tight bounds on competitive ratio algorithm discards with lowest value. also drops earliest among all low-value best algorithm. This can as much 1.5 times better than standard tail-drop policy, latest packets.In bounded show any online for uniform away from 1, independent size. analyze general and three special cases: bound 2; link bandwidth 1; only possible values.Finally, off-line scenario. give efficient optimal relation between models case.