Pacifier: High-Throughput Reliable Multicast Without "Crying Babies" in Wireless Mesh Networks

 


Overview of Pacifier

High-throughput, reliable multicast routing has many important applications in WMNs, such as software updates and video/audio file downloads. There are two primary challenges to supporting high-throughput, reliable multicast in WMNs. The first is no different from unicast: wireless links are inherently lossy due to varying channel conditions and interference. The second, known as the "crying baby" problem, is unique to multicast: the multicast source may have varying throughput to different multicast receivers, and hence trying to satisfy the reliability requirement for poorly connected receivers can potentially result in performance degradation for the rest of the receivers.

Pacifier is a high-throughput, reliable multicast protocol that systematically addresses the above two challenges. Pacifier seamlessly integrates four building blocks, namely,

to support high-throughput, reliable multicast routing and at the same time solve the "crying baby" problem. First, Pacifier builds an efficient multicast tree traditionally used by multicast protocols and naturally leverages it for opportunistic overhearing. Second, Pacifier applies intra-flow, random linear network coding to overcome packet loss over lossy links which avoids hop-by-hop feedback and the coordination of multicast tree forwarders in packet forwarding. Third, Pacifier applies rate limiting at the source, reducing the congestion level in the network. Fourth, Pacifier solves the "crying baby" problem by having the source send batches of packets in a round-robin fashion. This functionality allows Pacifier to improve the throughput of well-connected nodes drastically and often times of poorly connected nodes.


Implementation

Network coding-based wireless protocols, such as Pacifier or MORE, are typically implemented as a shim between the IP and the MAC layer, i.e., at layer 2.5. For example, the authors of MORE offer an implementation of the protocol using the Click modular router. For ease of prototyping, debugging, deployment, and evaluation, we implemented Pacifier at the application layer, using broadcast sockets, on Mandrake Linux 10.1 (kernel 2.6.8-12). For a fair comparison, we also implemented MORE, a state-of-the-art network coding-based reliable multicast (and unicast) protocol, at the application layer.

Our application-layer implementation of the protocols allows for quick modification and evaluation of various operations that affect the performance of this new class of "exotic" network coding-based routing protocols, other than network coding itself, such as forwarding list selection, batching scheme, and rate control, and helps to understand their impact on the performance of these protocols.

Although such an implementation unavoidably results in some performance degradation, compared to an implementation closer to the MAC layer, from crossing the kernel-user boundary, we note that this degradation is expected to be similar for both protocols, since they use the same type of network coding, they have the same memory requirements at the routers, and the same header fields.


Download

To facilitate further research on network coding-based protocols, we make the source code of Pacifier and MORE implementation publicly available. 15 research groups from 5 different countries have downloaded the code since October 2009. You can obtain the source code at the download page.


Evaluation

Our experiments [2] on MAP show that Pacifier increases the average multicast throughput over MORE by 83-114%, while it solves the "crying baby" problem, by increasing the maximum throughput gain for well-connected receivers by up to 14x. Interestingly and importantly, Pacifier also improves the throughput of the "crying babies", i.e., the poorly-connected receivers, by up to 5.4x.


Papers


People

 

myspace profile view counter