Reliable connectionless network protocol

[0002] This application is a continuation of Ser. No. 08/767,517 filed Dec. 16, 1996 ABN, which is a continuation of Ser. No. 08/343,761, filed Nov. 21, 1999 ABN.

[0003] The present invention relates to the field of protocols for a network environment, and more specifically to a reliable connectionless protocol.

[0004] FIG. 1aillustrates a prior art protocol for opening a connection in the transmission control protocol/internet protocol (TCP/IP) network environment. The open connection protocol consists of a three way handshake. For the example illustrated in FIG. 1a, the open connection is between “node 1” and “node 2”. In order to initiate the open connection, node 1 sends a segment having the SYN bits set in the code field. The node 2, in a second segment, sets both the SYN bit and ACK bits. This response by node 2 both acknowledges the first SYN segment as well as continues the handshake protocol with node 1. However, the second segment does not complete the protocol, but the second segment is a mere acknowledgment that is used to inform node 1, the initiator, that both sides agree that a connection has been established. In a third segment, the node 1 initiator sends an ACK segment back to node 2. After the connection has been established, data transfer may commence.

[0005] FIG. 1billustrates the prior art protocol for closing a connection in accordance with the TCP/IP networking protocol. The closed connection protocol is a modified three-way handshake. For the example illustrated in FIG. 1b, node 1 initiates closing of the connection. The response from the node after receiving the initial FIN segment for the close connection of TCP/IP protocol is different from the open connection. As shown in FIG. 1b, instead of generating a second FIN segment immediately, node 2 sends an acknowledgment. In response to the initial FIN segment, the network interface informs an application of the request to close the connection. When the application instructs the network interface to close the connection, node 2 sends the second FIN segment, and node 1 replies in a third segment using the ACK segment.

[0006] A reliable connectionless protocol is used in a networking environment. The reliable connectionless protocol utilizes a one way message protocol in order to maintain reliability without the additional overhead of opening and closing a connection. The network contains a plurality of nodes for transfer of data between a source node and at least one destination node. Each node configured for the message protocol of the present invention contains, in part, a transport layer coupled to at least one application.

[0007] In operation, the transport layer receives data for transfer between a source node and a destination node on the network. The transport layer divides the data into predetermined length data packets. The pre-determined length data packets are unrelated to the amount of data for transfer. In addition to generating the data packets, the transport layer generates a segment header for each data packet. The segment header defines an order for the corresponding data packet based on the original data received from the application. In one embodiment, the segment header defines whether the corresponding data packet is the first data packet, an interim data packet, or the last data packet.

[0008] The transport layer generates independent segments by combining each data packet with a corresponding segment header. Consequently, each segment, including the first segment and the last segment, contains a data packet. Additional control information is added to transfer the segments over the network. The independent segments are transferred from the source node to the destination node via the network such that each independent segment transfers part of the original data without establishing a connection.

[0009] A transport layer on the destination node utilizes the information in the segment header to determine a first segment for the data transfer, thereby allowing the destination node to begin to receive the data. The destination node transport layer extracts the data from the data packets to re-construct the original data. When the destination node receives the last segment, the destination node finishes the re-construction of the original data, and discards the information in the segment header used to re-construct the data.

[0010] Other features and advantages of the present invention will be apparent from the accompanying drawings, and from the detailed description that follows below.

[0011] The objects, features, and advantages of the present invention will be apparent from the following detailed description of the preferred embodiment of the invention with references to the following drawings.

[0012] FIG. 1aillustrates a prior art protocol for opening a connection in the transmission control protocol/internet protocol (TCP/IP) network environment.

[0013] FIG. 1billustrates the prior art protocol for closing a connection in accordance with the TCP/IP networking protocol.

[0014] FIG. 2 illustrates a plurality of nodes coupled to a network configured in accordance with one embodiment of the present invention.

[0015] FIG. 3 is a flow diagram illustrating a high level message protocol of the present invention.

[0016] FIG. 4 illustrates a segment format configured in accordance with one embodiment of the message based protocol of the present invention.

[0017] FIG. 5 is a flow diagram illustrating one method of a transport layer configured in accordance with the present invention.

[0018] FIG. 6 illustrates the operation for one embodiment of a transport layer that receives a segment for the message based protocol of the present invention.

[0019] The present invention is a reliable connectionless protocol used in a networking environment. Specifically, the present invention utilizes a one way message phenomenon in order to maintain reliability without the additional overhead of opening and closing a connection. The three-way handshakes used by the TCP/IP protocol are designed to coordinate two ends of a connection for data transfer even if both ends initiate or close down a connection simultaneously.

[0020] In the TCP/IP networking environment, the three-way handshake is both necessary and sufficient for correct synchronization between the two ends of a connection because the TCP/IP protocol depends upon an unreliable packet delivery service. Because of the unreliable packet delivery service, messages can be lost, delayed, duplicated or delivered out of order. In order to compensate for the unreliable service, the TCP/IP protocol specifies a time-out mechanism to retransmit lost requests. However, ambiguity and uncertainty is introduced if retransmitted or original requests arrive while the connection is being established, or if retransmitted requests are delayed until a connection has been established, used, and terminated. In order to solve these problems, the TCP/IP protocol specifies the three-way handshake protocol to guarantee that additional requests for connection do not occur after a connection has been established.

[0021] Reliability is an essential characteristic of a network environment. The present invention provides for a message protocol that ensures reliable transfer of discrete messages. The discrete messages may be of arbitrary but finite length. As is explained more fully below, the message protocol of the present invention is connectionless (e.g., the two end nodes between which data is transferred need only retain state about each of the other node while data is in transit). In general, the connectionless nature of the message based protocol allows a distributed network to scale without consuming resources for each new connection. In addition, the connectionless nature makes the network system robust in the face of individual node failure because no connections are being dropped.

[0022] In one embodiment, the message protocol is a modification of the TCP/IP connection based, reliable protocol. For this embodiment, the basic modification is the elimination of the handshakes that are used to open and close a TCP/IP connection. In the present invention, the three-way handshake protocol is eliminated in favor of adding the control information on top of the data payload for each message transfer. Using this connectionless protocol, data are received in a first segment of the message, and data are received in a last segment of the message.

[0023] In a network environment, round trips get more expensive the slower the network. Therefore, handshaking consumes more resources the slower the network. By avoiding the open and close connection handshakes, the present invention avoids unnecessary and expensive network traffic. In addition, the destination node is permitted. to view the data contained in a message as soon as the entire message is received at the destination node. For the TCP/IP network protocol, the destination node is required to wait for the handshake to complete before data may be viewed.

[0024] Typically, in network environments, a first channel is used to transmit data, and a second channel is used to open and close a connection. In addition, data are transmitted over a faster channel than the channel used to open and close a connection. For such a network environment, the destination node receives data before the receipt of an acknowledgment over the slower handshaking channel. In theory, data may be included with the initial transmission in the TCP/IP protocol. However, in the TCP/IP protocol, the destination node is not permitted to access the data until the handshake completes. Therefore, the destination node is required to wait for the round-trip acknowledgment over the slower data channel.

[0025] For the embodiment of the present invention that implements a modified TCP/IP protocol, the message protocol retains all other characteristics of the TCP/IP protocol, such as sliding windows, retransmission with back-off, and recovery from network errors. For example, network errors may include corruption, lost data, duplicated data, or data delivered out of sequence. Moreover, the message protocol of the present invention guarantees that separate discrete messages transmitted between a source node and a destination node arrive in the original order transmitted. Although a desirable attribute, preserving the ordering of discrete messages is not necessarily guaranteed by a connectionless protocol.

[0026] In general, when transmitting data between a source node and a destination node in accordance with the present invention, an application supplies data and a destination address. Prior to transmitting the data, the transport layer apportions the data into packets suitable for transport across network links. The size of the packets is determined based on the characteristics of the network, and is completely unrelated to the amount of data for transmission. Once packetization is complete, the source node transmits the packets over the network. The packets contain sufficient control information to allow independent processing and subsequent forwarding at intermediate hops for final delivery to the destination node. When packets arrive at the ultimate destination node, packets are reassembled into the original data. Consequently, only the source node and the destination node are required to maintain information about the data during transit.

[0027] FIG. 2 illustrates a plurality of nodes coupled to a network configured in accordance with one embodiment of the present invention. As shown in FIG. 2, a node 210 and node 220 are coupled to a network 200. For purposes of explanation and clarity, FIG. 2 illustrates two nodes on the network 200, however, any number of nodes may be configured in accordance with the teachings of the present invention. The network 200 may be configured to operate as any type of network. The nodes 210 and 220 may be part of a computer system, such as a server, used to interface the computer system to the network 200.

[0028] The nodes 210 and 220 shown in FIG. 2 include the functional units required to implement the present invention. A description of the node 210 is provided. However, each node on the network configured to operate in accordance with the present invention contains similar functional units. Specifically, the node 210 includes applications 230, transport layer 240 and network layer 260. In a preferred embodiment, the applications 230 and the transport layer 240 are implemented in software on a computer platform. In general, the applications 230 perform any type of function that requires network access.

[0029] The network layer 260 is configured to interface nodes 210 and 220 to the network 200. For purposes of explanation, the network layer 260 includes the physical layer to provide a physical link to interface the node 210 to the network 200. For example, the network layer 260 may be a network interface card used to interface a computer system to a network. In a preferred embodiment, the network layer, including the physical link, is implemented with a combination of software and hardware. The specific operation of the network layer 260 is dependent upon the particular network. The network layer 260 is intended to represent a broad category of such implementations used to interface computer systems to networks, which are well known in the art and which will not be described further.

[0030] As shown in FIG. 2, the transport layer 240 contains a packetization unit 250. The transport layer 240 implements the message based protocol of the present invention. As is explained more fully below, the packetization unit 250 generates separate segments to support the connectionless protocol. In one embodiment, the transport layer 240 and network layer 260 are configured to operate in accordance with a modified TCP/IP network protocol (e.g. a connectionless TCP/IP protocol).

[0031] FIG. 3 is a flow diagram illustrating a high level message protocol of the present invention. As shown in block 310, the transport layer 240 receives data and addressing information from an application within the applications 230 (FIG. 2). The data received by the transport layer 240 may be of any length. In response to receiving the data, the transport layer 240 apportions data in predetermined length packets as shown in block 320. The data packets are generated in the packetization unit 250. The length of the data packets are dependent upon the particular attributes of the network 200. However, any length data packets may be used without deviating from the spirit and scope of the invention.

[0032] As shown in block 330, the transport layer 240 generates independent segments for each data packet. In addition to the data packet, the transport layer 240 adds control information received from the applications 230. The transport layer 240 forwards the independent segments to the network layer 260 such that the segments are independently transmitted over the network 200 as shown in block 340.

[0033] FIG. 4 illustrates a segment format configured in accordance with one embodiment of the message based protocol of the present invention. A segment 400 contains a segment header 405. The segment header 405 further includes a first indication (FST) bit and a more to come (MTC) bit 415. Also, to specify the order for the particular segment, the segment contains a sequence number field 420. The source node for a network transaction is identified in a source identification (ID) field 425, and a destination address is identified in a destination identification (ID) field 430. Furthermore, the segment 400 includes a segment length field 440 and a data field 450. The data field contains the data packet for the particular segment, and the segment length field 440 indicates the length of the data in the data field 450.

[0034] The message format illustrated in FIG. 4 is used for each segment, including the first segment and the last segment. As is explained more fully below, the segment header 405 and the one way message protocol eliminate the need for handshaking. Furthermore, the order in which the segments are transmitted are determined by the destination node through the sequence number stored in sequence number field 420.

[0035] FIG. 5 is a flow diagram illustrating one method of a transport layer configured in accordance with the present invention. As shown in block 505, the transport layer 240 (FIG. 2) packetizes data received from the applications 230. As shown in blocks 510 and 520, if the segment is a first segment, then the transport layer 240 sets the FST bit for that particular segment. As shown in blocks 510 and 530, if the particular segment is not the first segment, then the FST bit is cleared. The transport layer 240 determines whether the particular segment is the last segment pertaining to that data stream. If the segment is the last segment, then the MTC bit is cleared as shown in blocks 540 and 550. Alternatively, if the segment is not the last segment, then the MTC bit is set as shown in blocks 540 and 560. For each segment, the transport layer 240 sets the source ID field 425, sequence number field 420, and the destination ID field 430 (FIG. 4). The data, apportioned for the segment, is appended to the segment in the data portion 450. This process is repeated for each data packet to generate independent segments.

[0036] FIG. 6 illustrates the operation for one embodiment of a transport layer that receives a message for the message based protocol of the present invention. As shown in block 610, a segment is received from the network 120. In response, the transport layer 240 extracts data and control bits as shown in block 620. In order to implement the connectionless protocol of the present invention, the transport layer 240 determines whether the FST bit is set as shown in 630. If the FST bit is set, then the transport layer 240 knows that the segment is the first segment of the message as shown in block 640. The transport layer 240 determines whether the MTC bit is set as shown in block 650. If the MTC bit is not set, then the destination node knows that the segment is the last segment in the message. If the MTC bit is set, then the destination node knows that the segment is not the last segment for that particular data stream, then steps 610, 620, 630, 640 and 650 are repeated.

[0037] Although the connectionless protocol of the present invention does not require opening and closing a connection, the destination node initializes local state information upon receipt of the first segment of the message. The local state information allows the destination node to track subsequent segments of the message, even if segments arrive out of order, to re-construct that message. However, the local state information is discarded after has been successfully received and reconstructed. In one embodiment, the local state information is retained for a short period of time after the message is received to prevent the receipt of duplicate segments as being interpreted as part of a new message. However, the amount of time that the local state information is retained by the destination node is completely independent of the action that the source node takes following the completion of the sending of the message.

[0038] The network 200 may include a number of network links.

[0039] The network links may vary widely in bandwidth and reliability. For example, the bandwidth of a network link may be sufficient to transport video or extremely limited. In general, data delivered by a network can be corrupted, duplicated, dropped, or delivered out of order. The present invention implements a message protocol to support reliable data delivery. In the message protocol, the payload or data transported is opaque in that no structure or representation of the data is understood or imposed by the protocol.

[0040] The message protocol provides for the reliable transport of discrete segments. Each individual segment contains an address to a destination node. If multiple segments within a message are sent from one source destination to the same destination node, then the segments of the message are received in the same order sent by the source node. The message protocol of the present invention is defined as an “at-most-once” protocol. That is, if the message can be delivered at all, the message is delivered exactly once. However, network link failure or unexpected termination of the destination node may cause the delivery to fail, thus preventing the message from being delivered at all.

[0041] In a preferred embodiment, reliable transport over the network is ensured by using positive acknowledgments combined with retransmission. A positive acknowledgment is an acknowledgment of data received. If an acknowledgment is not received in a certain amount of time, the source node retransmits the unacknowledged segments of the message. Generally, most transmission failures result from congestion on the network or delays at the destination node or other intermediate nodes. Any node on the network is permitted to discard a segment if that node does not have the resources to process the segment.

[0042] In order to avoid compounding the network congestion problem, the amount of time the source node waits prior to retransmission is increased between successive retransmissions. This procedure is known as exponential backoff. The exponential backoff technique allows the network time to clear and recover from the congested state. When the source node receives an acknowledgment, the source node starts to slowly transmits data. As data transmission continues, the source node gradually increases the rate of data transmission up to the full transmission rates. The exponential backoff technique avoids bouncing back and forth between congested and quiescent network conditions.

[0043] In the preferred embodiment, round-trip times taken for successful acknowledgments of transmission are observed and used to constantly adjust the retransmission timer. The adjustment of the retransmission timer permits adaptation to existing network and node conditions, thereby avoiding retransmissions based on a particular link that is consistently slower than other links.

[0044] The amount of data transmitted before requiring an acknowledgment is determined by a sliding window mechanism. With the sliding window mechanism, data are transmitted to the destination node. The source node then waits for an acknowledgment to indicate the amount of contiguous data received. As acknowledgments are received, the source node advances the window to transmit more data. The sliding window continues until all the data is transmitted and acknowledged. The size of the window is determined by the size of the buffer available to the destination node and the size is constantly adjusted. Because acknowledgments are sent by the destination node prior to receiving the last data sent in a particular window, the window advances even during transmission of data by the source node. Thus, an appropriate amount of buffer space available to the destination node ensures that the transmission of data approaches the maximum throughput of the network under normal conditions.

[0045] For example, consider a source node connected to a network via a slow 9600 bit per second (bps) upstream channel and a fast 1.5 Mbps downstream channel. An acknowledgment transmitted back to the source node takes approximately 100 to 300 ms depending on latencies in the upstream channel. During that time period, approximately 60 k bytes of data may be sent through the downstream channel before the source node stalls. Thus, if the window size is 64 k bytes, then the source node transmits as much as 64k bytes before waiting to receive an acknowledgment. Because the first acknowledgment should arrive before the source node reaches the end of the window, the source node immediately transmits more data. In practice, transfer rates will be marginally below the theoretical maximum.

[0046] Although the present invention has been described in terms of specific exemplary embodiments, it will be appreciated that various modifications and alterations might be made by those skilled in the art without departing from the spirit and scope of the invention as set forth in the following claims.