On tolerating single link,double link,and nodal failures in symmetric grid networks

In this paper, we consider a symmetric grid network consisting of N distinct nodes. The number of allowable calls (either the number of circuit switched calls or the maximum number of virtual connections such that QoS objectives are maintained) between any two nodes of the network is assumed to be a constant. We first determine this constant assuming that the network is fully loaded. Then, we find the maximum additional capacity needed on each link such that single link, and double link failures can be tolerated by rerouting calls around failed links. Results show that the maximum additional capacity needed to recover from any single link, double link, or single node failure, with no loss of connections (except for those connections terminating at a failed node) scales as ${1/\sqrt{(N)}}$ . Thus, we conclude that rerouting, combined with an admission policy which blocks new call attempts such that a fraction of capacity proportional to ${1/\sqrt{(N)}}$ is reserved for failure recovery, provides totally failsafe operation in the presence of such failure events.