Browsing by Author "Maihöfer, Christian"

Now showing 1 - 4 of 4

Open Access
Constructing height-balanced multicast acknowledgment trees with the token repository service
(1999) Maihöfer, Christian; Rothermel, Kurt
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.
Open Access
A delay analysis of tree-based reliable multicast protocols
(2001) Maihöfer, Christian; Rothermel, Kurt
We present a comparative delay analysis of tree-based reliable multicast protocols and show the influence of varying sending rates, group sizes, packet loss probabilities and branching factors of the control tree. Besides the average delivery delay we consider the delay to reliably deliver all packets and the round trip delay. The former two examines the delay between generation of a packet at the sender and correct reception at a randomly chosen receiver or all receivers, respectively. The latter is the delay between generation of a packet at the sender and reception of all acknowledgment packets at the sender. Our numerical results show that all tree-based protocols provide low delays and good scalability. From the four considered protocol classes, NAK-based protocols achieve the best scalability but ACK-based protocols achieve the lowest delays. An important aspect of our work is to be of practical relevance rather than being of only theoretical nature. Therefore, we have compared the analytical results with a RMTP and TMTP simulation. Both show similar results which confirms that our analysis can help to choose a suitable protocol and to tune them for improved performance.
Open Access
A robust and efficient mechanism for constructing multicast acknowledgment trees
(1999) Rothermel, Kurt; Maihöfer, Christian
A great variety of todays networked applications require a reliable multicast service. A number of the proposed reliable multicast protocols use a positive acknowledgment scheme, which returns ACKs to the sender to confirm correct delivery. To avoid the well-known implosion problem in the case of large receiver groups, often a tree-based approach is used, i.e., receivers are organized in a tree and ACK messages are passed along the edges of this so-called ACK tree. For building up this tree variations of the Expanding Ring Search (ERS) scheme have been proposed. However, our simulations show that ERS scales poorly. In this paper, we propose an alternative scheme for building up ACK trees. This scheme is based on a so-called token repository service, wherena token represents the right to connect to a certain node in the corresponding ACK tree. Nodes that want to join a group just request a token for this group from the (distributed) token repository service. Our simulations show that our scheme causes a much lower message overhead than ERS. Moreover, the quality of the resulting ACK trees in terms of delay and reliability is in many cases higher if generated with our scheme.
Open Access
Skalierbare und zuverlässige Gruppenkommunikation im Internet
(2002) Maihöfer, Christian; Rothermel, Kurt (Prof. Dr. rer. nat. Dr. h.c.)
Multicast erlaubt die bandbreitenschonende Auslieferung einer Nachricht an eine Gruppe von Empfängern. Anwendungen wie Informations- und Softwareverteilung an große Empfängergruppen, Audio- und Videokonferenzen, verteiltes Rechnen und verteilte Spiele lassen sich mit einem Multicast-Dienst effizient realisieren. Eine Reihe von Anwendungen erfordert dabei eine zuverlässige Nachrichtenauslieferung, die über den im Internet verfügbaren unzuverlässigen IP-Multicast-Dienst hinausgeht. Aufbauend auf IP-Multicast wird eine zuverlässige Nachrichtenauslieferung mittels Empfangsbestätigungen und Übertragungswiederholungen durch nicht-hierarchische oder hierarchische Transportprotokolle erreicht. Wie sich im Verlauf der Arbeit zeigen wird, erlauben lediglich hierarchische Transportprotokolle die skalierbare Realisierung eines zuverlässigen Multicast-Diensts zur Gruppenkommunikation. Diese ordnen alle Gruppenmitglieder in eine Hierarchie ein, die Kontrollbaum genannt wird. Durch den Kontrollbaum können notwendige Übertragungswiederholungen lokal begrenzt werden und müssen nicht mehr notwendigerweise vom ursprünglichen Sender durchgeführt werden. Die Verteilung dieser Last auf andere Gruppenmitglieder ermöglicht einen mit der Mitgliederzahl skalierbaren Dienst. Die Voraussetzung für den praktischen Einsatz ist ein skalierbares Verfahren zum Aufbau der Kontrollbäume. Mit dem Token-Repository-Service (TRS) wird in dieser Arbeit ein effizientes Verfahren zum Aufbau der Kontrollbäume vorgestellt. Drei Realisierungsvarianten des TRS-Diensts, TRS-R, TRS-K und TRS-M, erlauben unterschiedlichste Anforderungen zu berücksichtigen. Das wesentliche Entwurfskriterium aller Varianten ist eine skalierbare und effiziente Realisierung. Vergleichende Berechnungen und Simulationen mit alternativen Ansätzen unterstreichen nicht nur die Tragfähigkeit des TRS-Diensts. Dieser stellt momentan die einzige skalierbare Lösung zum Aufbau von Kontrollbäumen dar. Aufgrund der Unabhängigkeit des TRS-Diensts von einem Multicast-Routing-Protokoll ist es zudem die einzige Lösung, die durchgängig im gesamten Internet eingesetzt werden kann. Zur Erleichterung der Auswahl eines geeigneten zuverlässigen Multicast-Transportprotokolls und zur optimalen Konfiguration eines ausgewählten Transportprotokolls mit dem TRS-Dienst wird eine ausführliche probabilistische Analyse durchgeführt. Ausgangspunkt der Analyse ist nicht die Untersuchung konkreter Protokolle, sondern die Identifizierung wichtiger generischer Protokollklassen und deren anschließende Beurteilung. Dabei ergeben sich bedeutende Unterschiede bezogen auf den Bandbreitenbedarf, den Durchsatz und die Nachrichtenverzögerungen. Die Evaluation zeigt vielfache Vorteile für hierarchische Verfahren. Diese bieten nicht nur Skalierbarkeit, auch bezüglich des verursachten Nachrichtenaufwands, des Durchsatzes und der erzielbaren Nachrichtenverzögerung sind sie durch eine Verteilung der Last und kürzere Kommunikationswege gegenüber nicht-hierarchischen Protokollen im Vorteil. Als ein wesentlicher Parameter zur Konfiguration hierarchischer Transportprotokolle wird der Verzweigungsgrad des Kontrollbaums identifiziert werden. Im Gegensatz zu bisherigen Verfahren ermöglicht es der TRS-Dienst den Verzweigungsgrad flexibel zu konfigurieren. Die Analysen und Simulationen zeigen, dass bei einer geeigneten Wahl des Verzweigungsgrads der Durchsatz und die Verzögerung des zuverlässigen Transportprotokolls beträchtlich verbessert werden kann. Zusammenfassend erlaubt es der vorgestellte Token-Repository-Service durch seinen skalierbaren Kontrollbaumaufbau erstmals, zuverlässige Multicast-Kommunikation auch für große Gruppen zu etablieren. Durch die flexible Wahl des Verzweigungsgrads der entstehenden Kontrollbäume ist zudem eine beträchtliche Leistungsoptimierung des zuverlässigen Transportprotokolls sowie eine entscheidende Verringerung der Netzbelastung mit dem TRS-Dienst möglich.