Network traffic patterns

■ Random traffic

모든 source는 모든 destination으로 1/N traffic

load balance가 매우 좋음 (매우 안좋은 topology나 routing의 경우에도 random traffic에서는 좋게 보일 수 있음)

■ Permutation

각각의 source는 모든 traffic을 하나의 destination으로 보냄

   □ Bit permutation 

	Bitcomp	Bitrev	Bitrotation	Shuffle	Transpose
0000	1111(15)	0000(0)	0000(0)	0000(0)	0000(0)
0001	1110(14)	1000(8)	1000(8)	0010(2)	0100(4)
0010	1101(13)	0100(4)	0001(1)	0100(4)	1000(8)
0011	1100(12)	1100(12)	1001(9)	0110(6)	1100(12)
0100	1011(11)	0010(2)	0010(2)	1000(8)	0001(1)
0101	1010(10)	1010(10)	1010(10)	1010(10)	0101(5)
0110	1001(9)	0110(6)	0011(3)	1100(12)	1001(9)
0111	1000(8)	1110(14)	1011(11)	1110(14)	1101(13)
1000	0111(7)	0001(1)	0100(4)	0001(1)	0010(2)
1001	0110(6)	1001(9)	1100(12)	0011(3)	0110(6)
1010	0101(5)	0101(5)	0101(5)	0101(5)	1010(10)
1011	0100(4)	1101(13)	1101(13)	0111(7)	1110(14)
1100	0011(3)	0011(3)	0110(6)	1001(9)	0011(3)
1101	0010(2)	1011(11)	1110(14)	1011(11)	0111(7)
1110	0001(1)	0111(7)	0111(7)	1101(13)	1011(11)
1111	0000(0)	1111(15)	1111(15)	1111(15)	1111(15)

        ㅁ Bit complement : D_i = ~S_i

        ㅁ Bit reverse : D_i = S_b-i-1 (4x4 mesh에서 b=16)

           

[bitcomp]

[bitrev]

        ㅁ Bit rotation : D_i = S_i+1 mod b

        ㅁ Shuffle : D_i = S_i-1 mod b

        ㅁ Transpose : D_i = S_i+b/2 mod b

          

[bitrot]

[shuffle]

[transpose]

   □ Digit permutations

        ㅁ Tornado : D_x = S_x+(k/2-1)mod k (4x4 mesh에서 k=4)

             

[tornado]

        ㅁ Neighbor : D_x = S_x + 1 mod k

             

[neighbor]

출처: Principles and Practices of Interconnection Networks