【正文】 CirRouting Process ?Feature of the routing algorithm –Two types of transmission: Exchange and Circling –Preputation plexity (bitlevel) : O(n3)Sequential, O(n2)Parallel –Distributed routing –Only an XOR operation is needed in each step –Conflictfree –Every packet will reach its destination in at most n steps ?Proof of the Conflictfree feature –Modification of the Transformation matrices in the Algorithm Detourfinding can proceed in each step (keeping the transformation matrices nonsingular) –Wellformed loops are generated when need to circling –An LCpermutation is generated in each step so that the routing can proceed 53, Set up N Independent Paths for LC ? Circuit Switch/Wormhole Routing Mode ? Set up N independent paths simultaneously for an LCPermutation ? Routing Strategy – Find an appropriate order for the use of the n dimensions Algorithm Sequencing。 29 ELSE 30 Find b such that tb,a=1。 22 rk:=ek。 BEGIN FOR k:=n1 DOWNTO 0 DO IF dk≠sk THEN send D to IMG(k)(S) ELSE send D to IMG(detour[k])(S)。 021021dddDsssSnnnn????????100 101 110 101 101 100 110 010 111 111 000 011 001 111 010 001 001 011 000 101 101 100 100 100 110 110 110 010 111 000 011 111 001 010 001 011 000 000 011 010 Naive Routing 4, Conflicts in Routing Process ? Conflicts on nodes ? Conflicts on links ? Conflicts ? Buffer necessary ? Schedule process ? Longer time in a “step” 000 111 001 011 010 101 011 001 101 100 100 110 110 010 111 000 000 001 011 010 010 011 001 000 101 100 101 100 110 110 111 111 000 000 001 001 010 010 011 011 101 110 100 110 100 010 111 111 000 001 001 000 010 011 011 010 101 110 111 100 110 100 101 111 Dimension 2 Dimension 0 Dimension 1 N5, Conflictfree Routing ? TwoStage Routing – Rearrange the packets ? Detour Routing – Find circles ? Rearrangement for the Use of the Dimensions – Order the routing dimensions accordingly 51, TwoStage Routing for BPCPermutations ? BPCPermutations A BPC permutation of N numbers can be defined by an ntuple F=(f’n1, f’n2, …, f’0), where (f’n1, f’n2, …, f’0) is a permutation of (n1, n2, …, 0), and fi=|f’i| for 0≤ i≤ n1, such that ????????.0,039。 /* Modify R using . */ T:=R1。 13 rk:=ek。 33 END。 dimension. This is only used for modifying the transformation matrices, and for the proof of