Distributed algorithms for shortest-path, deadlock-free routing andbroadcasting in arbitrarily faulty hypercubes

摘要

The authors present a distributed table-filling algorithm forpoint-to-point routing in a degraded hypercube system. This algorithmfinds the shortest length existing path from each source to eachdestination in the faulty hypercube and fills the routing tables so thatmessages are routed along these paths. A novel scheme for broadcastrouting with tables is proposed, and the algorithm required to fill thebroadcast tables, given the point-to-point routing tables, is presented.In addition, the modifications necessary to make these algorithms ensuredeadlock-free routing are given. A quantitative and equalitativecomparison of previously proposed reroute strategies with table routing,where the tables are filled by the authors' algorithms, are presented