In this work, we examine the cost-effectiveness of routing traffic on service networks under random failures. Given a service network, that is subject to random link failures, we analyze the worst-case performance of the network in terms of the total cost incurred in routing the traffic to satisfy all the node pair demand requirements. We primarily focus on network failure scenarios, where b simultaneous links are non-functional. It is important to note that computing the worst-case routing cost over a set of link failure scenarios is classified as an NP-Hard problem. We propose an approach that leverages recent developments in robust optimization, integer, and linear programming to construct convex relaxation of the original NP-Hard problem. Our approach exploits the intrinsic binary nature of the link functionality (i.e., links are either functional or dead), to construct the convex relaxations, that provide quick and strong upper bounds for the original intractable worst-case routing cost problem. To substantiate our findings, we also provide computational results on real-life service network topologies.