Robustness Measure for Hypercube networks

Document Type

Article

Publication Date

11-1994

Publication Title

Computers & Electrical Engineering

Volume

20

Issue

6

First page number:

445

Last page number:

458

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

Computer network resources; Fault-tolerant computing; Hypercube networks (Computer networks); Parallel algorithms; Parallel computers; Routing (Computer network management)

Disciplines

Computer Engineering | Digital Communications and Networking | Electrical and Computer Engineering | Engineering | Signal Processing | Systems and Communications

Language

English

Permissions

Use Find in Your Library, contact the author, or interlibrary loan to garner a copy of the item. Publisher policy does not allow archiving the final published version. If a post-print (author's peer-reviewed manuscript) is allowed and available, or publisher policy changes, the item will be deposited.

UNLV article access

Search your library

Share

COinS