Systems and methods for estimating available bandwidth with multiple overloading streams are described. In one aspect, a set of packets are communicated by a probing sender to a receiver. The packets are sent at multiple sending rates. At least two of the sending rates result in multiple overloading streams of packets being sent to the receiver. The probing sender receives a set of queuing delay information from the receiver. The queuing delay information is based one-way delay measurements corresponding to receipt by the receiver of at least two pairs of successive packets of the packets. The probing sender estimates available bandwidth of the network based on the received queuing delay information and multiple sending rates associated with the multiple overloading streams of packets.