All-to-all communication in random regular directed graphs

Joohwan Kim, Arash Ghayoori, Rayadurgam Srikant

Research output: Contribution to journalReview article

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 languageEnglish (US)
Article number6971166
Pages (from-to)43-52
Number of pages10
JournalIEEE Transactions on Network Science and Engineering
Volume1
Issue number1
DOIs
StatePublished - Jan 1 2014

Fingerprint

Directed graphs
Peer to peer networks
Communication
Switches

ASJC Scopus subject areas

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

Cite this

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

In: IEEE Transactions on Network Science and Engineering, Vol. 1, No. 1, 6971166, 01.01.2014, p. 43-52.

Research output: Contribution to journalReview article

@article{899bfdbe31604e9aa8965c87c1454fba,
title = "All-to-all communication in random regular directed graphs",
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.",
author = "Joohwan Kim and Arash Ghayoori and Rayadurgam Srikant",
year = "2014",
month = "1",
day = "1",
doi = "10.1109/TNSE.2014.2376777",
language = "English (US)",
volume = "1",
pages = "43--52",
journal = "IEEE Transactions on Network Science and Engineering",
issn = "2327-4697",
publisher = "IEEE Computer Society",
number = "1",

}

TY - JOUR

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

AU - Kim, Joohwan

AU - Ghayoori, Arash

AU - Srikant, Rayadurgam

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 -