@article{Královič_Rovan_Ružička_Štefankovič_2012, title={Efficient deadlock-free multidimensional interval routing in hypercube-like networks}, volume={21}, url={https://www.cai.sk/ojs/index.php/cai/article/view/498}, abstractNote={We present deadlock-free packet/wormhole routing algorithms ba\-sed on multidimensional interval schemes for certain hypercube related multiprocessor interconnection networks and give their analysis in terms of the compactness (i.e.~the maximum number of intervals per link) and the buffer-size (i.e.~the ma\-xi\-mum number of buffers per node/link). The issue of a simultaneous reduction of the compactness and the buffer-size is fundamental, worth to investigate and of practical importance, since the interval routing and wormhole routing have been industrially realized in INMOS Transputer C104 Router chips. <br />In this paper we give an evidence that for some well-known interconnection networks there are efficient deadlock-free multidimensional interval routing schemes (DFMIRS) despite of a provable non-existence of efficient deterministic shortest path interval routing schemes (IRS). For $d$-dimensional hypercubes (tori) we present a $d$-dimensional DFMIRS of compactness $1$ and size $2$ (of compactness $1$ and size $4$), while for shortest path IRS we can achieve the reduction to $2$ (to at most $5$) buffers per node with compactness $2^{d-1}$ (with compactness $O(n^{d-1})$). For $d$-dimensional generalized butterflies we give a $d$-dimensional DFMIRS with compactness $2$ and size $3$, while each shortest path IRS is of the compactness at least superpolynomial in $d$. For $d$-dimensional cube-connected cycles we show a $d$-dimensional DFMIRS with compactness and size polynomial in $d$, while each shortest path IRS needs compactness at least $2^{d/2}$. <br />We also present a nonconstant lower bound (in the form $\sqrt{d}$) on the size of deadlock-free packet routing (based on acyclic orientation covering) for a set of monotone routing paths on $d$-dimensional hypercubes.}, number={3}, journal={COMPUTING AND INFORMATICS}, author={Královič, Rastislav and Rovan, Branislav and Ružička, Peter and Štefankovič, Daniel}, year={2012}, month={Feb.}, pages={265–287} }