节点文献
若干全光纤网络的容错路由问题
Fault Tolerant Routings in Some All-optical Networks
【作者】 陈美润;
【导师】 钱建国;
【作者基本信息】 厦门大学 , 应用数学, 2006, 硕士
【摘要】 全光纤网络可定义为弧对称的有向图G(即α是G的一条弧当且仅当它的反向α-1也是G的一条弧)。设Rf(G)是G的一个f-容错路由集(f-fault tolerant routing)。Rf(G)中通过弧α的有向路的数目定义为弧α的负载,G中的最大弧负载定义为在Rf(G)下G的负载,记为π(Rf(G))。G的f-容错弧负载是指在所有路由集Rf(G)下G的负载的最小值,记为πf(G),即πf(G)=(?)π(Rf(G))。称一个路由集Rf(G)为最优的(optimal)如果它满足等式π(Rf(G))=πf(G)。称路由集Rf(G)为均匀的(balanced)如果在Rf(G)下G中任意两条弧的负载之差至多为1。称一个最优均匀的路由集Rf(G)为平衡的(leveled)如果它的每个子路由集都是最优均匀的。 本文讨论一些特殊图类的容错路由问题及其πf指标。首先考虑每个部都含有m个点的完全n部图K{n,m}的容错路由集,其中n=pr,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}指标。其次构造了Qn和FH(n)的容错平衡路由集,其相应的f-容错弧负载指标也得到了确定。最后,沿用Arvind Gupta等所采用的设计理论方法,构造了Kn×Kn的一组(2n-3)-容错平衡的路由集并由此给出指标πf(Kn×Kn)的值。
【Abstract】 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 Rf(G) to denote an f-fault tolerant routing of G and π(Rf(G)) to denote the maximum load on its arcs induced by the routing Rf(G).The f-tolerant arc-forwarding index πf(G) of G is defined to be .We say that a routing Rf(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 Rf(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 Qn, folded hypercube FH(n) and product graph Kn ×Kn, respectively. Furthermore, the corresponding πf indexes of these graphs are given.
【Key words】 leveled fault tolerant routing; complete multipartite graph; hypercubes; folded hypercubes; product graph;
- 【网络出版投稿人】 厦门大学 【网络出版年期】2007年 01期
- 【分类号】TN929.11
- 【下载频次】36