As the Internet continues to grow, it faces an increasingly hostile environment and consequently, the need for security in network infrastructure is stronger than ever. In this scenario the Multi-Protocol Label Switching (MPLS) emerging paradigm, seems to be the cornerstone for developing most of the next generation network infrastructure-level services in the Internet. Unfortunately, due to the lack of a scalable means of verifying the authenticity and legitimacy of the control plane traffic in an MPLS domain, almost all the existing MPLS control and signaling protocols are extremely vulnerable to a variety of malicious attacks both in theory and in practice and communication between peer routers speaking the above common protocols is subject to active and passive forgery, hijacking and wiretapping activities. In this paper, we propose a robust framework for MPLS-based network survivability against security threats, by making the MPLS control and signaling protocols more secure. Our design goals include integrity safeguarding, protection against replay attacks, and gradual deployment, with routers not supporting authentication breaking the trust chain but operating undisturbed under any other respect.