若干全光纤网络的容错路由问题
|
摘要
全光纤网络可定义为弧对称的有向图G(即α是G的一条弧当且仅当它的反向α~(-1)也是G的一条弧)。设R_f(G)是G的一个f-容错路由集(f-fault tolerant routing)。R_f(G)中通过弧α的有向路的数目定义为弧α的负载，G中的最大弧负载定义为在R_f(G)下G的负载，记为π(R_f(G))。G的f-容错弧负载是指在所有路由集R_f(G)下G的负载的最小值，记为π_f(G)，即π_f(G)=(?)π(R_f(G))。称一个路由集R_f(G)为最优的(optimal)如果它满足等式π(R_f(G))=π_f(G)。称路由集R_f(G)为均匀的(balanced)如果在R_f(G)下G中任意两条弧的负载之差至多为1。称一个最优均匀的路由集R_f(G)为平衡的(leveled)如果它的每个子路由集都是最优均匀的。
本文讨论一些特殊图类的容错路由问题及其π_f指标。首先考虑每个部都含有m个点的完全n部图K_({n，m})的容错路由集，其中n=p~r，p为素数。当m=2时，K_({n，m})便为我们熟知的鸡尾酒图CP(n)，此时给出了CP(n)的一组(2n-3)-容错平衡的路由集并由此确定其相应的π_f(CP(n))指标。当n=3时，K_({n，m})为完全三部图且每个部都含有m个点，我们也给出了K_({3，m})的一组(2m-1)-容错平衡的路由集及相应的π_f(K_({3，m})指标。其次构造了Q_n和FH(n)的容错平衡路由集，其相应的f-容错弧负载指标也得到了确定。最后，沿用Arvind Gupta等所采用的设计理论方法，构造了K_n×K_n的一组(2n-3)-容错平衡的路由集并由此给出指标π_f(K_n×K_n)的值。
An all-optical network can be modelled as a symmetric directed graph G, i.e., if an arc (u,v)∈A(G) then (v,u)∈ A(G). We use R_f(G) to denote an f-fault tolerant routing of G and π(R_f(G)) to denote the maximum load on its arcs induced by the routing R_f(G).
The f-tolerant arc-forwarding index π_f(G) of G is defined to be .
We say that a routing R_f(G) is optimal if its load achieves the f-tolerant arc-forwarding index π_f(G); and it is balanced if the difference between loads of any two arcs is at most one. We say that an optimal balanced routing R_f(G) is leveled if each of its subroutings is also optimal and balanced.
In this paper, we first construct an f-fault tolerant routings for K_({n,m}), where K_({n,m}) is the complete n-partite graph with each partition part containing exactly m vertices and where, n is a prime power. In particular, if m = 2 or n = 3, these routings are shown to be leveled and, consequently, the corresponding π_f indexes for these graphs are determined. We also construct the leveled f-fault tolerant routings for hypercube Q_n, folded hypercube FH(n) and product graph K_n ×K_n, respectively. Furthermore, the corresponding π_f indexes of these graphs are given.
本文讨论一些特殊图类的容错路由问题及其π_f指标。首先考虑每个部都含有m个点的完全n部图K_({n，m})的容错路由集，其中n=p~r，p为素数。当m=2时，K_({n，m})便为我们熟知的鸡尾酒图CP(n)，此时给出了CP(n)的一组(2n-3)-容错平衡的路由集并由此确定其相应的π_f(CP(n))指标。当n=3时，K_({n，m})为完全三部图且每个部都含有m个点，我们也给出了K_({3，m})的一组(2m-1)-容错平衡的路由集及相应的π_f(K_({3，m})指标。其次构造了Q_n和FH(n)的容错平衡路由集，其相应的f-容错弧负载指标也得到了确定。最后，沿用Arvind Gupta等所采用的设计理论方法，构造了K_n×K_n的一组(2n-3)-容错平衡的路由集并由此给出指标π_f(K_n×K_n)的值。
An all-optical network can be modelled as a symmetric directed graph G, i.e., if an arc (u,v)∈A(G) then (v,u)∈ A(G). We use R_f(G) to denote an f-fault tolerant routing of G and π(R_f(G)) to denote the maximum load on its arcs induced by the routing R_f(G).
The f-tolerant arc-forwarding index π_f(G) of G is defined to be .
We say that a routing R_f(G) is optimal if its load achieves the f-tolerant arc-forwarding index π_f(G); and it is balanced if the difference between loads of any two arcs is at most one. We say that an optimal balanced routing R_f(G) is leveled if each of its subroutings is also optimal and balanced.
In this paper, we first construct an f-fault tolerant routings for K_({n,m}), where K_({n,m}) is the complete n-partite graph with each partition part containing exactly m vertices and where, n is a prime power. In particular, if m = 2 or n = 3, these routings are shown to be leveled and, consequently, the corresponding π_f indexes for these graphs are determined. We also construct the leveled f-fault tolerant routings for hypercube Q_n, folded hypercube FH(n) and product graph K_n ×K_n, respectively. Furthermore, the corresponding π_f indexes of these graphs are given.
引文
[1] A. Aggarwal, A. Bar-Noy, D. Coppersmith, R. Ramaswami,B. Schieber and M. Sudan, Efficient routing in optical networks, J. of the ACM 46 (1996) 973-1001.
[2] B. Beauquier, C. J. Bermond, L. Gargano, P. Hell, S. Perennes, and U. Vaccaro, Graph Problems arising from wavelength-routing in all-optical networks, in Proc. of the 2nd Workshop on Optics and Computer Science, part of IPPS'97, 1997.
[3] J. Manuch and L. Stacho, On f-wise arc forwarding index and wavelength allocations in faulty all-optical hypercubes, Theor. Informatics and Appl. 37 (2003) 255-270.
[4] B. Beauquier, All-to-all communication for some wavelength-routed all-optical networks, Networks 33 (1999) 179-187.
[5] Arvind Gupta, Jan Manuch, and Ladislav Stacho, Fault Tolerant Forwarding and Optical Indexes: A Design Theory Approach, Springer-Verlag Berlin Heidelberg 197-208, 2004.
[6] N. S. Mendelsohn, On maximal sets of mutuallly orthogonal idempotent Latin squares, Canad. Math. Bull. 14 (1971) 449.
[2] B. Beauquier, C. J. Bermond, L. Gargano, P. Hell, S. Perennes, and U. Vaccaro, Graph Problems arising from wavelength-routing in all-optical networks, in Proc. of the 2nd Workshop on Optics and Computer Science, part of IPPS'97, 1997.
[3] J. Manuch and L. Stacho, On f-wise arc forwarding index and wavelength allocations in faulty all-optical hypercubes, Theor. Informatics and Appl. 37 (2003) 255-270.
[4] B. Beauquier, All-to-all communication for some wavelength-routed all-optical networks, Networks 33 (1999) 179-187.
[5] Arvind Gupta, Jan Manuch, and Ladislav Stacho, Fault Tolerant Forwarding and Optical Indexes: A Design Theory Approach, Springer-Verlag Berlin Heidelberg 197-208, 2004.
[6] N. S. Mendelsohn, On maximal sets of mutuallly orthogonal idempotent Latin squares, Canad. Math. Bull. 14 (1971) 449.