This dissertation proposes a new approach to support wireless mobile internetworking on a large university campus or similar environment. Called Crosspoint, the approach combines wireless local-area network technology with high-speed switching technology. The combination provides a wireless communication system with sufficient aggregate bandwidth to handle massive, synchronized movements of mobile computers. Furthermore, the approach supports optimal routing to each mobile computer without requiring modification of the networking software on mobile computers, nonmobile computers, or routers in the existing Internet. This dissertation describes the design and implementation of Crosspoint. Through a prototype implementation, we have shown that the approach is feasible.

Weak connectivity, in the form of intermittent, low-bandwidth, or expensive networks is a fact of life in mobile computing. For the foreseeable future, access to cheap, high-performance, reliable networks, or strong connectivity will be limited to a few oases, such as work or home, in a vast desert of weak connectivity. The design of distributed file systems has traditionally been based on an assumption of strong connectivity. Yet, to provide ubiquitous data access, it is vital that distributed file systems make effective use of weak connectivity.

This dissertation describes the design, implementation, and evaluation of weakly connected operation in the Coda File System. The starting point of this work is disconnected operation, in which a file system client operates using data in its cache during server or network failures. Disconnected clients suffer from many limitations: updates are not visible to other clients, cache misses may impede progress, updates are at risk from client loss or damage, and the danger of update conflicts increases as disconnections are prolonged. Weak connectivity provides an opportunity to alleviate these limitations.

Coda's strategy for weakly connected operation is best characterized as application-transparent adaptation. The system bears full responsibility for coping with the demands of weak connectivity. This approach preserves upward compatibility by allowing applications to run unchanged. Coda provides several mechanisms for weakly connected operation motivated by actual experience. The foundation of adaptivity in this system is the communications layer, which derives and supplies information on network conditions to higher system layers. The rapid cache validation mechanism enables the system to recover quickly in intermittent environments. The trickle reintegration mechanism insulates the user from poor network performance by propagating updates to servers asynchronously. The cache miss handling mechanism alerts the user to potentially lengthy service times and provides opportunities for intervention.

A quantitative evaluation of these mechanisms, based on controlled experimentation and empirical data gathered from the deployed system in everyday use, shows that Coda is able to provide good performance even when network bandwidth varies over four orders of magnitude -- from modem speeds to LAN speeds.

Host mobility within the largely stationary internetwork has been treated thus far as a routing problem, to be solved entirely within the network layer of the ISO/OSI protocol model. However, mobility of host machines from one attachment point to another affects transport and higher layer protocols as well. In addition, the use of wireless links by mobile computers for attachment to the fixed network infrastructure, gives rise to performance problems due to low bandwidth and high error rates that are typical of wireless environments. The existing network protocols do not provide any mechanism to deal with the problems arising out of host mobility and wireless access. Widespread use of mobile and wireless capable computers is also likely to create a demand for new applications that utilize the mobile user's location for accessing information sources. Applications used in mobile wireless environments may also need to adapt to the changes in the characteristics of the wireless medium.

In this dissertation, we consider the problem of supporting distributed applications on mobile wireless computers that need to communicate with peer applications and servers on the wired internetwork. We present the design and implementation of Indirect Protocols, which allow the use of specialized network protocols for the wireless medium and mobile hosts in a way that is backward compatible with the existing protocols used over the wired internetwork. Indirect protocols are based on two key ideas: i) Special treatment of wireless links and mobile computers in an internetwork and ii) Use of mobility support routers (MSRs) as multi-protocol intermediaries. Mobility support routers provide the necessary support to ensure inter-operability with the existing wired network protocols. We show that the use of indirection results in improved performance at the transport layer and provides enhanced functionality at the remote procedure call (RPC) layer.

In recent years small, completely portable computers have become available on the marketplace. There is demand for such computers, termed walkstations, to access network services while retaining their mobility, and to operate effec- tively in a wide range of conditions. Future office environments are expected to support wireless networks with bandwidths which are several orders of mag- nitude greater than are available outdoors. In such environments, there will be powerful compute servers available for a walkstation's use.

This dissertation describes a novel architecture called Notus and its sup- port for applications operating in a mobile environment. The concept of the traded handoff is introduced, where applications are able to participate in the handoff process, rebuilding connections to the most appropriate service. This is expected to benefit walkstations which roam over large distances, where con- nections to servers would otherwise be strained, and also between heterogeneous networks where cooperation between the networks in performing a handoff might be problematic. It is also proposed in this dissertation that applications could benefit from the ability to migrate onto compute servers as a walkstation moves into the office environment. This enables both the walkstation to con- serve its own resources, and applications to improve the service provided to the end user. Finally, by interleaving a traded handoff with the migration process, it is possible for a migrating application to easily rebuild its connections as it moves to a new host.

The Notus architecture has been implemented, including a traded handoff service, and a new application migration service. The new application migration service was designed since existing application migration services are unsuited to mobile environments and it enables applications to migrate between hetero- geneous hosts with little disruption. Applications which use the service are written in a standard, compiled language, and normal running applications suf- fer little overhead. A number of existing applications which are representative of a walkstation's interactive desk-top environment have been adapted to use the Notus architecture, and are evaluated.

In summary, this work describes how mobility awareness and the support from appropriate tools, can enable walkstation applications to better adapt to a changing mobile environment, particularly when the walkstation is carried between different network types or over great distances.

This research addresses the problem of building software that can be responsive even in environments with widely variable or unknown resource availability. Application programmers' efforts to ensure responsiveness are rendered increasingly difficult by a number of trends in modern computing environments that increase service variability, including:

1. wide scale sharing of resources, such as with distributed file systems,
2. wireless networking for mobile computers, and
3. sporadic inclusion of multimedia in documents.

The key to this approach is the runtime construction of a global dependence graph that relates tasks to each other through their input and output dependencies. This graph is constructed by an application-independent system with minimal programmer effort, and is used at runtime to provide useful services, including:

1. adjusting resource allocation along the branches of the graph to improve response time for those tasks on which the user is currently focused,
2. pruning branches of the graph that no longer represent useful work, thus freeing resources for the computations of interest,
3. managing multiple results of improving quality and their storage behind the abstraction of program variables, and
4. synchronizing the execution of threads on new input quality versions according to programmer-specified semantics.

The combined effect is that it is easier to write applications that provide good responsiveness across a wide and unpredictable range of service variability.

This thesis is concerned with the protocol aspects to support mobility in a Wireless ATM (Asynhronous Transfer Mode) local area network (LAN) environment and adaptability in an ad-hoc wireless network environment. By mobility, this thesis encompasses: (a) defining a Wireless ATM LAN architecture, (b) design and performance evaluation of crossover switch discovery schemes, (c) design and implementation of a hybrid handover protocol, (d) support for uniformed and unified h-andovers of heterogeneous mobile connections.

A review of existing high speed multi-media wireless network architectures is performed and a Wireless ATM LAN architecture which supports (a) distributed handover management, (b) localisd and independent handovers, (c) transfer of handover control, (d) distributed location management, (e) integrated connection management, (f) distributed call admissions and (g) scalable and integrated routing is proposed. The proposed architecture has considered the mobility profiles of users in an in-building environment, where mobility is found to be relatively local. Consequently, a wireless cell clustering concept is employed so as to exploit the advantages of locality, allowing handovers to be handled by different switch entities.

To support handovers through an incremental re-establishment scheme with considerations given to both traffic and handover Quality of Service (QoS) requirements, the concept of crossover switch discovery is introduced. Four switch discovery schemes are proposed, implemented and their per- formance evaluated and compared to an existing scheme. Simulation results revealed two promising witch discovery schemes which are suitable for Wireless ATM LANs employing either a centralised or distributed connection management scheme.

Another aspects of mobility concerns with the ability to provide continuous connectivity to mobile hosts, throughout the live of the communication session. To support mobility in a Wireless ATM environment, a hybrid handover protocol is designed and implemented into a Cambridge Fairisle ATM switch. The implementation verified that the fast switching capability of an ATM switch can be similarly applied for fast re-routing of mobile ATM connections. It also ruled out some of the e-xisting approaches, which are not scalable and effective, when compared to our proposed connectin re-routing scheme.

Many existing research on mobile handovers are concerned with unicast connections. This thesis presents the very first treatment of supporting handovers of mobile multicast ATM connections. The significance of our proposed approach is to treat handovers of unicast and multicast connections as a single topic, i.e., similar handover procedures and crossover switch discovery scheme can be applied to both cases, therefore achieving uniformity and unity.

Finally, from a mobile networking perspective, adaptability refers to the ability of existing network protocols to respond in accordance to the changes caused by mobility, so that communications between mobile hosts can continue correctly. In this thesis, a novel distributed routing protocol, based on the concept of associativity, to support such communications is presented, implemented and evaluated. From an application perspective, however, adaptability refers to the ability to operate over a range of available bandwidth, i.e., user?s QoS may no longer be specified by a single value /level but multiple levels. New insights into application and network QoS adaptation are also presented in this thesis.

With the popularity of portable computers and the proliferation of wireless networking interfaces, there is currently a great deal of interest in providing IP networking support for host mobility using the Internet as a foundation for wireless networking. Most proposed solutions depend on a default route through the mobile host's home address, which makes for unnecessarily long routes. The major problem that this gives rise to is that of finding an efficient way of locating and routing that allows datagrams to be delivered efficiently to moving destinations whilst limiting costly Internet-wide locaion updates as much as possible.

Two concepts - "local region" and "patron service" - are introduced based on the locality features of the host movement and packet traffic patterns. For each mobile host, the local region is a set of designated subnetworks within which a mobile host often moves, and the patrons are the hosts from which the majority of traffic for the mobile host originated. By making use of the hierarchical addressing and routing structure of Internet, the two concepts are used to confine the effects of a host moving, so location updates are sent only to a designated host moving area and to those hosts whih are most likely to call again, thus proving nearly optimal routing for most communication.

The proposed scheme was implemented as an IP extension using a network simulator and evaluated from a system performance point of view. The results show a significant reduction in the accumulated communication time along with improved datagram tunneling, as compared with its extra location overhead. In addition, a comparison with another scheme shows that our functionality is more effective both for location update and routing efficiency. The scheme offers improved network and host scalability by isolating local movement from the rest of the world, and provides a convenient point at which to perform administration functions.

Disconnected operation based on optimistic replication has been demonstrated as an effective technique enabling mobile computers to access shared data in distributed file systems. To guard against inconsistencies resulted from partitioned data sharing, past research has focused on detecting and resolving write/write conflicts. However, experience shows that undetected read/write conflicts pose a subtle but serious threat to data integrity in mobile file access. Solving this problem is critical for the future success of mobile computing.

This dissertation shows that isolation-only transaction (IOT), an upward compatible transaction mechanism for the Unix File System, is a viable solution to this problem. The central idea of the IOT model is imposing serializability-based isolation requirements on partitioned transaction executions. Transactions executed on a disconnected client stay in a tentative state until the client regains connection to relevant servers. They are committed to the servers as soon as they pass consistency validation. Invalidated transactions are automatically or manually resolved to ensure global consistency. Powerful resolution mechanisms such as automatic transaction re-execution and application specific resolver invocation can transparently resolve conflicts for many common Unix applications. In addition, a concise conflict representation scheme enables application semantics to be smoothly integrated for only conflict resolution and consistency validation. The practical usability of IOT is further enhanced by a flexible interactive interface, full compatibility with existing Unix applications, and the ability to retain overall file system scalability, security and transparency.

A working IOT implementation in the Coda file system has been developed and used in experiments in software development and document processing applications. Quantitative evaluation based on controlled experiments and trace-driven simulations establish that the IOT model is scalable and incurs modest performance and resource overhead.

The main contributions of this thesis research are the following: the design of an isolation-only transaction model specialized for improving mobile file consistency while preserving upward compatibility with existing Unix applications; the development of a working IOT implementation in the Coda file system; experimentation and evaluation demonstrating the feasibility and practicality of the IOT model.

Efficient wireless channel allocation, location information management, design of low overhead communication protocols and causal dependency tracking, and fault tolerance are important areas of research in mobile computing systems. This dissertation proposes new and efficient solutions for these problems.

1. A probabilistic analysis of temporal imbalance in wireless channel demand is presented. The effectiveness of channel transfers depends on the duration for which imbalance persists.

2. A distributed dynamic channel allocation algorithm that adapts to spatial and temporal fluctuations in channel demand is presented. The algorithm requires minimal involvement of mobile nodes. The algorithm is deadlock free, starvation free, fair, and scalable.

3. A coterie based approach is adopted for update and querying location information of mobile nodes. Location updates and location queries are made at a subset of location servers. The set of servers, corresponding to a mobile node, for location update and query operations is dynamic. The dynamic nature of these sets alleviates situations of heavy burden on some location servers, when several mobile nodes are concentrated in a small area.

4. It is shown that in order to ensure causally ordered message delivery, only direct dependency information need to be sent with each message. An algorithm using this knowledge to enforce causal ordering of messages is presented. It can handle dynamically changing multicast communication groups.

5. Two alternatives to vector clocks for tracking causal dependencies, are presented. One scheme employs sets of dependency sequences, while the other relies on hierarchical clocks. Both schemes have low overheads, and are immune to fluctuations in the number of nodes in the system: a property that vector clocks lack.

6. For failure recovery, a quasi-synchronous checkpointing algorithm for mobile systems is presented. A minimal set of nodes needs to take local checkpoints. The underlying computation is not blocked during checkpointing. A minimal rollback/recovery algorithm is presented. Computation at a node is rolled back only if its state depends on operations that have been undone due to node failure(s).

All algorithms have low communication and storage overheads, can withstand disconnected operation of mobile hosts, and meet the energy conservation and low bandwidth constraints.

The full thesis is available here
Testing distributed programs and coping with host mobility are among the important topics in distributed computing. Issues in testing distributed programs are considered first, and then problems posed by host mobility in distributed systems are considered. For testing distributed systems, a hierarchy consisting of three levels is proposed. Level 1 involves selecting input data for the distributed program. Level 2 exists due to the asynchrony of the communication medium, and it consists of many runs for each input data selected at level 1. The difficulty at this level is that the number of runs for an input can be enormous. Distributed algorithms are presented to find and generate different runs. At Level 3, a run selected from level 2 is tested. Testing at level 3 is difficult due to the combinatorial explosion of the state space. Several techniques are provided to tackle the state explosion problem while testing a run for errors that are expressed using arbitrary predicates. The techniques include space efficient algorithms, a parallel algorithm, and a method to increase the granularity of an execution step. Next, assuming that errors can be expressed using predicates in conjunctive normal form, an efficient on-line distributed algorithm is presented for detecting them.

Recording global states is useful in setting distributed breakpoints. A message optimal algorithm for recording a global state of a system with causal message ordering is presented. Next, several distributed algorithms for communication support and fault tolerance in mobile systems are provided. Conventional algorithms for causal message ordering cannot be used directly for mobile systems due to their energy constraints. Three algorithms are devised for causally ordered message delivery in mobile systems. The first algorithm handles the resource constraints of the mobile hosts. However, the algorithm is not easily scalable and does not handle hosts disconnections. The second algorithm eliminates the above disadvantages at the cost of inhibiting some messages. The third algorithm is a trade-off between the two algorithms. In all three algorithms, mobile support stations perform considerable amount of work on behalf of mobile hosts. As mobile hosts are highly dependent on mobile support stations, coping with support station failures is important. Two schemes are presented to design mobile computing systems that can tolerate support station failures, and several related issues are discussed. Finally, a protocol to reliably broadcast messages in mobile wireless networks is provided.