In today’s world, many e-business initiatives such as workforce optimization, customer care, e-commerce, and corporate communication often depend on unprecedented levels of network access and agility. Pursuing these initiatives needs complex networking, dedicated IT resources for 24-hour monitoring and management, and cost-effective integrated voice and data services. In the face of these demands, many business houses are reassessing their corporate networking infrastructures and seriously considering out-sourcing alternatives. Service providers offering managed IPVPN services can help corporate business meet today’s challenges. The primary function of an IPVPN is to provide cost-effective, secure connectivity over a shared infrastructure with identical policies and service attributes that the enterprise enjoys within its dedicated private network. This monograph describes algorithms for building dynamic and resource-assured managed VPNs that can satisfy users of the VPN as well as increase the revenue generation for service providers. These algorithms span the areas of optimal tunnel path finding, dynamic bandwidth management, unicast and multicast restoration of VPNs.