The Research On The Diameter Of Double Loop Networks

Double loop networks have been widely studied as architecture for local area networks. A double loop digraph G ( N ; r , s ) has N vertices 0 ,1, 2 ,…, N-1 and 2N edges of two types: i�'i + r (mod N), i�'i + s (mod N), for some fixed steps 1≤r≠s < N. If gcd( N , r , s ) = 1, the double loop network G ( N ; r , s ) is strongly connected and exists a finite diameter. Let d ( N ; r , s )be the diameter of G ( N ; r , s ) and let us define d ( N ) = min{d ( N ; r , s ):1≤r≠s < N }; d1 ( N ) = min{d ( N ;1, s ):1 < s < N}. Now it is known that d1 ( n )≥d ( N )≥「3n」-2 =lb ( N). And here ?? X?? expresses an integer that is not smaller than X . Suppose that Z is a set of non-negative integers. For k∈Z, if d ( N ; r , s ) = d ( N ) = lb ( N )+ k, then G ( N ; r , s )is called a k -tight optimal double loop network. If d1 ( N ) > d ( N ) = lb ( N )+ k, then the integer N is called singular(k -tight) integer. Here are some of the main results in this paper:(1) Based on the works of Liu et al., a new algorithm to find h -tight( h≥0) optimal double loop networks is presented. For any N≤10⁸, we calculated the number of h (0≤h≤7)tight optimal double-loop networks and its first N with h (0≤h≤7)tight optimal. According to the results of our experiments, we have showed some errors of an efficient algorithm to find optimal double loop networks proposed by Aguilo and Fiol.(2) Based on the theory of L -shaped tile , Chinese remainder theorem and prime number theory , it is proved that infinite families of k -tight optimal double loop networks can be constructed when A + z ? 2 j≠0 , N(t)=3t+(2i-1)t+B;B=k₀²-nk₀+m,t=f²-if-nk₀+m,f=(2i-i²+4B)p¹·p²…P2^k2₀e+c,where i=1,3,e≥0,m,ne are integers.(3) A new approach is presented to construct infinite families of singulark -tight optimal double loop networks. As its applications, we give some infinite families of singular k -tight optimal double loop networks when and N (t )∈I i(t ) for any intergers...