Simulation Research On Double Loop Networks

Graph Theory is a favorite branch in discrete Mathematics and combinatory Mathematics.Since 1960's because of the practice requirements aroused form production management,military affairs,transportation and computer networks,and especial lots of discrete problems needing be resolved,on the other hand,being the advent of large mainframe computer that can calculate large scale complicate problems,Graph Theory and Application have made rapid progress.Graph parameters such as connectivity and diameter have been studied extensively due to their intrinsic importance in graph theory,combinatory and their relations to fault tolerance and transmission delay in communications networks.Double-loop networks(DLNs) are important form of graph,and important topological structure of computer networks and communication systems have been widely studied as architecture for local area networks and large scale parallel communication systems.Since 1970's,much effort have been made to study the diameter,optimality, routing path and fault tolerance of DLNs,and lots of contributions have been made.The process of seeking the diameter of a DLN is viewed as the traversal for all nodes in the DLN in this thesis,so the BFS(Breadth-First-Search) is proposed to obtain the diameter of a DLN,furthermore the simulation is applied to study DLNs. Main works in this thesis are summarized as follows.1.The diameter and optimality of DLNs.The diameter and optimality of DLNs are obtained by use of BFS(Breadth-First-Search).N-family refers to a family of DLNs that N is fixed but its steps 1≤r≠s≤N-1 and gcd(N,r,s)=1.There are maximum value,minimum value,and symmetry distribution in diameter in N-family.There widely existed tight optimal double loop networks and they symmetrically appear.The diameter of UDLN(undirected double loop networks) is approximately half of that of DLN(directed double loop networks).An equivalent topological structure-spiral ring-is formed by BFS.2.The distribution attribution of tight optimal DLN.The amount of tight optimal DLN in N-family is flat fluctuated with N,while the ratio of them is fluctuating decreased with N.3.The average diameter of DLN.The average diameter of DLN can also be calculated by BFS.The average diameter of a tight optimal DLN is not certainly the smallest in N-family,so a tight optimal DLN with the smallest average diameter in N-family is called a dual-optimal double-loop network.4.Simulation on L-shaped Tile of DLN.The diameter of DLN can be obtained by its equivalent L-shaped Tile.With the increasing of N and its steps,L-shaped Tile cannot be constructed by man hand.Computer simulation is applied in construction of L-shaped Tile,and the distribution of their shape and parameters are studied in this thesis.5.Equivalent binary tree of DLN.DLN is a kind of network topological structure. In order to acquire its diameter,DLN is usually transferred into other kind of topological structure.DLN is transformed into equivalent binary tree in this thesis. The diameter of DLN can be obtained by the equivalent binary tree.6.[+h]-Link Prior Routing Strategy for DLN.[+h]-Link Prior Routing Strategy for Double-Loop Network is proposed.The shortest[+h]-link prior path and the bamboo raft(a new kind of L-shaped Tile) for a double-loop network are obtained. There is inferring relationships among nodes in the bamboo raft.The diameter of a DLN can be derived from the shortest[+h]-link prior path.7.A simulation platform is constructed.Based on BFS,a simulation platform is constructed.The simulation platform is helpful for us to simulate the diameter, average diameter,optimality,spiral ring,binary tree,L-shaped Tile,and bamboo raft L-shaped Tile.