Static Networks

1. Degree of a node, d, is defined as the number of channels incident on the node.
2. Diameter, D, of a network having N nodes is defined as the longest path, p, of the shortest paths between any two nodes. For example, the diameter of a $4 \times 4$ Mesh $D=6$.
3. A network is said to be symmetric if it is isomorphic to itself with any node labeled as the origin; that is, the network looks the same from any node. Rings and Tori networks are symmetric while linear arrays and mesh networks are not.

• Completely Connected Networks (CCNs);
  • the cost of a completely connected network having N nodes, measured in terms of the number of links in the network, is given by $N(N-1)/2$, that is, $O(N^ 2)$.
  • The delay (latency) complexity of CCNs, measured in terms of the number of links traversed as messages are routed from any source to any destination, is constant, that is, O(1).
  • The degree of a node in CCN is $N-1$, that is, $O(N)$, while the diameter is $O(1)$.
• Linear Array Networks (LCNs)
  • In this network architecture, each node is connected to its two immediate neighboring nodes. Each of the two nodes at the extreme ends of the network is connected only to its single immediate neighbor.
  • The network cost (complexity) measured in terms of the number of nodes of the linear array is $O(N)$.
  • The delay (latency) complexity measured in terms of the average number of nodes that must be traversed to reach from a source node to a destination node is $N/2$, that is, $O(N)$.
  • The node degree in the linear array is $2$, that is, $O(1)$ and the diameter is $(N-1)$, that is, $O(N)$.

  Figure 2.11: Performance Characteristics of Static Networks.

  
  In Fig. 2.11, the basic performance characteristics of a number of static interconnection networks are summarized. (N is the number of nodes and n is the number of dimensions)