Patent ID: 7099314

Claim:
A method for self-routing a plurality of real data packets through a 2 n ×2 n switch, the switch having 2 n external output ports labeled with 2 n distinct binary output addresses in the form of b 1 b 2 . . . b n , and is composed of a plurality of switching cells interconnected into a k-stage bit-permuting network which is characterized by a guide γ(1), γ(2), . . . , γ(k) where γ is a mapping from the set {1, 2, . . . , k} to the set {1, 2, . . . , n}, wherein each of the switching cells is a sorting cell associated with the partial order “10 (‘0-bound’)<00 (‘idle’)<11 (‘1-bound’)”, each of the real data packets arriving at a distinct external input port determining an active input port and being destined for a binary destination address d 1 d 2 . . . d n , the method comprising: generating an idle packet as a stream of ‘0’ bits at each non-active external input port, generating a routing tag 1d γ(1) d γ(2) . . . d γ(k) ) for each of the real data packets based on the guide of the network and the destination address of the packet, generating a routing tag which is a string of k+1 ‘0’ bits for each of the idle packets, and routing the real data packets and the idle packets through the network by sorting the packets by the sorting cells of the network, wherein the sorting by each of the sorting cells is according to the associated partial order and is based upon the leading two bits, which are either ‘10’ or ‘11’ for the real data packet, or ‘00’ for the idle packet, of the routing tag of each of the two packets arrived at each of the cells, and wherein the second leading bit is removed from the routing tag or rotated to the end of the routing tag of each of the packets before the packet exits from a j-th stage cell such that the leading two bits of the routing tag of each of the packets at each ofthej-th stage cell, 1≦j≦k, are always ‘1d γ(j)’ or ‘ 00’.