Throughput Analysis for Persistent CSMA Systems

The channel throughput for a finite number of packet broadcasting users is analyzed for random access protocols, including slotted persistent carrier sense multiple access (CSMA) with and without collision detection and unslotted persistent CSMA with and without collision detection. We consider bothp- and 1-persistent CSMA. Our results can be extended to infinite population cases (by taking the proper limit), where they agree with the known throughput expressions when available.     

Mobile wireless network system simulation

This paper describes an advanced simulation environment which is used to examine, validate, and predict the performance of mobile wireless network systems. This simulation environment overcomes many of the limitations found with analytical models, experimentation, and other commercial network simulators available on the market today. We identify a set of components which make up mobile wireless systems and describe a set of flexible modules which can be used to model the various components and their integration. These models are developed using the Maisie simulation language. By modeling the various components and their integration, this simulation environment is able to accurately predict the performance bottlenecks of a multimedia wireless network system being developed at UCLA, determine the trade-off point between the various bottlenecks, and provide performance measurements and validation of algorithms which are not possible through experimentation and too complex for analysis.This work was supported in part by the Advanced Research Projects Agency, ARPA/CSTO, under Contract J-FBI-93-112 Computer Aided Design of High Performance Wireless Networked Systems, and by ARPA/CSTO under Contract DABT-63-94-C-0080 TransparentVirtual Mobile Environment.This paper was in part presented at the ACM Mobile Computing and Networking Conference (Mobicom '95), Berkeley, California, 14–15 November 1995.     

Nomadic computing and smart spaces

Currently, most users think of their computers as associated with their desktop appliances or with a server located in a dungeon in some mysterious basement. However, many of those same users can be considered nomads, in that they carry computers and communication devices with them in their travels between office, home, airport, hotel, automobile, and so on. Access to the Internet is necessary not only from one's “home base”, but also while in transit and after reaching one's destination. A number of capabilities must be put in place to support this new paradigm of nomadicity. Among these, we can include independence of location, motion, platform, and, with widespread presence, of access to remote files, systems, and services. Essentially, one seeks to provide the illusion of connectivity even when the nomad is disconnected and to provide seamless access to Internet services wherever the nomad travels. To achieve this, not only must the infrastructure be enhanced to provide these capabilities, but applications must become nomadically enabled as well. These ideas form the essence of the major shift to nomadic computing. But nomadic computing is merely the first step of the vision foreseen by the author. The next step will take us out of the netherworld of cyberspace and into the physical world of smart spaces. Environments will come alive with embedded technology, so that no longer will we see Internet services as coming to us from the screen on a computer, but rather those services will be embedded in the environment     

Nomadic computing (keynote address)

Nomadic computing is a phenomenon in computing and communications that is spreading rapidly. At this stage of its technology, the key problems and the basic understanding of its underlying principles are only beginning to be identified. Analysis and design tools are needed to assist in its development. In this paper, we discuss the nature of the tools and what one might look for in the way of applying some of them. We then pose some of the essential issues of nomadic computing and communications. This revised version was published online in June 2006 with corrections to the Cover Date.     

On a Self-Adjusting Capability of Random Access Networks

We consider a distributed communication network with many terminals which are distributed in space and wish to communicate with each other using a common radio channel. Choosing the transmission range in such a network involves the following tradeoff: a long range enables messages to reach their destinations in a few hops, but increases the amount of traffic competing for the channel at every point. We give a simple model for the per-hop delay in random access networks, analyze this tradeoff, and give the optimal transmission range. When choosing this optimal range, as a function of specified traffic and delay parameters, networks demonstrate an important self-adjusting capability. This capability to adjust to traffic makes heavily loaded networks far better than centralized systems (in which all messages must reach one common destination). Dividing a terminal population into power groups can improve any random access system, especially when the traffic is split between groups in an appropriate way, which we demonstrate. But since networks are hurt by destructive interference less than centralized systems, it is harder to improve them. Using power groups can significantly improve centralized systems, but will lead to a smaller relative improvement in networks. Decomposing the system into a hierarchy of ALOHA levels, with only a small population contending at the top level, can improve centralized systems but does not improve networks.     

The Benevolent Bandit Laboratory: a testbed for distributedalgorithms

The design, implementation, and use of a distributed processing environment on a network of IBM PCs running DOS is described. Temporarily unused PCs can be accessed by other users on the network to perform distributed computations. An owner of a PC need not be aware that the machine is being used during idle times; the machine is immediately returned when the owner begins to work again. Some degree of computation resiliency is provided in this unreliable environment; if a PC is part of a distributed algorithm and is reclaimed by its owner, the system finds a replacement node (if possible), resends the affected code to the processor, and restarts it. Thus, a distributed computation is able to proceed despite a set of transient processors. System performance, distributed applications, and fault tolerance are discussed. Performance improvements are demonstrated by applications like parallel merge sort and a distributed search solution to the eight puzzle     

Collecting unused processing capacity: an analysis of transientdistributed systems

It is suggested that if the large numbers of idle computers and workstations in distributed systems could be used then considerable computing power could be harnessed at low cost. Such systems are analyzed using Brownian motion with drift to model the execution of a program distributed over the idle computers in a network of idle and busy processors. The ways in which the use of these transient processors affects a program's execution time is determined. The probability density of a program's finishing time on both single and multiple transient processors is found. These results are explored for qualitative insight. Some approximations for the finishing time probability density are suggested     

Packet Switching in a Multiaccess Broadcast Channel: Dynamic Control Procedures

In a companion paper [1], the rationale for multiaccess broadcast packet communication using satellite and ground radio channels has been discussed. Analytic tools for the performance evaluation and design of uncontrolled slotted ALOHA systems have been presented. In this paper, a Markovian decision model is formulated for the dynamic control of unstable slotted ALOHA systems and optimum decision rules are found. Numerical results on the performance of controlled channels are shown for three specific dynamic channel control procedures. Several practical control schemes are also proposed and their performance compared through simulation. These dynamic control procedures have been found to be not only capable of preventing channel saturation for unstable channels but also capable of achieving a throughput-delay channel performance close to the theoretical optimum.