VPN Migration

im looking for any operational experiences/references
regarding large wan migrations from private frame-relay
to extranet VPNs for remote office connectivity.
specifically, what backbone provider(s) did you choose,
what type of cost savings were realized in both telco
charges as well as management overhead, and what
performance increases/decreases did you experience?