Although Transmission Control Protocol (TCP) is widely used in the Internet, its performance is poor in networks with long delays. To improve TCP performance in such networks as long-delay satellite environments, the use of a PEP (Performance Enhancing Proxy) has been proposed. The PEP operates on a router that connects a terrestrial link and a satellite link along a TCP connection. When a data packet arrives at the PEP, it forwards the packet to the destination host, transmits the corresponding ACK (premature ACK) to the source host on behalf of the destination host, and stores a copy of the packet in a local buffer (PEP buffer) in case retransmission of the packet is required. As a congestion control method on the PEP, a method that keeps the number of prematurely acknowledged packets in the PEP buffer below a threshold (watermark) value has been proposed, and a watermark value optimization algorithm has been also proposed under the assumption that all connections have the same route. In this paper, we propose a watermark value optimization algorithm under a more realistic assumption that connections have different routes. We define the upper bound of the average throughput of a connection as the maximum average throughput in the case that the connection only exists in network. For a given set of connections, the proposed algorithm tries to attain that the average throughputs of connections with smaller upper bounds are equal to their respective upper bounds, and the number of such connections (maximized-connections) is maximized, and the average throughputs of connections with larger upper bounds are maximized under the condition that they are equal to each other and are larger than or equal to any upper bound of the maximized-connections. Numerical examples show that the proposed algorithm attains such goal. © 2007 by the American Institute of Aeronautics and Astronautics, Inc. All rights reserved.