In the design of a computer network, one of the fundamental considerations is the reliability and availability of the communication paths between all pairs of centers in the network. These characteristics are strongly dependent on the topological layout of the communication links in addition to the reliability and availability of the individual computer systems and communication facilities. Based on graph theoretic models for computer and communication networks, many different reliability measures have been defined. Attempts have been made to characterize networks that are optimal with respect to these measures. In this paper, the most significant reliability criteria and their relevance to different applications will be discussed. Furthermore, we survey the status of current research on the different criteria. The difficulties and limitations on each reliability measure will be pointed out and what seem to be the most fruitful areas for further investigation will be indicated.