Computer systems for real-time transactions over the Internet require trustworthy and speedy data transmission. The recovery of packets from single-node and dual-link failures in Internet protocol (IP) networks should be rapid, but how should resilient techniques for link failures along paths in IP networks be developed? Network failure and recovery issues, as well as some solutions, exist in the literature [1,2,3]. However, how should we design practical IP layer solutions for constructing extremely fault-tolerant, cost-effective networks?
Kini et al. provide fast rerouting schemes for coping with failures that originate from single nodes and dual links in IP networks. The fast rerouting methods assume bidirectional node links, a two-vertex-connected network for single-node failure, and a three-edge-connected network for indiscriminate two link failures. One normal address and, at most, three protection addresses are assigned to each node to recognize the endpoints of channels that transmit recovery traffic in the region of protected links. Packets are routed over a protection graph with no abortive link to the safeguard address of each node. The rerouting schemes consist of procedures for: assembling the protection graphs for each node; selecting a tree in a protection graph for packet routing when node failure occurs; and generating the routing table entries at each node.
The authors examine packet forwarding for quick recovery from single-node failures. They use colored trees rooted at network nodes to illustrate the effects of forwarding a packet along the shortest tree first (STF) (shortest path to the root) and the red tree first (RTF) (prior to selecting a blue tree in the event of a failure in the red routing link of a protection graph). They perform simulation experiments with a variety of network topologies to assess the effectiveness of the newly developed rerouting schemes in resolving single-node and dual-link failures. The authors weigh the ratio of the recovery path lengths against the direct probable bypass around the failed links, to assess the performance of the STF approach and the RTF approach. The STF approach resulted in a lower number of path lengths than the RTF approach under single-link failure situations, but the average path lengths of both algorithms were similar in dual-link failure setups.
The authors use Dijkstra’s algorithm to extract the shortest paths between all possible node pairs. They use single-node failures to estimate the recovery paths, the mean recovery path length, and the mean shortest path length. The recovery paths, mean recovery path length, and mean shortest path length indicate the success of the STF and RTF approaches in recovering single-node failures. The STF approach produced superior recovery paths over the RTF approach, and on average we can forecast the mean shortest path length of the STF approach as roughly one-fourth of the mean recovery path length.
The authors present an incredibly succinct review of important single-link failure recovery algorithms, and the unique relevance of colored trees in tunneling packets. The proposed expandable fast rerouting schemes with negligible overheads can resolve up to two breakdown connections, a single-node failure, or dual-link failures in IP networks. The advocated IP-in-IP encapsulation-based tunneling in the rerouting schemes is intriguing. The authors provide noteworthy theory and reliable simulation results to recommend the fast rerouting schemes for providing IP networks with prompt recovery from failures.