Style of Work
In 1983, my first year of graduate school at
Carnegie Mellon University (CMU),
I attended a talk by well known computer scientist
Andy Van Dam
in which he said ``in computer science, if you haven't written the
program you don't know what you're talking about.''
I have taken Van Dam's philosophy as my own.
I am an inventive experimental computer scientist: my goal is to
invent significant new concepts for system design. In general, the
aim is to develop ideas that may have impact within about 2-5 years
after performance of the work. My work focuses on inventing new
designs, developing prototype implementations, and evaluating the
Although there are disadvantages to implementation and it is not
necessarily appropriate for all types of work, I believe that in
``systems'' subfields it is usually desirable, and that one should be
biased toward implementation, for several reasons. The first is that
predicting the impact of a new idea within a system is rarely
straightforward. A large system typically presents many constraints
that may foil an appealing idea. Second, large systems are usually
complex and the interplay of various mechanisms is often surprising.
Similarly, implementation aids in debugging a new idea and exposing
unrecognized assumptions and unconsidered details. Further, an
implementation -- as opposed to a more abstract description of an idea
-- provides a more specific demonstration of the idea and a more
concrete foundation for follow-up work. Finally, an implementation
often eases the reproducibility of results by others.
Upon joining the Columbia faculty in 1988, I abandoned the topic of
my doctoral dissertation
(techniques for incorporating atomic transactions into the operating
system) and started on the new subject of mobile computing. At
the time, portable computers and cheap hardware for wireless digital
data communication were curiosities, and the concept of mobile
computing presented virgin territory. Protocols and systems for
distributed computing were designed on the assumption that computers
did not move, and this assumption was so basic that for all practical
purposes it was impossible for a distributed system to continue
running automatically and normally if some of its constituent
computers changed locations. Relocation would terminate a computation
and require human intervention to reconfigure the system before
restarting. Starting from this point, with no pre-existing principles
for how to build effective mobile computing systems, my research
proceeded in two phases.
In the first phase -- transparent mobile computing -- I investigated
how to design lower layers of distributed computing systems to
hide from upper layers the fact that computers are moving.
This work resulted in new designs for several common and pre-existing
The most prominent example,
is a set of algorithms that allow a
computer to move from one IP network to another without having to
change its underlying IP address. Since the IP address does not
change, movement is invisible to all software above the IP layer,
including the operating system and applications. Other services that
my students and I designed or re-designed for mobile operation
the X11 protocol for remote graphics,
replicated read-only file service,
replicated read-write file service,
remote virtual memory paging.
The second phase of my research investigated how to enable application
programs running on mobile computers to automatically adjust to
changes that may occur in their surrounding environment as a result of
the computer's movement. My research evolved from hiding the
effects of mobility to exposing mobility in a structured manner
because it is not always possible or even desirable to hide the
effects of mobility. For example, it is simple for a mobile computer
to disconnect from a 100Mb LAN and re-connect to a 56Kb phone line or
9.6Kb wide area CDPD wireless service. However, the difference in
network bandwidth, a factor of 10,000, is so vast that it is difficult
to imagine any technique that operates only at a low layer, without
the benefit of knowing the meaning of the network traffic, that can by
itself automatically reduce communication by a factor approaching
10,000 yet still preserve the essential operation and performance of
Accordingly, I initiated work on techniques that permit
automatic adaptation to network heterogeneity.
Heterogeneity may be introduced by movement of a mobile host among
networks with substantially different characteristics. The resulting
solution is a mechanism for inserting and removing programs (called
``filters'') into the middle of client-server connections (even ones
that are already active), and then dynamically controlling filter
behavior. The filters are typically application-specific, and usually
act under control of an application running on a mobile host. They
may drop, delay, re-segment, or transform data moving to and from the
mobile host, making use of application knowledge about the meaning and
purpose of the traffic.
Besides the work described above, I have undertaken a few projects
that do not fit a theme:
How to automatically
transplant completely unmodified device
driver source code from one operating system kernel (Linux) to another
The resulting code was incorporated into both the commercial and
academic versions of the Mach microkernel (maintained by the Open
Software Foundation and the University of Utah, respectively).
OSF software was used the world over.
Whole path lookup for NFS. Standard NFS converts a path name such as
/a/b/c into a file handle for c using three
interactions between the client and file server, one each for
a, b, and c. Whole path lookup is an
optimistic procedure that translates a path into a file handle in a
single interaction almost all the time. The idea of whole path lookup
was later present as part of Sun's work on
WebNFS, a lightweight
version of NFS that was touted as an Internet file system.
A system that I quickly cobbled together
to solve a personal problem
has been used by a few colleagues and I have seen its
main idea -- hierarchical checksums -- appear in other work.
Briefly, the problem was keeping home and school versions of a tree of
files consistent. Hierarchical checksumming performs bottom-up
checksums on both trees. If two directories have identical checksums
it means that everything at and below those directories is identical,
allowing for massive pruning. Assuming few changes are made to the
home tree while away from school, the two trees can be quickly
compared and the master (school) version brought up to date.
Work at AT&T on
prefetching Web pages
won the best paper award at a recent conference. The idea is to
accumulate statistics about many clients' usage of hyperlinks in a
page. When that page is later fetched by a client, the fetching
client is also given the statistics and uses them to decide which of
the page's hyperlinks to prefetch. I implemented this idea in the
Mozilla browser and the CERN httpd proxy and evaluated it against
millisecond-accurate traces that I collected myself.
While on the faculty at Columbia, I graduated five doctoral students,
four of whom were my advisees. A sixth is due to graduate on December
6, 2000. In addition, two students wrote Masters theses with me, and
many others performed more limited research projects. I have worked
with undergraduates who have gone on to doctoral programs at Caltech
(Dan Maskit) and Carnegie Mellon (Jon Nowitz).
Below is a list of the MS and PhD students I have worked with,
including in each case the student's date of graduation, information
about his thesis, and his current employment. Some of these people
have graciously agreed to answer your questions about what it was like
to work with me.
PhD February 1993
``Protocols for Mobile Internetworking''
John's thesis developed the first practical approach to ``Mobile IP.''
Mobile IP is now the subject of an IETF working group and a proposed
standard. Mobile IP allows a mobile host to retain its IP address
even as it moves among networks with different IP network numbers.
John is a Principal Research Staff member at
AT&T Labs -- Research
in Florham Park, NJ.
John does not want his email address embedded in a web page. To send
mail to him, use ID ``ji'' and site ``research.att.com.''
PhD April 1993
``A File System for Mobile Computing''
Carl's thesis developed two ideas that help a mobile file system
client: a ``variable consistency'' approach to replicated file service
and intelligent prefetching. With variable consistency replication,
the idea is to spread server replicas widely; the client then contacts
the closest one. Updates spread throughout the replicas in standard
master-slave fashion. What is distinct about this approach to file
service is that TWO read calls are supported: one that searches the
replicas to return the guaranteed latest value, and one that performs
a faster search but may not return the latest value. The onus of
searching replicas is placed on the read call, where it belongs,
rather than placing the onus on the write call to spread widely a new
value that may or may not be read soon after. Having an ``eager'' as
well as a ``lazy'' read call makes the replica maintenance algorithms
simpler and makes service to a mobile client more efficient. Carl
also developed a system for prefetching that automatically exploits
system-detected patterns of repeate usage; this idea was significantly
expanded in Hui Lei's thesis, described
Carl is a research staff member at
IBM T.J Watson Research Laboratory
in Hawthorne, NY.
Send mail to Carl
PhD December 1994
``Context Aware Software Reconfiguration Supporting Distributed Mobile
Bill's thesis explains why and how to build a scalable notification
service for applications running on or communicating with mobile
Bill is a research staff member at
in Palo Alto, CA.
MS May 1995
``Xmove, A Pseudoserver for X Window Movement''
(paper based on the work)
Xmove addresses the movement of users among computers rather than the
movement of computers among networks. Xmove is an intermediary for
the X11 protocol that intercepts connections between X servers
(software, running on computers with displays, that updates the
display) and X clients (applications that send X commands to servers).
The user can tell Xmove to redirect X commands from one server to
another, thereby allowing the user to move from one display to another
while retaining the state of his windows.
MS August 1995
``Emulation of Linux Device Drivers in Mach 3.0''
(paper based on the work)
In the mid-90s, the [Mach microkernel]
was an interesting research platform but only a few people were using
it; thus, it suffered from a lack of device drivers relative to more
popular systems such as Linux. Shantanu solved this problem by making
changes to Mach to permit a completely unaltered Linux device
driver to be compiled and linked with Mach.
PhD July 1997
``A Proxy Based Filtering Mechanism for the Mobile Environment''
paper based on the work)
As a computer moves among networks, it may encounter situations of
varying bandwidth, bandwidth asymmetry, error rate, security,
and cost. Accordingly, it may be desirable to vary the amount and
nature of the network traffic between a mobile device and its
correspondents, depending on the network conditions available at the
moment to the mobile device. Bruce develops an architecture and
system for doing this: an intermdeiate proxy sits between mobile
device and correspondent host. The mobile device downloads code into
this proxy to control its behavior on a per-protocol or per-connection
basis. The mobile device may also remotely control the actions of the
code; for example, to allow more or fewer frames of an MPEG stream to
be passed through the intermediary.
Bruce is a staff member at
Juno Online Services
Send mail to Bruce
PhD February 1998
``Uncovering and Exploiting the Intrinsic Correlations Between File
paper based on the work)
Hui develops in detail a method for file prefetching and hoarding that
exploits the observed usage patterns of files. Read latency is
reduced up to 35%, while attribute cache and block cache miss rates
are reduced by up to 82% and 46%, respectively.
Hui is a research staff member at
IBM T.J Watson Research Laboratory
in Hawthorne, NY.
Send mail to Hui
PhD expected Fall 2000
``FiST: A File System Component Compiler''
The observation leading to Erez's work on FiST is that including new
file system code into a kernel or porting an existing file system
across operating systems is difficult but, on the other hand, much of
the work is mechanical or at least close enough possibly to be
automated. The solution is to create a file system ``compiler.'' The
compiler takes an abstract description of how a file system should
function and produces code for the target operating system. A system
based on stackable vnodes has been implemented in Solaris, Linux, and
FreeBSD and has been shown to allow significant modifications to a
file system to be easily added at the cost of 5-7% overhead.
Erez also did an MS thesis with me:
MS August 1994
``Automatic Discovery and Hot Replacement of Replicated Read-Only File
(paper based on the work)
The idea behind this work is to continually monitor file system
performance and to switch to a closer replica when performance begins
to fall off. This work explored only read-only replication.
Starting in January 2001, Erez will be Assistant Professor in the
Computer Science department of the State University of New York (SUNY)
at Stony Brook
Send mail to Erez