Figure 6. Center nodes of the torus network.

5.3 Proof of the Deadlock-Free in 3D Mesh-of-Torus Network

The routing process of packets in the 3D Mesh-of-Torus network consists of three steps under the guidance of dimension-order routing algorithm:
1) In Chapter 4, we have proven that the process of packets routing in source node plane is deadlock-free.
2) Packets will follow the rules defined in chapter 4 when routing in the third dimension. And we will prove it in chapter 4 that under this routing mechanism, we can forbid the formation of circular waiting and thus achieve in deadlock-free.
 3) We introduce the dimension order algorithm when packets transfer in the plane of destination node to prevent deadlock.