Fault-tolerant Routing for Pyramid Networks Using Least Level Minimal Routing Method

摘要

Pyramid networks have long been proposed for parallel processing. However, when the network contains multiple pairs of source and destination nodes, it is often difficult to use the pyramid efficiently since most of the algorithms try to simultaneously use the apex for each pair of nodes. Therefore, there may exist a severe bottleneck in such circumstances. We propose a Least Level Minimal Routing (LLMR) scheme for releasing the bottleneck in pyramid networks. At each vertex, the algorithm using LLMR needs only O(n) time to determine the shortest path from the source to the destination, where n denotes the number of levels in the nonfaulty pyramid network. Besides, LLMR releases the apex from almost all transmission load for any pair of nodes. Furthermore, it reduces enormously the traffic in higher levels of the pyramid. We also provide point-to-point node disjoint parallel routing algorithm in pyramid networks, where the lengths of the paths are at most 4n-2 steps.