Over the next decades, the Internet will evolve to support increasingly complex mission-critical services such as telerobotically controlled surgery. The world's first telerobotic surgery over the public Internet was performed in 2003, and since then several hundred more have been performed. Three critical requirements of these services include: (i) essentially 100% restoration capability, (ii) small and bounded end-toend queuing delays (ie < 250 millsec), and (iii) very low-jitter communications (ie < 10 millisec). In this paper, algorithms to provision mission-critical services over the Internet with essentially 100% restoration capability and essentially-perfect QoS are proposed, building upon two theoretical foundations. Mission-critical traffic is routed using the theory of shared backup protection paths or p-cycles, while background traffic is routed using multiple edge-disjoint paths. Mission-critical traffic is scheduled using the theory of recursive stochastic matrix decomposition to achieve two constraints: (i) near-minimal end to end queuing delay and jitter and (ii) essentially-perfect QoS. Designs of the Application-Specific Token-Bucket Traffic Shaper Queues (ASTSQs) and the Application-Specific Playback Queues (ASPQs) for telerobotic services are provided. To test the theory, extensive simulations of a saturated Internet backbone network supporting telerobotic services along with competing background traffic (ie VOIP, IPTV) are reported. It is shown that all missioncritical traffic can be delivered while meeting the three critical requirements, even in fully saturated backbone IP networks.