📄 http:^^www.cs.cornell.edu^info^people^barber^upf-unet^upf.html
字号:
MIME-Version: 1.0
Server: CERN/3.0
Date: Sunday, 01-Dec-96 18:54:21 GMT
Content-Type: text/html
Content-Length: 25954
Last-Modified: Wednesday, 21-Aug-96 19:44:20 GMT
<html><head><title>The U-Net Packet Filter</title><!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><img src = "http://www.cs.cornell.edu/Info/People/barber/upf-unet/switch.gif"><h1>The U-Net Packet Filter: An Extension to U-Net over Fast Ethernet</h1><h2>Masters of Engineering Project</h2><h2>August 20, 1996</h2><b><!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><a href="http://www.cs.cornell.edu/Info/People/barber">Jonathan Barber</a> (<!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><a href=mailto:barber@cs.cornell.edu>barber@cs.cornell.edu</a>)<br><!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><a href="http://www.cs.cornell.edu/Info/People/tve/tve.html">Professor Thorsten von Eicken</a><br><p><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><a href="http://www.cs.cornell.edu/">Department of Computer Science</a><br><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><a href="http://www.cornell.edu">Cornell University</a></b><p><!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><img src = "http://www.cs.cornell.edu/Info/People/barber/upf-unet/sepbar-6.gif"><p></head><p><body><h2>1.0 Abstract</h2>U-Net is high-bandwidth, low-latency network communication protocol that can deliver parallel-computing horsepower to a network of PCs. In this case, the PCs are connected via a fast ethernet switch. In its original implementation, computers connected through U-Net communicated through a simple communication scheme. The U-Net Packet Filter acts as an extension to the original implementation, giving U-Net the capability to communicate using open standards.<p><!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><img src = "http://www.cs.cornell.edu/Info/People/barber/upf-unet/sepbar-6.gif"><p><h1>2.0 Overview</h1>The job of the <i>U-Net Packet Filter (UPF)</i> is to demultiplex in-coming packets to their corresponding U-Net endpoint destinations. It is designed to demultiplex both <i>connection-oriented</i> and <i>connection-less</i> packets, depending on the protocol/field combinations.<p> In the case of connection-oriented packets, a channel specifies an endpoint-to-endpoint connection (i.e. a connection from one process to another). If process A connects to process B, then A can only communicate with B, and B can only communicate with A on that channel. If A wants to communicate with C, then it must open a separate channel.<p>In the case of connection-less packets, program A can open a broadcast or multicast channel. Any other process listening on that channel can receive packets sent from A.<p><!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><img src = "http://www.cs.cornell.edu/Info/People/barber/upf-unet/sepbar-6.gif"><p><h2>3.0 Design Goals</h2>The U-Net Packet Filter was designed with two goals in mind:<p><ol><li>Above all, it has to be fast. The ability to communicate over open standards is useless to U-Net if it can do so only at normal network data-rates.<p><li>The Packet Filter's topology has to be simplistic, and easily expandable. New filters cannot been written in pseudo-assembly and interpreted. New filters must programmed into the existing system, however, the packet filter's simplistic structure allows for a certain degree of creativity on the part of the programmer, thereby easing the task of the programming itself.<p></ol>The subsequent sections in this document discuss in detail the different components and structure of the U-Net Packet Filter, with an eye towards demonstrating that the design goals have been met.<p><!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><img src = "http://www.cs.cornell.edu/Info/People/barber/upf-unet/sepbar-6.gif"><p><h2>4.0 Implementation</h2>The current implementation, as of the date of this document, allows for 4 distinct filter types. They are, Raw U-Net (the simple communication scheme utilized by the original version of U-Net), Raw Ethernet (U-Net purely at the data-link layer), TCP/IP, and UDP/IP.<p> <hr><h3>4.1 Elementary Components</h3>The U-Net Packet Filter is a <i>Directed A-cyclic Graph (DAG)</i>. It is made up of two basic components:<p><ol><li><b>The Cell:</b> this is a data-structure that contains twelve 32-bit word entries. This is the Packet's most basic structure. The cell is used for storing channel information (such as a channel's field values, such as port numbers and addresses), and it is used as a pointer to other cells and hash table. Cells can be chained together to form doubly-linked lists. For complete details and usage information on cells in UPF, <!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><a href = "http://www.cs.cornell.edu/Info/People/barber/upf-unet/cell.html">click here</a>.<p><li><b>The Hash Table:</b> provided with a hashing function, these tables are used to spread out U-Net channels over a range of HASH_SIZE. Each table contains HASH_SIZE pointers to cells. These cells, as already mentioned, can be chained together in a linked-list. The combination of cells and hash-tables creates a hashing data-structure with chaining, which is the way in which hash tables are utilized in the current implementation of UPF.<p> </ol><p><center><b>Figure 1: Elemantary UPF Components</b><br><!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><img src = "http://www.cs.cornell.edu/Info/People/barber/upf-unet/components.gif"></center><p>Together, cells and hash tables are connected together to form a directed a-cyclic graph (DAG). When a packet comes in off of the ethernet wire, each protocol in the composite packet header is broken down into fields. These fields are then compared to information stored in the cells. As matches are found, we follow the appropriate path through the DAG.<p> The next section breaks down the current architecture of the U-Net Packet Filter, and discusses the protocols it currently supports.<hr><p><h3>4.2 Protocol Hierarchy in the U-Net Packet Filter DAG</h3>The current implementation supports 4 protocols, two of which are open standards. The following protocols are broken down has follows:<p><ol><li><b>Raw U-Net:</b> The modified version of U-Net (devtulip.c) is backwards compatible with the original implementation of U-Net. That is, packets can be demultiplexed to Raw U-Net channels based on the following fields:<p><ul><li>U-Net Code<li>U-Net Port number</ul><P><center><b>Figure 2: Raw U-Net Ethernet Header</b><br><!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><img src = "http://www.cs.cornell.edu/Info/People/barber/upf-unet/rawunet.gif"></center><p>These types of channels are not part of the UPF system. In the event that a Raw U-Net channel is detected, the UPF system is by-passed, and the packet is demultiplexed based strictly on the U-Net port number. If the ethernet card is running in promiscuous or multicast mode, then only the U-Net Type and U-Net-Port identify an endpoint/channel. These channels are not guaranteed to be unique.<p><hr><p><li><b>Raw Ethernet:</b> This protocol is similar to the Raw U-Net protocol, in that it is strictly a data-link layer protocol. Packets are demultiplexed to their corresponding endpoint/channel based on the following fields:<p><ul><li>Ethernet Source (Addr)<li>Raw Ethernet Type</ul><center><b>Figure 3: Raw Ethernet Header</b><br><!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><img src = "http://www.cs.cornell.edu/Info/People/barber/upf-unet/raweth.gif"></center><p>The combination of these two fields uniquely specify an endpoint (unless the Source Addr is an ethernet multicast or broadcast address). The ethernet type can be any 16-bit value, provided that it is not a reserved field (e.g. the IP ethernet type is 0x0800, and is a reserved type).<p> In the case where the only open channel's consist of Raw U-Net (not in the DAG) or Raw Ethernet channels, the DAG is merely a linked-list of ETH-TYPE cells (<!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><a href="http://www.cs.cornell.edu/Info/People/barber/upf-unet/cell.html">see the Cell Specification Page</a>).<p> <center><b>Figure 4: Raw Ethernet in the UPF DAG</b><br><!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><img src = "http://www.cs.cornell.edu/Info/People/barber/upf-unet/rawethDAG.gif"></center><p>When a Raw Ethernet Packet is received, fields the ethernet source and raw ethernet type are compared with the corresponding cell values for each element in the linked-list,until a match is found. For the case(s) in which a large number of Raw Ethernet channels are open, performance may be improved by replacing this linked list with a hash table.<p><hr><p><li><b>TCP/IP (Transmission Control Protocol/Internet Protocol):</b><p> This is a composite point-to-point protocol. The outer protocol is IP, and the inner is TCP. I refer to this as a single filter, as only both protocols together identify an endpoint. In reality, they are separate protocols.<p>The combination of the following fields uniquely identifies a TCP/IP endpoint:<p><ul><li> Ethernet Type -- Ethernet Protocol <li> IP Version -- IP Protocol<li> Transmission Protocol -- IP Protocol (specifies TCP Protocol)<li> Destination Port -- TCP Protocol<li> Destination Address -- IP Protocol<li> Source Address -- IP Protocol<li> Source Port -- TCP</ul><center><b>Figure 5: TCP/IP Composite Header</b><br><!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><img src = "http://www.cs.cornell.edu/Info/People/barber/upf-unet/ipheader.gif"></center><p>Notice that fields from three different protocols uniquely identify a channel. This corresponds to a traversal of the packet filter's DAG. UPF is designedto be fast. This means that in the interests of speed, we want to drop a packet from contention as soon as it is realized that the packet will not demultiplex to any endpoint.<p> Of the 7 preceding fields, we know that the packet is not IP if the ethernet type field does not match IP (0x0800). As an optimization, the IP ethernet cell is always located at the head of the Ethernet-level linked-list. Since IP demultiplexing is expensive, this results in just a single ethernet-type check.<p>At this point, we now know the packet is of type IP. At the next level in the DAG, we check the protocol and the IP version number. If the protocol is un-defined (i.e. is not TCP or UDP, ..., in this case TCP), or if the IP version number does not match the filter's IP version number, the packet is dropped. Again, this results in traversing a linked-list of protocol cells, or as its referred to in the source code, IP_PROTO cells, until a match is or isn't found.<p> <center><b>Figure 6: At the IP Protocol Level in the UPF DAG</b><br><!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><img src = "http://www.cs.cornell.edu/Info/People/barber/upf-unet/ipprotoDAG.gif"></center><p>If a match is found, then we descend another level into the DAG. At this point, we drop the packet if the destination port (TCP Protocol), does not exist in the filter. Since there can be as many as 2^16 possible ports, we perform a lookup into a hash table. The hash table itself is connected to the IP_PROTO cell corresponding to the TCP protocol. The hash function is defined within the source code by the function <i>hash_func_port()</i>. Since it is possible for multiple channels to exist on the same <port, protocol> combination, it might be necessary traverse a hash-chain of IP_CHANNEL_HASH cells. These cells contain the destionation port number, and pointer to a Channel hash table.<p><center><b>Figure 7: At the TCP/IP Channel Hash Level in the UPF DAG</b><br><!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><img src = "http://www.cs.cornell.edu/Info/People/barber/upf-unet/ipchanhashDAG.gif"></center><p>The 3 remaining fields, IP Source addr, IP Destination addr, and TCP source port, uniquely identify a TCP channel. A hash function is then used, defined by the function <i>hash_func_chan()</i> in the source code, to hash into a table connected to the IP_CHANNEL_HASH node. Again, there can be more than one node connected to a single index in the hash table. The hash function is meant to spread out the different channel combinations, so that a chain of IP_CHANNEL nodes will not have to be walked.<p><center><b>Figure 8: At the TCP/IP Channel Level in the UPF DAG</b><br><!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><img src = "http://www.cs.cornell.edu/Info/People/barber/upf-unet/ipchannelDAG.gif"></center><p>If a match is found in the IP_CHANNEL linked list, we demultiplex the packet to the corresponding endpoint.<p> In summary, demultiplexing TCP/IP packets requires traversing the DAG through 3 protocols.Note that the current implementation does not support IP fragmentation. This would be a natural extension to TCP/IP, as well as UDP/IP.<p><hr><p><li><b>UDP/IP (User Datagram Protocol):</b><p> Traversal of the DAG for UDP/IP is nearly identical to that of TCP/IP. The difference between the two protocols is that UDP/IP can be connection-less, while TCP/IP is always connection-oriented. This means that its possible to establish not only unicast channels, but multicast and broadcast channels as well.<p>Traversal of the DAG for UDP/IP requires the same seven fields that were used in TCP/IP. The difference is that at channel setup time, a unicast, multicast, or broadcast channel type can be selected. If the user creates a unicast channel, then traversal of the DAG occurs exactly as it did for TCP/IP, except that the transmission protocol is now UDP.<p> Choosing to open a multicast channel results in creating a new level of the DAG. Graph traversal proceeds as it did for TCP/IP, all the way to the IP_CHANNEL node. In UDP, the IP_CHANNEL node contains an x_cast field, which is set to either UNICAST, MCAST, or BCAST. If the field is MCAST, then we descend a level to a linked list of IP_MCAST cells.<p>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -