Methods and systems for a multimedia queue management solution that maintaining graceful Quality of Experience (QoE) degradation are provided. The method selects a frame from all weighted queues based on a gradient function indicating a network performance rate change and a distortion rate caused by the frame and its related frames in the queue, and dropping the selected frame and all its related frames, and continues to drop similarly chosen frame until a network performance rate change caused by the dropping frame and its related frames meets a predetermined performance metric. A frame gradient is a distortion rate divided by a network performance rate change caused by the frame and its related frames, and a distortion rate is based on a sum of each individual frame distortion rate when the frame and its related frames are replaced by some other frames derived from remaining frames based on a replacement method.