Electrical computers and digital processing systems: multicomput – Computer-to-computer data modifying
Reexamination Certificate
2000-02-15
2004-09-07
Burgess, Glenton B. (Department: 2153)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data modifying
C717S152000
Reexamination Certificate
active
06789127
ABSTRACT:
TECHNICAL FIELD
This invention relates generally to networking and more particularly to recognition of portion of a network packet at a network interface.
BACKGROUND OF THE INVENTION
Networking software is difficult to construct. One reason for this difficulty is that the physical on-the-wire representation of a network packet is not the same as the logical structure of the protocol data carried by the packet. So, a programmer must write interface code, usually as low level C, that understands the grammar of a packet and also performs necessary byte-order and alignment adjustments. Also, domain-specific information about the packet structure must often be coded at multiple locations in the system. The implementation of interface code, therefore, becomes a cumbersome and error-prone process.
Networking code in a system must interface with bare hardware in a network device, and at the same time implement complicated real-time algorithms. Generally, low-level data manipulation requirements and an emphasis on high performance have limited the choice of an implementation language to C. As a result, the development, testing, and deployment of new protocols is typically a slow and expensive process.
Motivated by this problem, significant research and effort have been directed to the development of systematic software architectures and languages for constructing networking software, usually by addressing a specific aspect of the complexity of networking code. One approach tries to better express the modular structure and composition of protocol layers. Another approach tries to better express the reactive control within each layer. A further approach emphasizes the verification aspect.
An additional aspect of the complexity of networking code comprises the low-level processing that takes place at the interfaces between the wire representation of a network packet and the protocol code in a host machine. This low-level processing typically involves data marshaling and unmarshaling, and packet classification (i.e., filtering) based on values extracted from the wire representation. The commonality in these tasks is that their implementation must take into account the physical on-the-wire layout of the logical protocol data. To allow interoperability, the physical formats usually are independent of any given machine's architecture. The physical formats typically pack data together as tightly as possible, to minimize the overhead per unit of actual content, for the header.
One can, for illustrative purposes, consider the interface tasks in a firewall implementation such as Linux (v2.0.32). The following Example 1 shows an abstracted form of code in Linux networking module (net/ipv4).
ip_fw_chk(struct iphdr *ip) {
struct tcphdr *tcp =
(struct tcphdr *)((_32 *)ip + ip→ihl);
int offset =
ntohs(ip→frag_off) & IP_OFFSET;
. . .
switch (ip→protocol) {
case IPPROTO_TCP:
if (!offset) {
src_port = utohs(tcp→source);
dst-port = ntohs(tcp→dst);
. . .
Example 1 first computes the starting address of an IP packet's payload into the variable tcp, by adding the size of the header (field ih
1
) to the start of the packet. Example 1 then computes the offset of the present IP fragment into the variable offset. As will be understood by those skilled in the art, a long payload may be transmitted by IP as a series of IP fragments, each of which contains a segment of the original payload, and an indication of those offset of the segment in the original payload.
In Example 1, the macro ntohs converts a network byte order representation to the host byte order representation for a 16-bit quantity. If the protocol in the payload is TCP and the offset is zero (first fragment), Example 1 extracts the source and destination port numbers from the TCP header. Subsequent code (not shown) implements specific firewall policies based on this extracted and other information, as will be understood by those skilled in the art.
The style of programming interface tasks of Example 1 has several drawbacks. For instance, a programmer must explicitly encode the layout of an IP packet using pointer arithmetic and bit operations. Further, the programmer must explicitly encode, using conditionals, the correlation between the protocol field's value of IPPROTO_TCP and the payload being a TCP packet. Also, the programmer must remember to convert, at all appropriate places, multi-byte numeric quantities between the network byte order and the host byte order. To put this burden in perspective, endianness related macros hton* and ntoh* appear together about 300 times in the net/ipv4 of the Linux implementation (v2.0.32). Each occurrence of such cumbersome programming, increases the possibility of coding error in offsets, sizes, correlations, or endianness.
As will be understood by those skilled in the art, interface tasks are pervasive in networking code. In the core protocol implementation, interface tasks occur in each layer of a protocol stack at input functions (such as ip_receive and tcp_receive for IP and TCP) and output functions (such as the corresponding ip_send and tcp_send). Interface tasks also occur in the implementation of increasingly important system services such as network monitoring, accounting, and security.
One example of such an implementation comprises a packet filter. A packet filter demultiplexes the incoming packet to a user-level process, depending on the filter specified by the process. Essentially, filter specifications parse the packet in the general style of Example 1. One notable difference from Example 1, is that filter specifications normally are byte-codes for the packet filter's virtual machine. Furthermore, hierarchical packet formats exist in contexts other than Internet protocols, giving rise to similar interface programming problems.
The programming style of Example 1 also raises concerns with respect to software engineering. For example, the same information of how to parse a packet, is encoded at multiple sites in a system, when that information should ideally be factored out (the “write once” principle). Moreover, there is no system-wide, formal description of the packet format. Instead, the packet format is hard coded at each instance of interface code. This disadvantageously precludes use of automated techniques (such as model-checking) for verifying an implementation of a protocol or service against a specification.
It would be desirable were “types” in a programming language employed to encode the description of a packet. For example, in the Standard ML programming language, one might tentatively express the logic of Example 1 using the code fragment of the following Example 2.
case (#payload ip) of
TCP {source, dst, . . . } =>
if ((#offset ip) = 0) then
. . .
The syntax #field var in Example 2 comprises field selection from a record. The term on the left of→ comprises a pattern, here matching the datatype TCP. In contrast to Example 1, the programmer in Example 2 need not explicitly interpret the wire format.
Although Example 2 simplifies one aspect programming, there are compelling reasons why protocol code is not written this way. First, marshaling and unmarshaling between the high-level data type and the wire format would be prohibitively expensive. Second, if a protocol layer needs to export a uniform, composable interface, one cannot assign a type to the payload because the set of possible data types that the interface must match, is unknown.
Turning to C code, C aggregate types (structs and unions) do not incur as high an overhead cost as Example 2 in terms of marshaling and unmarshaling between the high-level data type and the wire format. This is because in C, one can cast a void* buffer to any other pointer type, and vice versa. Nevertheless, software applications typically need to perform some adjustments before using a value as a primitive type, because of possible mismatches of alignment and byte order between a host machine's format and t
Chandra Satish
McCann Peter James
Burgess Glenton B.
Flynn Kimberly
Lucent Technologies - Inc.
LandOfFree
Preparation for network interface recognition of network... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Preparation for network interface recognition of network..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Preparation for network interface recognition of network... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3224063