MIRAGE: A Model for

Latency in Communication*

Author: Joseph D. Touch

Supervisor: David J. Farber

November 19, 1991

ABSTRACT

Mirage is an abstract model for the design and analysis of high speed wide area network (WAN) protocols. It examines the effects of latency on communication, and indicates that information separation is the distinguishing characteristic of gigabit WANs. Existing protocols will exhibit performance failures due to an inability to accommodate imprecision in the remote state. The name Mirage denotes the difficulty with latent communication, namely nodes never really ?see? each other precisely; rather, they work with (and around) the mirages which high speed and fixed latency conjure before them.

This dissertation describes the Mirage abstract model, as an extended finite state machine that accommodates imprecision via multiple simultaneous states and state space volume transformations. We introduce guarded messages, to accommodate nondeterministic data streams, and communicability, the upper bound on communication, given fixed latency and state predictability. Mirage demonstrates how excess bandwidth can be used to accommodate latency, and shows the bounds on latency constrained communication. Future work includes considering Mirage as an extension of Shannon?s communication theory, and comparing it to physics analogues.

Mirage was applied to the Network Time Protocol (NTP), to demonstrate its use and exemplify its abstract components. We show the equivalence between variation in state space imprecision and variation in transmission latency. Several ?optional? components of the NTP specification are shown to be required, and layering is violated in permitting sender anticipation.

To show the model?s advantages, Mirage was applied to processor - memory interaction as a

protocol, calling the result mNet (MicroNet). Using anticipation, we develop a novel interface which achieves a hit rate equivalent to that of a 50K byte cache, using 400 bytes of storage (patent

pending). mNet complements conventional cache techniques, especially where communication latency is the limiting factor in code execution, and where excess communication bandwidth is available. Dynamic traces measured the latency accommodation possible by the various implementation versions. We developed the TreeStack to manage multiple alternate states and

recursion in a single data structure; this structure may be of more general interest. Further mNet measurements would indicate the feasibility of a complete implementation, perhaps directly in hardware.

* This work is supported by the Information Science and Technology Office of the Defense Advanced Research Projects Agency, under contract NAG-2-639, and by an AT&T Graduate Research Fellowship, grant #111349.