In this paper, a new network structure called generalized Hierarchical Completely-Connected networks (HCCs) is proposed, and its properties and features are evaluated. Simple routing strategies for HCCs are also developed for shortest-paths routing algorithms. A set of HCCs constructed by the proposed method includes some conventional hierarchical networks, then it is called generalized one. The construction of an HCC starts from a basic block (a level-1 block) which consists of n nodes of constant degree. Then a level-h block for h 2 is constructed recursively by interconnecting any pair of macro nodes (n level-(h-1) blocks) completely. An HCC has a constant node-degree regardless of an increase in its size (the number of nodes). Furthermore, since an HCC has a hierarchically structured topology and the feature of uniformity, a wide variety of inter-cluster connections is possible. Evaluation results show that an HCC is suitable for very large computer systems.

In interconnection networks, deadlock recovery has been studied in routing strategy. The routing strategy for the deadlock recovery is intended to optimize the routing performance when deadlocks do not occur. On the other hand, it is important to improve the routing performance by handling deadlocks if they occur. In this paper, a routing strategy for suspensive deadlock recovery called an escape-restoration routing is proposed and its performance is evaluated. In the principle of the proposed techniques, a small amount of exclusive buffer (escape-buffer) at each router is prepared for handling one of deadlocked packets. The transmission of the packet is suspended by temporarily escaping it to the escape-buffer. After the other deadlocked packets were sent, the suspended transmission resumes by restoring the escaped packet. Evaluation results show that the proposed techniques can improve the routing performance more than that of the previous recovery-based techniques in handling deadlocks.