Abstract:
A multi-node data processing system implements a method that assures that plural messages are enabled &#34;fair&#34; access to a data stream. Each node includes apparatus for controlling message transmissions and/or receptions from another node over a communication network. The method comprises the steps of: transmitting a routing message from a first destination node to a source node, the routing message signalling a readiness of the destination node to receive a data message; transmitting a first data message to the first destination node from the source node in response to the ready message; transmitting a conditional disconnect message from the first destination node to the source node upon receipt of a predetermined amount (i.e. a &#34;slice&#34;) of the first data message. The source node responds to the conditional disconnect message by either (1) disconnecting from the first destination node, and commencing transmission of a slice of a second data message to a second destination node if during transmission of the slice of the first data message, the source node has received a ready message from the second destination node; or (2) continuing transmission of the data message to the first destination node until message end or, following the procedure in (1) if a new ready message is received by the source node from a further destination node, whichever occurs first.

Description:
FIELD OF THE INVENTION 
     This invention relates to communication management within a multi-node network, and, more particularly, to a method and apparatus for controlling message transmissions in such a network to assure that contending nodes have fair access to an output data stream. 
     BACKGROUND OF THE INVENTION 
     In prior art networks, message distribution and data stream access are generally controlled at the message transmitting end or via centralized control apparatus and functions. Such control functions are implemented using both circuit switches and packet data switches. The following art is representative of such systems. U.S. Pat. No. 4,683,564 to Young et al. describes a matrix circuit switch system wherein a common timing signal is used to configure the system during time slices and to perform desired line connections for signal transfer during each time slice. U.S. Pat. No. 5,105,424 to Fflag et al. describes a packet routing system wherein routing and switching functions are dependent upon data contained in packet headers. 
     U.S. Pat. No. 4,750,171 to Kedar et al. discloses a time division multiple access system for a shared data bus wherein time slot channels are asynchronously allocated. In U.S. Pat. No. 5,008,808 to Ahmadi et al., a switching network is described that handles both voice and packet switch data and further employs uniform mini-packets which contain self-routing data. Ahmadi et al. employ uniform switching blocks that implement time slice message allocation. 
     U.S. Pat. No. 4,298,959 to Sundermeyer et al. describes a direct memory access message transfer system wherein asynchronously received data is stored in accordance with initially received data from the data stream. U.S. Pat. No. 4,380,046 to Fung describes a parallel processing array which employs centralized array communications control. U.S. Pat. No. 4,550,402 of Gable et al. describes a packet communication control system which enables communications between local computer networks. Two different types of mini-packets are employed with one type including header destination address data and word count information in the message portion. The second type of mini-packet includes the data message. 
     U.S. Pat. No. 4,623,996 to McMillen describes a packet switching node that responds to packets with routing tag signals. Lehman et al. in U.S. Pat. No. 4,763,317 describe a communication network for both narrow and wideband communications. Integrated control systems concurrently control both a narrow and wideband equipment to enable more efficient message transfer. In U.S. Pat. No. 4,811,365 to Manno, a protocol is described that enables multiple nodes to share a channel through a satellite. One node is designated as a reference node and others are designated as slave nodes, with the reference node controlling access and assuring synchronization of slave node transmissions. 
     U.S. Pat. No. 5,191,578 to Lee describes a parallel packet routing system which employs a scalable space-domain switching system between clusters of processors. Time domain-switching aspects are also employed to enable packet Switch-like control. Makris et al. in U.S. Pat. No. 4,979,100 describe a packet switch control network that employs an arbitration system to control message access to a bus. U.S. Pat. No. 5,117,420 to Hillis et al. disclose a message packet router that merges packets addressed to the same destination and enables broadcasting of message packets. 
     Presently, multi-node communication systems see many applications in data processing. For instance, parallel-processing systems include many node processors that operate in parallel upon a common problem and are interconnected by a matrix switch network. Other multi-node systems are used to perform control functions, such as controllers especially designed for use with disk drive memories. Such controllers must not only have the ability to control I/O functions, but also be able to interface with a communication network so that data from the disk drives can be distributed to requesting host processors. Within such a multi-node controller, data can be transferred at extremely high data rates (on the order of 100 megabytes per second). However, communication networks that connect such a multi-node controller to external host processors generally are able to handle data at lower transfer rates (e.g. 20 megabytes per second). As a result, input/output modules in the multi-node networks enable a &#34;performance matching&#34; of internal data transfer rates to the slower input/output devices that are attached to the respective nodes to enable operations without wasteful latencies. Otherwise, long messages emanating from a node in a multi-node network need to be buffered in large buffer memories that may delay and/or data starve other nodes seeking access to the input/output communication network interface. To control message delay and allocation in a multi-node network through the use of a central control mechanism or process adds significant overhead cost to the network. To allocate control of such messages strictly from the transmitting end also results in substantial network overhead. For instance, transmitting nodes are unaware of what acts are occurring at destination nodes or whether other transmitting nodes are making demands upon a destination node that is presently interfacing with the transmitting node. As a result, considerable communications are required to establish an understanding of conditions at both ends of a communication link. 
     Accordingly, it is an object of this invention to provide an improved system and method for enabling a multi-node network to control access of messages to an output data stream. 
     It is another object of this invention to provide a multi-node network with a &#34;fairness&#34; slicing procedure that assures all messages have at least a minimum of access to an output data stream. 
     It is yet another object of this invention to provide an improved data routing system for a multi-node network wherein communications overhead is distributed throughout the network. 
     SUMMARY OF THE INVENTION 
     A multi-node data processing system implements a method that assures that plural messages are enabled &#34;fair&#34; access to a data stream. Each node includes apparatus for controlling message transmissions and/or receptions from another node over a communication network. The method comprises the steps of: transmitting a routing message from a first destination node to a source node, the routing message signalling a readiness of, the destination node to receive a data message; transmitting a first data message to the first destination node from the source node in response to the ready message; transmitting a conditional disconnect message from the first destination node to the source node upon receipt of a predetermined amount (i.e. a &#34;slice&#34;) of the first data message. The source node responds to the conditional disconnect message by either (1) disconnecting from the first destination node, and commencing transmission of a slice of a second data message to a second destination node if during transmission of the slice of the first data message, the source node has received a ready message from the second destination node; or (2) continuing transmission of the data message to the first destination node until message end or, following the procedure in (1) if a new ready message is received by the source node from a further destination node, whichever occurs first. 
    
    
     DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a block diagram of a multi-node network that implements the invention hereof. 
     FIG. 2 is a block diagram of a representative node. 
     FIG. 3 is a diagram illustrating a source node and two destination nodes that are to receive messages from the source node. 
     FIG. 4 are time-line charts helpful in understanding the operation of the nodes in FIG. 3 during the implementation of the message allocation procedure of the invention. 
     FIG. 5 is a block diagram of a pair of source nodes that wish to transmit messages to a single destination node. 
     FIG. 6 are time-line chart of nodal communications helpful in understanding the operation of the nodes of FIG. 5. 
     FIG. 7 is a block diagram of source and destination nodes, the source node having two messages to be transmitted to the destination node. 
     FIG. 8 is a time line chart helpful in understanding the operation of the nodes of FIG. 7. 
     FIG. 9 is a block diagram of two source nodes and two destination nodes, with the source nodes having messages to be transmitted to the destination nodes. 
     FIG. 10 are time line charts helpful in understanding the operation of the nodes of FIG. 9. 
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     In FIG. 1, a block diagram illustrates a multi-node network configured as a disk drive controller 10. Nodes A and D are data store nodes that connect, to coupled disk drives 12, 14 and 16, 18, respectively. A pair of communication interface nodes B and C provide input/output functions for disk drive controller 10. Host processors are coupled to nodes B and C via communication links that exhibit data transfer rates that are lower than available data transfer rates within disk drive controller 10. For instance, the communication links connecting nodes B and C to the host processors will characteristically operate at a 20 Megabytes/sec. transfer rate, whereas internal communications within disk drive controller 10 may operate at a 100 Megabytes/sec. rate. As a result, multi-node disk drive controller 10 must implement a procedure that enables allocation of the input/output data stream on a fairness basis across all messages which contend for the communication links. Such a procedure will be described in detail below. 
     In addition to data store and communication interface nodes, disk controller 10 further includes a cache node E which provides a temporary storage facility for both input and output data transfer functions. Disk drive controller 10 is expandable by addition of further nodes, all of which are interconnected by an internal communication network 20. The fairness communication protocol implemented by the invention hereof is such that it is expandable in accordance with the expansion of disk drive controller 10, without requiring any alteration to previously connected nodes or the network which interconnects them. 
     Each of nodes A-E in FIG. 1 is configured from a standard node arrangement shown in FIG. 2. A node includes a microprocessor 22 that controls the overall functions of the node. A memory interface module 24 controls communications between microprocessor 22 and plural memory modules within the node. One such memory module is an operand memory 26 which contains code that controls the operation of microprocessor 22. Another such memory is disk drive memory 28 that is connected by an interface module 30 to memory interface module 24. A buffer memory 32 is further connected by a buffer interface module 34 to memory interface module 24. Buffer memory 32 provides message buffering functions for both incoming and outgoing messages. An internal switch interface 36 provides interface functions for both incoming and outgoing message transfers. 
     If the node shown in FIG. 2 is utilized as a cache node, buffer module 32 will be larger in size than if the node is configured as a communication interface node or a data store node. If the node is configured as a communication interface node, it further includes a serial adapter module 38 that connects, via communication line 40, to a host processor 42. If the node is configured as a data store node, it will include an internal interface module 30 and one or more connected disk drives 28. 
     Certain modules within the node of FIG. 2 perform specific functions that implement the data transfer protocol to be discussed below. As will become apparent, each data message transmitted within controller 10 is assured of at least a minimum of access to an output data stream, thus assuring that at least a determined portion of the data message is transmitted. That determined portion of the data message is hereafter be referred to as a &#34;slice&#34;. It is to be understood that the size of a message slice is a programmable function and can be varied in accordance with a user&#39;s setting of a constant within the controlling software. 
     Each buffer interface module 34 includes a message slice counter 44 which provides an indication when a portion of a received message equals a predetermined slice count. At such time, buffer interface module 34 issues a conditional disconnect signal via network 22 to the node from which the message was received (i.e. a &#34;source&#34; node). 
     Also within buffer interface module 34 is a latch 46 which indicates a &#34;message waiting&#34;. Message waiting latch 46 is set when the node is receiving a message and another node seeks access to the node for message transmission purposes. Under such a condition, message waiting latch 46 is set so that when a slice of a currently incoming message is received, the node will know whether another source node is waiting its turn to obtain access. 
     Memory interface module 24 includes a &#34;ready&#34; queue 48 that is a queue of pointers to messages awaiting transmission. A ready queue is maintained when a node acts as a source node--as contrasted to when the node is receiving a message as a &#34;destination&#34; node. 
     While not specifically described herein in detail, data messages are preceded by control messages which inform various nodes of requests for data transfers and what data is being requested. A detailed discussion of such control messages is outside the scope of this invention. 
     It is a central assumption in the further description of this invention however, that destination nodes are aware of what messages are required to be transmitted/received and which nodes are the sources of those messages. The invention assures that, given such knowledge, that the message transmission space is fairly allocated amongst nodes so that no one node monopolizes a communication pathway. 
     In the description of the protocol implemented by the system shown in FIGS. 1 and 2, certain messages are employed to implement the protocol. Those messages are as follows: 
     Ready (RDY): 
     Receipt of this message tells a source node to put a message on its ready queue (RQ) and to try to commence its transmission. 
     Conditional Disconnect (CD): 
     This message is transmitted by a destination node to a source node upon a determination that a message slice from the source node has been received. The CD message instructs the source node to disconnect if a new message is waiting in the source node&#39;s ready queue either now or at some future time--but otherwise to keep transmitting the message. 
     Message Waiting (MW): 
     The MW message is generated at a destination node when, in the process of receiving a message from a first source node, a second source node attempts to transmit another message to the destination node. The message waiting latch 46 is set in such a case but is not examined until after a slice of a current incoming message is received. 
     A Disconnect message is then generated to the first source node to prepare for a message transmission from the second source node. 
     Disconnect (DC): 
     The DC message is generated by a destination node and instructs a source node to unconditionally disconnect from the destination node. 
     End of Transmission (EOT): 
     EOT is a flag at the end of a transmission which indicates that the transmission ends but that there is more data to be transmitted. The EOT flag is issued by the source node. End of Session (EOS): 
     An EOS is a flag at the end of a transmission indicating that all data has been transmitted and that the session is finished. The EOS flag is generated by a source node. 
     In the description of the message slicing protocol to be described with respect to FIGS. 3-10, the following nomenclature is utilized in the drawings: a source node is designated by a subscript &#34;S&#34;; a destination node is designated by a subscript &#34;D&#34;; a transmitted message is indicated as a &#34;RDY&#34;, &#34;CD&#34;, &#34;EOT&#34;, etc.; and the direction of message transmission is indicated by an arrow over the message designation. Thus, B D   RDY A S  designates that node B is the destination node, node A is the source node and that node B is transmitting a Ready (RDY) message to node A. 
     In FIG. 3, nodes B and C are communication interface nodes and are destinations for messages being transmitted from node A (a data store node). Under such a circumstance, it is desired that the messages from node A be handled so that the messages for both nodes B and C have equal abilities to arrive at their respective destination nodes without being blocked, one by the other. 
     In FIG. 4, a pair of time-line plots indicate message transmissions between source node A, destination node B and source node A, destination node C. Initially, it is assumed that source node A and destination node B have been informed by control messages that a data message is to be transmitted from node A to node B. Thus, at time T1 when destination node B is prepared to receive a data message, it transmits a Ready (RDY) message to source node A. Source node A responds by transmitting a slice of the data message to destination node B (T1-T3). As above indicated, the amount of data encompassed by a message slice is user-selectable. 
     Assume further that both nodes A and C have been informed by control messages that a message is to be transmitted from node A (source) to node C (destination). As a result, destination node C, when it is available to receive the message, dispatches an RDY message (at T2) to source node A. However, since source node A is already transmitting a first slice of a message to destination node B, that transmission continues without interruption. However, source node A does place the data message that is destined for transmission to destination node C in its Ready queue so as to make it ready for transmission at the termination of the slice transmission to destination node B. 
     At T3, the message slice count module 44 in destination node B signals that a slice has been received. As a result, destination node B transmits a conditional disconnect (CD) message to source node A. At T4, source node A responds with an EOT message to destination node B indicating that message transmission is being terminated, but that additional information awaits to be transmitted. At the same time, source node A sees a message indicator in its Ready queue which designates both the message to be transmitted and the destination node (node C). Source node A thus commences transmitting a slice of that message to destination node C. At T5, destination node B sends a Ready message to source node A and source node A puts into its ready queue the remainder of the message due for transmission to destination node B. 
     At T6, when the first slice has been transmitted to destination node C, destination node C transmits a CD message to source node A. Because source node A sees a message for destination node B in its Ready queue, source node A responds with an EOT message at T7 to destination node C and commences transmission of a further slice of the previously transmitted message to destination node B. At times T8, T9, T10 etc., the procedure continues, with message portions for destination nodes B and C being multiplexed so that respective slices thereof are successively sent to the respective destination nodes. This action continues until both messages are completed and end of session (EOS) messages are received from source node A at the respective destination nodes. 
     It can thus be seen that it is a destination node that exerts basic control on message slice transfers. Furthermore, a destination node requires no knowledge of what other destination nodes are signalling a respective source node as the source node, by virtue of its Ready queue and the described slice protocol assures that no one contending destination node will obtain exclusive access to a data pathway. 
     Turning to FIG. 5, a case will be considered where two source nodes (nodes A and F) are in contention to transmit messages to a single destination node (node C). In FIG. 6, a pair of time-lines indicate the respective messages that are handled by the nodes and enable message transmissions to be ordered. Again, both source nodes A and F and destination node C have been informed by a control path that messages are to be transmitted to destination node C. 
     Assume that destination node C is initially informed that a message from node A is to be received. At a time (e.g. T1) when destination node C is available for data reception, it transmits an RDY message to node A. Source node A responds by transmitting a first slice of the message to destination node C. At time T2, node C, having received a slice, transmits a CD message to node A. In this instance, the CD message is ignored because no other message is present in the Ready queue of source node A. As a result, transmission continues of message traffic between source node A and destination node C. 
     Assume now that at some later time T3, destination node C is informed that source node F has a message for it. Since destination node C has already received at least a first slice of the presently incoming message from source node A, it immediately responds by sending an RDY message to source node F at T3. However, since destination node C is. unaware of the state of source node F (e.g. source node F may be otherwise occupied with another message or node), node C continues receiving the message from source node A and does not immediately issue a CD message to source node A. As a result, source node A continues to transmit its message to destination node C--thereby preventing wasteful message downtime through the network. 
     When source node F receives the RDY message from destination node C, source node F tries to transmit its message to destination node C. However, because destination node C is still receiving a message from source node A, node C does not respond to an initial handshake signal from source node F, causing source node F to abort its transmission try. However, in response to the transmission attempt from source node F, destination node C sets its message waiting flag 46 at T4 and, immediately thereafter (at T5), transmits a DC message to source node A. The DC message differs from the CD message in that it is an absolute disconnect that causes source node A to respond by sending an EOT message to destination node C at T6. This action renders destination node C ready to receive a data message. 
     At some later time (e.g. T7), source node F performs a transmission retry to destination node C and succeeds in obtaining a response to its handshake action. As a result, source node F commences transmission of a first slice of a message to destination node C. When destination node C has received its first slice from source node F, it will transmit a CD message to source node F which is ignored because node F has no messages on its Ready Queue. Node C then sends a Ready message to node A at T9. When node A (at some later time T10) attempts to send the next slice of the data message, node C returns a message waiting signal and issues a disconnect to node F. Source node F then examines its message waiting flag and finds that source node A has attempted a data transmission. The procedure repeats as above indicated. The procedure then continues, on a multiplex basis, until the messages from both source nodes A and F are completed. 
     In FIG. 7, it is assumed that source node A has two messages (1 and 2) for destination node C, and that messages 1 and 2 become ready for transmission at different times. If it is assumed that message 1 is ready for transmission at T1, then when source node A receives an RDY message from destination node C (indicating availability to receive message 1), source node A transmits the first slice of message 1. At the end of the first slice, destination node C transmits a CD message to source node A, but since message 2 has not yet been signalled as ready for transmission (and placed in the Ready cue of source node A), source node A continues transmission of message 1 to destination node C and ignores the CD message (but remembers that it has occurred). 
     At some time between T2 and T3, a control path informs destination node C that message 2 is ready for transmission from source node A (i.e. message 2 is in the Ready queue of source node A). Because destination node C has already received at least a first slice of message 1, it responds by transmitting an RDY message to source node A. Source node A responds by transmitting an EOT message to destination node C for message 1 (because it previously received a CD message) and commences transmission of a first slice of message 2 to destination node C. After node C receives a message slice, it sends a CD to source node A (which is ignored until a message is added to its Ready Queue). Node C then sends a Ready for message 1 to source node A and Node A sends an EOT message for message 2. The aforesaid procedure continues until an EOS message is received at destination node C for both messages 1 and 2. 
     Turning to FIG. 9, a message transmission condition is illustrated wherein a pair of source nodes (B and C) are transmitting messages to a pair of destination nodes (A and D) with source node C having two .messages for different destination nodes. 
     As shown in FIG. 10, at T1 destination node A transmits an RDY message to source node B, with source node B responding by transmission of a slice of its message to destination node A. At T2, it is assumed that destination node D transmits an RDY message to source node C. In response, source node C transmits a first slice of message 1 to destination node D. It is further assumed that the first slice comprises the entirety of message 1. At T3, destination node A transmits a CD message to source node B, having received a slice of the message from source node B. 
     Assume that destination node A has been informed by a control path that a source node C has message 2 in its Ready queue awaiting transmission. As a result, at T4 destination node A transmits an RDY message to source node C. However, source node C is still in the process of transmitting an initial message 1 slice to destination node D. Therefore, source node C is unable to respond to the handshaking action from destination node A. Source node C thus continues to transmit the message to destination node D. 
     When destination node D transmits a CD message (upon receipt of a slice) to source node C, source node C responds with an EOS signal as message 1 transmission has been completed. Source node C then attempts transmission of message 2 to destination node A at T6, but because destination node A is still receiving a message from source node B, destination node A does not respond to the handshake but rather sets its message waiting flag. Immediately thereafter, at T7, destination node A transmits a DC signal to source node D indicating an unconditional disconnect (it will be recalled that the unconditional disconnect is transmitted because destination node A has already received at least a first slice of a message from source node B). In response, source node B transmits an EOT message to source node A, allowing source node A to be ready to receive message transmission from source node C upon a subsequent retry at T9. The procedure then continues as aforedescribed. 
     In summary, message control is distributed throughout the nodal structure of a multi-node data processing system. The control procedure is indefinitely expandable since each node contains its own control mechanisms (i.e. a message slice count module, a message waiting flag latch, and a Ready queue). Those instrumentalities enable both destination and source nodes to manage data transfers in a manner that no single message is allowed to monopolize a data transmission path to the exclusion of other contending messages. Basic message control is exerted by destination nodes. 
     It should be understood that the foregoing description is only illustrative of the invention. Various alternatives and modifications can be devised by those skilled in the art without departing from the invention. Accordingly, the present invention is intended to embrace all such alternatives, modifications and variances which fall within the scope of the appended claims.