Techniques are disclosed for generation of spanning trees that support provision of performance-guaranteed services over a circuit-switched network such as, for example, an optical-based network. For example, a technique for generating a spanning tree for use in forwarding Ethernet-based data in a circuit-switched network comprises the following steps/operations. Input information is obtained. The input information comprises a representation of the network, a set of Ethernet-enabled nodes in the network, and a set of demands. A spanning tree is computed based on at least a portion of the input information such that the spanning tree substantially satisfies one or more performance requirements (e.g., one or more bandwidth requirements) associated with the set of demands. Advantageously, in one embodiment, such techniques may provide for generation of spanning trees for use in supporting bandwidth-guaranteed Ethernet services such as E-LAN over a SONET (and SDH) network.