Article

Free access

Finite buffers for fast multicast

Author:

P. B. DanzigAuthors Info & Claims

SIGMETRICS '89: Proceedings of the 1989 ACM SIGMETRICS international conference on Measurement and modeling of computer systems

Pages 108 - 117

https://doi.org/10.1145/75108.75384

Published: 01 April 1989 Publication History

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.

References

[1]

D. Clark, "The Structming of Systems Using Upcalls", l Oth Symp. on Operating System Prin. 19, 5 (Dee 1985), 171-180.

Digital Library

[2]

H.G. Perros and T. Altiok, "Approximate Analysis of Open Networks of Queues with Blocking: Tandem Configurations", TSE 12,3 (March 86 ), 450-n461. North Carolina State. University.

Digital Library

[3]

J.L. Wang and J. A. Silvester, "Throughput Optimization of the Adaptive Multi-Receiver Sdective-Repeat ARQ Protocol Over Broadcast Links", Proceedings oflCCC, Tel Aviv, Israel October 1988.

[4]

A. Ganz and I. Chlamtae, "Queueing Analysis of Finite Buffer Token Networks", S1GMETR1CS, Santa Fe, New Mexico, May 1988, 30-36.

Digital Library

[5]

J. Chang and N. F. Maxemchuk, "Reliable Broadcast Protocols", Trans. Computer Systems 2, 3 (Aug. 1984), 251-273.

Digital Library

[6]

D. R. Chedton and W. Zwaenepoel, "Distributed Process Groups in the V Kemer', Trans. Computer Systems 3, 2 (May 1985), 77-107.

Digital Library

[7]

E.J. Feinler, O. J. Jacobsen, M. K. Stahl and C. A. Ward, DDN Protocol Handbood, Defense Communications Agency, December 1985.

[8]

L.F. Cabrera, E. Hunter, M. J. Karels and D. A. Mosher, "User-Process Communication Performance In Netwoks of Computers", TSE 14, 1 (Jan. 1988), 38-53.

Digital Library

[9]

R. Gusella and S. Zatti, "An Election Algorithm for a Distributed Clock Synchronization Program", 1EEE 6th International Conference on Distributed Computing Systems, Boston, May 1986.

[10]

M.M. Theimer and K. A. Lantz, Finding Idle Machines in a Workstation-based Distributed System, 8th International Conference on Distributed Computing Systems, June 1988.

[11]

S.M. Ross, Stochastic Processes, John Wiley & Sons, New York, NY, 1983.

[12]

W. Feller, An Introduction to Probability Theory and Its Applications Volume i and 2, John Wiley & Sons, New York, NY, 1970.

[13]

S. M. Ross, Introduction to Stochastic Dynamic Programming, Academic Press, New York, NY, 1983.

Digital Library

[14]

R. Weinstock, Calculus of Variations, McGraw-Hill, New York, NY, 1952.

[15]

M. Avriel, Nonlinear Programming: Analysis and Methods, Prentice Hall, Englewood Cliffs, NJ, 1976.

[16]

B. Simons and L. G. Votta, "The Optimal Retry Distribution for Lightly Loaded Slotted Aloha Systems", IEEE Transactions on Communications COM-33, 7 (July 1985), 724-725.

[17]

P.B. Danzig, "Buffer Overflow in Multicast", IEEE Trans. on Con~uters Special Issue on Performance Evaluation, (Submitted).

[18]

S. Deering, "Multicast Routing in intemetworks and Extended LANSs", SIGCOMM '88 Symposium, Aug. 16- 19, 1988, 55-64.

Digital Library

Cited By

Gemmell JLiebeherr JBassett D(1997)An API for scalable reliable multicastProceedings of Sixth International Conference on Computer Communications and Networks10.1109/ICCCN.1997.623291(60-64)Online publication date: 1997
https://doi.org/10.1109/ICCCN.1997.623291
Danzig P(1994)Flow Control for Limited Buffer MulticastIEEE Transactions on Software Engineering10.1109/32.26375120:1(1-12)Online publication date: 1-Jan-1994
https://dl.acm.org/doi/10.1109/32.263751
Stephenson PBirman K(1991)Fast causal multicastACM SIGOPS Operating Systems Review10.1145/122120.12212725:2(75-79)Online publication date: 1-Apr-1991
https://dl.acm.org/doi/10.1145/122120.122127
Show More Cited By

Index Terms

Finite buffers for fast multicast

Recommendations

Finite buffers for fast multicast

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 ...
Finite Buffers and Fast Multicast
Sizing router buffers
SIGCOMM '04: Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications

All Internet routers contain buffers to hold packets during times of congestion. Today, the size of the buffers is determined by the dynamics of TCP's congestion control algorithm. In particular, the goal is to make sure that when a link is congested, ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMETRICS '89: Proceedings of the 1989 ACM SIGMETRICS international conference on Measurement and modeling of computer systems

April 1989

242 pages

ISBN:0897913159

DOI:10.1145/75108

Chairman:
Domenico Ferrari
Univ. of California, Berkeley

ACM SIGMETRICS Performance Evaluation Review Volume 17, Issue 1
May 1989
209 pages
ISSN:0163-5999
DOI:10.1145/75372
Editor:
Blaine D. Gaither
Gould Inc., San Diego, CA
Issue’s Table of Contents

Copyright © 1989 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGMETRICS: ACM Special Interest Group on Measurement and Evaluation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 April 1989

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SIGMETRICS89

Sponsor:

SIGMETRICS

SIGMETRICS89: Performance 89 Intl Conference on Measurement & Modeling of Computer Systems

May 23 - 26, 1989

California, Oakland, USA

Acceptance Rates

Overall Acceptance Rate 459 of 2,691 submissions, 17%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
335
Total Downloads

Downloads (Last 12 months)77
Downloads (Last 6 weeks)7

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Gemmell JLiebeherr JBassett D(1997)An API for scalable reliable multicastProceedings of Sixth International Conference on Computer Communications and Networks10.1109/ICCCN.1997.623291(60-64)Online publication date: 1997
https://doi.org/10.1109/ICCCN.1997.623291
Danzig P(1994)Flow Control for Limited Buffer MulticastIEEE Transactions on Software Engineering10.1109/32.26375120:1(1-12)Online publication date: 1-Jan-1994
https://dl.acm.org/doi/10.1109/32.263751
Stephenson PBirman K(1991)Fast causal multicastACM SIGOPS Operating Systems Review10.1145/122120.12212725:2(75-79)Online publication date: 1-Apr-1991
https://dl.acm.org/doi/10.1145/122120.122127
Danzig P(1991)An analytical model of operating system protocol processing including effects of multiprogrammingACM SIGMETRICS Performance Evaluation Review10.1145/107972.10797419:1(11-20)Online publication date: 2-Apr-1991
https://dl.acm.org/doi/10.1145/107972.107974
Danzig PKeller T(1991)An analytical model of operating system protocol processing including effects of multiprogrammingProceedings of the 1991 ACM SIGMETRICS conference on Measurement and modeling of computer systems10.1145/107971.107974(11-20)Online publication date: 2-Apr-1991
https://dl.acm.org/doi/10.1145/107971.107974
Stephenson PBirman K(1990)Fast causal multicastProceedings of the 4th workshop on ACM SIGOPS European workshop10.1145/504136.504147(1-5)Online publication date: 3-Sep-1990
https://dl.acm.org/doi/10.1145/504136.504147
(2016)Virtualized I/OAttaining High Performance Communications10.1201/b10249-17(261-282)Online publication date: 19-Apr-2016
https://doi.org/10.1201/b10249-17
Heinrichs BHeinrichs B(1996)LiteraturMultimedia im Netz10.1007/978-3-642-79203-8_8(233-248)Online publication date: 1996
https://doi.org/10.1007/978-3-642-79203-8_8
Ammar M(1994)Probabilistic multicast: generalizing the multicast paradigm to improve scalabilityProceedings of INFOCOM '94 Conference on Computer Communications10.1109/INFCOM.1994.337653(848-855)Online publication date: 1994
https://doi.org/10.1109/INFCOM.1994.337653
Ammar M(1993)Probabilistic Multicast: Generalizing the Multicast Paradigm to Improve ScalabilityThe 8th IEEE Workshop on Computer Communications10.1109/CMPCMM.1993.659081(0_92-0_99)Online publication date: 1993
https://doi.org/10.1109/CMPCMM.1993.659081
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents