ReOpt: Near-Optimal Region Division for Low-Latency Regional Anycast

Regional IP anycast enhances traditional global anycast by organizing infrastructure into geographically-defined regions, each advertising distinct IP prefixes to attract local client traffic, though this approach introduces two key challenges: suboptimal intra-region routing from rigid geographic boundaries and cross-region path inflation due to excessive prefix multi-announcement. To address these, we propose ReOpt, an optimized anycast framework that dynamically minimizes latency through three key mechanisms: (1) real-time RTT measurements between client-site pairs and assess pairwise site preferences for each client, (2) intelligent multi-announcement strategies that enhance routing flexibility while maintaining stability, and (3) country-level region partitioning that simplifies DNS management while preserving geographic optimization. We formulate this as the Latency-Minimized Anycast Region Partition (LMARP) problem, prove its NP-hardness, and develop polynomial-time approximation algorithms with guaranteed approximation ratios. Our experimental evaluation on the PEERING testbed demonstrates that ReOpt-optimized regional anycast achieves significant latency improvements, reducing 90th percentile client latency by 4.6-9.3% across diverse partitions compared to conventional regional anycast, demonstrating its effectiveness in adapting to real network conditions beyond static geographic constraints.