{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,26]],"date-time":"2023-10-26T05:40:43Z","timestamp":1698298843190},"reference-count":8,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":4850,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1993,7]]},"abstract":"Abstract<\/jats:title>This paper proposes a new method, recursive expansion<\/jats:italic> (RE), for systematically constructing interconnection networks of arbitrary large size with high performance. On the basis of two small\u2010size networks, a frame and a unit, the RE method works in a manner of recursively replacing each node in the frame with an expanded network containing a set of copies of the unit and each edge in the frame with a set of interunit connections connecting a pair of the networks until a network of the desired size has been obtained. By RE, we can construct various kinds of large\u2010size and low\u2010cost interconnection networks. Two applications of the method, the \u210b\ufe01\u03a3<\/jats:sup>r<\/jats:sub> network based on the torus and the \u210b\ufe01\u03a3<\/jats:sup>r<\/jats:sub> network based on the hypercube, show that our method can produce networks with cost O((log3\/2<\/jats:sup> n<\/jats:italic>)\/(log3\/2<\/jats:sup> log n<\/jats:italic>)) (degree O(1)) and O<\/jats:italic>(log n<\/jats:italic> log log n<\/jats:italic>) (degree O(log log n<\/jats:italic>)). In addition to low cost, networks constructed by RE also possess other properties such as high constructability, good extendability, symmetric topology, and efficient message routing. This paper describes an algorithm, for automatically constructing arbitrary large size networks with high performance. For constructing a network of size n<\/jats:italic>r<\/jats:italic><\/jats:sub> through r<\/jats:italic> phases RE on the basis of a frame of degree d<\/jats:italic>f<\/jats:italic><\/jats:sub> and a unit of size n<\/jats:italic>u<\/jats:italic><\/jats:sub> and degree d<\/jats:italic>u<\/jats:italic><\/jats:sub>, the algorithm has a time complexity O((max{(d<\/jats:italic>f<\/jats:italic><\/jats:sub>\/n<\/jats:italic>u<\/jats:italic><\/jats:sub>), (d<\/jats:italic>u<\/jats:italic><\/jats:sub>\/r<\/jats:italic>)})rn<\/jats:italic>2<\/jats:sup>r<\/jats:italic><\/jats:sub>). Finally, a routing algorithm for networks constructed by RE is presented. The routing algorithm can realize point\u2010to\u2010point message routing without using a global routing table at each node and has a time complexity O((k<\/jats:italic>u<\/jats:italic><\/jats:sub> + k<\/jats:italic>f<\/jats:italic><\/jats:sub>)d<\/jats:italic>f<\/jats:italic><\/jats:sub>r<\/jats:italic>), where k<\/jats:italic>u<\/jats:italic><\/jats:sub> and k<\/jats:italic>f<\/jats:italic><\/jats:sub> are diameters of the frame and of the unit, d<\/jats:italic>f<\/jats:italic><\/jats:sub> is the degree of the frame, and r<\/jats:italic> is the number of phases of RE to construct the network. \u00a9 1993 by John Wiley & Sons, Inc.<\/jats:italic><\/jats:p>","DOI":"10.1002\/net.3230230421","type":"journal-article","created":{"date-parts":[[2007,5,12]],"date-time":"2007-05-12T15:18:00Z","timestamp":1178983080000},"page":"399-414","source":"Crossref","is-referenced-by-count":1,"title":["Construction of large\u2010size interconnection networks with high performance"],"prefix":"10.1002","volume":"23","author":[{"given":"Hong","family":"Shen","sequence":"first","affiliation":[]},{"given":"Ralph\u2010Johan","family":"Back","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","unstructured":"G. S.AlmasiandA.Gottlieb Highly Parallel Computing.Benjamin\/Cummings (1988)."},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/356654.356658"},{"key":"e_1_2_1_4_2","volume-title":"Selected Topics in Graph Theory","author":"Beineke L. W.","year":"1983"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(86)90008-0"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1109\/C-M.1981.220290"},{"key":"e_1_2_1_7_2","unstructured":"W. D.Hillis The Connection Machine Cambridge MA (1985)."},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1981.1675774"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1985.1676626"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230230421","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230230421","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,25]],"date-time":"2023-10-25T03:37:42Z","timestamp":1698205062000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230230421"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,7]]},"references-count":8,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1993,7]]}},"alternative-id":["10.1002\/net.3230230421"],"URL":"https:\/\/doi.org\/10.1002\/net.3230230421","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,7]]}}}