The network devices shown in FIG. 1, Device A 151 and Device B 154 are capable of establishing private network tunnels (e.g., VPN data tunnels) simultaneously using two or more uplinks. In some embodiments, at least one uplink for a respective network device uses a public network connection and at least one uplink for a respective network device uses a higher-quality connection. For example, Device A 151 uses Uplink 0 170 to connect to public/external network 120 using a low-cost and lower quality link provided by ISP 140a, and Uplink 1 171 to connect to a higher-quality MPLS link 175a. Unlike network devices utilizing a “hot standby” or backup uplink, Device A 151 uses at least two uplinks on an active basis during normal operation. The multi-uplink network devices shown in FIG. 1 each show two active uplinks, however those of ordinary skill in the art will appreciate from the present disclosure that in some embodiments, the multi-uplink devices disclosed herein utilize more than two simultaneously active uplinks. Furthermore, while the multi-uplink network devices shown in FIG. 1 show the use of Internet and MPLS uplinks, those of ordinary skill in the art will appreciate from the present disclosure that in some embodiments, the uplink connections include other technologies, including satellite services such as very small aperture terminal (VSAT) links.