A robustness measure for hypercube networks |
| |
Authors: | Shahram Latifi Suresh Rai |
| |
Affiliation: | a Electrical & Computer Engineering Department, University of Nevada-Las Vegas, 4505 Maryland Parkway, Las Vegas, NV 89154-4026, U.S.A. b Electrical & Computer Engineering Department, Louisiana State University, Baton Rouge, LA 70803, U.S.A. |
| |
Abstract: | Hypercube networks offer a feasible cost-effective solution to parallel computing. Here, a large number of low-cost processors with their own local memories are connected to form an n-cube (Bn) or one of its variants; and the inter-processor communication takes place by message passing instead of shared variables. This paper addresses a constrained two-terminal reliability measure referred to as distance reliability (DR) as it considers the probability that a message can be delivered in optimal time from a given node s to a node t. The problem is equivalent to that of having an operational optimal path (not just any path) between the two nodes. In Bn, the Hamming distance between labels of s and t or H(s, t) determines the length of the optimal path between the two nodes. The shortest distance restriction guarantees optimal communication delay between processors and high link/node utilization across the network. Moreover, it provides a measure for the robustness of symmetric networks. In particular, when H(s, t) = n in Bn, DR will yield the probability of degradation in the diameter, a concept which directly relates to fault-diameter. The paper proposes two schemes to evaluate DR in Bn. The first scheme uses a combinatorial approach by limiting the number of faulty components to (2H(s, t) − 2), while the second outlines paths of length H(s, t) and, then generates a recursive closed-form solution to compute DR. The theoretical results have been verified by simulation. The discrepancy between the theoretical and simulation results is in most cases below 1% and in the worst case 4.6%. |
| |
Keywords: | Disjoint paths distance reliability hamming distance hypercube networks node/link failure physical distance |
本文献已被 ScienceDirect 等数据库收录! |
|