论文部分内容阅读
全光纤网络可定义为弧对称的有向图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）的值。