Mesh Distance Formulae
Abstract
The author's study of mesh distance-distributions was prompted by his study of routing network simulator convergence. The variance of the path-length distribution in a mesh routing network affects the convergence of simulators used for studying routing networks. For a fine-grained multicomputer, such as the Mosaic, the number of distinct (src, dst) pairs is too large to simulate every path. Various network parameters converge to their true, asymptotic values as the average distance of the sampled paths converges to the mean distance. The first section of this report derives summation formulae used in subsequent calculations. A recursive technique for calculating a family of formulae is derived and it is used to deduce the needed equations. A Mathematica package that can be used to compute any formula in the family also is derived. The second section develops a recursive technique for computing the distance distribution of any mesh. The distributions of one- and two-dimensional meshes are derived explicitly. The third section computes the mean and variance of the distance distribution. Calculating the variance was the original motivation for studying the distribution, but it was discovered that the moments of the distribution could be computed without knowing the distribution. The final section presents a simple program that directly computes the distance distribution of any mesh. This program can be used to check the analytical results and to measure properties for which no equations are presented.
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 27, 1992
- Accession Number
- ADA447933
Entities
People
- Michael J. Pertel
Organizations
- California Institute of Technology