Applications that run on an overlay network-based managed service achieve high performance gains using a set of TCP optimizations. In a first optimization, a typical single TCP connection between a client and an origin server is broken into preferably three (3) separate TCP connections. These connections are: an edge-to-client connection, an edge-to-edge connection, and edge-to-origin connection. A second optimization replicates TCP state along the connection to increase fault tolerance. In this approach, preferably a given TCP connection is maintained on two servers. When a packet is received by one server, called the primary, its state is updated and then passed to a second server, called the backup. Only when the backup sends an acknowledgement back to the primary can it then send a TCP acknowledgement back to the host that originally sent the packet. Another optimization reduces connection establishment latency. In particular, data is sent across the edge-to-edge connection before waiting for a SYN/ACK from a receiving region to be received by the sending region. This is achieved by generating a SYN/ACK packet (at the sending region) and feeding it back to the edge-to-edge connection. This causes TCP to treat the connection as established, thereby allowing data to flow.