This paper introduces the Complete Josephus Cube, a fault-tolerant class of the recently proposed Josephus Cube [12] and proposes a cost-effective, fault-tolerant routing strategy for the Complete Josephus Cube. For a Complete Josephus Cube of order r, the routing algorithm can tolerate up to (r + I) encountered component faults in its message path and generates routes that are both deadlock-free and livelock-free. The message is guaranteed to be optimally (respectively, sub-optimally) delivered within a maximum of r (respectively, 2r + 1) hops. The message overhead incurred is only a single (r + 2)-bit routing vector accompanying the message to be communicated.