| Presentation | 2016-12-21 Theoretical Model of Interconnection Networks Consisting of Hosts and Switches Ryota Yasudo, Michihiro Koibuchi, Hideharu Amano, Koji Nakano, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Designing interconnection networks with low average shortest path length (ASPL) is an important object for researchers on computer systems. To this end, theoretical study is becoming essential. This work thus presents a host-switch graph, a theoretical model of interconnection networks. Interconnection networks consist of hosts and switches, and hence this model distinguishes between them. Designers’ goal is to construct a host-switch graph with the lowest ASPL between hosts for a given number of hosts and ports per switch. We provide the lower bound of the ASPL and study both deterministic and heuristic approaches. As a deterministic approach, we introduce typical host-switch graphs and discuss their ASPLs. We show a host-switch graph based on a clique provides the lowest ASPL, if it is constructable. As a heuristic approach, we study a randomized algorithm for host-switch graph. This approach must fix the number of switches. Hence, we carry out numerical simulations for various numbers of switches. Our results indicate the optimal number of switches can be predicted by the Moore bound, the known lower bound of the ASPL of regular undirected graphs. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | interconnection networksgraph theoryaverage shortest path length |
| Paper # | ISEC2016-79,COMP2016-40 |
| Date of Issue | 2016-12-14 (ISEC, COMP) |
| Conference Information | |
| Committee | COMP / ISEC |
|---|---|
| Conference Date | 2016/12/21(2days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Hiroshima University |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | Hiroo Itoh(Univ. of Electro-Comm.) / Masahiro Mambo(Kanazawa Univ.) |
| Vice Chair | Yuushi Uno(Osaka Pref. Univ.) / Kazuto Ogawa(NHK) / Atsushi Fujioka(Kanagawa Univ.) |
| Secretary | Yuushi Uno(Seikei Univ.) / Kazuto Ogawa(Kobe Univ.) / Atsushi Fujioka(Toshiba) |
| Assistant | / Toshihiro Ohigashi(Tokai Univ.) / Yuuji Suga(IIJ) / Atsuo Inomata(Tokyo Denki Univ.) |
| Paper Information | |
| Registration To | Technical Committee on Theoretical Foundations of Computing / Technical Committee on Information Security |
|---|---|
| Language | ENG-JTITLE |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Theoretical Model of Interconnection Networks Consisting of Hosts and Switches |
| Sub Title (in English) | |
| Keyword(1) | interconnection networksgraph theoryaverage shortest path length |
| 1st Author's Name | Ryota Yasudo |
| 1st Author's Affiliation | Keio University(Keio Univ.) |
| 2nd Author's Name | Michihiro Koibuchi |
| 2nd Author's Affiliation | National Institute of Informatics(NII) |
| 3rd Author's Name | Hideharu Amano |
| 3rd Author's Affiliation | Keio University(Keio Univ.) |
| 4th Author's Name | Koji Nakano |
| 4th Author's Affiliation | Hiroshima University(Hiroshima Univ.) |
| Date | 2016-12-21 |
| Paper # | ISEC2016-79,COMP2016-40 |
| Volume (vol) | vol.116 |
| Number (no) | ISEC-380,COMP-381 |
| Page | pp.pp.51-58(ISEC), pp.51-58(COMP), |
| #Pages | 8 |
| Date of Issue | 2016-12-14 (ISEC, COMP) |