General shuffle-exchange networks and their tag-based routing algorithms

This paper considers the problem of designing efficient routing algorithms for the backward network of a bidirectional general shuffle-exchange network (BGSEN). A BGSEN consists of the forward and the backward network. The control tag used in the forward (backward) network is called the forward (backward) control tag. It has been shown that Padmanabhan's formula (Padmanabham, 1991) can be used in the forward network. As for the backward network, Chen et al. (Chen et al., 2003) proposed a tag-based routing algorithm, which is based on the idea of using the forward control tag generated by Padmanabhan's formula inversely. Recently, Chen and Lou (Chen and Lou, 2006) also proposed a tag-based routing algorithm for the backward network. It should be noted, however, that Padmanabhan's formula is actually an explicit formula for computing the forward control tag. Neither (Chen et al., 2003) nor (Chen and Lou, 2006) provides an explicit formula for computing the backward control tag. This paper attempts to propose such formula that builds specifically for the backward control tag and greatly simplifies the computation process of Chen and Lou's algorithm.