BACKGROUND OF THE INVENTION

The present invention relates to a method and apparatus for controlling the flow of data among a plurality of computing devices. More particularly it relates to a protocol for allowing an end-entity in a network computer to be placed in and removed from a temporary condition of flow control that is recognizable in real time by the other end-entities in the computer network.

An end-entity is the tasks or processes within a station which perform the information processing for a particular system in a local area network (LAN) computer environment.

Computer networks providing data communication channels between communicating end-entities in interconnected systems rely primarily on embedded software for protocols and services to support a reliable mode of behavior. Examples are: the TCP-IP and X.25 protocols used by the Department of Defense and the emerging International Standards Organization's (ISO) Open System Interconnection (OSI) Model targeted for new applications.

In all but the smallest LANs, the exclusive use of software introduces limitations in performance and flexibility of interconnectivity. For example, layered architectures based on the OSI Reference Model (ISO 7498-1984) rely on a connection mode of operation to provide reliable data communications. While the standards do not specifically identify an embodiment, state of the art implementations of the connection-mode set of protocols and services are nevertheless largely in software.

In conventional LANs a connection is required to be established prior to reliable communications in an OSI environment. The connection has three distinct phases:

(a) connection establishment;

(b) data transfer; and

(c) connection release.

A connection is the controlling mechanism set forth to provide not only reliable communications, but flow control between peer end-entities as well. In order to guarantee delivery of in-sequence data transmissions, with no lost or duplicated data messages, every end-entity pair desiring to communicate must first establish a connection. As a key part of the connection establishment, and in order to avoid congestion in the overall LAN, resources at all routers are set aside during each individual connection setup. The number of simultaneous connections allowed, in any application, is therefore a function of the resources available throughout the LAN. Unfortunately, the number of simultaneous connections required in many applications can quickly become prohibitive. Also, management of the limited connection resources is difficult, time-consuming, and is usually an additional requirement for end-entities.

Although the concept of a multi-endpoint connection is introduced in the OSI Reference Model, and again in the various layer standards themselves, guidelines for establishing connections between three or more simultaneous communicating entities have yet to be set forth. So, in a many-to-many application environment, compromises regarding individual flow control and performance are difficult to avoid.

LANs employing a partial connection of hardware offer an improvement over the conventional systems. The Prioritized Carrier Sense Multiple Access with Collision Detect (P-CSMA/CD) with Tack-on Acknowledgement (T-ACK) access method and apparatus described in U.S. Patent Nos. 4,536,877 and 4,584,679 includes a reliable datagram mechanism between stations in a LAN implemented primarily in hardware. A reliable datagram service as employed here is defined as a perfect channel: one that has no lost or duplicated data messages as a result of the transmission media, and one in which data messages sent from the transmitting entity, through the transmission media to the receiving entity, arrive in the order sent. The P-CSMA/CD with T-ACK access method also

provides station level flow control as a function of message priority and of the number of buffers currently available at the receiving station. It provides two levels of filtering: filtering based on destination address, and filtering based on priority of input data frame versus number of remaining receive buffers to handle the incoming frame. The filtering by priority may be viewed as station level flow control.

While the P-CSMA/DC with T-ACK mechanism provides a hardware connection-like or virtual circuit service between stations, it does not provide a mechanism to prevent one or more end-entities from monopolizing the resources available at that station; that is, there is a station-to-station level of flow control in the P- CSMA/CD with T-ACK protocol, but no entity-to-entity level of flow control.

Some LANs provide end-entity flow control in a higher level of software protocol as a means to equitably share the end system resources among end users. The mechanism used in these LANs relies on a broadcast control message transmitted to every sending station in the network to convey any state change for any destination end-entity in any end system. There are several disadvantages inherent in this approach:

(a) broadcast messages updating all end system flow control tables add to overhead and congestion;

(b) backup timers and individual query control messages are required, as the broadcast mode of data communications is not a reliable service;

(c) flow control tables in this protocol are global in nature, requiring the protocol entity component that is resident in every end system to track the current state of every end- entity in every other end system, regardless of the intention to ever send to that entity; and

(d) adding or deleting entities at an end station in this approach is not possible without updating globally distributed flow control tables — a costly and complex endeavor.

In other network systems congestion is managed by a central controller (see, for example, U.S. Patent No. 4,677,616 to Franklin dated June 30, 1987) or by node controllers (see U.S. Patent No. 4,475,192 to Fernow, et al. dated October 2, 1984).

These devices require additional hardware and do not substantially reduce the flow control management overhead.

Accordingly, it is an object of the present invention to provide end station control of the flow of data from end-entity to end-entity in a computer network.

It is a further object of the present invention to provide a method for reducing data flow congestion in a computer network by restricting the movement of flow control status information to communicating station pairs.

It is yet a further object of the present invention to provide a method for reducing data flow congestion by determining the availability of buffer space in the receiving end-entity and controlling the flow of data from the transmitting end-entity based on that determination.

It is another object of the present invention to provide an apparatus for reducing data flow congestion in which the receiving device determines its flow control status responsive to a data transmission from a transmitting device, and in which the transmitting device controls the flow of data to the receiving device responsively to the flow control status.

These and many objects and advantages will be readily apparent to one skilled in the art to which the present invention pertains from a perusal of the claims and the following detailed description of preferred embodiments when read in conjunction with the appended drawings.

THE DRAWINGS

Figure 1 is a functional block diagram of a prior art computer network in which the present invention may be used.

Figure 2 is a functional block diagram of the transmitting station acknowledgment handler of the present invention.

Figure 3 is a functional block diagram of the receiving station acknowledgment generator of the present invention.

DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS A. Standard Architecture

The present invention provides flow control between communicating end-entities in a computer network. A preferred embodiment of the invention utilizes an architecture based on the International Standards Organization (ISO) Open Systems

SUBSTITUTESHEET

Interconnection (OSI) Reference Model (ISO 7498-1984) having the following seven layers.:

Application — Serves as window between correspondent end- entities using OSI. Constitutes the sole interface between end station applications and the LAN. Presentation — Concerned with syntax or representation of data (may include services such as encryption) . Session — Controls a dialogue established between communicating end-entities (concerned with data checkpoint/restart problem, dialogue recovery, or change of turn) . Transport — Provides end-to-end transfer of data messages between communicating entities in open systems (message packetization and flow control) . Network — Controls routing of message packets to end systems worldwide. Datalink — Controls routing of message packets between stations. This layer is further subdivided into the Logical Link Control (LLC) and Media Access Control (MAC) sublayers. Physical — Provides mechanical, electrical, functional and procedural means by which bits are transferred between stations. The IEEE 802.3 standard Carrier Sense Multiple Access with Collision Detect (CSMA/CD) access method is a means by which two or more stations share a common bus transmission medium. This standard describes one type of media access method used in the Physical layer and the Media Access Control (MAC) sublayer of the Datalink layer in the OSI model.

The IEEE 802.3 standard is actually a family of specifications. The particular member of the 802.3 standard used in this embodiment is the 10BASE5 subset. This subset specifies that the transmission speed is 10 Mbits/sec, that the keying method is baseband (DC levels) , that the medium used is Ethernet coaxial cable, that the maximum cable length without repeaters is 500 meters, and that the maximum number of end stations allowed without repeaters is 100. Only one cable can be used.

SUBSTITUTESHEET

Messages to be transmitted under 10BASE5 are presented to the MAC sublayer from the Logical Link Control (LLC) sublayer of the Datalink layer. The MAC sublayer encapsulates the message data (LLC Data) with header and trailer information, forming a MAC frame. Frames sent by this access method are made up of a number of octets which are transmitted serially on the medium. Each MAC frame contains the following information:

Preamble — 7 octets of a fixed bit pattern (10101010) which allows receiving stations to synchronize with the incoming frame's timing. Start Frame Delimiter (SFD) — A one-octet, fixed-bit sequence (10101011) indicating the start of a frame. Destination Address — 6 octets specifying the physical address of the destination (receiving) end station. Source Address — 6 octets specifying the physical address of the source (transmitting) end station. Length — 2 octets specifying the length of the frame. LLC Data — Up to 1500 octets of data. Note that this data may include header information used in higher layers of the protocol. Frame Check Sequence (FCS) — A four-octet Cyclical

Redundancy Check (CRC) computed for the frame as a function of the contents of all fields except the preamble, SFD, and FCS. All of the above fields, with the exception of the LLC Data field, which is created by an end-entity, are added by the MAC sublayer for transmission in this standard protocol.

To transmit, a station waits (defers) for a quiet period on the medium (no other station is transmitting) and then sends the intended message in bit serial form. The transmitting station continues to monitor the physical medium for interference from other sending stations while transmitting. If transmission is completed without contention, then a successful status is returned to the LLC sublayer. The only error status returned from this MAC service is maximum collisions (currently set to 16 in 10BASE5) .

At each station, the arrival of a MAC frame causes the receiving hardware to respond by synchronizing with the incoming preamble. After receipt of the FCS, the frame's Destination Address field is checked to decide whether the frame is to be received by this station. If so, the rest of the fields are brought in and the frame is checked for correctness. A frame is incorrect if it is too short, too long, not an integer number of octets, or if it contains an incorrect CRC in the FCS field. Tw or more stations transmitting simultaneously (a collision) will also result in the creation of an incorrect frame, known as a frame fragment. Valid LLC Data fields are presented to the Logical Link Control sublayer of the Datalink layer for reading and further processing in the destination end-entity.

The MAC sublayer continually monitors the physical medium for traffic. Whenever the medium is busy, the MAC sublayer defers to the passing frame by delaying any pending transmission of its own. After the medium goes idle, the MAC sublayer continues to defer for a proper Interframe Spacing (9.6 microseconds in 10BASE5) to ensure that effects of medium propagation delay and hardware delays at receiving stations are factored into the medium idle (Carrier Sense) decision. Then, if a frame is ready to be sent, transmission begins.

If the frame still collides with that of another station it will be detected on hardware (Collision Detect) . To enforce the collision, each transmitting station intentionally sends a few additional bytes (jamming) to ensure propagation of the collision throughout the system. The station then remains silent for a random amount of time (backoff) before attempting to transmit again. It is possible for repeated collisions to occur in a heavily loaded system. Since repeated collisions indicate a busy medium, the MAC sublayer attempts to adjust to the medium load by expanding the interval from which the random backoff time is selected.

At all stations, the bits resulting from a collision are received and decoded just as are the bits of a valid frame. Fragmentary frames received during collisions are distinguished from valid transmissions by the MAC sublayer by either an incorrect FCS field (bad CRC) or a short frame (802.3 specifies

a minimum frame size) . Since collisions are expected occasionally in 802.3, these frame fragments are simply discarded with no other action required. B. Enhanced Architecture

The present invention contains an enhanced Carrier Sense Multiple Access/Collision Detection (CSMA/CD) protocol designed around the 10BASE5 CSMA/CD media access method specified in IEEE 802.3. The enhancements are:

(a) the addition of a small hardware-generated acknowledgment frame called a TACK-ON Acknowledgment (T-ACK) ; and

(b) additional fields in the MAC frame.

The hardware generated T-ACK (see aforementioned U.S. Patent Nos. 4,536,877 and 4,584,679) contains status information sent by the receiving station back to the sending station at the completion of the transmitted frame. This feature is implemented by making use of a portion of the interframe gap (thereby extending it) to transmit the acknowledgement. Since no other station is allowed to transmit during this period, collisions should not occur. Since only the sending station is expecting the acknowledgment, destination and source address fields are not required and the size of the frame can be quite small. The T-ACK consists of:

Preamble and SFD — Identical in structure to the Preamble and SFD in the MAC frame previously defined; Status — a one-octet status field currently containing only three bits of significant information (8 states) ; and FCS - a two-octet FCS using the CRC-CCITT international standard generator polynomial. The other enhancement is the addition of fields to the MAC frame for end-entity flow control. The MAC frame to be transmitted in the present invention is identical to the 802.3 MAC frame with three additional extra fields incorporated. These additional fields are:

Sequence number — a single-octet field containing the sequence number for the transmitted frame. Used in maintaining in-sequence frames in a multimedium environment.

Priority — a single-octet field containing the message priority of the transmitted frame.

Logical Address — A two-octet field uniquely identifying the destination end-entity of the transaction in the receiving station. The additional MAC frame header fields and the status contained in the T-ACK frame provide the following services:

1) Virtual Circuit Service — The addition of the T-ACK provides the mechanisms for a reliable (virtual circuit) service.

2) Priority — A priority mechanism indicating a quality of service expected to be provided by the underlying protocol, for each message sent.

3) Flow Control — The MAC sublayer, in conjunction with upper layer protocol, provides end-entity flow control at the media level.

4) Multiple Media — Provisions for additional media. Message (Virtual Circuit Service) reliability is ensured at the media level, by the addition of the T-ACK and the sequence number field. Message reliability means that there are no lost or duplicated messages and that a stream of messages sent between any two stations will remain in the original order of transmission. Fast sending stations are prevented from overrunning slower receiving stations.

The T-ACK contains status information informing the sending station as to the success or failure of each transmission. If the receiving station rejects the incoming frame, for any reason, it conveys this information back to the sender via the T-ACK. The sending station then responds by resending the frame.

A level of determinism is added to the transmission access method by the establishment of priority levels on a message-by- message basis. Eight priority levels are available for use; seven are available to sending end-entities, and one is reserved for internal network management services. The priority of a

SUBSTIT T

particular message may be established by the user of the sending end-entity and passed in the Datalink layer.

At the transmitting station, the MAC sublayer adjusts the value of the 9.6 microsecond interframe gap timer by lengthening it in increments of 9.6 microseconds per priority level. So a message to be sent at priority level seven will be deferred for a much longer period than a higher priority message before beginning a transmission. Transmitting stations initiate a final carrier sense operation prior to transmitting (look before leap) and defer if a higher priority frame has already acquired the cable.

At the receiving station, the total number of receive buffers available for receipt of frames is distributed on a priority basis. Using the priority field in the MAC header, the receiving station hardware either accepts or rejects the incoming frame based on the number of remaining buffers in the receive buffer pool. Higher priority messages are allocated a larger share of the overall receive buffer pool. If a receiving station rejects an incoming frame for lack of buffers at that frame's priority level or below, then the receiving station will indicate this to the sender by returning a "NO BUFFERS" status in the T- ACK status field. The sender will then defer before sending messages at that priority level, or lower, allowing the receiving station to work off the load.

End-entity flow control is made possible by the addition of the T-ACK, and the logical address field in the MAC frame.

At the transmitting station, the MAC sublayer derives the value to be placed in the logical address field of the MAC header from the service access point address of the destination end- entity. This derivation algorithm uses maps and compresses the overall address of the destination end-entity into an address in the destination end system. Mapping is from an address unique within the entire LAN into an address unique only within the destination end system.

At the receiving station the MAC sublayer maintains the current state of each of its embedded end-entities. There are three possible states for these end-entities to be in: detached (or nonexistent) , attached and ready to receive, or attached and

in flow control. As a station is powered up, every end-entity address is mapped into the detached state in the MAC sublayer hardware. As end-entities are activated, the MAC sublayer is commanded to activate them at the media level. As end-entities enter and exit flow control, the MAC sublayer hardware is updated by commands from upper level protocol to reflect the current state.

The receiving station accepts or rejects an incoming MAC frame based on the current state of the locally resident end- entity pointed to by the logical address field in the frame. In either case, the sending station is notified via the T-ACK. In the case of a rejection, the sending station defers from sending to that destination entity until: (a) normal exit (notification by broadcast from the receiving station that end-entity flow control is removed) , or (b) time-out retry (end of time-out countdown started at the time the frame was enqueued) . The sending station also notifies upper layer protocol to allow back pressure to be applied to the local users, thereby avoiding congestion in the local BIU.

The apparatus of the present invention may use multiple media, such as a dual cable configuration. A selection process, such as a round-robin scheme may be employed to that end.

The services provided to the end-entities by the upper layer protocols are accessed by a set of library routines available in the Application layer. End-entities that communicate on the LAN contain a component of the Application layer built in at link time. There are basically two classes of services:

(a) the network management services; and

(b) the communication services.

The network management services allow end-entities to attach (announce themselves to the network) , detach (remove themselves f ^* om the network) , and perform directory lookups of other end- entities for purposes of communicating. An end-entity must be attached prior to sending or receiving data communications. This provides an access point to the LAN and gives other end-entities the opportunity to look up and communicate with this newly attached end-entity. The communication services provide end- entities with the basic sending and receiving capabilities.

SUBSTITUTESHEET

The upper layer protocol in the end station, using the underlying MAC sublayer flow control services, provide the flow control between each receiving end-entity and all other transmitting end-entities. The portion of the protocol related to data transmission is in the sending host, and the portion of the protocol related to data reception is in the receiving host.

In every participating host, there is a network configuration database. This database contains a set of parameters used to tune the network. This parameter set includes a minimum and maximum threshold for the number of receive buffers waiting for _. an end-entity. The parameters are set by the LAN manager based on the total number of buffers in the local receive buffer pool (a parameter in the database) and the maximum number of expected end-entities to be simultaneously attached to the network (also a parameter) .

When a message is sent to an end-entity, the current number of messages in the entity's queue is compared against the upper level threshold in the receiving host. If this threshold is crossed, the receiving host sends a control primitive to the MAC sublayer, placing this end-entity into flow control. No further data communications for this end-entity are allowed to enter this end station. As the end-entity removes data elements from the queue (via a component of the Application layer resident in the end-entity's task space) the lower threshold is checked against the current queue size. When the lower threshold is crossed, the MAC sublayer is commanded to remove the end-entity from flow control. This built-in hysteresis is designed to prevent thrashing.

Once an end-entity is in flow control status, transmitting stations attempting to transmit to this end-entity are notified via a "FLOW-CONTROL" status in the T-ACK. The sending host in the transmitting station prevents further communications to the end-entity in flow control status. When the receiving end- entity comes out of flow control, all stations are alerted with a broadcast message, and normal data communications may resume. C. Operation

With reference now to the figures, the operation of the present invention will be further described.

SUBSTITUTESHEET

A computer network in which the present invention may be used is illustrated in Figure 1 wherein a plurality of transmission media 10 are connected to a plurality of bus interface units 20 such as in a local area or metropolitan area network. The transmission media may be any suitable electronic transmission media including such media as twisted pair wire, high speed busses, fiber optic cables, coaxial cable, or radio frequency (RF) carrier waves.

Each of the bus interface units 20 interconnects an end station 22 to the plurality of transmission media 10. The end station 22 can be any conventional computer or computer-based device, such a work station, printer, or memory unit. Messages are generated at one of the end stations 22 and relayed through the associated bus interface unit 20 for forwarding to a second end station 22 through its associated bus interface unit 20. The message is propagated along one of the plurality of transmission media 10 and is available for receipt by any of the bus interface units 20 connected to the transmission medium 10 along which the message is propagating. The receiving bus interface unit 20 buffers and relays the message from the transmission medium 10 to the end station 22. Each end station includes one or more end-entities which process the information in the message or perform specific tasks. An end system 15 includes a bus interface unit 20 and its corresponding end station 22 with associated end-entities.

With reference now to Figures 2 and 3, the present invention may be divided into two portions: the transmitting station acknowledgment handler, and the receiving station acknowledgment generator.

As seen in Figure 2 the transmitting station acknowledgment handler is further divided into two portions: the transmitting bus interface unit (BIU) acknowledgment handler 120 (hereafter referred to as the sending BIU) , and the transmitting end station acknowledgment handler 122 (the sending host) .

As seen in Figure 3 the receiving station acknowledgment generator is further divided into two portions: the receiving bus interface unit (BIU) acknowledgment handler 140 (hereafter

referred to as the receiving BIU) , and the receiving end station acknowledgment handler 142 (the receiving host) .

The sending BIU 120 places a receiving end-entity 150 unique identifier in a control area of the sending data frame received from a transmitting end-entity 130. After sending the data frame, the sending BIU 120 receives the short hardware generated acknowledgment from the receiving end station 42 containing status information. As previously described, the present invention adds three new hardware states that the receiving end- entity 150 can be in, and therefore adds three new values of status to report back to the sending BIU 120 in the acknowledgment generated by acknowledgment reporter 45 in BIU 40. These new states are: (a) Entity Detached, (b) Entity Attached and Currently Receiving Data Frames, (c) Entity Attached and Currently in Flow Control.

Upon receiving in acknowledgment receiver 25 an Entity Flow Control status (state (c) above) in the hardware generated acknowledgment, the sending BIU 120 informs its sending host 122 that the receiving end-entity is in a flow control status. The sending host 122 exerts back pressure on the end station 22 by deferring future attempts at sending data communications to this receiving end-entity 150. This back pressure is applied to all locally resident end-entities 130 that attempt to send to the receiving end-entity 150 in flow control status and may be manifested in several ways. For example, (1) operation of end- entities 130 attempting to transmit to an end-entity 150 in flow control may be suspended until flow control is exited, or (2) attempted transmission may be returned to the end-entity 13 in error status. The choice may be made by the user of the transmitting end-entity 130 when end-entity parameters are established. Transmissions of end-entities 130 attempting to send to an end-entity 150 in a Detached status (state (a) above) are returned in error status.

The sending BIU 120 enqueues messages rejected by the receiving end station 42 due to Entity Flow Control status until one of two events occur: (a) Normal Exit, or (b) Time-out Retry.

SUBSTITUTE SHEET

On a normal exit, or when a time-out retry receives a normal status value in the received acknowledgment, all enqueued messages for that receiving end-entity 150 are transmitted, in sequence, by the sending BIU to the receiving station. The sending host is notified that it is to release messages for the receiving end-entity.

The receiving BIU 140 parses the incoming data frame, extracting the receiving end-entity 150 identifier from the frame and accepting or rejecting the frame based on the current flow control state for that end-entity. This decision is made by the receiving BIU 140 so that the decision to accept or reject may be conveyed back to the sending station in the acknowledgment generated in acknowledgment reporter 45.

The receiving host 142 monitors the state of the receiving end-entities 150 in its receiving station 42 that are currently attached to and using the services of the LAN. Receiving end- entities 150 are placed in flow control and removed from flow control based on a measurement of the receiving end-entity's current congestion. The number of data messages in the end- entity's input queue may be used as such a measure of congestion.

Although Figures 2 and 3 depict the transmitting and receiving components as separate entities, it is understood that each end system on the computer network may contain both components.

While the preferred embodiments of the present invention have been described, it is to be understood that the foregoing descriptions of preferred embodiments are illustrative only, and that the scope of the invention is to be defined solely by the appended claims when accorded a full range of equivalents, many variations and modifications naturally occurring to those skilled in the art from a perusal hereof.

SUBSTITUTESHEET