For the vast majority of source-destination pairs avoiding the USA or China on PlanetLab, Alibi Routing introduces less than 50% latency inflation; some pairs even see latency improvement due to overlay shortcutting (Figure 9). Latency inflation is relatively insensitive to the inequality factor δ when relays are successfully found.

On a 370-node PlanetLab deployment, Alibi Routing achieved near 100% success avoiding both the USA and China (Tables 1–2) with an average search cost of 1.0–1.66 nodes contacted (Table 4). In simulation over 20,000 globally distributed nodes, success rates were 93–100% at δ=0.5–1.0 with average search cost under 40 nodes (Table 3), capping TTL at 7.

§6.3, Tables 1–4 evaluation

Property 1 proves that a peer inside a forbidden region F cannot satisfy the safety condition: appearing safe would require reporting an RTT lower than (3/c)·distance(peer,F), a physical impossibility. Property 2 follows: all trustworthy peers ignore packets routing through F regardless of attacker-controlled neighbor sets, making Alibi Routing safe without assuming honest neighbor selection.

§5 defense

Alibi Routing fails for source-destination pairs close to or inside the forbidden region: approximately 10% of pairs cannot provably avoid China and 22% cannot avoid the USA at δ=1.0 (Figure 5), with a strong monotonic correlation between proximity to the forbidden region and the number of available relays (Figure 6). Additionally, about 50% of nodes in target regions fail the alibi condition when avoiding the USA due to its BGP routing centrality causing actual paths to transit it despite geographic distance (Figure 7a).

§6.1–6.2, Figures 4–7 evaluation

Alibi Routing proves packets avoided a forbidden geographic region using physical impossibility: a relay MACs forwarded packets, and the observed RTT must satisfy (1+δ)·R(s,r) < min_{f∈F}{R(s,f)+R(f,r)}, where the minimum RTT to any point in F is estimated as (3/c)·ShortestDistance(q,F) — fiber-optic links at 2/3 the speed of light. This proof requires only GPS coordinates and local RTT measurements, no BGP modifications or PKI.

§3, §4.4.1 defense