Cluster systems have been showing their great advantages in today’s Internet services for their high scalability and high availability. Linux Virtual Server (LVS), one of the popular technologies in building Internet services based on cluster, with its layer 4 scheduling strategy, is gaining increasing interests by ISPs as well as researchers. This paper proposes three new methods to achieve a connection-level (layer 4) fault tolerance for Load Balancer, one of which is called incremental backup and the other two are state mirroring. With these methods, the connections maintained in the primary machine can be safely restored in the backup machine in case of the primary’s failure without any loss on unfinished work, thus ensuring high availability for the Load Balancer. Compared with previous work, our schemes are more efficient and flexible. Although they are based on LVS, these methods can also be applied to other architectures with layer 4 switching.