A Network Architecture for Heterogeneous Mobile Computing

Eric A. Brewer, Randy H. Katz

Elan Amir , Hari Balakrishnan , Yatin Chawathe, Armando Fox3, Steven D. Gribble, Todd Hodes,
1 2

Giao Nguyen, Venkata N. Padmanabhan4, Mark Stemm, Srinivasan Seshan5, and Tom Henderson
University of California at Berkeley

This paper summarizes the results of the BARWAN and the power of supercomputers even while mobile— as
project, which focused on enabling truly useful mobile net- long as you access them over a ubiquitous network.
working across an extremely wide variety of real-world net- The resulting architecture reveals how to build this net-
works and mobile devices. We present the overall work out of an overlaid collection of networks, how to seam-
architecture, summarize key results, and discuss four broad lessly roam around it, how to make it perform well, and how
lessons learned along the way. The architecture enables to leverage computing in the infrastructure to enable new
seamless roaming in a single logical overlay network com- abilities and services for even the simplest mobile devices.
posed of many heterogeneous (mostly wireless) physical net- We believe in ubiquitous localized networking: the net-
works, and provides significantly better TCP performance work as a whole has broad coverage, but connection quality
for these networks. It also provides complex scalable and and services vary greatly by location. The connection may
highly available services to enable powerful capabilities vary from wired or infrared in-room networks with great per-
across a very wide range of mobile devices, and mechanisms formance, to metropolitan cellular networks, to satellite net-
for automated discovery and configuration of localized ser- works with high latencies but tremendous coverage. Services
vices. Four broad themes arose from the project: 1) the vary greatly as well: from home/office printer access, to
power of dynamic adaptation as a generic solution to hetero- local driving directions, to global services such as search
geneity, 2) the importance of cross-layer information, such engines and web access. This is an alternative to the idea of
as the exploitation of TCP semantics in the link layer, 3) the ubiquitous computing [Wei93] , in which we care far more
use of agents in the infrastructure to enable new abilities and about nearby connectivity than nearby computing.
to hide new problems from legacy servers and protocol We also believe in a powerful infrastructure that is highly
stacks, and 4) the importance of soft state for such agents for available, cost effective, and sufficiently scalable to support
simplicity, ease of fault recovery, and scalability. millions of users. In general, computation, storage and com-
plexity should be moved from the mobile devices into the
1 Introduction infrastructure, thus enabling powerful new services, better
overall cost performance, and small, light-weight, low-
The BARWAN project was a three-year DARPA-funded
power, inexpensive mobile devices with tremendous func-
project at the University of California at Berkeley that
tionality. We have built such an infrastructure and will show
focused on enabling truly useful mobile networking across
how it provides new abilities for a very simple mobile client,
an extremely wide variety of real-world networks and
the PalmPilot PDA.
mobile devices. This paper presents the overall architecture, We have implemented and evaluated the architecture
summarizes key results, and discusses broad lessons learned
over a three-year period; many of the specific results have
along the way. We attacked nearly all aspects of the prob-
already been evaluated in the literature. We will often refer
lem, including link-layer and transport protocols, mobile
to such papers for more detail and for complete coverage of
routing, power management, application support, multime-
the related work. This paper evaluates the architecture as a
dia streaming, and local and global network services.
whole and summarizes the lessons we have learned.
For quite some time, our group has been driven by a sim- The architecture is probably best introduced in terms of
ple but compelling mantra:
some of the challenging problems for which it offers solu-
Access is the Killer App tions:
Originally, in 1994, it was an argument against the prevail- • We provide seamless mobility both within a network
ing trend towards mobile devices that were essentially and across heterogeneous networks. The detection and
islands of computation— mobile computers looking for a setup of network connections is transparent and
“killer app” similar to a personal organizer. But the phrase is automatic, as is the selection of the best network in
really an argument that what matters is not so much what the range. For several networks, we also provide very low-
device can do, but rather the data and computing power to latency handoffs (below 200ms), thus enabling smooth
which it has access. It is possible to harness terabytes of data audio and video even while roaming.
• We provide a reliable transport layer, based on TCP,
1: Now at Fast Forward Networks that works with legacy servers, while hiding the effects
2: Now at MIT of wireless losses and asymmetry that typically ruin
3: Now at Stanford TCP performance.
4: Now at Microsoft Research
5: Now at IBM T. J. Watson Research Center

1
 Cell-based Wireless Network Services Automatic discovery and config-
Section 5 uration of localized services
Client
Internet Dynamic Adaptation of content
Presentation for heterogeneous networks
Section 4 and devices (the proxy archi-
tecture)
Satellite Transport Reliable data transport for wire-
Scalable, Section 3 less and asymmetric networks
Server Highly Available
Proxy Routing Roaming in heterogeneous net-
Section 2 works (Overlay IP)
Figure 1: Elements of the BARWAN Architecture. In
addition to heterogeneous clients, networks and servers, Transport-aware link-level
we provide a proxy to assist with mobility and dynamic Link Layer retransmission (Snoop proto-
adaptation. The three black circles indicate points visible Section 3.1 col); management of shared
from the client; horizontal handoffs occur between two wireless links
cells of the same network, while vertical handoffs occur Table 1: Layered view of the Architecture
between different networks, e.g., radio-frequency
wireless to satellite. The architecture also enables high-
performance reliable data transport for these networks. surmount these issues through a combination of TCP
enhancements and corrective agents in the infrastructure.
• We provide automatic discovery and configuration of Another key concept and primary contribution is the
local network services, such as local printers and DNS proxy architecture, which uses a powerful agent in the infra-
servers. We also provide remote control of local structure to adapt content dynamically to support heteroge-
environments even if they are new to the user, such as neous networks and mobile devices that (nearly all) servers
the A/V equipment another’s lab. handle poorly. The proxy enables useful access even from
• We support thin clients through dynamic adaptation of very simple devices.
content, tuning the content specifically for the device, Finally, we define an architecture for adaptive network
the user, and the current quality of the network services. IP connectivity is not sufficient: mobile users need
connection, often reducing latency by more than a to discover, configure and use local services, such as DNS
factor of five. We also enable new abilities for such servers, local printers, and in-room control of lights and A/V
devices by leveraging computation in the infrastructure. equipment. This enables a far richer environment for mobile
users, and when combined with the proxy greatly simplifies
• We provide cluster-based support for scalable, the creation and use of new services.
manageable and highly available infrastructure After looking at broad themes and our network testbed,
services. We also provide a layered programming we examine each of the four major areas in Sections 2
model for implementing services that allows authors to through 5. We close by revisiting our themes and summariz-
focus on service content rather than the challenges of ing our conclusions in Sections 6 and 7.
availability and scalability.
1.2 Four Key Themes
1.1 Basic Approach
There are some ideas and techniques that are used repeat-
The there two basic views of the architecture: the physi- edly throughout the architecture. In particular, there are four
cal view of a client roaming through an overlaid collection of general themes that merit higher-level discussion, and that
networks, shown in Figure 1, and the network-layer view, we revisit throughout the discussion.
shown in Table 1. Dynamic Adaptation is the general way we deal with
A key concept is overlay networking, which is the unifi- varying network conditions and with client heterogeneity.
cation of several heterogeneous networks, of varying cover- This includes new adaptive mechanisms for TCP, on-
age and performance, into a single logical network that demand format conversion, real-time video transcoding,
provides coverage that is the union of the networks’ cover- dynamic quality/performance tradeoffs, and even dynamic
age with performance corresponding to the best network in generation of customized user interfaces for small devices.
range. In addition to traditional cell-based roaming (horizon- Cross-layer Optimization: There are several places
tal roaming), we provide transparent roaming across the where we explicitly break the OSI networking model to
constituent networks (vertical roaming), even when this enable smarter adaptation or better performance. These
requires changing the IP address or network interface. include using physical layer information to trigger handoffs,
Given an overlay network, the next immediate challenge and exploiting transport-layer information to guide link-level
is the poor performance delivered by standard TCP over the retransmission and application-level dynamic adaptation.
wireless and asymmetric networks that enable mobility. TCP Agent-Based Capabilities: In order to maximize our
assumes that all losses are due to congestion, and that the ability to work with legacy clients, servers and TCP stacks,
connection is symmetrical, both of which may be false. We we often use agents within the network infrastructure to add

2
new capabilities or to improve performance. Fundamentally, 1600 250

Effective Bandwidth (Kb/s)

the role of these agents is to hide to vagaries of mobility, 1400
200
wireless networking and extreme heterogeneity from all of 1200

Latency (ms)
1000
the legacy clients and infrastructure; the agents make every- 150
800
thing look like it is “supposed to”. The alternative is take an 100
600
end-to-end approach in which you are allowed to modify all 400 50
components, including clients and servers. This has the 200
advantage of a potentially better overall solution, but it is 0
0

nearly impossible to deploy, since it requires upgrading most

clients and servers. We will show that the agent-based solu- 1000000 10000

Registration Time (ms)

Cell Diameter (Meters)
9000
tions not only have a better deployment path, but in many 100000
8000
cases perform better and in some cases are the only option, 10000
7000

because they leverage information outside of the particular 1000

6000
5000
end-to-end connection. We use agents to handle mobility 4000
100
and vertical handoff, to enhance TCP performance for wire- 3000
2000
10
less or asymmetric networks, and as the basis of proxy archi- 1000

tecture. 1 0

Exploit Soft State: Soft state is state that aids in perfor-

Figure 2: Testbed Networks Infrared (IBM)
mance or adds capabilities, but that is not required for cor-
Latency is the round-trip time; WaveLAN (900 MHz)
rectness. Soft state need not be recovered after failures, can
be thrown out at any time, and can typically be stale or Registration Time is the time to Metricom Ricochet
inconsistent without violating correctness. In general, most set up the initial connection. Hughes DBS Satellite
of our agents use soft state to make them simpler and trivi-
ally fault tolerant. We exploit soft state in all aspects of the
design.

1.3 BARWAN Testbed

We concentrate on four networks in the overlay testbed:
IBM Infrared Wireless LAN: This infrared network
forms our basic in-room network [IBM95]. Infrared
provides trivial spectrum reuse, and thus enables very
high bandwidth per cubic meter in buildings. It is also
the lowest cost network.
Lucent WaveLAN: We have used both the 900-MHz and
2.4-GHz versions [ATT94] as our building-size network.
We have coverage of four floors of Soda Hall, with one
or two basestations per floor.
Metricom Ricochet: This is a packet-based radio Figure 3: Wireless Overlay Network Structure
network for metropolitan areas [Met96], including the
Bay Area. We also deployed a private network in Soda 2 Overlay Networking
Hall for experimentation. Figure 3 shows an example of a wireless overlay net-
Hughes Direct-Broadcast Satellite (DBS): We have one work. Lower levels are comprised of high-bandwidth wire-
dish on top of Soda Hall and have also used a portable less cells that cover a relatively small area. Higher levels in
dish at remote sites [Dir98]. the hierarchy provide a lower bandwidth per unit area con-
Figure 2 shows the typical bandwidths, latencies, cell nection over a larger geographic area. In our system, we
sizes, and registration times for these networks. The Effective have three overlay levels. The lowest level is comprised of a
Bandwidth is the throughput measured by the user, excluding collection of disjoint room-size high-bandwidth networks,
overhead and retransmissions. Latency measures the round- which provide the highest bandwidth per-unit-area: one Mb/
trip time for a simple packet. Cell Size is the approximate s or more per room. The second level consists of building-
diameter of the coverage area of one transmitter (basesta- size high-bandwidth networks that provide approximately
tion). Registration Time is the time to set up the initial con- the same bandwidth as the room-size networks, but cover a
nection. The registration times were measured by sending a larger area, for example, a single floor of a building. The
stream of UDP packets to a mobile host, turning on the net- final level is a wide-area data network, which provides a
work interface, and marking the time between when the net- much lower bandwidth connection, typically tens of kilobits,
work interface was turned on and when the first data packet over a much wider geographic area. We can also support
was received by the mobile. The key conclusions are that “mobile” wired networks, such as dynamically connecting to
there is wide variation in all dimensions, and that there is no a local ethernet subnet via DHCP.
single “best” network.

3
 We must depend on existing networking technologies Multicast Care-of Address
and wireless data providers to have a full range of wireless
networks at our disposal. Although we would ideally modify
some components of these systems (e.g. basestation soft- Forwarding BS Buffering BS
ware), this is not always possible. For example, while we can Data
modify and experiment with the basestations for the room- Source Home Beacons Beacons
size and building-size overlays, the wide-area data overlay is Agent
owned and administered by a third party. As a result, we can-
not directly control the overlay’s infrastructure. This is an Mobile Host
important consideration because it limits the modifications
Figure 4: Elements of the Handoff System
we can make (in these cases) to support vertical handoff.
2.1 Vertical Handoffs balance low-latency handoffs with the issues of power and
bandwidth efficiency.
The primary objective of a vertical handoff system is to
minimize the handoff latency for an individual user while 2.2 The Handoff Mechanism
keeping bandwidth and power overheads as low as possible.
Handoffs are built on top of the mobile routing capabili-
There are some important differences between the hori- ties of Mobile IP [Per96], shown in Figure 4. Mobile Hosts
zontal and vertical handoffs. First, there is a distinction
(MHs) connect to a wired infrastructure via Basestations
between up and down in vertical handoffs: an upward verti-
(BSs) which act as Foreign Agents. A Home Agent (HA)
cal handoff is a handoff to an overlay with a larger cell size
encapsulates packets from the source and forwards them to
and lower bandwidth/area, and a downward vertical handoff
the basestations.
is a handoff to an overlay with a smaller cell size and higher
One important difference is that the care-of address (for
bandwidth/area. Downward vertical handoffs are less time- basestations we control) is a multicast rather than unicast
critical, because a mobile can always stay connected to the
address. The mobile selects a small group of BSs to listen to
upper overlay during handoff. Second, in a heterogeneous
this multicast address for packets forwarded by the HA. One
network, the choice of the “best” network can be challeng-
of the BSs is selected by the MH to be a forwarding BS; it
ing; for example, an in-building RF network with a weak
decapsulates the packets sent by the HA and forwards them
signal may yield better performance than a wide-area data
to the MH. The others are buffering BSs; they hold a small
network with a strong signal. Finally, there may also be number of packets from the HA in a circular buffer. These
financial differences that do not arise in a single network;
buffers are soft state: they improve performance and can be
some networks charge per minute or byte.
lost at any time without affecting correctness.
The primary technical objectives in the design of a seam-
Basestations send out periodic beacons similar to Mobile
less vertical handoff system are the balance among handoff
IP foreign-agent advertisements. The MH listens to these
latency, power consumption, and wasted bandwidth.
packets and determines which BS should forward packets,
Low-Latency Handoff: make the switch between net- and which should buffer packets in anticipation of a handoff;
works as seamless as possible with minimal interruption or
the rest simply don’t listen to the multicast group at all.
data loss. As a user roams among areas of good and poor
When the mobile initiates a handoff, as shown in Figure 5, it
connectivity, the only user-visible change should be due to
instructs the old BS to move from forwarding to buffering
the limitations of the specific networks. For example, lower
mode,1 and the new BS to move from buffering to forward-
levels may support full-motion video and high-quality audio,
ing mode. The new BS forwards the buffered packets that
while higher overlays may support only audio. the mobile has not yet received.
Power Savings: minimize the power drain due to multi-
An upward vertical handoff is initiated when several bea-
ple simultaneously active network interfaces. The simplest
cons from the current overlay network are not received. The
approach to managing multiple network interfaces (NIs) is to
MH decides that the current network is unreachable and
keep them on all the time. However, measurements of the
hands over to the next higher network. The arrival of bea-
network interfaces [SGHK96] show that the IBM Infrared and
cons on a lower overlay initiates a downward vertical hand-
WaveLAN interfaces together consume approximately 1.5 off. The MH determines that the mobile is now within range
watts even when not sending or receiving packets.
and switches to the lower overlay. The handoff starts when
Bandwidth Overhead: minimize the amount of addi-
the lower overlay becomes reachable or unreachable, and
tional network traffic used to implement handoffs. Imple-
ends when the first packet forwarded from the new overlay
menting vertical handoffs consumes bandwidth in the form
network arrives at the MH. We depend only on the presence
of beacon packets and handoff messages.
or absence of packets to make vertical handoff decisions.
There are many inherent tradeoffs in meeting these For horizontal handoffs, the MH uses a channel-specific
objectives. For example, reducing power consumption by
metric to compare different BSs and connects to the best one
keeping network interfaces off when not in use increases
according to that metric. This allows the horizontal handoff
handoff latency. Similarly, zero-latency handoff could be
achieved by simply sending and receiving data across all net-
work interfaces simultaneously at all times, but this results in 1: The arrows represent the logical endpoints of a message, not the path
an inordinate waste of bandwidth and power. Our goal is to that the message takes from source to destination. Messages go through the
new basestation if the old one is unreachable.

4
 Old BS MH New BS Metricom Ricochet 3500
4000
3000
3500
3000 2500

(Strong) (Weak) 2500

2000
2000

1500
1500
1000
1000

Milliseconds
500
500
0 0
Metricom to WaveLAN WaveLAN to Metricom

4000
Lucent WaveLAN 3000

3500 2500
3000
2000

(Weak) (Strong)
2500
2000 1500

1500 1000
1000
500
500
0 0
Handoff

WaveLAN to IR IR to WaveLAN
Latency

“Start IBM Infrared

“Stop Forwarding”
Forwarding” Basic Handoff Figure 6: Handoff Performance
Fast Beaconing Comparison of Basic Vertical
Header Handoff with the performance of
Double-cast two optimizations.

= Data Packet
= Beacon Packet packets on the new interface with none on the old. Key
= Handoff Message results include:
• Fast beaconing can result in subsecond handoff latency
Figure 5: Breakdown of a Handoff
proportional to the bandwidth overhead. This approach
consumes bandwidth whether or not data is being sent
system to operate seamlessly underneath the vertical handoff to the mobile device.
system. For an overlay network that handles mobility
directly, such as Metricom, our system does nothing and lets • Header double-casting results in very low latency
the network make its own horizontal handoff decisions. (170ms) with a modest bandwidth overhead (about
15% for WaveLAN).
2.3 Performance • The impact of HD on Metricom handoffs was limited
The primary metric we use to evaluate handoff perfor- because the high base latency negates the “up to date”
mance is the handoff latency, as pictured in Figure 5. More status providing by receiving packets on the secondary
detailed descriptions of this work [SK98] evaluate not only interface.
more optimizations, but also power management and band- • These low handoff latencies enable very smooth audio
width overhead. They also provide breakdowns of the per- and video across the handoff. Handoff is detectable but
formance numbers and analytical models for each method. not disruptive during an audio stream, and nearly
Here we examine the basic mechanism and the two most undetectable during a video stream.
useful optimizations:
Fast Beaconing (FB): The MH can selectively instruct a 2.4 Conclusions
subset of the BSs that are listening to its multicast group to We designed and implemented an overlay networking
transmit beacon packets at a higher frequency, thus reducing system that enables largely transparent handoffs from in-
the time to discover connectivity status. However, this room through metropolitan-area networks. In addition to the
reduces the effective bandwidth on the wireless interface and basic handoff mechanism, we developed two enhancements
may cause media access problems on the wireless subnet. that significantly reduce handoff latency, thus enabling
Header Double-casting (HD): Two BSs are placed in smooth handoffs even for intolerant applications such as
forwarding mode simultaneously; the current BS and a BS of audio playback.
the next higher overlay. The secondary BS sends only the Not all transitions between levels in the overlay network
headers of the packets (since the data is received on the pri- hierarchy can be treated identically. In our system, the best
mary interface); this provides up-to-date status for the sec- choice was specific to the pair of networks that were chosen.
ondary network. When more than n consecutive packets are For our testbed, header double-casting performs the best for
received on a new interface with none received on the old transitions between in-room and in-building networks, and
interface, the MH decides that the old overlay is unreachable fast beaconing works best for transitions between in-building
and initiates a handoff to the new interface. and wide-area networks.
Figure 6 compares these three approaches for four verti- Depending on the presence or absence of data packets
cal handoff scenarios. The beacon period was one second for rather than channel measurements allowed us to rapidly add
the Basic and HD versions, and 200ms for the FB version. new network interfaces to our hierarchy. In addition, by
For HD, we switched networks when we saw 10 consecutive depending only on packet reception, we can handle in an

5
identical way causes for disconnection other than mobility, Wired network
such as the insertion or removal of PCMCIA network cards.
Our solution touches all four themes. Transparent verti- Basestation
cal handoff is an agent-based dynamic adaptation to changes (Snoop agent)
in network quality, including disconnection and the discov-
ery of a better network. It uses cross-layer information both
for horizontal handoff (in networks that we have control of
the basestations) and for enabling upper layers to adapt to Fixed Host
network changes (covered in Section 4).
This is among the earliest work in the architecture, and it Mobile Host
does not uniformly exploit soft state. We do use soft state for
the low-latency handoffs, since we can lose data at the buff- Figure 7: Network topology of the single-hop cellular
ering basestations. However, we use hard state for the for- wireless network based on the WaveLAN. The snoop
warded connections, a decision we inherited from Mobile IP. agent runs at the basestations in the network.
Nonetheless, both still provide support for the power of soft
state, as we encountered many problems that could have TCP responds to all losses by invoking congestion control
been avoided if we didn’t have to maintain hard state at the and avoidance algorithms, resulting in degraded end-to-end
agents. For example, there are complex race conditions performance in wireless systems. In this section, we present
between the recovery of hard-state at the agents (after a fail- the design of a transport-aware link protocol, the Berkeley
ure) and the mobile moving out of range that would not exist Snoop protocol, to overcome these problems and shield
with soft state. If we redid the implementation today, we fixed senders on the Internet from the vagaries of the wire-
would use only soft state at the agents. less link. We also compare our protocol to alternatives to
understand the precise reasons for improved performance.
For more info: overlay networking [SK98][KB96]; low-latency
3.1.1 The Snoop Protocol
handoffs [Ses95][SBK97]; power management [SGHK96].
The Snoop protocol is founded on three of our design
themes: agent-based adaptation, cross-protocol interactions,
3 Reliable Data Transport over Wireless Networks in which the link agent is aware of transport semantics and
messaging, and the use of soft state. Due to the agent
Reliable data transport underlies many of the critical end- approach, we require no modifications to TCP implementa-
user applications supported in today’s Internet, including file tions on fixed hosts in the Internet, and we completely pre-
transfer, electronic mail, and access to the World Wide Web. serve the end-to-end semantics of TCP. The network
It is extremely challenging to achieve high transport perfor- topology and agent location are shown in Figure 7.
mance in an environment characterized by heterogeneous, For transfer of data from a fixed host to a mobile host, we
wireless access technologies. Wireless links bring the chal- deploy a snoop agent at the basestation. The agent caches
lenges of 1) high and bursty losses in addition to network unacknowledged TCP segments and performs local retrans-
congestion, 2) asymmetric effects, and 3) unfair and poor missions of lost segments, which it detects based on dupli-
utilization of shared links. In the next three sections, we dis- cate TCP acks from the mobile host and time-outs of locally
cuss each of these challenges in more detail and present sev- maintained timers. Furthermore, it suppresses duplicate
eral novel solutions. acknowledgments of wireless losses, so they are not seen by
The de facto standard protocol for reliable data transport the TCP sender, thus shielding the sender from these non-
in the Internet is the Transmission Control Protocol (TCP). congestion-related losses. In particular, the agent completely
TCP provides a reliable byte-stream abstraction to the higher hides transient situations of very low communication quality
layers, delivering bytes in-order to the application. TCP has and even temporary disconnection.
evolved to achieve excellent performance in conventional For data transfer from a mobile host to a fixed host, we
wired networks by adapting to end-to-end delays and con- exploit additional local knowledge because we control both
gestion losses. For this purpose, TCP maintains a running the basestation and mobile sender. The snoop agent detects
average of the estimated round-trip delay and the mean lin- missing packets at the basestation by snooping on packets
ear deviation from it. The TCP sender uses the cumulative arriving from the mobile host and identifying holes in the
acknowledgments (acks) it receives to determine which transmission stream. By using heuristics based on local
packets have reached the receiver, and provides reliability by queue-length information, the agent classifies wireless losses
retransmitting lost packets. TCP uses these regular acknowl- as being due to congestion or corruption, and adds corrup-
edgments to pace out new data at a consistent rate, a proce- tion-induced losses to a list of holes. When it eventually sees
dure called ack clocking. duplicate acknowledgments for these holes arriving from the
fixed receiver, signifying a loss of this packet, it sets a bit in
3.1 Combating Wireless Packet Losses its TCP header and forwards it on to the mobile sender. The
TCP is tuned to perform well in traditional networks sender uses this Explicit Loss Notification (ELN) bit to iden-
where packet losses occur almost entirely due to congestion. tify that the loss was unrelated to congestion, and retransmits
However, networks with wireless or other lossy links also the packet without taking any congestion-control actions.
suffer from significant losses due to bit errors and handoffs.

6
 Legacy Correct 1.6
LAN WAN TCP Semantics Snoop+SACK
1.4 Snoop
Vanilla TCP x x
Vanilla + SACK x 1.2

Throughput (Mb/s)
Split Connection x 1 Split+SACK
Split+SACK x 0.8 Vanilla + SMART SACK
Link-Level
Retransmission
x x
0.6 Vanilla + IEFT SACK
Snoop x x Vanilla TCP
Snoop+SACK x 0.4

0 0.2 0.4 0.6 0.8 1 1.2 1.4 0.2

Bandwidth (Mb/s)
0
Figure 8: TCP Performance over Wireless Links 16 32 64 128 256
Bit-error rate (1 error every x Kilobytes, average)
3.1.2 Snoop Evaluation Figure 9: Performance of six protocols (LAN case)
A variety of protocols have been proposed in the litera- across a range of bit-error rates, ranging from 1 error
ture to overcome the effects of wireless bit-errors on TCP every 16 KB to 1 every 256 KB shown on a log-scale.
performance. We classify these schemes into three broad
categories: 1) end-to-end protocols, where loss recovery is the time, and performance only gets worse with a larger
performed by the sender; 2) link-layer protocols, that pro- bandwidth-delay product (as in the WAN case).
vide local reliability; and 3) split-connection protocols, that Adding selective acknowledges (SACKs) helps to some
break the end-to-end connection into two parts at the bases- extent, but only when error rates are low or medium (see
tation to shield the sender from the wireless link. Figure 9). In the LAN case, we used a simple SACK scheme
Figure 8 compares the solutions for performance and based on a subset of the SMART proposal [KM97]. This was
indicates which solutions work with legacy TCP stacks and the best of the end-to-end protocols that we tried, but it is
which provide correct end-to-end semantics. The full papers still slower than the Snoop protocol. In the WAN case, we
on this topic examine more protocols and a wider array of based our SACK implementation [BSK95] on RFC 2018,
bit-error rates, and describe the Snoop protocol in detail which was 65% of optimal. SACKs often allow the sender to
[BSK95] [BPSK97]. recover from multiple losses without timing out. However,
We focus on data transfer from a fixed host to a mobile the sender’s congestion window decreases every time there
host. Each test consists of an 8MB transfer over a combined is a packet dropped on the wireless link, causing it to remain
network with a wired section and a single-hop wireless sec- small. This is precisely the situation that the Snoop protocol
tion using 915-MHz WaveLan. The LAN numbers use a sin- avoids.
gle 10 Mb/s ethernet hop and have a bandwidth-delay Split-connection approaches completely hide the wire-
product of about 1.9KB, while the WAN numbers use 16 less link from the sender by terminating the TCP connection
Internet hops over the wide area, with a bandwidth-delay at the basestation. The second connection can use techniques
product of about 23KB. We ensured that there were no such as negative or selective acknowledgments, rather than
losses due to congestion to isolate corruption from conges- standard TCP, to perform well over the wireless link. This
tion. Wireless losses were emulated by IP checksum corrup- class does not preserve the end-to-end semantics of TCP.
tion according to an exponential distribution of bit errors We present two examples: when the wireless connection
with an average bit-error rate of 1/64KB (about 1.9 x 10-6), uses vanilla TCP and when it uses the SMART-based SACK
which corresponds to a packet loss rate of 2.3% with 1400- scheme described above. With vanilla TCP, the performance
byte packets. Figure 9 graphs the performance against a improvement is not as good as the other schemes, especially
range of bit-error rates. in the WAN case. The congestion window of the wired side
End-to-end Protocols attempt to make the TCP sender remains large and stable compared to an end-to-end TCP
handle losses through the use of two techniques. First, they connection where the congestion window size fluctuates rap-
use some form of selective acknowledgments (SACKs) to idly. However, the wired connection doesn’t make rapid
allow the sender to recover from multiple packet losses in a progress because it periodically stalls due to the advertised
window without resorting to a coarse time-out. Second, they window from the basestation being zero. When SACKs are
attempt to have the sender distinguish between congestion used over the wireless connection, performance is improved.
and other forms of losses using an Explicit Loss Notification However, even this enhancement performs about 10% worse
(ELN) mechanism. than Snoop, in addition to not providing correct end-to-end
The simplest end-to-end approach is vanilla TCP (Reno), semantics and causing slower, more complicated handoffs.
which performs poorly as expected, with only 50% of the Link-layer solutions attempt to hide link-related losses
possible throughput on the LAN and 25% on the WAN. The from the TCP sender by using local retransmissions and pos-
basic problem is that the window size remains small all of sibly forward error correction. Since the end-to-end TCP
connection passes through the lossy link, the TCP sender

7
may not be fully shielded from wireless losses. This can hap- state intact, which further enables smooth handoffs and helps
pen either because of adverse timer interactions between the to hide the transient drop in performance from the sender.
two layers [Cox95], or more likely because of TCP’s duplicate
acknowledgments causing fast retransmissions at the sender 3.2 Combating the Effects of Asymmetry
even for segments that are locally retransmitted. TCP relies on the ack clocking mechanism to pace data
Our base link-layer algorithm uses cumulative acknowl- transmissions into the network. Although this leads to robust
edgments to determine losses and retransmits them locally congestion control in most wired networking scenarios, it
from the basestation to the mobile host; it leverages TCP degrades performance in networks that exhibit asymmetry.
acknowledgments instead of generating its own. It is equiva- A network is said to exhibit asymmetric characteristics with
lent to the Snoop protocol except that it does not suppress respect to TCP, if the data transport performance in one
duplicate acknowledgments. Thus, although this protocol direction significantly affects the traffic and network charac-
successfully prevents sender time-outs, it does not prevent teristics in the opposite direction. The traffic in the reverse
the sender from reducing its window in response to wireless direction could just be the TCP acks. This general definition
losses. In the LAN experiments, the throughput difference is leads to three kinds of asymmetry:
about 10%, but rises to 30% in the WAN case due to the Bandwidth: The bandwidth in the forward direction
higher bandwidth-delay product. The rapid fluctuations in (towards the user) is 10 to 1000 times larger than that in the
sender window size lead to an average size that is smaller reverse direction. Networks based on Direct Broadcast Satel-
than the WAN bandwidth-delay product, which is the reason lite (DBS) systems or wireless cable-modem technology
for the significant performance degradation. This situation is exhibit such asymmetry.
avoided by the TCP-aware Snoop protocol that suppresses Latency: In certain wireless networks, such as Cellular
duplicate acknowledgments. Finally, the best protocol, Digital Packet Data (CDPD), the underlying media-access
Snoop enhanced with SACK information, improves the per- control (MAC) protocol often results in a significantly larger
formance of basic Snoop, especially in burst error situations one-way latency from a basestation to a mobile client than in
(not shown, see [BPSK97]). the reverse direction. In half-duplex networks, such as the
To summarize, Snoop enhanced with SACK provides the Metricom Ricochet multi-hop wireless network, there is a
best performance among the protocols we studied, maintains large variable delay when a node switches from sending to
end-to-end semantics and involves no changes to TCP stacks receiving mode or vice versa, a problem that arises in the
on the fixed hosts. Its relative performance improves signifi- presence of bidirectional traffic including TCP acks. These
cantly as the bit-error rate increases (up to 20 times improve- factors reduce overall throughput and increase the variation
ment for the error rates we investigated), and also improves in round-trip times, which delays retransmissions.
as the bandwidth-delay product increases. Our results also Loss rates: Packet loss may be much greater upstream
demonstrate that the end-to-end connection need not be split than downstream. This could be inherent in the network
at the basestation to achieve good performance. SACKs help technology or the result of distinct upstream and downstream
in recovering from burst losses, but are not sufficient when networks. Ack losses limit the performance of TCP in the
windows are small. Finally, the use of ELN helps in separat- primary direction.
ing congestion control from loss recovery since the sender We identify three specific challenges that network asym-
can now be made aware of non-congestion-related losses. metry presents for TCP performance. We discuss end-to-end
The snoop protocol clearly reinforces our focus on agent- techniques (i.e., enhancements to TCP) and agent-based
based approaches since it works with legacy servers and pro- techniques to alleviate these problems.
vides the best performance, even over end-to-end solutions. First, the ack stream corresponding to a data transfer
Snoop exploits cross-layer information: in particular, we use could interfere with forward progress either 1) indirectly by
both a transport-aware link layer (with Snoop) and a link- the breakdown of ack clocking due to reverse-channel con-
aware transport protocol (with ELN). The snoop agent also gestion or wireless losses, or 2) directly by competing with
exploits soft state; its loss or corruption does not affect the the flow of data packets (as in half-duplex networks like
protocol’s correctness. We achieve this by taking advantage Metricom). Our basic solution is to decrease the frequency
of TCP’s cumulative acknowledgments, which makes it triv- of acks. Our end-to-end approach, called ack congestion
ial to refresh out-of-date state. If the state associated with the control, allows the receiver to reduce the frequency of acks
protocol is lost, it can be rebuilt upon the arrival of the next adaptively, while ensuring that the sender is not starved for
packet and acknowledgment. The snoop protocol should acks. This requires the TCP sender to tell the receiver the
thus be viewed as a performance booster for networks with size of its window. Our agent-based approach, called ack fil-
lossy links. This contrasts it with hard-state approaches such tering, operates at the router or basestation on the far side of
as split connections. the reverse channel. It exploits the cumulative nature of TCP
Finally, the use of soft state dovetails nicely with the acks to filter redundant acks from the queue when a new ack
low-latency handoff scheme of Section 2.2. It takes advan- arrives for the same connection.
tage of the intelligent multicast buffering at the basestations, This decreased frequency of acks leads to the second
designed to achieve low-latency handoffs, to perform the problem: since each new ack could cause the sender’s win-
mirroring of the Snoop agent’s soft state. When a handoff dow to slide forward by several segments, the sender could
completes, TCP connections thus resume with their snoop emit a burst of several packets back-to-back, and induce con-
gestion. Since the TCP sender increments its congestion

8
 40 AF

3.93
4.0 Forward 50 R: TCP Reno
35 ACC

Throughput (Kb/s)
3.5 R AF: Ack filtering
Reverse

Throughput (Kb/s)
Throughput (Mb/s)

40

26.70
30 ACC: Ack Cong Control

25.31
3.0
25

20.08
20.31
2.5 30
2.0 20 ACC AF
R

1.45
20 AF

1.29
15
1.5 R ACC
1.0 10 10
5.10
0.35

5
0.16

0.09
0.5

0.00
0
0 0 1 2 3
Reno ACC Reno+ ACC+ AF AF+ Number of wireless hops
Acksfirst Acksfirst Acksfirst
Figure 11: TCP throughputs from simulations of Reno,
Figure 10: Throughput of a 3 MB forward transfer and a ACC and AF, as a function of the number of wireless
100 KB reverse transfer; 10 Mb/s forward and 28.8 Kb/s hops. Simulation parameters are derived from the
reverse bandwidth. Note that the reverse throughput is 0 Metricom packet-radio network.
for the “AF+Acksfirst” case.

window based on the number of acks and not on how many forward transfer significantly by avoiding the long delays on
bytes are acknowledged with each ack, window growth the reverse channel, and 2) ack congestion control (ACC)
could be much slower. An end-to-end solution, called sender reduces the impact of forward acks on reverse transfers.
adaptation, breaks up a potentially large burst into several Figure 11 shows the performance of various schemes
smaller bursts and regulates these smaller bursts according to obtained via a simulation of the Metricom packet-radio net-
the effective data transfer rate of the connection. Our agent- work. The important observation is that ack filtering (AF)
based solution, called ack reconstruction, hides the infre- and to a lesser extent ack congestion control (ACC) result in
quent ack stream from the TCP sender by deploying an agent improved performance. The reduced frequency of acks
at the near side of the reverse channel. Once the acks have decreases MAC contention, reducing latency variation and
traversed the constrained network, the ack reconstructor eliminating overhead for switching directions. The perfor-
regenerates the original smooth ack stream by inserting new mance improvement is between 20% and 35%.
acks to fill in gaps and by spacing apart acks that have been To summarize, the set of end-to-end and agent-based
compacted. The end result is that an unmodified TCP sender techniques we have developed overcome the adverse effects
can continue to rely on standard ack clocking to sustain the of asymmetry in a variety of asymmetric situations.
data transfer at a consistent rate. As with Snoop, our solutions combine agent-based
The final problem arises specifically in an asymmetric- approaches with cross-layer information and extensive use
bandwidth situation where the acks of the forward-direction of soft state. In the best, version combine two agents to pro-
data transfer must share the constrained reverse channel with vide good performance with legacy TCP endpoints: the
a reverse-direction data transfer (simultaneous bidirectional agent on the far side of the asymmetric link provides ack
data transfers). With FIFO queuing, the large data packets of compression and better ack scheduling relative to bidirec-
the reverse transfer could block the transmission of acks for tional transfers, while the near-side agent reconstructs a
long periods of time, thereby starving the sender of the for- smooth ack stream to enable smooth ack clocking in unmod-
ward transfer. Our agent-based solution to this problem, ified senders. Both of these agents exploit cross-layer infor-
called acks-first scheduling, involves giving acks a strictly mation and assumptions (such as importance of a smooth ack
higher priority than data packets. The rationale is that the stream) as well as soft state for simple implementations that
small acks packets when sent infrequently would have little improve performance while maintaining correctness even in
impact on the performance of the reverse data transfer, but the presence of faults.
their timely transmission is critical to sustaining good perfor- 3.3 Summary
mance for the forward data transfer. Since the resolution of
this problem requires control over the scheduling of data and In summary, our general approach to improving data
acks at the reverse bottleneck link, it is not possible to solve transport performance in mobile, wireless networks has been
this problem without an agent. to identify the specific characteristics of such networks, such
We have performed a detailed evaluation of these solu- as wireless errors, asymmetry, and unfairness, that impact
tion techniques both via ns simulation as well as in our net- TCP performance, and then to explore both TCP enhance-
work testbed. These results are discussed in detail in [BPK97] ments and agent-based mechanisms that alleviate them.
and [BPK98]. We present here sample results for both the The agent-based approaches are often as good or better
asymmetric-bandwidth and asymmetric-latency configura- than end-to-end TCP modifications, and provide the critical
tions. Figure 10 shows the performance of various schemes additional advantage of immediate deployment, thus allow-
when there is two-way traffic in an asymmetric network. We ing us to integrate wireless technologies cleanly into the rest
make two observations: 1) acks-first scheduling helps the of the global Internet. The keys to making agents work well

9
 Client App Client App SPECint92/ Screen
App Support App Support Platform Bits/pixel
Memory Size
medium
low bandwidth High-end PC 198/64M 1280x1024 24, color
bandwidth Transcoders
Image Midrange PC 157/8M 1024x768 16, color
SPAND PostScript Midrange laptop 51/8M 640x480 8, color
Audio
Proxy Video Palm Pilot low/1M 160x160 2, gray
Table 2: Physical Variation Among Clients
high bandwidth

On-Demand Image Real-Time Video

Server Transformation Transcoding
Reduce resolution, color
Figure 12: Basic proxy architecture. The proxy uses the

Hardware
Reduce image resolution, depth, frame rate, frame
transcoders to optimize the quality of service for the color depth, convert to quality (e.g. quantization
client in real time. SPAND monitors end-to-end gray-scale or monochrome factors), convert to gray-
bandwidth and connectivity to the clients (and servers) with halftoning. scale or monochrome with
and notifies the proxy of any changes, which may result halftoning.
in changes in transcoding to adjust the quality of service. Format conversion: NV,
Format conversion: GIF,
Software
H.261, Motion JPEG,
are to exploit cross-layer information, such as the ack JPEG, PICT, Pilot format,
MPEG, InfoPad VQ [N+96];
PostScript; multicast to
semantics of TCP, and to build them based on soft state for multicast to unicast con-
unicast conversion
simplicity, scalability (since there is no consistency issue), version
and availability (since they are trivially restartable). Finally, Dynamic network varia-
Network

agent-based approaches are the only solution when we need Dynamic network varia-
tion due to RF effects or
to exploit cross-layer information from multiple connec- tion due to RF effects or
overlay handoffs; variation
tions, as illustrated by ack-first scheduling for asymmetric overlay handoffs.
in jitter or latency.
links.
Table 3: Dynamic adaptation in response to variations
For more info: Wireless TCP [BPSK97], Snoop and handoffs across client hardware and software, and dynamic
[BSK95]; handling asymmetry [BPK98]. network conditions.

down and the number of colors reduced, thereby reducing

4 The Proxy Architecture the size of the representation. For video, we can reduce the
frame size, frame rate, color depth, and resolution to create a
The key to applications in a mobile, wireless, very heter-
smaller but reduced-quality representation. Intimate knowl-
ogeneous environment is the proxy architecture, which uses
edge of each datatype allows distillation to achieve tremen-
a proxy as a smart intermediary between traditional servers
dous compression, sometimes better than a factor of ten, that
and heterogeneous mobile clients. The fundamental driver
preserves much of the semantic content of the original.
for this architecture is the inability of (nearly all) servers to
The first purpose of the distilled object is to allow the
handle the incredible variation in software, hardware and
user to receive some version of an object quickly; they can
networking capabilities of mobile clients. Through various
then evaluate the value of downloading the original, or some
forms of data transformation, the proxy can dynamically
part of the original. For instance, zooming in on a section of
translate between the needs of clients and the formats and
a graphic or video frame, or rendering a particular page con-
abilities of the servers. The basic architecture is shown in
taining PostScript text and figures without having to render
Figure 12.
the preceding pages. We define refinement as the process of
In addition to the wide variation in networks covered in
fetching some part (possibly all) of a source object at
previous sections, there are also significant variations in
increased quality, possibly the original representation.
software and hardware. Software variations include the data
The second and more powerful purpose is to enable new
formats that a client can handle, such as JPEG, PostScript
abilities in clients, which arises out of dynamic adaptation to
and video formats, and also protocol issues such as HTTP/
formats and data rates that the client can handle. For exam-
HTML extensions and multicast support. Hardware varia-
ple, we have enabled: 1) web browsing with graphics on the
tions are summarized in Table 2.
PalmPilot (covered in Section 4.4.1), 2) PostScript viewing
The key idea in on-demand transformation is distillation,
via distillation to HTML, 3) MBone video over ISDN,
which is highly lossy, real-time, datatype-specific compres-
transcoded from 400 Kb/s down to 128 Kb/s; and 4) partici-
sion that preserves most of the semantic content of a docu-
pation in multicast-based white-board sessions on the
ment or stream. For example, a color image can be scaled
PalmPilot, which supports neither multicast nor the basic

10
 18.8
1.9 Transmit
Cartoon 3.2
(KB) 5.5 Distill
10.3
492
Soda 2.3 446
Hall 3.2
4.5
(KB) 7.6

Figure 13: Scaling this JPEG image by a factor of two in 48

each dimension and reducing JPEG quality to 25% 2 59
Portrait 3
results in a size reduction from 10KB to 1.5KB. (KB) 4.9
9.4
white-board formats such as GIF images. These examples
illustrate the power of dynamic adaptation via an agent (the 0 5 10 15 20 25 30 35 40
proxy), and show how very simple clients can leverage a Latency (sec)
powerful infrastructure to achieve capabilities that they Figure 14: End-to-end latency for images with and
could not achieve on their own. without distillation. Each group of bars represents one
image with 5 levels of distillation; the top bar represents
4.1 On-Demand Transformation no proxy at all. The y-axis number is the distilled size in
Although we have looked at several data types for on- kilobytes (so the top bar gives the original size). Note
demand transformation, we will focus on just two examples, that two of the undistilled images are off the scale; the
Soda Hall image is off by an order of magnitude. These
images and video, since they are challenging and signifi- numbers are from a Sun SparcStation 20.
cantly reduce the required bandwidth. Table 3 shows several
kinds of dynamic adaptation that the proxy can make in 40
Peak Signal/Noise Ratio (dB)

response to hardware, software and network heterogeneity.

The image transcoder takes several input formats, includ- 38
ing GIF and JPEG, and produces an optimized output. Figure
13 shows an example transformation. The output depends on 36
the network conditions and the client’s hardware and soft- 34
ware capabilities. Typically we use a format that is both
small and easy for the client to render. 32
The graphs in Figure 14 depict end-to-end client latency
for retrieving the original and each of four distilled versions 30
of a selection of GIF images. The images are fetched using a 28
14.4 modem through the Berkeley PPP gateway, via a proxy 0 2 4 6 8 10 12 14 16 18
that runs each image through a GIF distiller. Each bar is seg-
Frames/Sec
mented to show the distillation latency and transmission
latency separately. Clearly, even though distillation adds
176x144, 28.8K 176x144, ISDN
latency at the proxy, it results in greatly reduced end-to-end
latency, in addition to better looking output for that client.
352x288, 28.8K 352x144, ISDN
As with image transformation, video-stream transcoding
mitigates all three forms of client variation. Figure 15 exhib- Figure 15: The four-way tradeoff among bandwidth,
its the tradeoffs that can be made in video distillation. The frame resolution, quality (measured in peak signal/noise
video transcoder, called vgw, handles several video formats ratio), and frames per second. Dynamic adaptation
and can transcode video in real time at frame rates up to 30 enables fine-grain control of these tradeoffs, and can
frames/second [AMZ95]. Since each frame is converted in real provide consistent quality or frame rates even as network
time, the proxy can make frame-by-frame tradeoffs and can conditions vary over time.
respond very dynamically to changing network conditions.
As an example of a new ability enabled by the architecture,
vgw makes it possible to watch MBone broadcasts over 4.2 Measuring Changes in Network Characteristics
ISDN via adaptation from about 400 Kb/s to 128 Kb/s. To use transcoding to adapt to network variation, the
In both cases, the original servers are unaware of the proxy must have an estimate of the current network condi-
transformations or of the limited capabilities of the clients or tions along the path from the proxy to the client. We have
networks. Thus we can combine very heterogeneous clients developed a network measurement system called SPAND
and networks with sophisticated legacy servers that target [SSK97], Shared Passive Network Performance Discovery,
stationary desktop PCs and workstations. that allows a measurement host to collect the actual applica-
tion-to-application network performance (e.g., available
bandwidth and latency) between proxies and clients. The

11
 Service: Service-specific code
• Workers that present human interface to what
TACC modules do, including device-specific

Requests/Second
presentation

Queue Length

Requests/second
• User interface to control the service
• complex services: implement directly on SNS layer.
TACC: Transformation, Aggregation, Caching, Customi-
zation
• API for composition of stateless data
transformation and content aggregation modules
• Uniform caching of original, post-aggregation and
post-transformation data
• Transparent access to Customization database (a)
SNS: Scalable Network Service support
• Incremental and absolute scalability
• Worker load balancing and overflow management

Queue Length
• Front-end availability, fault tolerance mechanisms
• System monitoring and logging
Figure 16: Scalable Network Service Layered Model

proxy consults this database of performance information to

determine the appropriate amount of distillation to use for a
particular client. We have also added hooks for clients or
third parties, such as the overlay networking software, to
notify the proxy of changing network conditions. All new (b)
transformations compute the degree of distillation based on
these new capabilities. Figure 17: Distiller queue lengths observed over time as
the load presented to the system fluctuates, and as
4.3 Scalable Cluster-Based Proxies distillers are manually brought down. (b) is an
enlargement of (a).
Because the proxy is a permanent part of the network
infrastructure, it must meet all of the utility requirements of
in April 1997, and many people use it all of the time even
the rest of the network, which include very high availability,
from wired networks such as modems and ISDN.
ease of management, and scalability to support millions of
The SNS layer is implemented on a network of worksta-
users. In addition, these capabilities are difficult to obtain, so
we would like to isolate the utility requirements from the tions to provide these benefits; the architecture and analysis
of this layer are beyond the scope of this paper, but are cov-
functionality of the proxy; this allows authors of proxy-
ered in [FGCB97]. Using a cluster of ten Sun 140-MHz Ultra-1
based services to focus on the content of their service rather
workstations, we were able to show that even the image-
than on the challenges of availability and scalability.
transformation part of TranSend, which is relatively heavy-
Towards this end, we break the proxy into three distinct
weight, scales linearly to handle over 170 transformations
layers, as shown in Figure 16. The lowest layer, Scalable
Network Service (SNS) support, provides all of the availabil- per second, which is sufficient for more than 10,000 simulta-
neous users, and more than 10 million transformations/day.
ity, scalability, load balancing and monitoring functionality.
We have also demonstrated very high availability, with
The middle layer, TACC, described below, provides a pro-
very low downtime since the TranSend service began opera-
gramming model for authors that simplifies service creation
tion. The fault-recovery capabilities enabled this uptime
and that hides the details of the SNS layer, thus providing
without any dedicated system-administration staff. Figure 17
scalability and availability “off the shelf.” The top layer han-
dles the actual presentation of data and client protocols such shows a trace of the availability, load balancing, and burst-
recovery mechanism in action. Failed TACC workers are
as HTTP, and manages all of the open connections. Typi-
cleanly restarted in a few seconds and new workers are auto-
cally service authors need only write TACC modules to
matically deployed as load rises; together these mechanism
implement their service, the SNS and service layers provide
ensure low latency (short queue lengths), load balancing, and
everything else.
excellent overall response time, even with faults.
To explore these issues, we built and deployed a scalable
transformation proxy called TranSend, which is available Finally, we found that the cost of the computing infra-
structure is extremely low, about 25 cents per user per month
publicly at http://transend.cs.berkeley.edu . It fol-
for all of the equipment [FGCB97]. The basic reason for better
lows the layered architecture and all of its functionality
cost performance is the statistical multiplexing enabled by
resides in the TACC layer via a collection of about a dozen
moving resources from client devices into the infrastructure,
modules. It has had over 10,000 unique users since its launch
where they can be shared. For example, ISPs typically have

12
1/20th as many modems as their customers, even though and runtime environments of the devices preclude their
every connection requires one on each end. Similarly, com- implementation. Even if data types such as GIF or JPEG
puting power in the infrastructure is more than twenty times images are supported, most Web images remain awkward to
more efficient simply because it is not idle 80% of the time use due to the limitations in the screen, the memory/storage
(or more), as in mobile devices, which are often off and have capacity, and the CPU performance. For example, the 3Com
bursty utilization even when in use [GB97]. PalmPilot has a 160x160x2 gray-scale display, 1MB of
NVRAM, and a 16-MHz Motorola Dragonball processor.
4.4 Generalized Proxies: The TACC Model The proxy architecture solves this problem by moving
So far, we have motivated the proxy architecture as a nearly all of the complexity and cost into the infrastructure,
mechanism for on-demand transformation. However, the where we can apply multiple workstations and leverage
proxy architecture is far more general and powerful. In par- powerful libraries and development environments. By shift-
ticular, we can generalize the proxy into a powerful platform ing complexity off of the impoverished device to the TACC
for composable infrastructure services. server, we were able to implement the Top Gun Wingman
This more general model is called TACC, for transforma- web browser on the Palm Pilot, the first (and so far only)
tion, aggregation, caching and customization. As described graphical web browser for the Pilot. Wingman has more than
above, transformation is an operation on a single data object 10,000 regular users.
that changes its content; examples include filtering, format The client-side code knows nothing about the web— it
conversion, encryption, and compression. merely knows how to receive and render various high-level
Aggregation involves collecting data from several data types such as bitmapped images and formatted text seg-
objects and collating it in a prespecified way. For example, ments. All of the HTTP/HTML processing, image parsing,
one aggregator collects all listings of cultural events from a image distillation, and page layout are implemented in the
prespecified set of Web pages, extracts the date and event TACC server as a pipeline of workers. The pipeline’s output
information from each, and combines the results into a is a ready-to-render page, with both graphics and text.
dynamically generated “culture this week” page. The combi- Our partitioning of the web browser has enabled a num-
nation of transformation and aggregation by TACC workers ber of innovative features that are not possible without the
results in an extremely general programming model; in fact, proxy architecture:
transformation proxies [Bro+96], proxy filters and caches, Accelerated Download Time: one worker in the Wing-
customized aggregators [SB97], and search engines are all man TACC pipeline performs the same on-the-fly image dis-
subsumed by the TACC model. tillation that we described above. This feature combined
Caching plays an interesting role in TACC, because in with more the efficient representation of the entire page as a
addition to caching original Internet content, the caches in single easy-to-parse data block (versus multi-connection
our architecture can store post-transformation data, post- HTML) makes download times on Top Gun Wingman faster
aggregation content and even intermediate results. Like all than even text-only PDA web browsers.
caches, its contents are entirely soft state that can be regener- Transparent Functionality Upgrades: because most of
ated at the expense of network latency or computation. the web browser is implemented in the TACC server, it has
Customization allows many users to share a smaller num- been possible for us to upgrade the browser’s functionality
ber of services, by parameterizing the services and recalling without redistributing software to all of the clients. For
each user’s parameters as they invoke the service. This is example, when we implemented a better graphics trans-
similar to allowing each user to pass different “command- former that performed high-frequency enhancement of
line arguments” to the service. The customization database, images to increase edge visibility, we simply dropped in this
in most respects a traditional ACID database, maps a user- worker as a replacement to the old image transformer, and
identification token, such as an IP address or HTTP cookie, all of our clients instantaneously began receiving higher
to a list of key-value parameters. quality images.
A key strength of our architecture is the ease of composi- Aggregation Services: the Wingman browser has access
tion of tasks; this affords considerable flexibility in the trans- to all of the aggregation services implemented in our TACC
formations and aggregations the service can perform, server, since they compose. We have also built and deployed
without requiring workers to understand task-chain forma- several aggregators that present condensed versions of popu-
tion, load balancing or burst management., any more than lar search engine and directory services that are better suited
programs in a Unix pipeline need to understand the imple- to the limited screen real estate on the Palm Pilot.
mentation of the pipe mechanism. We now look at some Support for Complex Data Types: there are many data
illustrative examples of TACC programs that reveal the types that would be simply infeasible to handle on the client
power of worker reuse and composition. side, such as ZIP files and PostScript. However, we can han-
dle these data types in the TACC server. For example, we
4.4.1 Top Gun Wingman implemented a worker that accepts a ZIP compressed
Bringing web access to resource-poor devices such as archive, and presents its contents to the browser as a list of
PDAs, smart phones, or set-top boxes is fundamentally diffi- hyperlinks. When the user selects a link, the TACC worker
cult because these devices are ill-suited to the tasks of pars- extracts the relevant object, performs any required data-type
ing, decoding, and rendering web content. These devices do specific transformations, and then sends only that trans-
not directly support web data types, and the development formed element to the client. Since Pilot applications are

13
 more immune to certain end-to-end attacks because of the
nature of the client devices. In fact, Charon turns such
Figure 18: Top Gun devices into a powerful form of “smart card.”
MediaBoard allows the The success of the TACC platform in supporting Wing-
PalmPilot to participate in man and other applications is strong evidence for its role as
shared-whiteboard sessions, an enabling technology for deploying complex, scalable,
despite its small display and highly available, and composable services.
inability to support the
Scalable Reliable Multicast 4.5 Summary
protocol on which the original We have presented a uniform architecture that addresses
MediaBoard is based. extreme variation in the areas of client hardware, software,
and connectivity, via powerful dynamic adaptation of proto-
cols and content. Because the architecture is structured
around agent-based on-demand transformation, we require
no changes to the existing infrastructure and servers.
normally stored as ZIP files, this allows users to install appli- We use cross-layer information to control the degree of
cations directly off of the Internet with a single click. distillation very dynamically based on current network con-
4.4.2 Other TACC Services ditions. For example, as a mobile user walks outside, not
only do we perform a seamless vertical handoff, but we also
In addition to Top Gun Wingman, there are many other notify the proxy of the change in network quality. In
TACC-based services. To illustrate the variety of applica- response the proxy increases the amount of distillation, thus
tions, we highlight a few that are being deployed at Berkeley maintaining the same response time (within about 10-20%)
for widespread public use. even though the network conditions have changed by more
Group Annotation for the Web: Inspired by prior work than an order of magnitude in bandwidth and latency
on annotating the Web [SMB96], we built a scalable, highly (assuming a handoff from WaveLAN to Metricom).
available group-annotation service. The annotations are kept Although not discussed, the cluster-based proxy imple-
in a separate database and are combined with source docu- mentation makes extensive use of soft state [FGCB97], includ-
ments on the fly via transformation; this allows annotation of ing all of the management and worker state except for user
any page, even without write access to the original. Controls profiles, which need to be persistent. In fact, we originally
are added with annotations, which allow the user to invoke a implemented the manager with mirrored hard state and fail-
Java-based annotation viewer/editor. over, but later replaced it with a much simpler and more
Top Gun MediaBoard: MediaBoard is a modular reim- effective soft-state based approach.
plementation of the shared Internet whiteboard wb [JM95]. The proxy architecture includes many significant contri-
Top Gun MediaBoard [CF97] is a TACC-based implementa- butions:
tion of this program for the PalmPilot, which is partitioned
so that the heavyweight Scalable Reliable Multicast (SRM) • On-demand transcoding reduces end-to-end latency,
protocol is run at the TACC server, by a MASH worker rep- often by an order of magnitude, for a wide range of
resenting a particular mb session. A compact unicast data- network media. Dynamic adaptation allows clients to
gram protocol is used for communication between the refine content selectively and spend more bandwidth
PalmPilot clients and the TACC server, which also does for improved quality as needed, e.g., zooming in on
coordinate transformations and image transformations (reus- part of an image or video frame.
ing many of the Wingman TACC modules) corresponding to • Knowledge of client limitations allows transcoders to
the MediaBoard draw operations occurring in the session. optimize content for each client: images, video, and
Top Gun MediaBoard thus performs both data adaptation rich text all look significantly better after distillation
and protocol adaptation, making it a prime example of the because they target the client’s optimal colormap and
flexibility of the TACC toolkit for building adaptive applica- screen fonts. This property leaves servers free to target
tions. Figure 18 shows a screenshot of the TGMB client. the high end.
Charon Indirect Authentication: We have built a prox-
• Knowledge of changing network conditions, via cross-
ied version of Kerberos IV, called Charon [FG96], for use
layer information, allows adaptation of transformation
with resource-poor clients such as PDAs and smart phones.
parameters to maximize the overall quality of service,
This partitioning allows an untrusted proxy to interact with
including both representation quality and performance.
the Kerberos infrastructure on behalf of the clients, giving
the clients full authenticated (and optionally encrypted) • Moving complexity into the infrastructure enables
access to the services but relieving them of the significant significant new abilities for clients, as illustrated by
burden of having a full Kerberos implementation. Even Wingman, Charon indirect authentication, and MBone
though nearly all of the Kerberos functionality is imple- participation over ISDN, among many other examples.
mented by the proxy, neither the user’s Kerberos password • The TACC model simplifies development of complex
nor their keys for new services ever leave the client device, services, and hides the very challenging problems of
thus enabling use of an untrusted proxy. Charon has the scalability, availability and load balancing.
same immunity to protocol-based attacks as Kerberos, and is

14
 • We have deployed for public use several TACC-based Local-area service discovery is based on embedding
services that not only provide compelling services, but location information into existing data networks rather than
also show that the proxy architecture really can enable using external information such as GPS coordinates. Outfit-
both powerful new services and a very heterogeneous ted subnets periodically broadcast a beacon packet to the
mobile and wireless infrastructure. local subnet broadcast addresses (and in some cases multi-
cast with limited scope).
For more info: transformation [FGBA96]; video transcoding The local server for a client’s current attachment point is
[AMZ95]; cluster-based services [FGCB97]; TACC applications encoded in the beacons. Notifications of a change are
[UCB97]; network monitoring and SPAND [SSK97] . implicit. Further service information is obtained by querying
this service discovery server. The list of local services can be
obtained by requesting the well-known meta-service
5 Adaptive Network Services “INDEX”. This minimal bootstrap standardizes the mecha-
nism without constraining its interpretation, thereby allow-
The Network Services component of the architecture
ing variation in resource discovery protocols as they evolve.
builds on our routing, transport, and the proxy architecture.
It provides support for locale-specific discovery of available We unified the service discovery bootstrap and mobility bea-
cons by observating that mobility beaconing is simply a form
resources and “on-the-move” reconfiguration of, and adapta-
of announce-listen protocol. The announce rate is one that
tion to, these resources. It additionally provides mobile cli-
provides acceptable handoff latency.
ents with a generic “remote control” for their environment.
Client-based beaconing is used in both the Active Badge
This supports seamless interaction with the current environ-
[HH94] and ParcTab systems [SAG+93], while Mobile IP uses
ment as clients roam in overlaid networks.
infrastructure-based beaconing, as do we. This is the correct
We have developed for our building the following exam-
ple services: design choice for three reasons: the support for user (rather
than infrastructure) anonymity, better bandwidth scalability
• untethered interaction with lights, video and slide in a network where there are many MHs per BS, and because
projectors, a VCR, an audio receiver, and other A/V power is more precious on mobile devices.
equipment from a wireless laptop computer; There is one additional field in the beacon packets: an
• automatic “on-the-move” reconfiguration for use of application-specific payload. This provides two advantages.
local DNS/NTP/SMTP servers and proxies; First, it makes data available to mobiles before registration
(in the Mobile IP sense), allowing the possibility of “anony-
• audited local printer access;
mous” access to this broadcast data. Second, it acts as a vehi-
• visualization of physical geography and object cle for announce/listen protocols that require only limited
locations via a protocol for interactive floor maps; announcement timer adaptability (discrete multiples of the
• advertising available local services (or other data) to base beaconing rate), such as control applications. We cur-
unregistered (“anonymous”) clients. rently piggyback a list of some or all of the available services
in the cell, allowing anonymous assessment of them and
Our premise is that providing basic IP access to clients is reducing discovery latency.
not enough. We must augment basic IP connectivity with an
adaptive network services infrastructure. Distillation proxies 5.2 Remote Control
are one example of a network service that may require dis-
Providing users with local services exposes new chal-
covery and reconfiguration. The challenge is to develop an
lenges. One is supporting group meetings in which some
open service architecture that allows heterogeneous clients
participants are physically clustered together in a meeting
to discover what they can do in a new environment and inter- room and others attend from distributed desktops via remote
act with it while making minimal assumptions about stan-
conferencing tools.
dard interfaces and control protocols.
For a room participant to interact with the local instantia-
We provide mechanisms for 1) service discovery, 2)
tions of the conferencing tools yet still participate in the
remote-control interfaces, and 3) access control based on
meeting, it is necessary to extend these (local) tools so they
physical locality.
can be controlled remotely. This requirement has two parts:
5.1 Service Discovery it must be possible to control the devices in the room (i.e.,
local services for each), and it must be possible for partici-
The service discovery protocol allows for the mainte- pants to control these things while participating in a meet-
nance of dynamic repositories of service information, adver- ing.
tises its availability, and supports queries against it. The To address these requirements, we extend both room
Service Location Protocol [VGPK97], under development by devices and existing collaborative applications with shared,
the IETF Service Location working group, is one proposal simplified, remote-control interfaces. These interfaces main-
for implementing local-area service discovery. tain two key departures from the current suite of collabora-
We have implemented local-area service discovery and tion tools. Rather than focus on use at the desktop, with local
are in the process of extending it for use in the wide-area. control of each application through its user interface (a one-
The latter introduces additional challenges: scalability, secu- to-one mapping of participants to controllers), we generalize
rity, hierarchies, and multiple administrative domains. this mapping, allowing a group of users to share control

15
through the use of their personal mobile devices. Addition- 6 Discussion
ally, we specify a set of “standard configurations” of these Returning to a broad view of the architecture, we exam-
applications and devices, thereby reducing the required com- ine some of the issues that we did not address, contrast BAR-
plexity. Details of our experience with “remote-controlled WAN with related work, and revisit our four themes.
vic” (rvic) are available [HN97].
An important area of ongoing work is in interface speci- 6.1 Key Issues not Addressed by BARWAN
fication languages (ISL), which we are using as a way to
There are several important areas that we did not directly
generate a functional user interface for devices and services
address in the architecture. First, we limited ourselves to off-
that have “never met”. That is, given an ISL for a service and the-shelf networks and mobile devices. Although we added
a simple device specification, we can generate the UI for that
agents, we did not modify the base software for our net-
service/device pair automatically. An extreme version of this
works, nor did we develop any new networking hardware.
would allow a service to have the same ISL for web use, for
We have learned several lessons that should enable better
touch-tone telephones, and for speech-based control.
future networks, such as the importance of network-interface
5.3 Scoping Access Control power management, the negative impact of half-duplex net-
working, and the importance of augmented infrastructure-
Making services available to visitors raises general secu- based beacons.
rity issues, including those specific to the wireless domain Similarly, we avoided developing our own mobile
[Bro95]. Local services require additional access control,
device, in part in response to the significant effort involved
because we extend local services for remote use. Global with the InfoPad project. However, we view the current set
access control is necessary, but not sufficient; the expected of devices as sufficient only for prototyping, and have high
behavior that environmental changes can only be affected by expectations for the next generation, which should be
people in that environment has been broken. For example, designed with the proxy architecture in mind. We have had
lights should not able to be turned off by a person across the discussion with device manufacturers along these lines.
country. Maintaining this expectation is important when We also dealt only tangentially with the infrastructure
extending existing social metaphors into an environment required for global authentication. The Charon work enables
with controllable objects. proxy-based authentication, and we can restrict access to
We address this by embedding tickets, random fixed- local users via beacon-based tickets, but those both prema-
length bit vectors, in the mobility beacons and requiring the turely assume that a global authentication system is in place.
current ticket to be included in all communications to serv- As such systems are deployed, our architecture extends them
ers. Periodically changing the tickets in an unpredictable to support heterogeneous clients and local services.
way and limiting the scope of the broadcast (e.g., to the local Finally, an important area of ongoing work is fairness
subnet) prevents remote access from nodes on the access and utilization for shared wireless networks such as wireless
control list that are not actually local. This ticket-based LANs. In addition to traditional MAC-layer issues, wireless
exclusion can be overridden by explicitly giving remote par- networks suffer from time-varying network performance per
ticipants the ticket. However, by restricting access by host and little or no mechanisms for collision detection. We
default, we better emulate the existing paradigm. are looking at channel dependent link-scheduling algorithms
5.4 Adaptive Network Services Summary based on class-based queueing to mitigate these effects.
Finally, we did not look at disconnected operation,
In summary, the adaptive network services layer of the instead assuming connectivity of varying quality. We
architecture provides functionality beyond IP dial-tone to believe that disconnected operation is an important capabil-
both roaming and local users. The themes that guide our ity for mobile users; we left it out only because there are sev-
work in this area include: eral major projects that address the issues
• Taking advantage of the availability of non-intrusive [MES95][Kle97][JTK97], and because we believe that those sys-
mobile client devices to allow users to use their tems are complementary to our work.
personal devices in a manner comfortable to them;
6.2 Related Projects
• Making the environment responsive and customizable
via remote-control access to devices and the to the There are at least several hundred useful papers that
services that make the devices useful; and relate to some aspect of the architecture; here we focus only
on broad projects of similar scope. For detailed coverage of
• Utilizing dynamic discovery and reconfiguration at related work in a specific area, please refer to the papers
multiple levels (service availability, service interfaces) listed in the “For More Info” list at the end of the correspond-
to address the inherent variability exposed in mobility- ing section.
enabled environments. The Coda and Odyssey projects at CMU focus on file-
system based support for mobile devices. The Coda system
For more info: localized services [HKSR97][HK97] [MES95] manages file-system consistency across intermittent
and disconnected access. BARWAN did not look at discon-
nected access, although we believe the Coda approach is
largely orthogonal and thus could be supported directly.
Odyssey [NSN+97] originally defined multiple quality levels

16
of file-system objects to support variation in network qual- remote-control interfaces via an ISL, we can dynamically
ity; their current approach adopts our notion of dynamic adapt the user interface to the capabilities of the client
adaptation and distillation (and the use of proxies) to provide device. These techniques give us tremendous flexibility and
both application-aware and application-transparent adapta- are the key to supporting networks and clients that vary by
tion at the file-system level. Much of the rest of the BAR- orders of magnitude across many dimensions.
WAN architecture is complementary, such as overlay Cross-layer Optimization: There are several places
networking and reliable data transport, and in fact there has where we explicitly break the OSI networking model to
been some joint work [NKNS96]. One major distinction is the enable smarter adaptation or better performance. For exam-
service focus of BARWAN, rather than the file-system focus ple, we use physical-layer information to trigger (horizontal)
of Odyssey, which enables not only localized services, but handoffs.
also complex TACC-based services (and protocols) such as A compelling example is the interaction of the transport
the Wingman browser. and link layers in our solutions to reliable data transport over
The InfoPad project [Bre+96][N+96] preceded BARWAN, wireless and asymmetric links. Snoop uses detailed TCP
had some overlap in personnel, and was very influential on knowledge to detect time-outs and duplicate acks, and it sup-
several of our network and application-support elements. presses duplicate acks to the sender to control when the
The InfoPad is a hand-held wireless tablet that depends on sender enters congestion control. Similarly, the ELN mecha-
both high-bandwidth networking (for bitmapped graphics nism allows the transport layer to know that a particular loss
and video) and extensive application support in the infra- was not due to congestion. The control of ack clocking in our
structure. For example, it depends on a modified version of support for asymmetric connections is another example of
X Windows on the server that renders all of the pixels (not controlling the transport layer from the link layer; we reduce
vector graphics) over the wireless connection. Although very acks on the reverse channel and then reconstruct them for
bandwidth intensive, this approach has the benefit of simple smooth flow from legacy TCP senders. We also exploit
low-power hardware, since it requires only simple process- transport-layer information when we use “acks first” sched-
ing on the device. A major distinction is thus our focus on uling, since we have to understand the purpose of the pack-
low-bandwidth links and some processing power on the ets. In all cases, we achieve significantly better performance
devices. We can also view the InfoPad as just another heter- and maintain the end-to-end semantics.
ogeneous device; for example, the video transcoder can con- Finally, we use transport-layer information to control the
vert video streams into InfoPad’s custom VQ format. proxy (essentially the presentation layer). This enables
UCLA’s work on nomadic computing [Kle97] addresses dynamic adaptation and thus maximizes the tradeoff
many of the same issues as BARWAN. In particular, it between quality and performance (response time for HTTP
shares the service focus of BARWAN. It provides strong requests; frame-rate for video streams), even in the presence
support for wide-area data management (predictive caching of varying network conditions.
and data consistency) and disconnected operation. However, Agent-Based Capabilities: To maximize our ability to
it does not (so far) address the issues of overlaid networks, work with legacy clients, servers and TCP stacks, we use
reliable data transport, or scalable complex infrastructure agents within the network infrastructure to add new capabili-
services. The proxy architecture has emerged as fundamental ties or to improve performance. Fundamentally, the role of
to the nomadic computing. these agents is to hide to vagaries of mobility, wireless net-
Rover [JTK97] is a toolkit for developing mobile applica- working and extreme heterogeneity from all of the legacy
tions that support disconnected operation. As with Coda, the servers and infrastructure; the agents make everything look
Rover work is complementary, and we expect to integrate like it is “supposed to”. The alternative is take an end-to-end
the Rover technology into our future work in this area. The approach in which you are allowed to modify all compo-
proxy architecture and network services work simplify the nents, including clients and servers. This has the advantage
infrastructure side of the Rover toolkit. of a potentially better overall solution, but it is nearly impos-
sible to deploy, since it requires upgrading most clients and
6.3 Four Themes Revisited servers.
We finish our discussion by revisiting our four themes. The overlay networking solution uses multiple agents,
Dynamic Adaptation is the general way we deal with one at the home base to forward packets, and one near the
varying network conditions and with client heterogeneity. mobile device to handle low-latency handoffs locally. These
Vertical handoff is a dynamic adaptation in response the agents primarily hide mobility from legacy servers by acting
presence or absence of packets on a particular overlay, while as a level of indirection. The local agent also enables fast
horizontal handoff is an adaptation based on physical-layer handoffs by maintaining state at multiple basestations via
feedback such as signal strength. local multicast.
The proxy architecture is an extreme form of dynamic In the case of transport issues, the agent-based
adaptation: we change the content dynamically depending on approaches usually performed as well or better than the end-
network conditions, device software and hardware capabili- to-end approaches, and provided the critical additional
ties, and user preferences. We demonstrated dynamic distil- advantage of immediate deployment, thus allowing us to
lation for both images and real-time video streams, in both integrate wireless technologies cleanly into the rest of the
cases enabling smooth tradeoffs between quality and perfor- global Internet. The snoop agent hides wireless losses from
mance across a range of devices. Similarly, by defining TCP senders, thus enabling them to work well for wireless

17
links. Similarly, we use a pair of agents to hide significant enables automatic configuration of mobile devices so they
problems with reverse channels in asymmetric links from can exploit local resources, and the remote control function-
TCP, again enabling new levels of performance for those ality makes it possible to control your environment with your
links without modifying all of the servers on the Internet. For personal PDA, even if you’ve never been in the room before.
both acks-first scheduling and shared wireless links, we These are powerful capabilities; we look forward to the day
showed that agents can perform link optimizations across a when they are regularly available to everyone.
collection of connections, which is not possible without a
local presence at the link or with just enhancements to the 8 References
TCP protocol. [AMZ95] E. Amir, S. McCanne and H. Zhang. An Application-
The most powerful agents, of course, are the cluster- Level Video Gateway. In Proc. of ACM Multimedia ’95,
based TACC servers, which can provide mobile users with November 1995.
the combined power of several workstations (even for a sin- [ATT94] AT&T Corporation. WaveLAN: PC/AT Card
gle HTML page). We demonstrated many capabilities that Installation and Operation. AT&T manual, 1994.
are not possible without the proxy, and produced several [Bre+96] E. Brewer et al. The Design of Wireless Portable
applications that depend on tremendous leverage from the Systems [InfoPad]. Proc. of Spring COMPCON ’95,
infrastructure to meet deliver their functionality, most nota- March 1995.
bly the PalmPilot web browser and whiteboard applications. [Bro+96] C. Brooks, M.S. Mazer, S. Meeks and J. Miller.
Even for web browsing from home, the proxy enables 3-7 Application-Specific Proxy Servers as HTTP Stream
times faster downloads and the receipt of (degraded) MBone Transducers. Proc. WWW-4, Boston, May 1996. http://
video. We expect powerful proxies to be fundamental to www.w3.org/pub/Conferences/WWW4/Papers/56.
future internet access. [BSK95] H. Balakrishnan, S. Seshan, and R.H. Katz. Improving
Exploit Soft State: Soft state is state that aids in perfor- Reliable Transport and Handoff Performance in Cellular
mance or adds capabilities, but that is not required for cor- Wireless Networks. ACM Wireless Networks, 1(4),
rectness. Soft state need not be recovered after failures, can December 1995.
be thrown out at any time, and can typically be stale or [BPK97] H. Balakrishnan, V. N. Padmanabhan and R. H. Katz.
inconsistent without violating correctness. In general, most The Effects of Asymmetry on TCP Performance. In
of our agents use soft state to make them simpler and trivi- Proc. of ACM Mobicom ’97, September 1997.
ally fault tolerant. We exploit soft state in all aspects of the [BPK98] H. Balakrishnan, V. N. Padmanabhan and R. H. Katz.
design, and in the few places that we didn’t use it, we either The Effects of Asymmetry on TCP Performance. In
regretted it (overlay networking) or rewrote the subsystem to ACM Mobile Networking (MONET), Special Issue on
Mobile Networking in the Internet, Spring 1998
use soft state (TACC manager).
[BPSK97] H. Balakrishnan, V. N. Padmanabhan, S. Seshan and R.
Fundamentally, soft state goes well with agents because
H. Katz. A Comparison of Mechanisms for Improving
the latter are typically added on to systems that already have
TCP Performance over Wireless Links. IEEE/ACM
a solution for end-to-end data integrity (such as TCP). Thus Transactions on Networking, December 1997.
agents tend to be both optional and not responsible for the [Bro95] D. Brown. Techniques for Privacy and Authentication in
state of the system that they extend. Limiting the agent’s Personal Communication Systems. IEEE Personal
state to soft state is thus not that difficult, and it enables triv- Communications, pp. 6–10, August 1995.
ial fault recovery and scalability. Perhaps more importantly, [CF97] Y. Chawathe and S. Fink. MASH Meets TACC: Top
soft state tends to avoid many difficult issues regarding fault Gun MediaBoard. http://http.cs.berkeley.edu/~yatin/
tolerance and data consistency, thus making the implementa- courses/isvc/report/.
tion of the agents far more simple overall. For example, even [Cox95] D. C. Cox. Wireless Personal Communications: What is
though we use two agents to manage the acks on a asymmet- it? IEEE Personal Communications, pages 20–34, April
ric link, our use of soft state means that either agent (or both) 1995.
can fail without effecting the correctness of the connection. [Dir98] The DirecPC Home Page. http://www.DirecPC.com, 1998.
In fact, they can restart in any or order or not at all and still [FG96] A. Fox and S. Gribble. Security on the Move: Indirect
maintain correctness. Finally, soft state works well for Authentication Using Kerberos, Proceedings of
agents because it focuses on availability rather than consis- MobiCom ’96, November 1996.
tency, which is the opposite of most fault-tolerant systems, [FGBA96] A. Fox, S. Gribble, E. Brewer and E. Amir. Adapting to
such as ACID databases. Network and Client Variability via On-Demand
Dynamic Distillation, Proceedings of ASPLOS-VII,
7 Conclusions October 1996.
[FGCB97] A. Fox, S. Gribble, Y. Chawathe and E. Brewer. Cluster-
The BARWAN project achieved nearly all of its goals: Based Scalable Network Systems, Proceedings of SOSP
we deployed a working network that really is useful. It is ’97. October 1997.
possible to roam among several networks and the perfor- [GB97] S. Gribble and E. Brewer. System Design Issues for
mance of the networks is quite good. The proxy is highly Internet Middleware Services: Deductions from a Large
available and supports thousands of users, several quality Client Trace. Proc. of the USITS ’97, December 1997.
services, and a wide range of mobile devices; two of these [HH94] A. Harter and A. Hopper. A Distributed Location
applications (TranSend and Wingman) have thousands of System for the Active Office. IEEE Network Magazine,
users each. The support for localized network services 8(1), January 1994.

18
[HK97] T. Hodes and R. Katz. “Composable Ad-hoc Mobile [Ses95] S. Seshan. Low Latency Handoffs in Cellular Data
Services for Universal Interaction”, Proceedings of Networks. Ph.D. thesis, University of California at
MobiCom ’97, September 1997. Berkeley, December 1995.
[HKSR97] T. D. Hodes, R. Katz, E. Servan-Schreiber, and L. A. [SGHK96] M. Stemm, P. Gauthier, D. Harada, and R. H Katz.
Rowe. Composable Ad-hoc Mobile Services for Reducing Power Consumption of Network Interfaces in
Universal Interaction. Proc. of The Third ACM/IEEE Hand-Held Devices. In Proc. of the Third Workshop on
International Conference on Mobile Computing. Mobile Multimedia Communications (MoMuC-3),
Budapest, Hungary, September, 1997. September 1996.
[HN97] T. Hodes and M. Newman, rvic: A vic Variant for [SK98] M. Stemm and R. H. Katz. Vertical Handoffs in
Remote Control of Shared Video Monitors, Wireless Overlay Networks. In ACM Mobile
http://http.cs.berkeley.edu/~hodes/rvic/index.html. Networking (MONET), Special Issue on Mobile
[IBM95] IBM Infrared Wireless LAN Adapter Technical Networking in the Internet, Spring 1998.
Reference. IBM Microelectronics - Toronto Lab, 1995. [SMB96] M. A. Schickler, M. S. Mazer, and C. Brooks. Pan-
[JM95] V. Jacobson and S. McCanne. Public Domain Network Browser Support for Annotations and Other Meta-
“Whiteboard”. ftp://ftp.ee.lbl.gov/conferencing/wb . Information on the World Wide Web. Proc. of the Fifth
[JTK97] A. D. Joseph, J. A. Tauber and M. Frans Kaashoek. International World Wide Web Conference, May 1996.
Mobile Computing with the Rover Toolkit. IEEE [SSK97] S. Seshan, M. Stemm, and R. H. Katz. SPAND: Shared
Transactions on Computers: Special issue on Mobile Passive Network Performance Discovery. In Proc. of the
Computing, 46(3). March 1997. First Usenix Symposium on Internet Technologies and
[Kle97] L. Kleinrock. Nomadicity: Anytime, Anywhere in a Systems (USITS ’97). December 1997.
Disconnected World, Mobile Networks and [UCB97] University of California at Berkeley, CS294-6: Internet
Applications, 1(4), pp. 351–357, January 1997. Services, Fall 1997. Class proceedings at http://
[KB96] R. H. Katz and E. A. Brewer. The Case for Wireless www.cs.berkeley.edu/~fox/cs294.
Overlay Networks. In Proc. of the SPIE Multimedia and [VGPK97] J. Veizades, E. Guttman, C. Perkins and S. Kaplan.
Networking Conference (MMNC’96), San Jose, CA, Service Location Protocol, Internet Draft #17, IEFT
January 1996. 1997. draft-ietf-srvloc-protocol-17.txt.
[KG97] M. Kornacker and R. Gilstrap. Group Annotation Using [Wei93] M. Weiser. Some Computer Science Issues in
TACC. http://kemet.berkeley.edu/ratogi/class/cs294-6. Ubiquitous Computing. Communications of the ACM,
[KM97] S. Keshav and S. Morgan. SMART Retransmission: 36(7), July 1993.
Performance with Overload and Random Losses. In
Proc. of INFOCOMM ’97.
[MES95] L. B. Mummert, M. R. Ebling and M. Satyanarayanan.
Exploiting Weak Connectivity for Mobile File Access.
Proc. of the 15th ACM Symposium on Operating
Systems Principles, December 1995.
[Met96] Metricom web page. http://www.metricom.com, 1996.
[N+96] S. Narayanaswamy et al. Application and Network
Support for InfoPad. IEEE Personal Communications,
March 1996.
[NKNS96] G. T. Nguyen, R. H. Katz, B. Noble, and M.
Satyanarayanan. A Trace-Based Approach for
Modelling Wireless Channel Behavior. Proc. of the
Winter Simulation Conference, December 1996.
[NSN+97] B. Noble, M. Satyanarayanan, D. Narayanan, J. E.
Tilton, J. Flinn, and K. Walker. Agile Application-
Aware Adaptation for Mobility. Proceedings of SOSP
’97, St. Malo, France, October 1997.
[Per96] C. Perkins. IP Mobility Support. RFC 2002, October
1996.
[SAG+93] B. N. Schilit, N. Adams, R. Gold, M. Tso, and R. Want.
The PARCTAB Mobile Computing System. In
Proceedings of the Fourth Workshop on Workstation
Operating Systems (WWOS-IV), October 1993.
[SB97] B. Schilit and T. Bickmore. Digestor: Device-
Independent Access to the World Wide Web. Proc. of
WWW-6, Santa Clara, CA, April 1997.
[SBK97] S. Seshan, H. Balakrishnan, and R. H. Katz. Handoffs in
Cellular Wireless Networks: The Daedalus
Implementation and Experience. Kluwer Journal on
Wireless Personal Communications, January 1997.

19