On the capacity of disjointly shared networks

J. C. Lagarias, A. M. Odlyzko, D. B. Zagier

Research output: Contribution to journalArticle

9 Citations (Scopus)

Abstract

Multi-access broadcast channels have the property that only one user can successfully transmit on the channel at a time. We consider a hypothetical channel called a disjointly shared channel in which more than one user pair can communicate simultaneously over physically disjoint parts of the channel. We consider the question of how much extra capacity such a channel has over that of a broadcast channel, as measured by the number of user pairs on the channel. The amount of extra capacity depends on the topology of the channel and the distribution of offered traffic. We analyze the problem for a particular disjointly shared channel having n users whose topology consists of k disjoint parallel cables. For an offered traffic pattern equally weighting each pair of users the capacity increases by at most a factor of three over that of k disjoint multi-access broadcast channels, i.e. on average at most 3k pairs of users will be communicating. For a specific offered traffic pattern which heavily weights connections between users close to each other the capacity is approximately αkn for a constant αk depending on the number of cables k, and it is shown that 1 4 ≤ αk < 1 2 with αk increading to 1 2 as k → ∞ The analysis for the second traffic pattern leads to a permutation enumeration problem which is solved using generating functions, continued fractions and Hermite polynomials.

Original languageEnglish (US)
Pages (from-to)275-285
Number of pages11
JournalComputer Networks and ISDN Systems
Volume10
Issue number5
DOIs
StatePublished - Jan 1 1985

Fingerprint

Cables
Topology
Polynomials

Keywords

  • Ethernet
  • Hermite polynomials
  • Multi-access broadcast channels
  • capacity continued fractions
  • disjointly shared channel

Cite this

On the capacity of disjointly shared networks. / Lagarias, J. C.; Odlyzko, A. M.; Zagier, D. B.

In: Computer Networks and ISDN Systems, Vol. 10, No. 5, 01.01.1985, p. 275-285.

Research output: Contribution to journalArticle

Lagarias, J. C. ; Odlyzko, A. M. ; Zagier, D. B. / On the capacity of disjointly shared networks. In: Computer Networks and ISDN Systems. 1985 ; Vol. 10, No. 5. pp. 275-285.
@article{44f5dfdb5d1f47ed84714c0ccbc46df4,
title = "On the capacity of disjointly shared networks",
abstract = "Multi-access broadcast channels have the property that only one user can successfully transmit on the channel at a time. We consider a hypothetical channel called a disjointly shared channel in which more than one user pair can communicate simultaneously over physically disjoint parts of the channel. We consider the question of how much extra capacity such a channel has over that of a broadcast channel, as measured by the number of user pairs on the channel. The amount of extra capacity depends on the topology of the channel and the distribution of offered traffic. We analyze the problem for a particular disjointly shared channel having n users whose topology consists of k disjoint parallel cables. For an offered traffic pattern equally weighting each pair of users the capacity increases by at most a factor of three over that of k disjoint multi-access broadcast channels, i.e. on average at most 3k pairs of users will be communicating. For a specific offered traffic pattern which heavily weights connections between users close to each other the capacity is approximately αkn for a constant αk depending on the number of cables k, and it is shown that 1 4 ≤ αk < 1 2 with αk increading to 1 2 as k → ∞ The analysis for the second traffic pattern leads to a permutation enumeration problem which is solved using generating functions, continued fractions and Hermite polynomials.",
keywords = "Ethernet, Hermite polynomials, Multi-access broadcast channels, capacity continued fractions, disjointly shared channel",
author = "Lagarias, {J. C.} and Odlyzko, {A. M.} and Zagier, {D. B.}",
year = "1985",
month = "1",
day = "1",
doi = "10.1016/0169-7552(85)90070-4",
language = "English (US)",
volume = "10",
pages = "275--285",
journal = "Computer Networks",
issn = "1389-1286",
publisher = "Elsevier",
number = "5",

}

TY - JOUR

T1 - On the capacity of disjointly shared networks

AU - Lagarias, J. C.

AU - Odlyzko, A. M.

AU - Zagier, D. B.

PY - 1985/1/1

Y1 - 1985/1/1

N2 - Multi-access broadcast channels have the property that only one user can successfully transmit on the channel at a time. We consider a hypothetical channel called a disjointly shared channel in which more than one user pair can communicate simultaneously over physically disjoint parts of the channel. We consider the question of how much extra capacity such a channel has over that of a broadcast channel, as measured by the number of user pairs on the channel. The amount of extra capacity depends on the topology of the channel and the distribution of offered traffic. We analyze the problem for a particular disjointly shared channel having n users whose topology consists of k disjoint parallel cables. For an offered traffic pattern equally weighting each pair of users the capacity increases by at most a factor of three over that of k disjoint multi-access broadcast channels, i.e. on average at most 3k pairs of users will be communicating. For a specific offered traffic pattern which heavily weights connections between users close to each other the capacity is approximately αkn for a constant αk depending on the number of cables k, and it is shown that 1 4 ≤ αk < 1 2 with αk increading to 1 2 as k → ∞ The analysis for the second traffic pattern leads to a permutation enumeration problem which is solved using generating functions, continued fractions and Hermite polynomials.

AB - Multi-access broadcast channels have the property that only one user can successfully transmit on the channel at a time. We consider a hypothetical channel called a disjointly shared channel in which more than one user pair can communicate simultaneously over physically disjoint parts of the channel. We consider the question of how much extra capacity such a channel has over that of a broadcast channel, as measured by the number of user pairs on the channel. The amount of extra capacity depends on the topology of the channel and the distribution of offered traffic. We analyze the problem for a particular disjointly shared channel having n users whose topology consists of k disjoint parallel cables. For an offered traffic pattern equally weighting each pair of users the capacity increases by at most a factor of three over that of k disjoint multi-access broadcast channels, i.e. on average at most 3k pairs of users will be communicating. For a specific offered traffic pattern which heavily weights connections between users close to each other the capacity is approximately αkn for a constant αk depending on the number of cables k, and it is shown that 1 4 ≤ αk < 1 2 with αk increading to 1 2 as k → ∞ The analysis for the second traffic pattern leads to a permutation enumeration problem which is solved using generating functions, continued fractions and Hermite polynomials.

KW - Ethernet

KW - Hermite polynomials

KW - Multi-access broadcast channels

KW - capacity continued fractions

KW - disjointly shared channel

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

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

U2 - 10.1016/0169-7552(85)90070-4

DO - 10.1016/0169-7552(85)90070-4

M3 - Article

VL - 10

SP - 275

EP - 285

JO - Computer Networks

JF - Computer Networks

SN - 1389-1286

IS - 5

ER -