Reliable multicast transport protocol

• US 8,612,617 B2
• Filed: 06/28/2007
• Issued: 12/17/2013
• Est. Priority Date: 06/28/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Yaqoob, Asad, Gemmell, David James
• Primary Examiner(s): TOWFIGHI, AFSHAWN M
• Application Number:
  US11/823,541
• Publication Number:
  US 20090006641A1
• Time in Patent Office: 2,364 Days
• Field of Search: 709230-237, 370310-430
• US Class Current: 709/230
• CPC Class Codes: H04L 12/1868 Measures taken after transmission, e.g. acknowledgments
• CPC Class Codes: H04L 12/1886 with traffic restrictions for efficiency improvement, e.g. involving subnets or subdomains
• CPC Class Codes: H04L 12/1895 for short real-time information, e.g. alarms, notifications, alerts, updates

Abstract

A semi-reliable multicast transport protocol uses multiple channels for communication between a server and multiple client devices. A join channel allows the sever to negotiate with client devices to join and exit a transmission session. A communication channel allows the server to communicate with client devices about a status of the transmission session. A polling channel initiated by a content transfer protocol, which runs on top of the transport protocol, transmits polling queries received from the content transfer protocol, receives client device responses to the polling queries, and passes the client device responses to the content transfer protocol. A data channel transmits data to client devices over a network.

Claims

1. A method for use in a computer system, the method comprising:

negotiating with a plurality of client devices, via a join channel, to join and exit a multicast transmission session at different times, wherein a first one of the plurality of client devices is permitted to join the multicast transmission session at a first time and wherein a second one of the plurality of client devices is permitted to join the multicast transmission session at a second time, wherein the first time is different from the second time, and wherein each of the plurality of client devices is able to receive the entirety of content associated with the multicast transmission session regardless of when each of the plurality of client devices joins the multicast transmission session;

communicating with the plurality of client devices, via a query channel, about a status of the multicast transmission session;

via a polling channel;

(i) transmitting polling queries received from a content transfer protocol, (ii) receiving, from the plurality of client device, responses to the polling queries, and (iii) passing the responses to the content transfer protocol;

transmitting data to the plurality of client devices via a data channel;

querying the plurality of client devices to determine a round trip time associated with each of the plurality of client devices;

selecting a single representative client device from the plurality of client devices to be a sender of acknowledgement messages based upon the determined round trip times; and

advertising a minimum negative acknowledgement back-off interval based on the round trip time associated with the selected representative client device.

2. The method of claim 1 further comprising receiving, from the single representative client device, an acknowledgement message that includes a cumulative identification of all received data packets by the single representative client device.

3. The method of claim 1 further comprising:

generating a source path message that includes one or more current protocol values, the one or more current protocol values comprising the advertised minimum negative acknowledgement back-off interval and the selected single representative client device; and

upon generation of the source path message, implementing a delay period configured to provide a window of time to receive, responsive to the source path message, an acknowledgement message from the selected single representative client device.

4. The method of claim 1 further comprising, at a client device of the plurality of client devices, and responsive to detecting loss of a data packet:

when the client device is not the single representative client device;

calculating a random back-off period based on the minimum negative acknowledgement back-off interval;

delaying, for the random back-off period, transmission of a negative acknowledgement message corresponding to the data packet; and

when the client device is the single representative client device;

transmitting the negative acknowledgement message without waiting for any back-off period.

5. The method of claim 4 further comprising, at the client device, when the client device not the single representative client device:

determining that the negative acknowledgement message need not be transmitted based on the receipt of at least one of;

(a) receipt of the data packet, (b) receipt of repair data corresponding to the data packet, or (c) receipt of a negative acknowledgement confirmation message corresponding to the negative acknowledgement message; and

responsive to determining the negative acknowledgement message need not be transmitted, not transmitting the negative acknowledgement message.

6. The method of claim 1 further comprising suppressing immediate negative acknowledgement messages from all client devices except the single representative client device.

7. The method of claim 6 further comprising:

transmitting a negative acknowledgement confirmation message that includes a data loss rate reported from the single representative client device; and

responsive to an indication that a particular client device other than the single representative client device has a local data loss rate worse than the data loss rate reported from the single representative client device, allowing a negative acknowledgement suppression waiver at the particular client device.

8. The method of claim 1 wherein at least a first client device of the plurality of client devices is an initial joiner, and wherein at least a second client device of the plurality of client devices is late joiner.

9. The method of claim 8, wherein transmitting data to client devices via a data channel further comprises sending a block of a data file corresponding to the transmission session to the first client device prior to the second client device joining the transmission session.

10. The method of claim 1

wherein negotiating with a plurality of client devices comprises:

receiving, from a first client device of the plurality of client devices, a join request comprising a join request timestamp;

assigning, responsive to the join request, a first client identifier for the first client device;

sending, to the first client device, responsive to the join request, a join acknowledgement comprising;

(a) the assigned first client identifier, (b) the join request timestamp, (c) a first timestamp, (d) a first minimum NAK back-off time, and (e) a first maximum NAK back-off time; and

receiving, from the first client device, responsive to the join acknowledgement, a first query channel reply packet comprising;

(a) the first client identifier, and (b) the first timestamp;

wherein (i) the join channel is configured to use unicast endpoints, (ii) a query channel is configured to transmit to the plurality of joined clients over a first unreliable base multicast protocol, (iii) the querying the plurality of client devices to determine a round trip time occurs via the query channel, (iv) the polling channel is configured to transmit to the plurality of joined clients over a second unreliable base multicast protocol, and (v) the data channel is configured to transmit to the plurality of joined clients over a third unreliable base multicast protocol; and

wherein communicating with the plurality of client devices comprises;

sending, to the plurality of joined client devices, a second query channel client packet comprising;

(a) a second back-off interval, and (b) a second timestamp; and

receiving, from the first client device and responsive to the second query channel client packet, a second query channel reply packet comprising;

(a) the first client identifier, (b) the second timestamp, and (c) a second delta time;

determining a third round trip time for the first client device, the third round trip time selected from the group consisting of a first round trip time and a second round trip time, wherein the determining the first round trip time is based on the first timestamp and the time the first query channel reply packet was received, and wherein the determining the second round trip time is based on the second timestamp, the second delta time, and the time the second query channel reply packet was received, and further wherein the first client device is selected as the single representative device based on the third round trip time; and

wherein transmitting data to the plurality of client devices via the data channel comprises;

transmitting, to the joined client devices, a source path message, the source path message advertising current protocol values, wherein the current protocol values include the minimum negative acknowledgement back-off interval and an indication that the first client is the single representative client device, and wherein advertising the minimum negative acknowledgement back-off interval includes transmitting the source path message; and

transmitting, to the joined client devices, a data packet comprising a transport header, a content header, and a content payload, wherein the transport header includes an indication that the first client is the single representative client device.

11. The method of claim 10, wherein the first unreliable base multicast protocol uses user datagram protocol multicast for transmission to the plurality of joined clients, the second unreliable base multicast protocol uses user datagram protocol multicast for transmission to the plurality of joined clients, and the third unreliable base multicast protocol uses user datagram protocol multicast for transmission to the plurality of joined clients.

12. A reliable multicast transmission system comprising:

a server computing device, the server computing device comprising;

a transport protocol layer, the content transfer protocol layer comprising;

a join channel for negotiating with a plurality of client devices to join and exit a multicast transmission session at different times, wherein a first one of the plurality of client devices is permitted to join the multicast transmission session at a first time and wherein a second one of the plurality of client devices is permitted to join the multicast transmission session at a second time, wherein the first time is different from the second time, and wherein each of the plurality of client devices is able to receive the entirety of content associated with the multicast transmission session regardless of when each of the plurality of client devices joins the multicast transmission session;

a query channel for communicating with the plurality of client devices about a status of the multicast transmission session;

a polling channel that transmits polling queries to the plurality of client devices and responses to the polling queries from the plurality of client devices; and

a data channel for transmitting a data file to the plurality of client devices;

wherein the transport protocol layer is further configured to;

suppress immediate acknowledgement messages from each of the plurality of client devices except for a single representative client device, wherein the single representative client device is selected based on round trip times associated with the plurality of client devices; and

advertise a minimum negative acknowledgement back-off duration based on the round trip time corresponding to the single representative client device; and

a content transfer protocol layer, the content transfer protocol layer comprising;

a data management function that identifies the data file for the multicast transmission session and provides the data file to the transport protocol layer in a form suitable for transmission; and

a polling management function that generates the polling queries to monitor reliability of data transmissions by the transport protocol layer, pass the polling queries to the transport protocol layer for transmission to the client devices, and receive responses to the polling queries by the plurality of client devices from the transport protocol layer.

13. The system of claim 12, wherein the polling queries ask the plurality of client devices for a number of blocks of the data file being transmitted that the plurality of client devices have yet to receive.

14. The system of claim 13, wherein the data management function further provides non sequential access to blocks of the data file to provide only blocks of the data file that the plurality of client devices have yet to receive.

15. The system of claim 13, wherein the data management function further removes duplicate block requests to create a single list of blocks to access for transmission.

16. The system of claim 15, wherein when removing duplicate block requests, the data management function begins with blocks requested by an oldest joining client device of the plurality of client devices and merges only blocks requested by other client devices of the plurality of client devices that joined the transmission session within a set time period of the oldest joining client device.

17. The system of claim 12, wherein the data management function guarantees integrity of the data file during the transmission session.

18. A method in a computer system for providing reliable multicast transmissions comprising:

negotiating with a plurality of client devices to join and exit a multicast transmission session at different times, wherein a first one of the plurality of client devices is permitted to join the multicast transmission session at a first time and wherein a second one of the plurality of client devices is permitted to join the multicast transmission session at a second time, wherein the first time is different from the second time, and wherein each of the plurality of client devices is able to receive the entirety of content associated with the multicast transmission session regardless of when each of the plurality of client devices joins the multicast transmission session;

communicating a query to the plurality of client devices requesting a status of the transmission session;

receiving a polling query initiated by a content transfer protocol;

transmitting the polling query to the plurality of client devices;

receiving responses to the polling query from the plurality of client devices;

passing responses to the polling query to the content transfer protocol;

transmitting a data file to the plurality of client devices;

determining round trip times associated with the plurality of client devices;

selecting one of the plurality of client devices to be a representative client device based upon the determined round trip times, wherein the representative client device transmits negative acknowledgement messages on behalf of the other client devices; and

advertising a minimum negative acknowledgement back-off time that corresponds to the round trip time associated with the selected representative client device, wherein the minimum negative acknowledgement back-off time indicates a minimum time for other client devices to wait before transmitting a negative acknowledgement message in response to missing a data packet.

19. The method of claim 18 further comprising providing non sequential access to blocks of the data file to provide only blocks of the data file that the plurality of client devices have yet to receive.