Sliding Key Triggered Retransmissions

When a instance of nte sends a summary packet, it starts upon the process of sending a sequence of keys. When a receiver matches a key sent by the sender, it can immediately send its retransmission request (which can be many objects if necessary) along with the key that was matched. On receiving this request, the sender then starts the retransmission of the missing data.

  

Figure 8.4: Sliding Key Triggered Retransmission Requests

What causes this to be scalable is the nature of the keys involved. The sender generates a random integer when it creates its summary message. Upon receipt of the summary message, the receiver also generates a random key. Then the sender sends its key along with a key mask which indicates the bits in the sender's key that must be matched in order for the receiver to send a retransmission request. This key/mask pair is sent several times (typically 2 or 3 times) and then if no retransmission request is forthcoming, the number of bits indicated by the mask is reduced by one, and the key/new mask pair is sent again. If no retransmission request is forthcoming by the time the mask indicates no bits need to be matched, then the process is started again with a new random key, a new summary report, and possibly a new current site. If no change has occurred since the previous summary report, the rate of sending sliding keys is reduced to half the rate for the previous round or until it reaches a preset lower rate limit. This process is illustrated in figure 8.4.

This is based on a scheme[#!ian:94!#] devised by Ian Wakeman for the solicitation of congestion report messages in multicast based adaptive video coders.

As the session messages give us a reasonable approximation of the size of the conference at the point when we generate the summary message, the sliding key can be started close to the point where it would be expected to elicit the first response if all receivers need a retransmission. For a typical thousand way conference, where only one receiver requires a retransmission, with each key/mask pair sent twice per round and an estimated worst case RTT of 250ms, this results in 4 (small) packets per second and a maximum delay of 5 seconds before requesting retransmission. Note that this is a much shorter time than can be achieved by having each receiver randomly choose a delay from a sufficiently large uniform interval to ensure approximately one retransmission request is made. If the conference was smaller, or more sites had suffered loss, this time would be reduced.