System and method for fast, reliable byte stream transport

• US 7,305,486 B2
• Filed: 06/28/2001
• Issued: 12/04/2007
• Est. Priority Date: 06/30/2000
• Status: Active Grant

• Current Assignee: The Research Foundation for The State University of New York (State University of New York)
• Original Assignee: The Research Foundation for The State University of New York (State University of New York)
• Inventors: Ghose, Kanad, Sulatycke, Peter
• Primary Examiner(s): Etienne; Ario
• Assistant Examiner(s): Osman; Ramy M
• Application Number:
  US09/894,585
• Publication Number:
  US 20020004842A1
• Time in Patent Office: 2,350 Days
• Field of Search: 709230-234, 709/223, 709/235, 370/235, 370/236
• US Class Current: 709/232
• CPC Class Codes: H04L 1/1614 using bitmaps
• CPC Class Codes: H04L 1/1628 List acknowledgements, i.e. the acknowledgement message consisting of a list of identifiers, e.g. of sequence numbers H04L1/1614 takes precedence
• CPC Class Codes: H04L 1/1809 Selective-repeat protocols
• CPC Class Codes: H04L 1/1848 Time-out mechanisms
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/18 End to end
• CPC Class Codes: H04L 47/193 at the transport layer, e.g. TCP related
• CPC Class Codes: H04L 47/39 Credit based
• CPC Class Codes: H04L 69/16 Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]
• CPC Class Codes: H04L 69/163 In-band adaptation of TCP data exchange; In-band control procedures

Abstract

Reliable byte stream transfer protocols play an important role in modern networks. The present invention implements such a protocol using credits for flow control and negative acknowledgements for reliable delivery. The credit mechanism uses credit transfer in installments and is immune to the losses or corruptions of intermediate credit installments. Negative acknowledgements are used to solicit the retransmission of data stream component. The present invention provides full compatibility at the programming interface with reliable byte transfer protocols, such as TCP, and also allows full interoperability among hosts running the aforesaid standard protocol or the protocol of the present invention.

Claims

1. A method for controlling a transmission of a data stream from a sending node to a receiving node in a data communication network, the method comprising:

(a) initially transmitting first information defining a begin and an end of a first unique range of data from a receiving node to a sending node, said first information authorizing transmission of a first quantity of data between the defined begin and end from said sending node;

(b) transmitting data of said data stream defined by said first information from a buffer disposed at said sending node to said receiving node;

(c) transmitting second information defining a begin and an end of a second unique range of data from said receiving node to said sending node when an event occurs, said second information authorizing transmission of a second quantity of data between the defined begin and the end from said sending node; and

(d) releasing at least a portion of said buffer at the sending node corresponding to said first unique range of data on receiving said second information.

2. The method of claim 1, wherein said releasing step occurs in response to at least one predetermined event selected one from the group consisting of:

a) at least one of said first unique range of bytes and said second unique range of bytes from said byte stream is received at said receiving node,

b) at least one of said first unique range of bytes and said second unique range of bytes from said byte stream is received at said receiving node and a congestion indicator at said receiver node is less than a predetermined threshold,

c) at least one of said first unique range of bytes and said second unique range of bytes from said byte stream is received at said receiving node and a data error indicator at said receiver node is less than a predetermined threshold,

d) a buffer disposed at said receiving node, and containing said at least one of said first unique range of bytes and said second unique range of bytes has free space,

e) a buffer disposed at said receiving node, and containing said at least one of said first unique range of bytes and said second unique range of bytes has free space and a congestion indicator at said receiver node is less than a predetermined threshold, and

f) a buffer disposed at said receiving node, and containing at least one of said first unique range of bytes and said second unique range of bytes has free space and a data error indicator at said receiver node is less than a predetermined threshold.

3. The method of claim 1, wherein the reception of said second information at said sending node indicates that at least a subset of said byte stream was correctly received at said receiving node.

4. The method of claim 1, wherein said step of transmitting of said second information is dependent upon a state of a counter which counts of a number of bytes received at said receiving node, wherein at least one of said initially transmitting first information step (a) and said transmitting second information step (c) comprise transmitting a predetermined number of credits from said receiving node to said sending node when said counter is equal to at least a predetermined value and decrementing said counter by the number of credits transmitted.

5. The method of claim 1, wherein at least one of said information defining the first unique range of data and said information defining the second unique range of data is adaptive to congestion detected in said data communication network, to reduce a data a size of the range of data in response to increasing congestion.

6. The method of claim 1, wherein said transmitting of said data of said stream is dependent upon a state of a counter, wherein said counter decrements in response to an amount of data transmitted, and incremented by an amount of data represented by a range of data authorized, said transmitting data step (b) comprises the sub-steps of:

i) transmitting said first unique range of data from said sending node to said receiving node when said counter is equal to at least said first quantity of data; and

ii) decrementing said counter by said number said first unique range of data upon said transmission thereof.

7. The method of claim 1, wherein said data transmitted in said initially transmitting first information step (a) and said transmitting second information step (c) are in a form compatible with Transmission Control Protocol (TCP) packets, whereby said method is compatible at the application programming interface (API) level with TCP.

8. The method of claim 1, wherein said first or second information authorizing transmission of a first or second quantity of data is transmitted by piggybacking existing traffic with said first or second information from said receiving node to said sending node.

9. The method of claim 1, wherein said first information or second information are not retransmitted if they are lost during transmission.

10. The method of claim 1, wherein said second unique range of data is contiguous to said first unique range of data.

11. The method of claim 1, further comprising the steps of:

d) at said sending node, upon receipt of said second information authorizing said second unique range of data, when said second unique range of data is non-contiguous with a prior received first unique range of data, sending data of said data stream intermediate said first unique range of data and said second unique range of data as though credits specifically authorizing sending thereof were explicitly received at said sending node.

12. The method of claim 11, further comprising the step of:

e) when at least one transmitted datum is lost or corrupted, transmitting from said receiving node to said sending node a negative acknowledgement identifying said at least one lost or corrupted datum.

13. The method of claim 12, further comprising the step of:

f) resetting said data communication network when said transmission of said negative acknowledgement occurs a maximum of a predetermined number of times.

14. The method of claim 12, wherein said negative acknowledgement is transmitted in response to a predetermined event.

15. The method of claim 12, wherein said at least one lost or corrupted datum is detected by means of error detection hardware only.

16. The method of claim 12, wherein said at least one lost or corrupted datum is detected only by software means for detecting errors.

17. The method of claim 12, the steps further comprising:

f) upon receipt of said negative acknowledgement at said sending node, retransmitting at least once, from said sending node to said receiving node, only said at least one lost or corrupted datum identified thereby.

18. The method of claim 1, said releasing step further comprising:

upon receipt of said first information authorizing transmission of said first unique range of data, and subsequent receipt of said second information defining said second unique range of data bytes, removing from a buffer at said sending node entries corresponding to said first unique range of data.

19. A method for transmitting a data stream from a sending node a receiving node in a communication network having a plurality of nodes and with a plurality of interconnect able paths, wherein said data are formed into a plurality of data packets in accordance with a predetermined protocol, the method comprising:

a) providing a predetermined identifier associated with data packets;

b) determining the predetermined identifier associated with a packet, and

c) if said predetermined identifier indicates a first transport system comprising a specified range of data credit and negative acknowledgement-based transport system;

(i) transmitting credits from a receiving node to a sending node responsive to occurrence of an event, said credits specifying a unique range of data having a defined begin and a defined end to be transmitted;

(ii) transmitting a specified unique range of data of a data stream from said sending node to said receiving node, corresponding to a range of data specified in credits received by said sending node from said receiving node; and

(iii) transmitting at least one negative acknowledgement from said receiving node to said sending node, specifying data for retransmission.

20. The method of claim 19, further comprising the steps of:

d) if said predetermined identifier indicates a second transport system that differ from said first transport system, processing said data stream by in accordance with said second transport system, whereby compatibility at the application programming interface (API) level of said first transport system and said second transport system is maintained.

21. The method of claim 19, the steps further comprising:

d) providing a first packet filter for filtering data packets at a sending node; and

e) providing a second packet filter for filtering data packets at a receiving node, so that said predetermined identifier indicates a credit and negative acknowledgement transport system dependent on said first and second packet filters.

22. The method of claim 19, the steps further comprising:

d) retransmitting at least once, from said sending node to said receiving node, data specified by said at least one negative acknowledgement, received at said sending node.

23. The method of claim 19, wherein said step (i) of transmitting said credits from said receiving node to said sending node occurs before said step (ii) of transmitting said specified range of data of said data stream.

24. The method of claim 23, wherein an initial transmitting of said credits step (i) occurs during a connection establishment of said sending node and said receiving node.

25. The method of claim 23, wherein said transmitting of said credits step (i) occurs after a connection establishment of said sending node and said receiving node.

26. The method of claim 19, wherein said event is one from the group of

a) a predetermined amount of data from said data stream is received at said receiving node,

b) a predetermined amount of data from said data stream is received at said receiving node and a congestion indicator at said receiving node is less than a threshold,

c) a predetermined amount of data from said data stream is received at said receiving node and a data error indicator at said receiving node is less than a predetermined threshold,

d) a buffer at said receiving node, containing data transmitted from said sending node to said receiving node, has free space,

e) a buffer at said receiving node, containing data transmitted from said sending node to said receiving node, has free space and a congestion indicator at said receiving node is less than a predetermined threshold, and

f) a buffer at said receiving node, containing data transmitted from said sending node to said receiving node, has free space and a data error indicator at said receiving node is less than a predetermined threshold.

27. The method of claim 19, wherein the reception of said credits at said sending node indicates that at least a subset of said byte stream was correctly received at said receiving node.

28. The method of claim 19, wherein said transmitting of said credits step (i) is dependent upon a counter at said receiving node exceeding a predetermined number representative of an amount of data received at said receiving node, said transmitting step (i) comprising the sub-steps of:

transmitting a number of credits from said receiving node to said sending node when said counter is equal to at least a predetermined value; and

decrementing said counter by said amount of data upon transmission of said credits.

29. The method of claim 19, wherein said credits from said transmitting credit step (i) are reduced or delayed to reflect congestion detection in said data communication network.

30. The method of claim 19, wherein said transmitting of said specified range of data step (ii) is dependent upon a counter exceeding a predetermined number representative of received credits at said sending node, said transmitting step (ii) including the sub-steps of:

transmitting said data from said sending node to said receiving node when said counter is equal to at least said number of bytes; and

decrementing said counter by said number of bytes upon said transmission of said bytes.

31. The method of claim 19, wherein said data transmitted in said transmission step (ii) are in a form compatible with Transmission Control Protocol (TCP) packets, whereby said method is compatible at the application programming interface (API) level with TCP.

32. The method of claim 19, wherein the established connection between said sending node and said receiving node is established using a standard 3-way handshake of Transmission Control Protocol (TCP).

33. The method of claim 19, the steps further comprising:

d) resetting a connection between said sending node and said receiving node when said transmission of at least one of said negative acknowledgements occurs a predetermined number of times.

34. The method of claim 19, wherein said transmitting of said credits step (ii) occurs by piggybacking said credits with existing traffic from said receiving node to said sending node.

35. The method of claim 19, wherein said credits in said transmitting credits step (i) are not retransmitted if they are lost.

36. The method of claim 19, wherein said at least one negative acknowledgement is transmitted upon occurrence of at least one predetermined event.

37. The method of claim 19, wherein said at least one negative acknowledgement specifies at least one corrupted byte for retransmission based exclusively on a signal generated by error detection hardware.

38. The method of claim 19, wherein said at least one negative acknowledgement specifies at least one datum for retransmission, after detection.

39. A system for transmitting a data stream from a sending node to a receiving node in a data communication network, comprising:

a) means for transmitting a range of data of a data stream from a sending node to a receiving node, said range of data having a specified beginning and a specified ending of a range of data credits present at said sending node;

b) means for transmitting a number of data credits specifying the beginning and the ending of the range of data of said data stream from said receiving node to said sending node upon occurrence of at least one event; and

c) means for transmitting at least one negative acknowledgement from said receiving node to said sending node, when at least one transmitted datum is lost or corrupted.

40. The system of claim 39, further comprising:

d) means for retransmitting at least once, from said sending node to said receiving node, said at least one lost or corrupted datum corresponding to said at least one negative acknowledgement received at said sending node.

41. The system of claim 39, wherein said means for transmitting said number of data credits from said receiving node to said sending node transmits said number of data credits before the transmission of said data of said data stream.

42. The system of claim 41, wherein said transmission of said number of credits occurs during a connection establishment of said sending node and said receiving node.

43. The system of claim 41, wherein said transmission of said number of credits occurs after a connection establishment of said sending node and said receiving node.

44. The system of claim 39, wherein said at least one event is selected from the group of one or more of:

a) a predetermined amount of data from said data stream is received at said receiving node,

b) a predetermined amount of data from said data stream is received at said receiving node and a congestion indicator at said receiver node is less than a predetermined threshold,

c) a predetermined amount of data from said data stream is received at said receiving node and a data error indicator at said receiver node is less than a predetermined threshold,

d) a buffer at said receiving node, containing said data transmitted from said sending node to said receiving node, has free space,

e) a buffer at said receiving node, containing said data transmitted from said sending node to said receiving node, has free space and a congestion indicator at said receiver node is less than a predetermined threshold, and

f) a buffer at said receiving node, containing said data transmitted from said sending node to said receiving node, has free space and a data error indicator at said receiver node is less than a predetermined threshold.

45. The system of claim 39, wherein the reception of said credits at said receiving node indicates that at least a subset of said data stream was correctly received at said receiving node.

46. The system of claim 39, wherein said means for transmitting a number of data credits is dependent upon a counter exceeding a number representative of an amount of data received at said receiving node, said means for transmitting comprising:

i) means for transmitting a number of data credits from said receiving node to said sending node when said counter is equal to at least a predetermined value; and

ii) means for decrementing said counter by an amount corresponding to the number of data credits transmitted upon transmission of said data credits.

47. The system of claim 39, wherein said data credits from said means for transmitting a number of data credits are reduced or delayed to reflect congestion detection in an established connection.

48. The system of claim 39, wherein said means for transmitting a range of data is dependent upon whether a counter exhausts a number representative of received data credits at said sending node, said means for transmitting comprising:

i) means for transmitting said data from said sending node to said receiving node when said counter is equal to at least a threshold value; and

ii) means for decrementing said counter based upon an amount of data transmitted.

49. The system of claim 39, wherein said data transmitted by said means for transmitting a range of data are in a form compatible with Transmission Control Protocol (TCP) packets, whereby said system is compatible at the application programming interface (API) level of TCP.

50. The system of claim 39, wherein a connection between said sending node and said receiving node is established using a standard 3-way handshake of Transmission Control Protocol (TCP).

51. The system of claim 39, further comprising:

d) means for resetting an established connection when said transmission of at least one negative acknowledgement for a given datum occurs a predetermined number of times.

52. The system of claim 39, wherein said means for transmitting said number of data credits is configured and adapted to piggyback said data credits with existing traffic from said receiving node to said sending node.

53. The system of claim 39, wherein said data credits in said means for transmitting a number of data credits are not retransmitted if they are lost.

54. The system of claim 39, wherein said at least one negative acknowledgement is transmitted upon occurrence of predetermined events.

55. The system of claim 39, wherein said at least one corrupted datum is detected by means of error detection hardware only.

56. The system of claim 39, wherein said at least one corrupted datum is detected only once by software error detection means.

57. A system for transmitting a data stream from a sending node having credits indicating a an amount of data from said data stream to be transmitted over an established connection to a receiving node in a communication network having a plurality of nodes and with a plurality of interconnect able paths, and wherein said predetermined amount of data is formed into a plurality of data packets in accordance with a predetermined protocol, the system comprising:

a) a predetermined identifier associated with said data packets;

b) a first transmitter for transmitting an amount of data of a data stream from a sending node to a receiving node, corresponding to a range of data having a begin datum and end datum specified by credits present at said sending node, if said predetermined identifier indicates implementation of a credit and negative acknowledgement transport system;

c) a second transmitter for transmitting credits from said receiving node to said sending node when a predetermined event occurs, said credits specifying a begin and an end of a range of data sought to be received; and

for transmitting a negative acknowledgement from said receiving node to said sending node, when at least one transmitted datum is lost or corrupted.

58. The system of claim 57, further comprising:

d) a processor for processing said data stream by a transport system independent of credit and negative acknowledgements, if said predetermined identifier indicates a transport system that is not exclusively credit and negative acknowledgement based,

whereby compatibility at the application programming level of the transport system independent of credit and negative acknowledgements protocol is maintained.

59. The system of claim 57, further comprising:

d) a first packet filter for filtering data packets at a sending node; and

e) a second packet filter for filtering data packets at a receiving node, so that said predetermined identifier indicates a credit and negative acknowledgement transport system dependent on said first and second packet filters.

60. The system of claim 57, said first transmitter further retransmitting at least once, from said sending node to said receiving node, said lost or corrupted datum corresponding to said negative acknowledgement received at said sending node.

61. The system of claim 57, wherein said credits transmitted from said receiving node to said sending node occurs before the transmission of said amount of data of said data stream.

62. The system of claim 61, wherein said transmitting of said credits occurs during a connection establishment of said sending node and said receiving node.

63. The system of claim 61, wherein said transmitting of said credits occurs after a connection establishment of said sending node and said receiving node.

64. The system of claim 57, wherein said predetermined event is selected from the group consisting of

a) a specified amount of data from said data stream is received at said receiving node,

b) a specified amount of data from said data stream is received at said receiving node and a congestion indicator at said receiver node is less than a predetermined threshold,

c) a specified amount of data from said data stream is received at said receiving node and a data error indicator at said receiver node is less than a predetermined threshold,

d) a buffer at said receiving node, containing said data transmitted from said sending node to said receiving node, has free space,

e) a buffer at said receiving node, containing said data transmitted from said sending node to said receiving node, has free space and a congestion indicator at said receiver node is less than a predetermined threshold, and

f) a buffer at said receiving node, containing said data transmitted from said sending node to said receiving node, has free space and a data error indicator at said receiver node is less than a predetermined threshold.

65. The system of claim 57, wherein the reception of said credits at said receiving node indicates that at least a subset of said data stream was correctly received at said receiving node.

66. The system of claim 57, wherein said second transmitter is dependent upon a counter exceeding a predetermined number representative of received data at said receiving node, said second transmitter:

i) transmitting a predetermined number of credits from said receiving node to said sending node when said counter is equal to at least a predetermined value; and

ii) decrementing said counter by an amount of credits transmitted upon transmission of said credits.

67. The system of claim 57, wherein said credits from said second transmitter are reduced or delayed to reflect congestion detection in an established connection.

68. The system of claim 57, wherein said first transmitter is dependent upon a counter exceeding a predetermined number representative of received credits at said sending node, said first transmitter:

(i) transmitting said data from said sending node to said receiving node when said counter is not exhausted; and

(ii) decrementing said counter based upon an amount of data transmitted.

69. The system of claim 57, wherein said data transmitted by said first transmitter are in a form compatible with Transmission Control Protocol (TCP) packets, whereby said system is compatible at the application programming level of TCP.

70. The system of claim 57, wherein the established connection between said sending node and said receiving node is established using a standard 3-way handshake of Transmission Control Protocol (TCP).

71. The system of claim 57, wherein said second transmitter resets said established connection when said transmission of at least one of said negative acknowledgements occurs a predetermined number of times.

72. The system of claim 57, wherein said second transmitter communicates credits by piggybacking existing traffic with said credits from said receiving node to said sending node.

73. The system of claim 57, wherein said credits in said second transmitter are not retransmitted if they are lost.

74. The system of claim 57, wherein said negative acknowledgement is transmitted based on at predetermined events.

75. The system of claim 57, wherein said at least one corrupted datum is detected by means of error detection hardware only.

76. The system of claim 57, wherein said at least one corrupted datum is detected only once by software error detection means.