For traffic control in high speed ATM Networks Usage Parameter Control (UPC) plays an important role. The existing UPC schemes have some limitations. It is difficult to implement policy which involves monitoring vioations while guaranteeing QoS for the compliant connections-particularly with respect to bursty traffic sources. This is due to the difficulty in measuring the Sustained Cell Rate (SCR) and Maximum Burst Size (MBS) parameters simultaneously. To ensure prompt action against policy-violations, speedy detection is an important requirement. But the existing UPC schemes do not have a satisfactory response time. In this paper, we propose a new scheme called Markovian State-Dependent UPC schemes (MSDU) to police SCR and MBS parameter violation simultaneously with a satisfactory response time. The MSDU scheme is performed by using two virtual queues: 1) a Markovian State Dependent Service queue and 2) a Fixed Service queue. The discrete time analysis of the MSDU is carried out for a bursty source which is a Markov-Modulated Bernoulli Process (MMBP). The improved effectiveness of the proposed MSDU is clarified by a numerical comparison with UPC based on standard Leaky Bucket scheme.