A class of tree algorithms with variable message length

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

• 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.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.4 Communications Management
          Subjects: Message sending

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Markov processes

General Terms:
Algorithms, Management