There are different tools to estimate the end to end available bandwidth (AB). These tools use techniques which send pairs of packets to the network and observe changes in dispersion or propagation delays to infer the value of the AB. Given the fractal nature of Internet traffic, these observations are prompt to errors affecting the accuracy of the estimation. This article presents the application of a clustering technique to reduce the estimation error due to wrong observations of the available bandwidth in the network. The clustering technique used is K-means which is applied to a tool called Traceband that is originally based on a Hidden Markov Model to perform the estimation. It is shown that using K-means in Traceband can improve its accuracy in 67.45 % when the cross traffic is about 70% of the end-to-end capacity.