Data processing: structural design – modeling – simulation – and em – Modeling by mathematical expression
Reexamination Certificate
2000-09-13
2004-08-03
Frejd, Russell (Department: 2123)
Data processing: structural design, modeling, simulation, and em
Modeling by mathematical expression
C398S050000, C398S068000
Reexamination Certificate
active
06772102
ABSTRACT:
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.
REFERENCES:
patent: 5194977 (1993-03-01), Nishio
patent: 5303077 (1994-04-01), Bottle et al.
patent: 5434700 (1995-07-01), Yoo
patent: 5587919 (1996-12-01), Cheng et al.
patent: 5619368 (1997-04-01), Swanson
patent: 5724167 (1998-03-01), Sabella
patent: 5757527 (1998-05-01), Mock
patent: 5825517 (1998-10-01), Antoniades et al.
patent: 5894362 (1999-04-01), Onaka et al.
patent: 5914798 (1999-06-01), Liu
patent: 5923651 (1999-07-01), Struhsaker
patent: 5959749 (1999-09-01), Danagher et al.
patent: 6005698 (1999-12-01), Huber et al.
patent: 6005851 (1999-12-01), Craddock et al.
patent: 6067259 (2000-05-01), Handa et al.
Wan et al., P. Optimal Placement of Wavelength Converters in Trees and Trees of Rings, Eight International Conference on Computer Coomunications and Networks, IEEE, Oct. 1999, pp. 392-397.*
Venugopal et al., K.R. A Heuristic for Placement of Limited Range Wavelength Converters in All-Opitcal Networks, Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies, IEEE, vol. 2, Mar. 1999, pp. 908-915.*
Watanabe et al., T. Vertex Covers and Connected Vertex Covers in 3-Connected Graphs, IEEE International Symposium on Circuits and Systems 1991, Jun. 1991, pp. 1017-1020.*
Yuan et al., S. A New Technique for Optimization Problems in Graph Theory, IEEE Transactions on Computers, vol. 47, Issue 2, Feb. 1998, pp. 190-196.*
Jon Kleinberg and Amit Kumar:Wavelength Conversion in Optical Networks, Proceedings of the 10th ACM-SIAM Symposium On Discrete Algorithms, 566-575, 1999.
Ralph Ballart and Yau-Chau Ching:SONET: Now Its the Standard Optical Network, IEEE Communications Magazine, Mar. 8-15, 1989.
Gordon Wilfong and Peter Winkler:Ring Routing and Wavelength Translation, Proceedings of the 9th ACM-SIAM Symposium On Discrete Algorithms, 333-341, 1998.
Frieder Ophir
Liu Liwu
Wan Peng-Jun
Frejd Russell
Illinois Institute of Technology
Pauley Petersen & Erickson
LandOfFree
Optimal placement of wavelength converters in trees and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Optimal placement of wavelength converters in trees and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal placement of wavelength converters in trees and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3274048