A local stream store of a local proxy caches one or more streams of data transmitted over the WAN to a remote proxy, where each stream is stored in a continuous manner and identified by a unique stream identifier (ID). In response to a flow of data received from a client, the local proxy examines the flow of data to determine whether at least a portion of the flow has been previously transmitted to the remote proxy via one of the streams currently stored in the local stream store. If the portion of the flow has been previously transmitted to the remote proxy, the local proxy transmits a first message to the remote proxy without sending actual content of the portion of the flow to indicate that the portion of the flow has been transmitted in one of the streams previously transmitted to the remote proxy.