A class of tree algorithms with variable message length

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A class of tree algorithms with variable message length

Full text

Pdf (453 KB)

Source

Applications, Technologies, Architectures, and Protocols for Computer Communication archive
Proceedings of the ACM SIGCOMM symposium on Communications architectures and protocols: tutorials & symposium table of contents

Montréal, Quebec, Canada, United States

Pages: 242 - 247

Year of Publication: 1984

ISBN:0-89791-136-9

Also published in ...

Authors

D. P. Gerakoulis	Electrical Engineering Department, City College of New York, New York, N.Y.
T. N. Saadawi	Electrical Engineering Department, City College of New York, New York, N.Y.
D. L. Schilling	Electrical Engineering Department, City College of New York, New York, N.Y.

Sponsor

SIGCOMM: ACM Special Interest Group on Data Communication

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 21, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/800056.802084 What is a DOI?

ABSTRACT

In this paper we present and analyze a class of tree algorithms with variable message length. First we analyze the algorithm according to which a message, consisting of a number of packets, is transmitted continuously after the successful transmission of its first packet, referred to as the tree algorithm with variable message length. The analysis of the algorithm is presented for the two cases of small number of users and of large number of users. In both cases the analysis shows a considerable improvement for the maximum throughput, which gets larger as the average message length increases. Second, we present the reservation tree algorithm, R-Tree, which uses &test& packets instead of the message's first packet to resolve the collision among users. The R-Tree maximum throughput approaches one as the average message length increases, which for single packet messages can be a maximum throughput of 0.776 for infinite number of users.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	John Capetanakis, "Generalized TDMA: The Multi-Accessing Tree Protocol," IEEE Transactions on Communications, vol. COM-27, October 1979.
	2	James Massey, "Collision Resolution Algorithms and Random-Access Communications," School of Engineering and Applied Science, UCLA, CA 90024
	3	T.N. Saadawi and A. Ephremides, "Analysis of the Tree Algorithm with a Finite Number of Buffered Users," ICC December '81.
	4	T.T. Liu and D. Towsley, "Window and Tree Protocols for Satellite Channels," INFCOM April '83.
	5	S. Lam, "Packet Broadcast Networks-A Performance Analysis of the R-Aloha Protocol," IEEE Transactions on Computers, July 1980.
	6	R. Cruz and B. Hujek, "A new upper bound to the throughput of the Multiaccess Broadcast Channel," IEEE Transactions on Information Theory, May '82.
	7	M.G.Hlachyj and R. Gallager, "Multiaccess of a Slotted Channel by finitely many users," Proceedings NTC81 New Orleans.
	8	M.L. Molle, "On the Capacity of infinite: population Multi Access Protocols," IEEE Transactions on Information Theory, May '82.
	9	T. Berger, N. Mehravari and G. Manson, "On Genie-Aided Upper Bounds to Multiple Access Contention Resolution Efficiency," International Symposium on Information Theory, Feb. '82.