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是一个有向图F，该图由非故障节点组成，如果从X到Y的路由上没有故障，则具有从节点X到节点Y的指向边缘的非故障节点。生存路线图的直径（由d（r（g，ρ）/f表示）可以是图G和常规p的耐故障度量之一。我们表明，我们可以使用三角形的任何触发平面图构造一个路由，该图形与三角形的触发平面图相比，与生存路线的直径相比，您可以在任何情况下（因此）构建2（或者），或者比较forte for for n. fiptals for n fort（| f。每个N节k连接图的路由λ，使得n [大于或相等] 2KII D12，其中途径度为O（K，D8N，D8），途径的总数为O（K，D12N，D1N，D1N）DA和D（r（g，λ）/F）[小于或等于] for for Inter for…for Inter for（r（r（g，λ）/f）， D21n, 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(D8nie D8），路由的总数为O（D8NIE D8）和D（r（g，ρnied22nie d2）/{f}）[对于任何故障f.2而言，小于或等于] 2。我们描述了将k边缘连接的图分配到k边界连接的子图中的有效算法，每个图都有特殊数量的元素（顶点和边缘）。如果每个子图包含指定的元素（称为基础），则将此问题称为混合k分区问题（称为k-part-wb），否则我们将其称为“混合k部分问题”，而没有碱基（称为k-part-wob）。该分区问题可用于定义最佳耐故障路由。我们表明，k-part-wb始终为每个k边缘连接的图都有解决方案，我们在没有基础的情况下考虑问题，我们获得以下结果：（1）对于任何k [大于或相等] 2，k-part-wob可以在O（| v | ii d8 | v | logi d22bv | ii d22bv | ii d8+| e | e | e | e | e | e | e | e | e | e | e | e | e | e | e | e | e | e | ii | ii | |对于每2 edge连接的图G =（V，E）和（3）4部分WOB可以在O（| E | II D12 D1 D1）中求解在O（| V | II D12 D1）中的O（| V | II D12 D1）中。我们还表明，如果输入图是平面，则可以在线性时间内解决上述所有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: "(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）存活路由图模型上的最优容错路由”，国际电子商务、科学和教育基础设施进展会议的会议记录。

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 划分问题的线性算法”计算机科学讲义。