We consider a multiplexer station which supports ATM video traffic streams. The system model also applies to the multiplexing operation carried out at the output queue of each output-queueing ATM switch. We assume that video signals are encoded by a two-level layered encoding algorithm under which each ATM cell is properly marked as a high-priority (HP) or low-priority (LP) cell according to the significance of the information carried by the cell. The video multiplexer implements a congestion-control based cell-discarding algorithm under which, when high congestion conditions are observed, the LP cells are discarded. In previous studies, the quality of the video streams under such a combined mechanism (of layered encoding and cell discarding algorithms) has been examined for a single stream, without incorporating the impact of the multiplexing operation. In addition, only long-term video quality behavior has been considered. In this paper, we take into account the high burstiness embedded in the video traffic as observed by the multiplexer at the cell-level and the frame-level time scales. We show that, if not carefully designed, a cell-discarding algorithm can cause both inter-frame and intra-frame short-term video quality degradations. To correct this situation, we introduce new cell-discarding algorithms which incorporate a probabilistic mechanism into their cell discarding scheme and which take into account the features of the bursty inter-frame and intra-frame processes. Two Video Degradation Indicators are introduced to measure the short-term inter-frame and intra-frame video quality degradation features experienced by a video stream. Through numerical examples, we identify and compare the system performance behavior under the introduced cell-discarding algorithms. It is shown that, under a prescribed long-term video quality level, the introduction of a probabilistic component in the cell-discarding process significantly improves the system performance, including the short-term video quality and the mean cell waiting time functions. In addition, it is observed that by dynamically calculating the value of the probabilistic component, the short-term video quality performance is further improved.