Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2001-04-05
2003-10-21
Alam, Shahid Al (Department: 2172)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C709S232000, C709S236000
Reexamination Certificate
active
06636859
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates in general to data processing and, in particular, to data processing system communication. Still more particularly, the present invention relates to a data processing system, method and program product for reassembling fragmented datagrams.
2. Description of the Related Art
The Internet can generally be defined as a worldwide collection of heterogeneous communication networks and associated gateways, bridges and routers that all employ the TCP/IP (Transport Control Protocol/Internet Protocol) suite of protocols to communicate data packets between a source and one or more destinations. As is well known to those skilled in the art, the TCP/IP suite of protocols corresponds to layers 3 and 4 (the network and transport layers, respectively) of the seven-layer International Organization for Standardization Open Systems Interconnection (ISO/OSI) reference model, which provides a convenient framework for discussing communication protocols. The ISO/OSI reference model further includes physical and link layers (layers 1 and 2, respectively) below the network and transport layers, and session, presentation, and application layers (layers 5 through 7, respectively) above the network and transport layers.
In communicating TCP/IP datagrams between devices over the Internet (or other networks), the maximum transmission unit (MTU) size of the various interfaces through which datagrams are communicated may differ. Accordingly, during output of a datagram, the sending IP layer checks if a data gram can be sent unfragmented. If so, the sending IP layer outputs the datagram through its interface unfragmented. However, if the sending EP layer determines the datagram cannot be transmitted unfragmented because the datagram size exceeds the interface's MTU, the sending IP layer disassembles the datagram into fragments smaller than its interface's MTU and outputs the fragments. During transmission, these fragments may be subject to further fragmentation by routers along the path to the recipient.
When the fragments of the datagram are received by the intended recipient, the receiving IP layer at the recipient must compile the original datagram from the received fragments. Because the recipient does not necessarily receive the fragments sequentially and may receive duplicate fragments, the receiving IP layer needs some mechanism to buffer received fragments and reassemble them to form a datagram. In the prior art, this mechanism is implemented as a single reassembly queue for all of the IP layer, as described in Chapter 10 of Stevens,
TCP/IP Illustrated Volume
2, which is incorporated herein by reference as background material.
The present invention recognizes that the use of a single reassembly queue by all of the IP layer undesirably limits communication performance. For example, in a symmetric multiprocessor (SMP) computer system, such as those commonly employed as e-commerce servers and the like, a large number of processes may be receiving numerous fragments belonging to different datagrams. Thus, many processes may desire to access the reassembly queue at the same time. However, to ensure the data integrity of the single reassembly queue under these conditions, access by the processes to the single reassembly queue is serialized by a lock that can be owned by only one process at a time. Contention for ownership of the lock can therefore severely degrade performance, particularly under high traffic conditions.
SUMMARY OF THE INVENTION
The present invention overcomes the foregoing and additional shortcomings in the art by providing an improved data processing system, method and program product for reassembling fragmented datagrams utilizing multiple reassembly queues that can be accessed in parallel by multiple processes.
In accordance with the present invention, a plurality of fragments of a plurality of datagrams are received by a recipient data processing system. In response to receipt of the plurality of fragments, a plurality of processes concurrently access a reassembly data structure to store the plurality of fragments, such that the plurality of datagrams are incrementally reassembled from the plurality of fragments. In one embodiment, the reassembly data structure can be implemented as a list containing a plurality of reassembly queues that each contain one or more queue entries for reassembling a respective datagram. Data integrity of the reassembly data structure can be maintained by associating a respective one of a plurality of locks with each of the plurality of reassembly queues so that only one process at a time can access each reassembly queue.
All objects, features, and advantages of the present invention will become apparent in the following detailed written description.
REFERENCES:
patent: 5815516 (1998-09-01), Aaker et al.
patent: 6202060 (2001-03-01), Tran
patent: 6421730 (2002-07-01), Narad et al.
patent: 6434620 (2002-08-01), Boucher et al.
patent: 6546425 (2003-04-01), Hanson et al.
Armitage, Grenville et al., “Packet Reassembly During Cell Loss”, IEEE Network, Sep. 1993, pp. 26-34.*
Lee, Dongman et al., “A Reliable Datagram Transport Protocol on Local Area Network”, Proceedings of the ACM SIGCOMM conference on Communications architectures & protocols, Sep. 1986, pp. 320-327.
Al Alam Shahid
Bracewell & Patterson L.L.P.
Emile Volel
Roberts Diana L.
LandOfFree
Method and system for reassembling fragmented datagrams... 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 system for reassembling fragmented datagrams..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for reassembling fragmented datagrams... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3157088