This work focuses on the definition of a novel approach of real-time QoS using the (m,k)-firm constraints into packet switched networks. We define the concept of loss-tolerant QoS with graceful degradation that consists in guaranteeing an acceptable level of QoS for loss-tolerant real-time applications in overload situation. Our approach is mainly applied to multimedia networks assuring the delivery of real-time loss-tolerant multimedia flows such as MPEG video broadcast, Voice over Ir, audio streams ... The contribution presented in this work is (1) to propose a novel scheduling algorithm to provide loss-tolerant QoS with graceful degradation, (2) validate the proposai through different and complementary techniques: mathematical analysis, simulation and implementation in test bed platform. Our approach of gracefully degraded QoS is based two concepts: (1) Bandwidth guarantee, (2) meeting the (m,k)-firm timing constraints. We have combined both concept to propose our scheduling algorithm, called (m,k)-WFQ, that performs fair resources sharing as dos WFQ while taking into account the (m,k)-firm timing constraints of each stream.