Patent ID: 7042878
Filing Date: 2006-05-09
Classification: H04L

Abstract:
1. A method for self-routing a plurality of packets through a 2 n ×2 n switch, the switch having 2 n external input ports and 2 n external output ports labeled with 2 n distinct binary output addresses in the form of b 1 b 2 . . . b n , and 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}, each of the packets destined for a rectangular set of output addresses represented by a quaternary sequence Q 1 , Q 2 , . . . , Q n , where each Q j is a quaternary symbol in any one of the three values: ‘0-bound’, ‘1-bound’, and ‘bicast’, wherein each of the switching cells is a sorting cell associated with the partial order “‘0-bound’ ‘bicast’ ‘1-bound’”, the method comprising: generating a routing tag Q routing each of the packets through the network by using Q