Method and system for dynamically adjusting transmit and receive parameters for handling negative acknowledgments in reliable multicast

• US 7,554,920 B2
• Filed: 03/04/2005
• Issued: 06/30/2009
• Est. Priority Date: 12/27/2001
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Alam, Mohammad Shabbir, Koti, Shirish R., Bahl, Pradeep
• Primary Examiner(s): Pham; Chi H
• Assistant Examiner(s): Faroul; Farah
• Application Number:
  US11/072,023
• Publication Number:
  US 20050147045A1
• Time in Patent Office: 1,579 Days
• Field of Search: 370/390, 370/235, 370/278, 370/312, 370/394, 370/408, 370/412, 370/445, 370/447, 370/448, 370/236, 370/282, 370/432, 709/235, 714/748, 445/422.1
• US Class Current: 370/236
• CPC Class Codes: H04L 1/1848 Time-out mechanisms
• CPC Class Codes: H04L 1/187 Details of sliding window management
• CPC Class Codes: H04L 1/1887 Scheduling and prioritising arrangements
• CPC Class Codes: H04L 2001/0093 Point-to-multipoint

Abstract

A method and system for multicast network transmissions dynamically sets response time parameters for handling negative acknowledgments (NAKs). When the sender receives a NAK for a lost packet, it returns an NAK confirmation (NCF), waits for a back-off time before sending requested repair data, and then waits for a “linger time” during which the sender does not respond to other NAKs for the same lost packet. The back-off time and the linger time are dynamically set according to the position of the requested sequence number in the sender'"'"'s transmit window such that the back-off time is shorter when the requested data is closer to being flushed out of the transmit window. After receiving the NCF, the receiver waits for a timeout period and resends the NAK if no repair data is received. The timeout period for data receipt is dynamically set according to a statistical average time for receiving repair data from the sender and the estimated sender'"'"'s transmit window size.

Claims

1. A method to facilitate multicast transmission, the method comprising:

receiving a negative acknowledgment from a receiver identifying a sequence number of a missing packet of the multicast transmission received by the receiver;

transmitting a confirmation of receipt of the negative acknowledgment;

setting a back-off time and a linger time based on a location of the sequence number within a transmit window maintained by the sender for retaining recently transmitted data of the multicast transmission for data repairs, wherein the response back-off time decreases as the sequence number approaches a trailing edge of the transmit window;

sending repair data for the missing packet after expiration of the back-off time;

waiting for expiration of the linger time after sending the repair data for the missing packet and ignoring other negative acknowledgments for the missing packet received during the linger time; and

adjusting a send rate using a predetermined tolerance level, the tolerance level based on a ratio of repair data packets sent versus all data packets sent.

2. The method of claim 1, further comprising evaluating the ratio of repair data packets sent versus all data packets sent at a predetermined sample period, and if the ratio exceeds the tolerance level then decrementing the send rate by a fraction of the requested send rate.

3. The method of claim 2, further comprising decrementing the send rate until the ratio of repair data sent versus all data packets sent does not exceed the tolerance level.

4. The method of claim 2, further comprising evaluating the ratio of repair data packets sent versus all data packets sent at the predetermined sample period, and if the ratio is less than the tolerance level and the send rate was previously decreased then incrementing the send rate until the send rate reaches the tolerance level.

5. The method of claim 1, further comprising determining the back-off time based at least in part on a separation between the sequence number and the trailing edge of the transmit window.

6. The method of claim 1, further comprising determining a response dwell time based on the back-off time and linger time that is constant for a session of the multicast transmission, and determining a ratio of the back-off time to the linger time based on a separation between the sequence number and the trailing edge of the transmit window.

7. A method to facilitate multicast transmission, the method comprising:

receiving original data packets of the multicast transmission from the sender;

detecting a packet missing from the multicast transmission;

sending a negative acknowledgment to the sender identifying the missing packet;

receiving a confirmation matching the negative acknowledgment;

setting a data waiting timeout according to a statistical average time for receiving repair data from the sender and a size of a transmit window maintained by the sender for retaining recently transmitted data of the multicast transmission for data repairs;

waiting for repair data for the missing packet up to expiration of the data waiting timeout,

determining whether a cycle of receiving a confirmation, setting, waiting, and resending has been repeated a pre-selected maximum number of times; and

resending the negative acknowledgment after expiration of the data waiting timeout if the repair data for the missing packet is not received and the cycle has not been repeated the pre-selected maximum number of times.

8. The method of claim 7, further comprising determining the data waiting timeout based at least in part on a number of retries of the data retry cycle already performed by the receiver.

9. The method of claim 8, further comprising increasing the data waiting timeout based on the number of retries already performed for a first portion of the pre-selected maximum number of retries.

10. The method of claim 9, further comprising determining the data waiting timeout for the first portion of the pre-selected maximum number of retries based on the statistical average time for receiving repair data multiplied by a factor that increases with the number of retries.

11. The method of claim 7, further comprising estimating a size of a transmit window of the sender based at least in part on a transmission time.

12. The method of claim 11, further comprising determining the data waiting timeout based at least in part on the estimated size of the transmit window.

13. The method of claim 12, further comprising determining the data waiting timeout based at least in part on at least of a measurement or estimation of network latency, a measurement or estimation of network loss rate, or a quantity of repair packets preceding a requested repair packet.