Error detection/correction and fault detection/recovery – Data processing system error or fault handling – Reliability and availability
Reexamination Certificate
2000-09-26
2004-04-27
Beausoliel, Robert (Department: 2184)
Error detection/correction and fault detection/recovery
Data processing system error or fault handling
Reliability and availability
C714S052000, C714S776000, C713S160000
Reexamination Certificate
active
06728909
ABSTRACT:
FIELD OF THE INVENTION
The present invention pertins generally to multiprocessor and clustered systems, and more particularly to a method for speculatively receiving data in the form of message packets to expedite message traffic between communicatively interconnected elements of a multiprocessor system.
BACKGROUND OF THE INVENTION
Many computing and processing systems today are collections of separate processing elements of one type or another that are interconnected by a data network for data communication. Wide area networks (WANs), local area networks (LANs), or system area networks (SANs) are a few examples of such interconnective networks. Many of these networks use a communication protocol that transmits information in the form of packets, an initial portion of which (often termed the “header”) contains information about the packet (e.g., its source and destination) and its content (e.g., if it carries data, a description of that data, and what is to be done with it). Whatever form the interconnection takes, efficient operation of the system as a whole depends, in part, upon the network architecture being able to provide fast, well-organized transfers of data between the system elements. Typically, that design will incorporate switches or routers that route message traffic through the various communication paths of the network, from one element of the system to one or more other elements of the system. Presently available switch designs are able to improve communication efficiency by a data-handling capability that uses latency reduction techniques. See, for example, U.S. Pat. Nos. 5,694,121 and 5,710,549, which deal with techniques for granting path access to multiple contending messages.
Other techniques for enhancing the network communication efficiency involve focusing on the topology of the network interconnect in an effort to remove or at least minimize loops and resultant deadlock. For example, massively parallel processing (MPP) systems may use hundreds if not thousands of interconnected processing elements and associated input/output equipment (e.g., disk storage, communications devices, printers, and the like). Communication between elements of an MPP system will require high band-width connections in order to reduce inter-element latency of message traffic to keep the system running as efficiently as possible.
Lacking proper design, a network is open to the possibility of a “deadlock” being created. This situation results when groups of messages cannot make further progress through the communicating network because of a circular dependency in which each message packet must wait for another to proceed before acquiring access to a communication link. But, even with a well designed interconnect or network topology, deadlock can occur when the destination is incapable of receiving messages as quickly as they are sent. Sluggish reception at a destination can cause message packets to back up through the interconnect and possibly impede message packet traffic bound for other system elements. Thereby, the effectiveness of the interconnect design is reduced—particularly during periods of high message traffic. This problem is particularly apparent in high speed interconnect schemes, and is exacerbated with the growth of the system.
One approach to reducing this problem is to provide the destination with sufficient buffer storage so that when a message packet is received it is stored to await processing. However, additional buffer storage can be expensive, making the approach a costly and often prohibitive solution, particularly for high-speed operation. An alternate approach, used in co-pending patent application Ser. No. 09/606,425, filed Jun. 28, 2000, for “Network Deadlock Avoidance Using Other Memory to Buffer Received Packets” is to use a buffer size sufficient to handle typical message traffic, but to use memory already available to spill messages to when the buffer becomes full during periods of heavy message traffic at the destination.
In addition, those protocols that use an initial portion (“header”) of the packet to provide particulars about the packet (its source, destination, content, etc.) can make a sluggish destination even more so. The reason being that header information is used, for example, to authenticate the packet (e.g., to verify that the source is authorized to do what the packet desires, etc.). However, before any verifications are made, the usual procedure is to receive the entire packet, check its correctness, and then proceed to authenticate the packet. For packets carrying large amounts of data, this can take some time.
Thus, it can be seen that there still exists a need for handling incoming message traffic at the receiving end in order to relieve message traffic-crowding on the network interconnect—particularly for systems that require high speed data communication between various of the system elements.
SUMMARY OF THE INVENTION
The present invention provides a processing system with a method of speculative reception of message packets containing data and other information. In particular, the invention is most advantageously used in systems of the type in which at least certain of the message packets include a header to describe the content of the packet.
Broadly, the invention involves initiating processing of the message packet after the header is received, but before the remainder of the packet is received and its correctness verified. Such processing may include determining that the source of the message packet is authorized to provide data to the recipient destination. When the entire message packet is received, an error-checking code which concludes the packet is checked, and if there is no error found, processing is completed by routing the data to its intended location at the destination element (e.g., a memory of a CPU). If, however, the error-checking indicates that the data or the message packet contains an uncorrectable error, the data will either be stored for later review, or discarded, depending upon the type of error.
A number of advantages are achieved by the present invention. First, early initiation of processing the message packet, before it is received in its entirety, allows a receiving element to ready itself much faster for receiving a subsequent message packet. This, in turn, leads to the advantage of keeping traffic moving on the interconnections used to communicate the system's elements to one another and lowering traffic congestion on that interconnect.
REFERENCES:
patent: 4692917 (1987-09-01), Fujioka
patent: 5121396 (1992-06-01), Irvin et al.
patent: 5208810 (1993-05-01), Park
patent: 5268900 (1993-12-01), Hluchyj et al.
patent: 5557751 (1996-09-01), Banman et al.
patent: 5574849 (1996-11-01), Sonnier et al.
patent: 5592536 (1997-01-01), Parkerson et al.
patent: 5675579 (1997-10-01), Watson et al.
patent: 5687314 (1997-11-01), Osman et al.
patent: 5694121 (1997-12-01), Krause et al.
patent: 5710549 (1998-01-01), Horst et al.
patent: 5835726 (1998-11-01), Shwed et al.
patent: 5860136 (1999-01-01), Fenner
patent: 5867501 (1999-02-01), Horst et al.
patent: 5935245 (1999-08-01), Sherer
patent: 6049889 (2000-04-01), Steely et al.
patent: 6108583 (2000-08-01), Schneck et al.
patent: 6151689 (2000-11-01), Garcia et al.
patent: 6163843 (2000-12-01), Inoue et al.
patent: 6163844 (2000-12-01), Duncan et al.
patent: 6331829 (2001-12-01), Kawai
patent: 6343323 (2002-01-01), Kalpio et al.
patent: 6480972 (2002-11-01), Cromer et al.
patent: 6490705 (2002-12-01), Boyce
patent: 6522665 (2003-02-01), Suzuki et al.
patent: WO009923538 (1999-05-01), None
Brown David A.
Bunton William P.
Krause John C.
Peet Charles E.
Beausoliel Robert
Chu Gabriel
Hewlett--Packard Development Company, L.P.
LandOfFree
Data communication with speculative reception of data in a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data communication with speculative reception of data in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data communication with speculative reception of data in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3265630