Wrong packet routing when UDP has MTU over 1500

The issue you're experiencing with UDP packet routing when the MTU exceeds 1500 bytes is complex and involves several AWS networking components. Let's break down the problem and potential causes:

1. MTU size: The standard MTU for most networks is 1500 bytes. When you send packets larger than this, they may need to be fragmented or dropped, depending on the network configuration.

2. Network Load Balancer (NLB) behavior: NLBs maintain UDP flow state based on source and destination IP addresses and ports. This ensures packets from the same flow are consistently sent to the same target. However, when the idle timeout period (120 seconds for UDP) elapses, the NLB considers the next incoming UDP packet as a new flow and may route it to a different target.

3. NAT Gateway vs. Load Balancer routing: The fact that some connections go through the NAT Gateway and others through the Load Balancer can lead to inconsistent routing, especially when large packets are involved.

4. Multiple instances behind the NLB: The issue occurring only with two instances behind the NLB suggests a potential problem with load distribution or session stickiness.

5. Packet fragmentation: Large UDP packets (over 1500 bytes) may be fragmented, and not all network devices handle fragmented UDP packets consistently.

To troubleshoot and potentially resolve this issue:

1. Check the MTU settings on your EC2 instances and ensure they match the network requirements.

2. Consider implementing Path MTU Discovery (PMTUD) to determine the optimal MTU size for your connections.

3. Review the NLB configuration, particularly the idle timeout settings and cross-zone load balancing.

4. Examine the security groups and network ACLs to ensure they're not interfering with the traffic flow.

5. Monitor the NLB's behavior using CloudWatch metrics to identify any patterns in traffic distribution.

6. Consider using packet capture tools like Wireshark on both the client and server sides to analyze the traffic flow and identify where packets are being dropped or rerouted.

7. If possible, try to keep the packet size below 1500 bytes to avoid fragmentation issues.

The fact that the issue started after a few months of live traffic without any changes suggests there might have been an underlying network configuration change or a gradual shift in traffic patterns. Continue monitoring the situation closely and consider reaching out to AWS support for more in-depth analysis if the problem persists.
Sources
Set the MTU for your Amazon EC2 instances - Amazon Elastic Compute Cloud
Troubleshoot Gateway Load Balancer's connectivity issues | AWS re:Post
Troubleshoot your Network Load Balancer - Elastic Load Balancing
Network Load Balancers - Elastic Load Balancing