Network Analysis Without Exponentiality Assumptions, Ph.D. Thesis

University of California at Berkeley.
Approved August 14, 1996.
Prof. Manuel Blum, Computer Science, Committee Chair
Prof. Sheldon Ross, Operations Research
Prof. Venkat Anantharam, Electrical Engineering
gzip'd postscript and pdf.


Theoretical analysis of networks often relies on exponentiality assumptions which are unrealistic but necessary for mathematical tractability. In some cases these assumptions are inconsequential, but in others their adoption may lead to invalid results.

We consider two broad areas of network analysis in which exponentiality assumptions are often used: The first of these is delay analysis of packet-routing networks. Delays occur in such networks when multiple packets seek to pass simultaneously through a bottleneck -- i.e., a part of the network which can accommodate only a single packet at a given time. The goal of the analysis is to determine the average packet delay associated with a particular routing scheme and arrival rate. Frequently, for analytic tractability, bottleneck times are modeled as independent exponentially-distributed random variables, which is often inaccurate.

A second area of analysis employing such assumptions is CPU load balancing in networks of time-sharing workstations. Processes are continually generated at workstations and may at any point be migrated (for a price) to another workstation in an effort to minimize the average process slowdown. The aim of the analysis is to develop and evaluate effective migration strategies. For analytical tractability, process CPU lifetimes (total CPU usage) are commonly modeled as exponentially-distributed random variables. However our measurements show process lifetime distributions are actually Pareto (inverse-polynomial).

For the case of packet-routing, we prove that for a large class of networks, the exponentiality assumptions always yield an upper bound on the actual average packet delay. This result validates the use of exponential service-time assumptions in queueing-theoretic analysis.

In contrast, we show that the exponentiality assumptions made in the analysis of process migration can yield incorrect results. This is potentially true even for models which accurately reflect CPU lifetime distributions in the first two moments. We introduce a new general technique whereby our measured process lifetime distribution is applied to derive a highly effective load balancing policy, without resorting to exponentiality assumptions. Also via the process lifetime distribution, we answer the long unresolved question of whether migrating active processes (preemptive migration) is necessary for load balancing, or whether migrating newborn jobs (remote execution) suffices.

Back to Mor's Home Page .