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

点击翻译按钮获取中文摘要

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