Disclosed herein are systems and methods for the creation, management, and utilization of a multi-region virtual overlay wide area network from a plurality of special purpose network appliances. In exemplary embodiments, multiple regions are created for the virtual overlay wide area network, each region having its own network topology. At least one network appliance from each region is in communication with at least one network appliance from each other region, for inter-region connectivity within the virtual overlay wide area network. A subnet sharing protocol can be utilized to exchange routing information among each network appliance within each region, and between each region.