Electrical computers and digital processing systems: multicomput – Computer-to-computer protocol implementing – Computer-to-computer data framing
Reexamination Certificate
2000-04-28
2004-03-30
Wiley, David (Department: 2143)
Electrical computers and digital processing systems: multicomput
Computer-to-computer protocol implementing
Computer-to-computer data framing
C370S394000
Reexamination Certificate
active
06714985
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to computer networks and, more particularly, to efficient reassembly of data packets in an intermediate station of a computer network.
BACKGROUND OF THE INVENTION
A computer network is a geographically distributed collection of interconnected communication media for transporting data between entities. An entity may consist of any device, such as a host or end station, that sources (i.e., transmits) and/or receives network messages over the communication media. Many types of computer networks are available, with the types ranging from local area networks (LANs) to wide area networks (WANs). The end stations, which may include personal computers or workstations, typically communicate by exchanging discrete messages, such as frames or packets, of data according to predefined protocols. In this context, a protocol consists of a set of rules defining how the stations interact with each.
Computer networks may be further interconnected by an intermediate station, such as a switch or router, having a plurality of ports that may be coupled to the networks. For example, a switch may be utilized to provide a “switching” function for transferring information between a plurality of LANs at high speed. Typically, the switch operates at the data link layer of a communications protocol stack (layer 2) in accordance with the IEEE 802.1D standard to receive a data packet at a source port that originated from a sending entity and forward that packet to at least one destination port for transfer to a receiving entity.
On the other hand, a router may be used to interconnect LANs executing different LAN standards and/or to provide higher level functionality than is typically provided by the switch. Routers typically operate at the network layer (layer 3) of a communications protocol stack, such as the Internet communications architecture protocol stack. The primary network layer protocol of the Internet architecture is the Internet protocol (IP) that provides internetwork routing and that relies on transport protocols for end-to-end reliability. An example of such a transport protocol is the Transmission Control protocol (TCP) contained within a transport layer (layer 4) of the Internet architecture. The term TCP/IP is commonly used to refer to the Internet architecture; the TCP/IP architecture is well known and described in
Computer Networks
, 3
rd
Edition,” by Andrew S. Tanenbaum, published by Prentice-Hall (1996).
It is generally common to configure switches that operate at layer
3
of the communications protocol stack and, in fact, switches may be further configured with the capability to examine information contained within a layer 4 header of a packet. This trend may lead to higher layer (“layer 4/7”) switches that are capable of rendering decisions (e.g., forwarding and routing decisions) by analyzing higher layer (e.g., application layer 7) data. In order to perform such higher layer decision operations, the switch must be capable of fragmenting a packet to examine the information contained in its higher layer headers and then reassembling the packet prior to forwarding it to at least one of its destination ports. In the context of a TCP/IP networking environment, the fragmentation and reassembly procedure is well known and described in detail in the
Internet Protocol, Request for Comments
(RFC) 791, by Information Sciences Institute University of Southern California (1981), which disclosure is hereby incorporated by reference.
Fragmentation of an IP datagram (hereinafter referred to as a packet) is also necessary if the LAN standards associated with the source and destination entities are dissimilar (e.g., Ethernet and Token Ring). In this case, the switch may need to alter the format of the packet so that it may be received by the destination entity. For example, if a packet originates in a network that allows a large packet size and traverses one or more links or local networks that limit the packet to a smaller size, the switch interconnecting the networks must fragment the IP packet. According to RFC 791, IP fragmentation apportions an IP packet into an arbitrary number of fragments that can be later reassembled.
FIG. 1
is a schematic block diagram of an IP packet
100
comprising an IP header portion
110
and a payload/data portion
150
. The IP header
110
comprises a version field
102
that indicates the format of the IP header, an Internet header length (IHL) field
104
that indicates the length of the Internet header and a type of service (TOS) field
106
that provides an indication of parameters of a desired quality of service. An IP total length field
108
specifies the length of the IP packet including the IP header and payload/data, while an IP identification field
110
specifies an identifying value assigned by the sending entity to aid in assembling the fragments of the packet.
The IP header further includes a more fragment (MF) flag
112
, an IP fragment offset field
114
that specifies the placement of the fragment within the IP packet and a time to live (TTL) field
116
that indicates a maximum time the packet is allowed to remain in the network. A protocol field
118
indicates the next level protocol used in the payload/data portion
150
of the packet, while a header checksum field
120
provides a checksum on only the IP header. The IP header further includes a source address field
122
containing the IP source address of the sending entity and a destination address field
124
containing the IP destination address of the receiving entity, along with an options field
126
and a padding field
128
.
To fragment an IP packet, an intermediate system (e.g., a switch) creates two or more new IP fragments and copies the contents of a portion of the IP header fields from the original packet into each of the IP headers of the fragments. The receiving entity of the fragments uses the contents of the IP identification field
110
to ensure that fragments of different packets are not mixed. That is, the identification field
110
is used to distinguish the fragments of one packet from those of another. The IP fragment offset field
114
informs the receiving entity about the position of a fragment in the original packet. The contents of the fragment offset field and the IP total length field
108
of each fragment determine the portion of the original packet covered by the fragment. The MF flag
112
indicates (e.g., when reset) the last fragment. The originating host of a complete IP packet sets the IP identification field
110
to a value that is unique for the source/destination address pair and protocol (e.g., TCP, UDP) for the time the packet will be active in the network. The originating host of the complete packet also sets the MF flag
112
to, e.g., zero and the IP fragment offset field
114
to zero.
The IP fragmentation and reassembly procedure is typically not performed by intermediate stations, but rather by host end stations in a network. For those intermediate stations (switches) that implement the procedure, the functions are typically performed in software using general-purpose processors. The amount of processing required to identify information inside an IP packet is substantial and a general-purpose processor may not have an architecture that is optimized to efficiently perform such processing. Moreover software implementation of IP packet reassembly introduces a critical bottleneck in packet processing operations at the switch.
In an IP network environment, higher layer (e.g., layer
4
/
7
) switches must reassemble fragments traversing the network into the original packet before processing the packet. To reassemble the fragments of an IP packet, the switch or host end station typically pre-allocates a buffer and then combines fragments having a similar 4-tuple arrangement comprising {IP identification, IP source, IP destination and IP protocol} values. Reassembly of the fragments is performed by placing the data portion of each fragment in a relative position indicated by th
Edsall Thomas J.
Gai Silvano
Malagrino Dante
Cesari and McKenna LLP
Cisco Technology Inc.
Collins Scott M.
Wiley David
LandOfFree
Method and apparatus for efficiently reassembling fragments... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for efficiently reassembling fragments..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for efficiently reassembling fragments... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3260613