System and method for fast, reliable byte stream transport

• US 20020004842A1
• Filed: 06/28/2001
• Published: 01/10/2002
• 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
• Granted Patent: US 7,305,486 B2
• Time in Patent Office: Days
• US Class Current: 709/235
• 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 fall interoperability among hosts running the aforesaid standard protocol or the protocol of the present invention.

Claims

1. A method for quickly and reliably transmitting a byte stream from a sending node having a number of credits with an established connection to a receiving node in a communication environment having a plurality of nodes and a plurality of interconnectable paths, the method comprising:

transmitting a predetermined number of bytes of a byte stream from a sending node to a receiving node, said predetermined number of bytes corresponding to the number of credits present at said sending node;

transmitting a predetermined number of credits from said receiving node to said sending node when a predetermined event occurs; and

transmitting a predetermined number of negative acknowledgements from said receiving node to said sending node, when at least one transmitted byte is lost or corrupted.

2. The method of claim 1, further including the step of retransmitting at least once, from said sending node to said receiving node, said lost or corrupted bytes corresponding to said predetermined number of negative acknowledgments received at said sending node.

3. The method of claim 1, wherein said step of transmitting said predetermined number of credits from said receiving node to said sending node occurs before the transmission of said predetermined number of bytes of said byte stream.

4. The method of claim 3, wherein said step of transmitting of said predetermined number of credits occurs during a connection establishment of said sending node and said receiving node.

5. The method of claim 3, wherein said step of transmitting of said predetermined number of credits occurs after a connection establishment of said sending node and said receiving node.

6. The method of claim 1, wherein said predetermined event is one from the group of a) a predetermined number of bytes from said byte stream is received at said receiving node, b) a predetermined number 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) a predetermined number 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 at said receiving node, containing said bytes transmitted from said sending node to said receiving node, has free space, e) a buffer at said receiving node, containing said bytes 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 bytes 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.

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

8. The method of claim 1, wherein said step of transmitting of said predetermined number of credits is dependent upon a counter exceeding a predetermined number representative of received bytes at said receiving node, said transmitting step including the steps of:

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 said byte size upon transmission of said credits.

9. The method of claim 1, wherein said credits from said credit transmission step are reduced or delayed to reflect congestion detection in an established connection.

10. The method of claim 1, wherein said step of transmitting of said predetermined number of bytes is dependent upon a counter exceeding a predetermined number representative of received credits at said sending node, said transmitting step including the steps of:

transmitting said bytes 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.

11. The method of claim 1, wherein said bytes transmitted in said byte transmission step are in the form of Transmission Control Protocol (TCP) packets, whereby said method is compatible at the application programming level of TCP.

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

13. The method of claim 1, further including the step of resetting said established connection when said transmission of at least one of said negative acknowledgements occurs a predetermined number of times.

14. The method of claim 1, wherein said transmitting of said predetermined number of credits occurs by piggybacking existing traffic with said credits from said receiving node to said sending node.

15. The method of claim 1, wherein said credits in said credit transmission step are not retransmitted if they are lost.

16. The method of claim 1, wherein said predetermined number of negative acknowledgements is transmitted at predetermined events.

17. The method of claim 1, wherein said at least one corrupted byte is detected by means of error detection hardware only.

18. The method of claim 1, wherein said at least one corrupted byte is detected only once by software error detection means.

19. A method for quickly and reliably transmitting a byte stream from a sending node having credits with an established connection to a receiving node in a communication environment having a plurality of nodes and with a plurality of interconnectable paths, where the bytes of said byte stream are formed into a plurality of data packets of a protocol, the method comprising:

providing a predetermined identifier associated with data packets;

if said predetermined identifier indicates a credit and negative acknowledgement transport system, transmitting a predetermined number of bytes of a byte stream from a sending node to a receiving node, corresponding to the number of credits present at said sending node;

transmitting a predetermined number of credits from said receiving node to said sending node when a predetermined even occurs; and

transmitting a predetermined number of negative acknowledgements from said receiving node to said sending node, when at least one transmitted byte is lost or corrupted.

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

if said predetermined identifier indicates a transport system that is not exclusively credit and negative acknowledgement based, processing said data stream by a transport system independent of credit and negative acknowledgements, whereby compatibility at the application programming level of a protocol is maintained.

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

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

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, further including the step of retransmitting at least once, from said sending node to said receiving node, said lost or corrupted bytes corresponding to said predetermined number of negative acknowledgments received at said sending node.

23. The method of claim 19, wherein said step of transmitting said predetermined number of credits from said receiving node to said sending node occurs before the transmission of said predetermined number of bytes of said byte stream.

24. The method of claim 23, wherein said step of transmitting of said predetermined number of credits occurs during a connection establishment of said sending node and said receiving node.

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

26. The method of claim 19, wherein said predetermined event is one from the group of a) a predetermined number of bytes from said byte stream is received at said receiving node, b) a predetermined number 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) a predetermined number 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 at said receiving node, containing said bytes transmitted from said sending node to said receiving node, has free space, e) a buffer at said receiving node, containing said bytes 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 bytes 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.

27. The method of claim 19, wherein the reception of said credits at said receiving 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 step of transmitting of said predetermined number of credits is dependent upon a counter exceeding a predetermined number representative of received bytes at said receiving node, said transmitting step including the steps of:

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 said byte size upon transmission of said credits.

29. The method of claim 19, wherein said credits from said credit transmission step are reduced or delayed to reflect congestion detection in an established connection.

30. The method of claim 19, wherein said step of transmitting of said predetermined number of bytes is dependent upon a counter exceeding a predetermined number representative of received credits at said sending node, said transmitting step including the steps of:

transmitting said bytes 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 bytes transmitted in said byte transmission step are in the form of Transmission Control Protocol (TCP) packets, whereby said method is compatible at the application programming level of TCP.

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

33. The method of claim 19, further including the step of resetting said established connection 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 predetermined number of credits occurs by piggybacking existing traffic with said credits from said receiving node to said sending node.

35. The method of claim 19, wherein said credits in said credit transmission step are not retransmitted if they are lost.

36. The method of claim 19, wherein said predetermined number of negative acknowledgements is transmitted at predetermined events.

37. The method of claim 19, wherein said at least one corrupted byte is detected by means of error detection hardware only.

38. The method of claim 19, wherein said at least one corrupted byte is detected only once by software error detection means.

39. A system for quickly and reliably transmitting a byte stream from a sending node having credits with an established connection to a receiving node in a communication environment having a plurality of nodes with a plurality of interconnectable paths, comprising:

means for transmitting a predetermined number of bytes of a byte stream from a sending node to a receiving node, said predetermined number of bytes corresponding to the number of credits present at said sending node;

means for transmitting a predetermined number of credits from said receiving node to said sending node when a predetermined event occurs; and

means transmitting a predetermined number of negative acknowledgements from said receiving node to said sending node, when at least one transmitted byte is lost or corrupted.

40. The system of claim 39, further comprising:

means for retransmitting at least once, from said sending node to said receiving node, said lost or corrupted bytes corresponding to said predetermined number of negative acknowledgments received at said sending node.

41. The system of claim 39, further comprising:

means for transmitting said predetermined number of credits from said receiving node to said sending node occurs before the transmission of said predetermined number of bytes of said byte stream.

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

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

44. The system of claim 39, wherein said predetermined event is one from the group of a) a predetermined number of bytes from said byte stream is received at said receiving node, b) a predetermined number 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) a predetermined number 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 at said receiving node, containing said bytes transmitted from said sending node to said receiving node, has free space, e) a buffer at said receiving node, containing said bytes 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 bytes 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 byte stream was correctly received at said receiving node.

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

means for 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

means for decrementing said counter by said byte size upon transmission of said credits.

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

48. The system of claim 39, wherein said means for transmitting of said predetermined number of bytes is dependent upon a counter exceeding a predetermined number representative of received credits at said sending node, said transmitting means comprising:

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

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

49. The system of claim 39, wherein said bytes transmitted by said byte transmission means are in the form of Transmission Control Protocol (TCP) packets, whereby said system is compatible at the application programming level of TCP.

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

51. The system of claim 39, further comprising:

means for resetting said established connection when said transmission of at least one of said negative acknowledgements occurs a predetermined number of times.

52. The system of claim 39, wherein said means for transmitting of said predetermined number of credits occurs by piggybacking existing traffic with said credits from said receiving node to said sending node.

53. The system of claim 39, wherein said credits in said credit transmission means are not retransmitted if they are lost.

54. The system of claim 39, wherein said predetermined number of negative acknowledgements is transmitted at predetermined events.

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

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

57. A system for quickly and reliably transmitting a byte stream from a sending node having credits with an established connection to a receiving node in a communication environment having a plurality of nodes and with a plurality of interconnectable paths, where the bytes of said byte stream are formed into a plurality of data packets of a protocol, the system comprising:

a predetermined identifier associated with data packets;

means for transmitting a predetermined number of bytes of a byte stream from a sending node to a receiving node, corresponding to the number of credits present at said sending node, if said predetermined identifier indicates a credit and negative acknowledgement transport system;

means for transmitting a predetermined number of credits from said receiving node to said sending node when a predetermined even occurs; and

means for transmitting a predetermined number of negative acknowledgements from said receiving node to said sending node, when at least one transmitted byte is lost or corrupted.

58. The system of claim 57, further comprising:

means 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 a protocol is maintained.

59. The system of claim 57, further comprising:

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

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, further comprising:

means for retransmitting at least once, from said sending node to said receiving node, said lost or corrupted bytes corresponding to said predetermined number of negative acknowledgments received at said sending node.

61. The system of claim 57, further comprising:

means for transmitting said predetermined number of credits from said receiving node to said sending node occurs before the transmission of said predetermined number of bytes of said byte stream.

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

63. The system of claim 61, wherein said means for transmitting of said predetermined number of 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 one from the group of a) a predetermined number of bytes from said byte stream is received at said receiving node, b) a predetermined number 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) a predetermined number 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 at said receiving node, containing said bytes transmitted from said sending node to said receiving node, has free space, e) a buffer at said receiving node, containing said bytes 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 bytes 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 byte stream was correctly received at said receiving node.

66. The system of claim 57, wherein said means for transmitting of said predetermined number of credits is dependent upon a counter exceeding a predetermined number representative of received bytes at said receiving node, said transmitting means comprising:

means for 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

means for decrementing said counter by said byte size upon transmission of said credits.

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

68. The system of claim 57, wherein said means for transmitting of said predetermined number of bytes is dependent upon a counter exceeding a predetermined number representative of received credits at said sending node, said transmitting means comprising:

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

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

69. The system of claim 57, wherein said bytes transmitted by said byte transmission means are in the form of 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 the standard 3-way handshake of Transmission Control Protocol (TCP).

71. The system of claim 57, further comprising:

means for resetting 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 means for transmitting of said predetermined number of credits occurs 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 credit transmission means are not retransmitted if they are lost.

74. The system of claim 57, wherein said predetermined number of negative acknowledgements is transmitted at predetermined events.

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

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