The techniques herein provide for enhanced overlay network-based transport of traffic, such as IPsec traffic, e.g., to and from customer branch office locations, facilitated through the use of the Internet-based overlay routing infrastructure. This disclosure in particular describes a method of managing and enforcing quality-of-service (QoS) in an Internet-based overlay network shared by a set of content provider customer entities. For each entity having a customer branch, the customer branch is coupled to the Internet-based overlay routing network. A quality-of-service (QoS) policy is configured for the customer. According to the method, utilization of the Internet-based overlay network against the configured QoS policy is then monitored. The QoS is then enforced for the customer and at least one other customer, based in part on the QoS policies.