The thesis "Routing algorithms in networks with the topology of udcirculant graphs" investigates topological properties of circulant udgraphs and their application to computer data exchange.ududCirculant graphs are undirected vertex transitive graphs with n vertices udand edges of length hi, (i=1, 2, ..., k). When selecting an appropriate udtopology for a computer network, circulant graphs represent an udintermediate choice between simple but unreliable ring topology and udreliable but expensive (and sometimes technologically unfeasible) fully udconnected topology. Due to their favorable properties--among which are udsymmetry, scalability, reliability, small diameter, and small average udnode distance,--circulant graphs are widely studied as suitable udtopologies for local area networks and parallel computer architectures. udThey have been efficiently used in ILLIAC IV, FDDI-token, SILK and SONET udrings, Intel Paragon, Cray T3D, MPP, and MICROS.ududRouting algorithms are used to solve data exchange problems in computer udnetworks. Data (i.e. a message) is split into several packages. The task udof a routing algorithm is to transfer the packages along the network udedges to their final destination and then to combine them into original udmessage. There are two types of routing algorithms. Static routing udalgorithms determine the path for each packet in the preprocessing phase ud(i.e. before the actual start of routing); dynamic routing algorithms udperform all the necccessary routing calculations on-the-fly. After the udpreprocessing phase the routing algorithm makes several successive udrouting steps. In each routing step the algorithm can move a packet from udits current node to one of the neighboring nodes. Routing algorithms can udbe used to solve various routing problems. A two-terminal routing is a udproblem where only one package has to be routed from its source to its udfinal destination. Routing algorithms for this problem aim to route a udpackage along one of its shortest paths. Much more complicated situation udoccurs when more than one package is present in the network. In this udcase, which is also known as the general routing problem, a routing udalgorithm tries to route all the packages to their final destination in udas few as possible routing steps.ududIn this thesis we first introduce the wide area of our work. We udextensively explain the meaning of the following terms: network, routing udmodel, routing problem, routing algorithm. We also present the criteria udfor measuring the quality of a given routing algorithm. In the following udthere are two main chapters. The first one is dedicated to the selected udtopology (i.e. circulant graphs) and the second one to the routing udalgorithms designed and tested for this topology.ududIn the chapter dedicated to circulant graphs we first summarize the udknown results and the most important topological properties. Then we udpresent a method for solving certain problems (such as calculating the uddiameter and calculating the shortest paths) by reduction to integer udlattice in which a point represents a walk in a graph. We introduce the udnotion of minimal projection and give the corresponding algorithm to udconstruct it. We present the integer lattice as a module, define the udnotion of packed basis, and present two algorithms for calculating it. udThen we introduce and prove several important features concerning udvectors of packed basis. We also introduce a new topology, the so called udsemi-directed circulant graphs, and present an O(log n) algorithm for udcalculating the shortest paths between nodes in these graphs. The proof udof correctness for this algorithm, which calculates the shortest paths udby using the minimal projection along the vectors of packed basis, is udbased on the properties of packed basis proved in earlier sections. We udalso present some k-generalizations of the algorithms presented for ud2-circulant graphs.ududIn the chapter on the routing in circulant graphs we first present two udrouting algorithms for the two-terminal routing problem (static and uddynamic version). Then we present a parameterized model used to describe udrouting algorithms and give five parameter-sets of five static routing udalgorithms for the general routing problem. We also describe a dynamic udalgorithm for the general routing problem and compare the efficiency of udthis algorithm with the best static one. At the end of the chapter we udpresent a generalization of a routing algorithm for general k-circulant udgraphs.ududIn the last chapter of the thesis we give some open questions and ideas udfor future work.ud
展开▼
