Redundant Array of Inexpensive Links (RAIL) Technique for Network Routing Survivability

Open Access
Author:
Wu, Bo Chen
Graduate Program:
Computer Science and Engineering
Degree:
Master of Science
Document Type:
Master Thesis
Date of Defense:
November 17, 2011
Committee Members:
  • George Kesidis, Thesis Advisor
  • Shashi Phoha, Thesis Advisor
  • Kyusun Choi, Thesis Advisor
Keywords:
  • routing survivability
  • large-scale failure
  • RAIL
  • smart redundancy
  • multipath routing protocol
Abstract:
In most large computer and communication networks, data packets are routed over a single path using intermediate router nodes in a network. Even though the router nodes may be well-protected, possible damage can still occur due to either natural (e.g., earthquake) or man-made (e.g., weapon of mass destruction (WMD) attack) disasters. A high-survivability network will be able to provide continuous service between end-point nodes even in the presence of such disasters. When a path is not available, a network routing protocol reacts by finding an alternate path to overcome temporary failures. However, a reactive routing protocol can cause a significant delay to time critical communication applications (e.g., Voice over IP, live video-conference, stock market trading applications, or patient monitoring applications). Another possible solution to alleviate the consequence of node failures is to redundantly replicate data packets and proactively route the replicated packets through different disjointed routing paths. Though the solution improves the availability of the network, it adds significant amount of transfer overhead. In this thesis, we are interested in dealing with situations in which a large number of network nodes/links located in a localized region may experience failure. A rare WMD attack or high intensity hurricane/earthquake can cause such damage. When a WMD event or natural disaster occurs, the shielding of the critical network components would minimize the damage, and hardware redundancy would reduce the physical network infrastructure recovery time. However, the shielding and redundant hardware components remain vulnerable to WMD attacks or natural disasters as well, and they might be destroyed at the same time as the primary components. This thesis proposes the concept of smart redundancy which uses the Redundant Array of Inexpensive Links (RAIL) technique to achieve the high routing survivability of the network. Our technique first fragments a data block into n stripes: p1, p2, …, pn. Then using Reed-Solomon Coding, the m additional check sum stripes are added, p1, p2, …, pn, pn+1, …, pn+m. The resulting n+m stripes are treated as n+m separate packets, which we will henceforth refer to as striped packets. Finally, these n+m striped packets are routed over n+m different routing paths, such that these routing paths are node- and link- disjoint. The Reed-Solomon coding is based on the theory Finite Field and offers the desirable property that the original packet can be completely reconstructed from any n out of n+m striped packet. Thus, by this method, up to m path failures are tolerated in the network. If the n+m multiple paths are completely non-overlapping and a path is assumed to have a failure probability of Pf, then the failure probability of m paths is Pfm « Pf.