\magnification\magstep1

\def\section#1{\bigskip\noindent{\bf #1}\medskip}
\baselineskip=18pt plus 2pt

%%%%%%%%%%%%%%%% A

\section{A. Cover page}
\centerline{\bf BAA \#90--21}
\centerline{Software Science and Technology: High-Performance
Computing}
\centerline{Efficient Packet Transmission and Reception\footnote*{I
was unclear on the spririt of this assignment.  It seems to me that
the effort required to create a {\it serious} research proposal would
be quite substantial.  A serious proposal would require (among other
things) a well-thought-out research idea, a careful study of
literature in relevant sub-domains, a careful selection and pricing of
relevant equipment, and at least some idea about how long things take
to accomplish.  I felt that the time required to put together such a
proposal was out of the scope of the time I have for this class, so
instead I have put together a mock proposal based on an idea I got
from David Cheriton at Stanford University, and I simply made up
everything having to do with cost or timescale.}}

\centerline{Contact: Ken Duda {\tt <kkkken@athena.mit.edu>}}

%%%%%%%%%%%%%%% B

\section{B. ``One-page'' summary of claims}

Current software technology requires packets bound for a network to be
written in memory three times during transmission, and three times
during reception.  By authorizing the network controller to access
memory shared with the process requesting network services, the copy
operations may be eliminated, substantially improving throughput,
latency, and host performance.  The relative improvement will be much
greater for very fast networks, such as packet-switched fiberoptic
networks, than for slower networks, such as Ethernet; thus, broadband
applications ({\it e.g.,} real-time video) should benefit the most.

\section{C. ``One-page'' summary of deliverables}

Deliverables include: a computer running an operating system and a
netork card using the strategy outlined above; standard network
services implemented using the above strategy (TCP/IP, RPC, OLTP);
performance comparisons with existing systems for both bulk-transfer
(large file transfer and real-time video) and small-transfer (null
RPC).

\section{D. Estimates of cost and time}

\def\divider{\noalign{\vskip 2pt}
&\omit\hrulefill\cr
\noalign{\vskip 2pt}}

\medskip
{\offinterlineskip
\halign{#\hfil\quad & \$\strut \hfil #\cr
\it \hfil Item & \omit\strut \it \hfil Cost\hfil \cr
\noalign{\vskip 2pt\hrule\vskip 2pt}
Laboratory Fees & 5,000.00\cr
Two Sun SparcStations & 20,000.00\cr
Logic Analyzer & 5,000.00\cr
Video Equipment Rental & 1,000.00\cr
Hardware for network and controllers & 5,000.00\cr
Stipend and Funding for two assistants & 150,000.00\cr
\divider
Subtotal & 186,000.00\cr
Overhead & 140,600.00\cr
\divider
Total & 326,600.00\cr}}



\medskip
{\offinterlineskip
\halign{#\hfil\quad &# \strut \hfil\cr
\it\hfil Milestone  & \it \hfil When \cr
\noalign{\vskip 2pt\hrule\vskip 2pt}
Development environment set up, assistants hired&Sept 1993\cr
Network card working (with device driver)&May 1994\cr
Kernel support for packet transmission&Sept 1994\cr
Library for RPC and TCP/IP&Jan 1995\cr
Performance measurements of RPC and TCP/IP taken&May 1995\cr
User-level services (file transfer, remote shell, video) &Aug 1995\cr
Performance comparisons of user-level services taken&Sept 1995\cr}}

\section{F. Statement of Work (SOW)}

Our goal is to develop a working network of machines on which we can
compare the relative performance and functionality of the network
interface proposed above with the standard network interface.  The
network interface is defined to include the network card, its
interface to the host CPU, the kernel code for handling the network
interface, and the interface the kernel provides to user processes.
In order to perform this comparison, we must first actually implement
the proposed network interface, and implement basic network services
on top of the interface.  We anticipate greater improvement in
broadband applications, and thus wish to compare performance over a
variety of applications.

The development portion of the project consists of two major
components: hardware and software.  On the hardware side, two network
boards must be developed that upon receiving a packet transfer it via
DMA into physical addresses preassigned by the kernel, and then signal
the kernel that a packet has been received.  On the software side, a
device driver for these cards must be written, and the kernel must be
modified to give user processes access to a card of this sort
(including modifying the existing network layer to use a card of this
sort for backward-compatibility).  In addition, a library must be
constructed to give applications convenient ways of using this sort of
interface, and then standard network services and test applications
must be implemented using this library.  The library will re-implement
standard networking calls to take advantage of the card's facilities.

During the later parts of this development phase, performance
measurement will take place.  For both network interface types, we
will measure the latency for single packets of various sizes, the
throughput for a contiuous packet stream, the latency of a null RPC
call, the throughput of RPC with large arguments and return values,
and the performance of higher-level applications, such as file
transfer and real-time video.  We will also make the same performance
measurements of systems that use the new card and kernel with
differenet kinds of applications: applications using BSD sockets and
the standard network library, applications using sockets and the new
network library, and applications designed for the new network
interface that take advantage of it directly.

\section{G. Transferable Technology}

A prospective user will be able to install the new network card and
kernel in his Sun workstation and notice no difference.  If existing
programs are re-linked against the new network library, he will enjoy
some enhanced performance (as packets will not have to be copied into
the kernel and then into user-space.)  By taking advantage of the
ability of the network card to write directly into core, new
applications designed for use with the card will enjoy larger
enhancements.

\section{H. Technical Rationale}

If one carefully examines each step in a network packet transmission
in conventional systems, one will see that the following steps are
taken:

1.  The recipient allocates a buffer to hold the packet

2.  The recipient asks its kernel to receive a packet

3.  The sender forms the packet in user space

4.  The sender asks the kernel to send the packet

5.  The kernel copies the packet for transmission

6.  The kernel copies the packet into the network card

7.  The packet is sent over the network

8.  The packet is received in the target network card

9.  The packet is copied into a buffer inside the kernel, 

10.  The kernel decides which process the packet is bound for

11.  The kernel copies the packet into the user process space

12.  The kernel wakes up the user process

13.  The user process interprets the packet

We are proposing a different architecture for dealing with the
communication of processes over a network.  I will now describe this
new architecture in detail, and explain why we expect better
performance from the new architecture.

Under the new archtecture, a network consists of a host address, a
process ID, and a memory address.  When a process wishes to receive
data from some source on the network, it first allocates a buffer to
hold the data.  It then informs its peer across the network of the
{\it address} of this buffer!  Next, it informs the kernel that it is
interested in receiving packets from a certain source into the given
address range; the kernel passes this authorization along to the
network card.  When the packet is sent, the sender will include the
process ID and the address it wants to send to.  The network card
will look up the process ID and address in its table, and, if they are
legal, will write the packet directly into memory using DMA.  (If they
aren't legal the packet is discarded and the kernel is never
notified.)  Then it will notify the kernel that a packet was received
for the given process at the given address and with the received
length.  The kernel will notify the receiving process as appropriate.
Once a packet has been received at a given address, the network card's
table entry authorizing receipt of the packet is deleted from the
network card's table, so that a second packet with the same target
address will not overwrite the first packet.

If an association between network peers is just starting, the
initiator of the association will not know what address to write the
initial packet into.  To handle this special case, a packet may be
addressed to a process ID with an ``unknown'' memory address.  A
server process may start up by requesting that packets addressed to it
with the ``unknown'' address be written into a certain address.  When
this initial packet is received, the server process is notified.
Presumably this packet will contain an address to which the response
should be sent.  The server process will do its work and send the
response to the given address.

Connection-oriented protocols present no fundamental additional
difficulties.  For ease of implementation and understanding,
everything above IP will be implemented in user-space, so the notion
of ``connection'' will exist only in the client.  This may increase
paging activity due to sleeping processes needing to keep their
connections fresh; we will attempt to detect this increase in our
performance measurements, and argue that parts of the protocol may be
movable into the kernel without loss of throughput, eliminating this
extra paging.

For comparison with the steps in conventional systems, the steps in
our system for transmitting a packet are:

1.  The recipient allocates a buffer to hold the packet

2.  The recipient asks its kernel to receive a packet

3.  The kernel notifies the network card that the packet may be
received into the given memory address

4.  The sender asks the kernel to send the packet

5.  The kernel asks the ethernet card to send the packet from the
given memory address

6.  The ethernet card reads the packet out of the user's memory and
puts it on the network

7.  The packet header (containing process ID and memory address) is
decoded by the target network card

8.  The network card looks up the process ID and memory address in its
table and makes sure they are legal

9.  If legal, the card writes the remainder of the packet into that
memory address

10.  The card notifies the kernel that a packet was received for the
given PID at the given address with a given length

11.  The kernel wakes up the receiving process

12.  The receiving process interprets the packet

There are a few problems with this scheme.  First, note that the
memory addresses sent in packets must be physical, because if they
were virtual then the page table for the target process would have to
be installed in the target machine's page table registers at the time
of packet receipt.  A problem arises when the physical page into which
the packet must be received is paged out.  One possible solution is to
have the network card buffer the packet if attempting to write it
causes a page fault.  Another is to only allow processes to receive
packets into special kernel-allocated buffers that are guaranteed to
always be paged in.  The second solution greatly simplifies the
network card's implementation (since under the second solution the
network card will only have to buffer one packet at a time) and may be
feasible for machines with lots of RAM.

\medskip

\noindent{\bf Comparison with ongoing research}
\smallskip

I know of no work going on attempting to optimize network access in
this sort of way.

\section{J. Facilities}

The facilities will be my room in Ashdown dormitory at MIT.  It has a
heater and a supply of electricity.  All equipment I will need will be
purchased through the grant money, namely, the workstations,
networking hardware (cable and transceivers), logic analyzer,
protoboard, EPROM programmer, miscellaneous tools, and parts for the
card.

\section{M. Cost Breakdown}

I have already done exactly this in part D.  No cost sharing is
anticipated.

\section{N. Bibliography}

I do not have exact citations here.  Relevant papers include the
original Ethernet paper from Xerox and papers on broadband network
interfaces.  If I had time for a literature search, I am sure I could
dig up some citations under those categories.

\bye

