In this paper, we examine the problem of estimating the capacity of bottleneck links and available bandwidth of end-to-end paths under non-negligible cross-traffic conditions. We present a simple stochastic analysis of the problem in the context of a single congested node and derive several results that allow the construction of asymptotically-accurate bandwidth estimators. We first develop a generic queuing model of an Internet router and solve the estimation problem assuming renewal cross-traffic at the bottleneck link. Noticing that the renewal assumption on Internet flows is too strong, we investigate an alternative filtering solution that asymptotically converges to the desired values of the bottleneck capacity and available bandwidth under arbitrary (including non-stationary) cross-traffic. This is one of the first methods that simultaneously estimates both types of bandwidth and is provably accurate. We finish the paper by discussing the impossibility of a similar estimator for paths with two or more congested routers.