An efficient tag-based routing algorithm for the backward network of a bidirectional general shuffle-exchange network

摘要

This letter considers the problem of designing efficient routing algorithms for the backward network of a bidirectional general shuffle-exchange network (BNBGSEN for short); switch elements in the network are of size k/spl times/k. It has been shown in (Z. Chen, et al., 2003) that the algorithm in (K. Padmanabham, 1991) can be used to obtain (as many as k) backward control tags for a source j to get to a destination i in a BNBGSEN. In this letter, we show that a BNBGSEN has a wonderful property: for each destination i, there are two backward control tags associated with it such that every source j can get to i by using one of the two tags. We use this property to derive an efficient tag-based routing algorithm.