Nowadays, faults and failures are increasing especially in complex systems such as Network-on-Chip (NoC) based Systems-on-a-Chip due to the increasing susceptibility and decreasing feature sizes. On the other hand, fault-tolerant routing algorithms have an evident effect on tolerating permanent faults and improving the reliability of a Network-on-Chip based system. This paper presents reliability and performance evaluation of two main kinds of fault-aware routing algorithms, deterministic and adaptive, used in Network-on-Chip architectures. The investigated methods have a multi-level structure for fault-tolerance and therefore, each level can be separately evaluated. To demonstrate the effectiveness of these methods, we propose an analytical approach for reliability assessment based on combinatorial reliability models to show the effect of fault-aware routing algorithms on overall NoC reliability. However, for performance evaluation, we conduct extensive simulations on different applications.