Researching And Designing Of The Parallel Routing Algorithm On Star Graph

Star graph network has good point edge symmetry, layered structure and fault-tolerant performance. The diameter and degrees of a star graph network are far smaller than hypercube which has the some node as the star graph. Thus, taking the star graph as an Internet network mode is paid close attention by researchers recently, and is considered the most likely to replace the hypercube structure which has been widely applied. It is significant for Internet network that data transmission from origin to destination effectively and correctly. By establishing some node-disjoint paths, not only can avoid information jams and improve information efficiency, but also can provide an alternative route when some nodes fault. Based on the topology structure characteristics of star graph network, a parallel paths search algorithm is designed and presented in this thesis.In the beginning, the background knowledge, current state of research and the topology structure characteristics of star graph network are presented. And then, the algorithm based on Hamiltonian circuit Latin square (HCLS) to search node-disjoint paths is designed. Whether the addresses of the origin node and the destination node have the same 1st dimension or not are discussed respectively.1. The addresses of the origin node and the destination node have the same 1st dimension. An algorithm for constructing the routing of a message on star graph is proposed. The k packets are transmitted from a origin node to a destination node simultaneously along paths on star network, where the ith packet traverses along the ith path(1≤i≤k). In order for all packets to arrive at the destination node quickly and securely, the ith path must be node-disjoint from all other paths. For construction of these paths, the HCLS is employed in this algorithm, which has O(n2) of the time complexity.2. The addresses of the origin node and the destination node have the different 1st dimension. Application HCLS for this situation to construct a routing algorithm is complex. In this case, some paths cannot arrival destination nodes directly when HCLS is used. So the routing function is recycled to arrival destination nodes. The algorithm to construct parallel paths in this case is presented, and the sum of paths and the length of each path are also given. The conclusion is proved and the effectiveness is verified through examples.