################################################ # # # ## ## ###### ####### ## ## ## ## ## # # ## ## ## ## ## ### ## ## ## ## # # ## ## ## ## #### ## ## ## ## # # ## ## ###### ###### ## ## ## ## ### # # ## ## ## ## ## #### ## ## ## # # ## ## ## ## ## ## ### ## ## ## # # ####### ###### ####### ## ## ## ## ## # # # ################################################ 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 (A version of this paper appears in the Proceedings of the 1993 USENIX Symposium on Mobile and Location-Independent Computing. The reader is referred to the proceedings for figures not contained in this text-only version of the paper.) Local Area Mobile Computing on Stock Hardware and Mostly Stock Software Terri Watson and Brian N. Bershad School of Computer Science Carnegie Mellon University 5000 Forbes Avenue Pittsburgh, PA 15213 Abstract In the Fall of 1992, the graduate Operating Systems class at Carnegie Mellon University implemented the necessary components to provide applications with a programmable interface to a mobile palmtop computer. The goal of the project was to expose project members to the area of mobile computing through ``shock immersion.'' Over the course of two months, students designed and implemented the infrastructure for a simple mobile computing environment for low-end palmtop machines. This programming environment was used to develop a suite of mobile applications such as a mailer, graphical locator map, the game tetris, and a scheme interpreter that allowed functions to be remotely executed on the palmtop. In this paper, we describe the results of the course project and the lessons learned. 1 Introduction This paper describes a local area mobile computing system that was built by the students in a graduate operating systems course. The goal of the project was to address many of the issues that arise when dealing with mobility of low-end palmtop computers (really, simple user interface devices) in the context of a single insulated environment (a building). In meeting this goal within the time frame of a single semester course, we used available hardware and software, and well-understood systems building techniques. This approach allowed us to concentrate on the issues of communication, routing, and ________________________________ ()This research was sponsored in part by The Defense Advanced Research Projects Agency, Information Science and Technology Office, under the title ``Research on Parallel Computing'', ARPA Order No. 7330, issued by DARPA/CMO under Contract MDA972-90-C-0035, by the Xerox Corporation, and by Digital Equipment Corporation. Bershad was partially supported by a National Science Foundation Presidential Young Investigator Award. Watson was partially supported by a National Science Foundation Graduate Fellowship. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of DARPA, XEROX, DEC, the NSF, or the U.S. government. 1 interface design, while leveraging off of equipment already on our desks, or available inexpensively at a local store. The BNU system is the result of the course project. BNU builds on an existing Unix network infrastructure to support small scale mobile computing for inexpensive, physically compact devices, such as palmtops, or ``wimps'' (wireless interconnected mobile processors). BNU supports wimp mobility through the use of proxy processes that run on workstations in the local area network. Each wimp has a proxy representative that presents a fixed location to applications. An RPC system provides reliable, sequenced communication between wimps, which are carried, applications, which are run on workstations, and proxies, which bridge the gap between the mobile and non-mobile world. Messages are automatically forwarded through dynamic adjustment of route information as wimps relocate. A nameserver acts as an initial contact point for location information during application bootstrapping. In this paper we describe the BNU system, and a set of mobile applications that demonstrate both the power and limitations of our prototype. The rest of this paper is organized as follows. In Section 2 we cover the mobile computing model supported and system structure. In Section 3 we describe sample applications. In Section 4 we summarize some lessons learned from the project. In Section 5 we discuss related work. Finally, in Section 6 we present some conclusions. 2 BNU structure Figure 1 illustrates the main components of the BNU system. Wimps are mobile user interface devices with capabilities for limited computation. Proxies serve as the wimps' presence in the LAN, concealing from both wimps and applications many of the complicating aspects of mobility. All application communication with a wimp is handled though that wimp's proxy. Routers are processes running on the machines to which wimps become directly connected. They ferry the packets from the mobile network (in our case, a low-bandwidth infrared link, or a tethered serial line), into the LAN. Applications are the end service providers. They run on workstations and communicate with wimps through proxies. BNU applications execute on workstations in the LAN, which are connected via a slow link to a mobile user interface device. The wimps are capable of local processing; applications make use of this by extending the wimp's RPC interface with additional functions that can be downloaded dynamically. In the rest of this section we discuss issues relating to communication, the wimps themselves, proxies and routers. 2.1 RPC and naming Applications, proxies, wimps, and routers communicate through BNU RPCs. An RPC interface is exported by registration with the nameserver and imported via nameserver lookup. We built a simple interface definition language and 2 Figure 1: BNU components. Wimps connect into the LAN by way of router processes that forward messages to the wimp's proxy. Proxies are the intermediaries between wimps and applications, hiding the complications of wimp mobility from both. implemented an interface generator for BNU called BIG(1). BIG allows the use of arrays, structs, and typedefs in the interface description. Parameters are tagged as in, out, or inout and procedures as with_reply (synchronous) or no_reply (asynchronous). Bandwidth and latency limitations of the communication link to the wimp encourage the use of function shipping. This allows applications to dynamically extend the wimp RPC interface with custom procedures. Multiple operations can be accomplished with one RPC and local processing on the wimp, requiring less bandwidth. Another motivation for providing an extensible RPC interface is the increased likelihood of short periods of disconnection, or infrequent high latency RPCs. The latter may occur when moving from one communications cell to another, as processes in the LAN (proxy, routers) become aware of the location change and update their routing information. The ability to load certain routines and data on the wimp can mask these glitches which play havoc with time-crucial applications (e.g. games) or just generally annoy the user. To permit such extensions in BNU, we modified a scheme interpreter to allow the execution of an eval call in the scope of a remote scheme interpreter executing on the wimp. An interpreter on the application/workstation side includes a remote eval function that sends an expression to an interpreter on the wimp where the actual evaluation is performed. This permits the definition and subsequent execution of new functions on the remote side, effectively extending the exported RPC interface of the wimp. ________________________________ (1)The name (and syntax) derives from Mach's stub generator MIG, although BIG supports only the transfer of simple types. 3 Each RPC is directed towards a named endpoint in the BNU environment. Specifically a ``BNUid'' must be provided as the first argument to an RPC. BNUids are similar both to internet socket addresses, in that they identify an endpoint of communication, and to ports in a system like Mach [Draves90] in that they are location transparent and can therefore name mobile endpoints. A name in the BNU namespace is composed of two parts: a domain and an instance. Each user has their own domain, much like a UNIX userid, and entities that exist on behalf of that user are instances within that domain. The wimp and proxy are well-known instances within a domain. Other instances are assigned dynamically to applications as they are started. The well-known instances, like well-known TCP ports, allow new applications to determine the BNUids of essential entities in the BNU environment such as the nameserver and proxy without having to access a nameserver. A nameserver provides service for all domains, so it has both a well-known instance and domain. The nameserver maintains mappings from key values to data, most commonly BNUids to native addresses. A native address is an endpoint address outside of the BNU naming scheme that can be used by the underlying transport protocol. For example, a native address in the LAN is an internet socket address. 2.2 The wimp Wimps are the mobile user interface devices that tie users into the BNU computing environment. Our wimps are HP 95LX palmtops running MS-DOS. They each have 1MB of RAM, a 300--19,200 baud serial line, a 2400 baud short-range infrared (IR) link, one PCMCIA 1.0 slot, and a 16x40 character display with graphics mode. The growing demand for small computers with PC-like capabilities means such devices are becoming increasingly inexpensive, on the order of a few hundred dollars. The wimp software for our prototype system exports a simple text and graphics RPC interface to applications, capable of drawing strings, simple graphics functions (pixels, lines, cursor motion) and handling keyboard input. Much of the screen oriented code was derived from a freely available graphics interface module for the HP. The communications support provides reliable, sequenced messages and RPC handling. The wimps can be connected through to the LAN via either a 9600 baud serial link when in ``tethered'' mode, or a 2400 baud link when wireless. Because the HP95's builtin IR link is limited to a range of about 8 inches, we built our own unit that could transmit data up to about 8 feet. Since the IR units were built in parallel with the rest of the system, most of the time wimps ran in tethered mode. Multiple applications may attempt to control the wimp at any one time, so BNU relies on a ``focus'' mechanism, similar to that used in the X Window System [Scheifler*86]. Applications request focus and are notified by RPC when the focus is acquired or lost. Only the application with focus can perform I/O operations on the wimp. The proxy records which application has current focus and simply blocks any request from those that don't. 4 2.3 The proxy A proxy process represents the wimp in the network at a fixed native address. When an application is started, it contacts the nameserver to learn the route (native address) to the proxy for its domain. The nameserver will start a proxy if one does not currently exist for the calling user. The proxy in turn contacts the nameserver to determine the wimp's location. At this point, a bootstrapping application (such as a terminal and shell) is started, from which the user can invoke other applications. Each application contacts the nameserver at its startup to locate the proxy for the user on whose behalf the application is running. Applications and their wimp direct all communication with each other through the wimp's proxy. By interfacing through the proxy, application processes are unaware of changes in wimp location and do not need updates to local routing information. The RPC interface exported by the proxy is the same interface as presented by the wimp, so an RPC to the proxy typically results in an identical RPC to the wimp. Optimizations within the proxy enable it to hide latency from the applications and better utilize limited bandwidth. Non-blocking RPCs from applications are queued by the proxy and immediately acknowledged. This asynchrony with respect to the application allows delivery of RPCs to the wimp to proceed in parallel with application processing, potentially reducing idle link time caused by waiting for the application to generate the next RPC. Where interface semantics allow, the queueing permits multiple RPCs to the proxy to be collapsed to a single, equivalent RPC to the wimp (for example, cursor motion followed by a text write). 2.4 Routing Physical mobility causes the location of the wimp's connection into the LAN to change, requiring that messages be re-routed. The RPC system is responsible for converting BNUids (used at the application level) to native addresses that can be used for transport and routing. Each entity (applications, the proxy, a wimp) maintains a local hintcache that maps BNUids into native addresses. The messaging layer, when delivering a message to a particular BNUid, inspects its hintcache for a match. If no match is found, the messaging layer queries the nameserver and the result is cached. The local route cache is updated whenever a message is received, always providing the messaging layer with enough routing context to deliver a reply message. Routers, which are processes running on machines to which wimps become electrically connected, periodically broadcast ``You Are Here'' packets which are received by any in-range wimps. If a wimp learns that it has moved (where it is now is different from where it was a few seconds ago), it sends a location status message to its proxy. In this way, a proxy is as aware of its wimp's location as is the wimp. 5 2.5 Some problems There are some clear, obvious problems with the system structure described in this section. For example, the current system assumes that a user is only using one wimp at a time, ensuring that the wimps are no more ubiquitous than the people who use them. Further partitioning the domain component of the BNUid namespace would address this problem. Another problem is that the current nameserver is centralized and non-replicated, making it an obvious bottleneck and single point of failure. Nameservers, though, are relatively easy to replicate using any of a number of techniques and systems [Birman85]. Since our environment did not have an abundance of IR units (we built 2), the system was largely developed and used in tethered mode, so some situations, such as ``what happens when somebody is bouncing between IR cells'' are not adequately addressed in the implementation. Lastly, there is no real security in the system. Messages are sent in the clear, and a message asserting a fact followed by a request (such as ``my name is bershad; show me my mail'') is taken at face value. 3 Applications We developed about a dozen mobile applications for BNU. Some of these applications were: o Zephyr. This application is a notice transport and delivery (paging) system developed by MIT-Project Athena [DellaFera*88]. Zephyr allows the delivery of a text message to a set of users in the system. Minimal changes were required to adapt the service to the BNU environment. A simple process in the workstation environment posed as the mobile user. When it received messages through the Zephyr notification service, it forwarded them on to the wimp using BNU RPC through the proxy. o Graphical Locator. This application uses location information to respond to queries for directions within a specific locale. An animated figure on the display describes a path from the current location to the destination. o BNUterm. This application is a terminal emulator that, in some sense provides the most flexibility, but it is not well suited to the wimp. BNUterm, derived from a VT-100 emulator, uses a character-at-a-time interface which performs poorly over the high-latency link. Furthermore, the wimp's small screen and awkward keyboard make its usage as a terminal quite unpleasant. o Tetris. This is an arcade-style game in which the player manipulates falling blocks of various shapes. This application worked well because of the extensible RPC paradigm. Tetris defined additional RPC functions to do more complex operations on the wimp (e.g. display updates) and so reduced bandwidth requirements. BNU also includes a simulator that emulates the wimp in an X11 environment. The simulator exports the same RPC interface as do the wimps, which allowed application development to proceed in parallel with infrastructure, and 6 facilitated early interface testing and design refinements. That all interaction with wimps was through a location transparent RPC service meant that the same application could communicate with either the simulator or the actual wimp. 4 Some lessons learned Building the BNU system allowed us to experiment with issues such as as routing, location transparency, and the limiting characteristics of the wimp interface. The following are some of the lessons learned from BNU: o Existing system software (e.g. MS-DOS, UNIX, threads, sockets) provides service to allow the construction of an experimental mobile palmtop system. In particular MS-DOS is small, cheap (i.e. available on inexpensive hardware), and allows use of existing software packages, such as the scheme interpreter and the display code for the HP. o The portability of devices such as the HP palmtop creates a new application paradigm. Unfortunately, the constraints on the physical size of these devices leads to awkward user interfaces that render many common Unix applications unusable in practice. For instance, an extended editing session on the palmtop can be particularly unpleasant. While UNIX was easily adapted to the last revolution in interface technology, namely windowing, it is clear that its typical terminal-style user interface is ill-suited to the next revolution, namely small-screen mobile machines. o Proxies work well to insulate applications from wimp location and temporary disconnection during relocation. o RPC with transparent routing also insulates applications from the details of wimp location. o Extensible RPC yields better application performance on low bandwidth communication links by increasing the amount of work done per RPC. For example, the Tetris game with downloaded functions ran in real time, but BNUterm, which causes an RPC per character, was painful to use. o Function shipping to support extensible RPC increases performance, but at the cost of greater wimp state, and therefore more complicated recovery mechanisms. Currently, applications are required to support state reloading if they choose to take advantage of extensible RPC. o Asynchronous invocation through the proxy facilitates better utilization of link bandwidth by allowing multiple application requests to be queued and delivered in parallel with application processing. This queueing allows compression of multiple RPCs and potentially reduces idle link time. 7 5 Related work Our use and management of wimps in BNU parallels that of the ParcTabs in the ubiquitous computing project at Xerox PARC [Weiser91, Weiser93]. Both systems use the mobile units primarily as user interface devices, and require applications executing in the LAN to communicate with the device through a proxy (or agent) [Adams*93]. The projects differ in one main dimension: BNU was built using an off-the-shelf palmtop running MS-DOS, an industry standard operating system. This allowed us to inexpensively acquire the hardware, and to leverage off of existing software, such as I/O drivers and a scheme interpreter. In contrast, Xerox's ParcTabs are custom-built, expensive, and require a special-purpose operating system. The main advantage of the ParcTabs, however, is that they are extremely well-integrated, offering a relatively high-bandwidth IR link (19.2Kb) with low power requirements. With time, though, we expect comparable communications hardware to become inexpensively available for commodity palmtops. The graphical locator application provides navigation functionality similar to the VuMan [Akella*92, Smailagic*93] and Navigator [Siewiorek*93] wearable computer systems. The VuMan systems allow a user to page through maps and blueprints to retrieve context-sensitive information using a ``heads-up'' display. The Navigator system follows on this by incorporating telecommunications, speech recognition, and position sensing. 6 Conclusions The BNU system and applications exposed us to practical concerns in mobile palmtop computing and allowed us to experiment with some simple solutions. Our use of stock hardware and ``mostly'' stock software demonstrates that there exists already a large amount of distributed systems technology (and artifact) that can be leveraged against the problems introduced by this class of mobile computing. Acknowledgments The BNU project resulted from the combined efforts of the students in the Fall 1992 CS 712 (graduate Operating Systems) course. While the authors did most of the worrying, the following students did most of the real work: Terry Allen, Shumeet Baluja, Claudson Bornstein, Yirng-An Chen, Scott Crowder, Eugene Fink, Geoff Gordon, Tammy Green, Karen Haigh, Todd Kaufmann, Jennifer Kay, James Landay, Gerald (Rob) Malan, Will Marrero, Paul Olbrich, Robert Olszewski, Manish Pandey, Henry Rowley, Stefan Savage, Motonori Shindou, Nick Thompson, Stephen Weeks, Bob Wheeler, Hao-Chi Wong, and Masanobu Yuhara. References [Adams*93] Adams, N., Gold, R., Schilit, B., Tso, M. and Want, R. The ParcTab Mobile Computing System. Submitted for publication. 8 [Akella*92] Akella, J., Dutoit, A. and Siewiorek, D. P. Concurrent Engineering: A Prototyping Case Study. In Proceedings of the 3rd IEEE International Workshop on Rapid System Prototyping, June 1992. [Birman85] Birman, K. P. Replication and Fault-Tolerance in the ISIS System. In Proceedings of the 10th ACM Symposium on Operating System Principles, pp. 79--86, December 1985. [DellaFera*88] DellaFera, C., Eichin, M., French, R., Jedlinsky, D., Kohl, J, and Sommerfeld, W. The ZEPHYR notification service. In Proceedings of the Winter 1988 USENIX Conference., pp. 213--19, February 1988. [Draves90] Draves, Richard P. A Revised IPC Interface. In Proceedings of the First Mach USENIX Workshop, pp. 101--121, October 1990. [Scheifler*86] Scheifler, R. W. and Gettys, J. The X Window System. ACM Transactions on Graphics, 5(2):79--109, April 1986. [Siewiorek*93] Siewiorek, D. P., Smailagic, A., Lee, J. and Adl-Tabatabai, A. An Interdisciplinary Concurrent Design Methodology as Applied to The Navigator Wearable Computer System. EDRC Technical Report, Carnegie Mellon University, May 1993. [Smailagic*93] Smailagic, A. and Siewiorek, D. P. The Design and Implementation of the VuMan Wearable Computer EDRC Technical Report, Carnegie Mellon University, March 1993. [Weiser91] Weiser, M. The Computer for the Twenty-First Century. Scientific American, 265(3):94--104, September 1991. [Weiser93] Weiser, M. Some Computer Science Issues in Ubiquitous Computing. To appear, Communications of the ACM, July 1993. 9