### Abstract

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 language | English (US) |
---|---|

Article number | 6971166 |

Pages (from-to) | 43-52 |

Number of pages | 10 |

Journal | IEEE Transactions on Network Science and Engineering |

Volume | 1 |

Issue number | 1 |

DOIs | |

State | Published - Jan 1 2014 |

### Fingerprint

### ASJC Scopus subject areas

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

### Cite this

*IEEE Transactions on Network Science and Engineering*,

*1*(1), 43-52. [6971166]. https://doi.org/10.1109/TNSE.2014.2376777

**All-to-all communication in random regular directed graphs.** / Kim, Joohwan; Ghayoori, Arash; Srikant, R.

Research output: Contribution to journal › Review article

*IEEE Transactions on Network Science and Engineering*, vol. 1, no. 1, 6971166, pp. 43-52. https://doi.org/10.1109/TNSE.2014.2376777

}

TY - JOUR

T1 - All-to-all communication in random regular directed graphs

AU - Kim, Joohwan

AU - Ghayoori, Arash

AU - Srikant, R.

PY - 2014/1/1

Y1 - 2014/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84937159742&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84937159742&partnerID=8YFLogxK

U2 - 10.1109/TNSE.2014.2376777

DO - 10.1109/TNSE.2014.2376777

M3 - Review article

AN - SCOPUS:84937159742

VL - 1

SP - 43

EP - 52

JO - IEEE Transactions on Network Science and Engineering

JF - IEEE Transactions on Network Science and Engineering

SN - 2327-4697

IS - 1

M1 - 6971166

ER -