The low cost and the wide availability make Ethernet the dominant networking technique of access networks. Standardization further extends the capabilities of Ethernet by adding traffic separation and prioritization (802.1Q) and by allowing use of multiple spanning trees (802.1s). In this paper we present an Ethernet based QoS architecture for broadband services with triple play support. We propose an optimization framework with Traffic Engineering where the MSTP trees are spanned taking both the traffic conditions and the QoS requirements into account. The optimization is based on our previously presented formal model. Here we propose a novel decomposition based tree constructing heuristic with high scalability. We conduct simulations to evaluate the performance of the heuristic method that provides nearly optimal solutions within acceptable time constraints.