Premium
Low‐congested interval routing schemes for hypercubelike networks
Author(s) -
Cicerone Serafino,
Di Stefano Gabriele,
Flammini Michele
Publication year - 2000
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/1097-0037(200010)36:3<191::aid-net6>3.0.co;2-k
Subject(s) - dilation (metric space) , interval (graph theory) , computer science , upper and lower bounds , interconnection , routing (electronic design automation) , constant (computer programming) , topology (electrical circuits) , computer network , mathematics , combinatorics , mathematical analysis , programming language
In this paper, we provide low‐congested interval routing schemes (IRS) for some common interconnection networks such as butterflies, wrapped butterflies, and cube‐connected cycles. In particular, by exploiting their hypercubelike structure, we show that 1‐IRS and 2‐IRS are already sufficient to get schemes with a congestion which is at most c times the optimal one, for low constant values of c . All such schemes have also a small dilation proportional to the diameter. Moreover, a new lower bound on the congestion achievable by schemes for butterfly networks is provided, which improves upon the best previously known one [25]. © 2000 John Wiley & Sons, Inc.