Wide-sense nonblocking for symmetric or asymmetric 3-stage Clos networks under various routing strategies

F. H. Chang, J. Y. Guo, F. K. Hwang, C. K. Lin

Research output: Contribution to journalArticle

8 Citations (Scopus)

Abstract

Beneš established the notion of wide-sense nonblocking by constructing an example on the symmetric 3-stage Clos network under packing which requires less hardware compared to strict nonblocking. This has remained the only example of a wide-sense non-blocking 3-stage Clos network which is not strictly nonblocking. In this paper, we study packing as well as several other routing strategies which have been studied in the literature and proved that no other example exists for the symmetric 3-stage Clos network. We then extend the study to asymmetric 3-stage Clos network for the first time. In particular, we extend Beneš example to asymmetric 3-stage Clos network and show that these are the only two possible examples for the strategies under study.

Original languageEnglish
Pages (from-to)375-386
Number of pages12
JournalTheoretical Computer Science
Volume314
Issue number3
DOIs
Publication statusPublished - 2004 Apr 10

Fingerprint

Routing
Packing
Hardware
Strictly
Strategy

Keywords

  • CD
  • CS
  • MI
  • P
  • STU
  • WSNB
  • Wide-sense nonblocking

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Wide-sense nonblocking for symmetric or asymmetric 3-stage Clos networks under various routing strategies. / Chang, F. H.; Guo, J. Y.; Hwang, F. K.; Lin, C. K.

In: Theoretical Computer Science, Vol. 314, No. 3, 10.04.2004, p. 375-386.

Research output: Contribution to journalArticle

@article{69183ef52c8f4b06ad9ae4558284e822,
title = "Wide-sense nonblocking for symmetric or asymmetric 3-stage Clos networks under various routing strategies",
abstract = "Beneš established the notion of wide-sense nonblocking by constructing an example on the symmetric 3-stage Clos network under packing which requires less hardware compared to strict nonblocking. This has remained the only example of a wide-sense non-blocking 3-stage Clos network which is not strictly nonblocking. In this paper, we study packing as well as several other routing strategies which have been studied in the literature and proved that no other example exists for the symmetric 3-stage Clos network. We then extend the study to asymmetric 3-stage Clos network for the first time. In particular, we extend Beneš example to asymmetric 3-stage Clos network and show that these are the only two possible examples for the strategies under study.",
keywords = "CD, CS, MI, P, STU, WSNB, Wide-sense nonblocking",
author = "Chang, {F. H.} and Guo, {J. Y.} and Hwang, {F. K.} and Lin, {C. K.}",
year = "2004",
month = "4",
day = "10",
doi = "10.1016/j.tcs.2003.12.021",
language = "English",
volume = "314",
pages = "375--386",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",
number = "3",

}

TY - JOUR

T1 - Wide-sense nonblocking for symmetric or asymmetric 3-stage Clos networks under various routing strategies

AU - Chang, F. H.

AU - Guo, J. Y.

AU - Hwang, F. K.

AU - Lin, C. K.

PY - 2004/4/10

Y1 - 2004/4/10

N2 - Beneš established the notion of wide-sense nonblocking by constructing an example on the symmetric 3-stage Clos network under packing which requires less hardware compared to strict nonblocking. This has remained the only example of a wide-sense non-blocking 3-stage Clos network which is not strictly nonblocking. In this paper, we study packing as well as several other routing strategies which have been studied in the literature and proved that no other example exists for the symmetric 3-stage Clos network. We then extend the study to asymmetric 3-stage Clos network for the first time. In particular, we extend Beneš example to asymmetric 3-stage Clos network and show that these are the only two possible examples for the strategies under study.

AB - Beneš established the notion of wide-sense nonblocking by constructing an example on the symmetric 3-stage Clos network under packing which requires less hardware compared to strict nonblocking. This has remained the only example of a wide-sense non-blocking 3-stage Clos network which is not strictly nonblocking. In this paper, we study packing as well as several other routing strategies which have been studied in the literature and proved that no other example exists for the symmetric 3-stage Clos network. We then extend the study to asymmetric 3-stage Clos network for the first time. In particular, we extend Beneš example to asymmetric 3-stage Clos network and show that these are the only two possible examples for the strategies under study.

KW - CD

KW - CS

KW - MI

KW - P

KW - STU

KW - WSNB

KW - Wide-sense nonblocking

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

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

U2 - 10.1016/j.tcs.2003.12.021

DO - 10.1016/j.tcs.2003.12.021

M3 - Article

AN - SCOPUS:1642586215

VL - 314

SP - 375

EP - 386

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

IS - 3

ER -