Abstract:
A method for determining an optimal placement of wavelength converters in an optical network while optimizing bandwidth use in which a skeleton undirected graph of a WDM network is generated, a contraction graph is constructed from the skeleton undirected graph, and a minimum vertex cover of the contraction graph is determined.

Description:
BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     This invention relates to a method for determining the optimal placement of wavelength converters in optical networks and, more particularly, to a method for placing the minimum number of wavelength converters in a fiber optic network, all the while optimizing the bandwidth use. The invention maps minimal converters to support optimal bandwidth utilization in hierarchically structured fiber optic networks, including trees, trees of rings, forests, and any combination thereof connected networks. 
     2. Description of Prior Art 
     In wavelength-routed WDM (wavelengths-division multiplex) optical networks without any wavelength conversion, the wavelength assignment must meet the wavelength continuity constraint; that is, the same wavelength is allocated on all the links in the path established for a connection. However, this constraint can be relaxed when wavelength converters are placed at certain nodes. If a node of the network contains a wavelength converter, any path that passes through this node may change its wavelength. In a network with wavelength converters, the wavelengths are assigned to individual links of all paths, with the restriction that the same wavelength be allocated on all of the links in any subpath that does not pass through a wavelength converter. It is apparent that wavelength assignments in networks with wavelength converters can sometimes be more efficient, that is use fewer wavelengths, than optimal wavelength assignments for the same set of paths when no wavelength converters are available. One extreme example is that if each node contains a wavelength converter, the number of wavelengths required for any routing is reduced down to the natural congestion or load bound, defined to be the maximum number of paths passing through any one link in the network. Another extreme example is placement of a converter at a single arbitrary node in a WDM ring, which ensures that the number of wavelengths required for any routing is equal to its load. 
     This, in turn, raises the question as to the placement of wavelength converters in a WDM network so that any routing can be satisfied using no more wavelengths than if there were wavelength converters at every node. A set S of nodes in a network is defined to be sufficient if, placing converters at the nodes in S, every set of paths can be routed with a number of wavelengths equal to its congestion bound. The minimum sufficient set problem (MSSP) was shown to be NP-complete in general WDM networks. In Kleinberg, J. et al., “Wavelength Conversion in Optical Networks”,  Proceedings  10 th ACM-SIAM Symposium On Discrete Algorithms , 1999, a tight connection between the minimum sufficient set problem in bi-directed graphs and the minimum vertex cover problem in undirected graphs was established. As a consequence of this connection, a simple two-approximation algorithm for a minimum sufficient set problem in bi-directed graphs was obtained. In addition, it is relatively easy to give an approximation-preserving reduction from the minimum vertex cover problem to the minimum sufficient set problem in bi-directed graphs. 
     While the teachings of Kleinberg, J. et al. set forth approximation solutions for general WDM networks, the topologies of most practical WDM networks are not general. In particular, trees and trees of rings are of more practical concrete relevance to the telecommunications industry. For practical reasons, backbone telecommunication networks need to reflect irregularity of geography, non-uniform clustering of users and traffic, hierarchy of services, dynamic growth, etc. In addition, wide-area multiwavelength technology is evolving around current signal wavelength networking architectures and existing fiber networks. These are mainly SONET rings and tree-like interconnection of such rings. (See, for example, Ballart, R. et al., “SONET: Now its the standard optical network”,  IEEE Communications Magazine , Pages 8-15, March 1989.) 
     We have found that the minimum sufficient set problem in these special topologies can be solved in polynomial time and, therefore, is not NP-complete. Our algorithms to find the minimum sufficient sets in these topologies are based on the reduction of the minimum sufficient set problem to the minimum vertex cover problem. These algorithms are very efficient and easy to implement. 
     SUMMARY OF THE INVENTION 
     It is one object of this invention to provide a method for determining the optimal placement of wavelength converters in a fiber optic network so as to utilize the minimum number of wavelength converters while optimizing the bandwidth use. 
     This and other objects of this invention are addressed by a method for determining an optimal placement of wavelength converters in an optical network while optimizing bandwidth use comprising the steps of generating a skeleton undirected graph of a WDM network, constructing a contraction graph from the skeleton undirected graph, and determining a minimum vertex cover of the contraction graph. This method is applicable to WDM networks comprising any of a number of underlining topologies including, but not limited to, trees, rings, trees of rings, forests and any combinations thereof. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     These and other objects and features of this invention will be better understood from the following detailed description taken in conjunction with the drawings wherein: 
     FIG. 1 a  is a diagram showing possible paths which can be taken in a network to get from point X to point Y; 
     FIG. 1 b  is a diagram showing the use of a wavelength converter in the network of FIG. 1 a  as a means for avoiding a congested link in the network; 
     FIG. 2 a  is a diagram of an example of a network comprising a clockwise ring of five nodes and the communication pairs to set up where no wavelength converters are employed; 
     FIG. 2 b  is a diagram showing the network of FIG. 2 a  having a wavelength converter for setting up the communication pairs; 
     FIG. 2 c  is a diagram of the network of FIG. 2 b ,which shows the manner in which the number of wavelengths required is reduced by the wavelength converter from five to three; 
     FIG. 3 is a diagram showing the various types of nodes or vertices in a graph corresponding to a network; 
     FIG. 4 is a diagram showing a contraction graph; 
     FIG. 5 is a diagram showing a leaf root and leaf node arrangement; 
     FIGS. 6 a ,  6   b  and  6   c  are diagrams showing application of the algorithm utilized in the method of this invention to a binary tree; and 
     FIG. 7 is a diagram showing a tree of rings network. 
    
    
     DESCRIPTION OF PREFERRED EMBODIMENTS 
     Definitions 
     As used herein, the term “graph” refers to a set of vertices or nodes connected by edges or lines. Graphs are usually represented by G=(V, E), where V is the set of vertices and E is the set of edges. 
     As used herein, the term “undirected graph” refers to a graph whose edges are unordered pairs of vertices. That is, each edge connects two vertices. 
     As used herein, the term “directed graph” refers to a graph whose edges are ordered pairs of vertices, that is, each edge can be followed from one vertex to the next. 
     As used herein, the term “connected graph” refers to an undirected graph which has a path between every pair of vertices. 
     As used herein, the term “NP” refers to a class of problems for which answers can be checked for correctness by an algorithm whose run time is polynomial in the size of the input. This does not require or imply that an answer can be found quickly, only that any claimed answer can be verified or refuted quickly. NP is the class which a nondeterministic machine accepts in polynomial time. 
     As used herein, the term “NP-complete” refers to a class of problems for which answers can be checked for correctness by an algorithm whose run time is polynomial in the size of the input (it is NP) and no other NP problem is more than a polynomial factor harder. Informally, a problem is NP-complete if answers can be verified quickly and the quick algorithm to solve this problem can be used to solve all other NP problems quickly. A trivial example of NP, but not NP-complete, is finding the AND of two boolean bits. The problem is NP, because one can quickly verify that the answer is correct, but knowing how to AND two bits doesn&#39;t help one quickly find, say, a tour of a graph. So AND is not NP-complete. 
     As used herein, the term “vertex cover” refers to a set of vertices in an undirected graph where every edge connects at least one vertex. The vertex cover problem is to find a minimum size set and is NP-complete. 
     As used herein, the term “polynomial time” refers to the case when the execution time of a computation, p(n), is no more than a polynomial function of the problem size, n. More formally, p(n) equals O(n k ) where k is a constant. 
     As used herein, the term “tree” refers to a data structure accessed beginning at the root node. Each node is either a leaf or an interior node. An interior node refers to or has links to one or more child nodes and is called the parent of its child nodes. Contrary to a physical tree, the root is usually depicted at the top of the structure and the leaves are depicted at the bottom. 
     As used herein, the term “forest” refers to a collection of one or more trees. 
     A WDM network is a bi-directed graph G=(V, E), that is one for which (u, v) is an element of E if and only if (v, u) is an element of E. The undirected graph obtained from G by replacing each bi-directed pair of edges with a single undirected edge is the skeleton of the network G, that is, G s =(V, E′). A set is sufficient in G s  if and only if it is sufficient in G. A vertex v is referred to as a branching node if its degree in G s  is greater than 2, a relay node if its degree in G s  is equal to 2, or a leaf node if its degree in G s  is equal to 1. A graph  10  has leaf nodes  11 , relay nodes  12 , and branch node  13  as shown in FIG. 3. A node of a path P is an internal node in the path if it is not one of the two endpoints. 
     FIG. 1 a  shows a network with three paths ABC, DE, and FG. For a signal to travel from X to Y, the signal can travel any of these three paths. However, if the link BC is congested, it would be desirable to avoid this congested link. By placing a wavelength converter at point A, the signal X at A may be converted enabling the path X→A→D→E→Y as shown in FIG. 1 b.    
     FIG. 2 a  shows a network comprising a clockwise ring having five vertices or nodes. To avoid possible congestion in going from Point  1  to Point  4  by way of Points  2  and  3 , it is desirable to enable a communication between Point  1  and Point  4 . In the example shown in FIG. 2 a , there are five communication pairs to set up—[( 1 ,  4 ), ( 2 ,  5 ), ( 3 ,  1 ), ( 4 ,  2 ), ( 5 ,  3 )]. Because each of these communication pairs shares some link of the ring, they cannot use the same wavelength. That is, each pair needs its own wavelength and, without the use of a wavelength converter, five wavelengths will be required. However, by adding a wavelength converter  20  as shown in FIG. 2 b , the number of wavelengths needed to set up the communication pairs is only three, represented by W 1 , W 2  and W 3 . Thus the frequency for communication pair ( 1 ,  4 ) is represented by W 1 ; the frequency for communication pair ( 2 ,  5 ) is represented by W 2 ; and the frequency for communication pair ( 3 ,  1 ) is represented by W 3 . Without the presence of wavelength converter  20 , the frequency of the signal going to communication pair ( 4 ,  2 ) is the same as the frequency for communication pair ( 4 ,  1 ), represented by W 1 . However, with wavelength converter  20  in place, as the signal passes through wavelength converter  20 , the frequency is switched for communication pair ( 1 ,  2 ) to a different frequency represented by W 2 . A similar situation exists for the communication pair ( 5 ,  3 ). This, instead of five wavelengths, only three wavelengths are required. FIG. 4 is a diagram showing a method for constructing another undirected graph G c  =(V c , E c ) from the graph G s , referred to as the contraction of the graph G s . The vertex set V c  consists of all branching nodes  13  in graph G s . For any two branching nodes u and v, (u, v) is an edge in E c  if and only if there exists a path in G s  between u and v such that all internal nodes in this path are relay nodes. By deleting leaf nodes  11  and relay nodes  12  and merging the relay paths, one arrives at the contraction graph G c  shown in FIG.  4 . 
     As previously stated, any minimum vertex cover of the contracted graph G c  is also a minimum sufficient set of graph G s . To find a minimum sufficient set in graph G s , it is only necessary to find a minimum vertex cover of its contraction, a potentially simpler undirected graph. In general, the minimum vertex cover problem is NP-complete and it has a two-approximation algorithm. It is a fixed-parameter tractable problem whether a graph has a vertex cover of size at most k can be decided with time O(f(k)·p(n)) where p(n) is a polynomial function of n, the number of vertices in G s  and f(k) is a fixed-parameter function. If the graphs are planar, the polynomial-time approximation scheme exists. However, when the graph is a tree or a tree of rings, as discussed hereinbelow, a minimum vertex cover can be found in polynomial time. 
     For WDM networks whose underlying topologies are trees, because any minimum vertex cover of the contraction tree is also a minimum sufficient set of the original network, and because the contraction of any tree is also a tree with the additional property that all internal nodes have degrees of at least three, it is only necessary to identify a minimum vertex cover of the contraction tree. 
     A general polynomial-time algorithm to find minimum vertex covers in forests, a broader set of topologies than trees, is as follows. An internal node of a forest is referred to as a leaf-root if its nodal degree is more than one and one of its neighbors is a leaf node. See FIG. 5 which shows a portion of a network having a leaf node  25  and a leaf root  26 . If a forest has no leaf-roots, then all edges are isolated and its minimum vertex cover consists of one node from each edge. If a forest contains some leaf-roots, then there is a minimum vertex cover which contains all the leaf-roots. This is shown as follows. Let C be a minimum vertex cover of graph G which contains the most number of leaf-roots of graph G, and let u be any leaf-root of graph G that is not in C. Let v be any leaf node that is a neighbor of u. Clearly, v must be in C, for otherwise the edge (u, v) would not be covered by C. 
     Consider C′=(C−{v})∪{u}. Then C′ is also a minimum vertex cover of graph G and contains one more leaf-roots of G than C. If it is assumed that it is not true that there exists a minimum vertex cover of graph G which contains all leaf-roots of G, the selection of C is contradicted. Thus, it must be true that a minimum vertex cover of G exists which contains all leaf-roots of G. 
     FIGS. 6 a ,  6   b  and  6   c  are diagrams showing application of the algorithm used in the method of this invention to a binary tree. Contraction of binary tree  30  (FIG. 6 a ) produces the contraction graph (FIG. 6 b ) having four leaf roots  4 ,  5 ,  6 , and  7 . By combining this set of leaf nodes with node  2  or  3 , one arrives at a minimum sufficient set comprising { 4 ,  5 ,  6 ,  7 ,  2 } or { 4 ,  5 ,  6 ,  7 ,  3 } (FIG. 6 c ). In either case, all edges are covered. So, for the binary tree graph in FIG. 6 a , the minimum sufficient set is C={ 4 ,  5 ,  6 ,  7 ,  2 } or C ={ 4 ,  5 ,  6 ,  7 ,  3 }; and wave converters are placed at these nodes. 
     Let G be any forest and C be any minimum vertex cover of G which contains all leaf-roots of G. Let G′ be the graph obtained from G by removing all leaf-roots of G and their incident edges. G′ is referred to as the residue of G. Let C′ be the vertex set obtained from C by removing all leaf-roots of G. Then G′ is also a forest and C′ is a minimum vertex cover of G′. Applying the proposition that a minimum vertex cover of G exists which contains all leaf-roots of G to G′ results in another minimum vertex cover C″ which contains all leaf-roots of G′. From this, an example algorithm to find the minimum vertex cover of a forest shown in Table 1 is derived. 
     
       
         
               
             
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
             
           
               
                 TABLE 1 
               
               
                   
               
               
                 Algorithm to find a minimum vertex cover of a forest. 
               
               
                   
               
             
             
               
                   
               
             
          
           
               
                 Algorithm: MVC_Forest 
               
             
          
           
               
                 Input: 
                 a forest G; 
               
               
                 Output: 
                 A minimum vertex cover of G; 
               
               
                 begin 
               
             
          
           
               
                   
                 if G has no leaf root 
               
             
          
           
               
                   
                 Return the set consisting of one node from 
               
               
                   
                 each edge; 
               
             
          
           
               
                   
                 else 
               
             
          
           
               
                   
                 add all leaf-roots of G to the vertex cover of 
               
               
                   
                 G; 
               
               
                   
                 form the residue graph G′ of G; 
               
               
                   
                 find the minimum vertex cover of G′ 
               
               
                   
                 recursively; 
               
               
                   
                 add them to the vertex cover of G; 
               
             
          
           
               
                 end 
               
               
                   
               
             
          
         
       
     
     In the algorithm MVC_Forest, all leaf-roots are selected in a single recursive step. One variation is to select only one leaf-root in a step. Such leaf-root can be chosen such that its removal and the removal of its incident edges from a tree G results in another tree. Such selection could potentially simplify the implementation. For both approaches, suitable data structures should be carefully designed to achieve a faster running time. 
     A tree of rings, as shown in FIG. 7, is a widely used interconnection topology in the telecommunications industry. In this topology, each node is within a ring and these rings are interconnected by means of a tree-like topology. It will be apparent to those skilled in the art that the contraction of any tree of rings is also a tree of rings. As the minimum vertex cover of the contraction graph provides an optimal sufficient set of the original graph, a polynomial-time algorithm that finds the minimum vertex cover in an arbitrary tree of rings can be provided. 
     It is well known that there are at least two leaf-nodes in any tree. Similarly, it can be shown that in any tree of rings, there exists at least two rings in which all nodes have a degree of 2 except one whose degree is 3. Such rings are referred to as leaf-rings. The only node in a leaf-ring whose degree is 3 is called a bridging-node. If it is supposed that a leaf-ring contains m nodes, then any minimum vertex cover contains at least        ⌈     m   2     ⌉                          
     nodes in this leaf-ring, where the ceiling of x is the smallest integer greater than or equal to x. As shown hereinbelow, there is always a minimum vertex cover which contains the bridging-node of any leaf-ring. 
     Consider the proposition that, where G is a tree of rings, there exists a minimum vertex cover of G which contains all bridging-nodes of all leaf-rings in G. To show that this proposition is true, assume that it is false and let C be a minimum vertex cover of G which contains the most number of bridging-nodes of G, and let u be any bridging-node of G that is not in C. Let R be the leaf-ring containing the bridging-node u. Then R cannot be a self-loop, for otherwise u must be in any vertex cover of G and, thus, in C too. So, R contains m≧2 nodes, for example, v 1 , v 2 , . . . , V m , where v 1 =u in a clockwise order. Clearly C must contain at least        ⌈     m   2     ⌉                          
     nodes in R, that is,               C   ⋂   R          ≥     ⌈     m   2     ⌉                            
     where |s| is the cardinality of the set s. 
     If 
     
       
           C ′=( C−R )∪{ v   i :1 ≦i≦m,i  is odd} 
       
     
     C′ is also a vertex cover of G, and                     C   ′          =                   C   -   R          +     ⌈     m   2     ⌉                   =                 C        -          C   ⋂   R          +     ⌈     m   2     ⌉                   ≤               C                                     
     Thus, C′ is also a minimum vertex cover of G. On the other hand, C′ contains one more bridging-node of G than C. This contradicts the selection of C as a result of which the proposition must be true. 
     The proof of this proposition suggests a minimum vertex covering of a leaf-ring. Suppose that a leaf-ring R contains m nodes, for example, v 1 , v 2  . . . , v m  in the clockwise order in which v 1  is its bridging node. The set of vertices 
     {v i :1≦i≦m, i is odd} 
     is called a canonical vertex cover of the leaf-ring R. For any leaf-ring R, there is a minimum vertex C of G which contains its canonical vertex cover. Let G−R denote the graph obtained from G by removing all nodes in R and their incident edges. Let C−R denote the vertex set obtained from C by removing the canonical vertex cover of R. Then G−R is also a tree of rings and C−R is a minimum vertex cover of G′. On the other hand, the union of the canonical vertex cover of R and any minimum vertex cover of G−R is also a minimum vertex cover of G. Based on this observation, the algorithm shown in Table 2 can be used to find the minimum vertex cover of a tree of rings. 
     
       
         
               
             
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
             
           
               
                 TABLE 2 
               
               
                   
               
               
                 Algorithm to find a minimum vertex cover of a tree of rings. 
               
               
                   
               
             
             
               
                   
               
             
          
           
               
                 Algorithm: MVC_Tree_Rings 
               
             
          
           
               
                 Input: 
                 A tree of rings G; 
               
               
                 Output: 
                 A minimum vertex cover of G; 
               
               
                 begin 
               
             
          
           
               
                   
                 C = φ; 
               
               
                   
                 while G is not empty 
               
             
          
           
               
                   
                 find a leaf-ring R in G; 
               
               
                   
                 add the canonical vertex cover of R to C; 
               
               
                   
                 G = G − R; 
               
             
          
           
               
                   
                 output C; 
               
             
          
           
               
                 end 
               
               
                   
               
             
          
         
       
     
     The algorithm MVC_Tree_Rings removes one leaf-ring at each step and adds its canonical vertex cover. With carefully selected data structures and implementation, its run-time can be linear in the size of the network. 
     From the algorithm MVC_Tree_Rings, the cardinality of any minimum vertex cover of a tree of rings can be explicitly counted. 
     If we let G=(V, E) be a tree of rings, and k be the number of odd-sized rings in G, then the cardinality of any minimum vertex cover of G is.                 V        +   k     2     .                          
     This can be shown as follows. Let R 1 , R 2  . . . , R 1  be the component rings in G. According to the above algorithm, each ring will evidentially become a leaf-ring and its canonical vertex cover will be added to the minimum vertex cover of G. It should be noted that the canonical vertex covers of different component rings are disjoint. Thereby, the cardinality of any minimum vertex cover of G is:                  ∑     i   =   1     l                     ⌈            R   i          2     ⌉       =                ∑     i   :            R   i             is                 even                                R   i          2       +       ∑     i   :            R   i             is                 odd                       R   i          +   1     2                     =                ∑     i   =   1     l                            R   i          2       +     k   2                   =                1   2            ∑     i   =   1     l               R   i              +     k   2                   =                   V        2     +     k   2                   =                   V        +   k     2                                  
     In addition, the cardinality of any minimum sufficient set is at least half of the number of branching-nodes. To reduce the number of converters needed, the topology should be carefully designed. For example, the topology can be chosen such that the number of branching nodes in each component ring is even. 
     While in the foregoing specification this invention has been described in relation to certain preferred embodiments thereof, and many details have been set forth for purpose of illustration, it will be apparent to those skilled in the art that the invention is susceptible to additional embodiments and that certain of the details described herein can be varied considerably without departing from the basic principles of the invention.