Data transmission using common sliding window

• US 7,072,973 B1
• Filed: 06/19/2001
• Issued: 07/04/2006
• Est. Priority Date: 06/19/2001
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Schrier, Evan J., Boswell, James M., Ogus, Aaron W., Toll, Roderick M., Newson, Paul E., Narayan, Michael J.
• Primary Examiner(s): Harrell, Robert B.
• Application Number:
  US09/884,634
• Time in Patent Office: 1,841 Days
• Field of Search: 709/230, 709/231, 709/232, 340/465, 340/470
• US Class Current: 709/232
• CPC Class Codes: G06F 13/387 for adaptation of different data processing systems to different peripheral devices, e.g. protocol converters for incompatible systems, open system
• CPC Class Codes: H04L 1/1635 Cumulative acknowledgement, i.e. the acknowledgement message applying to all previous messages
• CPC Class Codes: H04L 1/1671 the supervisory signal being transmitted together with control information
• CPC Class Codes: H04L 1/1685 the supervisory signal being transmitted in response to a specific request, e.g. to a polling signal
• CPC Class Codes: H04L 1/1809 Selective-repeat protocols
• CPC Class Codes: H04L 1/1832 Details of sliding window management
• CPC Class Codes: H04L 1/1838 for semi-reliable protocols, e.g. for less sensitive applications such as streaming video buffer level management for video bitstream receiver H04N21/44004
• CPC Class Codes: H04L 1/1841 Resequencing
• CPC Class Codes: H04L 1/187 Details of sliding window management
• 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/165 Combined use of TCP and UDP protocols; selection criteria therefor

Abstract

A networking protocol that supports the sending of reliable and non-reliable data in a common sliding window. Data to be transmitted according to the protocol is packaged into packets, where each packet has a header. Each packet carries a sequence number in the header, where the sequence numbers are successively assigned to each outgoing packet. As the packets are received, the recipient of the packets keeps track of the sequence numbers of received packets to determine whether any packets are missing and selectively acknowledges those packets that have been received. The selective acknowledgment is performed using a mask, where each bit in the mask indicates the presence or absence of a packet as an offset from a reference value. Based on the mask, the sender re-sends non-received reliable packets, and creates a second mask which indicates non-reliable non-received packets that will not be re-sent.

Claims

1. A method of sending first and second data from a first computing device to a second computing device remote from the first computing device, the first computing device and second computing device being communicatively connected by a network, the method comprising:

at said first computing device, creating a first packet which includes the first data and a first flag which indicates that said first packet is to be sent reliably;

at said first computing device, creating a second packet which includes the second data and a second flag which indicates that said second packet is to be sent non-reliably;

sending said first packet from the first computing device to the second computing device using the network;

determining that a first number of packets that have been sent from the first computing device to the second computing device and for which acknowledgement has not been received by the first computing device does not exceed a second number; and

sending said second packet from the first computing device to the second computing device using the network.

2. The method of claim 1, further comprising:

at the first computing device, receiving receipt-indication data which indicates that said first packet was not received;

determining that said first packet was sent reliably; and

re-sending said first packet from the first computing device to the second computing device.

3. The method of claim 2, wherein said first packet includes a first sequence number, wherein said receiving receipt-indication data which indicates that said first packet was not received includes:

receiving a second sequence number and a mask, said mask having a plurality of bits, each of said bits having an offset from a reference position in said mask, a specific bit from among said bits having a value of one, said specific bit from among said bits having a first offset from said reference position which corresponds to a second offset of said first sequence number from said second sequence number.

4. The method of claim 1, further comprising:

at the first computing device, receiving receipt-indication data which indicates that said second packet was not received;

determining that said second packet was sent non-reliably; and

sending, from the first computing device to the second computing device, a message which indicates that said second packet will not be re-sent.

5. The method of claim 4, wherein said second packet includes a first sequence number, wherein said receiving receipt-indication data which indicates that said second packet was not received includes:

receiving a second sequence number and a mask, said mask having a plurality of bits, each of said bits having an offset from a reference position in said mask, a specific bit from among said bits having a value of one, said specific bit from among said bits having a first offset from said reference position which corresponds to a second offset of said first sequence number from said second sequence number.

6. The method of claim 1, wherein said first packet comprises (a) a first header which includes said first flag, and (b) a body which includes the first data, and wherein said second packet comprises (a) a second header which includes said second flag, and (b) a body which includes the second data.

7. The method of claim 1, further comprising:

initializing a sequence number counter; and

incrementing said sequence number counter upon creation of a packet;

wherein said creation of said first packet comprises including a current value of said sequence number counter in said first packet and wherein said creation of said second packet comprises including said current value of said sequence number counter in said second packet.

8. The method of claim 1, further comprising:

receiving, at the first computing device, an acknowledgment that said first packet and said second packet have each been received by the second computing device.

9. A method of participating in communications with a first computing device, the method comprising:

at a second computing device remote from the first computing device, receiving a plurality of first packets, each of said packets including a sequence number;

at said second computing device, determining, based on said sequence numbers included in said plurality of first packets, that a second packet sent by the first computing device has not been received by the second computing device;

at said second computing device, sending to the first computing device an indication that said second packet has not been received, said indication comprising;

a reference number which is higher than or equal to a sequence number of said second packet; and

a mask having a plurality of bits which indicates, relative to said reference number, a sequence number of said second packet.

10. The method of claim 9, wherein each of said bits is located at an n-th offset into said mask, a lowest-order bit in the mask having a zero-th offset, and wherein a bit in said mask at an m-th offset is equal to one, m being equal to the sequence number of said second packet minus said reference number minus one.

11. The method of claim 9, wherein said reference number comprises an eight-bit number.

12. The method of claim 9, wherein said mask comprises a 32-bit data element.

13. The method of claim 9, wherein said indication further comprises a second mask having a plurality of bits which indicates, relative to said reference number, packets having sequence numbers more than a first number greater than said reference number, and wherein the sequence number of said second packet is greater than said first number.

14. A method of communicating with a computing device comprising:

sending to the computing device a first packet which includes;

(a) first data, and (b) an indication that said first packet is to be sent reliably;

sending to the computing device a second packet which includes;

(a) second data, and (b) an indication that said second packet is to be sent non-reliably;

receiving from the computing device an indication that said first packet and said second packet have not been received by the computing device;

re-sending said first packet to the computing device; and

sending to the computing device an indication that said second packet will not be re-sent.

15. The method of claim 14, wherein said first packet comprises a header which includes a command byte having a plurality of bits, a first of said plurality of bits comprising the indication that said first packet is to be sent reliably.

16. The method of claim 14, wherein said second packet has a sequence number associated therewith, and wherein said sending an indication that said second packet will not be re-sent comprises:

creating a third packet which includes;

a reference number;

a control byte having a plurality of bits, one or more of said plurality of bits indicating the presence in said third packet of one or more masks;

a mask having a plurality of bits, each of said bits corresponding to a packet sequence number relative to said reference number, the bit corresponding to the sequence number of said second packet indicating that said second packet will not be re-sent.

17. A device for communicating data in a computer network which connects the device to one or more remote devices, the device comprising:

a processor which executes computer-executable instructions;

a memory communicatively coupled to said processor, said memory storing;

first logic executable on said processor which receives (a) first data, (b) an indication of whether said first data is to be transmitted reliably or non-reliably, and (c) an identifier of a first one of the remote devices to which said first data is to be sent;

a sequence counter;

second logic executable on said processor which creates a package including (a) said first data, (b) second data indicative of said indication, and (c) a current value of said sequence counter, and which increments said sequence counter upon creation of said package;

a network interface which communicates said package to said first one of the remote devices over the computer network and which receives from said first one of the remote devices a selective acknowledgment indicative of whether said package has been received by said first one of the remote devices, said network interface being communicatively coupled to said memory and to the computer network;

said memory further storing;

third logic executable on said processor which creates a response that includes either (a) said first data, or (b) a message that said first data will not be re-sent, according to whether indication indicates reliable or non-reliable transmission of said first data.

18. The device of claim 17, wherein said message that said first data will not be re-sent comprises:

a reference number;

a mask having a plurality of bits, each of said bits corresponding to a sequence counter value relative to said reference number, wherein a one of said bits that corresponds to the sequence counter value of said package has a bit value which indicates that said first data will not be re-sent.

19. The device of claim 17, wherein said selective acknowledgment comprises:

a reference number;

a mask having a plurality of bits, each of said bits corresponding to a sequence counter value relative to said reference number, wherein a one of said bits that corresponds to the sequence counter value of said package has a bit value which indicates whether said package has been received by said first one of the remote devices.

20. A computer-readable storage medium having computer-executable instructions to perform a method of sending first and second data from a first computing device to a second computing device remote from the first computing device, the first computing device and second computing device being communicatively connected by a network, the method comprising:

at said first computing device, creating a first packet which includes the first data and a first flag which indicates that said first packet is to be sent reliably;

at said first computing device, creating a second packet which includes the second data and a second flag which indicates that said second packet is to be sent non-reliably;

sending said first packet from the first computing device to the second computing device using the network;

determining that a first number of packets that have been sent from the first computing device to the second computing and for which acknowledgement has not been received by the first computing device does not exceed a second number; and

sending said second packet from the first computing device to the second computing device using the network.

21. A computer-readable storage medium having computer-executable instructions to perform a method of participating in communications with a first computing device, the method comprising:

at a second computing device remote from the first computing device, receiving a plurality of first packets, each of said packets including a sequence number;

at said second computing device, determining, based on respective sequence numbers of said sequence numbers included in said plurality of first packets, that a second packet sent by the first computing device has not been received by the second computing device;

at said second computing device, sending to the first computing device an indication that said second packet has not been received, said indication comprising;

a reference number which is higher than or equal to a sequence number of said second packet; and

a mask having a plurality of bits which indicates, relative to said reference number, a sequence number of said second packet.

22. A computer-readable storage medium having computer-executable instructions to perform a method of communicating with a computing device, the method comprising:

sending to the computing device a first packet which includes;

(a) first data, and (b) an indication that said first packet is to be sent reliably;

sending to the computing device a second packet which includes;

(a) second data, and (b) an indication that said second packet is to be sent non-reliably;

receiving from the computing device an indication that said first packet and said second packet have not been received by the computing device;

re-sending said first packet to the computing device; and

sending to the computing device an indication that said second packet will not be re-sent.