The benefit of Class-of-Service (CoS) is an important topic in the "Network Neutrality" debate. As part of the debate, it has been suggested that over-provisioning is a viable strategy to meet performance targets of future applications, and that there is no need for to worry about provisioning differentiated services in an IP backbone for a small fraction of users needing better-than-best-effort service. In this paper, we quantify the extra capacity requirement for an over-provisioned classless (i.e.; best-effort) network compared to a CoS network providing the same delay or loss performance for premium traffic. We first develop a link model that quantifies the required extra capacity (REC). To illustrate key parameters involved in analytically quantifying REC, we start with simple traffic distributions. Then, for more bursty traffic distributions (e.g.; long-range dependent), we find the REC using ns-2 simulations of CoS and classless links. We, then, use these link models to quantify the REC for network topologies (obtained from Rocketfuel) under various scenarios including situations with "closed loop" traffic generated by many TCP sources that adapt to the available capacity. We also study the REC under link and node failures. We show that REC can still be significant even when the proportion of premium traffic requiring performance assurances is small, a situation often considered benign for the over-provisioning alternative. We also show that the impact of CoS on best-effort (BE) traffic is relatively small while still providing the desired performance for premium traffic. © 2012 Elsevier B.V. All rights reserved.