The Random Early Detection (RED) scheme for congestion control in TCP is well known over a decade. Due to a number of control parameters in RED, it cannot make acceptable packet-dropping decision, especially, under heavy network load and high delay to provide high throughput and low packet loss rate. We propose a solution to this problem using Markov chain based decision rule. We modeled the oscillation of the average queue size as a homogeneous Markov chain with three states and simulated the system using the network simulator software NS-2. The simulations show that the proposed scheme successfully estimates the maximum packet dropping probability for Random Early Detection. It detects the congestion very early and adjusts the packet-dropping probability so that RED can make wise packet-dropping decisions. Simulation results show that the proposed scheme provides improved connection throughput and reduced packet loss rate.