http:^^www.cs.cornell.edu^info^people^barber^upf-unet^upf.html

This data set contains WWW-pages collected from computer science departments of various universities

<center>
<b>Figure 9:  At the UDP/IP Mulitcast Level in the UPF DAG</b><br>
<!WA20><!WA20><!WA20><!WA20><!WA20><!WA20><!WA20><!WA20><!WA20><!WA20><!WA20><!WA20><img src = "http://www.cs.cornell.edu/Info/People/barber/upf-unet/multicastDAG.gif"></center>
<p>

Each node in this linked list corresponding to an IP_CHANNEL with the 
same address information, but with pointers to different channels.  In the 
event that a multicast IP_CHANNEL is matched, then we walk the entire 
IP_MCAST linked list, and demultiplex at each IP_MCAST cell.<p>

If the IP_CHANNEL node is of type BCAST, then we must demultiplex to 
every active channel on this port (dest_port).  This results in a traversal of 
every hash-chain for every index in the hash table connected to the 
IP_CHANNEL_HASH node.  The packet is then demultiplexed to every 
unicast and multicast channel open on the port.  If another broadcast channel 
is encountered, it is ignored (since a broadcast is already taking place).<p>

Multicast channels result in demultiplexing to many channels.  This involves 
copying the entire packet into multiple regions of user memory, for as many 
multicast channels that are open.  Broadcast channels result in even poorer 
performance, since the packet must be demultiplexed to every open channel
on the port.<p> 

In general, multicast and broadcast channels may be useful, but they incur a 
severe performance overhead.
</ul>

<hr>
<p>

<h3>4.3  Wild-Card Channels in IP</h3>

Both TCP/IP and UDP/IP composite protocols support wild-card channels.   
In order to demultiplex to an endpoint, the minimal requirements specify 
that the IP ethernet type, the IP Version number, the transport protocol, and a 
destination port must be specified.  The remaining fields, IP destination 
address, IP source address, and the source port can remain un-specified (they 
are declared as a WILD during channel creation).  The combination of 3 
wild-card fields results in seven distinct wild card priority levels, which are 
illustrated below.<p>

<center>
<b>Figure 10:  IP Channel Hash Table Priority Levels</b><br>
<!WA21><!WA21><!WA21><!WA21><!WA21><!WA21><!WA21><!WA21><!WA21><!WA21><!WA21><!WA21><img src = "http://www.cs.cornell.edu/Info/People/barber/upf-unet/hashprior.gif"></center>
<p>

The combination of only a WILD IP source address forms the highest 
priority, while the combination of all WILDS creates the lowest priority.<p>  

Wildcard channels will only pick up packets if there is no matching channel 
from the next-highest priority level.  This functionality is built into 
<i>hash_func_chan()</i>.  Each IP_CHANNEL hash table is partitioned into 
HASH_ENTRIES - 7 indexed hash buckets.  During graph traversal on 
packet reception, if a packet cannot be demultiplexed via the indexed hash 
chain, then we traverse each priority level on the corresponding destination 
port.  If a matching wild-card channel is found, UPF demultiplexes on that 
channel, and graph traversal ends.  If not, then UPF continues searching each 
next lowest priority level until they are all exhausted, at which time the 
packet can be dropped.<p>

Note that UDP Multicast and Broadcast channels are implemented as wild-card 
channels.  Since the channels are by definition connection-less, the IP source 
address and source port fields are WILD.  The down-side of this setup is that 
matching a multicast or broadcast channel requires exactly 3 hash misses (1 
for the missed index, and 2 for the preceding wild-card priority levels).  If a 
U-Net parallel program were to rely heavily on IP multicast or broadcast, this 
scheme may require alteration to boost performance.<p>

<!WA22><!WA22><!WA22><!WA22><!WA22><!WA22><!WA22><!WA22><!WA22><!WA22><!WA22><!WA22><img src = "http://www.cs.cornell.edu/Info/People/barber/upf-unet/sepbar-6.gif"><p>

<h2>5.0  Using UPF with U-Net, Benchmarks, and Demonstration 
Programs</h2>

You can obtain a copy of the UPF U-Net source tree, by saving 
<!WA23><!WA23><!WA23><!WA23><!WA23><!WA23><!WA23><!WA23><!WA23><!WA23><!WA23><!WA23><a href = "http://www.cs.cornell.edu/Info/People/barber/upf-unet/upf-unet.tar.gz">this link</a>.  The 
UPF code is designed to run on a Linux system over Fast Ethernet.  However, 
it should be extremely portable to any U-Net system running over Fast 
Ethernet.  This version, has been tested and bench-marked on Linux 1.3.71 
using the U-Net kernel patch (
<!WA24><!WA24><!WA24><!WA24><!WA24><!WA24><!WA24><!WA24><!WA24><!WA24><!WA24><!WA24><a href = "http://www.cs.cornell.edu/Info/Projects/U-Net/release-docs/install.html">see the U-Net supporting documentation</a>).<p>  

The source tree contains the following items:<p>
<ul>
<li>The source code for the U-Net Packet Filter Extension (./dev-tulip/upf.*)<p>

<li>The modified U-Net device driver (./dev-tulip/devtulip.*) for the SMC tulip
Fast Ethernet Card.<p>

<li>A User-level interface library to U-Net (./libunet/libunet.*) and some UPF 
user-level interface routines for creating channels (./libunet/conversion.*)<p>

<li>A Program that demonstrates the functionality of UPF U-Net (./test/
complex.c)<p>

<li> Several bench-marking Programs to minimum latency (pingpong_*).  
The completions "*" stand 
for "unet", "eth", and "ip", for Raw Unet, Raw Ethernet, and IP (TCP), 
respectively.  These programs can also be found under the ./test directory.<p>

<li>f) The supporting documentation (this document) can found in the 
directory ./docs .<p>
</ul>
<!WA25><!WA25><!WA25><!WA25><!WA25><!WA25><!WA25><!WA25><!WA25><!WA25><!WA25><!WA25><img src = "http://www.cs.cornell.edu/Info/People/barber/upf-unet/sepbar-6.gif"><p>


<h2>6.0  Performance Benchmarks</h2>
The U-Net Packet Filter was evaluated using a 133Mhz Pentium and a 90Mhz Pentium, 
connected to a Fast Ethernet Switch.  The programs pingpong_unet, pingpong_eth, 
and pingpong_ip, were used to test the roundtrip times for sending messages
using Raw Unet, Raw Ethernet, and TCP/IP, respectively.  1000 forty-byte packets 
were sent per test.  The following results were taken from several runs.<p>
<ul>
<li>Roundtrip time for Raw-Unet:  90.55 us/message
<p>
<li>Roundtrip time for Raw-Ethernet:  94.30 us/message
<p>
<li>Roundtrip time for TCP/IP:  109.50 us/message
<p>	
</ul>

Raw-Ethernet performed 4% slower than Raw-Unet.  TCP/IP performed 17% slower than Raw-Unet,
and 13% slower than Raw-Ethernet.<p>

Raw-Ethernet's performance was about as expected.  Traversal of the DAG is not free,
and requires some cycles. TCP/IP's performance is a little disappointing, especially since
the channel test was connection-oriented, and was the only channel open during testing.  
However, the significant performance drain could be partially attributed to the
hash lookups implemented with the IP filter.  
In order to demultiplex to a TCP/IP channel, a packet must 
traverse through two hash-table lookups.  In its current implementation, both 
hashing functions use a modulo operator.  The modulo of the hash function is taken against
the number of available hash buckets.  The use of the modulo operator incurs a large
expense, and might explain a significant portion of TCP/IP's performance drain.<p>

One way the hash functions can be improved would be to replace the modulo 
operations with an alternative similar operation, 
in order to hash a packet into one of the available hash buckets. 
Rather than use modulo, we could logically <b>and</b> the result of the hash 
function with a mask corresponding to the <b>log (base 2)</b> 
of the size of the hash table.  This would perform a function similar to the 
modulo operation while enormously reducing the
computational expense of the operation.<p>

There are undoubtably numerous optimizations one can make to the packet filter
to enhance performance.  This is left as future work.<p>

<!WA26><!WA26><!WA26><!WA26><!WA26><!WA26><!WA26><!WA26><!WA26><!WA26><!WA26><!WA26><img src = "http://www.cs.cornell.edu/Info/People/barber/upf-unet/sepbar-6.gif"><p>

<h2>7.0  How to Go About Adding a New Filter to UPF</h2>

Each filter is some combination of cells and hash tables connected together.  
In meeting the second design goal, the integration of a new filter to UPF is 
meant to be modular.  Each module requires at least 3 routines.<p>
<ol>
<li><b>add_Protocol():</b> a routine to dynamically add a channel of this prototype 
to the DAG. If the filter has not been installed for this channel type, then the 
filter is also installed.  If the add_Protocol() routine fails, then the channel 
creation up to the point of the error must be un-done.<p>

<li><b>find_Protocol():</b> this routine should be very fast!  Its responsible for 
demultiplexing packets to their endpoints.<p>

<li><b>deactivate_Protocol():</b> this routine dynamically removes a channel from 
the DAG, and de-allocates any memory associated with the channel.  If the 
channel is the last channel of its protocol, then the entire protocol is 
deactivated. This routine is important for long-running processes, where channels 
are created and destroyed based on run-time conditions.  Its important that all 
memory be recycled and accounted for.  This routine is not as important for 
short-running programs, such as benchmarks, since the 
<i>upf_shutdown()</i> routine will de-activate the entire DAG data-structure.<p> 
</ol>

The current implementation supports 4 different filters:  Raw Ethernet, IP, 
TCP, and UDP.  For each segmented protocol, there are exactly 3 essential 
routines (see the source code). That is, the aforementioned 3 routines exists for 
every module.  Actually, there is only one find_Protocol in the UPF system 
(<i>upf_findchannel()</i>).  However, this routine is broken up into C case statements, 
essentially breaking down the task of demultiplexing composite 
headers by protocols.<p>  

The designer of a new filter should feel free to define there own cell types, as 
is necessitated by the new filter.  The designer should feel free to modify the 
actual cell structure, if will improve the overall packet filter design, 
and can also define new hash functions as is needed.<p>
<!WA27><!WA27><!WA27><!WA27><!WA27><!WA27><!WA27><!WA27><!WA27><!WA27><!WA27><!WA27><img src = "http://www.cs.cornell.edu/Info/People/barber/upf-unet/sepbar-6.gif"><p>

<h2>8.0  Memory Management</h2>

All memory allocatation in the UPF system is chained together off of a 
pointer on the tulip-device structure.  As new cells and hash-tables are allocated, 
a new "wastebucket" structure is added to a garbage collecting list of 
wastebuckets.  Each wastebucket points towards the allocated structure.  Each 
structure in turn points back to the corresponding waste bucket.  A call to 
<i>upf_shutdown()</i> results in a traversal to each wastebucket.  At each bucket, 
the data structure it points to is de-allocated.  Since each structure points to its 
corresponding wastebucket, a call to <i>upf_deactivate()</i> results in proper 
maintenance of the watebucket linked-list.
<p>
<!WA28><!WA28><!WA28><!WA28><!WA28><!WA28><!WA28><!WA28><!WA28><!WA28><!WA28><!WA28><img src = "http://www.cs.cornell.edu/Info/People/barber/upf-unet/sepbar-6.gif"><p>

<h2>9.0  Other Possible Extensions to UPF</h2>

Througout this document, some possible extensions to UPF have been mentioned.  
In this section, we will discuss a few more.<p>

The current implementation of UPF handles multicast and broadcast channels.  
However, in order to properly join a multicast group, a process needs access 
to an IP multicast to Ethernet address resolver.  The de facto way of doing 
this now is via IGMP.  Therefore, the addition of an IGMP filter to UPF might 
be a good idea.<p>

If a group of U-Net processes were to need to dynamically need to create new IP channels,
then they would also require a way to resolve straight ethernet to IP address translations.
The addition of the <i>Address Resolution Protocol (ARP)</i> filter to UPF 
would also make a logical extension.<p>

In general, as many extensions can be made to UPF as is required by the needs
of the U-Net user(s)<p> 
<!WA29><!WA29><!WA29><!WA29><!WA29><!WA29><!WA29><!WA29><!WA29><!WA29><!WA29><!WA29><img src = "http://www.cs.cornell.edu/Info/People/barber/upf-unet/sepbar-6.gif"><p>

<h2>10.0  Conclusions</h2>

The attempt to create a packet filter that can be used
with U-Net was successful.  In doing so, I believe that our original design goals were met. 
This is, however, a beginning.  There is still a lot work that must be done in
developing both U-Net, and the U-Net Packet Filter.  Particulary in 
the case of UPF, performance can be improved.  Improvements to the current
hashing implementation, and tweaks to the source code in general will 
probably boost overall perforance of the filters.<p>

<!WA30><!WA30><!WA30><!WA30><!WA30><!WA30><!WA30><!WA30><!WA30><!WA30><!WA30><!WA30><img src = "http://www.cs.cornell.edu/Info/People/barber/upf-unet/sepbar-6.gif"><p>

<h2>11.0  Acknowledgments</h2>

I would like to thank the following individuals for their advice, guidance, and 
suggestions in designing and developing UPF:<p>
<ul>
<li>Gerry Toll
<li>Werner Vogels
<li>Anindya Basu
<li>Theodore Wong
<li>Professor Thorsten von Eicken.
</ul>
<!WA31><!WA31><!WA31><!WA31><!WA31><!WA31><!WA31><!WA31><!WA31><!WA31><!WA31><!WA31><img src = "http://www.cs.cornell.edu/Info/People/barber/upf-unet/sepbar-6.gif"><p>

<h2>12.0  References</h2>
<ul>

<li> Mary L. Bailey, Burra Gopal, Michael A. Pagels, Larry L. Peterson, 
Prasenjit Sarkar, "PathFinder:  A Pattern -Based Packet Classifier", 
Proceedings of the First Symposium on Operating Systems Design and 
Implementation, Usenix Association, November, 1994.<p>

<li> Thorsten von Eicken, Anindya Basu, Vineet Buch, and Wernel Vogels, 
"<!WA32><!WA32><!WA32><!WA32><!WA32><!WA32><!WA32><!WA32><!WA32><!WA32><!WA32><!WA32><a href="http://www.cs.cornell.edu/Info/Projects/U-Net/sosp.ps">
U-Net:  A User-Level Network Interface for Parallel and Distributed 
Computing></a>", Draft for SOSP-95, Cornell University, August, 1995.<p>

<li> Dawson R. Engler, M Frans. Kaashoek, "DPF:  Fast, Flexible Message 
Demultiplexing using Dynamic Code Generation", Association for 
Computing Machinery, Inc., 1996.<p> 

<li> Kamran Husain, Tim Parker, "Linux Unleashed", Sams Publishing,
Indianapolis, 1995.

<li> Chris Maeda, Brian N. Bershad, "Protocol Service Decomposition for 
High-Performance Networking", Carnegie Mellon University.<p>

<li> Steven McCane and Van Jacobson, "The BSD Packet Filter:  A new 
Architecture for User-level Packet Capture", Lawrence Berkeley Laboratory, 
December, 1992.<p>

<li> Matt Welsh, "<!WA33><!WA33><!WA33><!WA33><!WA33><!WA33><!WA33><!WA33><!WA33><!WA33><!WA33><!WA33><a href = "http://www.ddj.com/ddj/1995/1995.05/welsh.htm">
Implementing Loadable Kernel Modules for Linux; Loading 
and unloading kernel modules on a running system</a>", Dr. Jobb's Journal, 
1995.<p>

<li> Matt Welsh, Thorsten von Eicken, "
<!WA34><!WA34><!WA34><!WA34><!WA34><!WA34><!WA34><!WA34><!WA34><!WA34><!WA34><!WA34><a href="http://www.cs.cornell.edu/Info/Projects/U-Net">
U-Net: Protected, User-Level Networking Interface</a>",
 Cornell University, March, 1996.<p>

<li> Gary R. Wright, W. Richard Stevens, "TCP/IP Illustrated, Volume 1", 
Addison-Wesley Publishing Company, New York, 1995.<p>

<li>Masonobu Yuhura, Chris Maeda, Brian N. Bershad, J. Eliot B. Moss, 
"Deultiplexing for Multiple Endpoints and Large Messages", Carnegie 
Mellon University.<p>

</body>
</html>