FIG. 6 is a flowchart representation of a method 600 of establishing private network data tunnels between multi-uplink network devices in accordance with some implementations. In some implementations, method 600 is an extension or a more detailed process for performing some or all of the activities of method 500 described earlier. As such, for the sake of efficiency, reference is made, when appropriate, to corresponding activities in method 500. For the sake of additional clarity and detail, the method 600 is described with reference to FIG. 1, FIG. 2, FIG. 3A, FIG. 3B, FIG. 4A and FIG. 4B. In some implementations, method 600 is performed at a multi-uplink network device, such as Device A 151 or Device B 154, in FIG. 1. In some implementations, method 600 is performed at a device operating as a router and/or as a gateway node. In some implementations, method 600 is performed by one or more devices in communication with each other through a private network, such as a VPN.