Error recovery method in a system constituted by nodes connected by lienks which transfer error control fames.

Field of the Invention

0001This invention relates to the field of information communication between nodes in a network and more specifically to recovering from errors occurring during the transmission of data between nodes.

Background of the Invention

0002A variety of different types of network configurations have been proposed or used for transmitting data between interconnected nodes in a network. For example, Local Area Networks (LANs) comprise a number of computer based pieces of equipment which are normally distributed within a single establishment. A LAN is most commonly arranged into one of three basic topologies, namely star, bus and ring. More complex network configurations are possible by interconnecting a number of different LANs by means of switches in the form of bridges or routers.

0003These networks include some type of error recovery method. This includes a means of detecting an error end a means of correcting the error. The means of detecting the error can typically include a parity check on each byte or small quantity of information transferred. A parity check is the addition of usually a single bit by the transmitter to make the simple arithmetic summation of all of the bits within, for example a byte, transmitted into either an even number for even parity, or an odd number for odd parity. A Parity check will usually detect one bit errors and so is mainly used over short distances with transmission paths of high integrity.

0004For longer distances, or for transmission paths of lower integrity, a CRC (cyclic redundancy check) can be used. A CRC typically consists of one of two bytes that are sent for each block of bytes, such as after each 128, 256 or 512 bytes are sent. The particular CRC used is defined by the polynomial used to calculate it. A typical polynomial would be <maths id="math0001"><math display="inline"><mrow><mtext>X¹⁶ + X¹⁵ + X² + 1</mtext></mrow></math><img file="EP0576136A2_D0001.tif" /></maths> . The least significant one or two bytes are taken and transmitted after the data. The receiver applies the same method of calculating the polynomial to incoming data and then compares the answer it calculates with the incoming CRC. The probability of detecting even multi-bit errors, such as those associated with a long transmission path, is very high.

0005These error detection methods all correct errors by the receiving node requesting retransmission of the block of data containing the error. The retransmitted block is then checked in the same way as the originally transmitted block. These methods do not allow for the transmitting node to take corrective action where the receiving node does not acknowledge receipt of data. This can result in the transmitting node continuing to send frames until the buffer in the receiving node is full. The disadvantage of this is that at this point no further communication with the receiving node to assist error recovery is possible, since data will be rejected by the receiving node until it's buffer is cleared. In order to clear it's buffer, the receiving node may pass on incomplete data. This has a further disadvantage that if the data being sent is a replacement for previous data, for example, an updated version of a previously stored file, then the previously stored file may be corrupted by the incomplete data.

0006Where multiple paths from a transmitting node to a receiving node exist, it is possible to take corrective action to clear the buffer associated with the failing path, and also to ensure that the incomplete data is discarded, rather than passed on from the receiving node. This recovery will usually be coordinated by a single node having access to all receiving and transmitting nodes in the network. This access may be via other receiving/transmitting nodes. This single node or master is permanently defined for a given network. This has the disadvantage that a user of the network, that is, for example an application, that is inputting or outputting information to or from one of the receiving or transmitting nodes to be sent to another user, may wish to define a different node as a master. It has the further disadvantage that in the event of a failure of the master node, the error recovery co-ordination for the whole network will be inoperative.

Disclosure of the Invention

0007Accordingly the invention provides an error recovery method for use in an information communication system which comprises a plurality of nodes connected by links, information being transferred between the nodes, using one or more of said links, in frames of predefined types, including at least a first frame type used to transfer data and a second frame type used for error recovery, the information transfers being initiated by more than one node, the nodes having at least a first and a second mode of operation, the method comprising the steps of: defining a master node for controlling error recovery; on detecting an error on a link connecting a first and second node; switching one or both of the first and second nodes from a first to a second mode of operation wherein frames of the first type are discarded by the node at all of its ports and frames of the second type are accepted by the node at any of its ports; transmitting by one or both of the first and second nodes, to the master node, of a second frame type containing first error information; transmitting by the master node, to all nodes capable of initiating information transfer, of a second frame type containing second error information; transmitting by other nodes which have initiated frames of a first type using the link connecting first and second nodes, to each node to which the first type frames were sent, of instructions causing the first frame types to be discarded; on successful completion of the transmitting steps; transmitting by the master node, to the first and second node frames, causing the nodes to switch to the first mode of operation, where frames of all types are accepted; and transmitting by the master node, to all nodes capable of initiating information transfer, of a second frame type cancelling the second error information.

0008Preferably the step of defining a master node comprises selection of a master node by agreement between all nodes which are capable of initiating information transfer, using predetermined criteria. Preferably each node capable of initiating information transfer has a unique identifier and the predetermined criteria for agreeing a master node is selection of the node having the highest value for the unique identifier.

0009Preferably the error recovery method further comprises the steps, prior to switching one or both of the first or second nodes to the second mode of operation, of: retransmitting by the first or second nodes, to the respective other node, of the frames being transmitted when an error was detected; checking whether the retransmitted frame is received without error by the respective other node; and if the retransmitted frame is received without error, terminating the error recovery method.

0010Preferably the first error information identifies that an asynchronous event has occured on one of the ports of the node from which the first error information is transmitted and the second error information identifies that a link state change has occurred. Preferably the method further comprises: on a first node detecting the addition of a third node to a port on the first node; switching the first node from a first to a second mode of operation wherein frames of the first type are discarded by the node at all of its ports and frames of the second type are accepted by the node at any of its ports; transmitting by the first node, to the master node, of a second frame type containing third error information; transmitting by the master node, to the third node, of a second frame type containing the unique identity of the master; on successful completion of said transmitting steps; transmitting by the master node, to the first and third node, frames, causing the nodes to switch to the first mode of operation, where frames of all types are accepted; and transmitting by the master node, to all nodes capable of initiating information transfer, of a second frame type containing the unique identity of the third node.

0011Preferably the link is a serial link.

Brief Description of the Drawings

0012A preferred embodiment of the invention will now be described, by way of example only, with reference to the accompanying drawings, in which: <ul id="ul0001" list-style="none"><li>Figure 1 depicts the major functional components of a dual-ported node such as may be found in a network using the technique of the present invention;</li><li>Figure 2 is a block diagram of a simple network comprising a pair of interconnected single port nodes;</li><li>Figure 3 is a block diagram of a network comprising a string of interconnected single port and dual port nodes with a single transmission path between nodes;</li><li>Figure 4 is a block diagram of a network comprising a number of dual-ported nodes, such as those of figure 1, interconnected in a loop configuration having two possible transmission paths between nodes;</li><li>Figure 5 is a block diagram of a complex network of interconnected nodes, including single port, dual port and switch nodes;</li><li>Figure 6A shows the format of a single frame used in communication between nodes, such as those in figures 2 to 5;</li><li>Figure 6B shows the format of the address field component of Figure 6A;</li><li>Figure 7 is a block diagram of a personal computer system in which the present invention may be employed;</li><li>Figure 8 is a block diagram of a file server system in which the present invention may be employed.</li></ul>

Detailed Description of the Invention

0013The following conventions are used throughout this description:    The bits in an uncoded data byte are numbered 7 to 0 from left to right and Bit 7 is the most-significant bit. The most-significant byte of an integer is first. Bit values are represented as, for example 1b and Hexadecimal values are represented as, for example A2h.

0014The addressing scheme employed in the present invention distinguishes three types of node, according to the connectivity. These are single-port node, dual-port node and switch (3 - 16 ports). In a network employing the present invention, these nodes will typically be electronic devices e.g. computers, printers, storage devices etc.

0015Figure 1 shows a dual-port node 10 including two ports 16, 18 each connected to a serial link 12, 14. Also included is a 3 way router 20 which connects the ports to the node function 22. Depending on the address field, the router forwards an inbound frame to the node itself or to the outbound line of another port. When the node wants to originate a frame it instructs the router to transmit it on a specified port. All message and data frames relating to a particular command use the came port.

0016The following are types of network that can be implemented:

(i) Dedicated connection

0017Figure 2 shows the simplest case of a dedicated connection between 2 single-port nodes 30 &amp; 32.

(ii) Strings

0018Figure 3 shows a linear network of dual-port nodes 36, 38, 40, 42 known as a string. To allow unrestricted communication between any two nodes the maximum number of nodes in a string is 17, including the end nodes. This is because in the preferred embodiment a single hex digit is chosen for the address of a node in the string relative to any other node in the string. For example, this allows 16 devices to be connected to a single adapter port. The extreme nodes at either end of a string can be single-port nodes 34, dual-port nodes with one disconnected port 42 or switches.

(iii) Loops

0019A loop is a cyclic network containing only dual-port nodes 44, 45, 46, 47, 48 as shown in Figure 4. A loop provides better availability than a string because any single node can fail without blocking communication between any pair of the remaining nodes. A node can also be inserted into the loop or removed from the loop dynamically without preventing communication between the other nodes. To retain these availability properties the maximum number of nodes is limited to 17 for the same reasons as described in the string network above.

(iv) Switches

0020Figure 5 shows a complex network including two switches 106, 114, three strings 100,102,104; 108,110; 116,118 and a cyclic path linking node 118 to switch 114. Switches permit the inter-connection of a large number of nodes. They also allow alternate paths to be provided to achieve fault tolerance.

FRAMES

0021The two ports at opposite ends of a single serial link between nodes communicate in units called frames. A frame consists of a sequence of information bytes delimited at each end by a special protocol character known as a FLAG. A frame is divided into a sequence of 3 or 4 fields as shown in Figure 6A. CONTROL FIELD - The control field is always present and is one byte in length. The control field indicates the frame type. APPLICATION frames are used to transfer messages and data in normal operation. PRIVILEGED frames are used for configuration and error recovery. The Privileged messages associated with error recovery are described later. CONTROL frames are used for resets. ADDRESS FIELD - The address field is always present and is between one and six bytes in length, depending on the complexity of the network and the number of channels implemented by the destination node. This field is divided into a PATH component, a CHANNEL component and a PAD component. The Path routes the frame through the network to the destination node. The Channel consists of facilities within the destination node to receive a message or to receive a single data transfer. One Channel is predefined to receive messages. All other Channels are dynamically allocated for data transfers. The Pad, if necessary, is a single digit to make the address field up to an integral number of bytes. The value of the padding digit is normally unimportant since the destination node will have allocated the Channel and it therefore knows how many digits are needed to address it. DATA FIELD - The data field is optional and is of variable length up to 128 bytes maximum. This field carries application data or a message. Except for the messages defined later the contents of the data field are not relevant to this invention. CRC FIELD - The CRC field is always present and is two bytes long. This field is a standard Cyclic Redundancy Check of the Control, Address and Data fields. The destination must not regard any of the fields as valid until the CRC field has been received and checked. This will normally require each port to buffer at least one frame in the receiver. Since the control and address field may have changed, the router in a dual-port or switch node must regenerate the CRC field when forwarding a frame.

0022The maximum lengths of the address and data fields are chosen as a balance between network size, communication efficiency and implementation cost.

LAYERS

0023There are two layers in the serial link, a transport layer and an upper-level protocol. The transport layer defines the following functions: <ul id="ul0002" list-style="none"><li>o The protocol, eg. framing, flow control and addressing;</li><li>o Link management, eg. buffering, port states, resets, configuration and error recovery; and</li><li>o The physical medium, eg. encoding, modulation, clocking, line drivers/receivers, connectors and cables.</li></ul>    Each implementation of the serial link is responsible for defining: <ul id="ul0003" list-style="none"><li>o The data rate that is supported, ie. 10 MB/s or 20 MB/s or both; and</li><li>o The configuration of frame buffers in each port.</li></ul>    The following functions are defined by the relevant upper-level protocol: <ul id="ul0004" list-style="none"><li>o The interpretation of the user-defined characters.</li><li>o The content of the data field in application frames, eg. commands, status and data.</li></ul> The upper-level protocol initiates data transfers by exchanging message frames between the source node and the destination node. The destination node allocates a Channel to receive the data frames and it indicates the number of bytes that it can currently accept.

RESPONSES

0024To implement the necessary flow control, the destination sends the source two RESPONSES for each frame it receives, ACKNOWLEDGEMENT - a pair of consecutive ACK protocol characters and RECEIVER READY - a pair of consecutive RR protocol characters.

0025These protocol characters are used in pairs to protect the responses from being manufactured by transmission errors. A node only acts on a Response when it has received both characters of the pair without any other intervening characters.

0026In a network this protocol operates on each serial link independently. Responses are never forwarded by a router.

FRAME TYPES

0027The transport layer distinguishes three types of frame: CONTROL FRAMES - These are used for resets. The length of the data field must be zero, otherwise the receiving node will reject the frame. Control frames are actioned immediately by the destination node. They may be sent when the transmitting port is in Privileged or Normal mode. PRIVILEGED FRAMES - These are used by the transport layer for configuration and error recovery. They may be sent when the transmitting port is in Privileged or Normal mode. APPLICATION FRAMES - These are used only by the upper-level protocol. The content of the data field is of no relevance to the transport layer. When a port is in the Privileged mode the transmitter discards application frames.

0028The contents of the data field of each frame can consist of a command, status or data. For each command a node can be classified as either an INITIATOR, that is, the node that issued the command, or a TARGET, that is, the node that received the command. PORT MODES - A port may operate in either NORMAL or PRIVILEGED mode. Normal mode allows the port to send any type of frame over the link. Normal mode is entered from Privileged Mode when a port receives a Set_normal_mode message (described later). In Privileged mode the port will only send Control and Privileged frames to the remote node. Application frames are discarded by the transmitter. Privileged mode is entered from Normal mode when there is a link error which cannot be recovered by the Link ERP. It is also entered when a port is reset. DISABLED STATE - A port is DISABLED when it is reset (for example at power-on) or when the node has suffered a catastrophic internal error. In this state all communication is disabled, except for the reception of reset control frames. The port transmitter indicates the Disabled state by sending DIS characters continuously on the link. If the port has been reset then it will normally exit the Disabled state automatically.

MASTER

0029Exactly one Initiator in the network must be nominated as the Master. The application may select the Master itself. Alternatively the Master can be elected automatically by the transport layer during configuration. For example, the Initiator with the highest Unique_ID could be elected.

0030During the configuration process the Master informs all other nodes of its location by issuing a Privileged message to each node in turn. Subsequently each node reports an asynchronous event by sending a Privileged message to the Master. (A typical event would be an error that cannot recovered by the transport layer.) The Master sends a Privileged message to alert each other Initiator and it coordinates the recovery actions.

0031If the Master node fails or becomes disconnected then a new Master must be nominated to replace it. The new Master should then inform every other node of its location.

CONFIGURATION

0032UNIQUE_ID - All Initiators and switches are assigned a Unique_ID when the node is manufactured. The Unique_ID is typically stored in EPROM (Eraseable Programmable Read Only Memory). It consists of a 4-byte vendor identification followed by a 4-byte node identification assigned by the manufacturer. Both identifications are unsigned binary integers. The Unique_ID is used during error recovery to identify the commands that were issued by a particular Initiator. PROCEDURE - Each potential Initiator must perform a configuration process to determine the other nodes that are present and their path address(es). CONFIGURATION TABLE - In the configuration process every Initiator constructs a Configuration table which has an entry for every other node. The entry contains a description of a node (how many ports it has, which are operational, and it's UNIQUE_ID) and its Path address(es) from the Initiator.

0033Each Initiator configures the whole network when it powers on. An Initiator must also perform an additional partial configuration when a new link is connected to the network. In this case each Initiator will be alerted by a Privileged message, as described later.

0034If there is a link error that cannot be recovered by the transport layer each Initiator is also alerted by a Privileged message. If the error is permanent (for example the link has been disconnected) each Initiator unconfigures the path(s) to those nodes beyond the error by deleting them from its Configuration table. INITIATOR TABLE - During the configuration process every Target builds an Initiator table. Each table entry contains the Unique_ID of an Initiator and a return address from the Target to that Initiator. If an Initiator is using alternate Paths to the same Target then the table will contain one entry for each Path.

0035The Initiator table is used to quiesce outstanding commands during error recovery.

ERROR RECOVERY

0036The transport layer of the link includes a Link Error Recovery Procedure (LINK ERP) that attempts to recover errors by retransmitting the last 1 or 2 frames.

0037The strategy for recovering errors in a complex network with multiple Initiators will now be described. The strategy ensures data integrity and minimises the impact to other operations. For example, an error will not result in bad data being written to a disk drive. Also an error affects only the commands, Initiators and Targets currently using the failing link or node.

LINK ERRORS

0038HARDWARE ERROR - This error is indicated when a port detects an internal hardware error, for example a parity check. LINE FAULT - This error is indicated when the line driver or receiver detect an invalid voltage and the port is not in the Disabled state. The cable may be open or short circuit or the remote node may be powered off. ACK TIME-OUT - This error is indicated when the source port does not receive an ACK response within the specified time after transmitting the trailing FLAG of a frame other than Reset.

RECEIVER ERRORS

0039LOSS OF SYNCHRONISATION - This is indicated when the clock recovery circuits in the receiver detect a synchronisation error. CODE VIOLATION - This error is indicated if the receiver has not detected a 'loss of synchronisation' error and it decodes a character which is not in the defined alphabet or a character which causes a disparity violation. PROTOCOL ERROR - This error is indicated if none of the receiver errors above has occurred and a port receives an incorrect sequence of valid characters as listed here: <ul id="ul0005" list-style="none"><li>1. A short frame with less than 4 data characters between 2 FLAG characters. This may be caused by noise corrupting or manufacturing a FLAG.</li><li>2. A Privileged or Application frame and no buffer is available, that is, when RR_pending is set.</li><li>3. An isolated RR character. One half of the link will hang if an RR response is lost without any errors being detected, for example if both RR characters are changed to FLAG characters while the link is idle. This is extremely unlikely and therefore no recovery is provided in the transport layer. Instead the application should provide a time-out for each operation in progress.</li><li>4. An unexpected ACK response, that is, when Waiting_for_ACK is reset.</li><li>5. An isolated ACK character. If an ACK response is corrupted then the transmitter will also detect an ACK time-out.</li><li>6. A NUL character with no intervening data character since the last FLAG.</li><li>7. An ABORT character with no intervening data character since the the last FLAG.</li><li>8. An ABORT character that is not immediately followed by a FLAG.</li></ul> CRC ERROR - This error is indicated if a received frame has bad CRC, the frame has not been aborted and none of the receiver errors above has occurred. SEQUENCE ERROR - This error is indicated when a received frame has frame sequence number not equal to received sequence number, the frame has not been aborted, the frame is not a Control frame and none of the receiver errors above has occurred. A previous frame has probably been lost. FRAME REJECT - This error is indicated when a frame is received correctly with none of the receiver errors above, the frame has not been aborted, but the frame is unacceptable for any of the following reasons: <ul id="ul0006" list-style="none"><li>1. The frame contains more than 137 data characters. Note that the receiver must continue to accumulate the CRC until the trailing FLAG in order to verify that there hasn't been a transmission error, for example a corrupted FLAG.</li><li>2. The frame length is otherwise unacceptable to the implementation, for example a message frame is too long.</li><li>3. The control field is invalid.</li><li>4. The address field specifies a destination that is not implemented or currently invalid.</li><li>5. The length of the data field in a Control frame is not zero.</li></ul> Errors in this class are generally due to programming, synchronisation or compatibility problems.

LINK ERROR RECOVERY PROCEDURE (ERP)

0040An Error Recovery Procedure (ERP) is defined for the link to recover link errors at the frame level. This has the following benefits: <ul id="ul0007" list-style="none"><li>1. The upper-level protocol is simplified since recovery is transparent if it is successful.</li><li>2. There is normally no need to terminate any operations when an error occurs. However a device with limited buffering may overrun as a result of the extra time taken by the Link ERP.</li><li>3. There is no uncertainty about the state of the application in the remote node.</li><li>4. The compatibility of different link implementations is enhanced.</li></ul> It is expected that the Link ERP will normally be implemented in firmware running on the node processor. However the functions could conceivably be performed by a hardware finite state machine if performance is critical. If the ERP determines that a TRANSMISSION error occurred then it attempts to recover the error itself. If recovery is successful the Link ERP terminates and the upper-level protocol continues unaware of the error. The ERP cannot recover some errors transparently, for example hardware errors or permanent line faults. The ERP has been carefully designed so that both nodes will always recognise an unrecoverable error and remain synchronised. In these cases the ERP exits. Where possible, recovery is then attempted by command retry, as described later.

PRINCIPLES

0041The basic principles of the Link ERP are as follows: <ul id="ul0008" list-style="none"><li>1. Only the failing link invokes the Link ERP. Other links in the network are not involved.</li><li>2. The Link ERP recovers Privileged and Application frames only. It does not recover Control frames.</li><li>3. In normal operation the transmitter does not discard a Privileged or Application frame until it has received an ACK response. This indicates that the frame has been received correctly by the destination port. Therefore when an error occurs the affected frame(s) are still available for retransmission without reference to the upper-level protocol.</li><li>4. When an error is detected both ports, invoke the Link ERP and exchange status by means of Link Resets.</li><li>5. Recovery is performed separately for each line. Each port is responsible for recovering frames that were lost on its outbound line. Because the transmitter is allowed to start sending another frame before it receives an ACK response, up to 2 frames may need to be retransmitted.</li><li>6. Before restarting communication the Link ERP forces the port into the Disabled state. This synchronises the ERP's in both nodes and allows an orderly restart with the same mechanisms that are used at power-on.</li><li>7. The link protocol and ERP are designed to minimise the chances of losing or duplicating any frames when an error occurs. However the upper-level protocol should protect against these events wherever possible. For example, the byte count can be checked for zero at the end of a data transfer and time-outs can be used to detect lost messages.</li></ul>

LINK STATUS BYTE

0042During error recovery the Link ERP in each node builds a Link Status Byte and sends it to the other node in the address field of a Link Reset frame. The link status byte is defined as follows. <tables id="tabl0001" num="0001"><img file="EP0576136A2_D0002.tif" /></tables> H/W ERROR - When set to 1b, this bit indicates that the port detected an internal hardware error. LINE FAULT - When set to 1b, this bit indicates that the line driver or receiver detected a fault on the line. It is provided for diagnostic information only and it is not referenced by the Link ERP in the destination node. ACK T/O - When set to 1b, this bit indicates that the transmitter timed-out while waiting for an ACK response. It is provided for diagnostic information only and it is not referenced by the Link ERP in the destination node. RECEIVER ERRORS - This field contains a 3-bit code to identify the first error detected by the receiver: <tables id="tabl0002" num="0002"><table frame="all"><tgroup cols="2" colsep="1" rowsep="0"><colspec colnum="1" colname="col1" colwidth="78.75mm" /><colspec colnum="2" colname="col2" colwidth="78.75mm" /><tbody valign="top"><row><entry namest="col1" nameend="col1" align="right">0 0 0</entry><entry namest="col2" nameend="col2" align="left">No error</entry></row><row><entry namest="col1" nameend="col1" align="right">0 0 1</entry><entry namest="col2" nameend="col2" align="left">Loss of synchronisation</entry></row><row><entry namest="col1" nameend="col1" align="right">0 1 0</entry><entry namest="col2" nameend="col2" align="left">Code violation</entry></row><row><entry namest="col1" nameend="col1" align="right">0 1 1</entry><entry namest="col2" nameend="col2" align="left">Protocol error</entry></row><row><entry namest="col1" nameend="col1" align="right">1 0 0</entry><entry namest="col2" nameend="col2" align="left">CRC error</entry></row><row><entry namest="col1" nameend="col1" align="right">1 0 1</entry><entry namest="col2" nameend="col2" align="left">Sequence error</entry></row><row><entry namest="col1" nameend="col1" align="right">1 1 0</entry><entry namest="col2" nameend="col2" align="left">Frame reject</entry></row><row rowsep="1"><entry namest="col1" nameend="col1" align="right">1 1 1</entry><entry namest="col2" nameend="col2" align="left">Reserved</entry></row></tbody></tgroup></table></tables> When two or more errors occur simultaneously the lowest number is reported. RSN - This is the Receive Sequence Number for the last Privileged or Application frame that was acknowledged by the port. It is needed by the Link ERP in the remote node.

DEFINITION OF THE LINK ERP

0043To facilitate cross-referencing, when the the ERP fails each 'exit' is identified by a name in the description below. The first (or only) port that detects the error invokes its Link ERP. The Link ERP then proceeds as follows: 1. The ERP waits until the transmitter has finished sending the current frame, if any. Optionally the transmitter may choose to abort the current frame. 2. The ERP then builds the Link Status Byte by reference to the hardware. 3. If the line driver or receiver has detected a line fault then the ERP tries to reset the error. If this fails then the ERP exits indicating 'Permanent line fault'. 4. The ERP checks whether the receiver is detecting DIS characters. If so, the remote port may have entered the Disabled state due to a catastrophic error. The ERP exits indicating 'Remote port Disabled'. 5. The ERP constructs a Link Reset frame (see below) containing the Link Status Byte. It then sends two successive Link Reset frames to the remote node. Repeating the Link Reset in this way allows for either frame to be corrupted by noise. The remote port should now enter the Check state, if it has not already done so. Either way it will invoke its Link ERP and return two Link Resets containing the remote Link Status Byte. Link Reset frame format - <tables id="tabl0003" num="0003"><table frame="all"><tgroup cols="2" colsep="1" rowsep="0"><colspec colnum="1" colname="col1" colwidth="78.75mm" /><colspec colnum="2" colname="col2" colwidth="78.75mm" /><tbody valign="top"><row><entry namest="col1" nameend="col1" align="left">Control field</entry><entry namest="col2" nameend="col2" align="left">Message_code = 0Ch</entry></row><row><entry namest="col1" nameend="col1" align="left">Address field</entry><entry namest="col2" nameend="col2" align="left">Link Status Byte</entry></row><row><entry namest="col1" nameend="col1" align="left">Data field</entry><entry namest="col2" nameend="col2" align="left">Must be absent</entry></row><row rowsep="1"><entry namest="col1" nameend="col1" align="left">CRC field</entry><entry namest="col2" nameend="col2" align="left">Must be correct</entry></row></tbody></tgroup></table></tables> Link reset is confined to a single link. It is never propagated from one link to another. 6. The ERP checks whether a Link Reset has already been received from the remote node. If not the ERP starts a time-out and waits to receive a Link Reset. If no Link Reset has been received within 1 ms after the local node sent its second Link Reset then the ERP exits indicating 'Link Reset failed'. 7. The implementation must protect against the ERP looping if there is a permanent error. The following is an example of one method that can be used. Each invocation of the ERP increments a retry counter that is reset to zero periodically by a timer. If the number of retries in one period of the timer exceeds some maximum value then the ERP exits indicating 'Retry limit exceeded'. This scheme also protects against excessive use of the ERP in the event of severe external noise. 8. If either port has detected a hardware error then the ERP exits indicating 'Hardware error'. 9. If either port has indicated 'frame reject' then further communication may be meaningless. The ERP exits indicating 'Frame rejected'. 10. Otherwise the ERP calculates the number of outbound frames for which an acknowledgement is outstanding. The ERP also calculates the number of outbound frames for which the local port is expecting an acknowledgement but which have not been received by the remote port. If either of these checks fails the ERP exits indicating 'Invalid retry status'. 11. Otherwise the ERP arranges to resend the lost frames. 12. Those outbound buffers that do not need to be retransmitted must now be discarded. 13. If the port has received a frame containing any of the errors listed in "Receiver errors" then the appropriate inbound buffer must be discarded. Otherwise the ERP does not need to deal with the inbound buffers. If any are full they will be emptied by the upper-level protocol. 14. The ERP disables the port and resets all of the latches for hardware errors, ACK time-out and receiver errors. 15. The ERP waits until the remote port enters the Disabled state, as indicated by the receiver detecting DIS characters. This is required to synchronise the two Link ERP's and prevent the transmitter sending a frame while the remote port is not in the Normal mode. If the receiver does not detect DIS characters within 1 ms after the local port is Disabled then the ERP exits indicating 'Time-out waiting for Disabled state'. The remote port may be indicating an unrecoverable error. 16. Otherwise the ERP enables the port. 17. The ERP waits for the port to become Ready. This indicates that the remote port has completed its recovery. If the link does not become Ready within 1 ms after the local port entered the Enabled state then the ERP exits indicating 'Time-out waiting for Ready state'. This may indicate that the remote node has powered-off or suffered a catastrophic error. 18. Otherwise the ERP terminates successfully.

Non Link ERP error recovery

0044The actions each node should take if the Link ERP exits unsuccessfully will be described as well as a set of primitives and some procedures for dealing with events that are outside the scope of the Link ERP. These events are as follows: <ul id="ul0009" list-style="none"><li>A) The Link ERP fails. This could be a transient unrecoverable error or a permanent error such as a disconnected link.</li><li>B) A Target node does not respond to a command.</li><li>C) A router receives a frame which is addressed to a port that is not operational.</li><li>D) A node receives an invalid message and it does not know the return address.</li><li>E) A new link is connected to the network.</li></ul>

0045For the first 4 events (A-D) the Initiators will typically terminate the affected commands and retry them, using an alternate path if necessary. In the last case (E) no commands should be affected.

Description of the privileged messages

0046The following sections define the messages to support error recovery. In all cases the control field indicates a frame type of 'Privileged'. SET_MASTER - This message is sent from the Master to every other node in the network during the Configuration process. It specifies a Return_address and a Tag to be used when the node wants to send the Master a Link_alert message. The destination node records this information and returns a Response message. <tables id="tabl0004" num="0004"><img file="EP0576136A2_D0003.tif" /></tables><dl id="dl0001"><dt>MESSAGE_CODE</dt><dd>This byte identifies the message as 'Set_master'.</dd><dt>TAG</dt><dd>This 2-byte field is returned in the Response message. The same Tag is also used in a Link_alert message if the node subsequently reports a link state change. The Tag is assigned by the Master and it must be unique among the Tags that are currently active from the Master. It remains active until the node receives another Set_master message.</dd><dt>RETURN_ADDRESS</dt><dd>This 4-byte field specifies the value that should be placed in the address field of the resulting Response message and any subsequent Link_alert. If a node receives Set_master and it has a port in Privileged mode then it should send a Link_alert to the Master BEFORE sending the Response for Set_master. A node only stores the Return_address and Tag for the most-recent Set_master that it has received.</dd></dl> RESPONSE - This message is returned to acknowledge the Set_master, Master_alert, Quiesce and Set_normal_mode messages. Response is sent on the same port that received the original message. <tables id="tabl0005" num="0005"><img file="EP0576136A2_D0004.tif" /></tables><dl id="dl0002"><dt>MESSAGE_CODE</dt><dd>This byte identifies the message as 'Response'.</dd><dt>RETURN_CODE</dt><dd>This byte is set to 00h if the original message was processed successfully. Any other value indicates that the requested function could not be completed.</dd><dt>TAG</dt><dd>This 2-byte field is copied from the original message. It identifies the message that is being acknowledged. The address field in Response is obtained from the Return_address field in the message being acknowledged.</dd></dl> LINK_ALERT - A node sends this message to inform the Master of an asynchronous event on one of its ports. The Master does not respond directly. <tables id="tabl0006" num="0006"><img file="EP0576136A2_D0005.tif" /></tables><dl id="dl0003"><dt>MESSAGE_CODE</dt><dd>This byte identifies the message as 'Link_alert'.</dd><dt>TYPE</dt><dd>This byte is coded to indicate the event. The main types are as follows: <ul id="ul0010" list-style="none"><li>o Port now operational. This indicates that a new link has been connected.</li><li>o Addressed port not operational. This indicates that the router received a frame that could not be forwarded.</li><li>o Message reject. This indicates that the node received an invalid message and it does not know the return address, for example Message_code is invalid.</li><li>o Permanent fault. The Link ERP failed because, for example, the link has been disconnected.</li><li>o Unrecoverable error. This indicates a transient error that could not be recovered by the Link ERP.</li><li>o Remote port not responding. This indicates that the remote port did not respond during the Link ERP.</li><li>o Remote port disabled. The Link ERP was entered because the port received DIS characters. For example, the remote node may have been reset or it may have suffered a catastrophic internal error.</li></ul></dd><dt>TAG</dt><dd>This 2-byte field contains the Tag specified by the most recent Set_master message. It allows the Master to determine which node has sent the Link_alert.</dd><dt>PORT</dt><dd>Bits 3:0 contain an unsigned integer to identify the affected port.</dd></dl> The address field in a Link_alert message is obtained from the Return_address field in the most recent Set_master message. MASTER_ALERT - This message is sent from the Master to each other Initiator. It has 2 uses: <ul id="ul0011" list-style="none"><li>1. To forward a Link_alert for an asynchronous event.</li><li>2. To indicate that both ports of a link have been put into Normal mode, for example following error recovery.</li></ul> In both cases the Initiator returns a Response message to the Master. <tables id="tabl0007" num="0007"><img file="EP0576136A2_D0006.tif" /></tables><dl id="dl0004"><dt>MESSAGE_CODE</dt><dd>This byte identifies the message as 'Master_alert'.</dd><dt>TYPE</dt><dd>If the Master_alert is forwarding a Link_alert then this byte is copied from the corresponding Link_Alert. In this case the destination Initiator should Quiesce any commands that were using the specified Path before returning the Response. If the Master is indicating that both ports of a link have been returned to Normal mode then this byte is set to FFh.</dd><dt>TAG</dt><dd>This is a 2-byte field assigned by the Master and returned in the Response from the destination Initiator. It must be unique among all the Tags currently active from the Master.</dd><dt>RETURN_ADDRESS</dt><dd>This 4-byte field specifies the value that should be placed in the address field of the Response message.</dd><dt>PATH</dt><dd>This 4-byte field specifies the address of the node that generated the Link_alert, relative to the Initiator that received Master_alert.</dd><dt>PORT</dt><dd>Bits 0:3 are copied by the Master from the corresponding Link_Alert message.</dd></dl> QUIESCE - This message is sent from an Initiator to a Target during error recovery to quiesce all commands from a specified Initiator. The Target returns a Response message after it has quiesced the affected commands. The Target does not return status for the quiesced commands. <tables id="tabl0008" num="0008"><img file="EP0576136A2_D0007.tif" /></tables><dl id="dl0005"><dt>MESSAGE_CODE</dt><dd>This byte identifies the message as 'Quiesce'.</dd><dt>TAG</dt><dd>This is a 2-byte field assigned by the Initiator and returned in the Response from the Target.</dd><dt>RETURN_ADDRESS</dt><dd>This 4-byte field specifies the value that should be placed in the address field of the Response message.</dd><dt>UNIQUE_ID</dt><dd>This is the 8-byte Unique_ID of the Initiator whose commands are to be quiesced. The Target must search its Initiator table to convert the Unique_ID to aReturn_address before selecting the commands to be quiesced. Specifying the Initiator with a Unique_ID rather than a Return_address allows an Initiator to use an alternate path for the Quiesce if the original path is no longer available. It also allows the Master to issue a '3rd party' Quiesce on behalf of a missing Initiator.</dd></dl> SET_NORMAL_MODE - This message is sent by the Master to change a port from Privileged mode to Normal mode. The destination node returns a Response message. When the ports at both ends of a link have been placed in Normal mode the link can be used for Application frames. <tables id="tabl0009" num="0009"><img file="EP0576136A2_D0008.tif" /></tables><dl id="dl0006"><dt>MESSAGE_CODE</dt><dd>This byte identifies the message as 'Set_normal_mode'.</dd><dt>PORT</dt><dd>Bits 3:0 contain an unsigned integer which identifies the port to be changed to Normal mode.</dd><dt>TAG</dt><dd>This is a 2-byte field assigned by the Master and returned in the Response from the destination node. It must be unique among all Tags currently active from the Master.</dd><dt>RETURN_ADDRESS</dt><dd>This 4-byte field specifies the value that should be placed in the address field of the Response message.</dd></dl>

Recovery Procedures

0047This section shows how the previous concepts and Privileged messages are used during error recovery.

A) LINK ERP FAILS

0048This indicates that the error was unrecoverable by the transport layer. Both ports of the failing link enter Privileged mode and so their transmitters discard Application frames. This avoids frames backing up and blocking other traffic. It also prevents any further data from being transferred through the affected link and being written onto magnetic media.

0049Each node sends a Link_alert message to the Master, provided the Return_path specified by Set_master during configuration does not include the failing link. Thus the Master will receive 1 or 2 Link_alert messages.

Recovery then proceeds as follows:

0050<ul id="ul0012" list-style="none"><li>1. If the Link_alert indicates 'Remote port not responding' then the Master issues a reset control frame to the failing node immediately. The Master then unconfigures the affected link(s) and node(s). (If the failing node recovers after the reset then the adjacent node(s) will generate another Link_Alert indicating 'Port now operational'. This will cause the affected links and nodes to be reconfigured.) </li><li>2. If the Link_alert indicates 'Remote port disabled' the remote node may have been reset or it may have suffered a catastrophic internal error. In the first case the remote node will normally re-enable the port itself. In the second case the node may require to be reset. The Master waits up to 1 second to receive another Link_alert from the adjacent node indicating 'Port now operational'. This Link_alert indicates that the node has now recovered. If the Link_alert is not received the Master assumes the cause was a catastrophic error and it issues a reset control frame to the node. In this case the Master unconfigures the affected link(s) and node(s).</li><li>3. If the Link_alert indicates 'Permanent fault' then the Master also unconfigures the affected link(s) and node(s).</li><li>4. The Master issues a Master_alert to each other Initiator that remains in its Configuration table.</li><li>5. If the Master_alert indicates a permanent fault or a node has been reset then the other Initiators unconfigure the affected link(s) and node(s).</li><li>6. Each Initiator identifies those commands that were in progress over the failing link and it stops the associated outbound data transfers.</li><li>7. Each Initiator issues a Quiesce message to each Target that was executing an affected command, providing the Target remains configured (possibly by using an alternate path). If the Master determines that a previous Initiator has been removed from the network by the error then it sends a '3rd party' Quiesce to ALL remaining Targets on behalf of the missing Initator. The Targets return a Response message for each Quiesce. Each other Initiator sends a Response message to the Master for the Master_alert message when all of its affected Targets have been quiesced. </li><li>8. If the link is still configured the Master sends a Set_normal_mode to each port. The Master waits for the Response messages for Set_normal_mode.</li><li>9. The Master sends a Master_alert message to each other Initiator to indicate that both ports are now in Normal mode. Each Initiator returns a Response.</li><li>10. If the link is still configured or there is an alternate path each Initiator reissues its affected commands.</li></ul>

B) TARGET DOES NOT RESPOND

0051An Initiator is expected to start an anti-hang timer for each command that it issues to a Target. The timer is stopped when the Initiator receives status indicating that the Target has finished processing the command. The timer protects against an undetected link failure in the path to the Target node or a software failure in the Target itself. If the timer expires before it is stopped then the Initiator should proceed as follows: <ul id="ul0013" list-style="none"><li>1. The Initiator issues a Privileged message to query each intermediate node in turn, starting with the adjacent node. If any node does not reply then that node is assumed to be hung. Otherwise the Target node is hung.</li><li>2. The Initiator issues a reset control frame to the node which is hung. This will disable all ports on that node.</li><li>3. The connected ports in the adjacent nodes will detect this, invoke the Link ERP and generate a Link_alert indicating 'Remote port disabled'. This will be handled as previously described.</li></ul>

C) ADDRESSED PORT NOT OPERATIONAL

0052A frame could be addressed erroneously to a router port that is not operational. This is handled as follows: <ul id="ul0014" list-style="none"><li>1. The node detecting the error sends a Link_alert to the Master indicating 'Addressed port not operational'. The port remains in Privileged mode.</li><li>2. The Master issues a Master_alert to each other Initiator specifying 'Addressed port not operational'.</li><li>3. Each Initiator terminates any affected commands and the associated outbound data transfers. Then it returns a Response.</li><li>4. If there is an alternate path each Initiator reissues its affected commands.</li></ul>

D) INVALID MESSAGE RECEIVED

0053If the destination node knows the return address (for example the message had an invalid parameter) then it returns a Response with a non-zero Return_code. Otherwise the destination node generates a Link_alert specifying 'Message reject'. This is handled similar to the case of 'Addressed port not operational' above except that the port remains in Normal mode.

E) NEW LINK CONNECTED

0054When a new link is connected to the network a port on one of the existing nodes will become operational: <ul id="ul0015" list-style="none"><li>1. The node sends a Link_alert to the Master specifying 'Port now operational'.</li><li>2. The Master configures the new node(s).</li><li>3. The Master issues Set_master to the new node(s). Each node returns a Response.</li><li>4. The Master issues Set_normal_mode to the port that generated the Link_alert and the other new port(s). Each port returns a Response.</li><li>5. The Master sends a Master_alert specifying 'Port now operational' to each other Initiator. Each Initiator returns a Response.</li><li>6. Every other Initiator configures the new node(s).</li></ul>

Examples

0055The error recovery method described above may be used in a variety of different applications, two examples of which are described below. It will be appreciated that the present invention can readily be used in other types of network. A string of dual-ported devices is particularly attractive for connecting I/O devices to a personal computer, as shown in Figure 7. Adapter 50 which will typically reside in the system unit of a personal computer is attached via link 51 to disk drive 52 which is in turn attached to disk drive 54 via link 53 which is in turn attached to printer 56 via link 55. The use of a string reduces the attachment cost per device and it avoids wiring congestion at the adapter. The use of the error recovery technique of the present invention prevents an error resulting in bad data being written to a disk drive or incorrect data being printed. Optionally the loop can be closed by provision of link 57 to provide increased bandwidth or a measure of fault-tolerance. An error only affects commands using the failing link or node, so with the closed loop all nodes apart from the failing one can still be accessed.

0056Figure 8 shows a typical network configuration that could be used as a high availability file server. High availability is important in such a shared system. This application also requires dual-ported disk drives, but this time the main reason for the second port is to provide a backup path in the event of a failure in the primary attachment path. Therefore in practice all serial disk drives will probably be dual-ported. In conjunction with disk arrays, dual-ported disk drives allow configurations with no single point of failure, as shown in Figure 8. In this configuration a pair of servers 60 and 62 are connected via dedicated links to both switches 64 and each port of the dual-ported disk drives 68, 70 72 and 74 is connected to one of the switches. The use of dedicated links to each drive allow full concurrent maintenance with no impact to the operation of other drives.