|
We consider the following problem. In a wavelength-routing optical network, given a specified logical topology to be embedded on a physical topology (PT) how do we choose the routes on the physical topology so as to minimize the number of distinct wavelengths used in the construction of the logical topology (LT) . The construction of LT may be with or without wavelength changers; both the cases are considered. We formulate an Integer Linear Program (ILP), which is identical to a multicommodity flow problem, to solve the LT construction problem with wavelength changers (WC), the objective being to minimize the distinct wavelengths used on any link of the PT. We note that this is equivalent to solving for minimizing the maximum congestion on any link in a multicommodity flow problem .The solutions of the ILP give an exact solution to the problem with WC. On relaxing the Integer constraints in the above program we get a lower bound on the number of wavelengths required with or without WC. Computational results are presented for the NSFNET , EONNET, ARPANET and randomly generated physical topologies for a complete logical topolgy i,e the logical topology to be embedded is a (N-l) regular directed graph, where the N denotes the number of sources/sinks of traffic. The solutions of the LP relaxation of the above are rounded to give a physical route for every source destination pair under consideration . Given the set of paths we formulate the wavelenght assignment problem, that arise when no WC are used as a graph (vertex) colouring problem and some heuristic algorithms are given to solve for the colouring. We also formulate an ILP to solve the colouring problem once the set of paths are given on which we have route to achieve the desired construction of logical topology.
|
