All-to-all communication in random regular directed graphs

Joohwan Kim, Arash Ghayoori, R. Srikant

Research output: Contribution to journalReview articlepeer-review


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.

Original languageEnglish (US)
Article number6971166
Pages (from-to)43-52
Number of pages10
JournalIEEE Transactions on Network Science and Engineering
Issue number1
StatePublished - Jan 1 2014

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Computer Science Applications
  • Computer Networks and Communications


Dive into the research topics of 'All-to-all communication in random regular directed graphs'. Together they form a unique fingerprint.

Cite this