Optimal routing in binomial graph networks

Thara Angskun; George Bosilca; Brad Vander Zanden; Jack Dongarra

doi:10.1109/PDCAT.2007.4420191

Optimal routing in binomial graph networks

Thara Angskun, George Bosilca, Brad Vander Zanden, Jack Dongarra

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

4 Scopus citations

Abstract

A circulant graph with n nodes and jumps j₁, j₂, ..., j_m is a graph in which each node i, 0 ≤ i ≤ n-1, is adjacent to all the vertices i±j_k mod n, where 1 ≤ k ≤ m. A binomial graph network (BMG) is a circulant graph where jk is the power of 2 that is less than or equal to n. This paper presents an optimal (shortest path) two-terminal routing algorithm for BMG networks. This algorithm uses only the destination address to determine the next hop in order to stay on the shortest path. Unlike the original algorithms, it does not require extra space for routing tables or additional information in the packet. The experimental results show that the new optimal algorithm is significantly faster than the original optimal algorithm.

Original language	English
Title of host publication	18th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2007
Pages	363-370
Number of pages	8
DOIs	https://doi.org/10.1109/PDCAT.2007.4420191
State	Published - 2007
Externally published	Yes
Event	18th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2007 - Adelaide, SA, Australia Duration: Dec 3 2007 → Dec 6 2007

Publication series

Name	Parallel and Distributed Computing, Applications and Technologies, PDCAT Proceedings

Conference

Conference	18th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2007
Country/Territory	Australia
City	Adelaide, SA
Period	12/3/07 → 12/6/07

Access to Document

10.1109/PDCAT.2007.4420191

Cite this

Angskun, T., Bosilca, G., Zanden, B. V., & Dongarra, J. (2007). Optimal routing in binomial graph networks. In 18th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2007 (pp. 363-370). Article 4420191 (Parallel and Distributed Computing, Applications and Technologies, PDCAT Proceedings). https://doi.org/10.1109/PDCAT.2007.4420191

@inproceedings{171ded7559a548989d5b08ba3a86b436,

title = "Optimal routing in binomial graph networks",

abstract = "A circulant graph with n nodes and jumps j1, j2, ..., jm is a graph in which each node i, 0 ≤ i ≤ n-1, is adjacent to all the vertices i±jk mod n, where 1 ≤ k ≤ m. A binomial graph network (BMG) is a circulant graph where jk is the power of 2 that is less than or equal to n. This paper presents an optimal (shortest path) two-terminal routing algorithm for BMG networks. This algorithm uses only the destination address to determine the next hop in order to stay on the shortest path. Unlike the original algorithms, it does not require extra space for routing tables or additional information in the packet. The experimental results show that the new optimal algorithm is significantly faster than the original optimal algorithm.",

author = "Thara Angskun and George Bosilca and Zanden, {Brad Vander} and Jack Dongarra",

year = "2007",

doi = "10.1109/PDCAT.2007.4420191",

language = "English",

isbn = "0769530494",

series = "Parallel and Distributed Computing, Applications and Technologies, PDCAT Proceedings",

pages = "363--370",

booktitle = "18th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2007",

note = "18th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2007 ; Conference date: 03-12-2007 Through 06-12-2007",

}

Angskun, T, Bosilca, G, Zanden, BV & Dongarra, J 2007, Optimal routing in binomial graph networks. in 18th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2007., 4420191, Parallel and Distributed Computing, Applications and Technologies, PDCAT Proceedings, pp. 363-370, 18th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2007, Adelaide, SA, Australia, 12/3/07. https://doi.org/10.1109/PDCAT.2007.4420191

Optimal routing in binomial graph networks. / Angskun, Thara; Bosilca, George; Zanden, Brad Vander et al.
18th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2007. 2007. p. 363-370 4420191 (Parallel and Distributed Computing, Applications and Technologies, PDCAT Proceedings).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Optimal routing in binomial graph networks

AU - Angskun, Thara

AU - Bosilca, George

AU - Zanden, Brad Vander

AU - Dongarra, Jack

PY - 2007

Y1 - 2007

N2 - A circulant graph with n nodes and jumps j1, j2, ..., jm is a graph in which each node i, 0 ≤ i ≤ n-1, is adjacent to all the vertices i±jk mod n, where 1 ≤ k ≤ m. A binomial graph network (BMG) is a circulant graph where jk is the power of 2 that is less than or equal to n. This paper presents an optimal (shortest path) two-terminal routing algorithm for BMG networks. This algorithm uses only the destination address to determine the next hop in order to stay on the shortest path. Unlike the original algorithms, it does not require extra space for routing tables or additional information in the packet. The experimental results show that the new optimal algorithm is significantly faster than the original optimal algorithm.

AB - A circulant graph with n nodes and jumps j1, j2, ..., jm is a graph in which each node i, 0 ≤ i ≤ n-1, is adjacent to all the vertices i±jk mod n, where 1 ≤ k ≤ m. A binomial graph network (BMG) is a circulant graph where jk is the power of 2 that is less than or equal to n. This paper presents an optimal (shortest path) two-terminal routing algorithm for BMG networks. This algorithm uses only the destination address to determine the next hop in order to stay on the shortest path. Unlike the original algorithms, it does not require extra space for routing tables or additional information in the packet. The experimental results show that the new optimal algorithm is significantly faster than the original optimal algorithm.

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

U2 - 10.1109/PDCAT.2007.4420191

DO - 10.1109/PDCAT.2007.4420191

M3 - Conference contribution

AN - SCOPUS:48049124724

SN - 0769530494

SN - 9780769530499

T3 - Parallel and Distributed Computing, Applications and Technologies, PDCAT Proceedings

SP - 363

EP - 370

BT - 18th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2007

T2 - 18th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2007

Y2 - 3 December 2007 through 6 December 2007

ER -

Optimal routing in binomial graph networks

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this