Back to SIGMOBILE Main Page
Comments Contact Us Search and Site Map
Executive Committee
Annual Meetings
Annual Reports
SIGMOBILE Publications
Sponsored Conferences
Sponsored Workshops
In-Cooperation Events
Requesting Sponsorship
Distinguished Service
Outstanding Contribution
MobiCom Best Student Paper
SIGMOBILE Membership
Online Application

Abstracts of Selected Ph.D. Theses in the Area of Mobile Computing Awarded in 1995

Low-Latency Handoff for Cellular Data Networks

Srinivasan Seshan

University of California at Berkeley, CA, USA
December 1995

The full dissertation is available here
In this dissertation, we examine the problem of performing handoff quickly in cellular data networks. We define handoff as the process of reconfiguring the mobile host, wireless network and backbone wired network to support communication after a user enters a different cell of the wireless network. In order to support applications and protocols used on wired networks, the handoff processing must not significantly affect the typical end-to-end loss or delay of any communications. This dissertation concentrates on two specific areas of handoff processing: routing updates and state distribution. The techniques we use to solve these problems are:

  1. Multicast to set up routing in advance of handoff.
  2. Hints, based on information from the cellular wireless system, to predict handoff.
  3. Intelligent buffering, enabled by the multicast of data, to prevent data loss without the use of complicated forwarding.
  4. State replication, enabled by the multicast, to avoid explicit state transfers during the handoff processing.

This dissertation describes the design, implementation and evaluation of these techniques in a variety of networking and computing environments. We have shown that any necessary routing updates and state transfers can be performed in a few milliseconds. For example, our implementation in an IP-based testbed completes typical handoffs in 5 - 15 msec. In addition, the handoff processing introduces no additional packet delays or data loss. The primary cost of our algorithms to improve handoff latency is the use of excess bandwidth on the wired backbone networks. However, we have introduced base station layout algorithms that reduce this cost. In current systems, the performance improvement provided by these techniques easily outweigh the resources consumed. Since wired backbone networks will continue to have much greater available bandwidth than their wireless counterparts, this trade-off between handoff performance and network resources will continue to be advantageous in the future.

Medium Access Control Schemes for DS-CDMA Wireless Packet Networks

Zhao Liu

University of Pennsylvania, Philadelphia, PA, USA
September 1995

Medium Access Control (MAC) is the kernel for any wireless communication network and there is no exception for Direct-Sequence Code Division Multiple Access (DS-CDMA) wireless networks. This dissertation focuses upon MAC schemes for DS-CDMA wireless packet networks.

The first part of the dissertation concentrates on channel access protocols for DS-CDMA wireless packet networks. We begin by investigating the approach of using Slotted ALOHA random access protocol for DS-CDMA wireless packet networks. A discrete time Markov chain based analytical framework is developed to analyze this class of protocols. We demonstrate that, by proper design, the system throughput can be doubled with respect to that of a bandwidth equivalent multi-channel Slotted ALOHA system. After observing that Slotted ALOHA does not provide the necessary control for accommodating multimedia traffic, we develop an efficient demand assignment access protocol, named Distributed-Queuing Request Update Multiple Access (DQRUMA). We demonstrate that the delay-throughput performance of the DQRUMA protocol is close to the best possible using any access protocol. We then investigate the approach of using DQRUMA as a demand assignment access protocol for Multi-Code CDMA (MC-CDMA) wireless packet networks that support multi-rate traffic. The network incorporates MC-CDMA and DQRUMA to form a unified bandwidth-on-demand fair-sharing platform for multi-rate services. We demonstrate that the system can provide close to ideal-access performance for a mix of different-rate traffic.

The second part of the dissertation concentrates on interference control in DS-CDMA cellular systems. We begin by developing Signal-to-Interference Ratio (SIR) based Dynamic Call Admission Control (DCAC) schemes for a conventional DS-CDMA cellular system. A soft capacity - residual capacity - is proposed for DCAC purposes. We demonstrate that the proposed SIR based DCAC schemes always outperform the fixed CAC scheme, even under overload situation. We then investigate the reverse link intercell interference in MC-CDMA cellular systems. We derive a Maximum Capacity Power Allocation (MCPA) criterion to reduce the excessive interference caused by high rate MC-CDMA transmissions. We demonstrate that although high-rate MC-CDMA mobiles near the cell boundary can cause significant increase in interference to neighboring cells, MCPA can effectively reduce the MC-CDMA interference to some reasonable range.

A framework for integrating Mobile Hosts within the Internet

Pravin Bhagwat

University of Maryland, USA
August 1995

The full dissertation is available here
Host mobility and wireless access are two emerging design considerations that pose challenging problems at all layers of the networking protocol stack. This dissertation investigates their impact on the design of link, network, and transport layer protocols. At the network layer, we have designed and implemented a new routing architecture that allows the current set of Internet standards to support routing to mobile hosts. At the link and transport layers, we have designed mechanisms to improve throughput over error-prone wireless channels.

At the network layer, the most crucial problem is that of routing. The existing Internet routing mechanisms cannot route packets to hosts whose points of attachment to the network change over time. Exploiting IP's Loose Source Route option, we have designed and implemented a routing scheme which provides location independent network access to TCP/IP compliant mobile hosts. It also allows mobile hosts equipped with multiple network interfaces to dynamically migrate active network sessions from one network interface to another. The proposed scheme only requires the addition of two new entity types, Mobile Routers and Mobile Access Stations. These entities perform all required mobility-aware functions, such as address translation, user tracking and location management. No modifications to existing host or router software are required.

Although MobileIP provides continuous network connectivity to mobile hosts, the effects of host movement and wireless medium characteristics are often visible at the transport layer. We consider the effect of wireless medium characteristics on the performance of Transmission Control Protocol (TCP) sessions. Unlike wired networks, packets transmitted on wireless channels are often subject to burst errors which cause back to back packet losses. We show that TCP's error-recovery mechanisms perform poorly when packets from a TCP session are subject to burst errors. Unlike other approaches which require modification to TCP, our solution requires enhancements only at the wireless link layer, thus making it applicable to other transport protocols as well. We use a Channel State Dependent Packet (CSDP) scheduler which takes wireless channel characteristics into consideration in making packet dispatching decisions. Our results show that the CSDP technique provides improved throughput, better channel utilization, and fairness among multiple TCP streams.


Structuring Distributed Algorithms and Services for Networks with Mobile Hosts

Arup Acharya

Rutgers University, New Jersey, USA
May 1995

The full dissertation is available here
Integration of mobile computers within existing data networks introduces new issues in the design of distributed algorithms and services. Location of a mobile host changes with time, and so the message count of a distributed algorithm should account for the "search" necessary to locate mobile participants. Further, mobile hosts are faced with resource constraints not commonly encountered by their tethered counterparts, viz. a low-bandwidth connection to the rest of the network, and tight restrictions on power consumption.

This dissertation introduces a system model for networks with mobile hosts. To bridge the resource disparity between mobile and static hosts, we propose a two-tier principle for structuring distributed algorithms in this model. We also propose that location-management of mobile participants be integrated with algorithm design.

We first consider a simple, yet fundamental distributed algorithm: a logical ring with a token circulating amongst participants, and restructure it for servicing token requests from mobile hosts. Second, we tackle the problem of delivering a multicast message to mobile recipients from exactly-one location. Third, we present a checkpointing algorithm to record a consistent global state of a distributed application executed on mobile hosts.

The ACM Special Interest Group on Mobility of Systems, Users, Data and Computing