Flooding for Reliable Multicast in Multi-Hop Ad Hoc Networks

Christopher Ho, Katia Obraczka, Gene Tsudik and Kumar Viswanath,
Workshop on Discrete Algorithms and Methods for Mobile Computing & Communications (DialM '99),
Seattle, WA. August 1999.
Abstract

Ad Hoc Networks are gaining popularity as a result of advances in smaller, more versatile and powerful mobile computing devices. The distinguishing feature of these networks is the universal mobility of all hosts. This requires re-engineering of basic network services including reliable multicast communication.

This paper considers the special case of highly mobile fast-moving ad hoc networks and argues that, for such networks, traditional multicast approaches are not appropriate. Flooding is suggested as a possible alternative for reliable multicast and simulation results are used to illustrate its effects. The experimental results also demonstrate a rather interesting outcome that even flooding is insufficient for reliable multicast in ad hoc networks when mobility is very high. Some alternative, more persistent variations of flooding are sketched out.

In-Memory Directories: Eliminating the Cost of Directories in CC-NUMAs

Christopher Ho, Heidi Ziegler and Michel Dubois
Proceedings of the 10th ACM Symposium on Parallel Algorithms and Architecture (SPAA '98),
Puerto Vallarta, Mexico. June 1998.

Abstract

In cache-coherent non-uniform memory access (CC-NUMA) multiprocessors, the amount of memory consumed by the directories grows with the number of memory blocks and the number of processors. In this paper, we propose to eliminate the cost of directories by storing directory entries in the same memory used for the data that we keep coherent. A memory block stores either data when the block is uncached, or directory information when the block is cached. Only one extra bit per memory block is required to distinguish whether it contains data or directory information. We call this approach "in-memory directories". The trade-off is that the new protocol consumes more network bandwidth and has slightly higher latencies. We quantify this trade-off using a subset of programs in the SPLASH-2 benchmarks. The evaluations show that in-memory directories are competitive with dedicated full-mapped directories and are a viable alternative to SCI for scalable multiprocessor systems. We also propose variants to the basic in-memory protocol, which reduce its memory access overhead.

Back Home