This dissertation is the first evaluation of Mirage as an abstract model. We have discussed the impetus for the model and described the components of the model. Mirage has been described by its application to an existing protocol to exemplify its abstract components, and has been used to design a new protocol to illustrate components not manifested in existing protocols.
The Mirage model has been useful in refining our questions as to why existing protocols may fail in the gigabit, wide-area domain. Mirage has also presented one possible solution to the predicted failure. Further, the model was used to design a novel processor-memory interface, for which a patent has been applied.
Before we elaborate on these conclusions, a review of previously presented conclusions may be useful, especially because of the conglomeration of discussions contained herein.
Mirage began with a discussion based on the question of whether existing protocols would ÔfailÕ in gigabit, wide-area networks. We concluded that existing protocols will exhibit a performance failure in domains where information separation is high, due to their inability to accommodate variability in the communicated data stream.
Existing protocols are largely based on connection establishment and management, whereas we define the protocol as facilitating the communication of the data itself. This leads to our description of the limitation of interaction in the presence of latency, based on the limitations of the channel, and the extent to which the interaction is known to be constrained.
ÒWhat we have here is a failure to communicateÓ - the Warden, in Cool Hand Luke
This discussion led to the formulation of the domain in which the Mirage model is applicable. This domain is based on a set of tenets, listed in Chapter 2, and repeated below.
TENET 1: Communication is logical information synchrony among information separated entities
TENET 2: A protocol is a mechanism for maintaining communication
TENET 3: Information
separated entities are separated in time*space, in units of pending-information
TENET 4: Bandwidth-delay
product is a measure of information separation
The Mirage model was described in terms of transformations on state space subsets. This description led to our definitions of stability and communicability. Communicability in turn led to the development of guarded messages to partition the state space, and isopotency as the description of the way in a set of physical guarded messages represents a single logical message.
Mirage describes how error and latency are conjugates, and that the tradeoff between them is determined by the extent of existing constraints, the variance in behavior of a remote entity, the latency with which that behavior is measured, and the precision to which that behavior is modeled.
Existing protocols were used to exemplify the components of the abstract Mirage model. Describing the model components of Mirage as they applied to NTP showed the violation of layering in the protocol, because the internal, optional algorithms were required for the description of the state space transformations and partitioning. Some of the constraint conditions were also modified as the result of this work.
Analysis of NTP also indicated that Mirage applied not only to fixed latency variable state systems, but also fixed state variable latency systems. This demonstrated the equivalence between variance in state and variance in latency.
Finally, the measurements of NTP were verified from the Mirage model by using the probability density function (pdf) interpretation of the Mirage constraint equations, where the set-notation version of the temporal transformation is expressed in terms of pdf convolutions.
Mirage was also applied to a new domain, that of processor-memory interaction, to exhibit some of its components which existing protocols did not manifest. The result, m‑Net (MicroNet) showed the use of guarded messages, isopotency, and anticipation of the Mirage model. Measurements indicate that the simple branching stream model of Mirage was reasonable for a real instance of a protocol, and that an implementation of m‑Net was feasible.
Comparisons of the anticipation of m‑Net indicate that a version with as little as 400 bytes of storage can reduce the effects of latency as well as a 50K byte cache. m‑Net reduces the penalty of latency using data management, anticipation, and increased bandwidth utilization (both channel and memory bandwidth).
The application of Mirage has resulted in a novel design, for which a patent has been applied. Various levels of implementation were described, corresponding to various partitions of the state space, as proscribed in the Mirage communicability and stability criteria.
Furthermore, existing research in anticipatory memory interfaces was extended through the application of Mirage. Finally, we developed a formula describing the speedup limitations, with respect to existing protocols (a Mirage version of AmdahlÕs Law).
The description of Mirage and the applications to which Mirage was applied were presented here in chronological order. This was an exercise in the creation of an abstract model to describe a phenomenon, although the phenomenon was expected and not observed. We predict that the performance failure of existing protocols will be due to an increase in information separation. Under this assumption, the Mirage model is an effective model, both to describe the failure and to indicate methods to avoid it.
This research differs from many other gigabit protocol analyses because it is based on initial principles of communication and interaction, rather than as an extension to existing protocol instances. Mirage shows that layering is detrimental to high speed protocols, not only on performance grounds, but because it is semantically incompatible with state space partitioning required for communicability and stability constraints.
We began this discourse with a set of 6 questions, discussed in Chapter 1, and repeated, and addressed below.
1) Existing protocols show substantial drops in channel utilization in domains with high bit-latency.
The performance failure in existing protocols is due to their inability to anticipate sufficient information to occupy the round trip latency. The drop in channel utilization is the result of this inability; protocols that are able to anticipate can surpass the performance of existing protocols. The limitation of anticipation protocols is the result of an unmanageable expansion in the state of the receiver, and thus represents a constraint of the communication itself, rather than the protocol mechanism chosen.
2) The advantages to modeling the endpoints of the link, rather than the channel itself.
If the channel is modeled, as in ShannonÕs communication model [Sh63], transmission errors can be accommodated (i.e., corrected). If the endpoints are modeled (Mirage), latency can be accommodated (i.e., compensated via anticipation).
3) Why we conclude that the sender should anticipate the receiver.
Sender anticipation is the consequence of partitioning the state space of the senderÕs perception of the receiver. Communicability is possible when the partition is efficient, and when that partition is used by the sender to maintain stability.
4) How this results in a tradeoff between error and bit-latency.
The tradeoff between error and latency is a tradeoff between communicability and stability. If a larger state space (i.e., larger error) is considered the stable set, then more latency can be tolerated. Reduction of errors is facilitated by constriction of the stability state, corresponding to a lower bit-latency over which state expansion must be compensated.
5) Why achieving increased channel utilization necessitates avoiding layered protocols, i.e., why we need to look inside packets.
If the partitioning cannot be determined, latency cannot be tolerated. Layering prohibits the efficient partitioning of the state space via semantic information of the temporal transformation expansion. In effect, layering clouds the description of the expansion of the perception of a remote state; if the expansion is hidden, it cannot be predictably anticipated or managed.
6) There is a limit to how well we can get around things, which is a function of:
a) variability in the receiver state
b) bit-latency
c) power of the sender to accommodate this variability
d) ability of the channel to accommodate this variability
The limit to Òhow well we can get around thingsÓ is communicability, which is a measure of the extent to which stability can be maintained. Communicability decreases with bit-latency increases or with increases in receiver variance, because either permits the perception of the remote state to expand more rapidly. The power of sender accommodation is determined by the degree to which an efficient partition of this perception can be determined. Channel accommodation is determined by bandwidth, in its ability to transfer the entire isopotent set in the latency given.
Mirage provides a model for understanding the effects of latency on communication. It differs substantially from existing models, and was useful both in the description of an existing protocol and in the design of a new protocol. Mirage reduces to conventional models where information separation approaches zero, because it is an extension of finite state models into a state space subset model.
ÒIt is better to debate a question
without
settling it
than to settle a question
without
debating it.Ó
-
Joseph Joubert, 1754-1824,
in In Search of SchršdingerÕs
Cat [Gr84]
The most important result of this work is the questions that were asked. Mirage is a model in which the effects of latency can be considered, and in which performance failures of existing protocols can be considered. Issues of layering, stability, and the limitation of communication in the presence of high bandwidth-delay products can be discussed though the use of the Mirage model.
This dissertation presented the Mirage model, and provided some examples of its use in protocol analysis and design. The model can be further developed as an abstract medium for protocol science. Mirage can also be applied to other protocols, to analyze their effectiveness or examine their limitations in the presence of latency. The protocol developed as part of this research, m‑Net, can also be further investigated, and an implementation developed.
Mirage was described as an abstract model for latency. The Mirage model concept transcends the actual model description; it is the incorporation of imprecision and temporal constraints to existing models. The description in this dissertation was presented as an extension to existing finite state machine models (and elaborated in Appendix E), but can be described in terms of other existing models as well. One such example uses Petri Nets as the corresponding existing model (Appendix F). The Mirage model can also be interpreted as an extension of ShannonÕs communication model, as a temporal extension to that work. Preliminary description of this interpretation appears in Appendix A.
Mirage was developed by applying intuition from analogs in physics, notably particle interactions, to communication issues. The correlation between Mirage and physics may also be of more formal interest. A discussion of some analogs used in the development of the model appears in Appendix B.
The TreeStack is another abstract component of Mirage which may have more general application. Further investigation of this data structure, and whether it exists or is useful in other domains, may prove useful.
Mirage can be used to analyze protocols that are more intricate than NTP. Current protocol research is focusing on issues of flow control, both anticipatory and reactive. Application of Mirage to flow protocols may assist in this analysis.
Mirage can also be used to design other new protocols, as it was used herein to develop m‑Net. Future work on m‑Net includes emulation to measure the feasibility of a Total anticipatory design, to determine the space requirements for a given latency. An implementation of m‑Net, either in software or directly in hardware, would also be useful in further analysis of the benefits of this protocol.
[Ag83] Aggarwal, S. and
Kurshan, R.P., ÒModeling Elapsed Time in Protocol Specification.Ó In Protocol
Specification, Testing, and Verification.
North-Holland, Rudin, H. and West, C.H., (Eds), pp. 51-62, 1983.
[An67] Anderson, D.W., Sparacio,
F.J., and Tomasulo, R.M., ÒThe IBM System/360 Model 91 Machine Philosophy and
Instruction-Handling.Ó IBM Journal of Research and Development (Jan. 1967), pp. 8-24.
[An88] Anderson, D.P., ÒAutomated
protocol implementation with RTAG.Ó IEEE Transactions on Software
Engineering V. SE-14, N.3 (Mar. 1988), pp. 291-300.
[As56] Ashby, W. Ross, An
Introduction to Cybernetics, Methuen,
London, (1956).
[Ba90a] Balraj, Timothy S. and Yemini,
Yechiam, ÒPROMPT - A Destination Oriented Protocol for High Speed Networks.Ó In
Participant's Proceedings, International Workshop on Protocols for
High-Speed Networks, IFIP WG 6.1/WG
6.4, Palo Alto, CA, Nov. 1990.
[Ba90b] Bakoglu, H.B. and Whiteside, T.,
ÒIBM RISC System/6000 Hardware Overview.Ó IBM Journal of Research and
Development (1990).
[Be87] Bertsekas, Dimitri and
Gallager, Robert, Data Networks,
Prentice-Hall (1987).
[Be91] Benitez, Manuel E. and
Davidson, Jack W., ÒCode Generation for Streaming: an Access/Execute
Mechanism.Ó In ASPLOS-IV, ACM,
1991, pp. 132-141.
[Bo78] Bochmann, Gregor V.,
ÒFinite State Description of Communication Protocols.Ó Computer Networks, N.2 (1978), pp. 361-372, Pub. by North-Holland.
[Bu62] Buchholz, Werner, (Ed),
Planning a Computer System: Project Stretch, McGraw-Hill (1962), pp. 229-248.
[Ca70] Carr, C.S., Crocker,
S.D., and Cerf, Vint G., ÒHOST-HOST Communication Protocol in the ARPA
Network.Ó In Spring Joint Computer Conference, AFIPS, 1970, pp. 589-597.
[Ca91] Callahan, David,
Kennedy, Ken, and Porterfield, Allan, ÒSoftware Prefetching.Ó In ASPLOS-IV, ACM, Also: SIGARCH Computer Architecture News, V. 19,
N. 2; SIGOPS Operating Systems Review, V.25 Special Issue; SIGPLAN Sigplan
Notices, V. 26, N. 4, Apr. 1991, pp. 40-52.
[Ch81] Choi, Tat Y. and Miller,
Raymond E., ÒProtocol Analysis and Synthesis by Structured Partitions.Ó Computer
Networks, N.6 (1981), pp. 367-381,
Pub. by North-Holland.
[Ch86] Cheriton, David R., ÒVMTP: A
Transport Protocol for the Next Generation of Communication Systems.Ó In Communications
Architectures and Protocols, ACM
Sigcomm, ACM Press, Stowe, VT, Also Computer Communication Review, V. 16, N. 3,
Aug. 1986, pp. 406-415.
[Ch88a] Chesson, Greg, Eich, Brendan, Schryver,
Vernon, Cherenson, Andrew, and Whaley, Al, XTP Protocol Definition Revision 3.0. Tech. Rept. Protocol Engines, Inc., 1900 State
Street, Suite D, Santa Barbara, CA 93101, Jan., 1988.
[Ch88b] Cheriton, David, VMTP: Versatile Message
Transaction Protocol. Tech. Rept.
RFC-1045, DARPA Network Working Group Report, Stanford University, Feb., 1988.
[Ch89] Cheriton, David R. and
Williamson, Carey L., ÒVMTP as the Transport Layer for High-Performance
Distributed Systems.Ó IEEE Communications Magazine (Jun. 1989), pp. 37-44.
[Ch91] Cheriton, David, Dissemination-Oriented
Communication Systems. Mar. 1991,
Presented at the DARPA Networking Principal Investigator's Meeting, Monterey
CA.
[Cl87] Clark, David D.,
Lambert, Mark L., and Zhang, Lixia, NetBlt: A Bulk Data Transfer Protocol. Tech. Rept. RFC-998, DARPA Network Working Group
Report, MIT, Mar. 1987.
[Cl89] Clark, D.,
Jacobson, V., Romkey, J., and Salwen, H., ÒAn analysis of TCP processing
overhead.Ó IEEE Communications Magazine V. 27 (Jun. 1989), pp.
23-29.
[Co91a] Comer, Douglas E., Internetworking
with TCP/IP - Principles, Protocols, and Architecture, Prentice-Hall, Englewood Cliffs, NJ, Vol. 1 (1991).
[Co91b] Comer, Douglas E., Internetworking
with TCP/IP - Principles, Protocols, and Architecture, Prentice-Hall: Englewood Cliffs, NJ, Vol. I (1991),
pp. 199.
[Cr89] Cristian, Flaviu, ÒA
Probabilistic Approach to Distributed Clock Synchronization.Ó In Ninth IEEE
International Conference on Distributed Computing Systems, IEEE, Jun. 1989, pp. 288-296.
[De73] DeWitt, Bryce and
Graham, Neill, (Eds), The Many-Worlds Interpretation of Quantum Mechanics, Princeton University Press, Princeton, NJ (1973).
[Di76] Dijkstra, E.W., A
Discipline of Programming,
Prentice-Hall, NJ (1976).
[Do77] Doyle, Jon, Truth
Maintenance Systems for Problem Solving. Tech. Rept. MIT AI Lab TR-419, MIT, Cambridge, MA, Sept., 1977.
[Do79] Doyle, Jon, ÒA Truth
Maintenance System.Ó Artificial Intelligence V. 12,
N.3 (1979).
[Do89] Dollas, Apostolos and
Krick, Robert F., ÒThe Case for the Sustained Performance Computer
Architecture.Ó Computer Architecture News V. 17, N.6 (Dec. 1989),
pp. 129-136.
[Do90] Doeringer, Willibald
A., Dykeman, Doug, Kaiserswerth, Matthias, Meister, Bernd Werner, Rudin, Harry,
and Williamson, Robin, ÒA Survey of Light-Weight Transport Protocols for
High-Speed Networks.Ó IEEE Transactions on Communications V. 38,
N.11 (Nov. 1990), pp. 2025-2039.
[Fa76a] Farber, David J. and Pickens, John
R., ÒThe Overseer: A Powerful Communications Attribute for Debugging and
Security in Thin-Wire Connected Control Structures.Ó In IEEE International
Communications Conference, IEEE,
1976.
[Fa76b] F8 Guide to Programming, Fairchild Camera and Instrument Corporation,
Mountain View, CA, 1976.
[Fa76c] F8 User's Guide, Fairchild Camera and Instrument Corporation,
Mountain View, CA, 1976.
[Fe90a] Feldmeier, David C.,
ÒMultiplexing Issues in Communication System Design.Ó In Communications
Architectures and Protocols, ACM
Sigcomm, ACM Press, Also Computer Communications Review, V. 20, N. 4, Sept.
1990, pp. 209-219.
[Fe90b] Ferrari, Domenico and Verma, Dinesh
C., ÒReal-Time Communication in a Packet-Switching Network.Ó In Participant's
Proceedings, International Workshop on Protocols for High-Speed Networks, IFIP WG 6.1/WG 6.4, Palo Alto, CA, Nov. 1990.
[Fe90c] Feldmeier, David C. and
Biersack, Ernst W., ÒComparison of Error Control Protocols for High
Bandwidth-Delay Product Networks.Ó In Participant's Proceedings,
International Workshop on Protocols for High-Speed Networks, IFIP WG 6.1/WG 6.4, Palo Alto, CA, Nov. 1990.
[Fr89] Fraser, A.G.,
ÒThe Universal Receiver Protocol.Ó In Protocols for High-Speed Networks, Rudin, Harry and Williamson, Robin, (Eds), IFIP,
North-Holland, 1989, pp. 19-25.
[Ga65] Gamow, George, Mr.
Tompkins in Paperback, Cambridge
University Press, NY (1965).
[Gi79] Gifford, D.K.,
ÒWeighted Voting for Replicated Data.Ó In Symposium on Operating System
Principles, ACM Sigops, Dec. 1979,
pp. 150-159.
[Go] Gouda,
M.G., Sabnani, K.K., and Netravali, A.N., Self-stabilizing and Correctness
Properties of a New Class of High Speed Transport Protocols. (To appear).
[Go86] Gove, Philip Babcock,
(Ed), Webster's Third New International Dictionary of the English Language,
Unabridged, Merriam-Webster, Springfield, MA (1986).
[Go88] Gotzhein, Reinhard,
ÒKnowledge-oriented consideration of communication protocols.Ó In Protocol
Specification, Testing, and Verification.
North-Holland, Aggarwal, S. and Sabnani, K., (Eds), pp. 295-306, 1988.
[Go90] Golestani, S.
Jamaloddin, ÒA Stop-and-Go Queuing Framework for Congestion Management.Ó In Communications
Architectures and Protocols, ACM
Sigcomm, ACM Press, Also Computer Communication Review, V. 20, N. 4, Sept.
1990, pp. 8-18.
[Gr84] Gribbin, John, In
Search of Schršdinger's Cat, Bantam
Books, Toronto (1984).
[Gr87] Graham, William R.,
ÒResearch and Development Strategy for High Performance Computing.Ó In Report
of the Executive Office of the President.
Office of Science and Technology Policy, Nov., 1987.
[Ha28] Hartley, R.V.L.,
ÒTransmission of Information.Ó Bell System Technical Journal V. 7 (1928),
pp. 535-563.
[Ha84] Halpern, Joseph Y. and
Moses, Yoram, ÒKnowledge and Common Knowledge in a Distributed Environment.Ó In
Symposium on Principles of Distributed Computing, ACM Sigops-Sigact, ACM Press, Aug. 1984.
[Ha87] Halang, Wolfgang A., ÒA
Distributed Logic Program Instruction Prefetching Scheme.Ó Microprocessing
and Microprogramming V. 19 (1987), pp. 407-415.
[Ha88a] Halsall, Fred, Data
Communications, Computer Networks, and OSI, Addison Wesley, Second (1988).
[Ha88b] Hawking, Stephen W., A Breif History
of Time, Bantam Books, Toronto (1988).
[Ha91] Halliwell, Jonathan J.,
ÒQuantum Cosmology and the Creation of the Universe.Ó Scientific American (Dec. 1991), pp. 28-35.
[He90] Hennessy, John L. and
Patterson, David A., Computer Architecture: A Quantitative Approach, Morgan Kaufmann, San Mateo, CA (1990).
[Hi56] Hill, T.L., Statistical
Mechanics, McGraw-Hill, NJ (1956).
[Ho78] Hoare, C.A.R.,
ÒCommunicating Sequential Processes.Ó Communications of the ACM V. 21,
N.8 (1978).
[Hs86] Hsu, Peter Y.T. and
Davidson, Edward S., ÒHighly Concurrent Scalar Processing.Ó IEEE Computer
Architecture (1986), pp. 386-395.
[IB90] Assembler Language
Reference for IBM AIX Version 3 for RISC System/6000, IBM Corporation, Austin, TX, 1990.
[II87] III, Jacob J.
Wolf and Ghosh, Biswadip, ÒModeling Very Large Area Networks (VLAN) Using and
Information Flow Approach.Ó In Symposium on the Simulation of Computer
Networks, IEEE Computer Society, IEEE
Computer Society Press, Aug. 1987, pp. 36-44.
[IS88a] ISO, LOTOS - a formal
description technique based on the temporal ordering of observational behavior. Tech. Rept. ISO-8807, International Organization for
Standardization, 1988.
[IS88b] ISO, Estelle - a formal description
technique based on an extended state transition model. Tech. Rept. ISO-8807, International Organization for
Standardization, 1988.
[Ja55] Jacobson, Homer,
ÒInformation, Reproduction and the Origin of Life.Ó American Scientist V. 43,
N.1 (Jan. 1955), pp. 119-127.
[Ja84] Jay, Frank, (Ed),
IEEE Standard Dictionary of Electrical and Electronics Terms, IEEE Inc., NY, ANSI/IEEE Standard 100-1984 (1984).
[Ja88a] Jacobson, V. and Braden, R.,
TCP Extensions for Long-Delay Paths.
Tech. Rept. RFC-1072, DARPA Network Working Group Report, Lawrence Berkeley
Labs and Information Sciences Institute, CA, Oct., 1988.
[Ja88b] Jacobson, Van, ÒCongestion
Avoidance and Control.Ó ACM Computer Communication Review (Oct. 1988), pp. 314-329.
[Ja89] Jain, Raj, ÒA
Delay-Based Approach for Congestion Avoidance in Interconnected Heterogeneous
Computer Networks.Ó ACM Computer Communication Review V. 19,
N.5 (Oct. 1989), pp. 56-71.
[Ja90] Jain, Raj, Myths
About Congestion Management in High-Speed Networks. Tech. Rept. DEC-TR-726, Digital Equipment Corp.,
Littleton, MA, Oct. 1990.
[Je85] Jefferson, David
R., ÒVirtual Time.Ó ACM Transactions on Programming Languages and Systems V. 7,
N.3 (Jul. 1985), pp. 404-425.
[Ka85] Karplus, Kevin and
Nicolau, Alexandru, ÒEfficient Hardware for Multi-way Jumps and Pre-fetches.Ó IEEE
Micro V. 18 (1985), pp. 11-18.
[Ka86] Karplus, Kevin and
Nicolau, Alexandru, ÒGetting High Performance with Slow Memory.Ó In 31st
IEEE Computer Society International Conference, IEEE, 1986, pp. 248-253.
[Ka91] Katevenis, Manolis and
Tzartzanis, Nestoras, ÒReducing the Branch Penalty by Rearranging Instructions
in Double-Width Memory.Ó In ASPLOS-IV, ACM, 1991, pp. 15-27.
[Kl75] Kleinrock,
Leonard, Queueing Systems: Theory,
Wiley, NY, Vol. 1 (1975).
[Ko90] Ko, Keng-Tai, Mishra,
Partho P., and Tripathi, Satish K., ÒPredictive Congestion Control in
High-Speed Wide-Area Networks.Ó In Participant's Proceedings, International
Workshop on Protocols for High-Speed Networks, IFIP WG 6.1/WG 6.4, Palo Alto, CA, Nov. 1990.
[Kr85] Kritzinger, Pieter S.,
ÒAnalyzing the Time Efficiency of a Communication Protocol.Ó In Protocol
Specification, Testing, and Verification.
North-Holland, Yemeni, Y., Strom, R., and Yemeni, S., (Eds), pp. 527-539, 1985.
[Kr91] Krick, Robert F. and
Dollas, Apostolos, ÒThe Evolution of Instruction Sequencing.Ó IEEE Computer (Apr. 1991), pp. 5-15.
[La82] Lam, Simon S. and
Shankar, A. Udaya, ÒAn Illustration of Protocol Projections.Ó In Protocol
Specification, Testing, and Verification.
North-Holland, Sunshine, C., (Ed), pp. 343-360, 1982.
[La86] Lam, Simon S.,
ÒProtocol Conversion – Correctness Problems.Ó In Communications
Architectures and Protocols, ACM
Sigcomm, ACM Press, Stowe, VT, Also Computer Communication Review, V. 16, N. 3,
Aug. 1986, pp. 19-29.
[La90] Larus, James R.,
Abstract Execution: A Technique for Efficiently Tracing Programs. Tech. Rept. #912, Computer Sciences Technical Report,
University of Wisconsin-Madison, Madison, WI, Feb. 1990.
[Le84] Lee, Johnny K.F. and
Smith, Alan Jay, ÒBranch Prediction Strategies and Branch Target Buffer
Design.Ó IEEE Computer V. 17, N.1 (Jan. 1984), pp. 6-22.
[Le87] Lee, Roland L., Lew,
Pen-Chung, and Lawrie, Duncan H., ÒData Prefetching in Shared Memory
Multiprocessors.Ó In International Conference on Parallel Processing, IEEE, 1987, pp. 28-31.
[Li87] Lin, F.J., Chu,
P.M., and Liu, M.T., ÒProtocol Verification Using Reachability Analysis: The
State Space Explosion Problem and Relief Strategies.Ó In Communications
Architectures and Protocols, ACM
Sigcomm, ACM Press, 1987, pp. 126-135.
[Li88] Lilja, David J.,
ÒReducing the Branch Penalty in Pipelined Processors.Ó IEEE Computer (Jul. 1988), pp. 47-55.
[Ma84] MacGregor, Doug, Mothersole,
Dave, and Moyer, Bill, ÒThe Motorola MC68020.Ó IEEE Micro V. 4,
N.4 (Aug. 1984), pp. 101-118.
[Ma85] Marzullo, Keith and Owicki, Susan,
ÒMaintaining Time in a Distributed System.Ó ACM Operating Systems Review V. 19,
N.3 (Jul. 1985), pp. 44-54.
[Me76] Merlin, Phillip M. and
Farber, David J., ÒOn the Recoverability of Communication Protocols.Ó In IEEE
International Communications Conference,
IEEE, 1976, pp. 21-26.
[Mi80] Milner, R.E., A
Calculus of Communicating Systems,
Springer-Verlag, Berlin, Germany (1980).
[Mi85] Mills, David L.,
Network Time Protocol. Tech. Rept.
RFC-958, DARPA Network Working Group Report, M/A-COM Linkabit, Sept., 1985.
[Mi88] Mills, David L.,
Network Time Protocol (Version 1), Specification and Implementation. Tech. Rept. RFC-1059, DARPA Network Working Group
Report, University of Delaware, Jul., 1988.
[Mi89a] Mills, David L., Internet time
synchronization. Tech. Rept.
RFC-1129, DARPA Network Working Group, University of Delaware, Oct., 1989.
[Mi89b] Mills, David L., Network Time
Protocol (Version 2), Specification and Implementation. Tech. Rept. RFC-1119, DARPA Network Working Group
Report, University of Delaware, Sept., 1989.
[Mi90a] Mills, David L., ÒInternet
Architecture Workshop: Future of the Internet System Architecture and TCP/IP
Protocols.Ó ACM Computer Communication Review V. 20,
N.1 (Jan. 1990), pp. 6-17, Report of workshop chair..
[Mi90b] Mills, David L., Network Time
Protocol (Version 3), Specification and Implementation. Tech. Rept. RFC-xxxx, DARPA Network Working Group
Report, University of Delaware, Jul., 1990.
[Mo82] Moli, Gesualdo Le, Palazzo,
Sergio, and Andreoni, Gaetano, ÒA Model of Entity for the Definition of
Protocols, Services, and Interfaces.Ó In Protocol Specification, Testing,
and Verification. North-Holland,
Sunshine, C., (Ed), pp. 249-258, 1982.
[Mo89] MC68040 User's Manual, Motorola, 1989.
[Ne90] Netravali, Arun N.,
Roome, W.D., and Sabnani, K., ÒDesign and Implementation of a High-Speed
Transport Protocol.Ó IEEE Transactions on Communications V. 38,
N.11 (Nov. 1990), pp. 2010-2024.
[Ni91] Nicholson, A.,
Golio, J., Borman, D.A., Young, J., and Roiger, W., ÒHigh Speed Networking at
Cray Research.Ó ACM Computer Communication Review V. 21,
N.1 (Jan. 1991), pp. 99-110.
[Oe90] Oehler, Richard and
Groves, Randy D., ÒIBM RISC System/6000 Processor Architecture.Ó IBM Journal
of Research and Development V. 34, N.1 (Jan. 1990), pp. 23-36.
[Ok86] Okumra, Kaoru, ÒA Formal
Protocol Conversion Method.Ó In Communications Architectures and Protocols, ACM Sigcomm, ACM Press, Stowe, VT, Also Computer
Communication Review, V. 16, N. 3, Aug. 1986, pp. 30-37.
[Os76] Osborne, Adam, An
Introduction to Microcomputers: Some Real Products, Adam Osborne and Associates: Berkeley, CA, Vol. 2
(1976), Chapter 2.
[Pa90a] Partridge, Craig, ÒHow Slow is One
Gigabit Per Second?.Ó ACM Computer Communication Review V. 20,
N.1 (Jan. 1990), pp. 44-53.
[Pa90b] Partridge, Craig, Workshop Report:
Internet Research Steering Group Workshop on Very-High-Speed Networks. Tech. Rept. RFC-1152, DARPA Network Working Group
Report, BBN Systems and Technologies, Apr., 1990.
[Pa91] Partridge, Craig, Late
Binding (working title), Ph.D.
dissertation, in progress, Harvard University, 1991.
[Pe62] Petri, C.A., Communication
with automata, Ph.D. dissertation,
Darmstadt Institute of Technology, Bonn, Germany, 1962.
[Pe77] Peterson, J.L.,
ÒPetri Nets.Ó ACM Computing Surveys
V. 9, N.3 (Sept. 1977), pp.
223-252.
[Pe80] Pease, M.,
Shostak, R., and Lamport, L., ÒReaching Agreement in the Presence of Faults.Ó Journal
of the ACM V. 27, N.2 (1980), pp. 228-234.
[Pe89] Penrose, Roger, The
Emperor's New Mind, Oxford University
Press, Oxford (1989).
[Pl80] Plotkin, G.D.,
ÒDijkstra's Predicate Transformers and Smyth's Powerdomains.Ó In Abstract
Software Specifications. LNCS 86,
Bj¿rner, D., (Ed), 1980.
[Po80] Postel, Jon, User
Datagram Protocol. Tech. Rept.
RFC-768, DARPA Network Working Group Report, USC Information Sciences
Institute, Aug., 1980.
[Po81a] Postel, Jon, Transmission Control
Protocol. Tech. Rept. RFC-793,
DARPA Network Working Group Report, Information Sciences Institute, CA, Sept.,
1981.
[Po81b] Postel, Jon, Internet Protocol -
DARPA Internet Program Protocol Specification. Tech. Rept. RFC-791, DARPA Network Working Group
Report, USC Information Sciences Institute, Sept., 1981.
[Po81c] Postel, Jon, Internet Control
Message Protocol. Tech. Rept.
RFC-792, DARPA Network Working Group Report, USC Information Sciences
Institute, 1981.
[Po83] Postel, Jon, Time
Protocol. Tech. Rept. RFC-868,
DARPA Network Working Group Report, USC Information Sciences Institute, May,
1983.
[Po88] Postel, Jon, ÒSummary
of National Communcation Initiative Issues.Ó In Report on the Advanced
Computer Communication Workshop.
Information Sciences Institute, pp. 43-44, CAMar., 1988.
[Ra78] Randell, R., Lee, P.A.,
and Treleaven, P.C., ÒReliability Issues in Computing System Design.Ó ACM
Computing Surveys V. 10, N.2 (Jun. 1978), pp. 123-166.
[Ra87] Raveche, Harold J., ÒA
National Computing Initiative.Ó In SIAM Workshop Report. SIAM, Phila, PA1987.
[Ra88] Ramakrishnan, K.K. and
Jain, Raj, ÒA Binary Feedback Scheme for Congestion Avoidance in Computer
Networks with a Connectionless Network Layer.Ó In Communications
Architectures and Protocols, ACM
Sigcomm, ACM Press, 1988, pp. 303-313.
[Re91] Renteln, Paul, ÒQuantum
Gravity.Ó American Scientist V.
79, N.6 (Nov.-Dec. 1991), pp.
508-527.
[Ri72] Riseman, Edward
M. and Foster, Caxton C., ÒThe Inhibition of Potential Parallelism by
Conditional Jumps.Ó IEEE Transactions on Computers (Dec. 1972), pp. 1405-1411.
[Ro90] Rose, Marshall T., The
Open Book: A Practical Perspective on OSI, Prentice Hall (1990).
[Sa89] Sabnani, K. and
Netravali, A., ÒA High-Speed Transport Protocol for Datagram / Virtual Circuit
Networks.Ó In Communications Architectures and Protocols, ACM Sigcomm, ACM Press, Also Computer Communications
Review, V. 19, N. 4, Sept. 1989, pp. 146-157.
[Sa90] Sanders, Robert M. and
Weaver, Alfred C., ÒThe Xpress Transfer Protocol (XTP) - A Tutorial.Ó ACM
Computer Communication Review V.
20, N.5 (Oct. 1990), pp. 67-80.
[Sc82a] Schwartz, R.L. and
Melliar-Smith, P.M., ÒFrom State Machines to Temporal Logic: Specification
Methods for Protocol Standards.Ó In Protocol Specification, Testing, and
Verification. North-Holland,
Sunshine, C., (Ed), pp. 3-19, 1982.
[Sc82b] Schwartz, Richard L. and
Melliar-Smith, P.M., ÒFrom State Machines to Temporal Logic: Specification
Methods for Protocol Standards.Ó In Protocol Specification, Testing, and
Verification. North-Holland,
Sunshine, C., (Ed), pp. 3-19, 1982.
[Sh63] Shannon, Claude E. and
Weaver, Warren, The Mathematical Theory of Communication, University of Illinois Press, Urbana, IL (1963).
[Sh82] Shankar, A. Udaya and
Lam, Simon S., ÒOn Time-Dependent Communication Protocols and Their
Projections.Ó In Protocol Specification, Testing, and Verification. North-Holland, Sunshine, C., (Ed), pp. 215-233,
1982.
[Sh85] Shankar, A. Udaya and
Lam, Simon S., ÒSpecification and Verification of Time-Dependent Communication
Protocols.Ó In Protocol Specification, Testing, and Verification. North-Holland, Yemeni, Y., Strom, R., and Yemeni,
S., (Eds), pp. 215-226, 1985.
[Sh88] Shimony, Abner, ÒThe
Reality of the Quantum World.Ó Scientific American (Jan. 1988), pp. 46-53.
[Si82] Simon, Gerald A.
and Kaufman, David J., ÒAn Extended Finite State Machine Approach to Protocol
Specification.Ó In Protocol Specification, Testing, and Verification. North-Holland, Sunshine, C., (Ed), pp. 113-133,
1982.
[Si89] Simpson, J.A. and
Weiner, E.S.C., (Eds), The Oxford English Dictionary, Clarendon Press, Oxford, Vol. III, 2nd (1989).
[Si91] Sidhu, Deepinder,
Chung, Anthony, and Blumer, Thomas P., ÒExperience with Formal Methods in
Protocol Development.Ó ACM Computer Communication Review V. 21,
N.2 (Apr. 1991), pp. 81-101.
[Sm82] Smith, Alan Jay, ÒCache
Memories.Ó ACM Computing Surveys V.
14, N.3 (Sept. 1982), pp. 473-530.
[Sm84] Smith, James E., ÒDecoupled
Access/Execute Computer Architectures.Ó ACM Transactions on Computer Systems V. 2,
N.4 (Nov. 1984), pp. 289-308.
[Sm89] Smith, Jonathan M., Concurrent
Execution of Mutually Exclusive Alternatives, Ph.D. dissertation, Available as Computer Science Department
technical report CUCS-241-89, Columbia University, 1989.
[St87] Stallings,
William, Handbook of Computer-Communications Standards: The Open Systems
Interconnection (OSI) Model and OSI-Related Standards, MacMillan, Inc., Vol. 1 (1987).
[St88] Stankovic, John
A., ÒMisconceptions About Real-Time Computing: A Serious Problem for Next
Generation Systems.Ó IEEE Computer (Oct. 1988), pp. 10-19.
[St90] Stamos, James W.
and Gifford, David K., ÒImplementing Remote Evaluation.Ó IEEE Transactions
of Software Engineering V. 16, N.7 (Jul. 1990), pp. 710-722.
[Su88] Sun Microsystems, Inc.,
RPC: Remote Procedure Call Protocol Specification. Tech. Rept. RFC-1057, DARPA Network Working Group
Report, Jun., 1988.
[Su89] Sun Microsystems, Inc.,
NFS: Network File System Protocol Specification. Tech. Rept. RFC-1094, DARPA Network Working Group
Report, Mar., 1989.
[Ta88] Tanenbaum, Andrew S., Computer
Networks, Prentice-Hall, NJ, Second (1988).
[To87] Toueg, Sam and
Srinkanth, T.K., ÒOptimal Clock Synchronization.Ó Journal of the ACM V. 34,
N.3 (Jul. 1987), pp. 626-645.
[To89] Touch, Joseph D. and
Farber, David J., ÒMirage: A Model for Ultra-High-Speed Protocol Analysis and
Design.Ó In Protocols for High-Speed Networks, Rudin, Harry and Williamson, Robin, (Eds), IFIP,
North-Holland, Available as Univ. of Penn. Dept. of Computer and Information
Science Tech. Report MS-CIS-89-79 / DSL-1, 1989, pp. 115-134.
[To90a] Touch, Joseph D., Mirage: A Model
for Latency in Communication.
Tech. Rept. MS-CIS-90-74 / DSL-3, Dept. of Computer and Information Science,
University of Pennsylvania, (dissertation proposal), Oct., 1990.
[To90b] Tokoro, Mario, Computational Field
Model: Toward a New Computing Model / Methodology for Open Distributed
Environment. Tech. Rept.
SCSL-TR-90-006, Sony Computer Science Laboratory, Inc., Tokyo, Japan, Jun.,
1990.
[To91a] Touch, Joseph D. and Farber, David
J., Mirage: An Introduction. Feb.
1991, (submitted to ACM Computer Communication Review).
[To91b] Touch, Joseph D. and Farber, David
J., An Active Instruction Decoding Processor-Memory Interface. Sept. 1991, Patent applied for, Univ. of
Pennsylvania.
[Ve86] Venkatraman, R.C. and
Piatowski, Thomas F., ÒA Formal Comparison of Formal Protocol Specification
Techniques.Ó In Protocol Specification, Testing, and Verification. North-Holland, Diaz, M., (Ed), pp. 401-420, 1986.
[Wa72] Watson, W.J., ÒThe TI ASC: A
Highly Modular and Flexible Super Computer Architecture.Ó In AFIPS Fall
Joint Computer Conference, AFIPS,
AFIPS Press, Montvale, NJ, Dec. 1972, pp. 221-228.
[Wa81] Watson, Richard W.,
ÒTimer-Based Mechanisms in Reliable Transport Protocol Connection Management.Ó Computer
Networks, N.5 (1981), pp. 47-56, Pub.
by North-Holland.
[Wa89] Watson, Richard W., ÒThe
Delta-t Transport Protocol: Features and Experience.Ó In Protocols for
High-Speed Networks. Elsevier Science
(North-Holland), Rudin, H. and Williamson, R., (Eds), pp. 3-17, 1989.
[Wa90] The SPEC Benchmark Report, Waterside Associates, Freemont, CA, Jan. 1990.
[Wa91] Wall, David W., ÒLimits of
Instruction-Level Parallelism.Ó In ASPLOS-IV, ACM, Apr. 1991, pp. 176-188.
[Wi48] Wiener, Norbert, Cybernetics:
or Control and Communication in the Animal and the Machine, MIT Press, Cambridge, MA (1948).
[Wo90] Woodside, C.M., Ravinadran,
K., and Franks, R.G., ÒThe Protocol Bypass Concept for High Speed OSI Data
Transfer.Ó In Participant's Proceedings, International Workshop on Protocols
for High-Speed Networks, IFIP WG
6.1/WG 6.4, Palo Alto, CA, Nov. 1990.
[Ye87] Yeh, Y.S., Hluchyj,
M.G., and Acampora, A.S., ÒThe Knockout Switch: A Simple, Modular Architecture
for High-Performance Packet Switching.Ó IEEE Journal on Selected Areas of
Communications V. SAC-5, N.8 (Oct. 1987), pp. 1274-1283.
[Zh89] Zhang, Lixia, A New
Architecture for Packet Switching Network Protocols, Ph.D. dissertation, Massachusetts Institute of
Technology, Cambridge, MA, Jul. 1989.
[Zh90] Zhang, Lixia,
ÒVirtualClock: A New Traffic Control Algorithm for Packet Switching Networks.Ó
In Communications Architectures and Protocols, ACM Sigcomm, ACM Press, Also Computer Communication
Review, V. 20, N. 4, Sept. 1990, pp. 19-29.