A bypassing path based routing algorithm for the pyramid structures

摘要

A pyramid structure is a collection of connected mesh structures. It is well known that a pyramid structure of size n has a diameter of log n, which immediately leads to a natural routing algorithm, using only links between adjacent meshes. However, such paths are often unavailable because of the existence of faulty nodes and/or links. In this paper, we present the concept and technical details of an alternative routing algorithm, based on a collection of bypassing paths, for the potentially faulty pyramid structures that makes use of the links both within and between meshes contained in such structures.We also study some of the mathematical properties of this set of bypassing paths, including their average lengths, to suggest a characterization of the proposed alternative routing algorithm.