Personal tools
You are here: Home Publications Optimal Routing in Binomial Graph Networks
Document Actions

Thara Angskun, George Boslica, and Jack Dongarra (2007)

Optimal Routing in Binomial Graph Networks

In: The International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT), Adelaide, Australia.

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 mode 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.

by Charles Koelbel last modified 2008-05-09 08:00
« September 2010 »
Su Mo Tu We Th Fr Sa
1234
567891011
12131415161718
19202122232425
2627282930
 

VGrADS Collaborators include:

Rice University UCSD UH UCSB UTK ISI UTK

Powered by Plone