强定向图的强距离及网格的容错自适应路由
|
摘要
1736年，Euler解决哥尼斯堡七桥问题标志着图论的诞生。今天，图论在计算机科学、通讯科学、化学、生物学、物理学等学科的应用已经是众所周知的。
在交通系统中应用单行道不仅是改善城市交通堵塞状况的经济而有效的方法，而且提高了交通安全，减轻了交通管理工作．单行道问题的图论模型最初由Robbins提出，单行道问题可以归结为图的定向问题。Chartrand等人提出了强定向图中强距离的概念。设G是一个二边连通图，D是G的一个强定向。D中任两个顶点u，v间的强距离sd(u，v)为D中包含u，v的最小强有向子图的弧数。点u的强离心率se(u)定义为u与图中其他所有点的强距离的最大值。强定向图D的强半径srad(D)(强直径sdiam(D))定义为图中所有点的强离心率的最小值(最大值)。二边连通图G的最小强半径srad(G)(最大强半径SRAD(G))为G的所有强定向图的强半径的最小值(最大值)。相应地，G的最小强直径sdiam(G)(最大强直径SDIAM(G))为G的所有强定向图的强直径的最小值(最大值)。确定一个图G的srad(G)、SRAD(G)、sdiam(G)和SDIAM(G)这四个参数的问题是图论研究中有重要应用背景的前沿课题。
由于对计算机运算性能日益增长的需求，多处理器计算机正在被广泛使用。网格结构是多处理器计算机系统互连的拓扑结构，它已被证明拥有许多吸引人的特性。并行计算机使用网格作为基本架构已有多年。网络中的路由是指将消息从源节点(处理器)经过一些中间节点最终传递到目标节点的过程。当网络中存在故障时，设计路由算法使消息绕过故障点最终到达目标点具有客观重要意义。
本文研究强定向图的强距离及网格的容错自适应路由。对满足Ore条件的图，给出了最小强半(直)径、最大强半(直)径的上、下界；对笛卡尔乘积图G_1×G_2，确定了G_1×G_2的最小强半(直)径与G_1×G_2的半(直)径以及G_1和G_2的最小强直径之间的关系，并进而确定了一些特殊笛卡尔乘积图的最小强直径的值，确定了SDIAM(K_m×K_n)的值，SDIAM(P_m×P_n)的下界，SRAD(K_m×K_n)和SRAD(P_m×P_n)相应的上、下界。对于以网格作为并行计算机拓扑结构的多处理器计算机系统的容错自适应路由的研究，本文提出了裂痕故障块模型，在此模型下，所有的故障都包含在块的内部。当块形成时，可以由每个节点的状态判断该点所处的位置—在块的边界、块的内部或块的外部。对块的内部点及边界点设计了新的特殊路由，对块外部的点仍采用一般路由方案，并证明所给的路由方案一定能克服活锁状态将消息送到目标节点。
全文共分为五章。
在第一章，我们首先给出本文的基本概念和符号，综述了本文研究领域的已有结果和本文的主要结论。
在第二章，我们研究Ore图G的最小强半(直)径srad(G)(sdiam(G))、最大强半(直)径SRAD(G)(SDIAM(G))的上、下界，得到以下结论：g≤srad(G)≤5，g≤sdiam(G)≤9，[n／2]≤SRAD(G)≤n，n≤SDIAM(G)≤n+1，其中n，g分别为G的顶点数和围长。
在第三章，研究了笛卡尔乘积图G_1×G_2的最小强半(直)径，证明了如下结果：srad(G_1×G_2)=2r(G_1×G_2)，sdiam(G_1×G_2)≤min{sdiam(G_1)+sdiam(G_2)，2d(G_1×G_2)，4r(G_1×G_2))；给出sdiam(G_1×G_2)=2d(G_1×G_2)成立的三个充分条件，并由所给出的充分条件确定了一些特殊笛卡尔乘积图的最小强直径的值；确定了SDIAM(K_m×K_n)的确切值，SDIAM(P_m×P_n)的下界，SRAD(K_m×K_n)和SRAD(P_m×P_n)的上、下界。
在第四章，我们给出了二维网格的容错自适应路由。当网格中存在故障时，原有的贪婪路由方案不一定能将信息送到目标点，可能陷入活锁状态(信息在网络的某子网络循环，到不了目标点)。为此，我们设计了算法，用以构造网络中的不交的极小故障块，使得块的边界和块外部没有故障，同时，当块形成时每个节点有相应的稳定状态，可以根据点的稳定状态判断它的位置一位于块的外部、块的边界或块的内部。在我们的容错路由方案里，处于块边界及内部的点都有特殊的路由，并证明了给出的路由方案一定能克服潜在的活锁状态，将信息送到目标点。与这方面的现有算法最大的区别在于，在我们的方案里，故障块内部的点也可以成为目标点或源点。这是网络容错性方面的一个显著的提高。
在第五章中，我们将二维网格中的故障块模型推广到多维网格中，给出相应的容错自适应路由，并证明了所给出的自适应路由不会产生活锁状态。
另外，在每一章中，我们都给出了相关的发展前景和展望。
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_1, G_2 be any connected graph, we present the exactvalue of srad(G_1×G_2), consider the relationship between sdiam(G_1×G_2) andr(G_1×G_2), d (G_1×G_2). 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_1×G_2) = 2r(G_1×G_2),sdiam(G_1×G_2)≤min{sdiam(G_1)+sdiam(G_2), 2(?)(G_1×G_2), 4r(G_1×G_2)}. Furthermore,we establish three sufficient conditions for sdiam(G_1×G_2) = 2d(G_1×G_2)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.
在交通系统中应用单行道不仅是改善城市交通堵塞状况的经济而有效的方法，而且提高了交通安全，减轻了交通管理工作．单行道问题的图论模型最初由Robbins提出，单行道问题可以归结为图的定向问题。Chartrand等人提出了强定向图中强距离的概念。设G是一个二边连通图，D是G的一个强定向。D中任两个顶点u，v间的强距离sd(u，v)为D中包含u，v的最小强有向子图的弧数。点u的强离心率se(u)定义为u与图中其他所有点的强距离的最大值。强定向图D的强半径srad(D)(强直径sdiam(D))定义为图中所有点的强离心率的最小值(最大值)。二边连通图G的最小强半径srad(G)(最大强半径SRAD(G))为G的所有强定向图的强半径的最小值(最大值)。相应地，G的最小强直径sdiam(G)(最大强直径SDIAM(G))为G的所有强定向图的强直径的最小值(最大值)。确定一个图G的srad(G)、SRAD(G)、sdiam(G)和SDIAM(G)这四个参数的问题是图论研究中有重要应用背景的前沿课题。
由于对计算机运算性能日益增长的需求，多处理器计算机正在被广泛使用。网格结构是多处理器计算机系统互连的拓扑结构，它已被证明拥有许多吸引人的特性。并行计算机使用网格作为基本架构已有多年。网络中的路由是指将消息从源节点(处理器)经过一些中间节点最终传递到目标节点的过程。当网络中存在故障时，设计路由算法使消息绕过故障点最终到达目标点具有客观重要意义。
本文研究强定向图的强距离及网格的容错自适应路由。对满足Ore条件的图，给出了最小强半(直)径、最大强半(直)径的上、下界；对笛卡尔乘积图G_1×G_2，确定了G_1×G_2的最小强半(直)径与G_1×G_2的半(直)径以及G_1和G_2的最小强直径之间的关系，并进而确定了一些特殊笛卡尔乘积图的最小强直径的值，确定了SDIAM(K_m×K_n)的值，SDIAM(P_m×P_n)的下界，SRAD(K_m×K_n)和SRAD(P_m×P_n)相应的上、下界。对于以网格作为并行计算机拓扑结构的多处理器计算机系统的容错自适应路由的研究，本文提出了裂痕故障块模型，在此模型下，所有的故障都包含在块的内部。当块形成时，可以由每个节点的状态判断该点所处的位置—在块的边界、块的内部或块的外部。对块的内部点及边界点设计了新的特殊路由，对块外部的点仍采用一般路由方案，并证明所给的路由方案一定能克服活锁状态将消息送到目标节点。
全文共分为五章。
在第一章，我们首先给出本文的基本概念和符号，综述了本文研究领域的已有结果和本文的主要结论。
在第二章，我们研究Ore图G的最小强半(直)径srad(G)(sdiam(G))、最大强半(直)径SRAD(G)(SDIAM(G))的上、下界，得到以下结论：g≤srad(G)≤5，g≤sdiam(G)≤9，[n／2]≤SRAD(G)≤n，n≤SDIAM(G)≤n+1，其中n，g分别为G的顶点数和围长。
在第三章，研究了笛卡尔乘积图G_1×G_2的最小强半(直)径，证明了如下结果：srad(G_1×G_2)=2r(G_1×G_2)，sdiam(G_1×G_2)≤min{sdiam(G_1)+sdiam(G_2)，2d(G_1×G_2)，4r(G_1×G_2))；给出sdiam(G_1×G_2)=2d(G_1×G_2)成立的三个充分条件，并由所给出的充分条件确定了一些特殊笛卡尔乘积图的最小强直径的值；确定了SDIAM(K_m×K_n)的确切值，SDIAM(P_m×P_n)的下界，SRAD(K_m×K_n)和SRAD(P_m×P_n)的上、下界。
在第四章，我们给出了二维网格的容错自适应路由。当网格中存在故障时，原有的贪婪路由方案不一定能将信息送到目标点，可能陷入活锁状态(信息在网络的某子网络循环，到不了目标点)。为此，我们设计了算法，用以构造网络中的不交的极小故障块，使得块的边界和块外部没有故障，同时，当块形成时每个节点有相应的稳定状态，可以根据点的稳定状态判断它的位置一位于块的外部、块的边界或块的内部。在我们的容错路由方案里，处于块边界及内部的点都有特殊的路由，并证明了给出的路由方案一定能克服潜在的活锁状态，将信息送到目标点。与这方面的现有算法最大的区别在于，在我们的方案里，故障块内部的点也可以成为目标点或源点。这是网络容错性方面的一个显著的提高。
在第五章中，我们将二维网格中的故障块模型推广到多维网格中，给出相应的容错自适应路由，并证明了所给出的自适应路由不会产生活锁状态。
另外，在每一章中，我们都给出了相关的发展前景和展望。
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_1, G_2 be any connected graph, we present the exactvalue of srad(G_1×G_2), consider the relationship between sdiam(G_1×G_2) andr(G_1×G_2), d (G_1×G_2). 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_1×G_2) = 2r(G_1×G_2),sdiam(G_1×G_2)≤min{sdiam(G_1)+sdiam(G_2), 2(?)(G_1×G_2), 4r(G_1×G_2)}. Furthermore,we establish three sufficient conditions for sdiam(G_1×G_2) = 2d(G_1×G_2)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.
引文
[1] J. Al-Sadi, K. Day, and M. Ould-Khaoua, "Probability Vectors: A New Fault-Tolerant Routing Algorithm for k-ary n-cubes", Proc. 17th ACM Symp. Applied Computing (SAC'02), 2002, pp. 830-834.
[2] J. Bang-Jensen, G. Gutin, Digraphs: Theory, Algorithms and Applications, Springer-Verlag London Berlin Heidellberg, 2001.
[3] F. Boesch, R. Tindell, Robbins's theorem for mixed multigraphs, Amer. Math. Monthly, 1980, Vol. 87(9): pp. 716-719.
[4] J.A. Bondy, U.S.R. Murty, Graph Theory with Applications, The Macmillan Press LTD., 1976.
[5] R.V. Boppana, S. Chalasani, Fault-tolerant wormhole routing algorithms for mesh networks, IEEE Trans. Computers, July 1995, Vol. 44(7): pp. 848-864.
[6] Y.M. Boura, C.R. Das, Fault-tolerant routing in mesh networks, Proc. of 1995 Int'l Conf. on Parallel Processing, 1995, pp. 106-109.
[7] G. Chartrand, D. Erwin, M. Raines, P. Zhang, Strong distance in strong digraphs, J. Combin. Math. Combin. Comput., 1999, Vol. 31: pp. 33-44.
[8] G. Chartrand, D. Erwin, M. Raines, P. Zhang, On strong distance in strong oriented graphs, Congr. Numer., 1999, Vol. 138: pp. 49-63.
[9] G. Chartrand, S. Tian, Distance in digraphs, Computers Math. Applic., 1997, Vol. 34(11): pp. 15-23.
[10] Meirun Chen, Xiaofeng Guo, Hao Li, Lower and upper orientable strong diameters of graphs satisfying the Ore condition, Applied Mathematics Letters (2009), Vol 22(7), 994-997.
[11] Meirun Chen, Xiaofeng Guo, Lower and upper orientable strong radius and diameter of the cartesian product of complete graphs, to appear in Ars Combinatoria.
[12] M.S. Chen, K.G. Shin, Adaptive fault-tolerant routing in hypercube multicomputers, IEEE Trans. on Computers, 1990, Vol 39(12), pp. 1406-1415.
[13] A.A. Chien, J.H. Kim, Plannar-adaptive routing: Low-cost adaptive networks for multi-processors, Proceedings of the 19th International Symposium on Computer Architecture, 1992, pp. 268-277.
[14] G.M. Chiu and S.P. Wu, A fault-tolerant routing strategy in hypercube multicomputers, IEEE Trans. Compters, 1996, Vol. 45(2): pp. 143-155.
[15] W.-S. Chiue, B.-S. Shieh, On connectivity of the Cartesian product of two graphs, Appl. Math. Comput., 1999, Vol. 102: pp. 129-137.
[16] W. Chou, A.W. Bragg, A.A. Nilsson, The need for adaptive routing in the chaotic and unbalanced traffic environment, IEEE Trans. Comm., Apr. 1981, pp. 481-490.
[17] V. Chv(?)tal, C. Thomassen, Distances in orientations of graphs, Journal of Combinatorial Theory, Series B, 1978, Vol. 24: pp. 61-75.
[18] Intel Corp., A Touchstone DELTA System Description, 1991.
[19] W.J. Dally, "The J-Machine: System support for Actors", Actors Knowledge-Based Concurrent Computing, Hewitt and Agha, eds., MIT Press, 1989.
[20] P. Dankelmann, H. Swart, D. Day, On strong distance in oriented graphs, Discrete Math., 2003, Vol. 266: pp. 195-201.
[21] K. Day, A.-E. Al-Ayyoub, The cross product of interconnection networks, IEEE Trans. Parallel Distributed Systems, 1997, Vol. 8(2): pp. 109-118.
[22] P.T. Gaughan, B.V. Dao, S. Yalamanchili, D.E. Schimmet, Distributed, deadlock-free routing in faulty, pipelined, direct interconnection networks, IEEE Trans. Computers, 1996, Vol. 45(6): pp. 651-665.
[23] C. Glass, L. Ni, Maximally fully adaptive routing in 2D meshes, Proc. 1992 Int'l Conf. Parallel Processing, Aug. 1992, pp. 101-104.
[24] G.J. Glass, L.M. Ni, "Fault-tolerant wormhole routing in meshes without virtual channels", IEEE Trans. Parallel and Distributed Systems, 1996, Vol. 7(6): pp. 620- 636.
[25] G. Gutin, Minimizing and maximizing the diameter in orientations of graphs, Graphs and Combinatorics, 1994, Vol. 10: pp. 225-230.
[26] Libeskind-Hadas, E. Brandt, Origin-based fault-tolerant routing in the mesh, Proc. of the 1st Int'l Symp. on High Performance Computer Architecture, 1995, pp. 102-111.
[27] Yi Huang, Meirun Chen, Lower and upper orientable strong radius and diameter of the Cartesian product of complete paths, Journal of Xinjiang University (National Science Edition), (2009), Vol 26(1), 33-37..
[28] J.S. Juan, C. Huang, On the strong distance problems of pyramid networks, Applied Mathmatics and Computation, 2008, Vol. 195: pp. 154-161.
[29] J.S. Juan, C. Huang, I. Sun, The strong distance problem on the Cartesian product of graphs, Information Processing Letters, 2008, Vol. 107: pp. 45-51.
[30] C. Huang, J.S. Juan, The strong distance problems of toroidal and semitoroidal mesh graphs, in: Proceedings of the 22nd Workshop on Combinatorial Mathematics and Computational Theory, 2005, pp. 192-196.
[31] J.S. Juan, C. Huang, The strong distance problem, Proc. Int. Conf. on Parallel and Distributed Processing Techniques and Applications, PDPTA'04, CSREA 2004, Vol, Ⅱ, pp. 699-705.
[32] K.M. Koh, E.G. Tay, Optimal Orientations of Products of Paths and Cycles, Discrete Applied Mathematics, 1997, Vol. 78: pp. 163-174.
[33] K.M. Koh, E.G. Tay, On optimal orientations of Cartesian products of graphs (Ⅰ), Discrete Mathematics, 1998, Vol. 190: pp. 115-136.
[34] K.M. Koh, E.G. Tay, The diameter of an orientation of a complete multipartite graph, Discrete Mathematics, 1996, Vol. 149: pp. 131-139.
[35] K.M. Koh, E.G. Tay, The minimum diameter of orientations of complete multipartite graphs, Graphs Combin., 1996, Vol. 12: pp. 333-339.
[36] K.M. Koh, E.G. Tay, On optimal orientations of Cartesian products of even cycles and paths, Networks, 1997, Vol. 30: pp. 1-7.
[37] K.M. Koh, E.G. Tay, On optimal orientations of Cartesian products of even cycles, Networks, 1998, Vol. 32: pp. 299-306.
[38] K.M. Koh, E.G. Tay, On optimal orientations of Cartesian products with a bipartite graph, Discrete Applied Mathematics, 1999, Vol. 98: pp. 103-120.
[39] K.M. Koh, E.G. Tay, On optimal orientations of Cartesian products of graphs (Ⅱ): Complete graphs and even cycles, Discrete Mathematics, 2000, Vol. 211: pp. 75-102.
[40] K.M. Koh, E.G. Tay, On optimal orientations of G vertex-multiplications, Discrete Mathematics, 2000, Vol. 219: pp. 153-171.
[41] K.M. Koh, E.G. Tay, On optimal orientations of Cartesian products of trees, Graphs Combin., 2001, Vol. 17: pp. 79-97.
[42] K.M. Koh, E.G. Tay, On a conjecture concerning optimal orientations of the Cartesian product of a triangle and an odd cycle, Discrete Mathematics, 2001, Vol. 232: pp. 153- 161.
[43] K.M. Koh, E.G. Tay, Optimal orientations of graphs and digraphs: A survey, Graphs and Combinatorics, 2002, Vol. 18: pp. 745-756.
[44] Y. Lai, F. Chiang, C. Lin, T. Yu, Strong distance of complete bipartite graphs, The 19th Workshop on Combinatorial Mathematics and Computation Theory, 2002, pp. 12-16.
[45] Y. Lai, J. Hsiao, F. Chiang, Orientable strong radius and diameter of hypercube, The 20th Workshop on Combinatorial Mathematics and Computation Theory, 2003, pp. 143-148.
[46] T.C. Lee, J.P. Hayes, A fault-tolerant communication scheme for hypercube computers, IEEE Trans. Computers, 1992, Vol. 41(10): pp. 1242-1256.
[47] Euler Leonhard, Solutio problemutis ad geometriam situs pertinantis, Academinae Petropolitanae, 8, pp. 128-140, 1736.
[48] A.C. Liang, S. Bhattacharya, W.T. Tsai, Fault-tolerant multicasting on hypercubes, J. Parallel and Distributed computing, 1994, Vol. 23(3): pp. 418-428.
[49] S.L. Lillevik, Thc touchstone 30 gigaflop DELTA prototype, Proc. Sixth Distributed Memory Computing Conf., 1996, pp. 671-677.
[50] D.H. Linder, J.C. Harden, An adaptive and fault tolerant wormhole routing strategy for k-ary n-cubes, IEEE Trans. Computers, 1991, Vol. 40(1) pp. 2-12.
[51] M.N. Lionel and K.M. Philip, A survey of wormhole routing techniques in direct networks, Computer, 1993, Vol. 26, pp. 62-76.
[52] Huifang Miao, Xiaofeng Guo, Lower and upper orientalbe strong radius and strong diameter of complete k-partite graphs, Discrete Applied Mathematics, 2006, Vol, 154 (11): pp. 1606-1614.
[53] Huifang Miao, Xiaofeng Guo, Strong distances in strong oriented complete k-partite graphs, to appear in Ars Combinatoria.
[54] Huifang Miao, Xiaofeng Guo, Optimal strong (k, d)-orientation of Complete k-partite graphs, Discrete Applied Mathematics, 2009, Vol, 157(8): pp. 1729-1736.
[55] J. Miguel-Alonso, J.A. Gregorio, V. Puente, F. Vallejo, and R. Beivide, "Load Unbalance in k-ary n-cube Networks", Proc. 10th Int'l Euro-Par Conf., Sept. 2004.
[56] H.E. Robbins, A theorem on graphs, with an application to a problem of tratfic control, Amer. Math. Monthly, 1939, Vol, 46): pp. 281-283.
[57] C.L. Seitz, W.C. Athas, C.M. Flaig, A.J. Martin, J. Seizovic, W.K. Su, The architecture and programming of the ametek series 2010 multicomputer, Proceedings of the Third Conference on Hypercube Concurrent Computers and Applications, 1988, pp. 33-36.
[58] C.C. Su, K.G. Shin, Adaptive fault-tolerant deadlock-free routing in meshes and hypercubes, IEEE Trans. Computers,IEEE Trans. Comput., 1996, Vol. 45(6), pp. 666- 683.
[59] Y.J. Sub, B.V. Dao, J. Duato, S. Yalamanchili, Software based fault-tolerant oblivious routing in pipelined networks, Proc. 1995 Int'l Conf. Parallel Processing, 1995, pp. 101-105.
[60] D. Wang, A rectilinear-monotone polygonal faulty block model for fault-tolerant minimal routing in mesh, IEEE Trans. Computers, March 2003, Vol. 52(3): pp. 310-320.
[61] J. Wu, "Reliable unicasting in faulty hypercubes using safety levels", IEEE Trans. Comput., 1997, vol. 46(2): pp. 241-247.
[62] J. Wu, Fault-tolerant adaptive and minimal routing in mesh-connected multicomputers using extended safety levels, IEEE Trans. Parallel and Distributed Systems, 2000, Vol. 11(2): pp. 149-159.
[63] D. Xiang, J. Sun, J. Wu, K. Thulasiraman, Fault-tolerant routing in planarly constructed fault blocks, Proc. of 1995 Int'l Conf. on Parallel Processing, 2005, pp. 577-584.
[2] J. Bang-Jensen, G. Gutin, Digraphs: Theory, Algorithms and Applications, Springer-Verlag London Berlin Heidellberg, 2001.
[3] F. Boesch, R. Tindell, Robbins's theorem for mixed multigraphs, Amer. Math. Monthly, 1980, Vol. 87(9): pp. 716-719.
[4] J.A. Bondy, U.S.R. Murty, Graph Theory with Applications, The Macmillan Press LTD., 1976.
[5] R.V. Boppana, S. Chalasani, Fault-tolerant wormhole routing algorithms for mesh networks, IEEE Trans. Computers, July 1995, Vol. 44(7): pp. 848-864.
[6] Y.M. Boura, C.R. Das, Fault-tolerant routing in mesh networks, Proc. of 1995 Int'l Conf. on Parallel Processing, 1995, pp. 106-109.
[7] G. Chartrand, D. Erwin, M. Raines, P. Zhang, Strong distance in strong digraphs, J. Combin. Math. Combin. Comput., 1999, Vol. 31: pp. 33-44.
[8] G. Chartrand, D. Erwin, M. Raines, P. Zhang, On strong distance in strong oriented graphs, Congr. Numer., 1999, Vol. 138: pp. 49-63.
[9] G. Chartrand, S. Tian, Distance in digraphs, Computers Math. Applic., 1997, Vol. 34(11): pp. 15-23.
[10] Meirun Chen, Xiaofeng Guo, Hao Li, Lower and upper orientable strong diameters of graphs satisfying the Ore condition, Applied Mathematics Letters (2009), Vol 22(7), 994-997.
[11] Meirun Chen, Xiaofeng Guo, Lower and upper orientable strong radius and diameter of the cartesian product of complete graphs, to appear in Ars Combinatoria.
[12] M.S. Chen, K.G. Shin, Adaptive fault-tolerant routing in hypercube multicomputers, IEEE Trans. on Computers, 1990, Vol 39(12), pp. 1406-1415.
[13] A.A. Chien, J.H. Kim, Plannar-adaptive routing: Low-cost adaptive networks for multi-processors, Proceedings of the 19th International Symposium on Computer Architecture, 1992, pp. 268-277.
[14] G.M. Chiu and S.P. Wu, A fault-tolerant routing strategy in hypercube multicomputers, IEEE Trans. Compters, 1996, Vol. 45(2): pp. 143-155.
[15] W.-S. Chiue, B.-S. Shieh, On connectivity of the Cartesian product of two graphs, Appl. Math. Comput., 1999, Vol. 102: pp. 129-137.
[16] W. Chou, A.W. Bragg, A.A. Nilsson, The need for adaptive routing in the chaotic and unbalanced traffic environment, IEEE Trans. Comm., Apr. 1981, pp. 481-490.
[17] V. Chv(?)tal, C. Thomassen, Distances in orientations of graphs, Journal of Combinatorial Theory, Series B, 1978, Vol. 24: pp. 61-75.
[18] Intel Corp., A Touchstone DELTA System Description, 1991.
[19] W.J. Dally, "The J-Machine: System support for Actors", Actors Knowledge-Based Concurrent Computing, Hewitt and Agha, eds., MIT Press, 1989.
[20] P. Dankelmann, H. Swart, D. Day, On strong distance in oriented graphs, Discrete Math., 2003, Vol. 266: pp. 195-201.
[21] K. Day, A.-E. Al-Ayyoub, The cross product of interconnection networks, IEEE Trans. Parallel Distributed Systems, 1997, Vol. 8(2): pp. 109-118.
[22] P.T. Gaughan, B.V. Dao, S. Yalamanchili, D.E. Schimmet, Distributed, deadlock-free routing in faulty, pipelined, direct interconnection networks, IEEE Trans. Computers, 1996, Vol. 45(6): pp. 651-665.
[23] C. Glass, L. Ni, Maximally fully adaptive routing in 2D meshes, Proc. 1992 Int'l Conf. Parallel Processing, Aug. 1992, pp. 101-104.
[24] G.J. Glass, L.M. Ni, "Fault-tolerant wormhole routing in meshes without virtual channels", IEEE Trans. Parallel and Distributed Systems, 1996, Vol. 7(6): pp. 620- 636.
[25] G. Gutin, Minimizing and maximizing the diameter in orientations of graphs, Graphs and Combinatorics, 1994, Vol. 10: pp. 225-230.
[26] Libeskind-Hadas, E. Brandt, Origin-based fault-tolerant routing in the mesh, Proc. of the 1st Int'l Symp. on High Performance Computer Architecture, 1995, pp. 102-111.
[27] Yi Huang, Meirun Chen, Lower and upper orientable strong radius and diameter of the Cartesian product of complete paths, Journal of Xinjiang University (National Science Edition), (2009), Vol 26(1), 33-37..
[28] J.S. Juan, C. Huang, On the strong distance problems of pyramid networks, Applied Mathmatics and Computation, 2008, Vol. 195: pp. 154-161.
[29] J.S. Juan, C. Huang, I. Sun, The strong distance problem on the Cartesian product of graphs, Information Processing Letters, 2008, Vol. 107: pp. 45-51.
[30] C. Huang, J.S. Juan, The strong distance problems of toroidal and semitoroidal mesh graphs, in: Proceedings of the 22nd Workshop on Combinatorial Mathematics and Computational Theory, 2005, pp. 192-196.
[31] J.S. Juan, C. Huang, The strong distance problem, Proc. Int. Conf. on Parallel and Distributed Processing Techniques and Applications, PDPTA'04, CSREA 2004, Vol, Ⅱ, pp. 699-705.
[32] K.M. Koh, E.G. Tay, Optimal Orientations of Products of Paths and Cycles, Discrete Applied Mathematics, 1997, Vol. 78: pp. 163-174.
[33] K.M. Koh, E.G. Tay, On optimal orientations of Cartesian products of graphs (Ⅰ), Discrete Mathematics, 1998, Vol. 190: pp. 115-136.
[34] K.M. Koh, E.G. Tay, The diameter of an orientation of a complete multipartite graph, Discrete Mathematics, 1996, Vol. 149: pp. 131-139.
[35] K.M. Koh, E.G. Tay, The minimum diameter of orientations of complete multipartite graphs, Graphs Combin., 1996, Vol. 12: pp. 333-339.
[36] K.M. Koh, E.G. Tay, On optimal orientations of Cartesian products of even cycles and paths, Networks, 1997, Vol. 30: pp. 1-7.
[37] K.M. Koh, E.G. Tay, On optimal orientations of Cartesian products of even cycles, Networks, 1998, Vol. 32: pp. 299-306.
[38] K.M. Koh, E.G. Tay, On optimal orientations of Cartesian products with a bipartite graph, Discrete Applied Mathematics, 1999, Vol. 98: pp. 103-120.
[39] K.M. Koh, E.G. Tay, On optimal orientations of Cartesian products of graphs (Ⅱ): Complete graphs and even cycles, Discrete Mathematics, 2000, Vol. 211: pp. 75-102.
[40] K.M. Koh, E.G. Tay, On optimal orientations of G vertex-multiplications, Discrete Mathematics, 2000, Vol. 219: pp. 153-171.
[41] K.M. Koh, E.G. Tay, On optimal orientations of Cartesian products of trees, Graphs Combin., 2001, Vol. 17: pp. 79-97.
[42] K.M. Koh, E.G. Tay, On a conjecture concerning optimal orientations of the Cartesian product of a triangle and an odd cycle, Discrete Mathematics, 2001, Vol. 232: pp. 153- 161.
[43] K.M. Koh, E.G. Tay, Optimal orientations of graphs and digraphs: A survey, Graphs and Combinatorics, 2002, Vol. 18: pp. 745-756.
[44] Y. Lai, F. Chiang, C. Lin, T. Yu, Strong distance of complete bipartite graphs, The 19th Workshop on Combinatorial Mathematics and Computation Theory, 2002, pp. 12-16.
[45] Y. Lai, J. Hsiao, F. Chiang, Orientable strong radius and diameter of hypercube, The 20th Workshop on Combinatorial Mathematics and Computation Theory, 2003, pp. 143-148.
[46] T.C. Lee, J.P. Hayes, A fault-tolerant communication scheme for hypercube computers, IEEE Trans. Computers, 1992, Vol. 41(10): pp. 1242-1256.
[47] Euler Leonhard, Solutio problemutis ad geometriam situs pertinantis, Academinae Petropolitanae, 8, pp. 128-140, 1736.
[48] A.C. Liang, S. Bhattacharya, W.T. Tsai, Fault-tolerant multicasting on hypercubes, J. Parallel and Distributed computing, 1994, Vol. 23(3): pp. 418-428.
[49] S.L. Lillevik, Thc touchstone 30 gigaflop DELTA prototype, Proc. Sixth Distributed Memory Computing Conf., 1996, pp. 671-677.
[50] D.H. Linder, J.C. Harden, An adaptive and fault tolerant wormhole routing strategy for k-ary n-cubes, IEEE Trans. Computers, 1991, Vol. 40(1) pp. 2-12.
[51] M.N. Lionel and K.M. Philip, A survey of wormhole routing techniques in direct networks, Computer, 1993, Vol. 26, pp. 62-76.
[52] Huifang Miao, Xiaofeng Guo, Lower and upper orientalbe strong radius and strong diameter of complete k-partite graphs, Discrete Applied Mathematics, 2006, Vol, 154 (11): pp. 1606-1614.
[53] Huifang Miao, Xiaofeng Guo, Strong distances in strong oriented complete k-partite graphs, to appear in Ars Combinatoria.
[54] Huifang Miao, Xiaofeng Guo, Optimal strong (k, d)-orientation of Complete k-partite graphs, Discrete Applied Mathematics, 2009, Vol, 157(8): pp. 1729-1736.
[55] J. Miguel-Alonso, J.A. Gregorio, V. Puente, F. Vallejo, and R. Beivide, "Load Unbalance in k-ary n-cube Networks", Proc. 10th Int'l Euro-Par Conf., Sept. 2004.
[56] H.E. Robbins, A theorem on graphs, with an application to a problem of tratfic control, Amer. Math. Monthly, 1939, Vol, 46): pp. 281-283.
[57] C.L. Seitz, W.C. Athas, C.M. Flaig, A.J. Martin, J. Seizovic, W.K. Su, The architecture and programming of the ametek series 2010 multicomputer, Proceedings of the Third Conference on Hypercube Concurrent Computers and Applications, 1988, pp. 33-36.
[58] C.C. Su, K.G. Shin, Adaptive fault-tolerant deadlock-free routing in meshes and hypercubes, IEEE Trans. Computers,IEEE Trans. Comput., 1996, Vol. 45(6), pp. 666- 683.
[59] Y.J. Sub, B.V. Dao, J. Duato, S. Yalamanchili, Software based fault-tolerant oblivious routing in pipelined networks, Proc. 1995 Int'l Conf. Parallel Processing, 1995, pp. 101-105.
[60] D. Wang, A rectilinear-monotone polygonal faulty block model for fault-tolerant minimal routing in mesh, IEEE Trans. Computers, March 2003, Vol. 52(3): pp. 310-320.
[61] J. Wu, "Reliable unicasting in faulty hypercubes using safety levels", IEEE Trans. Comput., 1997, vol. 46(2): pp. 241-247.
[62] J. Wu, Fault-tolerant adaptive and minimal routing in mesh-connected multicomputers using extended safety levels, IEEE Trans. Parallel and Distributed Systems, 2000, Vol. 11(2): pp. 149-159.
[63] D. Xiang, J. Sun, J. Wu, K. Thulasiraman, Fault-tolerant routing in planarly constructed fault blocks, Proc. of 1995 Int'l Conf. on Parallel Processing, 2005, pp. 577-584.