M.Sc Thesis

M.Sc StudentChayat Ronen
SubjectApplying Deterministic Procedures to Reliable Multicast
DepartmentDepartment of Electrical and Computer Engineering
Supervisor PROFESSOR EMERITUS Raphael Rom


IP multicast is becoming the emerging infrastructure for mass delivery of information, from streaming audio and video media to multi-player games, software distributions and shared whiteboards. There have been several proposals to expand the basic unreliable service so that it can provide reliable delivery of data, in terms of ordering and loss recovery. Some of these proposals do not scale well, mainly due to feedback implosion. This is caused by excessive rate of feedback messages arriving from receivers seeking to recover network losses. In many scenarios derived from the topology of the network, receivers experience correlated losses that cause their feedbacks to be synchronized and packed into lengthy bursts. Such patterns of feedback are either difficult or impossible to handle by the source, and moreover, they contribute to the formation of network congestions and buffer overflows on links leading to it.

While many existing reliable-multicasting protocols seek to desynchronize receivers' feedbacks by probabilistic methods, thus circumventing the implosion problem, we show that there are certain deterministic methods that guarantee implosion avoidance and provide exposure control, without incurring the overhead of excessive state and timer-based maintenance associated with probabilistic schemes. We provide a formal description of these deterministic methods, namely the Reactive Window and the Proactive Window, and prove their correctness. In order to demonstrate their associated performance advantages, we use both for building a simple reliable multicast protocol termed SDMP (Scalable Dissemination Multicast Protocol) and compare its performance with PGM (Pragmatic General Multicast),
a protocol that uses probabilistic methods of de-synchronization.