The Random regular graph (RRG) has recently been proposed as an interconnect topology for future large scale data centers and HPC clusters. An RRG is a special case of directed regular graph (DRG) where each link is unidirectional and all nodes have the same number of incoming and outgoing links. In this work, we establish bounds for DRGs on diameter, average $k$<alternatives> <inline-graphic xlink:href="faizian-ieq2-2741492.gif"/></alternatives>-shortest path length, and a load balancing property with $k$<alternatives> <inline-graphic xlink:href="faizian-ieq3-2741492.gif"/></alternatives>-shortest path routing, and use these bounds to evaluate RRGs. The results indicate that an RRG with $k$ <alternatives><inline-graphic xlink:href="faizian-ieq4-2741492.gif"/></alternatives> -shortest path routing is not ideal in terms of diameter and load balancing. We further consider the Generalized De Bruijn Graph (GDBG), a deterministic DRG, and prove that for most network configurations, a GDBG is near optimal in terms of diameter, average $k$<alternatives> <inline-graphic xlink:href="faizian-ieq5-2741492.gif"/></alternatives>-shortest path length, and load balancing with a $k$<alternatives> <inline-graphic xlink:href="faizian-ieq6-2741492.gif"/></alternatives>-shortest path routing scheme. Finally, we use modeling and simulation to exploit the strengths and weaknesses of RRGs for different traffic conditions by comparing RRGs with GDBGs.