A graph theoretic model and the design of routing algorithms for optical networks

光网络的图论模型和路由算法设计

基本信息

批准号：
10680352
负责人：
WADA Koichi
金额：
$ 1.79万
依托单位：
Nagoya Institute of Technology
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
1998
资助国家：
日本
起止时间：
1998 至 1999
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-10680352/
关键词：
optical network fault tolerance routing diameter of graph planar graph routing table k-partition of graph distributed computing

项目摘要

We constructed a fixed routing model in which fault-tolerance of optical networks can be evaluated and we obtain the following results in the model.1. The surviving route graph R(G,ρ)/F for a graph G, a routing p and a set of faults F is a directed graph consisting of nonfaulty nodes with a directed edge from a node x to a node y if there are no faults on the route from x to y. The diameter of the surviving route graph (denoted by D(R(G,ρ)/F) could be one of the fault-tolerance measures for the graph G and the routine p. We show that we can construct a routing for any triconnected planar graph with a triangle such that a diameter of the surviving route graphs is two (thus optimal) for any faults F(|F|【less than or equal】 2). We also show that we can construct a routing λ for every n-node k-connected graph such that n 【greater than or equal】 2kィイD12ィエD1, in which the route degree is O(kィイD8nィエD8), the total number of routes is O(kィイD12ィエD1n)DA and D(R(G,λ)/F) 【less than or equal】 3 for … More any fault set F(|F| < k) and we can construct a routing ρィイD21ィエD2 for every n-node biconnected graphs, in which the total number of routes is O(n) and D(R(G,ρィイD21ィエD2)/{f}) 【less than or equal】 2 for any fault f, and using ρィイD21ィエD2 a routing ρィイD22ィエD2 for every n-node biconnected graphs, in which the route degree is O(ィイD8nィエD8), the total number of routes is O(nィイD8nィエD8) and D(R(G,ρィイD22ィエD2)/{f}) 【less than or equal】 2 for any fault f.2. We describes efficient algorithms for partitioning a K-edge-connected graph into k edge-disjoint connected subgraphs, each of which has a special number of elements (vertices and edges). If each subgraph contains the specified element (called base), we call this problem the mixed k-partition problem with bases (called k-PART-WB), otherwise we call it the mixed k-partition problem without bases (called k-PART-WOB). This partition problems can be used to define optimal fault-tolerant routings. We show that k-PART-WB always has a solution for every k-edge-connected graph and we consider the problem without bases and we obtain the following results : (1) for any k 【greater than or equal】 2, k-PART-WOB can be solved in O(|V|ィイD8|V|logィイD22ィエD2BV|ィエD8+|E|) time for every 4-edge-connected graph G = (V, E), (2) 3-PART-WOB can be solved in O(|V|ィイD12ィエD1) for every 2-edge-connected graph G = (V,E) and (3) 4-PART-WOB can be solved in O(|E|ィイD12ィエD1) for every 3-edge-connected graph G = (V,E). We also show that if the input graph is planar, all the k-partition problems stated above can be solved in linear time. Less

我们构建了一个可以评估光网络容错性的固定路由模型，并在模型中得到以下结果： 1．图G、路由p和的存活路由图R(G,ρ)/F。故障集 F 是由非故障节点组成的有向图，如果从 x 到 y 的路线上没有故障，则具有从节点 x 到节点 y 的有向边幸存路线图的直径（表示为）。 D(R(G,ρ)/F) 可以是图 G 和例程 p 的容错度量之一。我们表明，我们可以为任何具有直径为的三角形的三连通平面图构建路由。对于任何故障 F(|F|【小于或等于】 2)，幸存的路由图都是两个（因此是最佳的）。我们还表明，我们可以为每个 n 节点 k 连接图构造一个路由 λ，使得 n 【。大于等于】 2kD12D1，其中路由度为 O(kD8nD8)，路由总数为 O(kD12D1n)DA 和 D(R(G,λ) )/F) [小于或等于] 3 对于… 更多任何故障集F(|F| < k) 我们可以为每个 n 节点双连通图构造一个路由，在其中对于任何故障 f，路由总数为 O(n) 且 D(R(G,ρD21D2)/{f}) [小于或等于] 2，并且对每个 n 节点双连接使用 ρD21 D2 路由 D22图中，路线度数为O(D8)，路线总数为对于任何故障 f.2，O(nD8nD8) 和 D(R(G,ρD22D2)/{f}) 【小于或等于】2 我们描述了将 K 边连通图划分为 k 边不相交的有效算法。连接的子图，每个子图都有特定数量的元素（顶点和边）如果每个子图包含指定的元素（称为基），我们将这个问题称为混合k-划分。有基数的问题（称为 k-PART-WB），否则我们将其称为无基数的混合 k 划分问题（称为 k-PART-WOB）。我们证明，该划分问题可用于定义最优容错路由。 k-PART-WB 对于每个 k 边连通图总是有一个解，我们考虑无基问题，得到以下结果： (1) 对于任何 k 【大于或等于】2，k-PART-WOB可以解决在对于每个 4 边连通图 G = (V, E)，(2) 3-PART- WOB 的时间为 O(|V|D8|V|logD22D2BV|D8+|E|) 时间，可以在 O(|V| 中求解DiD12D1) 对于每个 2 边连通图 G = (V,E) 和 (3) 4-PART-WOB 可以求解对于每个 3 边连通图 G = (V,E)，O(|E|DiD12D1) 我们还表明，如果输入图是平面的，则上述所有 k 分区问题都可以在线性时间内解决。