################################################ # # # ## ## ###### ####### ## ## ## ## ## # # ## ## ## ## ## ### ## ## ## ## # # ## ## ## ## #### ## ## ## ## # # ## ## ###### ###### ## ## ## ## ### # # ## ## ## ## ## #### ## ## ## # # ## ## ## ## ## ## ### ## ## ## # # ####### ###### ####### ## ## ## ## ## # # # ################################################ The following paper was originally published in the Proceedings of the USENIX Mobile & Location-Independent Computing Symposium Cambridge, Massachusetts, August 2-3, 1993 For more information about USENIX Association contact: 1. Phone: 510 528-8649 2. FAX: 510 548-5738 3. Email: office@usenix.org 4. WWW URL: https://www.usenix.org Agent-Mediated Message Passing for Constrained Environments Andrew Athan and Dan Duchamp Computer Science Department Columbia University New York, NY 10027 {athan,djd}@cs.columbia.edu 1 Introduction We outline desirable features for a general-purpose inter-process communic* *ation mechanism suited to the needs of mobile computers operating under bandwidth and power con* *straints. 1.1 World View Since mobile computing is presently still in its infancy, we first discuss* * our "world view" and how it leads to the problems that our design seeks to solve. A convenient overs* *implification of the design space for mobile computing is the following: o There is a spectrum of mobile devices, anchored at the two ends by the not* *ions of "terminal" and "computer." A "terminal" is a device with limited ability for computation or storage. * *A terminal provides a user interface only, and is animated entirely by signals from some "infr* *astructure" computer. A computer, on the hand, possesses some degree of compute and storage capa* *city, and is capable of standalone operation. o There are two sorts of communication networks, public and private. The ess* *ential difference is that public networks charge per-use and therefore communication is a recur* *ring cost, whereas in private networks the cost is largely front-loaded to a one-time install* *ation, with limited ongoing cost paid for network maintenance, and typically none for communic* *ation. Although the public/private distinction need not imply anything about avai* *lable bandwidth, in practice public networks _ both wired and wireless _ are likely to offe* *r very much less bandwidth per user than private networks during the foreseeable future. Fu* *rthermore, in many cases the "last link" to the client computers can be expected to be wirele* *ss. In these cases, bandwidth will be limited whether the network is public or private. The re* *sulting architecture is a highly capable infrastructure of high speed networks and servers, fri* *nged by a much lower speed and more expensive last link to the mobile computer. Because of their complete dependence on access to bandwidth for communication w* *ith the infrastruc- ture, terminal-based system designs seem ill suited for operation in low-bandwi* *dth public-network environments. Accordingly, because of their wider applicability, we focus our a* *ttention on computer- based designs. 2 Design Given that mobile devices will commonly operate as computers, there is nee* *d for application and system software running on a mobile computer permitting the exchange of dat* *a between mobile computers and servers in the infrastructure. Constraints on the mobile computer* *'s communication bandwidth and power consumption affect how best to perform this communication. * * We contend that current binding and message delivery mechanisms are not ideal for these ci* *rcumstances. 2.1 Failings of Current Mechanisms 2.1.1 Overuse of Bandwidth If the "last link" to the mobile computer is a wireless one, then it is de* *sirable to limit the use of that link's bandwidth. One approach is to recognize that not all data re* *turned out of the infrastructure is equally valuable. Present transport mechanisms view intra-mes* *sage data as a one- dimensional stream, and flow control governs only which prefix of the stream is* * sent. Likewise, separate messages (inter-message data) are viewed as equally valuable, and cann* *ot be filtered except once received by the destination. The architecture discussed above _ a high spe* *ed infrastructure fringed by a lower speed and more expensive last link _ motivates the addition * *of a policy module at the edge of the infrastructure that can reorder, suppress, or otherwise proc* *ess data flowing out of the infrastructure to mobile computers. 2.1.2 Client-Server Model With current distributed binding techniques, a server registers a (string,* * port) tuple with a name server; the client later looks up the tuple and remembers the port value, * *thus binding to the server. Except for some replicated services or administratively pre-arranged "w* *ell known ports," the lifetime of a binding is typically equal to the lifetime of the particular serv* *er process that registered the tuple. Another aspect of this model is that a server must be running before a cli* *ent can get service. As a result, server daemons tend to proliferate, one for each service. In a workst* *ation/office environment, such proliferation is not unreasonable: the workstation is probably always turn* *ed on and connected to the network; furthermore, the workstation probably has virtual memory and pl* *enty of backing store, meaning that accretion of a large number of daemons that seldom do anyth* *ing has little cost. When communicating with a mobile computer, the situation may be very diff* *erent. It may be infeasible _ for power reasons _ to expect the mobile computer to be continu* *ously running all the various daemons that might be addressed by incoming messages: the mobil* *e computer may be turned off, or it may not have virtual memory or may be limited in backing s* *tore; either way, accretion of many long-lived server daemons may be impossible or undesirable. It is preferable to automatically start applications on demand. Simple exa* *mples of this ca- pability exist: the UNIX inetd program, for example. It should also be possib* *le to pause and automatically resume applications as well as start them. During the time that a* *n application at one endpoint of a transport connection is paused, the connection should not break i* *f the other endpoint sends data. 2.2 Overview We propose an inter-process communication mechanism that addresses the sho* *rtcomings noted above. Specifically, 1.A message is considered not as a sequence of typed objects (as in Mach [1]* *, for example), but as a hierarchy of typed objects. Roughly speaking, "important" or immediat* *e-delivery data belongs near the top of the hierarchy, while less important or deferrable * *data belongs near the bottom. 2.An undeliverable message can be stored for later delivery. Storage include* *s the possibility of filtering and/or reordering message delivery, to place important data ahea* *d of less important data. 2 3.Delivery of a message destined to a server program that is not running can* * cause the destination program to be automatically started or resumed. Each of these features is governed by "hooks" made available to both source and* * destination. These are policy hooks that help customize message delivery. Policy issues include ho* *w to perform message filtering and whether/when to automatically start a program on the mobile compu* *ter. This is the much-discussed idea of an "agent" that continuously operates within the infrast* *ructure on behalf of a mobile user or computer, and building such an agent is the goal of our work. The ability to start the destination process on demand and/or to store a m* *essage for later delivery makes our model of binding more general than the standard client-serve* *r model. In the client-server model, both source and destination must be executing simultaneous* *ly. The binding becomes useless when either process shuts down. In contrast, our model includes* * Email-like deferred communication, which is intended to help cases wherein power or bandwidth limit* *ations might render communication with a mobile computer sometimes impossible and other times undes* *irable. The following sections sketch our ideas in somewhat greater depth. 2.3 Hierarchical Data Organizing data into a hierarchy is a commonly proposed technique for the * *coding and framing of images and video for network transmission. In this formulation of the idea, * *data at the top of the hierarchy comprises a moderate-resolution basis of the image(s) while data * *at the bottom of the hierarchy represents additional information that adds possibly-nonessential* * sharpness to the image(s). By transmitting more or less of the hierarchy, image quality can be * *varied smoothly according to available bandwidth. Other domains in which it can be useful to or* *ganize message data into a hierarchy include: o Email, which can be divided into portions such as: important header field* *s, unimportant header fields, message summary, new versus quoted text, checksum, and anno* *tations and/or large embedded objects (bitmaps, sound) that might be considered optional. o Ordinary documents, which often divide naturally into a hierarchy. Hyperte* *xt documents are inherently composed of a collection of clearly separate units. o File data, especially that requested by an interactive editor. In this cas* *e, it is important to deliver the first page promptly, but remaining pages can often be delayed. In each case, the goal of the hierarchy is to distinguish vital data from incid* *ental data. In our formulation, the "importance hierarchy" is specified by the source * *and made visible to the destination, so the destination can choose which parts of a message to igno* *re, which parts to receive, and when to receive. Piece-by-piece receipt of messages already organized into a hierarchy is a* * conceptually simple extension to primitives for typed messages. For example, Mach's message format * *is a fixed-size header followed by a variable number of descriptor/data pairs; each (fixed-size) descr* *iptor defines the size and type of the data (either in-line or out-of-line) that follows. Mach's msg_r* *eceive() primitive receives an entire message into a pre-allocated buffer. A different message fo* *rmat similar to an expanded i-node is appropriate for hierarchical data. The new message format co* *ntains a fixed-size header, a small fixed-size area for descriptor/data pairs, and a fixed number o* *f conceptual "pointers" to the remainder of the message. Each such pointed-to segment contains further * *descriptor/data pairs. The new msg_receive_segment() primitive receives one segment as a time;* * the existing msg_receive() can still be used to receive the entire message. The descriptor f* *ormat is expanded to include an additional field that can describe the meaning of the data. This * *information can help guide the receiver as to which segments to receive next; Mach's descriptor curr* *ently carries only type information. 3 One of the trickiest issues in formulating hierarchical messages is defini* *ng the moment the kernel may consider a message as delivered. This atomic transition point is important * *for permitting the operating system to begin garbage collection and other actions that are depende* *nt on the message having been delivered. 2.4 Binding and Message Delivery The address of a communication endpoint on a mobile computer consists of t* *wo sub-addresses, one being the intended destination, and the other being the agent that lives in* * the infrastructure as a permanent representation of a mobile user or host. This two-part address w* *e call a composite address. The intended destination sub-address is statically assigned so that it can* * be long-lived. We presume that a program running on a mobile computer might be frequently restart* *ed and hence would receive different port numbers on each instantiation. Therefore, a port i* *s a poor address for the intended destination because frequent re-registration and re-binding would * *be necessary. The agent's sub-address is an ordinary Mach port. The endpoint address consists of both the long-lived sub-address and the a* *gent's port since one always needs the combination of the two in order to successfully reach either t* *he destination or, as a backup, its agent. This address format obscures the port of the destination on * *the mobile computer, since it is regarded as information possibly too short-lived to be of practical* * use. The composite address is presumed to be far more long-lived, because the agent presumably res* *tarts less often _ its very purpose is to be available as a proxy for the mobile computer. To learn a composite address, a process either has the address passed to i* *t (e.g., as the return address included as part of a request) or goes to a new type of name server tha* *t associates a string or other identifying pattern with the composite address. Messages sent from the mobile computer are addressed to an ordinary Mach p* *ort, and list the composite address as the return address. A message sent to the mobile computer * *is addressed to the agent's port sub-address embedded within the composite address; accordingly, me* *ssages traveling from the infrastructure to the mobile computer are passed through the agent, wh* *ere they can be delayed, suppressed, etc. Once such an "outbound" message passes the agent's policy tests and merits* * delivery, the agent must know an address on the mobile computer. The intended destination may be up* * and running, in which case the agent must discover the Mach port value for the destination; * *alternatively, the agent may need to start the appropriate program on the mobile computer. Accordi* *ngly, the mobile computer must run a Mach name server (which, by definition, has a well-known po* *rt value) that is augmented with an interface to the agent and the ability to fork servers on dem* *and. This name server stores the string-to-port mappings for the active programs on the mobile comput* *er; the binding is short-lived, as noted in the criticism above, but this short-lived binding is v* *isible to the agent only, and therefore is a limited inconvenience. Additionally, the agent maintains a d* *atabase listing the names and file locations of server executables.1 The agent uses this informatio* *n to direct the mobile computer's augmented name server to start a program on demand. In summary, besides the need for the agent itself, the mobile computer mus* *t run an augmented names server, and a new name service must be created to maintain associations b* *etween strings and composite addresses. 3 Related Work The ideas described in this paper are only a small step away from many dif* *ferent pieces of prior work. The notion of automatically starting the program that is a message's desti* *nation is present in _______________________________1 Much like nanny, Mach's server-server. 4 various "software toolbus" designs in the software engineering community. One t* *oolbus with this capability is Polylith [4]. Tadpole portable computers have for some time run a* * modified version of SunOS that can pause and resume the whole system. While this mechanism is too c* *oarse-grained for our needs, pausing the whole system is related to pausing a process, since * *process state is not self-contained - important state exists in kernel data structures. Structuring message data is an old idea. Many message-based operating sys* *tems provide a structured, typed message model; Mach is only one example. Typed, structured da* *ta is the basis for several standards, including the ASN.1 message syntax and ODA. In these cases, * *however, typing is added to structure in order to ease (or make possible) data interpretation by t* *he application. The notion of separating logical "delivery" from physical, on-demand deliv* *ery of data is the basis for copy-on-write and, at finer granularity, on-demand RPC parameter pass* *ing [3]. There are numerous naming/binding mechanisms for message-based systems. Tw* *o differing examples include Mach, in which an endpoint is named by a string and bound to a* * port, and Field [5], in which an endpoint is named by a printf-like pattern and binding is done* * by a central agent that matches messages sent with patterns registered earlier by interested desti* *nations. Mach contains the notion of a "backup port" [2]. The right to receive mes* *sages reverts to a "primary" port's backup port when the primary port is destroyed. This mechani* *sm is close to something we need, since it provides some capability for an agent to receive me* *ssages intended for a now-unreachable mobile computer. However, our approach requires a more long-las* *ting relationship between an endpoint on a mobile computer and the corresponding endpoint at the * *agent. In our setting, the current locus of delivery can ping-pong back and forth between the* * mobile computer and the agent. 4 Summary We have presented a case for the need for an inter-process communication m* *echanism that provides (1) a backup message delivery location where message storage and filte* *ring can be done, (2) the ability to receive data partially and on-demand, and (3) the ability to* * sense lack of a server and initiate its execution if warranted. We have sketched a simple design (for * *a Mach environment) that can implement these features. All these capabilities are motivated by the likelihood that mobile compute* *rs will be operating in bandwidth-limited and power-limited environments. These constraints raise th* *e cost of extraneous communication between the mobile computer and the infrastructure, and motivate * *mechanisms to distinguish between essential and non-essential communication. The likelihood * *that a user will opt to disconnect his computer from expensive public communication facilities m* *otivates deferred communication, which converts what would otherwise be a binding error into dela* *yed, elective message delivery. 5 References [1]M. Accetta et al. Mach: A New Kernel Foundation for UNIX Development. In Pr* *oc. Summer USENIX, USENIX, pages 93-112, July, 1986. [2]R. V. Baron et al. MACH Kernel Interface Manual. Unpublished. Available by * *anonymous ftp from mach.cs.cmu.edu:/mach3/doc/unpublished/sup/sup.doc [3]Y. J. Cycowicz, J. Micallef, and G. E. Kaiser. Demand-Driven Parameter-Pasi* *ng in Remote Procedure Call. Unpublished technical report. February 1987. [4]J. M. Purtilo and C. R. Hofmeister. Dynamic Reconfiguration of Distributed * *Programs. In Eleventh Intl. Conf. on Distributed Computing Systems, IEEE, pages 560-571,* * May 1991. [5]S. P. Reiss. Connecting Tools Using Message Passing in the Field Environmen* *t. IEEE Software, 7(4):57-66, July 1990. 5