Section

I. deadlock nature of torus and avoidance without using virtual channel

    Torus is basically a modified form of mesh topology by connecting every initial point to the end point. Its wraparound links inside the network will decrease the communicating time since its structure features enable remote servers to connect with each other directly in each dimension. In addition, torus will have a shorter network diameter, so it will not be limited in its scalability as well as regularity.
    But torus network also has some drawbacks. Torus network naturally has the tendency to be immersed in deadlock situation due to its ring structure. Deadlock is a phenomena that all the resources are waiting for the other resource to release a block. To be more specific, traffics from different locations will compete for the limited resources the whole network possesses, such as buffer resources and link bandwidth. They occupy partial resources that others are applying for while others are waiting for resources occupied by them. Unless external interrupts break this dilemma, they will keep asking for the resources for their advancing. The circular structure of torus is easier to arrange for resources traffic deadlock in the network. To solve this problem, people have put forward a concept called virtual channels that will tackle with this problem by remapping the number of nodes. But the employment of virtual channel will increase the complexity of routing node considering of its mounting additional resource expenditure rate and arbitration as well as judgment expense for each node. So, we shift our focus on finding a revised deadlock-free topology with the implementation of virtual channels. And we will present our new topology in the next section.

II. MESH-OF-TORUS TOPOLOGY

    Figure 1 illustrates a Mesh-of-Torus hybrid-interconnected data center network. 16×16 servers compose the whole network of three levels. A 4×4 torus network is considered as the basic cell to construct higher level network. Multiple torus networks are connected in mesh network. And two adjacent torus networks are connected by four links. The whole network are divided into(2×2)×(2×2)×(4×4)hierarchical network. 2×2 torus networks form a third-level subnet and 2×2 third-level subnets cover the whole network. And we employ the routing and port assignment mechanism proposed by us in chapter 4 into this 4×4 torus network.  And we will discuss the effectiveness of the routing algorithm in the subsequent section. So, we can see that in this new structure, no virtual channels are applied in the switching fabric of each server.
    Compared with hierarchical mesh and traditional torus, Mesh-of-Torus has the following structure characteristics:
    1) The network diameter is considerably smaller than that of hierarchical mesh. 4×4 torus network are employed as the basic cell of the whole network. Compared with hierarchical mesh, the introduction of wraparound links can notably reduce the number of intermediate nodes that packets will pass by. Especially when the source node and the destination node are not in the same subnet, hops will greatly reduce, making it possible for packets to reach their terminations in even shorter durations. The diameter of Mesh-of-Torus is less than that of traditional torus. Additionally, the switching fabric of a server in Mesh-of-Torus network can be simplified without the implementation of virtual channels and corresponding complicated arbitration as well as the scheduling mechanism. More detailed comparisons of various network parameters, such as node degrees, network diameters, total number of links and the employment of virtual channels are listed in table 4 within the same network size in different kinds of networks.
    2) A hierarchical mesh has different routing table scale for servers in various locations. Compared with servers at the brim of hierarchical mesh, servers at the center of mesh are supposed to store more paths. To uniform the memory size for routing table, we have to expand the network according to its routing table scale. But in a Mesh-of-Torus, paths are independent of their location in the net when passing through servers. In particular, using the routing and port assignment mechanism proposed by us in the 4*4 torus, all the servers will store equally 32 paths that passing them. The analysis and comparison of the composition of the routing table for a server in a three hierarchical mesh and Mesh-of-Torus are given in table 5.
    3) Mesh-of-Torus is unable to balance the node degree. When it is scaled up in the domain of 2D plane, partial server ports are idling and they will never be utilized. But if it is extended to 3D data center network, those dormant ports will be activated to construct effective data center network for better performance. Details on extension rules for a 2D Mesh-of-Torus network will be illustrated in chapter  5.