This paper studies the average hop count measure for virtual path layouts of ATM and optical networks.Routing in the ATM and
optical network models is based on covering the network with simple virtual paths, under some constraints on the allowed
load (i.e., the number of paths that can share an edge).The
hop count is the number of edges along the virtual path.
Two basic results are established concerning the average hop count parameter. The first concerns comparing the maximum and
average hop count measures assuming uniform all-to-all communication requirements. We develop a rather general connection
between the two measures for virtual path layouts with bounded maximum load.This connection allows us to extend known lower
bounds on the maximum hop count into ones on the average hop count for network families satisfying certain conditions, termed
non-condensingly contractable (NCC) graph families. Using this characterization, we establish tight lower bounds on the average hop count of virtual path layouts
with bounded maximum load for paths, cycles, and trees.
Our second result is an algorithm for designing a virtual path layout of minimum average hop count for a given tree network
with general (weighted) one-to-all requirements.
Department of Applied Mathematics and Computer Science, The Weizmann Institute, Rehovot, 76100 Israel. peleg@wisdom.weizmann.ac.il.Supp
orted in part by a grant from the Israel Ministry of Science and Art.
Department of Mathematics and Computer Science, Bar Ilan University, Ramat Gan 52900, Israel. uripinch@macs.biu.ac.il