This happens occasionally when you have a very busy VPN tunnel (>200 packets per second). To understand why, you have to first understand what Anti-Replay is doing.
The goal of Anti-Replay is to prevent a malicious user from replaying a captured VPN packet. Even if the packet is protected with Encryption and Message Integrity, it is undesirable for someone to 'resend' a protected packet at a later time.
For example, if I deposit $100 cash in my bank account at my local branch, at some point in time my bank branch is going to send packets to my branch headquarters that effectively state "increase my balance by $100". If I were malicious, even if I can't read the packets (due to encryption), and even if I can't change the amount to 1,000 or 10,000 (due to Message Integrity), if I simply just duplicate the packet(s) and resend them on the wire, I could theoretically continually increase my bank balance by $100.
This is what Anti-Replay is trying to protect you from.
It does this by embedding what is called a Sequence number in each packet. Then each end simply tracks to see the last Sequence number received, and if the next packet received is not the next expected Sequence number, the packet is discarded.
That is the basic (and somewhat simplified) premise of Anti-Replay. But lets take a look at how IPsec does it specifically.
Anti-Replay within IPsec
Instead of just looking at the last number received, each party in the secured communication maintains an Anti-Replay Window. By default, on a Cico ASA, the Anti-Replay window is 64 packets.
The parties participating in the IPsec tunnel then simply keep track of only the last 64 packets received. Let's illustrate how the Anti-Replay window is used in an ASA (although the example will work for any IPsec speaker).
If a packet comes through with sequence number #200, the ASA will mark #200 as the "last packet received", and track the previous 64 packets -- what would be packets #137-#200.
- If the next packet received is #150, then the ASA accepts the packet and notes that #150 was received.
- If the next packet received is #130, the ASA discards this packet since it fell outside of the Anti Replay Window.
- If the next packet received is #150 again, the ASA discards this packet since it was tracking the 64 packets before the last one received (#200) and knows that a packet with a sequence number of #150 was already received.
Now lets say the next packet received is #210. This causes the 64-packet window slides forward, which means the ASA will now only accept and track packets #147-#210.
- If packet #150 is received yet again, it gets dropped, since it was still being tracked and within the window.
- If packet #131 is received, it is now dropped, since it is now outside the Anti-Replay window.
- If packet #151 is received, the packet is accepted since it is both within the Anti-Replay window, and has not been received before.
And now, lets say packet #220 arrives. This advances the window, and now packets with sequence number #157-#220 are being tracked.
- If packet #150 is received once more, the ASA has stopped tracking whether #150 was received already, however it still gets dropped because it now falls outside the Anti-Replay window.
- If packet #160 arrives, it gets accepted since it is both within the latest Anti-Replay window, and has not been received before.
And this process continues until the Sequence Number maxes out and resets back to to zero. It is worth noting, that the Sequence Number is not an infinite field and does have an innate maximum. In the case of IPsec, the field is 32 bits, and therefore the Sequence Number maxes out at approximately 4.2 billion.
When the maximum is reached, the keys which were securing the packets must be rotated to avoid a looped sequence number vulnerability.
The solution to your Problem
What is happening in your case specifically is the window is moving forward to fast, and legitimate packets that should be accepted are being dropped because they arrive at the other end just as the Anti-Replay window moved out of range.
The solution: Increase the Anti-Replay window. But the tricky part is what do you increase it to?
A good rule of thumb is for your Anti-Replay window to be 0.5x to 1x your average Packets Per Second. I suggest starting conservative (0.5x) and increasing slowly until your performance errors falls within an acceptable level.
Do not be over-aggressive with increasing the Anti-Replay window, because that leaves you open to inadvertently accepting a replayed packet. Increase it slowly until you are happy with the results.
On an ASA, the command is:
crypto ipsec security-association replay window-size <new size>
You should do this on both ends of the VPN tunnel.