Low-congested interval routing schemes for hypercubelike networks

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.