All-to-all communication in random regular directed graphs

We consider networks formed by the union of M random 1 -regular directed graphs. These graphs are also called permutation models in the literature. We first present a proof showing that the expansion factor of such graphs is greater than or equal to N a.a.s when M> 4\;\log\; N, where N is the number of nodes in the network. The reason for considering such random graph models is their applicability in the design of peer-to-peer networks and data center networks of switches. Assuming that each node in the network has upload and download capacities greater than 8\; \log\; N, we also show that the above result implies that all-to-all communication is possible in such a network, if the total incoming data rate and the total outgoing data rate at each node are both less than or equal to 1.