A Nonbacktracking Matrix Decomposition Algorithm for Routing on Clos Networks

John D. Carpinelli; A. Yavuz Oruç

doi:10.1109/26.231969

A Nonbacktracking Matrix Decomposition Algorithm for Routing on Clos Networks

John D. Carpinelli, A. Yavuz Oruç

Electrical and Computer Engineering

Research output: Contribution to journal › Article › peer-review

12 Scopus citations

Abstract

A number of matrix decomposition schemes were reported for routing on Clos switching networks. These schemes occasionally fail to find the right decomposition, unless backtracking is used. This paper shows that a partition may occur during the decomposition process, and that this is the underlying reason these algorithms fail for some decompositions. It then presents a parallel algorithm which can recognize when a partition exists and set up the Clos network without backtracking.

Original language	English (US)
Pages (from-to)	1245-1251
Number of pages	7
Journal	IEEE Transactions on Communications
Volume	41
Issue number	8
DOIs	https://doi.org/10.1109/26.231969
State	Published - Aug 1993

All Science Journal Classification (ASJC) codes

Electrical and Electronic Engineering

Access to Document

10.1109/26.231969

Cite this

@article{5e81d948b9844627a37e70b91f9ab319,

title = "A Nonbacktracking Matrix Decomposition Algorithm for Routing on Clos Networks",

abstract = "A number of matrix decomposition schemes were reported for routing on Clos switching networks. These schemes occasionally fail to find the right decomposition, unless backtracking is used. This paper shows that a partition may occur during the decomposition process, and that this is the underlying reason these algorithms fail for some decompositions. It then presents a parallel algorithm which can recognize when a partition exists and set up the Clos network without backtracking.",

author = "Carpinelli, {John D.} and Oru{\c c}, {A. Yavuz}",

year = "1993",

month = aug,

doi = "10.1109/26.231969",

language = "English (US)",

volume = "41",

pages = "1245--1251",

journal = "IEEE Transactions on Communications",

issn = "0090-6778",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "8",

}

TY - JOUR

T1 - A Nonbacktracking Matrix Decomposition Algorithm for Routing on Clos Networks

AU - Carpinelli, John D.

AU - Oruç, A. Yavuz

PY - 1993/8

Y1 - 1993/8

N2 - A number of matrix decomposition schemes were reported for routing on Clos switching networks. These schemes occasionally fail to find the right decomposition, unless backtracking is used. This paper shows that a partition may occur during the decomposition process, and that this is the underlying reason these algorithms fail for some decompositions. It then presents a parallel algorithm which can recognize when a partition exists and set up the Clos network without backtracking.

AB - A number of matrix decomposition schemes were reported for routing on Clos switching networks. These schemes occasionally fail to find the right decomposition, unless backtracking is used. This paper shows that a partition may occur during the decomposition process, and that this is the underlying reason these algorithms fail for some decompositions. It then presents a parallel algorithm which can recognize when a partition exists and set up the Clos network without backtracking.

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

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

U2 - 10.1109/26.231969

DO - 10.1109/26.231969

M3 - Article

AN - SCOPUS:0027640744

SN - 0090-6778

VL - 41

SP - 1245

EP - 1251

JO - IEEE Transactions on Communications

JF - IEEE Transactions on Communications

IS - 8

ER -

A Nonbacktracking Matrix Decomposition Algorithm for Routing on Clos Networks

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this