\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 }} %%%%%%%%%%%%%%% 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