System and method for fast, reliable byte stream transport

• US 7,899,925 B2
• Filed: 12/04/2007
• Issued: 03/01/2011
• Est. Priority Date: 06/30/2000
• Status: Expired due to Term

• 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): Osman; Ramy M
• Application Number:
  US11/950,322
• Publication Number:
  US 20100046370A1
• Time in Patent Office: 1,183 Days
• Field of Search: 709230-236, 709/223, 370/229
• 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, comprising:

receiving, at a transmitter, a first set of credits specifying a first starting data element and a first ending data element within a data stream;

sending, by the transmitter, sequential data elements specified by the first set of credits, commencing at the first starting data element and ceasing at the first ending data element;

receiving, at the transmitter, a second set of credits specifying a second starting data element and a second ending data element within the data stream, the second set of credits specifying a non-overlapping range of the sequential data elements specified by the first set of credits, wherein the second set of credits implicitly acknowledges the sequential data elements specified by the first set of credits; and

sending, by the transmitter, sequential data elements specified by the second set of credits, commencing at the second starting data element and ceasing at the second ending data element.

2. The method of claim 1, further comprising receiving an acknowledgement representing receipt of a range of the sequential data elements specified by the second set of credits.

3. The method of claim 1, further comprising receiving a negative acknowledgement representing a failure of receipt of the sequential data elements specified by the second set of credits within a predetermined period of time.

4. The method of claim 3, further comprising sending a packet of data representing a range of the sequential data elements specified by the negative acknowledgement upon receipt of the negative acknowledgment.

5. The method of claim 3, further comprising determining an indication of network congestion based on a rate of negative acknowledgements.

6. The method of claim 1, wherein at least one of the first and second set of credits is defined based on a capacity of a buffer at a receiver.

7. The method of claim 1, wherein receiving the first set of credits comprises receiving the first set of credits in response to a number of credits on hand being zero.

8. The method of claim 1, wherein a number of data elements represented by the first set of credits is different that a number of data elements represented by the second set of credits.

9. The method of claim 1, wherein receiving the second set of credits comprises acknowledging receipt of the sequential data elements specified by the first set of credits.

10. The method of claim 1, wherein the first set of credits comprise a first number of data elements to be transmitted, and further comprising:

reducing a number of credits remaining based on a transmission of data elements, wherein transmission ceases in response to the number of credits reaching zero.

11. The method of claim 1, wherein the second set of credits is not part of an explicit acknowledgment message.

12. A method, comprising:

transmitting, from a receiver, a first set of credits specifying a first starting data element and a first ending data element within a data stream;

receiving, at the receiver, sequential data elements specified by the first set of credits;

transmitting, from the receiver, a second set of credits specifying a second starting data element and a second particular ending data element within the data stream, wherein the second set of credits implicitly acknowledges the sequential data elements specified by the first set of credits; and

receiving, at the receiver, sequential data elements specified by the second set of credits, the second set of credits specifying a non-overlapping range of the sequential data elements specified by the first set of credits.

13. The method of claim 12, further comprising transmitting a negative acknowledgement (NACK) representing a failure to receive one or more data elements within a predetermined period of time.

14. The method of claim 12, wherein at least one of the first and second set of credits is defined based on a capacity of a buffer at a receiver.

15. The method of claim 12, wherein a number of data elements represented by the first set of credits is different that a number of data elements represented by the second set of credits.

16. The method of claim 12, wherein transmitting the second set of credits comprises acknowledging receipt of the sequential data elements specified by the first set of credits.

17. The method of claim 12, further comprising determining an indication of network congestion based on a rate of negative acknowledgements.

18. A non-transitory computer readable medium, having stored therein instructions, the instructions comprising:

receiving, at a transmitter, a first set of credits specifying a first starting data element and a first ending data element within a data stream;

sending, by the transmitter, sequential data elements specified by the first set of credits, commencing at the first starting data element and ceasing at the first ending data element;

receiving, at the transmitter, a second set of credits specifying a second starting data element and a second ending data element within the data stream, the second set of credits specifying a non-overlapping range of the sequential data elements specified by the first set of credits, wherein the second set of credits implicitly acknowledges the sequential data elements specified by the first set of credits; and

sending, by the transmitter, sequential data elements specified by the second set of credits, commencing at the second starting data element and ceasing at the second ending data element.

19. The non-transitory computer readable medium of claim 18, wherein sending the sequential data elements specified by the first set of credits are comprises sending the sequential data elements specified by the first set of credits via a Transmission Control Protocol (TCP) packet.

20. The non-transitory computer readable medium according to claim 18, wherein receiving the first set of credits comprises receiving the first set of credits in a byte stream.

21. The non-transitory computer readable medium of claim 18, wherein the second set of credits is not part of an explicit acknowledgment message.

22. An apparatus, comprising:

means for receiving a first set of credits specifying a first starting data element and a first ending data element within a data stream;

means for sending sequential data elements specified by the first set of credits, commencing at the first starting data element and ceasing at the first ending data element;

means for receiving a second set of credits specifying a second starting data element and a second ending data element within the data stream, the second set of credits specifying a non-overlapping range of the sequential data elements specified by the first set of credits, wherein the second set of credits implicitly acknowledges the sequential data elements specified by the first set of credits; and

means for sending sequential data elements specified by the second set of credits, commencing at the second starting data element and ceasing at the second ending data element.

23. The apparatus of claim 22, wherein the second set of credits is not part of an explicit acknowledgment message.

24. An apparatus, comprising:

means for transmitting a first set of credits specifying a first starting data element and a first ending data element within a data stream;

means for receiving sequential data elements specified by the first set of credits;

means for transmitting a second set of credits specifying a second starting data element and a second particular ending data element within the data stream, wherein the second set of credits implicitly acknowledges the sequential data elements specified by the first set of credits; and

means for receiving sequential data elements specified by the second set of credits, the second set of credits specifying a non-overlapping range of the sequential data elements specified by the first set of credits.

25. A non-transitory computer readable medium having instructions stored thereon, the instructions comprising:

transmitting, at a receiver, a first set of credits specifying a first starting data element and a first ending data element within a data stream;

receiving, at the receiver, sequential data elements specified by the first set of credits;

transmitting, at the receiver, a second set of credits specifying a second starting data element and a second particular ending data element within the data stream, wherein the second set of credits implicitly acknowledges the sequential data elements specified by the first set of credits; and

receiving, at the receiver, sequential data elements specified by the second set of credits, the second set of credits specifying a non-overlapping range of the sequential data elements specified by the first set of credits.