 Open Access
 Total Downloads : 5
 Authors : Rashmi H.U, Harshitha N.U, Bindu.N.S
 Paper ID : IJERTCONV2IS13070
 Volume & Issue : NCRTS – 2014 (Volume 2 – Issue 13)
 Published (First Online): 30072018
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
A New Proposed Interconnection Topology: C2Mesh
1Rashmi H.U, 2Harshitha N.U, 3 Bindu.N.S
1,2B.E Student, Dept. of ECE
3Assistant professor, Dept. of E&C
1, 2,3Vidyavardhaka College of Engineering, Mysore, India rashmihasini9@gmail.com
harshithauthappa@gmail.com bindu.ns5@gmail.com
Abstract: CenterConnected mesh is a recent and a quite advanced interconnection topology. The performance of the c2 mesh technology is improved and has an edge over the simple 2D mesh and torus interconnection topologies. This paper focuses on the features of the center connected mesh topology. It also provides a detailed analysis of its architectural potential in terms of routing algorithms. The n*n c2 mesh has different topological properties which have been given primary importance here.
Index words: Mesh, Torus, Interconnection networks, routing.

INTRODUCTION
The various network elements can be connected in different topologies like star, ring, mesh, tree topology etc. Among all the technologies the mesh topology is the most simple and efficient network topology. The network performance decreases drastically as the size of the mesh increases and also due to large network diameter and little bisection width [6]. In Torus network the diameter of the network is reduced but there is an increase in the bisection width and structural complexity. In order to overcome the above mentioned drawbacks some improved network topologies, like Dmesh [5], Dtorus [5], Xmesh[6] and SDTorus [6] have been proposed by adding some extra links [1],[3]. All these network topologies are usually very complex to design and are quite expensive.
One of the important properties that all the network topologies should satisfy is the scalability property which states that the number of nodes requiredimmediately must be supported by the network and also there should be scope for improvement without causing any overhead. In order to enhance the scalability property and make the network complex the Centerconnected Mesh (C2Mesh) network was proposed. The C2Mesh network has good topological properties compare to previous proposed networks.
This paper is organized into different sections Section 2 discusses related work, Section 3 describes theproposed network topology and its topological properties. Section 4 explainsthe routing algorithm for nÃ—n C2Mesh. Finally, Section 5 concludes the work.

DISCRIPITION
The layout pattern of the interconnections between the computers in a network is called as the network topology or network architecture. Devices on the network are referred to as nodes. The most common nodes are computers and peripheral devices. The mesh network is very simple and hence it is the most suitable network topology for small scale interconnections. In a mesh network each node is connected to every other node of the network. The figure1 shows a simple mesh network.
Figure1: A simple Mesh
The increase in the size of the network results in the increase of the network diameter and reduction in the bisection width. As a result the performance and the efficiency of communication between the nodes degenerate rapidly [6]. The DMesh and DTorus networks were introduced in order to promote the performance and scalability of the both Mesh and Torus network [5].By adding diagonal links to an ordinary mesh network a DMesh network can be constructed easily shown in figure 2.. In a DMesh network, each inner node has a degree of eight, and each peripheral node has adegree of three or five.
Figure 2: An N = 5 x 5 diagonal mesh network in XY coordinates
The DTorus topology reduces the network diameter [5]. For the purpose of network on chip a special Meshlike topology known as XMesh, was
SubsectionA, provides the physical connection of C2Mesh using node numbers and subsection B, explain the physical connection C2Mesh using 2D addressing.
C2Mesh using node numbers
In this method consider that all nodes has a unique number, where first node having the number 0 and is referred to as node(0) and second node having 1 and is referred to as node(1) and so on. In the nÃ—n network, last node will have nÃ—n 1 number so it is referred to as node (nÃ—n 1), figure4 shows how to design the nÃ—n C2Mesh, first design simple nÃ—n 2DMesh, and find the center , connect all four corner nodes to the center node(s). The center of the mesh can be calculatedas follows:
introduced and its routing algorithm is called XM [6]. By adding some diagonal edges on the Mesh
Center =
( 1)
2
topology, the average distances of the Xmesh network is reduced. The figure 3 shows the network diagram of XMesh. Given the same network size, XMesh has the same edge number with Torus topology [6]. The very regular and symmetrical interconnection network is The SD Torus network [6]. Adding two extra diagonals to a 2DTorus network the results in a SDTorus network. Extra diagonals links from northwest to southeast direction are connected. Therefore each node increases its node degree with two extra edges. The DMesh, DTorus, the XMesh and SD Torus, are still complicated and cost effective due to network design and implementation point of view and especially for its routing algorithm, because high node degree networks also leads to high cost.
Figure3: XMesh Network Diagram

C2MESH NETWORK
When the corner nodes of a simple 2D Mesh is connected to the center nodes of mesh, center connected mesh will be formed. Thus we need four extra edges to design the nÃ—n C2Mesh. To design a nxn Torus mesh 2n additional edges are required, when compared to a basic nxn mesh.
One of the important advantages of c2 mesh is that it requires only four extra links irrespective of the sizeof the mesh. This has reduced the implementation cost.
(1) 1
2
And if n is odd then center= (n*n1)/2, and corners will be connected as follows: NorthWest corner will connect to node(center), North East corner will connect to node(center), WestSouth corner will connect to node(center), SouthEast corner will connect to node(center), Means all corners will connected to single center node, figure4.
Fig.4: nÃ—n C2Mesh for odd n=5.
If n is even than center = n*(n1)/21, and the corners will be connect as follows: NorthWest corner will connect to node (center), North East corner will connect to node (center +1), West South corner will connect to node (center +n), and SouthEast corner will connect to node (center
+(n+1)), figure5.
Fig. 5: nÃ—n C2Mesh for even n=6.

C2Mesh using 2D addressing scheme.
In this method consider that network is in 2D matrix form and all nodes has a unique address in the form of node(i, j),such as first node having the address (0,0) and refer as node(0,0) and second node having address (0,1) and referred as node(0,1) and so on. In the nÃ—n network, last node will have address (n1,n 1) so will refer as node(n 1, n 1),figure6.To design the nÃ—n C2Mesh, first design simple nÃ—n 2DMesh by this addressing scheme, and find the center to connect all four corner nodes to center node(s). The center address (i,j) of the mesh can be calculated as follows:
= 1 , =
connected to node(i,j+1), WestSouth corner will connect to node(i+1,j), and South East corner will connect to node(i+1,j+1),figure7
Figure7 nÃ—n C2Mesh for even n=6.

Topological Properties
For C2Mesh network topology with nÃ—n nodes, it has the following topological properties.First of all C2Mesh ntwork is simple as Mesh, with four extra edges, while it perform like as Torus. It can be seen in the figure1 and figure2. The design and implementation is simple and easy like Mesh. Secondly, the diameter of C2Mesh network with nÃ—n nodes is n1 in all cases, except n is 2 or 4. In the case when n is 2 or 4, than its diameter is equal to n. From the distance distribution for the given node in C2Mesh network in figure1 (b) and figure 2 (b), we can see in that, the maximum distance
between two nodes in the C2Mesh network is n1.
(i, j)= 2
= 1, =
2
If n is odd than i = (n1)/2 , j = I, and the corners will be connect as follows: NorthWest corner will connect to node(i,j),NorthEast cornerwill connect to node(i ,j), West South corner will connected to node(i, j), and SouthEast corner will connected to node(i, j),means all corners connected to single center node,figure3.
Fig. 6: nÃ—n C2Mesh for odd n =5.
If n is even than i = n/21, j = i, and the corners will be connect as follows: NorthWest corner will connect to node(i,j),NorthEast corner will
Third, the bisection width of C2Mesh network with nÃ—n nodes is n in the case of even n, and n+3 in the case of odd n. The bisection width is smallest with compare to other networks. To divide a C2Meshnetwork with nÃ—n nodes into two equal sets of nodes, is easy when n is even but when n is odd, a horizon and vertical line can be drawn along with the center node of the network, let see figure 8.

6Ã—6 C2Mesh

Figure7 nÃ—n C2Mesh for even n=6.
In the table1, the topological properties comparison for different networks is given. Comparing with the other networks, with the same size nÃ—n node, the C2Mesh network has the same diameter as the torus, Mesh, Dmesh, Dtorus, and XMesh networks. The cost of a network is typically measured in terms of the number of links and the complexity of the routing nodes. For C2Mesh network with nÃ—n nodes, has node degree 4 with some nodes of degree 3, but when n is even, 4 nodes has degree 5, and when n is odd only one, center node has degree 8.


ROUTING ALGORITHM
The best feature of C2Mesh network with nÃ—n nodes, is the shortest path from any source to any destination is maximum n1, it means the shortest path length of any source to any destination node is not more than n it will be always less than n (except if n =2 or 4).
To design nÃ—n Torus, then it requires 2n extra links then nÃ—n Mesh while in the nÃ—n C2Mesh topology requires only 4 extra links, and it is fixed for any size of C2Mesh. In order to design the routing algorithm, we have implemented both methods using node numbers and using 2D addressing, but both methods uses the following set of steps: Routing Algorithm for C2Mesh (CCM routing):routing_CCM(src_node, dest_node)

Find centers of C2Mesh.

Find the corner nodes of C2Mesh.

Find submeshes1 for src_node and submesh2 fardest_node.

Move from src_node to center node of the sub mesh1if (distance of corner node +1 < distance of centernode)move from src_node to corner node than dest_node maximum n 1, it means the shortest path length of any source to any destination node is not more than n it will be always less than n (except if n =2 or 4).direct tocenter nodeelse move from src_node to center node to dest_node


CONCLUSION
The C2Mesh network is a simple improved mesh network where all four corner nodes are connected to the center of Mesh. The C2Mesh network provides the network diameter n1 in large networks, and it provides good performance then Mesh and similar to
Torus. The further study will focus on the evaluation of C2Mesh network performance with other networks.

REFERENCES

Tang K W, Padubidri S A., Diagonal and toroidal mesh networks, IEEE Transactions on Computers, 1994, 43(7), pp. 815826

Dally W J, Towles B., Principles and practices of interconnection networks, San Francisco, CA, USA:Morgan Kaufmann, 2004

Ogras U Y, Marculescu R., It's a small world after all: NoC performance optimization via longrange link insertion, IEEE Transactions on Very Large ScaleIntegration (VLSI)
Systems, 2006, 14(7), pp. 693706

Zhu X J, Hu W W, Ma K, et al., XMesh: meshlike topology for network on chip, Journal of Software, 2007, 18(9): 21942204.

Ouyang Y M, Zhu B, Liang H G, et al, Networks on chip based on diagonal interlinked mesh topology structure,
Computer Engineering, 2009, 35(22), pp. 100102

Yagang WANGa, Huimin DUb, Xubang SHENa, Topological properties and routing algorithm for semi diagonal torus networks, The Journal of ChinaUniversities of Posts and Telecommunications, Volume 18, Issue 5,
October 2011, pp.6470

C2Mesh : New Proposed Topology Lalit Kishore Arora1, Rajkumar
Properties 
Mesh 
Torus 
DMesh 
DTorus 
XMesh 
SDTorus 
Mesh 
No. of Links 
22 2 
22 
42 6+2 
42 4+2 
22 
32 
22 2+4 
No. of Nodes 
2 
2 
2 
2 
2 
2 
2 
Node Degree 
4 & 2 
4 
8, 5 & 3 
8, 6 & 5 
8,6,4 & 4 
6 
5, 4 & 3 (1 node of 8 if n is odd) 
Diameter 
2n2 
n1 
n1 
n1 
n1 
2n/3 
n1 
Bisection 
n 
2n 
3n2 
4n2 
n+4 
3n 
n(n+3 if n is odd) 
Throughput 
<=b 
<=2b 
<=2b 
<=2b 
<=2b 
<=2b 
<=2b 
Path Diversity 
Yes 
Yes 
Yes 
Yes 
No 
Yes 
Yes (No if n is odd) 
Avg Distance d=dimension 
d*n/3 
d*n/4 
d*n/4 
d*n/4 
d*n/4 
– 
d*n/4 