The Strong Distance Of Strong Oriented Graphs And The Fault-tolerant Adaptive Routing In Meshes

In 1736, Euler's work on the seven bridges problem of K(o丨¨)nigsberg [47] markedthe birth of graph theory. Nowadays, it is well known that graph theory is widelyapplied in computer science, communication science, chemistry, biology, physics andall other disciplines.The application of one-way street in transport system is an economic and effectivemethod to improve traffic congestion. It also enhances traffic safety and reducesthe traffic management. The graph theoretical model of one-way street problem wasproposed by Robbins [56], one-way street problem is actually the issue of orientationin graph. Chartrand et al. proposed the concept of strong distance [7]. Let G bea two-edge connected graph, D be a strong orientation of G. The strong distancesd(u,ν) between u andνis the minimum number of arcs of a strong sub-digraphof D containing u andν. The strong eccentricity se(u) of u is the strong distancebetweenνand a vertex farthest from u. The strong radius srad(D) (resp. strongdiameter sdiarn(D))is the minimum (resp. maximum) strong eccentricity amongall vertices of D. The lower (resp. upper) orientable strong radius srad(G) (resp.SRAD(G)) of a two-edge connected graph G is the minimum (resp. maximum)strong radius over all strong orientations of G. The lower (resp. upper) orientablestrong diameter sdiam(G) (resp. SDIAM(G)) of a two-edge connected graph Gis the minimum (resp. maximum) strong diameter over all strong orientations ofG. Call the problem discussing the above four values in strong oriented graphs thestrong distance problem.Due to the increasing demand for computing performance, multi-processors arebeing extensively used. The mesh structure is one of the most important interconnectionnetwork models. As a topology to interconnect multiprocessor computersystems, it has been proved to possess many attractive properties. Parallel computersusing mesh as their underlying architecture have been around for years. Routingis a process to send message from a source node to a destination node, passingsome intermediate nodes. Design algorithms routing the message to the destinationbypassing the faults is significant when there exist some faults in the network.This thesis is concerned with strong distance in strong oriented graphs and fault-tolerant adaptive routing in meshes. We determine the bounds on the upperand lower orientable strong radius and strong diameter of graphs satisfyingthe Ore condition. Let G₁, G₂ be any connected graph, we present the exactvalue of srad(G₁×G₂), consider the relationship between sdiam(G₁×G₂) andr(G₁×G₂), d (G₁×G₂). Moreover, we determine the values of the lower orientablestrong diameters of some special graphs. Furthermore, we give the exact value ofSDIAM(K_m×K_n), a lower bound for SDIAM(P_m×P_n), an upper and lowerbound for SRAD(K_m×K_n) and SRAD(P_m×P_n), respectively. For the study offault-tolerant adaptive routing in multi-processor computer systems which use themesh as topology, we propose the cracky faulty block model, the faults are containedin the blocks by this model. When the blocks are formed, every node can determineits location by the stable status-on the border of the block, inside the block, outsidethe blocks. We design new routing scheme for the nodes in the faulty block, whilea node outside the faulty blocks route the message by the basic greedy algorithm.Furthermore, we prove that the fault-tolerant adaptive routing algorithm providedwill overcome the livelock situation and send the message to its destination.There are five chapters in this thesis.In chapter one, we present the basic definitions and notations, the known resultsabout the problem discussed and our new progress.In chapter two, we consider the strong distance problem of graphs satisfying theOre condition in terms of the order n and the girth g, obtain the following results:g≤srad(G)≤5, g≤sdiam(G)≤9, [n/2]≤SRAD(G)≤n, n≤SDIAM(G)≤n+1.In chapter three, we study the lower orientable strong radius and strong diameterof the Cartesian product of graphs and prove that: srad(G₁×G₂) = 2r(G₁×G₂),sdiam(G₁×G₂)≤min{sdiam(G₁)+sdiam(G₂), 2(?)(G₁×G₂), 4r(G₁×G₂)}. Furthermore,we establish three sufficient conditions for sdiam(G₁×G₂) = 2d(G₁×G₂)holds and determine the values of the lower orientable strong diameters of somespecial graphs. Moreover, we give the exact value of SDIAM(K_m×K_n), a lowerbound for SDIAM(P_m×P_n), an upper and lower bound for SRAD(K_m×K_n) andSRAD(P_m×P_n), respectively. In chapter four, we present the fault-tolerant adaptive routing in two-dimensionalmesh. The basic greedy algorithm doesn't guarantee that the message can reach thedestination, it may be trapped in a part of the network (called livelock). In order toavoid the situation, we design algorithms to form some minimal and disjoint rectangularblocks (called faulty blocks) such that the faults are contained inside theblocks. At the same time, when the faulty blocks form, every node has a stablestatus by our algorithm and it can judge its location-outside the blocks, in theboundary of the block, inside the block, by the status. By our fault-tolerant adaptiverouting algorithm, the nodes in the faulty block have special routing scheme;if the message is sent to a node outside the faulty blocks then it is routed by thebasic greedy algorithm. Finally, we prove that the fault-tolerant adaptive routingalgorithm provided is livelock-free. Different with the most papers in this aspect,the node inside a faulty block can be the candidate routing nodes in our model. Themessage can be sent to its destination as long as the destination is connected in themesh. This is a noticeable overall improvement of fault-tolerabililty of the system.In chapter five, we extend the faulty block model in two-dimensional mesh tothe multi-dimensional meshes and give the corresponding fault-tolerant adaptiverouting. We also prove that the fault-tolerant adaptive routing provided is livelockfree.