Available Bandwidth Estimation Techniques and Tools (ABETTs) have recently been envisioned as a supporting mechanism in areas such as compliance of service level agreements, network management, traffic engineering and real-time resource provisioning, flow and congestion control, construction of overlay networks, fast detection of failures and network attacks, and admission control. However, it is unknown whether current ABETTs can run efficiently in any type of network, under different network conditions, and whether they can provide accurate available bandwidth estimates at the timescales needed by these applications. This dissertation investigates techniques and tools able to provide accurate, low overhead, reliable, and fast available bandwidth estimations. First, it shows how it is that the network can be sampled to get information about the available bandwidth. All current estimation tools use either the probe gap model or the probe rate model sampling techniques. Since the last technique introduces high additional traffic to the network, the probe gap model is the sampling method used in this work. Then, both an analytical and experimental approach are used to perform an extensive performance evaluation of current available bandwidth estimation tools over a flexible and controlled testbed. The results of the evaluation highlight accuracy, overhead, convergence time, and reliability performance issues of current tools that limit their use by some of the envisioned applications. Single estimations are affected by the bursty nature of the cross traffic and by errors generated by the network infrastructure. A hidden Markov model approach to end-to-end available bandwidth estimation and monitoring is investigated to address these issues. This approach builds a model that incorporates the dynamics of the available bandwidth. Every sample that generates an estimation is adjusted by the model. This adjustment makes it possible to obtain acceptable estimation accuracy with a small number of samples and in a short period of time. Finally, the new approach is implemented in a tool called Traceband. The tool, written in ANSI C, is evaluated and compared with Pathload and Spruce, the best estimation tools belonging to the probe rate model and the probe gap model, respectively. The evaluation is performed using Poisson, bursty, and self-similar synthetic cross traffic and real traffic from a network path at University of South Florida. Results show that Traceband provides more estimations per unit time with comparable accuracy to Pathload and Spruce and introduces minimum probing traffic. Traceband also includes an optional moving average technique that smooths out the estimations and improves its accuracy even further.