Exact Formulas for the Average Internode Distance in Mesh and Binary Tree Networks

The average internode distancein an interconnection network (or its average distance for short) is an indicator of expected message latency in that network under light and moderate network traffic. Unfortunately, it is not always easy to find an exact value for the average internode distance, particularly for networks that are not node-symmetric, because the computation must be repeated for many classes of nodes. In this short paper, we derive exact formulas for the average internode distance in mesh and complete binary tree networks.