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和故障集F的存活路由图R（G，ρ）/F是由无故障节点组成的有向图，如果从x到y的路由上没有故障，则有向图的有向边是从x到y的。生存路由图的直径（记为D（R（G，ρ）/F））可以作为图G和例程p的容错度量之一。我们证明了我们可以为任何具有三角形的三连通平面图构造路由，使得对于任何故障F（|F| [小于或等于] 2）。我们还证明了对于每个n-节点k-连通图，我们可以构造一个路由λ，使得n [大于或等于] 2k D12 D1，其中路由度为O（k D8 n D8），路由总数为O（k D12 D1 n）DA和D（R（G，λ）/F）[小于或等于] 3， ...更多信息 2、F = F（|F| < k），并且我们可以为每个n-结点的双连通图构造一个路由ρ_n_D_（21）_D_2，其中路由总数为O（n），D（R（G，ρ D21 D2）/{f}）[小于或等于] 2，并利用ρ D21 D2，对每一个路由度为O的n-结点双连通图，给出了路由ρ D22 D2（G，ρ_D_8 n ρ_D_8），对于任意故障f，路由总数为O（n ρ_D_8 n ρ_D_8）和D（R（G，ρ_D_22 ρ_D_2）/{f}）[小于或等于] 2。我们描述了有效的算法划分为k个边不相交的连通子图，其中每一个有一个特殊数量的元素（顶点和边）的K-边连通图。如果每个子图都包含指定的元素（称为基），我们称这个问题为有基的混合k-划分问题（称为k-PART-WB），否则我们称它为无基的混合k-划分问题（称为k-PART-WOB）。这种划分问题可以用来定义最优容错路由。我们证明了k-PART-WB对每个k-边连通图总是有解的，并且我们考虑了无基问题，得到了如下结果：（1）对任意k [大于或等于] 2，k-PART-WOB可以在O（|V|电子邮件：[e-mail]| V| logイD22 D2 BV|电子邮件 *| E|（2）3-PART-WOB可以在O（|V|（3）4-PART-WOB可以在O（|E|对任意3-边连通图G =（V，E），设G =（V，E）是一个3-边连通图，则G =（V，E）是一个3-边连通图.我们还证明了，如果输入图是平面的，所有的k-划分问题，上述可以在线性时间内解决。少

项目成果

K.Wada,W.Chen: "Linear Algorithms for a k-partition problem of planar graphs without specifying bases" Lecture Notes in Computer Science Graph-Theoretic Concepts in Computer Science. 1517. 324-336 (1998)

K.Wada、W.Chen：“不指定基数的平面图 k 划分问题的线性算法”计算机科学中的图论概念讲义。

K. Wada: "Optimal Fault-Tolerant Routing on Surviving Route Graph Model"Proc. of International Conference on Advances in Infrastructure for Electronic Business, Science, and Education on the Internet. (to appear). (2000)

K. Wada：“存活路由图模型上的最优容错路由”Proc。

永田,陳,和田: "(1)3連結平面的グラフに対する最適な耐故障性ルーティング"電子情報通信学会技術報告. COMP-99-3. 17-24 (1999)

Nagata、Chen、Wada：“(1) 3 连接平面图的最佳容错路由”COMP-99-3 (1999)。

K. Wada, W. Chen: "Linear Algorithms for a k-partition Problem of Planar Graphs without Specifying Bases"Lecture Notes in Computer Science. 1517. 324-336 (1998)

K. Wada、W. Chen：“不指定基数的平面图 k 划分问题的线性算法”计算机科学讲义。

K.Wada: "(4)Optimal Fault-Tolerant Routings on Surviving Route Graph Model"Proc,of International Comference on Advances in Infrastructure for Electronic Business,Science,and Education on the Internet. (to appear). (2000)

K.Wada：“（4）存活路由图模型上的最优容错路由”，国际电子商务、科学和教育基础设施进展会议的会议记录。