Electrical computers and digital data processing systems: input/ – Input/output data processing – Input/output data buffering
Reexamination Certificate
1999-04-07
2004-03-30
Park, Ilwoo (Department: 2182)
Electrical computers and digital data processing systems: input/
Input/output data processing
Input/output data buffering
C710S017000, C710S037000
Reexamination Certificate
active
06715008
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to computer communication protocols, and more specifically to a credit-based message protocol in a multi-processor computer system.
2. Discussion of Background Art
Multi-processor computer systems are made up of multiple processor nodes communicating over a high-speed interconnection network. Each processor node typically includes a processor and local Random Access Memory (RAM). Computational tasks are divided among processor nodes to maximize utilization of resources available at different processor nodes. Dividing a task among processor nodes can reduce the time needed to produce a result, but implies that one part of a task being processed by one node may depend on the results of another part of the tasked being processed by another processor node. The various sub-tasks must exchange information relevant to their processing, and synchronize their processing, via the network.
Different methods of communication exist. The shared-memory method of communication is very fast because each processor can simply read what has been written by other processors. However, in this method the critical memory areas used for communications by one sub-task are not protected from being overwritten by another sub-task. In a message-passing model, on the other hand, each processor can only access its own memory and can only communicate with other processors by explicitly composing a message and sending it to other processors. This model protects communications because one processor cannot write to another processor's memory.
In either of these methods of communication, when a first processor node sends a message to a second processor node, the first node waits for an acknowledgement from the second node. When the message reaches the second node, there are three possibilities: the message is accepted, the message is lost, or the message is blocked. If the receiving processor node is too busy or too full to process the message, the message may be lost. The receiving processor may return a message indicating the loss of the message or it may remain silent. If the message is blocked, then the communication interface clogs the system and clogging propagates backward, congesting the network and/or harming the system.
An efficient way to receive messages allows incoming messages to be written to a receiving node memory buffer that is shared between all senders that may communicate with the receiver. If any particular sender continually sends messages to the receiver, for example, due to a software or hardware error in the sender, that sender can over-run the receiver and fill up the shared buffer. Then, additional incoming messages may be discarded or blocked in the network. In either case, the flood of erroneous messages would interfere with the processing of legitimate messages from other nodes.
What is needed, therefore, is a message passing system that overcomes the above-discussed deficiencies.
SUMMARY OF THE INVENTION
The present invention provides a credit-based mechanism to limit the maximum number of packets a node can receive from another node in a multi-processor node computer system. The invention includes a buffer pool and a credit mechanism in each node wherein the buffer temporarily stores incoming packets sent by other nodes. The credit mechanism allocates a predetermined number of packets which a node can receive from another node so that no sending node can use more than its allocated share of the buffer pool, and thus assures that the buffer pool will not overflow. Even though a node can continue to transmit unwelcome packets, the packets are not written into the packet buffer pool, and are thus discarded. Because the packet buffer does not overflow, the receiving node can continue to communicate with other nodes.
REFERENCES:
patent: 5748629 (1998-05-01), Caldara et al.
patent: 5867663 (1999-02-01), McClure et al.
patent: 6209064 (2001-03-01), Weber
patent: 6246684 (2001-06-01), Chapman et al.
patent: 6246687 (2001-06-01), Siu
Wolf-Dietrich Weber, et al., “The Mercury Interconnect Architecture: A Cost-effective Infrastructure for High-performance Servers”, In proceedings of the 24th International Symposium on Computer Architecture (ISCA '97), pp 22-30, Jun. 1997.
http://www.webopedia.com/TERM/o/octet.html, Octet (last visited Jan. 24, 2002).
http://www.webopedia.com/TERM/cell.html, Cell (last visited Jan. 24, 2002).
Douglas E. Comer, Internetworking With TCP/IP VOI I: Principles, Protocols, and Architecture, Third Edition, p. 36, 308, Prentice Hall, Upper Saddle River, New Jersey.
Carr & Ferrell LLP
Fujitsu Ltd.
Kim Harold
Park Ilwoo
LandOfFree
Method and system for over-run protection in a message... 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 over-run protection in a message..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for over-run protection in a message... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3202014