In the two-stage relay selection strategy of UW-LFRR, how does Phase I differ from Phase II in terms of search objective and computational complexity, especially under different failure scenarios?
Phase I aims to quickly graft traffic back to the original backbone with minimal detour (at most 2 extra hops) and has computational complexity O(|Ku|), making it suitable for most failure scenarios where the backbone is partially available. Its search objective is to find a grafting point on the original shortest path (Porig) that minimizes the distance from the repair node to the boundary relay (BR). Phase II, in contrast, is triggered only when the backbone is completely disrupted within the branch-off region (Cmain = ∅), and it searches for a relatively optimal detour over all of Ku with complexity approximately O(|Ku| log|Ku|). Its search objective is to find a pair (BR, GR) that minimizes the total cost (dGu(RN, BR) + 1 + dCfallback(GR, DST)), ensuring connectivity when the backbone is fully cut.
