As technology scales, fault tolerance is becoming a key concern in on-chip communication. Consequently, this work examines fault tolerant communication algorithms for use in the NoC domain. Two different flooding algorithms and a random walk algorithm are investigated. We show that the flood-based fault tolerant algorithms have an exceedingly high communication overhead. We find that the redundant random walk algorithm offers significantly reduced overhead while maintaining useful levels of fault tolerance. We then compare the implementation costs of these algorithms, both in terms of area as well as in energy consumption, and show that the .ooding algorithms consume an order of magnitude more energy per message transmitted.