A method protects data transmission from failures, wherein the data transmissions are from a source to a destination in a Multi-Protocol Label Switching (MPLS) network, and the data transmissions are via a labeled-switch path (LSP) with segment protection in protection domains. A maximum recovery time for each protection domain is constrained, and for each protection domain, one or more backup tunnels are determined. A graph of nodes of the LSP and the backup tunnels is constructed, wherein edges in the graph represent the links between the nodes. A weight is assigned to each edge to produce a weighted graph. Based on the weighted graph, a path from the source to the destination that satisfies a reliability constraint with a minimum cost is determined by using an optimal combination of segment protections and a reliability-guaranteed least-cost