| Presentation | 1993/9/24 A Fault Tolerant Routing Algorithm for Arrangement Graphs Peter Yamakawa, Hiroyuki Ebara, Hideo Nakano, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | This paper presents a depth first search-based routing protocol for arrangement interconnection network in the presence of faulty links.(n,k)-Arrangement graph,a superset of Star graph,is a good candidate for parallel computers.This topology offers facilities for the designer in working with size,degree,and diameter.These parameters are so essential in practical situations.The protocol exploits fully the properties of this network,and attempts to route a message to the destination via optimal path(shortest path). Also,if optimal paths are blocked our algorithm looks for the available shorter path from the destination.In addition,we give the mathematical expression for the probability of routing messages traveling over optimal paths.The results show that our algorithm routes a message with high probability for any selection of the parameters n and k. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | fault tolerant system / routing algorithm / distributed algorithm / parallel computer / arrangement graph |
| Paper # | COMP93-49 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 1993/9/24(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | A Fault Tolerant Routing Algorithm for Arrangement Graphs |
| Sub Title (in English) | |
| Keyword(1) | fault tolerant system |
| Keyword(2) | routing algorithm |
| Keyword(3) | distributed algorithm |
| Keyword(4) | parallel computer |
| Keyword(5) | arrangement graph |
| 1st Author's Name | Peter Yamakawa |
| 1st Author's Affiliation | Faculty of Engineering,Osaka University() |
| 2nd Author's Name | Hiroyuki Ebara |
| 2nd Author's Affiliation | Faculty of Engineering,Osaka University |
| 3rd Author's Name | Hideo Nakano |
| 3rd Author's Affiliation | Faculty of Engineering,Osaka University |
| Date | 1993/9/24 |
| Paper # | COMP93-49 |
| Volume (vol) | vol.93 |
| Number (no) | 249 |
| Page | pp.pp.- |
| #Pages | 10 |
| Date of Issue | |