Finite Buffers and Fast Multicast
Danzig, Peter B.
Technical Report Identifier: CSD-88-489
Abstract: When many or all of the recipients of a multicast message respond to the multicast's sender, their responses may overflow the sender's available buffer space. Buffer overflow is a serious, known problem of broadcast-based protocols, and can be troublesome when as few as three or four recipients respond. We develop analytical models that calculate the expected number of buffer overflows that can be used to estimate the number of buffers necessary for an application. The common cure for buffer overflow requires that recipients delay their responses by some random amount of time in order to increase the minimum spacing between response messages, eliminate collisions on the network, and decrease the peak processing demand at the sender. In our table driven algorithm, the sender tries to minimize the multicast's latency, the elapsed time between its initial transmission of the multicast and its reception of the final response, given the number of times (rounds) it is willing to retransmit the multicast. It includes in the multicast the time interval over which it anticipates receiving the response, the round timeout. We demonstrate that the latency of single round multicasts exceeds the latency of multiple round multicasts. We show how recipients minimize the sender's buffer overflows by independently choosing their response times as a function of the round's timeout, sender's buffer size, and the number of other recipients.