NFS Tracing By Passive Network Monitoring

Matt Blaze

Department of Computer Science Princeton University mab@cs.princeton.edu

ABSTRACT

Traces of filesystem activity have proven to be useful for a wide variety of
purposes, ranging from quantitative analysis of system behavior to
trace-driven simulation of filesystem algorithms. Such traces can be
difficult to obtain, however, usually entailing modification of the
filesystems to be monitored and runtime overhead for the period of the
trace. Largely because of these difficulties, a surprisingly small number of
filesystem traces have been conducted, and few sample workloads are
available to filesystem researchers.

This paper describes a portable toolkit for deriving approximate traces of
NFS [1] activity by non-intrusively monitoring the Ethernet traffic to and
from the file server. The toolkit uses a promiscuous Ethernet listener
interface (such as the Packetfilter[2]) to read and reconstruct NFS-related
RPC packets intended for the server. It produces traces of the NFS activity
as well as a plausible set of corresponding client system calls. The tool is
currently in use at Princeton and other sites, and is available via
anonymous ftp.

1. Motivation

Traces of real workloads form an important part of virtually all analysis of
computer system behavior, whether it is program hot spots, memory access
patterns, or filesystem activity that is being studied. In the case of
filesystem activity, obtaining useful traces is particularly challenging.
Filesystem behavior can span long time periods, often making it necessary to
collect huge traces over weeks or even months. Modification of the
filesystem to collect trace data is often difficult, and may result in
unacceptable runtime overhead. Distributed filesystems exa cerbate these
difficulties, especially when the network is composed of a large number of
heterogeneous machines. As a result of these difficulties, only a relatively
small number of traces of Unix filesystem workloads have been conducted,
primarily in computing research environments. [3], [4] and [5] are examples
of such traces.

Since distributed filesystems work by transmitting their activity over a
network, it would seem reasonable to obtain traces of such systems by
placing a "tap" on the network and collecting trace data based on the
network traffic. Ethernet[6] based networks lend themselves to this approach
particularly well, since traffic is broadcast to all machines connected to a
given subnetwork. A number of general-purpose network monitoring tools are
avail able that "promiscuously" listen to the Ethernet to which they are
connected; Sun's etherfind[7] is an example of such a tool. While these
tools are useful for observing (and collecting statistics on) specific types
of packets, the information they provide is at too low a level to be useful
for building filesystem traces. Filesystem operations may span several
packets, and may be meaningful only in the context of other, previous
operations.

Some work has been done on characterizing the impact of NFS traffic on
network load. In [8], for example, the results of a study are reported in
which Ethernet traffic was monitored and statistics gathered on NFS
activity. While useful for understanding traffic patterns and developing a
queueing model of NFS loads, these previous stu dies do not use the network
traffic to analyze the file access traffic patterns of the system, focusing
instead on developing a statistical model of the individual packet sources,
destinations, and types.

This paper describes a toolkit for collecting traces of NFS file access
activity by monitoring Ethernet traffic. A "spy" machine with a promiscuous
Ethernet interface is connected to the same network as the file server. Each
NFS-related packet is analyzed and a trace is produced at an appropriate
level of detail. The tool can record the low level NFS calls themselves or
an approximation of the user-level system calls (open, close, etc.) that
triggered the activity.

We partition the problem of deriving NFS activity from raw network traffic
into two fairly distinct subprob lems: that of decoding the low-level NFS
operations from the packets on the network, and that of translating these
low-level commands back into user-level system calls. Hence, the toolkit
consists of two basic parts, an "RPC decoder" (rpcspy) and the "NFS
analyzer" (nfstrace). rpcspy communicates with a low-level network
monitoring facility (such as Sun's NIT [9] or the Packetfilter [2]) to read
and reconstruct the RPC transactions (call and reply) that make up each NFS
command. nfstrace takes the output of rpcspy and reconstructs the sys tem
calls that occurred as well as other interesting data it can derive about
the structure of the filesystem, such as the mappings between NFS file
handles and Unix file names. Since there is not a clean one-to-one mapping
between system calls and lower-level NFS commands, nfstrace uses some simple
heuristics to guess a reasonable approximation of what really occurred.

1.1. A Spy's View of the NFS Protocols

It is well beyond the scope of this paper to describe the protocols used by
NFS; for a detailed description of how NFS works, the reader is referred to
[10], [11], and [12]. What follows is a very brief overview of how NFS
activity translates into Ethernet packets.

An NFS network consists of servers, to which filesystems are physically
connected, and clients, which per form operations on remote server
filesystems as if the disks were locally connected. A particular machine can
be a client or a server or both. Clients mount remote server filesystems in
their local hierarchy just as they do local filesystems; from the user's
perspective, files on NFS and local filesystems are (for the most part)
indistinguishable, and can be manipulated with the usual filesystem calls.

The interface between client and server is defined in terms of 17 remote
procedure call (RPC) operations. Remote files (and directories) are referred
to by a file handle that uniquely identifies the file to the server. There
are operations to read and write bytes of a file (read, write), obtain a
file's attributes (getattr), obtain the contents of directories (lookup,
readdir), create files (create), and so forth. While most of these
operations are direct analogs of Unix system calls, notably absent are open
and close operations; no client state information is maintained at the
server, so there is no need to inform the server explicitly when a file is
in use. Clients can maintain buffer cache entries for NFS files, but must
verify that the blocks are still valid (by checking the last write time with
the getattr operation) before using the cached data.

An RPC transaction consists of a call message (with arguments) from the
client to the server and a reply mes sage (with return data) from the server
to the client. NFS RPC calls are transmitted using the UDP/IP connection
less unreliable datagram protocol[13]. The call message contains a unique
transaction identifier which is included in the reply message to enable the
client to match the reply with its call. The data in both messages is
encoded in an "external data representation" (XDR), which provides a
machine-independent standard for byte order, etc.

Note that the NFS server maintains no state information about its clients,
and knows nothing about the context of each operation outside of the
arguments to the operation itself.

2. The rpcspy Program

rpcspy is the interface to the system-dependent Ethernet monitoring
facility; it produces a trace of the RPC calls issued between a given set of
clients and servers. At present, there are versions of rpcspy for a number
of BSD-derived systems, including ULTRIX (with the Packetfilter[2]), SunOS
(with NIT[9]), and the IBM RT running AOS (with the Stanford enet filter).

For each RPC transaction monitored, rpcspy produces an ASCII record
containing a timestamp, the name of the server, the client, the length of
time the command took to execute, the name of the RPC command executed, and
the command- specific arguments and return data. Currently, rpcspy
understands and can decode the 17 NFS RPC commands, and there are hooks to
allow other RPC services (for example, NIS) to be added reasonably easily.

The output may be read directly or piped into another program (such as
nfstrace) for further analysis; the for mat is designed to be reasonably
friendly to both the human reader and other programs (such as nfstrace or
awk).

Since each RPC transaction consists of two messages, a call and a reply,
rpcspy waits until it receives both these components and emits a single
record for the entire transaction. The basic output format is 8 vertical-bar
separated fields:

timestamp | execution-time | server | client | command-name | arguments |
reply-data

where timestamp is the time the reply message was received, execution-time
is the time (in microseconds) that elapsed between the call and reply,
server is the name (or IP address) of the server, client is the name (or IP
address) of the client followed by the userid that issued the command,
command-name is the name of the particular program invoked (read, write,
getattr, etc.), and arguments and reply-data are the command dependent
arguments and return values passed to and from the RPC program,
respectively.

The exact format of the argument and reply data is dependent on the specific
command issued and the level of detail the user wants logged. For example, a
typical NFS command is recorded as follows:

690529992.167140 | 11717 | paramount | merckx.321 | read |
{"7b1f00000000083c", 0, 8192} | ok, 1871

In this example, uid 321 at client "merckx" issued an NFS read command to
server "paramount". The reply was issued at (Unix time) 690529992.167140
seconds; the call command occurred 11717 microseconds earlier. Three
arguments are logged for the read call: the file handle from which to read
(represented as a hexadecimal string), the offset from the beginning of the
file, and the number of bytes to read. In this example, 8192 bytes are
requested starting at the beginning (byte 0) of the file whose handle is
"7b1f00000000083c". The command completed successfully (status "ok"), and
1871 bytes were returned. Of course, the reply message also included the
1871 bytes of data from the file, but that field of the reply is not logged
by rpcspy.

rpcspy has a number of configuration options to control which hosts and RPC
commands are traced, which call and reply fields are printed, which Ethernet
interfaces are tapped, how long to wait for reply messages, how long to run,
etc. While its primary function is to provide input for the nfstrace program
(see Section 3), judi cious use of these options (as well as such programs
as grep, awk, etc.) permit its use as a simple NFS diag nostic and
performance monitoring tool. A few screens of output give a surprisingly
informative snapshot of current NFS activity; we have identified quickly
using the program several problems that were otherwise difficult to
pinpoint. Similarly, a short awk script can provide a breakdown of the most
active clients, servers, and hosts over a sampled time period.

2.1. Implementation Issues

The basic function of rpcspy is to monitor the network, extract those
packets containing NFS data, and print the data in a useful format. Since
each RPC transaction consists of a call and a reply, rpcspy maintains a
table of pending call packets that are removed and emitted when the matching
reply arrives. In normal operation on a reasonably fast workstation, this
rarely requires more than about two megabytes of memory, even on a busy net
work with unusually slow file servers. Should a server go down, however, the
queue of pending call messages (which are never matched with a reply) can
quickly become a memory hog; the user can specify a maximum size the table
is allowed to reach before these "orphaned" calls are searched out and
reclaimed.

File handles pose special problems. While all NFS file handles are a fixed
size, the number of significant bits varies from implementation to
implementation; even within a vendor, two different releases of the same
operating system might use a completely different internal handle format. In
most Unix implementations, the handle contains a filesystem identifier and
the inode number of the file; this is sometimes augmented by additional
information, such as a version number. Since programs using rpcspy output
generally will use the handle as a unique file identifier, it is important
that there not appear to be more than one handle for the same file.
Unfortunately, it is not sufficient to simply consider the handle as a
bitstring of the maximum handle size, since many operating systems do not
zero out the unused extra bits before assigning the handle. Fortunately,
most servers are at least consistent in the sizes of the handles they
assign. rpcspy allows the user to specify (on the command line or in a
startup file) the handle size for each host to be monitored. The handles
from that server are emitted as hexadecimal strings truncated at that
length. If no size is specified, a guess is made based on a few common
formats of a reasonable size.

It is usually desirable to emit IP addresses of clients and servers as their
symbolic host names. An early ver sion of the software simply did a
nameserver lookup each time this was necessary; this quickly flooded the
network with a nameserver request for each NFS transaction. The current
version maintains a cache of host names; this requires a only a modest
amount of memory for typical networks of less than a few hundred hosts. For
very large networks or those where NFS service is provided to a large number
of remote hosts, this could still be a potential problem, but as a last
resort remote name resolution could be disabled or rpcspy configured to not
translate IP addresses.

UDP/IP datagrams may be fragmented among several packets if the datagram is
larger than the maximum size of a single Ethernet frame. rpcspy looks only
at the first fragment; in practice, fragmentation occurs only for the data
fields of NFS read and write transactions, which are ignored anyway.

3. nfstrace: The Filesystem Tracing Package

Although rpcspy provides a trace of the low-level NFS commands, it is not,
in and of itself, sufficient for obtaining useful filesystem traces. The
low-level commands do not by themselves reveal user-level activity. Furth
ermore, the volume of data that would need to be recorded is potentially
enormous, on the order of megabytes per hour. More useful would be an
abstraction of the user-level system calls underlying the NFS activity.

nfstrace is a filter for rpcspy that produces a log of a plausible set of
user level filesystem commands that could have triggered the monitored
activity. A record is produced each time a file is opened, giving a summary
of what occurred. This summary is detailed enough for analysis or for use as
input to a filesystem simulator.

The output format of nfstrace consists of 7 fields:

timestamp | command-time | direction | file-id | client | transferred | size

where timestamp is the time the open occurred, command-time is the length of
time between open and close, direc tion is either read or write (mkdir and
readdir count as write and read, respectively). file-id identifies the
server and the file handle, client is the client and user that performed the
open, transferred is the number of bytes of the file actually read or
written (cache hits have a 0 in this field), and size is the size of the
file (in bytes).

An example record might be as follows:

690691919.593442 | 17734 | read | basso:7b1f00000000400f | frejus.321 | 0 |
24576

Here, userid 321 at client frejus read file 7b1f00000000400f on server
basso. The file is 24576 bytes long and was able to be read from the client
cache. The command started at Unix time 690691919.593442 and took 17734
microseconds at the server to execute.

Since it is sometimes useful to know the name corresponding to the handle
and the mode information for each file, nfstrace optionally produces a map
of file handles to file names and modes. When enough information (from
lookup and readdir commands) is received, new names are added. Names can
change over time (as files are deleted and renamed), so the times each
mapping can be considered valid is recorded as well. The mapping infor
mation may not always be complete, however, depending on how much activity
has already been observed. Also, hard links can confuse the name mapping,
and it is not always possible to determine which of several possible names a
file was opened under.

What nfstrace produces is only an approximation of the underlying user
activity. Since there are no NFS open or close commands, the program must
guess when these system calls occur. It does this by taking advantage of the
observation that NFS is fairly consistent in what it does when a file is
opened. If the file is in the local buffer cache, a getattr call is made on
the file to verify that it has not changed since the file was cached.
Otherwise, the actual bytes of the file are fetched as they are read by the
user. (It is possible that part of the file is in the cache and part is not,
in which case the getattr is performed and only the missing pieces are
fetched. This occurs most often when a demand-paged executable is loaded).
nfstrace assumes that any sequence of NFS read calls on the same file issued
by the same user at the same client is part of a single open for read. The
close is assumed to have taken place when the last read in the sequence
completes. The end of a read sequence is detected when the same client reads
the beginning of the file again or when a timeout with no reading has
elapsed. Writes are handled in a similar manner.

Reads that are entirely from the client cache are a bit harder; not every
getattr command is caused by a cache read, and a few cache reads take place
without a getattr. A user level stat system call can sometimes trigger a
getattr, as can an ls -l command. Fortunately, the attribute caching used by
most implementations of NFS seems to eliminate many of these extraneous
getattrs, and ls commands appear to trigger a lookup command most of the
time. nfstrace assumes that a getattr on any file that the client has read
within the past few hours represents a cache read, otherwise it is ignored.
This simple heuristic seems to be fairly accurate in practice. Note also
that a getattr might not be performed if a read occurs very soon after the
last read, but the time threshold is generally short enough that this is
rarely a problem. Still, the cached reads that nfstrace reports are, at
best, an estimate (generally erring on the side of over-reporting). There is
no way to determine the number of bytes actually read for cache hits.

The output of nfstrace is necessarily produced out of chronological order,
but may be sorted easily by a post-processor.

nfstrace has a host of options to control the level of detail of the trace,
the lengths of the timeouts, and so on. To facilitate the production of very
long traces, the output can be flushed and checkpointed at a specified inter
val, and can be automatically compressed.

4. Using rpcspy and nfstrace for Filesystem Tracing

Clearly, nfstrace is not suitable for producing highly accurate traces;
cache hits are only estimated, the timing information is imprecise, and data
from lost (and duplicated) network packets are not accounted for. When such
a highly accurate trace is required, other approaches, such as modification
of the client and server kernels, must be employed.

The main virtue of the passive-monitoring approach lies in its simplicity.
In [5], Baker, et al, describe a trace of a distributed filesystem which
involved low-level modification of several different operating system
kernels. In contrast, our entire filesystem trace package consists of less
than 5000 lines of code written by a single programmer in a few weeks,
involves no kernel modifications, and can be installed to monitor multiple
heterogeneous servers and clients with no knowledge of even what operating
systems they are running.

The most important parameter affecting the accuracy of the traces is the
ability of the machine on which rpcspy is running to keep up with the
network traffic. Although most modern RISC workstations with reasonable
Ethernet interfaces are able to keep up with typical network loads, it is
important to determine how much informa tion was lost due to packet buffer
overruns before relying upon the trace data. It is also important that the
trace be, indeed, non-intrusive. It quickly became obvious, for example,
that logging the traffic to an NFS filesystem can be problematic.

Another parameter affecting the usefulness of the traces is the validity of
the heuristics used to translate from RPC calls into user-level system
calls. To test this, a shell script was written that performed ls -l, touch,
cp and wc commands randomly in a small directory hierarchy, keeping a record
of which files were touched and read and at what time. After several hours,
nfstrace was able to detect 100% of the writes, 100% of the uncached reads,
and 99.4% of the cached reads. Cached reads were over-reported by 11%, even
though ls com mands (which cause the "phantom" reads) made up 50% of the
test activity. While this test provides encouraging evidence of the accuracy
of the traces, it is not by itself conclusive, since the particular workload
being monitored may fool nfstrace in unanticipated ways.

As in any research where data are collected about the behavior of human
subjects, the privacy of the individu als observed is a concern. Although
the contents of files are not logged by the toolkit, it is still possible to
learn something about individual users from examining what files they read
and write. At a minimum, the users of a mon itored system should be informed
of the nature of the trace and the uses to which it will be put. In some
cases, it may be necessary to disable the name translation from nfstrace
when the data are being provided to others. Commercial sites where filenames
might reveal something about proprietary projects can be particularly
sensitive to such concerns.

5. A Trace of Filesystem Activity in the Princeton C.S. Department

A previous paper[14] analyzed a five-day long trace of filesystem activity
conducted on 112 research worksta tions at DEC-SRC. The paper identified a
number of file access properties that affect filesystem caching perfor
mance; it is difficult, however, to know whether these properties were
unique artifacts of that particular environment or are more generally
applicable. To help answer that question, it is necessary to look at similar
traces from other computing environments.

It was relatively easy to use rpcspy and nfstrace to conduct a week long
trace of filesystem activity in the Princeton University Computer Science
Department. The departmental computing facility serves a community of
approximately 250 users, of which about 65% are researchers (faculty,
graduate students, undergraduate researchers, postdoctoral staff, etc), 5%
office staff, 2% systems staff, and the rest guests and other "external"
users. About 115 of the users work full-time in the building and use the
system heavily for electronic mail, netnews, and other such communication
services as well as other computer science research oriented tasks (editing,
compiling, and executing programs, formatting documents, etc).

The computing facility consists of a central Auspex file server (fs) (to
which users do not ordinarily log in directly), four DEC 5000/200s (elan,
hart, atomic and dynamic) used as shared cycle servers, and an assortment of
dedicated workstations (NeXT machines, Sun workstations, IBM-RTs, Iris
workstations, etc.) in indi vidual offices and laboratories. Most users log
in to one of the four cycle servers via X window terminals located in
offices; the terminals are divided evenly among the four servers. There are
a number of Ethernets throughout the building. The central file server is
connected to a "machine room network" to which no user terminals are
directly connected; traffic to the file server from outside the machine room
is gatewayed via a Cisco router. Each of the four cycle servers has a local
/, /bin and /tmp filesystem; other filesystems, including /usr, /usr/local,
and users' home directories are NFS mounted from fs. Mail sent from local
machines is delivered locally to the (shared) fs:/usr/spool/mail; mail from
outside is delivered directly on fs.

The trace was conducted by connecting a dedicated DEC 5000/200 with a local
disk to the machine room net work. This network carries NFS traffic for all
home directory access and access to all non-local cycle-server files
(including the most of the actively-used programs). On a typical weekday,
about 8 million packets are transmitted over this network. nfstrace was
configured to record opens for read and write (but not directory accesses or
individual reads or writes). After one week (wednesday to wednesday),
342,530 opens for read and 125,542 opens for write were recorded, occupying
8 MB of (compressed) disk space. Most of this traffic was from the four
cycle servers.

No attempt was made to "normalize" the workload during the trace period.
Although users were notified that file accesses were being recorded, and
provided an opportunity to ask to be excluded from the data collection, most
users seemed to simply continue with their normal work. Similarly, no
correction is made for any anomalous user activity that may have occurred
during the trace.

5.1. The Workload Over Time

Intuitively, the volume of traffic can be expected to vary with the time of
day. Figure 1 shows the number of reads and writes per hour over the seven
days of the trace; in particular, the volume of write traffic seems to
mirror the general level of departmental activity fairly closely.

An important metric of NFS performance is the client buffer cache hit rate.
Each of the four cycle servers allocates approximately 6MB of memory for the
buffer cache. The (estimated) aggregate hit rate (percentage of reads served
by client caches) as seen at the file server was surprisingly low: 22.2%
over the entire week. In any given hour, the hit rate never exceeded 40%.
Figure 2 plots (actual) server reads and (estimated) cache hits per hour
over the trace week; observe that the hit rate is at its worst during
periods of the heaviest read activity.

Past studies have predicted much higher hit rates than the aggregate
observed here. It is probable that since most of the traffic is generated by
the shared cycle servers, the low hit rate can be attributed to the large
number of users competing for cache space. In fact, the hit rate was
observed to be much higher on the single-user worksta tions monitored in the
study, averaging above 52% overall. This suggests, somewhat
counter-intuitively, that if more computers were added to the network (such
that each user had a private workstation), the server load would decrease
considerably. Figure 3 shows the actual cache misses and estimated cache
hits for a typical private works tation in the study.

Thu 00:00  Thu 06:00  Thu 12:00  Thu 18:00  Fri 00:00  Fri 06:00  Fri 12:00
Fri 18:00 Sat 00:00 Sat 06:00 Sat 12:00 Sat 18:00 Sun 00:00 Sun 06:00 Sun
12:00 Sun 18:00 Mon 00:00 Mon 06:00 Mon 12:00 Mon 18:00 Tue 00:00 Tue 06:00
Tue 12:00 Tue 18:00 Wed 00:00 Wed 06:00 Wed 12:00 Wed 18:00

1000

2000

3000

4000

5000

6000

Reads/Writes per hour

Writes

Reads (all)

Figure 1 - Read and Write Traffic Over Time

5.2. File Sharing

One property observed in the DEC-SRC trace is the tendency of files that are
used by multiple workstations to make up a significant proportion of read
traffic but a very small proportion of write traffic. This has important
implications for a caching strategy, since, when it is true, files that are
cached at many places very rarely need to be invalidated. Although the
Princeton computing facility does not have a single workstation per user, a
similar metric is the degree to which files read by more than one user are
read and written. In this respect, the Princeton trace is very similar to
the DEC-SRC trace. Files read by more than one user make up more than 60% of
read traffic, but less than 2% of write traffic. Files shared by more than
ten users make up less than .2% of write traffic but still more than 30% of
read traffic. Figure 3 plots the number of users who have previously read
each file against the number of reads and writes.

5.3. File "Entropy"

Files in the DEC-SRC trace demonstrated a strong tendency to "become"
read-only as they were read more and more often. That is, the probability
that the next operation on a given file will overwrite the file drops off
shar ply in proportion to the number of times it has been read in the past.
Like the sharing property, this has implications for a caching strategy,
since the probability that cached data is valid influences the choice of a
validation scheme. Again, we find this property to be very strong in the
Princeton trace. For any file access in the trace, the probability that it
is a write is about 27%. If the file has already been read at least once
since it was last written to, the write probability drops to 10%. Once the
file has been read at least five times, the write probability drops below
1%. Fig ure 4 plots the observed write probability against the number of
reads since the last write.

Thu 00:00  Thu 06:00  Thu 12:00  Thu 18:00  Fri 00:00  Fri 06:00  Fri 12:00
Fri 18:00 Sat 00:00 Sat 06:00 Sat 12:00 Sat 18:00 Sun 00:00 Sun 06:00 Sun
12:00 Sun 18:00 Mon 00:00 Mon 06:00 Mon 12:00 Mon 18:00 Tue 00:00 Tue 06:00
Tue 12:00 Tue 18:00 Wed 00:00 Wed 06:00 Wed 12:00 Wed 18:00

1000

2000

3000

4000

5000

Total reads per hour

Cache Hits (estimated)

Cache Misses (actual)

Figure 2 - Cache Hits and Misses Over Time

6. Conclusions

Although filesystem traces are a useful tool for the analysis of current and
proposed systems, the difficulty of collecting meaningful trace data makes
such traces difficult to obtain. The performance degradation introduced by
the trace software and the volume of raw data generated makes traces over
long time periods and outside of comput ing research facilities particularly
hard to conduct.

Although not as accurate as direct, kernel-based tracing, a passive network
monitor such as the one described in this paper can permit tracing of
distributed systems relatively easily. The ability to limit the data
collected to a high-level log of only the data required can make it
practical to conduct traces over several months. Such a long term trace is
presently being conducted at Princeton as part of the author's research on
filesystem caching. The non-intrusive nature of the data collection makes
traces possible at facilities where kernel modification is impracti cal or
unacceptable.

It is the author's hope that other sites (particularly those not doing
computing research) will make use of this toolkit and will make the traces
available to filesystem researchers.

7. Availability

The toolkit, consisting of rpcspy, nfstrace, and several support scripts,
currently runs under several BSD-derived platforms, including ULTRIX 4.x,
SunOS 4.x, and IBM-RT/AOS. It is available for anonymous ftp over the
Internet from samadams.princeton.edu, in the compressed tar file
nfstrace/nfstrace.tar.Z.

Thu 00:00  Thu 06:00  Thu 12:00  Thu 18:00  Fri 00:00  Fri 06:00  Fri 12:00
Fri 18:00 Sat 00:00 Sat 06:00 Sat 12:00 Sat 18:00 Sun 00:00 Sun 06:00 Sun
12:00 Sun 18:00 Mon 00:00 Mon 06:00 Mon 12:00 Mon 18:00 Tue 00:00 Tue 06:00
Tue 12:00 Tue 18:00 Wed 00:00 Wed 06:00 Wed 12:00 Wed 18:00 0

100

200

300

Reads per hour

Cache Hits (estimated)

Cache Misses (actual)

Figure 3 - Cache Hits and Misses Over Time - Private Workstation

0 5 10 15 20

n (readers)

0

20

40

60

80

100

% of Reads and Writes used by > n users

Reads

Writes

Figure 4 - Degree of Sharing for Reads and Writes

0 5 10 15 20

Reads Since Last Write

0.0

0.1

0.2

P(next operation is write)

Figure 5 - Probability of Write Given >= n Previous Reads

8. Acknowledgments

The author would like to gratefully acknowledge Jim Roberts and Steve Beck
for their help in getting the trace machine up and running, Rafael Alonso
for his helpful comments and direction, and the members of the pro gram
committee for their valuable suggestions. Jim Plank deserves special thanks
for writing jgraph, the software which produced the figures in this paper.

9. References

[1] Sandberg, R., Goldberg, D., Kleiman, S., Walsh, D., & Lyon, B. "Design
and Implementation of the Sun Net work File System." Proc. USENIX, Summer,
1985.

[2] Mogul, J., Rashid, R., & Accetta, M. "The Packet Filter: An Efficient
Mechanism for User-Level Network Code." Proc. 11th ACM Symp. on Operating
Systems Principles, 1987.

[3] Ousterhout J., et al. "A Trace-Driven Analysis of the Unix 4.2 BSD File
System." Proc. 10th ACM Symp. on Operating Systems Principles, 1985.

[4] Floyd, R. "Short-Term File Reference Patterns in a UNIX Environment,"
TR-177 Dept. Comp. Sci, U. of Rochester, 1986.

[5] Baker, M. et al. "Measurements of a Distributed File System," Proc. 13th
ACM Symp. on Operating Systems Principles, 1991.

[6] Metcalfe, R. & Boggs, D. "Ethernet: Distributed Packet Switching for
Local Computer Networks," CACM July, 1976.

[7] "Etherfind(8) Manual Page," SunOS Reference Manual, Sun Microsystems,
1988.

[8] Gusella, R. "Analysis of Diskless Workstation Traffic on an Ethernet,"
TR-UCB/CSD-87/379, University Of California, Berkeley, 1987.

[9] "NIT(4) Manual Page," SunOS Reference Manual, Sun Microsystems, 1988.

[10] "XDR Protocol Specification," Networking on the Sun Workstation, Sun
Microsystems, 1986.

[11] "RPC Protocol Specification," Networking on the Sun Workstation, Sun
Microsystems, 1986.

[12] "NFS Protocol Specification," Networking on the Sun Workstation, Sun
Microsystems, 1986.

[13] Postel, J. "User Datagram Protocol," RFC 768, Network Information
Center, 1980.

[14] Blaze, M., and Alonso, R., "Long-Term Caching Strategies for Very Large
Distributed File Systems," Proc. Summer 1991 USENIX, 1991.

Matt Blaze is a Ph.D. candidate in Computer Science at Princeton University,
where he expects to receive his degree in the Spring of 1992. His research
interests include distributed systems, operating systems, databases, and
programming environments. His current research focuses on caching in very
large distributed filesystems. In 1988 he received an M.S. in Computer
Science from Columbia University and in 1986 a B.S. from Hunter College. He
can be reached via email at mab@cs.princeton.edu or via US mail at Dept. of
Computer Science, Princeton University, 35 Olden Street, Princeton NJ
08544.