The increasing demand for high-quality streaming video delivered to mobile clients necessitates efficient bandwidth utilization and allocation at not only the wireless channel but also the wired backhaul of broadband cellular networks. In this context, we propose techniques for increasing the link utilization and enhancing the quality-of-experience (QoE) for end users while multiplexing video streams over a wired link. For increasing the link utilization, we present a generic multi-tiered bandwidth estimation and scheduling scheme that can guarantee lower bounds on loss for flows at lower tiers. This scheme can be used for supporting heterogeneous loss classes, providing differentiated losses for different layers of video streams, or providing per-flow guarantees using lower aggregate bandwidth than schemes proposed in the literature. For enhancing the enduser QoE, we present a scheme for minimizing correlated losses and improving the smoothness of video quality by minimizing the maximum loss suffered by any logical unit of a stream and also the variability in loss across the length of the stream. In extensive simulations performed using video sources encoded in various formats, our multi-tiered scheme could lower the estimated bandwidth and improve statistical multiplexing gains by up to 25% with two and three classes and over 30% in the context of providing per-flow guarantees and differentiated loss for different layers. Our loss-minimization approach could lower the maximum loss by a factor of five and the loss variance by more than an order of magnitude. © 2013 IEEE.