Acknowledgement Protocol for Serial Data Network With Out-of-Order Delivery

The present invention relates generally to systems and methods for transmitting frames or packets of information through a communication network. More particularly, the invention is directed to systems and methods for transmitting frames or packets of information in serial networks which utilize acknowledgments and allow out-of-order delivery of the frames or packets.

Numerous serial data communication protocols exist for transmitting frames or packets of information from an initiator (source) node to a recipient (destination) node in local and wide area networks. To ensure the consistency of the data at the receiving end, conventional practice involves the use of an acknowledgment transmission from the recipient node back to the initiator node upon acceptance of the information in the frame by the recipient. Though acknowledgment signals are not used as a routine in voice communication environments, comprehensive acknowledgment usage is mandatory for integrity in digital data transmissions.

A commercially available example of a serial network is the fibre optical serial channel used with the RISC System/6000 workstation product sold by IBM Corporation. Another example of such a system is defined by the Fibre Channel Standard (FCS) being developed by the American National Standards Institute (ANSI) X3T9.3 Task Group. The technology is documented in the Fibre Channel Physical and Signaling Interface (FC.sub.-- PH) Rev. 2.2 document available from Global Engineering, 2805 McGaw Street, Irvine, Calif. 92714.

A fundamental weakness of the technologies in present use and proposed in such standards arises from the need of an acknowledgment frame for each data frame transmitted by the initiator. Without specific network protocol constraints, out-of-order delivery of data frames is the serial packet network norm of operation. Even if delivery of data frames or packets follows the order transmitted, there remains the possibility that the processing of the frames by the recipient to confirm adequacy of the information in the frames may differ between successive frames. The timing of the acknowledgment transmissions would follow accordingly. Similarly, the acknowledgment frame is also subject to the out-of-order delivery to the initiator as a consequence of a busy network. In some circumstances the acknowledgment frame is completely lost as a consequence of an error in the network. Also possible are volitional deletions of acknowledgments by the network as a consequence of congestion or priority conditions. On the other hand, the rate of network communication is reduced significantly if the protocol requires that the data frames wait for an acknowledgment of each preceding data transmission, or that channels of the network be monopolized to ensure consistency of the data transmission and acknowledgment information.

In addition to acknowledgments that are lost, and as a consequence initiate error procedures within the network, standards of the type noted earlier define networks in which one or more acknowledgment frames have the misfortune of being transmitted and retransmitted into a then busy network. In each case the acknowledgment frames are returned to recipient node for later retransmission while the initiator node waits for the acknowledgment specific to the data frame.

Given the difficulty of handling out-of-order or lost acknowledgments, the prevailing design practice has been to require an ordered transmission in which an acknowledgment is expected for each data frame transmitted. Though the standards contemplate the use of time windows for delayed acknowledgment, the approach has proven to be relatively slow and particularly susceptible to further degradation as network congestion increases.

The present invention provides systems and methods of practice which facilitate out-of-order transmission of data by the initiator, and acknowledgment information by the recipient, in frames or packets over a multi-node serial network. The architecture and protocol are implemented by system and method resources at the initiator and recipient ends of the communication path. The resources relate data frame serial number or sequence count as defined at the initiator node to corresponding serial number or sequence count in the acknowledgment information transmitted from the recipient node. The invention is characterized by its provision for controller parameter information in the acknowledgment frame, such information representing that all acknowledgments for data frames prior to the serial number or sequence count of the acknowledgment were transmitted by the recipient node. In a preferred implementation, the acknowledgment frame includes within the frame header parameter field a control bit to indicate by its state the transmission status of all preceding acknowledgment frames.

These and other features of the invention will be more clearly understood and appreciated upon considering the detailed description which follows.

FIG. 1 is a schematic block diagram of a network.

FIG. 2 is a schematic block diagram of a fibre channel standard communication hierarchy.

FIG. 3 is a schematic block diagram of a FC-2 frame format.

FIG. 4 is a schematic block diagram of a frame header format.

The present invention finds particular usage and value in systems and methods conforming to the Fibre Channel Standard (FCS) defined by the ANSI X3T9.3 Task Group. The FCS defines a serial communication architecture and protocol for a network composed of multiple nodes connected through a communication medium. Information in the form of a data frame or packet is transmitted from an initiator node to a recipient node. FCS also defines an acknowledgment protocol, in which the recipient transmits a frame or packet of information back to the initiator to indicate reception of the data frame or packet.

A high level depiction of the FCS network appears in FIG. 1. Fabric 1 is the medium of communication, and broadly encompasses both optical and electronic transmission and related data manipulation resources. The fabric has connected thereto a multitude of N.sub.-- Ports 2, each comprised of initiator/recipient systems suitable to communicate over the network. Examples of node systems include workstations, super computers, disk arrays, and personal computers. Prior practices have confirmed that where switching fabric 1 allows out-of-order delivery, transmissions requiring acknowledgments are slow in the absence of a bandwidth allocation (channel monopoly) mode of operation. The poor performance for an out-of-order delivery protocol has been attributed to the fabric busy states or priority transmissions which delay mandated acknowledgment frames.

The present invention provides out-of-order delivery of both data and acknowledgment frames while retaining network performance. The initiator node provides with each data frame transmitted to the recipient a frame serial number or sequence count for the frame. Each acknowledgment frame transmitted by the recipient, to indicate delivery of the data frame, contains the matching serial number or sequence count of the corresponding data frame which it is acknowledging. However, the acknowledgment frame also incorporates a control bit within the frame header parameter field to indicate the status at the recipient as of that data frame. The status in the acknowledgment frame indicates whether or not all acknowledgments to data frames prior to that identified by the acknowledgment frame serial number or sequence count have been transmitted by the recipient. The additional control parameter can be a single bit, indicating by binary state the composite transmission history of earlier acknowledgment frames.

A preferred implementation of the acknowledgment protocol described above draws upon the FCS network depicted in FIG. 1. As defined by FCS, the channels of communication between nodes provide for any-to-any and peer-to-peer communication, as well as master-slave or initiator-target relationships. Each has resources to provide three classes of service through the fabric: Class 1--Dedication Connection, Class 2--Multiplex (Connectionless), and Class 3--Datagram (Connectionless).

Each FCS channel is defined as logically composed of multiple hierarchical levels, as schematically depicted in FIG. 2. The channel is not "layered" with fixed service intervals between levels, but rather, allows for a high level of chip integration of functions in successive layers. For instance, the signal protocols accomplished in layers FC-0, FC-1 and FC-2 can be implemented in a single integrated circuit chip.

FC-0 defines the physical link attributes, which include support for various data rates, single and multi-mode optical fibre, coaxial cable, and twisted pair wires. Transmitter/receiver pairs include long wave and short wave lasers, long wave LEDs, and electrical interfaces.

FC-1 uses the IBM 8B/10B transmission code to provide reliable communication. The 8B/10B code is DC-balanced and provides special 10-bit transmission characters which facilitate byte and word alignment through the use of ordered sets. An ordered set is a four byte word which contains a K28.5 in its first position followed by three data characters. Ordered sets are used to specify primitive signals, primitive sequences and frame delimiters (Start.sub.-- of.sub.-- Frame, End.sub.-- of.sub.-- Frame).

Primitive sequences are ordered sets of digital information used to initialize or reset the fibre link. Continuous transmission of a specific primitive sequence conveys network status information. Each primitive sequence is interlocked waiting for a primitive sequence transmitted in response. Following a link initialization protocol of primitive sequences, idles (a primitive signal) are transmitted on the link. Frame transmission is accomplished by inserting a frame in the idle stream. Each frame is encapsulated between a Start.sub.-- of.sub.-- Frame (SOF) delimiter and an End.sub.-- of.sub.-- Frame (EOF) delimiter, as shown in FIG. 3.

The Start.sub.-- of.sub.-- Frame delimiter delineates a frame boundary, defines a sequence boundary, and identifies the Class (1, 2, or 3) of the frame. The frame header immediately follows the SOF and contains sufficient information to control the transfer of information from a ULP in an initiator (source) N.sub.-- Port to a ULP in a recipient (destination) N.sub.-- Port. Following the frame header is the data field which may contain optional headers and payload. A 32-bit CRC checks the contents of the frame from the frame header to the end of the data field. The data field is required to be a word-multiple and may contain up to three fill bytes on the end of the data field.

The FC-2 level (FIG. 2) provides the format for performing I/O operations, known as exchanges. An exchange is composed of one or more sequences flowing in one direction at any given time. Each sequence is composed of a consecutive series of data frames. As shown in FIG. 3, the first data frame of a sequence is identified by a SOFix (initiate) to define the beginning of a sequence (where x specifies Class 1, 2, or 3). Other frames within the sequence are started with a SOFnx (normal).

The fields composing the frame header are shown in FIG. 4. R.sub.-- CTL is used for routing control. D.sub.-- ID (Destination Identifier) and S.sub.-- ID (Source Identifier) are 24 bit fields used to identify a specific N.sub.-- Port within the address domain of the fabric. The small address was chosen to allow fast N.sub.-- Port selection within the fabric. The TYPE field specifies the upper level protocol being used. The F.sub.-- CTL (Frame Control) field provides a number of control bits which aid the signaling protocol. SEQ.sub.-- ID is a one-byte identifier to identify a specific sequence within an exchange. DF.sub.-- CTL, (Data Field Control) identifies the presence of optional headers in the data field.

The SEQ.sub.-- CNT field is a frame count within the sequence. Each sequence starts with a SEQ.sub.-- CNT of 0 and is incremented by one for each frame transmitted. The OX.sub.-- ID is a 2-byte exchange identifier uniquely assigned by the initiator of the exchange. The RX.sub.-- ID is a 2-byte exchange identifier uniquely assigned by the recipient of the exchange. The parameter field is used to contain a relative offset of the payload for data frames.

In Class 1 and 2, each data frame is acknowledged by transmitting an ACK frame with a matching SEQ.sub.-- CNT. Busy and reject frames are also defined to notify the transmitter that the frame could not be delivered. A Class 1 dedicated connection is requested by transmitting a frame containing an SOFcl delimiter. The S.sub.-- ID N.sub.-- Port waits for an ACK frame in response from the recipient N.sub.-- Port. When the ACK is received, the connection is established and the first sequence initiated. Each N.sub.-- Port may then initiate other sequences. The connection is removed by transmitting an EOFdt (disconnect-terminate) delimiter on the last ACK. A remove connection protocol is defined in order to coordinate removal of the connection.

In Class 2, each data frame is delivered as a single entity without the establishment of a dedicated connection. In Class 2, busy and reject response frames are also provided. The normal rules for originating and managing exchanges apply to both Class 1 and 2. In Class 3, each data frame is delivered on a best-effort basis without response frames.

In order to determine the operating characteristics of an N.sub.-- Port, each N.sub.-- Port performs a login sequence with the fabric and each N.sub.-- Port with which it communicates. Parameters include classes supported, number of buffers available (credit), and worldwide name. Since the number of buffers is known, each N.sub.-- Port may transmit frames up to its credit limit (M) prior to receiving an ACK frame. The ACK frame transmitted in response indicates that the buffer which received the frame is available for further frame reception. If an error is detected, the sequence is aborted and retransmitted in its entirety or from the point of failure, depending on the ULP.

In the preferred context of a fibre channel standard network operating in a Class 2 mode, the present invention provides system and method resources at the initiator and recipient nodes to create and use control information contained in a frame header parameter field of the acknowlegment frame, such control information indicating that all prior acknowledgment frames were transmitted by the recipient. The preferred implementation utilizes a control bit in parameter field 3 of the frame header defined by the format in FIG. 4. The delivery of an acknowledgment to the initiator node with the control bit set to 0 indicates that all acknowledgment frames prior to the serial number associated with that acknowledgment were in fact transmitted by the recipient node. On the other hand, the presence of a 1 in the control bit position indicates that at least one of the data frames with a serial number preceding that of the acknowledgment had, as of the transmission time of the acknowledgment in question, either not been received, or not been processed by the recipient, been found to have an error, or not been acknowledged. Thus, the combination of the data frame serial number and control bit in the acknowledgment frame extends the status information to include both a data frame delivery status and an acknowledgment transmission history.

The use of an acknowledgment frame with a control bit indicative of prior data frame receipt and acknowledgment transmission status provides numerous network benefits. First, it permits out-of-order delivery and processing of data frames at the recipient node, since the status of the order as perceived by the initiator is reset each time the control bit conveys a historical update. Out-of-order delivery is similarly permissible for the acknowledgment frames. This is particularly important in that a network conforming to the architecture and protocol defined in the fibre channel standard is susceptible to conflicting transmissions which have priority. Such events can delay or defer for later re-transmission the affected acknowledgment frames. Furthermore, even the complete loss of an acknowledgment frame is no longer of consequence when utilizing the system and method defined by the present invention.

In the preferred implementation, a workstation such as the RISC System/6000 with an AIX operating system, both available from IBM Corporation, executes application code at the initiator and recipient nodes to accomplish the methods defined by the invention.

The initiator is the transmitter of data frames and the receiver of acknowledgment frames. The recipient is the receiver of the data frames and transmitter of the acknowledgment frames. Both the initiator and recipient track the progress of the sequence (collection of data frames flowing in one direction) in a Sequence Status Block. In this embodiment, Fabric Busy (F.sub.-- BSY) frames are processed. In addition, Max.sub.-- Credit is used as the upper bound on the number of unacknowledged data frames that may be transmitted before receiving an acknowledgment. Credit.sub.-- Cnt is a variable in the transmitter used to count data frames which have not been acknowledged. Credit.sub.-- Cnt is incremented on data frame transmission and decremented on reception of an acknowledgment. Both F.sub.-- BSY and Credit.sub.-- Cnt are optional features. When Parm=0 in the ACK frame, all acknowledgment frames up to that FR.sub.-- CNT have been transmitted. When Parm=1 in the ACK frame, one or more previous data frames has not been acknowledged.

Pseudocode, from which source code can be derived, sets forth the preferred process to be accomplished at the initiator node. In general, the pseudocode prescribes the tracking of data frame transmissions and the receipt of related acknowledgment frames. The pseudocode begins with an initialization sequence, defines a data frame transmission tracking sequence, defines an acknowledgment receipt processing sequence, and concludes with a sequence responsive to the acknowledgment information. The variables used in the pseudocode are defined individually as follows:

FR.sub.-- CNT--the serial number transmitted in the Data frame by the Initiator (i.e. part of the frame header).

I.sub.-- FR.sub.-- CNT--the highest Data frame serial number transmitted by the Initiator which is retained in the Sequence Status Block.

ACK.sub.-- FR.sub.-- CNT--the highest serial number of any ACK frame received which is retained in the Sequence Status Block.

ACK.sub.-- R.sub.-- R--ACK Receive Register (in this example, 8 bits) indexed 0 to 7 where index value 7 (a bit) corresponds to ACK.sub.-- FR.sub.-- CNT. Index value 6 corresponds to ACK.sub.-- FR.sub.-- CNT-1 and index value 0 corresponds to ACK.sub.-- FR.sub.-- CNT-7.

CREDIT.sub.-- CNT--a value representing the number of buffers available in the Recipient for receiving Data frames.

MAX.sub.-- CREDIT--a value representing the maximum number of buffers available at the Recipient for receiving Data frames.

MISS.sub.-- ACK.sub.-- CNT--a count of ACK frames received which are out of the ACK window of processing. Credit is reclaimed after the Sequence is completed.

The system and process activities at the recipient node generally track the data frame reception and the acknowledgment frame transmission operations. The pseudocode begins with an initialization sequence, defines operations related to the reception of a data frame, defines processes associated with creating a frame header for the acknowledgment frame, undertakes the transmission of the acknowledgment frame, and defines a response to a busy state of the network fibre. The variables used in the pseudocode set forth below for the recipient node are defined as follows:

FR.sub.-- CNT--the serial number received in the Data frame by the Recipient (i.e. part of the frame header) and transmitted in the ACK frame acknowledging the Data frame specified by FR.sub.-- CNT.

DF.sub.-- FR.sub.-- CNT--the highest Data frame serial number received by the Recipient which is retained in the Sequence Status Block.

DF.sub.-- R.sub.-- R--Data frame .sub.-- Receive.sub.-- Register (in this example, 8 bits) indexed 0 to 7 where index value 7 (a bit) corresponds to DF.sub.-- FR.sub.-- CNT. Index value 6 corresponds to DF.sub.-- FR.sub.-- CNT-1 and index value 0 corresponds to DF.sub.-- FR.sub.-- CNT-7. This register is used to detect missing Data frames.

ACK.sub.-- FR.sub.-- CNT--the highest serial number of any ACK frame transmitted which is retained in the Sequence Status Block.

ACK.sub.-- T.sub.-- R--ACK.sub.-- Transmit.sub.-- Register (in this example, 8 bits) indexed 0 to 7 where index value 7 (a bit) corresponds to ACK.sub.-- FR.sub.-- CNT. Index value 6 corresponds to ACK.sub.-- FR.sub.-- CNT-1 and index value 0 corresponds to ACK.sub.-- FR.sub.-- CNT-7.

CREDIT.sub.-- CNT--a value representing the number of buffers available in the Recipient for receiving Data frames.

BITNUM--a register used in calculations to set bits in a register.

SETBIT--a register used in calculations to set bits in a register.

GOBIT--a single bit variable used to control a DO.sub.-- WHILE loop.

Although the invention has been described and illustrated by way of a specific embodiment, the methods, systems and programs encompassed by the invention should be interpreted consistent with the breadth of the claims set forth hereinafter.