Techniques are described for providing managed computer networks. In some situations, the techniques include managing communications for computing nodes of a managed computer network by automatically determining to separate a particular outgoing packet or other outgoing communication from a source computing node into multiple parts (e.g., multiple packets) to be independently sent using two or more alternative network paths between the sending computing node and the destination for the communication. For example, a manager module associated with the source computing node may automatically determine to encode the outgoing communication into a dynamically determined quantity of multiple parts (e.g., by using a configurable erasure code), such as based on current information about available alternative paths, and another manager module associated with the destination may receive at least some of the multiple parts and decode them into the original outgoing communication, which is then provided to the destination.