Managing encoded multi-part communications for provided computer networks

A computer-implemented method comprising:

• obtaining information regarding a first virtual computer network having multiple computing nodes, the first virtual computer network being overlaid on a distinct substrate network that interconnects the multiple computing nodes;
• and
• managing, by one or more configured computing systems, a communication sent by a sending one of the multiple computing nodes of the first virtual computer network to an intended final destination, the managing of the communication including:
• determining, by the one or more configured computing systems, one or more alternative paths from the sending one computing node to the intended final destination;
• determining, by the one or more configured computing systems, a first quantity of one or more parts into which to encode the communication based at least in part on information about the determined alternative paths, and encoding the communication into the one or more parts of the determined first quantity;
• and
• forwarding, by the one or more configured computing systems, each of the parts of the encoded communication from the sending one computing node to the intended final destination along one of the determined alternative paths, wherein each of the determined alternative paths is used to forward at least one of the parts.

A system comprising:

• one or more processors of one or more computing systems;
• and
• one or more modules that are configured to, when executed by at least one of the one or more processors:
• obtain information regarding a first virtual computer network having multiple computing nodes, the first virtual computer network being overlaid on a distinct substrate network that interconnects the multiple computing nodes;
• and
• managing one or more communications sent by one or more of the multiple computing nodes of the first virtual computer network, the multiple communications each being sent by a sending one of the multiple computing nodes and having an intended final destination, the managing of each of the one or more communications including:
• determining one or more alternative paths from the sending computing node for the communication to the intended final destination of the communication;
• determining a first quantity of one or more parts into which to encode the communication based at least in part on information about the determined alternative paths, and encoding the communication into the one or more parts of the determined first quantity;
• and
• forwarding each of the parts of the encoded communication from the sending computing node for the communication to the intended final destination of the communication along one of the determined alternative paths, wherein each of the determined alternative paths is used to forward at least one of the parts.