Technical Report TR-1999-15

BibliographyMaihöfer, Christian; Rothermel, Kurt: Constructing Height-Balanced Multicast Acknowledgment Trees with the Token Repository Service.
University of Stuttgart, Faculty of Computer Science, Technical Report No. 1999/15.
12 pages, english.
CR-SchemaC.2.2 (Network Protocols)
C.2.3 (Network Operations)
C.2.4 (Distributed Systems)
Keywordsmulticast; reliable multicast; ERS; token repository service; ACK tree; TRS; height-balanced
Abstract

Many reliable multicast protocols use so-called ACK-trees to avoid the well-known acknowledgment implosion problem in case of large multicast groups. For constructing ACK trees, usually expanding ring search techniques are applied. Our simulation results show that those techniques have scalability problems itself. In this paper, we propose a novel approach for building ACK trees, the token repository service (TRS). The basic concept of our approach is a token, which represents the right to connect to a certain node in the corresponding ACK tree. For each node in the ACK tree TRS stores a token for each potential successor this node can accept. A node that wants to join a group requests TRS for an appropriate token. The TRS protocol described in this paper provides for height-balanced ACK trees. Our simulation results show that the created height-balanced ACK trees have significant benefits. They reduce round trip delay and optimize reliability in case of node failures. Moreover, compared to expanding ring search, TRS results in a much lower message overhead.

Full text and
other links
HTML (generated from PostScript)
Department(s)University of Stuttgart, Institute of Parallel and Distributed High-Performance Systems, Distributed Systems
Entry dateNovember 24, 1999
   Publ. Department   Publ. Institute   Publ. Computer Science